Questions: Universal Gates: NOR and NAND

Question 1

You need to build a NOT gate using only NAND gates. How many NAND gates are required and how are they connected?

• A. Two NAND gates in series: output of first feeds both inputs of second
• B. One NAND gate: connect the input signal to both inputs of a single NAND gate
• C. Three NAND gates: one for each input stage and one for the output
• D. A NOT gate cannot be built from NAND gates alone

Answer: (B)

NAND(A, A) = NOT(AND(A, A)) = NOT(A). When both inputs receive the same signal A: if A = 1, the output is NOT(1 AND 1) = 0; if A = 0, the output is NOT(0 AND 0) = 1. One NAND gate with both inputs tied together produces a NOT gate. This self-inversion trick is the foundation for building all other logic from NAND alone.

Question 2

A chip manufacturer can produce only one gate type reliably. Which of the following would allow them to build a complete processor?

• A. AND gates only
• B. OR gates only
• C. NAND gates only
• D. XOR gates only

Answer: (C)

NAND is universal: any Boolean function can be implemented using only NAND gates. This is exactly why the TTL 7400 series (NAND gates) was used to build early integrated circuits — one reliable gate type composes into arbitrarily complex logic. AND alone, OR alone, and XOR alone are not universal: none can produce NOT from themselves, which is required for functional completeness.

Question 3

AND gates and OR gates together form a universal set — any Boolean function can be built using primarily AND and OR gates.

• T. True
• F. False

Answer: False

False. AND and OR together cannot implement NOT. Without negation, you can only build monotone Boolean functions (where changing any input from 0 to 1 never decreases the output). Most useful logic requires complementation — for example, NAND, NOR, and XNOR are all unreachable from AND and OR alone. A set of gates is universal only if it can produce all Boolean functions, including those requiring negation.

Question 4

NAND is universal because it can implement AND, OR, and NOT using only NAND gates, and AND/OR/NOT together can express any Boolean function.

• T. True
• F. False

Answer: True

True. This is the argument for NAND universality: NAND(A,A) = NOT A; feeding a NAND output through another NAND-NOT recovers AND; De Morgan's theorem gives OR(A,B) = NAND(NOT A, NOT B) = NAND(NAND(A,A), NAND(B,B)). Since AND, OR, and NOT are functionally complete, and each can be built from NAND alone, NAND alone suffices to implement any Boolean function. NOR is universal by the symmetric argument.

Question 5

Why can NAND gates implement any Boolean function while AND gates alone cannot? What property does NAND have that AND lacks?

Model answer: NAND can produce logical negation (NOT); AND cannot. By connecting both inputs of a NAND to the same signal, NAND(A,A) = NOT(A). From NOT plus NAND itself, you can build AND (by inverting a NAND output) and OR (via De Morgan's theorem). AND is a monotone function — it can only preserve or lose 1-bits, never invert them. Without negation, many Boolean functions requiring complementation are unreachable. Negation is the critical operation that makes a gate set functionally complete.

The formal property is functional completeness. Any complete set must be able to produce negation. AND and OR are both monotone, so together they still cannot generate NOT — their combination is still incomplete. NAND inherently contains negation (it is AND followed by NOT), which is why it alone achieves completeness. NOR works for the same reason (OR followed by NOT).