Minimal representations in terms of Nand functions of the first two steps in the evolution of the same cellular automata as on the facing page . … The picture at the top left shows the action of a single Nand function. The next three pictures show how the operations used in DNF formulas can be built up from Nand s.

The first non-trivial axiom system that even allows the Nand operator is {(a ∘ a) ∘ (a ∘ a)  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 Axiom systems for basic logic (propositional calculus) formulated in terms of Nand ( ⊼ ). … Each axiom system given applies equally well to Nor as well as Nand .

Most people seem to find it difficult to think in terms of Nand ( Nand is for example not associative, but then neither is Nor ). And Nand on the face of it rarely seems useful in everyday situations. … Circuit designers sometimes use the linguistic construct " p nand q ".

Logic operations and universality Knowing that the circuits in practical computers use only a small set of basic logic operations—often just Nand —it is sometimes assumed that if a particular system could be shown to emulate logic operations like Nand , then this would immediately establish its universality. … For somehow there also has to be a way to store arbitrarily large amounts of data—and to apply suitable combinations of Nand operations to it. Yet while practical computers have elaborate circuits containing huge numbers of Nand operations, we now know that for example simple cellular automata that can be implemented with just a few Nand operations (see page 619 ) are enough.

And indeed it has been known since before 1900 that both Nand and Nor on their own work—a fact I already used on pages 617 and 775 . … Nand and Nor are the only primitive functions that work on their own.

With up to 6 Nand s and 2 variables none of the 16,896 possible axiom systems of this kind work even up to 3-value operators. But with 6 Nand s and 3 variables, 296 of the 288,684 possible axiom systems work up to 3-value operators, and 100 work up to 4-value operators. … If one looks at axiom systems of the form {…  a, a ∘ b  b ∘ a} the first one that one finds that allows only Nand and Nor with 2-value operators is {(a ∘ a) ∘ (a ∘ a)  a, a ∘ b  b ∘ a} .

Nand and Nor yield the smallest number of theorems.

The picture below shows as an example theorems from the formulation of logic discussed above based on Nand. The theorems of logic formulated in terms of Nand.

Cellular automaton [Nand] formulas For 1 step, the elementary cellular automaton rules are exactly the 256 n = 3 Boolean functions. … They require an average of about 11.6 Nand operations, and a maximum of 27 (achieved by rules 107 and 121). For rule 254 the result after t steps (which is always asymmetric, even though the rule is symmetric) is Nest[{{#, # 〚 2 〛 + 1}, # 〚 2 〛 + 1} &, {{1, 1}, {2, 2}}, t - 2] If explicit copy operations were allowed, then the number of Nand operations after t steps could not increase faster than t 2 for any rule.

It turns out that any rule for blocks of black and white cells can be represented as some combination of just a single type of operation—for example a so-called Nand function of the kind often used in digital electronics. And given this, one can imagine finding for any particular rule the formula that involves the smallest number of Nand functions.