Boolean Function

A Boolean function in $n$ variables is a function

$$f(x_1, \dots, x_n),$$

where each $x_i$ can be 0 or 1 and $f$ is 0 or 1. Determining the number of monotone Boolean functions of $n$ variables is known as Dedekind's Problem. The number of monotonic increasing Boolean functions of $n$ variables is given by 2, 3, 6, 20, 168, 7581, 7828354, ... (Sloane's A000372, Beeler et al. 1972, Item 17). The number of inequivalent monotone Boolean functions of $n$ variables is given by 2, 3, 5, 10, 30, ...(Sloane's A003182).

Let $M(n,k)$ denote the number of distinct monotone Boolean functions of $n$ variables with $k$ mincuts. Then

$$M(n,0) = 1$$

$$M(n,1) = 2^n$$

$$M(n,2) = 2^{n-1}(2^n - 1) - 3^n + 2^n$$

$$M(n,3) = {\textstyle{1\over 6}} (2^n)(2^n - 1)(2^n - 2) - 6^n + 5^n + 4^n - 3^n.$$

References

Beeler, M.; Gosper, R. W.; and Schroeppel, R. HAKMEM. Cambridge, MA: MIT Artificial Intelligence Laboratory, Memo AIM-239, Feb. 1972.

Sloane, N. J. A. Sequences A003182/M0729 and A000372/M0817 in ``An On-Line Version of the Encyclopedia of Integer Sequences.'' http://www.research.att.com/~njas/sequences/eisonline.html and Sloane, N. J. A. and Plouffe, S. The Encyclopedia of Integer Sequences. San Diego: Academic Press, 1995.