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.
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 |
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).
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
(1)
| |||
(2)
| |||
(3)
| |||
(4)
|