A simple Boolean function maps n binary inputs to a single binary output. There are 2^n possible input states, each of which maps to either 0 or 1 at the output. Thus, the number of possible functions of this form is 2^(2^n). Each of these can be realized by means of the elementary logic operations AND, OR, and NOT. An important subset of all possible Boolean functions is the MONOTONE functions, which consist of those functions that can be realized using just AND and OR operations (no NOT operations). For a more detailed description, see Generating the Monotone Boolean Functions. Dedekind's Problem is to determine the number M(n) of distinct monotone functions of n variables. Although Dedekind first considered this question in 1897, there is still no concise closed-form expression for M(n). As of 1999 the following values are known n M(n) --- ----------------------- 0 2 1 3 2 6 3 20 4 168 5 7581 6 7828354 7 2414682040998 8 56130437228687557907788 Quite a lot of work has been done to prove upper and lower bounds on M(n), but no closed-form expression is known. One way of partitioning the number of distinct monotone functions of n variables is to classify them according to the number of distinct input states that map to the output value of 1. For example, in the case n=5 we have # of events # of events k with k states k with k states 0 1 17 605 1 1 18 580 2 5 19 530 3 10 20 470 4 20 21 387 5 35 22 310 6 61 23 215 7 95 24 155 8 155 25 95 9 215 26 61 10 310 27 35 11 387 28 20 12 470 29 10 13 530 30 5 14 580 31 1 15 605 32 1 16 621 Total 7581 As you would expect, this is a symmetrical partition. Another way of splitting up M(n) is according to the number of "mincuts" needed to specify the function. The mincuts of a monotone function consist of the set of input states in that function, LESS the "redundant" states. (Given two states X and Y, the state X is redundant to Y iff X U Y = Y.) For example, the functions of 5 variables can be divided up as follows: # of distinct functions k with k mincuts 0 1 1 32 2 285 3 1090 4 2020 5 2146 6 1380 7 490 8 115 9 20 10 2 Total 7581 If we had a general formula for the number of distinct monotone functions (of n variables) with k mincuts, we would have a solution of Dedekind's Problem. Let M(n,k) denote this number. Obviously M(n,0) = 1 and M(n,1) = 2^n. In addition, I've noticed that M(n,2) = (2^n)(2^n - 1)/2 - (3^n - 2^n) M(n,3) = (2^n)(2^n - 1)(2^n - 2)/6 - (6^n - 5^n - 4^n + 3^n) Does anyone know of similar formulas for M(n,k) with k > 3? Postscript: For the answer, see Progress on Dedekind's Problem.

Return to MathPages Main Menu