|
Dedekind's Problem |
|
|
|
A simple Boolean function maps n binary inputs to a single binary output. There are 2n 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^(2n). 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 were 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 one 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) = 2n. In addition, I've noticed that |
|
|
|
|
|
|
|
Does anyone know of similar formulas for M(n,k) with k > 3? |
|
|
|
Postscript: For the answer, see Progress on Dedekind's Problem. |
|
|
