Prove De Morgan's theorems; XOR using NAND

De Morgan's theorems

De Morgan's theorems tell how to complement a sum or a product of variables.

Theorem 1: The complement of a sum equals the product of the complements.

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

So a NOR gate equals a bubbled AND gate (AND with inverted inputs).

Theorem 2: The complement of a product equals the sum of the complements.

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

So a NAND gate equals a bubbled OR gate (OR with inverted inputs).

Proof by truth table

Column 4 = column 5 and column 7 = column 8 for every input, so both theorems are proved.

Algebraic proof of Theorem 1: if $X = A + B$ and $Y = \bar A \bar B$, then $X + Y = A + B + \bar A \bar B = A + B + \bar B = 1$ and $X \cdot Y = A \bar A \bar B + B \bar A \bar B = 0$. Since $X + Y = 1$ and $XY = 0$, Y is the complement of X. Theorem 2 follows by duality.

Diagrams

 Theorem 1: NOR = bubbled AND
 A --|‾‾‾\             A --o|‾‾‾\
     | OR  )o-- Y   =       | AND )-- Y
 B --|___/             B --o|___/

 Theorem 2: NAND = bubbled OR
 A --|‾‾‾\             A --o|‾‾‾\
     | AND )o-- Y   =       | OR  )-- Y
 B --|___/             B --o|___/

 (o = inversion bubble)

XOR using minimum NAND gates

$Y = A \oplus B = A\bar B + \bar A B$. It can be built with 4 two-input NAND gates:

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

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

G1 output feeds one input of both G2 and G3; A goes to G2, B goes to G3; G2 and G3 feed G4.