NAND gate

A NAND gate outputs the complement of an AND: $0$ only when all inputs are $1$.

$f=\overline{x_1{x}_2}$

$x_1$	$x_2$	$\overline{x_1{x}_2}$
0	0	1
0	1	1
1	0	1
1	1	0

Drawn as an AND symbol with a small bubble at the output — the bubble is the negation, same convention as a NOT gate.

CMOS implementation

A 2-input NAND uses 4 transistors: 2 PMOS in parallel (pull-up network) and 2 NMOS in series (pull-down network).

The pull-down chain conducts only when both NMOS are on — i.e., when both inputs are $1$ — pulling the output low. For any other input combination, at least one PMOS in the pull-up is on (because at least one input is $0$, turning a PMOS on), and the output is pulled high.

This is the natural way CMOS implements AND-like behavior. To get a true AND, you tack a NOT after the NAND, which costs another 2 transistors. NAND is cheaper than AND in CMOS.

Universality

NAND is a universal gate: any Boolean function can be built from NAND alone. The basic conversions:

• NOT: tie both NAND inputs together: $\overline{x\cdot x}=\overline{x}$.
• AND: NAND followed by NAND-as-NOT: $(x\text{ NAND }y)\text{ NAND }(x\text{ NAND }y)=xy$.
• OR: invert both inputs (each via NAND-as-NOT) then NAND them: $(x\text{ NAND }x)\text{ NAND }(y\text{ NAND }y)=\overline{\overline{x}\overline{y}}=x+y$ by De Morgan’s Laws.

This is why NAND gates are sometimes the only primitive in a fabrication library — everything else is composed from them. Compare with NOR gate, which is also universal but uses series PMOS (slower).

NAND-NAND synthesis

Any SOP expression can be converted directly to an all-NAND implementation:

1. Write $f$ in SOP form.
2. Apply double negation: $f=\overline{\overline{f}}$.
3. Push the inner negation into the OR using De Morgan’s Laws — each AND term becomes the NAND of its literals, and the outer OR becomes a final NAND.

Result: two layers of NAND gates, one for each AND term and one to combine them. Same structure as the original AND-OR circuit, just every gate replaced by a NAND.

Useful identities:

• $a+b=\overline{\overline{a}\cdot \overline{b}}=\overline{a}\text{ NAND }\overline{b}$ — OR by NAND-ing the inverted inputs (De Morgan).
• $a\cdot b=\overline{\overline{a\cdot b}}=(a\text{ NAND }b)\text{ NAND }(a\text{ NAND }b)$ — recover an AND by inverting a NAND.
• $a+b=(a\text{ NAND }a)\text{ NAND }(b\text{ NAND }b)$ — OR built entirely from NAND, using NAND-as-NOT to invert each input first.