A **Boolean algebra** (B,∨,∧,¬) is an algebra, that is,
a set and a list of operations, consisting of a nonempty set B, two
binary operations x∨y and x∧y, and a unary operation ¬x,
satisfying the equational laws of Boolean logic.

Example 1. The algebra ({0,1},∨,∧,¬) defined by (i) 0∨0 = 0 and otherwise x∨y = 1, (ii) 1∧1 = 1 and otherwise x∧y = 0, and (iii) ¬0 = 1, and ¬1 = 0.

One of the simpler ways to define the equational laws of Boolean
logic is as those equations holding identically of Example 1,
where ``identically'' means ``for all values of its variables.''
For example x = x∨x holds for all elements x of **2**, which
is easily verified by trying both values of x, namely 0∨0 = 0 and
1∨1 = 1. On the other hand although x = x∨y holds for three of
the four possible combinations of values of x and y, it fails when x =
0 and y = 1, and so x = x∨y is not a Boolean identity.

In this way our first example can serve not only to illustrate the concept but also to complete the definition of Boolean algebra by defining Boolean logic.

Example 2. The algebra (B,∪,∩,~) where B is a nonempty set
of sets including the empty set, ∪ is union, ∩ is intersection,
and for any set X in B, ~X is the *relative complement* of X,
defined as the set of all elements each appearing in some element of
B but not in X. An algebra of this form has been called a *field
of sets* (as distinct from a number field such as the field of
rationals) by G. Birkhoff, who proved that every Boolean algebra
is isomorphic to a field of sets. Example 2 is therefore the most
general example possible of a Boolean algebra, up to isomorphism.

When n variables occur in any such equation, there are only
2^{n} cases to check in order to decide if that equation
is a Boolean identity. It follows that a computer can decide with
2^{n} evaluations of such pairs of terms whether or not an
equation with n variables is a Boolean identity. Whether this can
be decided much faster, specifically in time polynomial in n (e.g.
57n^{14}+13n^{3}+4 steps) was famously shown by Steve
Cook in 1970 to be equivalent to the question of whether P=NP, namely
whether every problem solvable in nondeterministic polynomial time
is also solvable in deterministic polynomial time.

The operations ∨, ∧, and ¬ and constants 0 and 1
constitute a *basis* for the set of all Boolean operations on
**2**. This means that every Boolean operation can be represented
by a term built up using those operations, for example the ternary
operation x∨(y∧z).

This would seem like a definition of ``Boolean operation''
until we notice that actually *every* finitary operation on
**2** can be built in this way. For example there are 16 binary
operations on **2**, all of which can be expressed with terms
written using only ∨, ∧, ¬, 0, and 1. Likewise there are
2^{23} = 256 ternary Boolean operations. In general
there are 2^{2n} Boolean operations of finite
arity n. This gives a very simple definition of a Boolean operation,
namely as any finitary operation on the two-element set {0,1}.

In a class of algebras defined as all the models of a set of equations it is usually the case that some algebras of the class satisfy more equations than just those needed to qualify them for the class. The class of Boolean algebras is unusual in that, with a single exception, every Boolean algebra satisfies exactly the Boolean identities and no more. The exception is the one-element Boolean algebra, which necessarily satisfies every equation, even x = y, and is therefore sometimes referred to as the inconsistent Boolean algebra.

Underlying every Boolean algebra is a partially ordered set
(B,≤). The *partial order* relation is defined by x ≤
y just when x = x∧y, or equivalently when y = x∨y. Given a set
X of elements of a Boolean algebra, an upper bound on X is an element
y such that for every element x of X, x ≤ y, while a lower bound
on X is an element y such that for every element x of X, y ≤ x.

A sup (supremum) of X is a least upper bound on X, namely an upper bound on X that is less or equal to every upper bound on X. Dually an inf (infimum) of X is a greatest lower bound on X. The sup of x and y always exists, being x∨y, and likewise their inf, namely x∧y. The empty sup is 0 (the bottom element) and the empty inf is 1 (top). It follows that every finite set has both a sup and an inf. Infinite sets may or may not have a sup and/or an inf.

Any partial order (B,≤) such that every pair x,y of elements has
both a sup and an inf is called a *lattice*. We write x∧y
for the sup and x∧y for the inf. The lattice is said to be
*distributive* when x∧(y∨z) = (x∧y)∨(x∧z), or
equivalently when x∨(y∧z) = (x∨y)∧(x∨z), since either
law implies the other in a lattice.

