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


        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 

        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


       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


       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

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