Boolean Algebra - Axiomatizing Boolean Algebra

Axiomatizing Boolean Algebra

The above definition of an abstract Boolean algebra as a set and operations satisfying "the" Boolean laws raises the question, what are those laws? A simple-minded answer is "all Boolean laws," which can be defined as all equations that hold for the Boolean algebra of 0 and 1. Since there are infinitely many such laws this is not a terribly satisfactory answer in practice, leading to the next question: does it suffice to require only finitely many laws to hold?

In the case of Boolean algebras the answer is yes. In particular the finitely many equations we have listed above suffice. We say that Boolean algebra is finitely axiomatizable or finitely based.

Can this list be made shorter yet? Again the answer is yes. To begin with, some of the above laws are implied by some of the others. A sufficient subset of the above laws consists of the pairs of associativity, commutativity, and absorption laws, distributivity of ∧ over ∨ (or the other distributivity law—one suffices), and the two complement laws. In fact this is the traditional axiomatization of Boolean algebra as a complemented distributive lattice.

By introducing additional laws not listed above it becomes possible to shorten the list yet further, see Boolean algebra (logic). In 1933 Edward Huntington showed that if the basic operations are taken to be x∨y and ¬x, with x∧y considered a derived operation (e.g. via De Morgan's law in the form x∧y = ¬(¬x∨¬y)), then the equation ¬(¬x∨¬y)∨¬(¬x∨y) = x along with the two equations expressing associativity and commutativity of ∨ completely axiomatized Boolean algebra. When the only basic operation is the binary NAND operation ¬(x∧y), Stephen Wolfram has proposed in his book A New Kind of Science the single axiom (((xy)z)(x((xz)x))) = z as a one-equation axiomatization of Boolean algebra, where for convenience here xy denotes the NAND rather than the AND of x and y.