De Morgan; X-NOR using a universal gate

De Morgan's theorems

De Morgan's theorems tell us 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} = \overline{A}\cdot\overline{B}$$

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

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

In words: to complement an expression, change every OR into AND (and every AND into OR) and complement each variable. So a NOR gate is the same as an AND gate with inverted inputs ("bubbled AND"), and a NAND gate is the same as an OR gate with inverted inputs ("bubbled OR").

Proof by truth table

Column 4 equals column 5 for all inputs, which proves Theorem 1. Column 7 equals column 8, which proves Theorem 2.

Algebraic proof of Theorem 1: if $X = A+B$ and $Y = \overline{A}\,\overline{B}$, then $Y$ is the complement of $X$ only if $X+Y=1$ and $X\cdot Y=0$.

$$\begin{aligned} X+Y &= A+B+\overline{A}\,\overline{B} = A + B + \overline{A} = 1 \\ X\cdot Y &= (A+B)\overline{A}\,\overline{B} = A\overline{A}\,\overline{B} + B\overline{A}\,\overline{B} = 0+0 = 0 \end{aligned}$$

So $\overline{A+B} = \overline{A}\,\overline{B}$. Theorem 2 follows by duality.

X-NOR gate using NOR gates only

$$Y = A \odot B = AB + \overline{A}\,\overline{B}$$

Four NOR gates are enough:

1. $G_1 = \overline{A+B}$
2. $G_2 = \overline{A + G_1} = \overline{A}\,(A+B) = \overline{A}B$
3. $G_3 = \overline{B + G_1} = \overline{B}\,(A+B) = A\overline{B}$
4. $Y = \overline{G_2 + G_3} = \overline{\overline{A}B + A\overline{B}} = AB + \overline{A}\,\overline{B}$

A ──┬──────────────┐
    │              [NOR]── G2 ──┐
    ├──[NOR]── G1 ─┤            [NOR]── Y = A XNOR B
    │              [NOR]── G3 ──┘
B ──┴──────────────┘

(G1 = NOR(A,B); G2 = NOR(A,G1); G3 = NOR(B,G1); Y = NOR(G2,G3).)

The output is 1 only when A = B, so the circuit is an X-NOR gate. (With NAND gates, four NANDs give X-OR and a fifth NAND used as an inverter gives X-NOR.)