Boolean Function

Consider a Boolean algebra of subsets b(A) generated by a set A, which is the set of subsets of A that can be obtained by means of a finite number of the set operations union, intersection, and complementation. Then each of the elements of b(A) is called a Boolean function generated by A (Comtet 1974, p. 185). Each Boolean function has a unique representation (up to order) as a union of complete products. It follows that there are 2^(2^p) inequivalent Boolean functions for a set A with cardinality p (Comtet 1974, p. 187).

In 1938, Shannon proved that a two-valued Boolean algebra (whose members are most commonly denoted 0 and 1, or false and true) can describe the operation of two-valued electrical switching circuits. The following table gives the truth table for the 2^(2^2)=16 possible Boolean functions of two binary variables.

A B F_0 F_1 F_2 F_3 F_4 F_5 F_6 F_7

0 0 0 0 0 0 0 0 0 0

0 1 0 0 0 0 1 1 1 1

1 0 0 0 1 1 0 0 1 1

1 1 0 1 0 1 0 1 0 1

A B F_8 F_9 F_(10) F_(11) F_(12) F_(13) F_(14) F_(15)

0 0 1 1 1 1 1 1 1 1

0 1 0 0 0 0 1 1 1 1

1 0 0 0 1 1 0 0 1 1

1 1 0 1 0 1 0 1 0 1

The names and symbols for these functions are given in the following table (Simpson 1987, p. 539).

operation symbol name

F_0 0 FALSE

F_1 A ^ B AND

F_2 A ^ !B A AND NOT B

F_3 A A

F_4 !A ^ B NOT A AND B

F_5 B B

F_6 A xor B XOR

F_7 A v B OR

F_8 A nor B NOR

F_9 A XNOR B XNOR

F_(10) !B NOT B

F_(11) A v !B A OR NOT B

F_(12) !A NOT A

F_(13) !A v B NOT A OR B

F_(14) A nand B NAND

F_(15) 1 TRUE

Determining the number of monotonic Boolean functions of n variables is known as Dedekind's problem and is equivalent to the number of antichains on the n-set {1,2,...,n}. Boolean functions can also be thought of as colorings of a Boolean n-cube. The numbers of inequivalent monotonic Boolean functions in n=1, 2, ... variables are given by 2, 3, 5, 10, 30, ...(OEIS A003182).

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

M(n,0) = 1

(1)

M(n,1) = 2^n

(2)

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

(3)

M(n,3) = 1/6(2^n)(2^n-1)(2^n-2)-6^n+5^n+4^n-3^n.

(4)

Explore with Wolfram|Alpha

WolframAlpha

More things to try:

References

Comtet, L. "Boolean Algebra Generated by a System of Subsets." §4.4 in Advanced Combinatorics: The Art of Finite and Infinite Expansions, rev. enl. ed. Dordrecht, Netherlands: Reidel, pp. 185-189, 1974.Shapiro. "On the Counting Problem for Monotone Boolean Functions." Comm. Pure Appl. Math. 23, 299-312, 1970.Simpson, R. E. Introductory Electronics for Scientists and Engineers, 2nd ed. Boston, MA: Allyn and Bacon, 1987.Sloane, N. J. A. Sequence A003182/M0729 in "The On-Line Encyclopedia of Integer Sequences."Wolfram, S. A New Kind of Science. Champaign, IL: Wolfram Media, pp. 616-619, 806-807, and 1096-1097, 2002.

Referenced on Wolfram|Alpha

Boolean Function

Cite this as:

Weisstein, Eric W. "Boolean Function." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/BooleanFunction.html

Boolean Function

See also

Explore with Wolfram|Alpha

References

Referenced on Wolfram|Alpha

Cite this as:

Subject classifications