A Boolean algebra is a bounded lattice that is distributive and in which every element has
a complement. Its meet and join
operations correspond to intersection and union
in a set representation. A Boolean algebra of sets is a family of subsets
of a fixed universal set 
, containing 
and 
and closed under finite union,
intersection, and complementation
relative to 
.
Its partial order is given by 
iff 
in this model. The corresponding Boolean
ring uses symmetric difference for addition
and intersection for multiplication.
For a finite family 
of subsets of 
, the generated Boolean algebra 
consists of the unions
of the nonempty complete products of the generators
and their complements (Comtet 1974, p. 185).
These nonempty complete products are its atoms.
If there are 
such products, then 
has 
elements, with 
.
It has 
elements precisely when all 
complete products are
nonempty.
More generally, a finite Boolean algebra with 
atoms has 
elements. In contrast, the algebra of all Boolean
functions of 
independent Boolean variables has 
elements, because its 
input assignments can be assigned output values independently
(Comtet 1974, p. 186).
Shannon (1938) 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. In modern times, Boolean algebra and Boolean functions are therefore indispensable in the design of computer chips and integrated circuits.
Boolean algebras have a recursive structure apparent in the Hasse diagrams illustrated above for Boolean algebras with 
, 3, 4, and 5 atoms. Each half is
a Boolean algebra with 
atoms (Skiena 1990, pp. 169-170). The Hasse
diagram for a finite Boolean algebra with 
atoms has 
vertices, and for 
its underlying graph is isomorphic
to the 
-hypercube graph.
A Boolean algebra can be formally defined as a set 
of elements 
, 
, ... with the following properties:
1. 
has two binary operations, 
(logical AND, or "wedge")
and 
(logical OR, or "vee"),
which satisfy the idempotent laws
 |
(1)
|
the commutative laws
 |  |  |
(2)
|
 |  |  |
(3)
|
and the associative laws
 |  |  |
(4)
|
 |  |  |
(5)
|
2. The operations satisfy the absorption law
 |
(6)
|
3. The operations are mutually distributive
 |  |  |
(7)
|
 |  |  |
(8)
|
4. 
contains a least element 
and a greatest element 
, represented by the empty set
and universal set in a set model, which satisfy
 |  |  |
(9)
|
 |  |  |
(10)
|
 |  |  |
(11)
|
 |  |  |
(12)
|
5. 
has a unary operation 
of complementation, which obeys the laws
 |  |  |
(13)
|
 |  |  |
(14)
|
(Birkhoff and Mac Lane 1996). This equational definition permits 
, giving the one-element Boolean algebra.
In the slightly archaic terminology of Bell (1986, p. 444), a nontrivial Boolean algebra can be defined as a set 
of elements 
, 
, ... with binary operators 
(or 
; logical OR) and 
(or 
; logical AND) such that
1a. If 
and 
are in the set 
,
then 
is in the set 
.
1b. If 
and 
are in the set 
,
then 
is in the set 
.
2a. There is an element 
(zero) such that 
for every element 
.
2b. There is an element 
(unity) such that 
for every element 
.
3a. 
.
3b. 
.
4a. 
.
4b. 
.
5. For every element 
there is an element 
such that 
and 
.
6. There are at least two distinct elements in the set 
.
Huntington (1933ab) presented the following basis for Boolean algebra:
1. Commutativity: 
.
2. Associativity: 
.
3. Huntington axiom: 
.
H. Robbins then conjectured that the Huntington axiom could be replaced with the simpler Robbins axiom,
 |
(15)
|
The algebra defined by commutativity, associativity, and the Robbins axiom is called Robbins algebra. Computer theorem proving demonstrated that every Robbins algebra satisfies the second Winker condition, from which it follows immediately that all Robbins algebras are Boolean (Kolata 1996, McCune 1997).
Wells, C. F. "Boolean
Expression Manipulation."