Generating the Monotone Boolean Functions
The monotone Boolean functions (events) of n variables are those
that can be constructed using only AND and OR operations (without
NOT's). An elementary way of constructing and counting these
functions is to begin with a function of n=0 variables, which
can only have a constant state, either 0 or 1, with no logical
operations at all. Thus the monotone Boolean functions of 0
variables are
input
states
function null
-------- ----
1 0
2 1
To construct the monotone functions of 1 variable, we can simply
take each monotone function X of 0 variables and adjoin it to any
other monotone function Y of 0 variables such that X U Y = Y. Thus
we can adjoin either 0 or 1 to the function 0, but we can only adjoin
1 to the function 1. This gives the three monotone functions of 1
variable
input
states
function 01
-------- --
1 00
2 01
3 11
To construct the monnotone boolean functions of two variables, we
repeat the process, considering each of the one-variable functions
X in turn, and adjoining to it any other member Y of the one-variable
set such that X U Y = Y. This gives the six monotone Boolean functions
of two variables
input
states
0011
function 0101
-------- ----
1 0000
2 0001
3 0011
4 0101
5 0111
6 1111
Likewise to find the monotone Boolean functions of three variables,
we consider each two-variable monotone function X and adjoin to it
any other two-variable monotone function Y such that X U Y = Y.
This gives the twenty monotone Boolean functions of three variables
input
states
00001111
00110011
function 01010101
-------- --------
1 00000000 20
2 00000001 19
3 00000011 14
4 00000101 14
5 00000111 11
6 00001111 6
7 00010001 14
8 00010011 11
9 00010101 11
10 00010111 9
11 00011111 5
12 00110011 6
13 00110111 5
14 00111111 3
15 01010101 6
16 01010111 5
17 01011111 3
18 01110111 3
19 01111111 2
20 11111111 1
---
168
The numbers in the right hand column indicate, for each of these
functions, how many others on this list absorb it. Thus, if we go
on to the next stage we would produce all 168 of the four-variable
monotone Boolean functions.
In general a Boolean function of n variables consists of the
specification of the output state (either 0 or 1) for each of
the 2^n possible input states. Thus there are 2^(2^n) possible
Boolean functions of n variables. Each of these functions can
be represented by a 2^n bit binary number F in the range from 0 to
2^(2^n) - 1, and each input state can be represented by an n-bit
number I in the range from 0 to 2^n - 1. A given function F is
NON-monotonic if and only if for some two input states I1 and I2
we have F(I1)=1 and F(I2)=0 and (I1 OR I2)=I2. This just expresses
the fact that the output state of a monotonic function cannot turn
FALSE by simply setting one of the input components TRUE, because
this would would yield a negation function.
Incidentally, it's obvious that a string Y cannot absorb X if Y is
numerically less than X, because X must either have more significant
bits or else we can subtract the leading bits from both X and Y, and
then the residual of X must still exceed the residual of Y. Repeating
this process, we must eventually find a bit place that is 1 for X and
0 for Y, and hence Y does not absorb X. Therefore, as shown in the
tables above, the jth element on the list of all M(n) monotone boolean
functions (in ascending numerical order) of n variables can be absorbed
by at most M(n)-j+1 elements (counting itself). It follows trivially
that M(n+1) is less than or equal to M(n)[M(n)+1]/2. However, this
does not represent a particularly strong upper bound on M(n), since it
just says each value is no more than roughly half the square of the
previous value. In contrast, Hansel (1966) proved that M(n) is less
than or equal to 3^C(n) where C(n) denotes the "middle" binomial
coefficient, i.e., 1, 2, 3, 6, 10, 20, 35, 70,.. Hence the upper
bound on M(7) according to Hansel's formula is 1/243 of the square of
the upper bound on M(6), whereas the upper bound based on the trivial
recursive formula is more than 1/2 of the square of the upper bound
on M(6).
In 1981, Korshunov derived asymptotically matching upper and lower
bounds on M(n), which means the ratio of the bounds approaches 1 as
n increases. These bounds give the following approximate expression
for M(n) if n is even:
_ _
C(n) | / -n/2 2 -n-5 -n-4 \ |
M(n) ~ 2 exp| c(n) ( 2 + n 2 - n 2 ) |
|_ \ / _|
where C(n) is the middle binomial coefficient again, and c(n) is the
neighboring binomial coefficient. For example, the 6th row of binomial
coefficients is 1 6 15 20 15 6 1, so we have C(6)=20 and c(6)=15. A
similar expression applies for odd n. This formula gives the
approximate values listed below
n M(n) Korshunov's approximation
--- ----------------------- ---------------------------
2 6 6.59
4 168 185.19
6 7828354 8151600.62
8 56130437228687557907788 5.4279E+22
The problem of enumerating the number of distinct monotone Boolean
functions of n variables was first studied by Dedekind. For a
discussion of this and some related results, see Dedekind's Problem.
Return to MathPages Main Menu
Сайт управляется системой
uCoz