Proof — Huntington's theorem (Boole's Boolean)

Statement

Boolean algebra is a symbolic logic for encoding logical arguments into a language manipulable by mathematics. Structure from Logic. Huntington formalized the "grammar" of Boolean operations—the three basic operations AND (∧), OR (∨), and NOT (¬)—as an axiomatic system. Boolean algebra underlies digital circuits, SAT, and the foundations of computation.

Formula

x ∧ y, x ∨ y, ¬x

Equation

Idempotent: x² = x; De Morgan: ¬(x∧y) = ¬x∨¬y

Proof sketch

Boole proposed the calculus in The Mathematical Analysis of Logic (1847) and An Investigation of the Laws of Thought (1854). Huntington (1904) axiomatized Boolean algebra, formalizing the grammar of Boolean operations. Shannon (1937) applied it to switching circuits. Boolean logic is the foundation of Boolean satisfiability (SAT) and thus of NP-completeness.

Source

Boole proposed 1847; Huntington, Sets of independent postulates for the algebra of logic, 1904.

Domains

mathematics, computer-science