Question 3 of 6: Boolean-Algebra Minimization from a Product-of-Sums Expression

Question 3: Boolean-Algebra Minimization from a Product-of-Sums Expression (20 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. A 4-variable Boolean function specified as a product of three sum (OR) terms, not necessarily minimized.

Find. (a) The canonical SOP (minterm list); (b) the minimized SOP of $F$; (c) the minimized SOP of $\overline F$; (d) the minimized POS of $\overline F$.

Approach. Evaluate each OR-factor's FALSE condition, union them to find where $F=0$, complement that set to get the $F=1$ minterms (part a); K-map-minimize $F$ directly (part b); K-map-minimize $\overline F$ from the complementary minterm set (part c); then apply De Morgan to the part-(b) minimized SOP of $F$ to obtain the minimized POS of $\overline F$ directly (part d).

1. Part (a) — find where $F=0$, then complement. Each OR-factor is false only where every one of its literals is false: $(W+\overline X+\overline Y)$ fails only at $W{=}0,X{=}1,Y{=}1$ (any $Z$) — minterms $\{4,5\}$; $(\overline W+\overline Z)$ fails only at $W{=}1,Z{=}1$ (any $X,Y$) — minterms $\{9,11,13,15\}$; $(W+Y)$ fails only at $W{=}0,Y{=}0$ (any $X,Z$) — minterms $\{0,1,4,5\}$. $F=0$ on the union $\{0,1,4,5,9,11,13,15\}$, so $F=1$ on the complement: $$F=\boxed{\Sigma m(2,3,6,7,8,10,12,14)}$$ (8 minterms out of 16.)
2. Part (b) — minimize $F$ by K-map grouping. Plotting the 8 minterms, $\{8,10,12,14\}$ all share $W{=}1,Z{=}0$ with $X,Y$ ranging over all four combinations — a full quad, giving the prime implicant $W\overline Z$. The remaining pair $\{2,3\}$ shares $W{=}0,X{=}0,Y{=}1$ (only $Z$ differs), giving $\overline W\,\overline X Y$. No larger group covers $\{2,3\}$ (extending to $\{2,3,6,7\}$ would need $X$ free, but $6,7$ are NOT in the $F=1$ set), so both are essential — minterm $2$ is covered only by $\overline W\,\overline XY$, and minterms $9,10$-adjacent... i.e. minterm $8$ is covered only by $W\overline Z$: $$F=\boxed{W\overline Z+\overline W\,\overline XY}$$, and against a prime-implicant chart confirming both terms are essential with nothing left uncovered.
3. Part (c) — minimize $\overline F$ from its own minterm set. $\overline F$'s minterms are the 8 rejected in part (a): $\{0,1,4,5,6,7,9,11,13,15\}$ — ten cells (this is a 4-variable function, so the $F{=}1$/$F{=}0$ split need not be even). K-map grouping: $\{4,5,6,7\}$ ($W{=}0,X{=}1$, $Y,Z$ free) is a quad giving $\overline WX$; $\{0,1\}$ ($W{=}0,X{=}0,Y{=}0$) pairs to $\overline W\,\overline X\,\overline Y$; $\{9,11,13,15\}$ ($W{=}1,Z{=}1$, $X,Y$ free) is a quad giving $WZ$. Checking essentiality: minterm $0$ is covered only by $\overline W\,\overline X\,\overline Y$ (not by $\overline WX$, which needs $X{=}1$); minterms $6,7$ are covered only by $\overline WX$ (not by the other two terms); minterms $9,11,13,15$ are covered only by $WZ$ — all three terms are essential and together cover every one of the ten minterms: $$\overline F=\boxed{\overline WX+\overline W\,\overline X\,\overline Y+WZ}$$ verified against all 16 rows (this is the complement of the part-(b)/(a) result at every input).
4. Part (d) — De Morgan the part-(b) minimized SOP of $F$ to get the minimized POS of $\overline F$. Rather than re-grouping a fourth K-map, the minimized POS of $\overline F$ is obtained directly by complementing the minimized SOP of $F$ found in part (b): if $F=W\overline Z+\overline W\,\overline XY$, then by De Morgan $$\overline F=\overline{W\overline Z}\cdot\overline{\overline W\,\overline XY}=(\overline W+Z)(W+X+\overline Y)$$ $$\overline F=\boxed{(\overline W+Z)(W+X+\overline Y)}$$