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:

Known solutions:Dedekind's Problem at MathPages.com.

Dedekind's Problem at MathWorld.

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

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.