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: atomic BA ≅ powerset.

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.