Dedekind's Problem
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