Chapter 12: The Principle of Computational Equivalence

Section 9: Implications for Mathematics and Its Foundations

Logic in languages

Human languages always seem to have single words for And, Or and Not. A few have distinct words for Or and Xor: examples are Latin with vel and aut and Finnish with vai and tai. Nor is somewhat rare, though Dutch has noch and Old English ne. (Modern English has only the compound form neither ... nor.) But remarkably enough it appears that no ordinary language has a single word for Nand. The reason is not clear. 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. But perhaps these are just reflections of the historical fact that Nand has never been familiar from ordinary languages.

Essentially all computer languages support And, Or and Not as ways to combine logical statements; many support And, Or and Xor as bitwise operations. Circuit design languages like Verilog and VHDL also support Nand, Nor and Xnor. (Nand is the operation easiest to implement with CMOS FETs—the transistors used in most current chips; it was also implemented by pentode vacuum tubes.) Circuit designers sometimes use the linguistic construct "p nand q".

The Laws of Form presented by George Spencer Brown in 1969 introduce a compact symbolic notation for Nand with any number of arguments and in effect try to develop a way of discussing Nand and reasoning directly in terms of it. (The axioms normally used are essentially the Sheffer ones from page 773.)

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