Universal gates (NAND - NOR completeness): Question bank

Vocabulary you need first (defined here, so no trap relies on an unexplained word)

Worked visual reference (study before the traps)

The tables and schematic below are the ground truth every reveal points back to.

Figure 1 — the truth tables for the four gates in play. Read each row as "given these inputs, here is the output bit."

Figure 2 — building NOT, AND, OR from NAND, drawn as circuits with gate counts. Follow the wires: notice AND is NAND then an inverter (2 gates), while OR must invert both inputs first (3 gates).

Figure 3 — the minimal 4-NAND XOR, traced signal by signal. Each gate node is labelled with the Boolean expression it carries, so you can see why 3 gates cannot suffice.

True or false — justify

Every item: decide true or false, then give the reason. Bare T/F earns nothing.

A single NAND gate is functionally complete on its own.

True. From one NAND type you can rebuild NOT, AND, and OR (Figure 2), and

{

AND, OR, NOT

}

is a known complete set — so NAND transitively expresses every Boolean function.

The set

{

AND, OR

}

is functionally complete.

False. Both AND and OR are monotonic (raising an input can never lower the output), so no combination can ever produce inversion (NOT). Without NOT you cannot reach every truth table.

{

AND, NOT

}

is functionally complete.

True. NOT gives inversion, and OR is recoverable via De Morgan:

A + B = \overline{\overline{A} \cdot \overline{B}}

. So AND plus NOT covers all three primitives.

NAND and NOR are the only two-input universal gates.

True (among the standard two-input gates). They are the only two whose single-gate output is not monotonic and includes a built-in inversion; AND, OR, XOR, XNOR, etc. each fail to be universal alone.

XOR is a universal gate.

False. XOR-only circuits produce only affine functions (built from XOR and constants), which is a strict subset of all Boolean functions — AND itself isn't affine, so XOR can't reach it.

Making OR from NAND uses more gates than making AND from NAND.

True. AND = 2 NANDs (NAND then invert); OR = 3 NANDs (invert both inputs, then NAND) — compare the two circuits in Figure 2. OR pays extra because De Morgan demands inverting each input first.

For NOR, AND is the cheaper construction and OR the more expensive one.

False — it's mirrored. NOR's native cheap operation is OR (2 NORs); AND from NOR costs 3 NORs. This swap is exactly the duality between NAND and NOR (see Duality Principle).

A NAND with both inputs tied to

A

still needs a separate inverter to give

\overline{A}

False.

A ↑ A = \overline{A \cdot A} = \overline{A}

by idempotence (

A \cdot A = A

) — the tied NAND is the inverter, one gate, nothing extra.

A ↑ B

equals

A + B

False.

A ↑ B = \overline{A B}

(NAND), not OR — see the differing output columns in Figure 1. To get OR you must invert the inputs first:

A + B = (A ↑ A) ↑ (B ↑ B)

If a gate can build NOT and AND, it is automatically universal.

True. OR follows from NOT and AND via De Morgan, giving all three primitives — hence completeness.

Spot the error

Each line contains a flawed claim or derivation. State what's wrong.

Claim: "OR from NAND is

A + B = A ↑ B

The right side is

\overline{A B}

(NAND), which is not OR. The correct build inverts inputs first:

A + B = (A ↑ A) ↑ (B ↑ B)

— De Morgan's input-inversion was skipped.

Claim: "AND from NAND takes one gate because NAND already ANDs."

NAND gives

\overline{A B}

, the inverse of AND. You must invert that output, so AND = 2 NANDs:

(A ↑ B) ↑ (A ↑ B) = A B

(the two-gate path in Figure 2).

Claim: "To invert

A

with a NAND, feed

A

to one input and leave the other floating."

A floating input is undefined and unsafe. Tie both inputs to

A

A ↑ A = \overline{A}

Claim: "AND is universal because it's the most basic gate."

Basicness is irrelevant; universality needs inversion. AND is monotonic and can never output a bit lower than its inputs force, so it cannot make NOT.

Claim: "

A ↓ A

gives AND of

A

with itself."

A ↓ A = \overline{A + A} = \overline{A}

— it's NOT, not AND. NOR with tied inputs inverts (via idempotence

A + A = A

), just like NAND.

Claim: "De Morgan says

A + B = \overline{\overline{A} + \overline{B}}

