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."