Questions: Boolean Functions, Logic Gates, and Digital Circuits

Question 1

You want to build a circuit for f(x,y,z) = 1 exactly when at least two of the three inputs are 1. What is the first step in the systematic DNF construction?

• A. Apply Boolean algebra identities to minimize the gate count before building anything
• B. Identify every row of the truth table where the output is 1, then write an AND term for each such row
• C. Write the CNF first, then convert it to DNF by De Morgan's laws
• D. Build the circuit top-down starting from the output gate

Answer: (B)

DNF construction starts with the truth table: enumerate all 2ⁿ input combinations, mark those where the output is 1, and write one AND term (minterm) per such row. The minterm for inputs (1,1,0) would be (x ∧ y ∧ ¬z). Then OR all the minterms together. The result is provably correct but possibly redundant — simplification comes afterward, as a separate step using Boolean algebra identities.

Question 2

Two engineers design circuits for the same Boolean function. Engineer A's circuit uses 12 gates; Engineer B's uses 7. Which is the canonical representation?

• A. Engineer A's — the DNF/CNF form is the unique canonical representation of any Boolean function
• B. Engineer B's — the minimum-gate circuit is always canonical by definition
• C. Neither — Boolean functions have no single canonical circuit; both compute the same function correctly, and even the minimum-gate circuit may not be unique
• D. Whichever circuit matches the original truth table row-for-row

Answer: (C)

DNF and CNF are normal forms (structured representations) but not canonical in the sense of uniqueness — you can write multiple valid DNF expressions for the same function. Circuits are even less canonical: different algebraic simplifications can yield different minimal circuits with the same gate count. Circuit complexity asks 'what is the minimum possible?' but does not produce a unique answer. Both engineers' circuits are valid; minimality is a separate optimization question.

Question 3

The existence of DNF and CNF representations proves that every Boolean function, regardless of how many variables it has, can be computed by a circuit built from AND, OR, and NOT gates.

• T. True
• F. False

Answer: True

This is the completeness guarantee of DNF/CNF. For any Boolean function, you can always construct a DNF by reading off the minterms from the truth table. Since DNF uses only AND, OR, and NOT, every Boolean function has a circuit using only these three gate types. This means {AND, OR, NOT} is a functionally complete set — it suffices to compute any computable Boolean function.

Question 4

The DNF representation of a Boolean function is unique — there is exactly one correct DNF expression for any given function.

• T. True
• F. False

Answer: False

Multiple DNF expressions can represent the same function. For example, (x ∧ y) ∨ (x ∧ ¬y) and x are logically equivalent — both are valid DNF expressions for the same function, but they look very different. DNF is a normal form (it constrains the *structure* to OR-of-ANDs) but not a canonical form (it does not guarantee uniqueness). The fully reduced or minimal DNF may be closer to unique but still is not guaranteed to be so in all cases.

Question 5

What is the difference between showing that every Boolean function *can* be expressed in DNF, and finding a minimal DNF expression? Why does this distinction matter in circuit design?

Model answer: Showing that DNF exists is an existence proof — it tells you a circuit can always be built, using at most one AND gate per minterm and one large OR gate. But the resulting circuit may be enormous and redundant. Finding a minimal expression is an optimization problem: apply Boolean algebra identities to reduce gate count or circuit depth. In hardware design, the difference between a naive DNF circuit and an optimized one can mean thousands of extra gates, higher power consumption, and slower operation.

The completeness of DNF/CNF answers 'is a circuit possible?' The answer is always yes. Circuit complexity answers 'how efficient can it be?' — and this is where most of the hard problems in the field live. Separating the two questions keeps reasoning clear: first establish that a function is computable, then ask how efficiently.