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