Jump to content

Minimal axioms for Boolean algebra

From Wikipedia, the free encyclopedia
This is an old revision of this page, as edited by David Eppstein (talk | contribs) at 19:29, 6 November 2018 (Undid revision 867592443 by Factsmatterandstuff (talk) relevant but its relevance could be explained better and using a more reliable source. Also let's not keep going on and on about Wolfram did this and Wolfram did that, when multiple people did it and Wolfram is not the subject of the article.). The present address (URL) is a permanent link to this revision, which may differ significantly from the current revision.

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). It is an axiom with six NAND operations and three variables equivalent to Boolean algebra:

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

Wolfram found 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 also reported by McCune et al. (2002), who also found a longer single axiom for Boolean algebra based on disjunction and negation.[1]

Researchers have known for some time that single equational axioms (i.e., 1-bases) exist for Boolean algebra,[2] including representation in terms of disjunction and negation and in terms of the Sheffer stroke. Wolfram and McCune et al proved that the Wolfram axiom is a single equational axiom for Boolean algebra, and that there were no smaller single equational axioms for Boolean algebra expressed only with the NAND operation.[1][3]

See also

Notes

  1. ^ a b McCune, William; Veroff, Robert; Fitelson, Branden; Harris, Kenneth; Feist, Andrew; Wos, Larry (2002), "Short single axioms for Boolean algebra", Journal of Automated Reasoning, 29 (1): 1–16, doi:10.1023/A:1020542009983, MR 1940227
  2. ^ Padmanabhan, R.; Quackenbush, R. W. (1973), "Equational theories of algebras with distributive congruences", Proceedings of the American Mathematical Society, 41: 373–377, doi:10.2307/2039097, MR 0325498
  3. ^ "Proof of Wolfram's Axiom for Boolean Algebra". doi:10.24097/wolfram.65976.data.; Wolfram, 2002, p. 810–811.

References


Retrieved from "https://en.wikipedia.org/w/index.php?title=Minimal_axioms_for_Boolean_algebra&oldid=867598637"