| Ron's Site |
| Ramblings in mathematics and computer science |
By Ron Zeno
Wednesday, July 10, 2002Dedekind'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 MathPages.com.
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.
