info prev up next book cdrom email home

Boolean Function

A Boolean function in $n$ variables is a function

\begin{displaymath}
f(x_1, \dots, x_n),
\end{displaymath}

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

$\displaystyle M(n,0)$ $\textstyle =$ $\displaystyle 1$  
$\displaystyle M(n,1)$ $\textstyle =$ $\displaystyle 2^n$  
$\displaystyle M(n,2)$ $\textstyle =$ $\displaystyle 2^{n-1}(2^n - 1) - 3^n + 2^n$  
$\displaystyle M(n,3)$ $\textstyle =$ $\displaystyle {\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.




© 1996-9 Eric W. Weisstein
1999-05-26