A proof that the axiom system {((b ∘ c) ∘ a) ∘ (b ∘ ((b ∘ a) ∘ b)) a} given as example (g) on page 808 can reproduce the Sheffer axiom system (c), and is thus a complete axiom system for logic. The proof involves taking the original axiom [A] and using it to establish a sequence of lemmas [Ln], from which it is eventually possible to prove the three Sheffer axioms [Tn]. In each part of the proof each line can be obtained from the previous one just as on page 775 by applying the axiom or lemma indicated. Explicit operators have been omitted to allow expressions to be printed more compactly. The proof shown takes a total of 343 steps, and involves intermediate expressions with as many as 128 Nands. It is quite possible that the proof could be considerably shortened. Note that any proof can always be recast without lemmas, but will usually then be much longer.

Exportable Images for This Page:

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