TOPICS
Search

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.

ABF_0F_1F_2F_3F_4F_5F_6F_7
0000000000
0100001111
1000110011
1101010101
ABF_8F_9F_(10)F_(11)F_(12)F_(13)F_(14)F_(15)
0011111111
0100001111
1000110011
1101010101

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

operationsymbolname
F_00FALSE
F_1A ^ BAND
F_2A ^ !BA AND NOT B
F_3AA
F_4!A ^ BNOT A AND B
F_5BB
F_6A xor BXOR
F_7A v BOR
F_8A nor BNOR
F_9A XNOR BXNOR
F_(10)!BNOT B
F_(11)A v !BA OR NOT B
F_(12)!ANOT A
F_(13)!A v BNOT A OR B
F_(14)A nand BNAND
F_(15)1TRUE

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)

See also

Antichain, Boolean Algebra, Booleans, Complete Product, Conjunction, Dedekind's Problem, Karnaugh Map, Mincut, Monotonic Function

Explore with Wolfram|Alpha

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 Web Resource. https://mathworld.wolfram.com/BooleanFunction.html

Subject classifications