Making Other Gates using NAND Gates

NOT Gate

NOT gate

Implementation

Proof

(see De Morgan's law, tautology)

AND Gate

AND gate

Implementation

Proof

OR Gate

OR gate

Implementation

Proof

NOR Gate

NOR gate

Implementation

Proof

Literally an OR gate with a NOT equivalent NAND gate stuck to the end.

Full proof:

XOR Gate

XOR gate

There are two common derivations of xor:

Implementation

Lemma 1

proof

Proof - Circuit 1

Proof

XNOR Gate

XNOR gate

Implementation

Proof - Circuit 1

Literally circuit 1 from XOR with a NOT equivalent NAND gate stuck to the end

Proof - Circuit 2

Remark

The second circuit is actually "faster" than the first circuit. (3 times propagation delay of a NAND gate instead of 4. This can be observed by finding the longest path a signal will take to reach the end). For XOR, both circuits had the same propagation delay, but circuit 2 had more cost.