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).
AND NOT 
XNOR 
OR NOT 
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)
|
