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's 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).[3]

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[4] 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[5] is also shown that a pair of equations (conjectured by Stephen Wolfram) are equivalent to Boolean algebra.

See also

References

  1. ↑ Stephen Wolfram, A New Kind of Science, 2002, p. 808–811 and 1174.
  2. ↑ Rudy Rucker, A review of NKS, The Mathematical Association of America, Monthly 110, 2003.
  3. ↑ William Mccune, Robert Veroff, Branden Fitelson, Kenneth Harris, Andrew Feist and Larry Wos, Short Single Axioms for Boolean algebra, J. Automated Reasoning, 2002.
  4. ↑ Robert Veroff and William McCune, A Short Sheffer Axiom for Boolean algebra, Technical Memorandum No. 244
  5. ↑ 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

External links

This article is issued from Wikipedia - version of the 8/19/2015. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.