Textbook of AI

Boolean algebra is the algebra of two-valued logic, founded by George Boole in An Investigation of the Laws of Thought (1854). Variables take values $0$ (false) and $1$ (true); the basic operations are AND ($\cdot$ or $\wedge$, returning $1$ iff both inputs are $1$), OR ($+$ or $\vee$, returning $1$ iff at least one input is $1$) and NOT ($\neg$ or overbar, flipping the value). The standard laws make Boolean algebra a complemented distributive lattice:

• Commutativity: $x \cdot y = y \cdot x$, $x + y = y + x$
• Associativity: $(x \cdot y) \cdot z = x \cdot (y \cdot z)$
• Distributivity: $x \cdot (y + z) = (x \cdot y) + (x \cdot z)$
• Idempotency: $x \cdot x = x$, $x + x = x$
• Complementation: $x \cdot \neg x = 0$, $x + \neg x = 1$
• De Morgan's laws: $\neg(x \cdot y) = \neg x + \neg y$, $\neg(x + y) = \neg x \cdot \neg y$

Any Boolean function $f: \{0,1\}^n \to \{0,1\}$ can be written in disjunctive normal form (a sum of products) or conjunctive normal form (a product of sums). Functional completeness is achieved with $\{\text{AND}, \text{OR}, \text{NOT}\}$, or with the single operators NAND or NOR, which is why CMOS digital circuits are typically built from NAND/NOR gates.

Claude Shannon's 1937 master's thesis, A Symbolic Analysis of Relay and Switching Circuits, recognised that Boolean algebra exactly described the behaviour of relay switching circuits, connecting Boole's nineteenth-century logic to twentieth-century engineering. Every logic gate in every digital circuit is a realisation of a Boolean operation; every digital circuit can be specified by a Boolean expression and minimised by Boolean algebraic manipulation. Practical minimisation tools include Karnaugh maps for small functions, the Quine--McCluskey algorithm for moderate ones, and modern logic synthesis software (e.g. ABC, Synopsys Design Compiler) for VLSI designs with billions of gates.

In AI and theoretical computer science, Boolean satisfiability (SAT) -- deciding whether a Boolean formula has any satisfying assignment -- is the prototypical NP-complete problem (Cook--Levin theorem, 1971). Modern SAT solvers using conflict-driven clause learning (CDCL) routinely handle formulas with millions of variables and underlie hardware verification, automated planning, software model checking, cryptanalysis and many heuristic search systems. Variants such as MaxSAT, #SAT (model counting) and QBF extend the framework to optimisation, probabilistic inference and game-theoretic reasoning.

Boolean algebra also underpins propositional logic, the simplest fragment of mathematical logic, and through it the entire edifice of symbolic AI: rule-based expert systems, theorem provers, description logics and answer-set programming all operate on extensions of the Boolean substrate. Even modern neural networks ultimately compute through Boolean circuits, since their floating-point arithmetic is implemented by hundreds of millions of NAND gates.