Boolean Algebra

Origin. Boole introduced algebraic logic (1847, 1854). Stone proved representation theorem (1936). Algebraic foundation of propositional logic. Every Boolean algebra is isomorphic to a field of sets. Universal in digital circuits, databases, and logic.

Models. Algebra of truth values. Two elements: 0 (false), 1 (true). Operations: ∧ (and), ∨ (or), ¬ (not). Laws: commutativity, associativity, distributivity, complements. Models propositional logic algebraically. Foundation for digital design.

Formalism.

Boolean algebra: (B, ∧, ∨, ¬, 0, 1) satisfying:

Axioms:

1. Commutativity: a ∧ b = b ∧ a, a ∨ b = b ∨ a
2. Associativity: (a ∧ b) ∧ c = a ∧ (b ∧ c), (a ∨ b) ∨ c = a ∨ (b ∨ c)
3. Absorption: a ∧ (a ∨ b) = a, a ∨ (a ∧ b) = a
4. Identity: a ∧ 1 = a, a ∨ 0 = a
5. Distributivity: a ∧ (b ∨ c) = (a ∧ b) ∨ (a ∧ c), a ∨ (b ∧ c) = (a ∨ b) ∧ (a ∨ c)
6. Complements: a ∧ ¬a = 0, a ∨ ¬a = 1

Derived laws:

• De Morgan: ¬(a ∧ b) = ¬a ∨ ¬b, ¬(a ∨ b) = ¬a ∧ ¬b
• Double negation: ¬¬a = a
• Idempotence: a ∧ a = a, a ∨ a = a

Order: a ≤ b iff a ∧ b = a iff a ∨ b = b Makes (B, ≤) a complemented distributive lattice.

Stone representation: Every Boolean algebra ≅ subalgebra of powerset algebra. Ultrafilters correspond to points in Stone space.

Free Boolean algebra: On n generators: 2^(2^n) elements. All Boolean functions representable.

Symbols.

Metatheory. Boolean algebras form a variety, closed under subalgebras, products and homomorphic images, and the variety is generated by the two-element algebra 2 — which is why truth tables are a decision procedure, since an equation holds in every Boolean algebra iff it holds in 2. Indeed 2 is the only subdirectly irreducible Boolean algebra, so by Birkhoff's theorem every Boolean algebra is a subdirect product of copies of it. Stone's representation theorem (1936) makes this concrete: every Boolean algebra is isomorphic to the algebra of clopen sets of its space of ultrafilters, hence to a field of sets. The theorem is not constructive — over ZF it is equivalent to the Boolean prime ideal theorem, which is strictly weaker than the axiom of choice. Every finite Boolean algebra is isomorphic to a powerset 2ⁿ, and a complete atomic Boolean algebra is isomorphic to a powerset algebra; atomicity alone is not enough, as the finite–cofinite algebra on an infinite set shows. The free Boolean algebra on n generators has 2^(2ⁿ) elements and is the Lindenbaum–Tarski algebra of classical propositional logic on n variables; on countably many generators it is the unique countable atomless Boolean algebra. Tarski (1949) proved the first-order theory of Boolean algebras decidable.

Applies to. Digital circuit design. Database query optimization (relational algebra). Propositional logic semantics. Set theory operations. SAT solving. Type systems (intersection/union). Switching theory.

Limitations. The structure is equational and propositional: quantification is not expressible, and first-order logic needs cylindric or polyadic operators added on top of the Boolean ones. Complementation forces bivalence — a ∨ ¬a = 1 and ¬¬a = a are axioms — so there is no room for truth-value gaps, degrees, or constructive distinctions, and weakening the complement to a relative pseudocomplement leaves the variety altogether for Heyting algebras. The algebra brings no computational relief: equational validity is TAUT, coNP-complete, and satisfiability is SAT, NP-complete by Cook (1971) and Levin (1973). Infinite Boolean algebras need not be complete — infinite joins may fail to exist, the infinite distributive laws fail in general, and the clopen algebra of a Stone space is closed under finite but not infinite unions. Ultrafilters are unavailable in ZF, their existence being the Boolean prime ideal theorem, so both the representation and the two-valued semantics require a choice principle. And the Lindenbaum quotient identifies all provably equivalent formulas, so no distinction of proof or of content survives it.

© 2026 Lingenic LLC