Showing Text From Page | View Full page with images

So this means that logic can be set up using just a single operator. But how complicated an axiom system does it then need? The first box in the picture below shows that the direct translation of the standard textbook And, Or, Not axiom system from page 773 is very complicated.

But boxes (b) and (c) show that known alternative axiom systems for logic reduce the size of the axiom system by about a factor of ten. And some further reduction is achieved by manipulating the resulting axioms—leading to the axiom system used above and given in box (d).

But can one go still further? And what happens for example if one just tries to search simple axiom systems for ones that work?

One can potentially test axiom systems by seeing what operators satisfy their constraints, as on page 805. The first non-trivial axiom system that even allows the Nand operator is {(a · a) · (a · a) == a}. And the first axiom system for which Nand and Nor are the only operators allowed that involve 2 possible values is {((b · b) · a) · (a · b) == a}.

But if one now looks at operators involving 3 possible values then it turns out that this axiom system allows ones not equivalent to Nand

Captions on this page:

Axiom systems for basic logic (propositional calculus) formulated in terms of Nand (\[Nand]). The number of operators that occur in these axiom systems is respectively 94, 17, 17, 13, 9, 6, 6, 6. System (a) is a translation of the standard textbook one given on page 773 in terms of And, Or and Not. (b) is based on the Robbins axioms from page 773. (c) is the Sheffer axiom system. (e) is the Meredith axiom system. The other axiom systems were found for this book. (d) was used on page 775. (g) and (h) are as short as is possible. Each axiom system given applies equally well to Nor as well as Nand.

From Stephen Wolfram: A New Kind of Science [citation]