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:

Commutativity: a ∧ b = b ∧ a, a ∨ b = b ∨ a
Associativity: (a ∧ b) ∧ c = a ∧ (b ∧ c), (a ∨ b) ∨ c = a ∨ (b ∨ c)
Absorption: a ∧ (a ∨ b) = a, a ∨ (a ∧ b) = a
Identity: a ∧ 1 = a, a ∨ 0 = a
Distributivity: a ∧ (b ∨ c) = (a ∧ b) ∨ (a ∧ c), a ∨ (b ∧ c) = (a ∨ b) ∧ (a ∨ c)
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.

Symbol	Unicode	Name	Meaning
∧	U+2227	Meet/And	Conjunction
∨	U+2228	Join/Or	Disjunction
¬	U+00AC	Complement	Negation
0	—	Zero/False	Bottom
1	—	One/True	Top
≤	U+2264	Order	Boolean order
⊕	U+2295	XOR	Symmetric difference
·	—	Product	Alternative for ∧

Metatheory. Boolean algebras form a variety (equational class). Complete and decidable theory. Stone duality: Boolean algebras ↔ Stone spaces. Every finite Boolean algebra = 2^n for some n. Lindenbaum algebra of propositional logic is Boolean. Atomicity: 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.

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. Only propositional, not first-order. Cannot express "for all" or "exists." Two-valued: no degrees of truth. Complete algebra but limited expressiveness. Extensions: modal algebras, Heyting algebras. Infinite Boolean algebras more complex.