Question

Prove that the NAND gate is universal by showing how to build the AND, OR, and NOT functions using a two-input NAND gate.

Short answer

According to DeMorgan’s law, the complement of the OR of two values is equal to the AND of their complements and the complement of the AND of two values is equal to the OR of their complements.

Using this law, the AND function for two values X and Y can be built as$XY=\overline{\overline{X·Y}}$

The OR function can be built as$X+Y=\overline{\overline{X}·\overline{Y}}$.

The NOT function can be built as$\overline{X}=\overline{X·X}$.

Step-by-step solution

DeMorgan’s theorem is a set of rules for boolean expressions for AND, OR, NOT functions

According to DeMorgan’s theorem,

$$\begin{gathered} \overline{A·B}=\overline{A}+\overline{B} \\ \overline{A+B}=\overline{A}·\overline{B} \end{gathered}$$

Build AND function using two-input NAND gate

To build AND function using NAND gate, two NAND gates are required. The value X and Y is passed to the first NAND gate and the output of the first gate is passed to both inputs of the second NAND gate.

Build OR function using a two-input NAND gate

To build OR function using NOR gate, two NOR gates are required. The same value X is passed to the both inputs of the first NAND gate and Y to the inputs of both inputs to the second NAND gate. The output of these two NAND gates is passed to the third NOR gate. The output of the third NOR gate is equal to the OR function.

Build NOT function using two-input NAND gate

To build a NOT function using a NAND gate, one NAND gate is required. The input to the NAND gate is a tie of the two inputs together.