Universal gates; Ex-OR using NAND

Universal gates

The universal gates are NAND and NOR. They are called universal because any Boolean function, and every other gate (NOT, AND, OR, XOR, XNOR), can be built using only NAND gates or only NOR gates. For example, with NAND only: NOT A = $\overline{A A}$, AND = NAND followed by NOT, OR = $\overline{\bar A \bar B}$. This lets a whole circuit be made from one type of IC (e.g. 7400), which simplifies manufacture and reduces cost.

XOR using only NAND gates

$Y = A \oplus B = A\bar B + \bar A B$ needs four 2-input NAND gates.

$$\begin{aligned} Y &= A\bar B + \bar A B \\ &= A(\bar A + \bar B) + B(\bar A + \bar B) \quad (\text{since } A\bar A = B\bar B = 0) \\ &= A\,\overline{AB} + B\,\overline{AB} \\ &= \overline{\overline{A\,\overline{AB}} \cdot \overline{B\,\overline{AB}}} \quad (\text{De Morgan}) \end{aligned}$$

Gates: $G_1 = \overline{AB}$, $G_2 = \overline{A G_1}$, $G_3 = \overline{B G_1}$, $Y = \overline{G_2 G_3}$.

 A --+---------------[NAND G2]--+
     |                 |        |
     +--[NAND G1]--G1--+        +--[NAND G4]-- Y
     |                 |        |
 B --+---------------[NAND G3]--+