Wrong operator inside. The correct form is

A + B = \overline{\overline{A} \cdot \overline{B}}

(bar over an AND). Mixing up the inner operation breaks the whole OR-from-NAND construction — see De Morgan's Laws.

Claim: "You verified OR-from-NAND on the row

A = B = 1

only, so it's correct."

One row cannot verify a construction; you must check all four rows of the truth table (Figure 1). The tricky row is

A = B = 0

, where both inversions become 1.

Claim: "NAND is universal but NOR is not, since NOR is rarer."

Rarity is a manufacturing fact, not a logic fact. NOR is fully universal by duality — swap every AND↔OR in the NAND proof.

Why questions

Why must a universal gate contain an inversion (NOT) inside it?

Because purely monotonic gates (AND, OR) can never turn a 1 into a 0; some Boolean functions require that flip, so without built-in inversion the gate set cannot reach every truth table.

Why does OR-from-NAND cost 3 gates while AND-from-NAND costs only 2?

AND just needs NAND-then-invert (2). OR needs De Morgan, which inverts both inputs (2 gates) before one final NAND — an extra inverter compared to AND, visible as the wider circuit in Figure 2.

Why does the cheap/expensive pattern flip when you switch from NAND to NOR?

NAND bunches inputs with AND-then-invert (so AND is near-native), while NOR bunches with OR-then-invert (so OR is near-native). The duality between them swaps every AND↔OR, and therefore swaps the gate counts.

Why is

{

AND, OR, NOT

}

used as the reference "complete set" in the proof?

It is a small, familiar set already known to express any Boolean function; if one gate can reproduce all three, it inherits that completeness transitively — a chain-of-proof shortcut.

Why do ALUs and CPUs favor NAND (or NOR) over stocking AND/OR/NOT separately?

A factory can mass-produce a single standardized, cheap part and wire it into any circuit; in CMOS, NAND/NOR are also physically the smallest, lowest-transistor-count gates.

Why does tying both NAND inputs together produce NOT rather than something else?

With both inputs equal to

A

, the AND inside becomes

A \cdot A = A

(idempotence), so the gate outputs

\overline{A}

Why can't we prove universality just by building NOT and OR — why also show AND?

You don't need all three from scratch: once you have NOT plus either AND or OR, De Morgan supplies the third. Showing NOT + AND (or NOT + OR) already closes the proof.

Edge cases

What does a NAND output when both inputs are 0?

\overline{0 \cdot 0} = \overline{0} = 1

. NAND outputs 0 only when both inputs are 1; every other combination — including all-zeros — gives 1 (top row of Figure 1).

What does a NOR output when both inputs are 0?

\overline{0 + 0} = \overline{0} = 1

. NOR outputs 1 only in this all-zeros case; any input being 1 forces the output to 0.

If you feed all-1s into a network built only from AND gates, can any output ever be 0?

No. With every input at 1, monotonic AND-only logic can only output 1 — a concrete demonstration that AND alone cannot invert, hence isn't universal.

What is

A ↑ A

when

A = 1

, and does it match

\overline{A}

1 ↑ 1 = \overline{1 \cdot 1} = \overline{1} = 0 = \overline{A}

. It matches, confirming the tied-input NAND is a genuine inverter for both

A = 0

and

A = 1

How many NAND gates does XOR need, and why isn't it just 3?

4 NANDs (Figure 3). XOR (

A \overline{B} + \overline{A} B

) needs a shared intermediate gate

g_{1}

feeding two branches; drop to 3 and you cannot keep both product terms alive at once.

Is a constant output (always-1 or always-0) a Boolean function a universal gate must be able to build?

Yes. Constants are valid Boolean functions; NAND can make them (e.g.

A ↑ \overline{A}

is always 1), which a truly complete gate must handle — another reason non-inverting gates fall short.

Does functional completeness depend on the number of input variables?

No. "Functionally complete" means any function of any number of variables is expressible; NAND/NOR satisfy this for all arities, not just two-input functions.

Connections

Boolean Algebra & Logic Gates
De Morgan's Laws — the identity behind every OR/AND conversion
Truth Tables — the tool to verify each trap's claim
Duality Principle — why NAND↔NOR gate counts mirror
CMOS Transistors — why the inverting gates are cheapest to build
Combinational Circuits — where these constructions get assembled
Logic Gate Symbols