Questions: Logic Gates and Combinational Circuits

Question 1

A hardware manufacturer wants to mass-produce a single gate type that can implement any Boolean function. Which gate should they choose, and why?

• A. AND — because sum-of-products expressions build every Boolean function from AND and OR
• B. OR — because any Boolean expression can be written as a disjunction of terms
• C. NOT — because negation is the most primitive Boolean operation
• D. NAND — because NAND alone can simulate NOT, AND, and OR, making it sufficient for all Boolean functions

Answer: (D)

NAND is functionally complete: NOT(A) = NAND(A,A); AND(A,B) = NOT(NAND(A,B)); OR(A,B) = NAND(NOT A, NOT B) — all derivable from NAND alone. Since AND, OR, and NOT are sufficient to express any Boolean function (via sum-of-products or product-of-sums), NAND alone suffices. NOR is equally complete by a symmetric argument. This is why real hardware often uses only one gate type internally — AND and OR require additional transistors to derive from NAND, but this cost is worth the manufacturing simplicity.

Question 2

Inputs A = 1 and B = 1 are fed into two gates: one OR gate and one XOR gate. What outputs do they respectively produce?

• A. OR outputs 1; XOR outputs 1
• B. OR outputs 1; XOR outputs 0
• C. OR outputs 0; XOR outputs 1
• D. OR outputs 0; XOR outputs 0

Answer: (B)

OR(1,1) = 1 because OR outputs 1 whenever at least one input is 1. XOR(1,1) = 0 because XOR outputs 1 only when the inputs differ — when both are 1, they are equal, so XOR outputs 0. This is the critical distinction: OR is 'at least one is true,' XOR is 'exactly one is true.' In the half adder, the sum bit uses XOR (1+1 in binary produces a sum bit of 0 with a carry of 1) precisely because XOR captures the 'different' condition.

Question 3

A combinational circuit's output depends on its current inputs and also on the sequence of previous inputs it has processed.

• T. True
• F. False

Answer: False

This describes a sequential circuit, not a combinational one. Combinational circuits are stateless — they contain no feedback loops and no memory elements. The output is determined entirely and immediately by the current input values; history plays no role. Sequential circuits (flip-flops, registers, counters) do retain state and produce outputs that depend on both current inputs and past history. Keeping this distinction clear is essential: designing memory or counters requires sequential logic, while purely functional transformations (arithmetic, multiplexing, decoding) use combinational logic.

Question 4

Any Boolean function, no matter how many inputs or outputs, can be implemented using only NAND gates.

• T. True
• F. False

Answer: True

This is the theorem of functional completeness. Every Boolean function can be expressed in sum-of-products or product-of-sums form using AND, OR, and NOT. Since NAND can simulate each of these three operations (NOT(A) = NAND(A,A); AND via double-NAND; OR via De Morgan), NAND alone is sufficient to implement any Boolean function. NOR is equally complete. This result is not merely theoretical — it underlies real chip manufacturing, where entire processors are built from one gate type.

Question 5

Explain how to construct a NOT gate using only a single NAND gate. Why does this demonstrate NAND's functional completeness?

Model answer: Connect both inputs of a NAND gate to the same signal A: the gate computes NAND(A, A). When A = 0, both inputs are 0, and NAND(0,0) = 1. When A = 1, both inputs are 1, and NAND(1,1) = 0. This is exactly NOT(A). Building NOT from NAND is the first step in demonstrating functional completeness: once you have NOT(A) = NAND(A,A), you can build AND(A,B) = NOT(NAND(A,B)) (a NAND followed by a NAND-as-NOT), and OR(A,B) = NAND(NOT A, NOT B) (by De Morgan's law). Since AND, OR, and NOT together can express any Boolean function, NAND alone is sufficient for all of them.

NOR achieves the same universality by a symmetric argument: NOR(A,A) = NOT(A); OR(A,B) = NOT(NOR(A,B)); AND(A,B) = NOR(NOT A, NOT B). The practical consequence is that a chip foundry can manufacture billions of identical NAND (or NOR) cells and assemble any digital circuit — from an adder to a processor — purely from combinations of that one cell type.