XOR gate using minimum NAND gates

An XOR gate gives $Y = A \oplus B = A\bar B + \bar A B$. With NAND gates only, the minimum is four 2-input NAND gates.

Derivation

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

So the gates are:

• $G_1 = \overline{AB}$
• $G_2 = \overline{A \cdot G_1}$
• $G_3 = \overline{B \cdot G_1}$
• $Y = \overline{G_2 \cdot G_3}$

Circuit

 A --+-----------------|‾‾\
     |                 |G2 |o--+
     |  |‾‾\      +----|__/    |   |‾‾\
     +--|G1 |o----+            +---|G4 |o-- Y
     +--|__/      +----|‾‾\    +---|__/
     |                 |G3 |o--+
 B --+-----------------|__/

Verification

Output Y is 1 only when the inputs differ, which is the XOR function. Total: 4 NAND gates.