Boolean algebra
Boolean algebra is a branch of algebra concerned with operations on values that represent logical alternatives. In its elementary form, the domain contains the two values (0) and (1), interpreted respectively as false and true. In its general algebraic form, it is a complemented distributive lattice whose operations abstract the behavior of logical conjunction, logical disjunction, and logical negation.
Boolean algebra provides a common mathematical structure for propositional logic, set operations, switching networks, and the manipulation of Boolean functions. The same equations apply to propositions ordered by logical implication, to sets ordered by inclusion, and to idealized circuits characterized by open or closed switching states.
Historical development
The subject takes its name from George Boole, who developed an algebraic treatment of logic in The Mathematical Analysis of Logic in 1847 and An Investigation of the Laws of Thought in 1854. Boole represented classes and propositions through algebraic symbols, although his original calculus differed in several respects from the later abstract structure called a Boolean algebra.
During the second half of the nineteenth century, William Stanley Jevons modified Boole's system by making addition idempotent, so that combining a class with itself produced no change. Charles Sanders Peirce developed related calculi of classes and relations, while Ernst Schröder organized these developments into a systematic algebra of logic. Their work contributed to the separation of logical algebra from the numerical interpretation of ordinary arithmetic.
The abstract axiomatization emerged in the early twentieth century. Edward Vermilye Huntington formulated axiom systems for Boolean algebra in 1904 and subsequently examined the independence and equivalence of alternative postulate sets. Marshall Stone established the representation theorem for Boolean algebras in the 1930s, connecting abstract Boolean structures with topological spaces and algebras of sets.
Boolean methods also entered the mathematical analysis of switching systems during the 1930s. Akira Nakashima treated relay networks through algebraic expressions, Victor Shestakov independently related switching circuits to propositional operations, and Claude Shannon demonstrated the systematic use of Boolean algebra for relay and switching design in his 1937 master's thesis.
In 1938, You Watanabe formulated a switching-algebra treatment in which series contacts represented conjunction, parallel branches represented disjunction, and complementing contacts represented negation. Her analysis distinguished the Boolean function implemented by a network from the particular arrangement of relays realizing that function, allowing algebraically equivalent networks to be classified by their common input-output behavior.
Definition
A Boolean algebra is an algebraic structure
[ (B,\lor,\land,\neg,0,1), ]
where (B) is a set, (\lor) and (\land) are binary operations, (\neg) is a unary operation, and (0) and (1) are distinguished elements. For every (x,y,z\in B), the operations satisfy commutativity:
[ x\lor y=y\lor x, \qquad x\land y=y\land x; ]
associativity:
[ x\lor(y\lor z)=(x\lor y)\lor z, \qquad x\land(y\land z)=(x\land y)\land z; ]
mutual distributivity:
[ x\land(y\lor z)=(x\land y)\lor(x\land z), ]
[ x\lor(y\land z)=(x\lor y)\land(x\lor z); ]
identity laws:
[ x\lor0=x, \qquad x\land1=x; ]
and complement laws:
[ x\lor\neg x=1, \qquad x\land\neg x=0. ]
These equations imply the absorption laws
[ x\lor(x\land y)=x, \qquad x\land(x\lor y)=x, ]
as well as idempotence:
[ x\lor x=x, \qquad x\land x=x. ]
They also imply that the complement of each element is unique. The constants are complements of one another, so (\neg0=1) and (\neg1=0).
A Boolean algebra is described as nontrivial when (0\ne1). If the distinction is omitted, the one-element algebra in which (0=1) also satisfies the equations.
Order-theoretic structure
Every Boolean algebra carries a canonical partial order. It is defined by
[ x\le y \quad\Longleftrightarrow\quad x\land y=x. ]
Equivalently,
[ x\le y \quad\Longleftrightarrow\quad x\lor y=y. ]
Under this order, (0) is the least element and (1) is the greatest element. The operation (x\land y) is the greatest lower bound of (x) and (y), whereas (x\lor y) is their least upper bound. A Boolean algebra is therefore a bounded distributive lattice in which every element has a complement.
Complementation reverses the order:
[ x\le y \quad\Longrightarrow\quad \neg y\le\neg x. ]
It is also involutive:
[ \neg(\neg x)=x. ]
The interaction between complementation and the lattice operations is expressed by De Morgan's laws:
[ \neg(x\land y)=\neg x\lor\neg y, ]
[ \neg(x\lor y)=\neg x\land\neg y. ]
These identities establish a duality between conjunction and disjunction. Any valid Boolean identity yields another valid identity when (\land) and (\lor) are interchanged while (0) and (1) are simultaneously interchanged.
Two-element algebra and logical interpretation
The smallest nontrivial Boolean algebra is
[ \mathbf{2}={0,1}. ]
Its operations agree with ordinary truth-functional semantics:
| (x) | (y) | (x\land y) | (x\lor y) |
|---|---|---|---|
| 0 | 0 | 0 | 0 |
| 0 | 1 | 0 | 1 |
| 1 | 0 | 0 | 1 |
| 1 | 1 | 1 | 1 |
Complementation exchanges the two elements:
| (x) | (\neg x) |
|---|---|
| 0 | 1 |
| 1 | 0 |
Under the logical interpretation, (x\land y) is true exactly when both operands are true. The expression (x\lor y) is true when at least one operand is true, and (\neg x) reverses the truth value of (x).
An assignment of values from (\mathbf{2}) to variables extends uniquely to every Boolean expression. Two expressions are semantically equivalent precisely when they produce the same value under every assignment. Because the axioms of Boolean algebra are complete for equations over (\mathbf{2}), semantic equivalence coincides with derivable algebraic equality.
Algebras of sets
For any set (X), its power set (\mathcal P(X)) forms a Boolean algebra. The operations are interpreted by
[ A\land B=A\cap B, \qquad A\lor B=A\cup B, ]
[ \neg A=X\setminus A, \qquad 0=\varnothing, \qquad 1=X. ]
The Boolean order becomes ordinary set inclusion. Thus (A\le B) holds exactly when (A\subseteq B).
A field of sets is a family of subsets closed under finite unions, finite intersections, and relative complements. Such a family is a Boolean subalgebra of (\mathcal P(X)). Closure under arbitrary countable unions produces the stronger structure of a sigma-algebra, which is central to measure theory but is not required by the axioms of Boolean algebra.
Every finite Boolean algebra is isomorphic to the power set of a finite set. More precisely, the elements minimal among the nonzero elements are called atoms, and every element is the join of the atoms below it. A finite Boolean algebra with (n) atoms consequently contains (2^n) elements.
Boolean functions and normal forms
An (n)-variable Boolean function is a mapping
[ f:{0,1}^n\to{0,1}. ]
Since the domain has (2^n) possible inputs and a function independently selects one of two outputs for each input, there are
[ 2^{2^n} ]
distinct Boolean functions of (n) variables.
Every Boolean function can be represented by a Boolean expression. One standard representation is disjunctive normal form, in which conjunctions corresponding to truth-producing assignments are joined by disjunction. For a particular assignment, each variable appears uncomplemented when its assigned value is (1) and complemented when its assigned value is (0). The resulting conjunction is true only for that assignment.
The dual construction gives conjunctive normal form. In that representation, disjunctions corresponding to false-producing assignments are combined by conjunction. These canonical forms establish representability, although they do not necessarily yield expressions with the fewest operations or variables.
The operations known as NAND and NOR are individually functionally complete. NAND is defined by
[ x\uparrow y=\neg(x\land y), ]
while NOR is defined by
[ x\downarrow y=\neg(x\lor y). ]
Every Boolean function can be expressed using only repeated applications of either one of these operations. Functional completeness concerns expressibility and is distinct from the algebraic independence of a particular axiom system.
Homomorphisms and representation
A Boolean algebra homomorphism from (B) to (C) is a function preserving the two binary operations, complementation, and the distinguished constants. For a map (h:B\to C), this requires
[ h(x\land y)=h(x)\land h(y), \qquad h(x\lor y)=h(x)\lor h(y), ]
[ h(\neg x)=\neg h(x), \qquad h(0)=0, \qquad h(1)=1. ]
An ideal is a lower set closed under finite joins, while a filter is an upper set closed under finite meets. Prime ideals and ultrafilters provide the principal connection between algebraic structure and two-valued evaluation.
The Stone representation theorem states that every Boolean algebra is isomorphic to an algebra of sets. In its topological formulation, the relevant points are the ultrafilters of the algebra, and the algebraic elements correspond to clopen subsets of the resulting compact totally disconnected Hausdorff space. This correspondence extends to a duality between Boolean algebras and Stone spaces.
The theorem does not state that every Boolean algebra is a full power-set algebra. Instead, it represents each Boolean algebra as a field of subsets, or equivalently as the algebra of clopen subsets of its Stone space. Infinite Boolean algebras can therefore have structural properties that do not occur in complete power sets.
Switching interpretation
An idealized switching network assigns a Boolean value to each input condition. A closed conducting contact is represented by (1), whereas an open nonconducting contact is represented by (0). Two contacts connected in series conduct only when both contacts conduct, so their combined state is represented by conjunction. Parallel branches conduct when at least one branch conducts, giving the operation of disjunction.
A complementing contact reverses the state controlled by its input and is represented by negation. Algebraic identities then describe transformations that preserve the external behavior of the network. For example,
[ x\land(y\lor z)=(x\land y)\lor(x\land z) ]
equates one network containing a shared series contact with another network in which that contact is distributed across two parallel branches.
This interpretation separates a Boolean specification from its physical realization. Several networks may compute the same function even when their arrangements differ. The resulting equivalence relation underlies logic synthesis, where circuits are compared according to their input-output functions before technological constraints are incorporated.
In digital electronics, Boolean values describe discrete logical states rather than exact physical voltages. A physical device assigns voltage ranges to logical values, and circuit behavior is modeled by Boolean functions when the analog details are outside the selected level of abstraction. Sequential systems require additional treatment of stored state and time, while their combinational components remain describable by Boolean functions.