Chapter 10: Processes of Perception and Analysis

Section 11: Traditional Mathematics and Mathematical Formulas

Primitive [Boolean] functions

There are several possible choices of primitive functions that can be combined to represent any Boolean function. In DNF And, Or and Not are used. Nand=Not[And[##]]& alone is also sufficient, as shown on page 619 and further discussed on page 807. (It is indicated by \[Nand] in the main text.) The functions And, Xor and Not are equivalent to Times, Plus and 1-#& for variables modulo 2, and in this case algebraic functions like PolynomialReduce can be used for minimization. (See also page 1102.)

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