|
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 monotone 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 2n possible input states. Thus there are 2^(2n) possible Boolean functions of n variables. Each of these functions can be represented by a 2n bit binary number F in the range from 0 to 2^(2n) – 1, and each input state can be represented by an n-bit number I in the range from 0 to 2n – 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 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 3C(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: |
|
|
|
|
|
|
|
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. |
|
|
