Universal Gates (NAND/NOR) & Static Hazards

Universal gates

A gate family is universal if every Boolean function can be built from it alone. NAND and NOR are each universal, because each can synthesize the three primitive operations:

Here $x\uparrow y=\overline{xy}$ (NAND) and $x\downarrow y=\overline{x+y}$ (NOR). XOR, XNOR, MUX, etc. follow by composition.

NAND-NAND realization of an SOP (the key trick)

A minimized sum-of-products $f=P_1+P_2+\dots+P_k$ is a two-level AND-OR network. Double-negate and apply De Morgan:

$f=\overline{\overline{P_1+\dots+P_k}}=\overline{\overline{P_1}\cdot\overline{P_2}\cdots\overline{P_k}}.$

So $f$ equals a NAND of the per-product NANDs: every AND becomes a NAND, the output OR becomes a NAND — same topology, same gate count, provided wide-fan-in NANDs exist. Dually, a product-of-sums maps to a two-level NOR-NOR network.

Counting gates with only 2-input NANDs

When the only primitive is a 2-input NAND, the free NAND-NAND substitution no longer covers wide gates — you must build them from a tree of 2-input NANDs:

• A complemented product $\overline{AB}$ = 1 NAND.
• Combining two already-OR-able signals $u+v=\overline{\,\overline{u}\,\overline{v}\,}$ costs 3 NANDs (two NAND-inverters + one final NAND), unless the inverted forms are already on hand.

Mini-example (Q76): $f=AB+CD+EF+GH$. The four NANDs $\overline{AB},\overline{CD},\overline{EF},\overline{GH}$ give the products (4 gates). Pair them: $q_1=\overline{\overline{AB}\cdot\overline{CD}}$, $q_2=\overline{\overline{EF}\cdot\overline{GH}}$ (gates 5–6) so $q_1=AB+CD$, $q_2=EF+GH$ already un-inverted. The final OR $q_1+q_2=\overline{\overline{q_1}\,\overline{q_2}}$ needs two inverters + one NAND (gates 7–9). Total 9 two-input NANDs.

Static hazards

Real gates have nonzero propagation delay, so a logically-constant output can momentarily glitch when one input toggles. In a single-output combinational circuit:

• Static-1 hazard: output should stay $1$ but dips to $0$ — the classic flaw of an AND-OR (SOP) network.
• Static-0 hazard: output should stay $0$ but spikes to $1$ — the dual flaw of an OR-AND (POS) network.

Cause & fix (SOP, static-1). On the Karnaugh map, a static-1 hazard sits on the boundary between two adjacent ON-cells covered by different product terms with no single term spanning both. As the toggling variable switches the active AND gate, the output can momentarily fall to 0. Cover that bridge with one redundant consensus term — the prime implicant that overlaps both groups. The consensus of $xy$ and $\overline{x}z$ (eliminating $x$) is $yz$:

$xy+\overline{x}z=xy+\overline{x}z+yz.$

Each added consensus term is exactly one extra AND gate; it is logically redundant but timing-essential.

Mini-example (Q79). Among the adjacent ON-cell pairs of an SOP, the only two not already inside a common product term are bridged by two consensus terms — so the minimum number of extra AND gates to make the SOP hazard-free is 2.

Exam trick: Two-level AND-OR is hazard-prone but maps to NAND-NAND for free — and two-level NAND-NAND (or NOR-NOR) using only 2-input gates is not free: each wide merge of two signals costs 3 NANDs. To kill static-1 hazards, list every distance-1 ON-pair, cross off those inside one product term, and add one consensus term (one AND gate) per leftover pair.