Boolean Minimization — POS/NOR, SOP/AND-OR, and NAND-Only Realizations: 04-BS-8, December 2019, Q2

Question 2: Boolean Minimization — POS/NOR, SOP/AND-OR, 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.

Check

The five given product terms are minterms 15, 11, 2, 14, 10, i.e. $F=\Sigma m(2,10,11,14,15)$. Part (b)'s "implement by OR and minimum standard gates" is read as the direct AND-OR (SOP) realization of the minimized expression, and part (c)'s "the minimized form of F" is read as that same minimal SOP (not the part (a) POS, which does not map onto a NAND-NAND network).

Given. $F(w,x,y,z)=\Sigma m(2,10,11,14,15)$ (5 minterms out of 16, from the printed SOP expression).

Find. (a) Minimal POS and its NOR-only realization. (b) Minimal SOP realized with standard AND/OR gates. (c) The minimal SOP realized with 2-input NAND gates only.

Approach. K-map/Quine–McCluskey the 5 ones for the minimal SOP, and the 11 zeros (=F') for the minimal POS (De Morgan converts each zero-group into one sum term); brute-force verify both against the full 16-row truth table; then realize the POS with a 2-level NOR-NOR network (NOR computes the complement of a sum term, and NOR of those complements reconstructs the AND-of-sums by De Morgan), the SOP directly with AND/OR/NOT, and the same SOP with a 2-input-NAND-only network (AND$\to$NAND+inverter, OR$\to$NAND-of-inverted-inputs, collapsing to a single final NAND once every product term is already complemented).

Part (a), Step 1 — minimal POS. Minimizing the 11 zero-minterms (equivalently, $F'$) gives the prime implicants $w'x$, $y'$, $w'z$ (Quine–McCluskey, brute-force verified); applying De Morgan to each zero-group term-by-term converts them into the three sum terms of the POS: $$F = (w+x')\,(y)\,(w+z')$$ 3 sum terms, 5 literals total.
Part (a), Step 2 — NOR-only realization. A 2-level NOR-NOR network realizes a POS exactly as a NAND-NAND network realizes an SOP: each first-level NOR gate computes the complement of one sum term, and NOR-ing those complements reconstructs the AND of the sums by De Morgan ($(A'+B'+C')'=A\cdot B\cdot C$). The single-literal term $y$ needs its complement $y'$, built with a NOR whose two inputs are tied together (a NOR-as-inverter, so the design still uses NOR gates exclusively): $$N_1=\overline{w+x'},\quad N_2=\overline{y+y}=y',\quad N_3=\overline{w+z'},\quad F=\overline{N_1+N_2+N_3}$$ 6 NOR gates total ($x'$ and $z'$ each need their own NOR-as-inverter since the POS literals are not otherwise available, 2 two-input NORs for $N_1,N_3$, one NOR-as-inverter for $N_2=y'$, and one 3-input NOR to combine) — the minimum for a 2-level NOR realization of a 3-term POS whose literals $x',z'$ are not given complemented.
Fig. Q2(a) — NOR-only realization of $F=(w+x')(y)(w+z')$. $x'$ and $z'$ are built with NOR-as-inverter gates; the final stage is a 3-input NOR.
Part (b) — standard AND/OR realization. Minimizing the 5 one-minterms directly gives the minimal SOP $$F = wy + x'yz'$$ 2 terms, 5 literals — verified against the full truth table. Realized directly with one inverter (for $x'$), a 2-input AND for $wy$, a 3-input AND for $x'yz'$, and a 2-input OR combining them: 4 gates total, the standard/minimum count for a direct 2-level AND-OR realization of this expression.
Fig. Q2(b) — direct AND-OR realization of the minimal SOP $F=wy+x'yz'$.
Part (c) — 2-input-NAND-only realization. Starting from the same minimal SOP $F=wy+x'yz'$: build $x'$ and $z'$ with NAND-as-inverter gates, $A=\overline{wy}$ directly, and $B=\overline{x'yz'}$ via a 3-gate chain (since a 3-literal AND needs one intermediate double-negation to reach a 2-input-only network: $p=\overline{x'y}$, $\overline{p}=x'y$, $B=\overline{(x'y)z'}$); the final stage is a single NAND, because $F=\overline{A\cdot B}=\overline{\overline{wy}\cdot\overline{x'yz'}}=wy+x'yz'$ by De Morgan — no extra inversion needed since $A,B$ are already the complemented product terms. 7 two-input NAND gates total (2 inverters + 5-gate SOP network).
Fig. Q2(c) — 2-input-NAND-only realization of $F=wy+x'yz'$ (7 gates).

Final results — Question 2
Item	Result
Minimal POS	$(w+x')(y)(w+z')$
(a) NOR gate count	6
Minimal SOP	$wy+x'yz'$
(b) standard AND/OR/NOT gate count	4
(c) 2-input NAND gate count	7

Concept & Theory

Topic: POS vs. SOP minimization; NOR-NOR and NAND-NAND universal-gate realizations.

Key relations: De Morgan's theorems $\overline{A+B}=\bar A\bar B$, $\overline{AB}=\bar A+\bar B$; a NOR gate with tied inputs is an inverter, and so is a NAND gate with tied inputs; POS$\to$NOR-NOR and SOP$\to$NAND-NAND are dual constructions.

Why this works: A 2-level NOR-NOR network computes $\overline{\sum \overline{\text{sum}_i}}$, which by repeated De Morgan is exactly $\prod\text{sum}_i$ — the POS. Symmetrically a NAND-NAND network computes $\overline{\prod\overline{\text{term}_i}}=\sum\text{term}_i$, the SOP. Both constructions need no extra inverters at the output stage precisely because the first-level gates already output the complemented sub-expression the second level needs.

Common pitfall: Applying the "just swap the gate type" NAND-NAND/NOR-NOR shortcut to a term with more literals than the gate's input count allows — a 3-literal product term cannot be built from a single 2-input NAND, and skipping the intermediate double-negation step (as in $B$ above) produces a wrong function, not merely an inefficient one.

Source: Mano & Ciletti, Digital Design §3 (Boolean algebra, De Morgan, POS/SOP, universal gates).

Question 2 of 5: Boolean Minimization — POS/NOR, SOP/AND-OR, and NAND-Only Realizations

Question 2: Boolean Minimization — POS/NOR, SOP/AND-OR, and NAND-Only Realizations (25 marks)