To install click the Add extension button. That's it.

The source code for the WIKI 2 extension is being checked by specialists of the Mozilla Foundation, Google, and Apple. You could also do it yourself at any point in time.

Kelly Slayton
Congratulations on this excellent venture… what a great idea!
Alexander Grigorievskiy
I use WIKI 2 every day and almost forgot how the original Wikipedia looks like.
Live Statistics
English Articles
Improved in 24 Hours
Added in 24 Hours
Show all languages
What we do. Every page goes through several hundred of perfecting techniques; in live mode. Quite the same Wikipedia. Just better.

Minimal axioms for Boolean algebra

From Wikipedia, the free encyclopedia

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:[1]

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

It is one of 25 candidate axioms for this property identified by Stephen Wolfram, by enumerating the Sheffer identities of length less or equal to 15 elements (excluding mirror images) that have no noncommutative models with four or fewer variables, and was first proven equivalent by William McCune, Branden Fitelson, and Larry Wos.[2][3] MathWorld, a site associated with Wolfram, has named the axiom the "Wolfram axiom".[4] McCune et al. also found a longer single axiom for Boolean algebra based on disjunction and negation.[3]

In 1933, Edward Vermilye Huntington identified the axiom

as being equivalent to Boolean algebra, when combined with the commutativity of the OR operation, , and the assumption of associativity, .[5] Herbert Robbins conjectured that Huntington's axiom could be replaced by

which requires one fewer use of the logical negation operator . 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 1996 with the aid of theorem-proving software.[6][7][8] 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 1967 by Carew Arthur Meredith:[9]

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

In 1973, Padmanabhan and Quackenbush demonstrated a method that, in principle, would yield a 1-basis for Boolean algebra.[11] Applying this method in a straightforward manner yielded "axioms of enormous length",[3] 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

which is written in terms of OR and NOT.[3]

YouTube Encyclopedic

  • 1/5
    5 085
    480 999
    191 428
    67 719
    407 272
  • Boolean Axioms
  • Example Problems Boolean Expression Simplification
  • Boolean Algebra 1 – The Laws of Boolean Algebra
  • Simplification of Boolean Expression using Boolean Algebra Rules | Important Question 2
  • Fundamentals of Boolean Algebra



  1. ^ Wolfram, Stephen. "Logic, Explainability and the Future of Understanding". Stephen Worfram Writings.
  2. ^ Wolfram, Stephen (2002). A New Kind of Science. Wolfram Media. ISBN 978-1579550080.
  3. ^ a b c d 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, S2CID 207582048
  4. ^ Rowland, Todd; Weisstein, Eric W. "Wolfram Axiom". MathWorld.
  5. ^ Huntington, E. V. (1933). "New Sets of Independent Postulates for the Algebra of Logic, with Special Reference to Whitehead and Russell's Principia Mathematica". Trans. Amer. Math. Soc. 25: 247–304.
  6. ^ Henkin, Leon; Monk, J. Donald; Tarski, Alfred (1971). Cylindric Algebras, Part I. North-Holland. ISBN 978-0-7204-2043-2. OCLC 1024041028.
  7. ^ McCune, William (1997). "Solution of the Robbins Problem". Journal of Automated Reasoning. 19 (3): 263–276. doi:10.1023/A:1005843212881. S2CID 30847540.
  8. ^ Kolata, Gina (1996-12-10). "Computer Math Proof Shows Reasoning Power". The New York Times. For errata, see McCune, William (1997-01-23). "Comments on Robbins Story". Argonne National Laboratory. Archived from the original on 1997-06-05.
  9. ^ Meredith, C. A.; Prior, A. N. (1968). "Equational logic". Notre Dame J. Formal Logic. 9 (3): 212–226. doi:10.1305/ndjfl/1093893457. MR 0246753.
  10. ^ Meredith, C. A. (1969). "Equational postulates for the Sheffer stroke". Notre Dame J. Formal Logic. 10 (3): 266–270. doi:10.1305/ndjfl/1093893713. MR 0245423.
  11. ^ Padmanabhan, R.; Quackenbush, R. W. (1973). "Equational theories of algebras with distributive congruences". Proc. Amer. Math. Soc. 41 (2): 373–377. doi:10.1090/S0002-9939-1973-0325498-2.
This page was last edited on 18 October 2023, at 00:02
Basis of this page is in Wikipedia. Text is available under the CC BY-SA 3.0 Unported License. Non-text media are available under their specified licenses. Wikipedia® is a registered trademark of the Wikimedia Foundation, Inc. WIKI 2 is an independent company and has no affiliation with Wikimedia Foundation.