From: "G. A. Edgar" Subject: Re: lattice for positive boolean functions Date: Thu, 16 Sep 1999 13:24:37 -0400 Newsgroups: sci.math Perhaps this is what you are looking for... The free distributive lattice with three generators has 18 elements. Birkhoff, LATTICE THEORY (3rd edition) p. 34. Then on p. 61 he considers n generators, and refers to papers of Yamamoto (1954) and Moore & Shannon (1956) In article <7rr69d$lo4$1@netnews.upenn.edu>, Hee H Kwak wrote: > I am new to this field, and I would like to know if there is any paper > regarding to the lattice for the positve boolean function (no-negation > with AND and OR connectives only). For instance, the lattice with > only two variables will be as follows: > > x_1 v x_2 > / \ > / \ > x_1 x_2 > \ / > \ / > x_1 & x_2 > > > I think I have a lattice with three variables. However, I have a > difficulty of getting a lattice with four or more variables. I heard > that the number of positive boolean functions are within 2^n and > 2^2^n, where n is the number of variables. However, I hope there may > be a upper bound for the height of lattice, which may be less than > 2^n. I would like to know if there is a upper bound for the height of > the lattice for positive boolean functions. I would appreciate if any > one can point me where to look for. > -- Gerald A. Edgar edgar@math.ohio-state.edu Department of Mathematics telephone: 614-292-0395 (Office) The Ohio State University 614-292-4975 (Math. Dept.) Columbus, OH 43210 614-292-1479 (Dept. Fax) ============================================================================== From: rld@math.ohio-state.edu (Randall Dougherty) Subject: Re: lattice for positive boolean functions Date: 17 Sep 1999 16:46:43 GMT Newsgroups: sci.math In article <7rr69d$lo4$1@netnews.upenn.edu>, Hee H Kwak wrote: [same quoted article as above --djr] The height is exactly (2^n)-1 (assuming that "height" is defined so that the height of the lattice pictured above is 3; i.e., the height is the length of the longest chain). This is an upper bound because, if f lies below g, then g is satisfied by more input settings (T,F-vectors) than f is, and the number of input settings satisfying a given boolean function with these restrictions must be 1, 2, 3, ... , or (2^n)-1. And here is a way to get a chain of length (2^n)-1: List all the conjunctions of the variables x_i in "odometer order": c_1 = x_1 c_2 = x_2 c_3 = x_1 & x_2 c_4 = x_3 c_5 = x_1 & x_3 c_6 = x_2 & x_3 . . . c_(2^n-1) = x_1 & x_2 & ... & x_n Then, for each k, there is an input setting that makes c_k true but c_j false for all j > k. Hence, if d_k = c_k v c_(k+1) v ... v c_(2^n-1), then the sequence d_1, d_2, ... , d_(2^n-1) is a chain. Randall Dougherty rld@math.ohio-state.edu Department of Mathematics, Ohio State University, Columbus, OH 43210 USA "I have yet to see any problem, however complicated, that when looked at in the right way didn't become still more complicated." Poul Anderson, "Call Me Joe" ============================================================================== From: Yves Moinard Subject: Re: lattice for positive boolean functions Date: Mon, 20 Sep 1999 10:42:43 +0200 Newsgroups: sci.math.research Hee H Kwak wrote: [same quoted article as above --djr] You have a Logic and Computation Group in your University which could probably give you some hints. Otherwise, you may have a look at the marvellous Sloane's electronic encyclopedy of integer sequences (i do not have the url at hand, but it is easy to find it) and look for ``Dedekind numbers''. There you will get a few relevant indications, including useful url's. Yves Moinard