Questions: Logic Gates Fundamentals

Question 1

A chip manufacturer wants to standardize production by using only a single type of gate for all digital circuits. An engineer claims this is impossible — you need at least both AND and NOT gates together. Is the engineer correct?

• A. Yes — AND and NOT are required together because OR cannot be derived from them alone
• B. No — a NAND gate alone is functionally complete and can implement any Boolean function
• C. No — but only NOR gates can achieve this, not NAND gates
• D. Yes — OR, AND, and NOT are all required because no single gate can replicate all three

Answer: (B)

NAND gates are individually functionally complete — you can build NOT (NAND with both inputs tied together), AND (NAND followed by NOT), and OR (by De Morgan's law) using only NAND gates. The same is true of NOR gates. This matters enormously for manufacturing: chip fabs can optimize a single transistor geometry rather than designing separate cell libraries for AND, OR, and NOT. Most modern CMOS logic is built primarily from NAND gates for exactly this reason.

Question 2

Why is the XOR gate particularly important in arithmetic circuits, compared to AND, OR, and NOT?

• A. XOR produces the carry bit in binary addition, which AND and OR cannot compute
• B. XOR captures the sum bit in binary addition — the same behavior as adding two bits and taking the result modulo 2
• C. XOR is simpler to construct from transistors than AND or OR gates
• D. XOR can process three or more inputs simultaneously, making it faster than AND for wide operands

Answer: (B)

In binary addition: 0+0=0, 0+1=1, 1+0=1, 1+1=10. The sum bit (ignoring carry) is 1 when inputs differ and 0 when they match — exactly XOR's truth table. The carry bit is 1 only when both inputs are 1 — exactly AND's truth table. So a 1-bit adder is XOR (for sum) + AND (for carry). XOR's unique role in capturing 'differ' behavior (addition mod 2) makes it indispensable in binary arithmetic, including adders, comparators, and error-detection circuits.

Question 3

A truth table for a logic circuit with n inputs always has exactly 2^n rows — one for each possible combination of input values.

• T. True
• F. False

Answer: True

Each of the n inputs is independently either 0 or 1. The total number of distinct combinations is 2 × 2 × … × 2 (n times) = 2^n. A 2-input gate has 4 rows; a 3-input gate has 8 rows; a 10-input circuit has 1,024 rows. This exponential growth is why Boolean algebra simplification matters: reducing a 10-gate circuit to 7 gates is not cosmetic — it eliminates inputs, collapses truth tables, and reduces physical chip area and power consumption.

Question 4

NOT is the most complex of the three basic gates because it requires both AND and OR operations internally to compute its output.

• T. True
• F. False

Answer: False

NOT is actually the simplest gate — it has one input and produces its complement: 0 becomes 1, 1 becomes 0. Its truth table has only 2 rows. NOT requires no AND or OR logic. The complexity claim is backwards: it is NAND and NOR that are derived from combinations of basic gates (AND+NOT and OR+NOT, respectively). NOT can itself be implemented as a NAND gate with both inputs tied together — not the reverse.

Question 5

What does it mean for a set of logic gates to be 'functionally complete,' and why does this property matter for building digital circuits?

Model answer: A set of gates is functionally complete if any Boolean function — any mapping from binary inputs to binary outputs — can be expressed using only gates from that set. {AND, OR, NOT} is functionally complete; so is {NAND} alone, and {NOR} alone. This matters because every digital computation is a Boolean function: arithmetic, comparison, memory, control logic. If your gate set is functionally complete, you can build any digital system whatsoever using only that gate type. Incomplete sets impose limits — for example, {AND, OR} without NOT cannot invert a signal, restricting what circuits are expressible.

Functional completeness is what guarantees that transistor-based digital logic can compute anything computable. The specific choice of which complete set to use affects cost, speed, and chip area — but not the set of computable functions.