TOPICS
Search

Wolfram Axiom


A single axiom that is satisfied only by NAND or NOR must be of the form "something equals a," since otherwise constant functions would satisfy the equation. With up to six NANDs and two variables, none of the 16896 possible axiom systems of this kind work even up to 3-value operators. But with 6 NANDS and 3 variables, 296 of the 288684 possible axiom systems work up to 3-value operators, and 100 work up to 4-value operators (Wolfram 2002, p. 809).

Of the 25 of these that are not trivially equivalent, it then turns out that only the Wolfram axiom

 ((p nand q) nand r) nand (p nand ((p nand r) nand p))=r

and the axiom

 (p nand ((q nand p) nand p)) nand (q nand (r nand p))=q,

where  nand denotes the NAND operator, are equivalent to the axioms of Boolean algebra (Wolfram 2002, pp. 808-811 and 1174). These candidate axioms were identified by S. Wolfram in 2000, who also proved that there were no smaller candidates.


See also

Boolean Algebra, Huntington Axiom, Robbins Axiom

Portions of this entry contributed by Todd Rowland

Explore with Wolfram|Alpha

References

Wolfram, S. A New Kind of Science. Champaign, IL: Wolfram Media, pp. 808-811 and 1174, 2002.

Referenced on Wolfram|Alpha

Wolfram Axiom

Cite this as:

Rowland, Todd and Weisstein, Eric W. "Wolfram Axiom." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/WolframAxiom.html

Subject classifications