NAND and NOR

The fundamental gate types are NOT, AND, OR.

We want to find a gate that contains at these fundamental gates, so that we can express any circuit using just this gate

✅ Minimal Requirements for Completeness

To express all Boolean functions, we need:

Negation: the ability to invert a signal (NOT)
Binary composition: either AND or OR suffices, since they are duals via De Morgan’s laws

Primitive:

$$ A \uparrow B = \neg(A \land B) $$

Operation	NAND-Only Construction	Explanation
`NOT` A
$$
A \uparrow A
$$
`NOT` `(`A `AND` A`)` –> Negation of Idempotency
A `AND` B
$$
(A \uparrow B) \uparrow (A \uparrow B)
$$
`NOT``{` $\quad$`NOT` `(`A `AND` B`)` `AND` $\quad$`NOT` `(`A `AND` B`)` `}` –> Double-Negation through Idempotency
A `OR` B
$$
(A \uparrow A) \uparrow (B \uparrow B)
$$
`NOT``{` $\quad$`NOT` `(`A `AND` A`)` `AND` $\quad$`NOT` `(`B `AND` B`)` `}` –> DeMorgan’s Law through Idempotency

Primitive:

$$ A \downarrow B = \neg(A \lor B) $$

Operation	NOR-Only Construction	Explanation
`NOT` A
$$
A \downarrow A
$$
`NOT` `(`A `OR` A`)` –> Negation of Idempotency
A `OR` B
$$
(A \downarrow B) \downarrow (A \downarrow B)
$$
`NOT``{` $\quad$`NOT` `(`A `OR` B`)` `OR` $\quad$`NOT` `(`A `OR` B`)` `}` –> Double-Negation through Idempotency
A `AND` B
$$
(A \downarrow A) \downarrow (B \downarrow B)
$$
`NOT``{` $\quad$`NOT` `(`A `OR` A`)` `OR` $\quad$`NOT` `(`B `OR` B`)` `}` –> DeMorgan’s Law through Idempotency

Find out more about primitive NAND $(\uparrow)$ and NOR $(\downarrow)$ expressions at Sheffer Stroke and Pierce Arrow

Last updated on 2025-11-08