Given a lattice with a bottom element 0 and a top element 1, a
pair x,y of elements is called *complementary* when x∧y
= 0 and x∨y = 1, and we then say that y is a complement of x
and vice versa. Any element x of a distributive lattice can have
at most one complement. When every element of a lattice has a
complement the lattice is called complemented. It follows that in
a complemented distributive lattice, the complement of an element
always exists and is unique, making complement a unary operation.
Furthermore every complemented distributive lattice forms a Boolean
algebra, and conversely every Boolean algebra forms a complemented
distributive lattice. This provides an alternative definition of a
Boolean algebra, namely as any complemented distributive lattice.

An *atom* of a Boolean algebra is an element x such that
there exist exactly two elements y satisfying y ≤ x, namely x and 0.
A Boolean algebra is said to be *atomic* when every element is a
sup of some set of atoms (the bottom element is always the empty sup).

Every finite Boolean algebra is atomic, and moreover isomorphic to
the power set 2^{X} of the set X of its atoms, under the
operations of union, intersection, and complement, with 0 and 1
realized by respectively the empty set and X. Conversely every finite
power set forms a Boolean algebra under union, intersection, and
complement.

This converse can be strengthened by dropping ``finite.''
However the converse of this strengthening does not hold: there exist
Boolean algebras that are not isomorphic to any power set under union
and intersection. The smallest infinite power set is 2^{N}
where N is the set of natural numbers, which Cantor showed to be
uncountable. There do however exist countably infinite Boolean
algebras, two examples of which we now give.

1. Finite and confinite sets of integers. A cofinite set of integers is one that omits only finitely many integers. The finite sets are clearly closed under finite union and finite intersection, and likewise the cofinite sets are so closed. The complement (with respect to the set of all integers) of a finite set is cofinite and vice versa. The union of a finite set with a cofinite set is cofinite, while their intersection is finite. Hence this set of sets of integers is closed under all the Boolean operations. These operations furthermore satisfy all the Boolean identities. Hence this set of sets forms a field of sets in the above sense of Birkhoff and hence a Boolean algebra. It is atomic (the atoms are the singletons or one-element sets, and every set is the sup of its elements in this algebra) but not complete (any set X of atoms has a sup if and only if the union of X is either finite or cofinite, so in particular the set of even atoms has no sup).

2. The free Boolean algebra on countably
many generators. Given countably many variables
v_{0},v_{1},v_{2},…, this is the set
of all abstract terms that can be built up from these variables using
the operations x∧y, x∨y, ¬x, and the constants 0 and 1.
Any such term will be finite and so use only finitely many variables.
Terms are *abstract* in the sense that two terms that always
have the same value in **2** are considered to be the same term,
e.g. x∧y and y∧x. Without the abstractness requirement,
x∧y and y∧x would be distinct terms whence they would violate
the Boolean identity x∧y = y∧x when built up from x and y.
The abstractness condition ensures that the Boolean identities
are always satisfied.

The free countable Boolean algebra is atomless. In particular,
for any x there is always a smaller nonzero element, namely
x∧v_{i} where v_{i} is any variable not appearing
in the term x. Surprisingly it can be shown that every countable
atomless Boolean algebra is isomorphic to the free countable Boolean
algebra. Furthermore this algebra is not complete, for example any
set X of variables has a sup if and only if the set is finite.

The free Boolean algebra on n generators, n finite, has
2^{2n} elements. These are the semantically
distinct terms that can be built using n variables. When n = 2 this
algebra has 16 elements, namely the 16 binary Boolean operations.
Because finitely generated Boolean algebras are finite, the
class of Boolean algebras is said to be *locally finite*.
(Contrast this with finitely generated monoids, e.g. the set of all
words on a 2-letter alphabet; the class of monoids is therefore not
locally finite.)

Just as groups have homomorphisms between them, so do Boolean algebras. A Boolean homomorphism is a function h from one Boolean algebra (B,∨,∧,¬,0,1) to another (B',∨',∧',¬',0',1'), such that h(0) = 0', h(1) = 1', h(x∨y) = h(x)∨'h(y), and h(x∧y) = h(x)∧'h(y). From this it follows that h(¬x) = ¬'h(x) (hint: use x∧¬x = 0 and x∨¬x = 1, along with the uniquess of a solution in y to x∨y = 1, x∧y = 0).

The category **Bool** of Boolean algebras has as objects all
Boolean algebras and as morphisms the homomorphisms between them.

There exists a unique homomorphism from **2** to every Boolean
algebra, since any homomorphism must carry bottom to bottem and
top to top. A Boolean algebra with this property is called an
*initial* Boolean algebra. It can be shown that any two
initial Boolean algebras are isomorphic, whence we say *the*
initial Boolean algebra.

