Nand expressions If one allows a depth of at most 2n any n -input Boolean function can be obtained just by combining 2-input Nand functions. … The pictures below show the distributions of numbers of Nand operations needed for all 2 2 n n -input Boolean functions. … First, expressions containing progressively more Nand operations were enumerated, and those for functions that had not been seen before were kept.

The symbol ⊼ stands for Nand , sometimes known as Sheffer stroke. The axioms given here do not immediately say whether Nand is commutative (so that (p ⊼ q)  (q ⊼ p) ).

Universal logical functions The fact that combinations of Nand or Nor are adequate to reproduce any logical function was noted by Charles Peirce around 1880, and became widely known after the work of Henry Sheffer in 1913. … Nand and Nor are the only 2-input functions universal in this sense. ( {Equal} can for example reproduce only functions {9, 10, 12, 15} , {Implies} only functions {10, 11, 12, 13, 14, 15} , and {Equal, Implies} only functions {8, 9, 10, 11, 12, 13, 14, 15} .) … Of these, 6 are straightforward generalizations of Nand and Nor .

Nand tautologies At each step every possible transformation rule in the axioms is applied wherever it can. … Pages 818 and 1175 discuss the sequence of all Nand theorems listed in order of increasing complexity.

And with 6 Nand s (as in (g) and (h)) no system of the form {…  a} works even up to k = 4 . … With 3 variables, all 32 cases with 6 Nand s are equivalent to (a ∘ b) ∘ (a ∘ (b ∘ c)) , which is axiom system (f) in the main text. … But the fact that there are fairly few short such equivalences for Nand (see page 818 ) implies that there can be no axiom system for Nand with 6 or less Nand s except the ones discussed above.

Other examples [of minimal systems] Minimal systems achieving particular purposes are shown on page 619 for Boolean functions evaluated with Nand s, pages 759 and 889 for Turing machines, page 1142 for sorting networks, and page 1035 for firing squad synchronization.

The proof shown takes a total of 343 steps, and involves intermediate expressions with as many as 128 Nand s.

Nand theorems The total number of expressions with n Nand s and s variables is: Binomial[2n, n]s n + 1 /(n + 1) (see page 897 ).

Nand = Not[And[##]] & alone is also sufficient, as shown on page 619 and further discussed on page 807 .

With black and white interpreted as True and False , the forms of operators shown here correspond respectively to And , Equal , Implies and Nand .