NAND logic

This article is about NAND logic in the sense of building other logic gates using just NAND gates. For NAND gates, see NAND gate. For NAND in the purely logical sense, see Logical NAND. For logic gates generally, see Logic gate.

The NAND Boolean function has the property of functional completeness. This means that any Boolean expression can be re-expressed by an equivalent expression utilizing only NAND operations. For example, the function NOT(x) may be equivalently expressed as NAND(x,x). In the field of digital electronic circuits, this implies that it is possible to implement any Boolean function using just NAND gates.

The mathematical proof for this was published by Henry M. Sheffer in 1913 in the Transactions of the American Mathematical Society (Sheffer 1913). A similar case applies to the NOR function, and this is referred to as NOR logic.