Question 5 of 5: Boolean Function Minimization — POS, SOP, and NAND-Only Realizations

Question 5: Boolean Function Minimization — POS, SOP, and NAND-Only Realizations (25 marks)

Question text not reproduced: the examination questions are © Engineers and Geoscientists BC. Open the official past paper (linked at the top of this page) to read the question, then follow the worked solution below.

Given. $F(p,q,r) = (p+q+r)(p+q+r')(p+q'+r)(p'+q'+r)$, a product of 4 sum (maxterm) factors.

Find. (a) minimum POS expression + gate realization; (b) a realization with only 2 AND gates and 1 OR gate; (c) the part (a) form realized in 2-input NAND gates only.

Approach. Apply the consensus identity $(X+r)(X+r')=X$ to collapse adjacent factors before resorting to a K-map; cross-check the result against a K-map of F's zeros. For part (b), re-express F in minimal sum-of-products (SOP) form by grouping the K-map's 1-cells directly. For part (c), realize the POS form of part (a) with NAND gates via De Morgan’s theorem.

1. Part (a) — algebraic reduction. The first two factors share “p+q” and differ only in r vs. r′: $$(p+q+r)(p+q+r') = (p+q) + r\,r' = (p+q) + 0 = p+q$$ (consensus identity). F is now $(p+q)\cdot(p+q'+r)\cdot(p'+q'+r)$. Each of the four original factors is a maxterm — it is 0 exactly where its own literals are all 0 — so F=0 at (p,q,r) = 000, 001, 010, 110 and F=1 at the other four rows (011, 100, 101, 111). Plotting the zeros on a K-map: {000,001} share p=0,q=0 (r free) → group term (p+q); {010,110} share q=1,r=0 (p free) → group term (q'+r). No group of four zeros exists (the two pairs share no second common variable), so these two pairs are the minimal cover. $$\boxed{F = (p+q)(q'+r)}$$

2. Part (b) — minimal SOP, 2 AND + 1 OR. F's ones are at minterms 3,4,5,7 (011,100,101,111). K-map grouping of the ONE-cells: {3,7} share q=1,r=1 (p free) → term q·r; {4,5} share p=1,q=0 (r free) → term p·q′. Together these two pairs cover all four 1-cells exactly once each, with no group of four available (m3 and m5 are not adjacent, so no larger rectangle exists). $$\boxed{F = q\cdot r + p\cdot q'}$$ — needs only 2 AND gates + 1 OR gate (plus one inverter for q′), confirmed identical to the part (a) form for all 8 rows.

3. Part (c) — NAND-only realization of the part (a) POS form. Taking F′ by De Morgan on $F=(p+q)(q'+r)$: $$F' = (p+q)' + (q'+r)' = p'q' + qr'$$ which is itself a 2-term SOP, so it realizes directly in the classic NAND-NAND pattern (NAND-NAND on an SOP reproduces the SOP itself, by double negation): N1 = NAND(p′,q′), N2 = NAND(q,r′), N3 = NAND(N1,N2) = p′q′+qr′ = F′. One further NAND used as an inverter (both inputs tied to N3) then recovers F = NOT(F′). Three more NAND-as-inverters supply the complements p′,q′,r′ that this chain needs (the question gives only the true forms p,q,r as primary inputs — see the check callout). $$\boxed{7 \times \text{2-input NAND gates: 3 inverters} + N1 + N2 + N3 + \text{1 final inverter}}$$ verified gate-by-gate against F for all 8 rows.