The amazing NAND

If you are in Hong Kong and you need help for university mathematics courses, please visit www.all-r-math.com.

In daily language and mathematical articles, we frequently use the four basic logical operations: "not", "and", "or", "if-then". However, in electronics, the most fundamental logical operation is "nand" -- the NAND ("not and") operation can be used to implement other logical operations.

The symbol for NAND gate.

The truth table of NAND is $$\begin{array}{c|c|c} p&q&p|q \\ T & T & F \\ T & F & F \\ F & T & F \\ F & F & T \end{array}$$ In other words, the output is false only if both $p$ and $q$ are true. (Note that apart from $p|q$, there are other symbols for NAND, for example $p\bar{\wedge}q$, see here.)

From NAND we can construct the four basic logical operations, which are the building blocks of the symbolic logic:

• Negation: Not $p$. $$\begin{array}{c|c} p&\neg p\\ T & F\\ F & T \end{array}$$ By comparing its truth table with the truth table of $p|p$, we see that $$\neg p = p|p.$$
• Conjunction: $p$ and $q$. $$\begin{array}{c|c|c} p&q&p\wedge q \\ T & T & T \\ T & F & F \\ F & T & F \\ F & F & F \end{array}$$ The output is true only if both $p$ and $q$ are true. It turns out that $$p \wedge q = (p|q)|(p|q).$$ Note also that $p|q = \neg (p\wedge q)$, i.e. "$p$ NAND $q$" is indeed "Not ($p$ AND $q$)".
• Disjunction: $p$ or $q$. $$\begin{array}{c|c|c} p&q&p\vee q \\ T & T & T \\ T & F & T \\ F & T & T \\ F & F & F \end{array}$$ The output is false only if both $p$ and $q$ are false. It turns out that $$p \vee q = (p|p)|(q|q).$$
• Conditional: If $p$ then $q$. $$\begin{array}{c|c|c} p&q&p\rightarrow q \\ T & T & T \\ T & F & F \\ F & T & T \\ F & F & T \end{array}$$ The output is false only if $p$ is true but $q$ is false. It turns out that $$p \rightarrow q = p|(q|q).$$

It is also possible to build all the logical operations from the NOR ("not or") operation.