NAND vs NOR as the universal gate

NAND and NOR are both universal, so any function can be built from either alone; the difference is cost, which depends on the function. For (A AND B) OR C the engine's NAND-only construction needs three gates and the NOR-only construction nine.

The NAND family builds AND cheaply (a NAND and an inverter) and OR as a NAND of inverted inputs; the NOR family is the mirror image. An AND-OR structure like (A AND B) OR C maps onto NAND almost for free: by De Morgan, (A AND B) OR C is NAND(NAND(A, B), NOT C), and the engine's construction, with its self-fed inverter, counts three gates. The same function on NOR needs the OR-of-AND rebuilt as inverters around NOR gates, nine in the engine's count. Both constructions are checked exactly against the original.

The asymmetry flips with the function. The discount rule (student OR senior) AND NOT expired, an OR followed by an AND with a negation, costs two NOR gates and eleven NAND, as the comparison of truth and decision tables shows. The rule is that a sum of products favours NAND and a product of sums favours NOR, because each basis absorbs one level of its own operator and one inversion.

In technology the choice is also about speed and area: in CMOS the NAND gate's series transistors are the faster kind, which is one reason NAND is the default family, while NOR appears where its structure fits the function. The converter page lets you count both for any expression, and the law pages prove the six constructions, NOT, AND and OR from each gate.

Example

f := (A AND B) OR C · output

Exact checks

Always true (tautology)? No Counterexample: A = F, B = F, C = F · Exhaustively checked and solver cross-checked · 1 rows

Always false (contradiction)? No Counterexample: A = F, B = F, C = T · Exhaustively checked and solver cross-checked · 2 rows

Can be true? Yes Example assignment: A = F, B = F, C = T · Exhaustively checked and solver cross-checked · 2 rows

Truth table (8 rows)

NAND vs NOR as the universal gate
#	A	B	C	f
0	FALSE	FALSE	FALSE	FALSE
1	FALSE	FALSE	TRUE	TRUE
2	FALSE	TRUE	FALSE	FALSE
3	FALSE	TRUE	TRUE	TRUE
4	TRUE	FALSE	FALSE	FALSE
5	TRUE	FALSE	TRUE	TRUE
6	TRUE	TRUE	FALSE	TRUE
7	TRUE	TRUE	TRUE	TRUE

Logic diagram

Karnaugh map

A \ BC

0m0

1m1

1m3

0m2

0m4

1m5

1m7

1m6

cells m6, m7A AND B
cells m1, m3, m5, m7C

(A AND B) OR C · Derived (A AND B) OR C. Exactly equivalent on every assignment.

Minterms and maxterms

f(A, B, C) = Σm(1, 3, 5, 6, 7)f(A, B, C) = ΠM(0, 2, 4)

Variable order: A, B, C · 8 rows

Normal forms

Conjunctive normal form (CNF)

(A OR C) AND (B OR C)

2 clauses, 4 literals · complete · Distribution ×1

Disjunctive normal form (DNF)

(A AND B) OR C

2 terms, 3 literals · complete

NAND-only and NOR-only

NAND-only form

NAND(NAND(A, B), NAND(C, C))

3 gates · verified equivalent on every row

NOR-only form

NOR(NOR(NOR(NOR(A, A), NOR(B, B)), C), NOR(NOR(NOR(A, A), NOR(B, B)), C))

9 gates · verified equivalent on every row

The common slip

Converting mechanically and stopping. The engine's construction is correct and counted, but a hand design that uses De Morgan from the start, as the four-NAND XOR does, is often smaller; the count is a starting point, and the equivalence check keeps the hand design honest.

Questions

Why is a NAND-only XOR four gates but the engine says more?

Because the hand circuit shares the first NAND between two paths, which text cannot express and the mechanical construction does not look for. The worked example proves the four-gate circuit equivalent to XOR.

Does the inverter style change the count?

It can: a self-fed inverter duplicates its input subtree, and the engine switches to a constant-input inverter only when the self-fed form would exceed its size bound. The result says which style it used.

Practice

NAND-only and NOR-only design exercises with answers

Compare

Generated from the Tangibool engine, semantics tangibool-semantics/1, engine 1.0.0, build 2026-11-07. Every table, map, simplification and verdict on these pages was computed by the Tangibool engine when the site was built, and every claim was re-checked by the same exact checker the app uses. Limits are stated where they apply. © 2026 Foreranger LTD.