Questions: Implementing Boolean Functions with Gates

Question 1

A truth table has 3 inputs (A, B, C) and outputs 1 exactly when A=1, B=0, C=1 AND when A=1, B=1, C=1. What is the simplified SOP expression for this function?

• A. F = A·B̄·C + A·B·C, which cannot be simplified further
• B. F = A·C, because the B variable cancels out (B̄ + B = 1)
• C. F = A + C, because each minterm contributes one input
• D. F = A·B·C only, since the second minterm dominates the first

Answer: (B)

In SOP form: F = A·B̄·C + A·B·C. Using Boolean algebra: factor out A·C to get A·C·(B̄ + B) = A·C·1 = A·C. This demonstrates the power of Boolean simplification — the two minterms differ only in the value of B, meaning B is irrelevant to the output. The function is true whenever A=1 AND C=1, regardless of B. This simplification eliminates one AND gate and one NOT gate from the two-level circuit.

Question 2

Which of the following gate sets is functionally complete — capable of implementing any Boolean function?

• A. {AND, OR} only
• B. {NAND} alone
• C. {OR, NOT} only
• D. {AND, XOR} only

Answer: (B)

NAND alone is functionally complete: NOT A = A NAND A; A AND B = (A NAND B) NAND (A NAND B); A OR B = (A NAND A) NAND (B NAND B). This means any circuit — regardless of complexity — can be built using only NAND gates. {AND, OR} without NOT is NOT functionally complete (cannot express NOT). {OR, NOT} can express AND via De Morgan's law, so it is complete. {AND, XOR} cannot express OR without NOT. In real chip design, NAND-only implementations simplify manufacturing.

Question 3

Any Boolean function can be implemented using only AND, OR, and NOT gates.

• T. True
• F. False

Answer: True

The sum-of-products (SOP) procedure guarantees this. For any truth table, write one AND term (minterm) for each row where the output is 1, using NOTs to invert inputs that are 0 in that row, then combine all minterms with ORs. The resulting circuit uses only AND, OR, and NOT. This shows {AND, OR, NOT} is functionally complete. The circuit may not be minimal, but it is always correct — every possible function has an SOP representation.

Question 4

A NAND gate alone cannot implement most Boolean functions — you need at least one additional gate type to achieve functional completeness.

• T. True
• F. False

Answer: False

NAND alone is functionally complete. You can express NOT using a NAND with both inputs tied together (A NAND A = NOT A), express AND by double-NANDing, and express OR via De Morgan's law using NANDs. Since {AND, OR, NOT} is functionally complete and all three can be built from NAND, NAND inherits functional completeness. NOR alone is also functionally complete by symmetric reasoning. This result is fundamental to digital hardware design.

Question 5

Explain the sum-of-products (SOP) approach: how do you go from a truth table to an SOP expression, and what two-level circuit structure does it produce?

Model answer: Scan the truth table for every row where the output is 1. For each such row, write an AND term (minterm) that is true exactly for that input combination: include each input variable directly if it is 1 in that row, or negated (NOT) if it is 0. Then OR all the minterms together. The result is a two-level circuit: the first level is a bank of AND gates (one per minterm), each fed by the input variables and their complements via NOT gates; the second level is a single OR gate whose inputs are the AND gate outputs. This structure directly implements the SOP expression and is guaranteed to be correct for any truth table.

The SOP procedure is a mechanical recipe that always works, regardless of the function's complexity or structure. Its name comes from the algebraic form: a sum (OR) of products (ANDs). The two-level depth is significant — every SOP circuit, no matter how many minterms, can be evaluated in exactly two gate delays. This predictability is valuable in hardware design. After deriving the correct SOP, the next step is simplification (Karnaugh maps) to reduce gate count while preserving correctness.