Boolean Algebra

Boolean algebra is the branch of algebra in which variables take only two values — typically denoted 0 and 1, or false and true — and the operations are defined by logical rather than arithmetic rules. It was developed by George Boole in the mid-nineteenth century as a formalization of logical inference, and was later recognized by Claude Shannon as directly applicable to the design of electrical switching circuits.

The basic operations are AND (conjunction, analogous to multiplication), OR (disjunction, analogous to addition with the rule 1+1=1), and NOT (negation, or complement). These three operations are functionally complete: any logical function, no matter how complex, can be expressed using only combinations of AND, OR, and NOT.

Boolean algebra is the foundational formalism of digital logic design, computer programming, database query languages, and formal verification. Its power lies in the structural isomorphism between logical propositions and switching circuits: every Boolean expression corresponds to a circuit, and every circuit to an expression.

Functional Completeness and the Sheffer Stroke

The claim that AND, OR, and NOT are functionally complete is correct but not the deepest truth. In 1913, Henry Sheffer proved that a single operation — the NAND operator (not-and, or the Sheffer stroke) — is sufficient to express every Boolean function. NOR (not-or) is similarly complete. This is not merely a curiosity. It is an engineering revelation: every digital circuit in existence, from the simplest inverter to the most complex microprocessor, could in principle be built from nothing but NAND gates. The functional completeness of two-operand NAND means that the manufacturing problem of digital electronics reduces to fabricating one device, in one configuration, in vast numbers. The transistor-as-NAND-gate is the atomic element from which all computation is composed.

Boolean Algebra as the Algebra of Sets

Boolean algebra is structurally identical to the algebra of sets. AND corresponds to intersection, OR to union, NOT to complement, and the distributive laws of Boolean algebra mirror the distributive laws of set theory. This is not an analogy. It is a categorical equivalence: every Boolean algebra is a lattice of sets, and every finite Boolean algebra is isomorphic to the power set of some finite set. The 0 and 1 are the empty set and the universal set. The implication A → B is the subset relation. Boolean algebra is, in this sense, the universal algebra of classification — the formal system that governs how categories combine, exclude, and subsume one another.

This set-theoretic reading explains why Boolean algebra reappears in every domain that deals with classification: database query languages (SQL's WHERE clause is a Boolean expression), information retrieval (Boolean search: term1