The book’s said that The NAnd Function has an interesting theoretical property : Each one of the operations And, Or, and Not can be constructed from it, and it alone. Since every Boolean function can be constructed from And, Or, and Not operations using the canonical representation method, it follows that every Boolean function can be constructed from Nand operations alone.
Some of the logic gates presented here are typically referred to as ‘‘elementary’’ or ‘‘basic.’’ At the same time, every one of them can be composed from Nand gates alone. Therefore, they need not be viewed as primitive. Due to this property, NAND and NOR gates are sometimes called “universal gates”.
A NOT gate is made by joining the inputs of a NAND gate. Since a NAND gate is equivalent to an AND gate followed by a NOT gate, joining the inputs of a NAND gate leaves only the NOT part.
An AND gate is made by following a NAND gate with a NOT gate. This gives a NOT NAND.
The Negated AND, NO AND or NAND gate is the opposite of the digital AND gate, and behaves in a manner that corresponds to the opposite of AND gate, as shown in the truth table on the left. A LOW output results only if both the inputs to the gate are HIGH. If one or both inputs are LOW, a HIGH output results.
The NAND gate is significant because any boolean function can be implemented by using a combination of NAND gates. This property is called functional completeness.
Digital systems employing certain logic circuits take advantage of NAND’s functional completeness. In complicated logical expressions, normally written in terms of other logic functions such as AND, OR, and NOT, writing these in terms of NAND saves on cost, because implementing such circuits using NAND gate yields a more compact result than the alternatives.
NAND gates can also be made with more than two inputs, yielding an output of LOW if all of the inputs are HIGH, and an output of HIGH if any of the inputs is LOW. These kinds of gates therefore operate as n-ary operators instead of a simple binary operator. Algebraically, these can be expressed as the function NAND(a, b, …, n), which is logically equivalent to NOT(a AND b AND … AND n).
– The Elements of Computing Systems, Chapter 1