Site hosted by Build your free website today!
Ron's Site
Ramblings in mathematics and computer science

A quick introduction to Dedekind's problem

By Ron Zeno
Wednesday, July 10, 2002

Dedekind's Problem is to determine the number M(n) of distinct monotone Boolean functions (functions that do not include the NOT operation) of n variables.

For an introduction to Dedekind's problem, see:

Dedekind's Problem at

Dedekind's Problem at MathWorld.

Sequence A000372 in the On-Line Encyclopedia of Integer Sequences.

Known solutions:
n M(n)
0 2
1 3
2 6
3 20
4 168
5 7,581
6 7,828,354
7 2,414,682,040,998
8 56,130,437,228,687,557,907,788

Copyright 2002 Ron Zeno

Computing M(n):

It could take over a month just to compute M(7) on a high-end personal computer.  Computing M(8) must have taken a huge amount of computing power.

Here is the source to a small C++ program that computes M(2) through M(6), plus M(7) if you have the patience and computing power.