Consider a Boolean algebra of subsets 
generated by a set 
, which is the set of subsets of 
that can be obtained by means of a finite number of the set
operations union, intersection, and complementation. Then each of the elements of
is called a Boolean function generated
by 
(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 
inequivalent Boolean functions for a set 
with cardinality 
(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 
possible Boolean functions of two binary variables.
The names and symbols for these functions are given in the following table (Simpson 1987, p. 539).
Determining the number of monotonic Boolean functions of 
variables is known as Dedekind's
problem and is equivalent to the number of antichains
on the 
-set
. Boolean functions can also
be thought of as colorings of a Boolean 
-cube. The numbers of inequivalent monotonic Boolean functions
in 
,
2, ... variables are given by 2, 3, 5, 10, 30, ...(OEIS A003182).
Let 
denote the number of distinct monotonic Boolean functions of 
variables with 
mincuts. Then
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
Cite this as:
Weisstein, Eric W. "Boolean Function." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/BooleanFunction.html