De Morgan's laws; XOR using 3-input NAND

De Morgan's laws

First theorem: the complement of a sum (OR) of variables equals the product (AND) of their complements.

$$\overline{A + B} = \bar{A} \cdot \bar{B}$$

Second theorem: the complement of a product (AND) of variables equals the sum (OR) of their complements.

$$\overline{A \cdot B} = \bar{A} + \bar{B}$$

In words: "break the bar and change the sign".

Examples

• $\overline{A + B + C} = \bar A \bar B \bar C$ and $\overline{ABC} = \bar A + \bar B + \bar C$ (extended to 3 variables).
• $\overline{(A + \bar B)C} = \overline{A + \bar B} + \bar C = \bar A B + \bar C$.
• Check with A = 1, B = 0: $\overline{1 + 0} = 0$ and $\bar 1 \cdot \bar 0 = 0 \cdot 1 = 0$.

XOR gate using only 3-input NAND gates

A 3-input NAND gives $\overline{XYZ}$. If one input is tied to logic 1 (HIGH, e.g. +5 V through a resistor), it behaves as a 2-input NAND: $\overline{X \cdot Y \cdot 1} = \overline{XY}$. (Tying the unused input to one of the used inputs also works, since $XX = X$.) So the 4-NAND XOR circuit is built with four 3-input NAND gates:

$$\begin{aligned} G_1 &= \overline{A \cdot B \cdot 1} = \overline{AB} \\ G_2 &= \overline{A \cdot G_1 \cdot 1} \\ G_3 &= \overline{B \cdot G_1 \cdot 1} \\ Y &= \overline{G_2 \cdot G_3 \cdot 1} = A\bar B + \bar A B = A \oplus B \end{aligned}$$

 A --+-------------[NAND3 G2]--+
     |               |    1 -->|
     +--[NAND3 G1]---+         +--[NAND3 G4]-- Y
     |   1 -->|      |         |    1 -->|
 B --+-------------[NAND3 G3]--+
                          1 -->|
 (1 --> : third input tied to logic HIGH)