The Wolfram axiom is the result of a computer exploration undertaken by Stephen Wolfram in his A New Kind of Science looking for the shortest single axiom equivalent to the axioms of Boolean algebra (or propositional calculus). The result of his search was an axiom with six Nands and three variables equivalent to Boolean algebra:
With the dot representing the Nand logical operation (also known as the Sheffer stroke), with the following meaning: p Nand q is true if and only if not both p and q are true. It is named for Henry M. Sheffer, who proved that all the usual operators of Boolean algebra (Not, And, Or, Implies) could be expressed in terms of Nand. This means that logic can be set up using a single operator.
Wolfram’s 25 candidates are precisely the set of Sheffer identities of length less or equal to 15 elements (excluding mirror images) that have no noncommutative models of size less or equal to 4 (variables).
Researchers have known for some time that single equational axioms (i.e., 1-bases) exist for Boolean algebra, including representation in terms of disjunction and negation and in terms of the Sheffer stroke. Wolfram proved that there were no smaller 1-bases candidates than the axiom he found using the techniques described in his NKS book. The proof is given in two pages (in 4-point type) in Wolfram's book. Wolfram's axiom is, therefore, the single simplest axiom by number of operators and variables needed to reproduce Boolean algebra.
Sheffer identities were independently obtained by different means and reported in a technical memorandum in June 2000 acknowledging correspondence with Wolfram in February 2000 in which Wolfram discloses to have found the axiom in 1999 while preparing his book. In is also shown that a pair of equations (conjectured by Stephen Wolfram) are equivalent to Boolean algebra.