Wolfram axiom
The Wolfram axiom is the result of a computer exploration undertaken by Stephen Wolfram[1] 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[2] of his search was an axiom with six NAND operations and three variables equivalent to Boolean algebra:
- [math]\displaystyle{ ((a|b)\,|\,c) \;|\; (a\,|\,((a|c)\,|\,a)) = c }[/math]
where the vertical bar represents the NAND logical operation (also known as the Sheffer stroke).
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).[3]
Researchers have known for some time that single equational axioms (i.e., 1-bases) exist for Boolean algebra,[4] including representation in terms of disjunction and negation and in terms of the Sheffer stroke. Wolfram proved[5][6] that his equation is a single equational axiom for Boolean algebra, and he proved[7] that there were no smaller single equational axioms for Boolean algebra expressed only with the NAND operation.
Sheffer identities were independently obtained by different means and reported in a technical memorandum[8] 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[9] is also shown that a pair of equations (conjectured by Stephen Wolfram) are equivalent to Boolean algebra.
See also
Notes
- ↑ Wolfram, 2002, p. 808–811 and 1174.
- ↑ Rudy Rucker, A review of NKS, The Mathematical Association of America, Monthly 110, 2003.
- ↑ William Mccune, Robert Veroff, Branden Fitelson, Kenneth Harris, Andrew Feist and Larry Wos, Short Single Axioms for Boolean algebra, J. Automated Reasoning, 2002.
- ↑ Padmanabhan, R.; Quackenbush, R. W. (1973)
- ↑ Wolfram, 2002, p. 810–811.
- ↑ "Proof of Wolfram's Axiom for Boolean Algebra". doi:10.24097/wolfram.65976.data. https://datarepository.wolframcloud.com/resources/Proof-of-Wolframs-Axiom-for-Boolean-Algebra.
- ↑ Wolfram, 2002, p. 1174.
- ↑ Robert Veroff and William McCune, A Short Sheffer Axiom for Boolean algebra, Technical Memorandum No. 244
- ↑ Robert Veroff, Short 2-Bases for Boolean algebra in Terms of the Sheffer stroke. Tech. Report TR-CS-2000-25, Computer Science Department, University of New Mexico, Albuquerque, NM
References
- Padmanabhan, R.; Quackenbush, R. W. (1973). "Equational theories of algebras with distributive congruences". Proc. Amer. Math. Soc. 41: 373-377. doi:10.1090/S0002-9939-1973-0325498-2.
- Wolfram, Stephen (2002). A New Kind of Science. Wolfram Media. ISBN 978-1579550080. http://www.wolframscience.com/nks/.
External links
- Stephen Wolfram, 2002, "A New Kind of Science, online".
- Weisstein, Eric W.. "Wolfram Axiom". http://mathworld.wolfram.com/WolframAxiom.html.
- http://hyperphysics.phy-astr.gsu.edu/hbase/electronic/nand.html
- Weisstein, Eric W.. "Boolean algebra". http://mathworld.wolfram.com/BooleanAlgebra.html.
- Weisstein, Eric W.. "Robbins Axiom". http://mathworld.wolfram.com/RobbinsAxiom.html.
- Weisstein, Eric W.. "Huntington Axiom". http://mathworld.wolfram.com/HuntingtonAxiom.html.
 | ||
| ||
| ||
| ||
| ||
 |