In the other direction, there may exist many homomorphisms from
a Boolean algebra B to **2**. Any such homomorphism partitions
B into those elements mapped to 1 and those to 0. The subset of
B consisting of the former is called an *ultrafilter* of B.
When B is finite its ultrafilters pair up with its atoms; one atom is
mapped to 1 and the rest to 0. Each ultrafilter of B thus consists
of an atom of B and all the elements above it; hence exactly half
the elements of B are in the ultrafilter.

For infinite Boolean algebras the notion of ultrafilter becomes considerably more delicate. One simpleminded ultrafilter of the Boolean algebra of finite and cofinite sets of integers is the set of cofinite integers, but there are many more. Likewise the powerset of the integers has among its ultrafilters the set of all subsets containing a given integer; there are countably many of these "standard" ultrafilters, which may be identified with the integers themselves, but there are uncountably many more "nonstandard" ultrafilters. These form the basis for nonstandard mathematics, providing representations for such classically inconsistent objects as infinitesimals and delta functions.

Recall the definition of sup and inf from the section above on the
underlying partial order of a Boolean algebra. A *complete*
Boolean algebra is one every subset of which has both a sup and an inf.

A complete homomorphism is one that preserves all sups that exist,
not just the finite sups, and likewise for infs. A complete atomic
Boolean algebra, or CABA, is a Boolean algebra that is atomic and has
all sups and infs. The category CABA of all CABAs and their complete
homomorphisms is dual to the category of sets and their functions,
meaning that it is equivalent to the opposite of that category (the
*abstract* category resulting from reversing all morphisms).
However the category Bool of Boolean algebras and their homomorphisms
is dual to the category of totally disconnected compact Hausdorff
spaces, or Stone spaces.

Gaifman and Hales independently showed in 1964 that free complete
Boolean algebras did not exist. This suggests that it is impossible
to have an infinitary Boolean logic for lack of terms. However free
CABAs (complete atomic Boolean algebras) *do* exist for all
cardinalities of a set V of generators, namely the power set algebra
2^{2V}, this being the obvious generalization
of the finite free Boolean algebras.

The nonexistence of complete Boolean algebras can be traced to
failure to extend the equations of Boolean logic suitably to all
laws that should hold for infinitary conjunction and disjunction, in
particular the neglect of distributivity in the definition of complete
Boolean algebra. A complete Boolean algebra is called *completely
distributive* when arbitrary conjunctions distribute over arbitrary
disjunctions and vice versa. A complete and completely distributive
Boolean algebra is isomorphic to a CABA, whence there do exist free
complete and completely distributive Boolean algebras. This neatly
rescues infinitary Boolean logic from the fate the Gaifman-Hales
result seemed to consign it to.

There are many other definitions of a Boolean algebra besides the ones already encountered. We list four of the more important here. As it would take us too far afield to develop the necessary background for each, we leave a fuller understanding of these as a project to pursue with the help of a suitable search engine.

(Stone) A Boolean algebra is a ring satisfying x² = x.
A ring satisfying this condition is called a Boolean ring, whence a
Boolean algebra is a Boolean ring, with the ring multiplication as
conjunction and the ring addition as XOR (exclusive-or) or ⊕,
definable as x⊕y = (x∧¬y)∨(¬x∧y), which in
the two-element Boolean algebra can be defined as the truth value of
x ≠ y, and which can also be viewed as addition mod 2. Those who
are picky about the impact of change of base will argue that a Boolean
ring is not itself a Boolean algebra, while acknowledging however
that the category of Boolean rings is equivalent to the category
of Boolean algebras. Others will argue that the choice of basis
should be irrelevant to the concept of Boolean algebra, and that
one should compare algebras on the strength of all the operations
obtained by composition (called a *clone* for ``closed nest of
operations'') and not just the basis. From that perspective Boolean
rings and Boolean algebras have exactly the same operations in their
respective clones, namely all the Boolean operations.

(Lawvere) A Boolean algebra is a product-preserving set-valued
functor F:C→Set from the category C of finite power sets and
*all* functions between them. Because it preserves products,
any such functor is determined by the set F(2) to which F maps the
two-element power set 2. This set then serves as the underlying set
of the Boolean algebra represented by this functor. The functor then
interprets the functions from the finite power sets to the two-element
power set as the Boolean operations on F(2). All other functions
between finite power sets are then interpreted as tuples of Boolean
operations on F(2).

(Stone) A Boolean algebra is the set of all continuous functions from a totally disconnected compact Hausdorff space, or Stone space, to the Sierpinski space (the two-element topological space with three open sets). This is just the reverse direction of the duality mentioned earlier from Boolean algebras to Stone spaces.

(Johnstone) A Boolean algebra is an object of the ind-completion of the category of finite Boolean algebras, aka finite power sets and all meet- and join-preserving functions between them. In this definition Boolean algebras arise as colimits of diagrams of finite Boolean algebras.