Lesson 01

Deriving Logic Gates Using Only NAND

A systematic derivation of common logic gates built exclusively from NAND gates. The NAND gate is “universal”—any digital circuit can be built using only NANDs.

Notation\(A'\) = NOT A|\(A \cdot B\) = AND|\(A + B\) = OR|NAND: \((A \cdot B)'\)

Notation Reference

  • A' means NOT A
  • A * B means A AND B
  • A + B means A OR B
  • A 2-input NAND gate computes: (A * B)'

In rendered math below, AND is written as \(A \cdot B\) and NOT as \(A'\).

1) NOT gate from NAND

Goal

Target function: Z = NOT(A) = A'

NAND identity used

\(\text{NAND}(A,B) = (A \cdot B)'\)

Tie both NAND inputs to the same signal \(A\):

\(Z = \text{NAND}(A,A) = (A \cdot A)'\)

Since \(A \cdot A = A\), we get:

\(Z = (A \cdot A)' = A'\)

This implements NOT using a single NAND.

Wiring Diagram

ANANDZ = A'Tie both NAND inputs to A: Z = NAND(A,A) = (A*A)' = A'

Truth Table

AAA * A(A * A)'
0001
1110

2) AND gate from NAND

Goal

Target function: Z = A * B

Algebraic derivation

Start from NAND and apply De Morgan's law:

\((A \cdot B)' = A' + B'\)

Invert both sides:

\(((A \cdot B)')' = (A' + B')'\)

Simplify the left side:

\(A \cdot B = (A' + B')'\)

You can also prove the final form directly (De Morgan):

\((A' + B')' = (A')' \cdot (B')' = A \cdot B\)

NAND-only construction

A NAND gate already gives \((A \cdot B)'\). An AND gate is just “NAND then NOT”:

\(X = \text{NAND}(A,B) = (A \cdot B)'\)
\(Z = \text{NAND}(X,X) = X' = ((A \cdot B)')' = A \cdot B\)

Wiring Diagram

ABNANDX = (A*B)'NANDZ = A*BAND = NOT(NAND(A,B)) = NAND( NAND(A,B), NAND(A,B) )

3) OR gate from NAND

Goal

Target function: Z = A + B

Algebraic derivation

Start by inserting double-negations:

\(A + B = A'' + B''\)

Apply De Morgan's law to rewrite OR in terms of NAND structure:

\(A'' + B'' = (A' \cdot B')'\)

So \(A + B = (A' \cdot B')'\). That is: invert A, invert B, then NAND the results.

NAND-only construction

We already built an inverter from NAND: \(A' = \text{NAND}(A,A)\). So:

\(A' = \text{NAND}(A,A)\)
\(B' = \text{NAND}(B,B)\)
\(Z = \text{NAND}(A',B') = (A' \cdot B')' = A + B\)

Wiring Diagram

ABNANDA'NANDB'NANDZ = A + BOR = NAND(A', B') where A' = NAND(A,A) and B' = NAND(B,B)

Summary

NOT1 NANDTie inputs together
AND2 NANDsNAND + NOT
OR3 NANDsNOT + NOT + NAND

Continue adding sections (XOR, XNOR, MUX, etc.) using the same pattern: Goal → Algebra → NAND-only wiring → Truth table