Minimal axioms for Boolean algebra

In mathematical logic, minimal axioms for Boolean algebra are assumptions which are equivalent to the axioms of Boolean algebra (or propositional calculus), chosen to be as short as possible. For example, an axiom with six NAND operations and three variables is equivalent to Boolean algebra:

$((a|b)\,|\,c)\;|\;(a\,|\,((a|c)\,|\,a))=c$

where the vertical bar represents the NAND logical operation (also known as the Sheffer stroke).

Stephen Wolfram identified this axiom by testing 25 candidate axioms, the set of Sheffer identities of length less or equal to 15 elements (excluding mirror images) that have no noncommutative models with four or fewer variables. The result that this is the shortest axiom using the NAND operation, based on an exhaustive list of identities for this operation, was reported by McCune et al., who also found a longer single axiom for Boolean algebra based on disjunction and negation.

In 1933, Edward Vermilye Huntington identified the axiom

${\neg ({\neg x}\lor {y})}\lor {\neg ({\neg x}\lor {\neg y})}=x$

as being equivalent to Boolean algebra, when combined with the commutativity of the OR operation, $x\lor y=y\lor x$, and the assumption of associativity, $(x\lor y)\lor z=x\lor (y\lor z)$. Herbert Robbins conjectured that Huntington's axiom could be replaced by

$\neg (\neg (x\lor y)\lor \neg (x\lor {\neg y}))=x,$

which requires one fewer use of the logical negation operator $\neg$. Neither Robbins nor Huntington could prove this conjecture; nor could Alfred Tarski, who took considerable interest in it later. The conjecture was eventually proved in 1997 with the aid of theorem-proving software. This proof established that the Robbins axiom, together with associativity and commutativity, form a 3-basis for Boolean algebra. The existence of a 2-basis was established in 1968 by Carew Arthur Meredith:

$\neg ({\neg x}\lor y)\lor x=x,$

$\neg ({\neg x}\lor {\neg y})\lor (z\lor y)=y\lor (z\lor x).$

The following year, Meredith found a 2-basis in terms of the Sheffer stroke:

$(x|x)|(y|x)=x,$

$x|(y|(x|z))=((z|y)|y)|x.$

In 1973, Padmanabhan and Quackenbush demonstrated a method that, in principle, would yield a 1-basis for Boolean algebra. Applying this method in a straightforward manner yielded "axioms of enormous length", thereby prompting the question of how shorter axioms might be found. This search yielded the 1-basis in terms of the Sheffer stroke given above, as well as the 1-basis

$\neg (\neg (\neg (x\lor y)\lor z)\lor \neg (x\lor \neg (\neg z\lor \neg (z\lor u))))=z,$

which is written in terms of OR and NOT.