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, and each zero-condition must be converted to a minterm index using the weighting $m=8W+4X+2Y+Z$: $(W+\overline X+\overline Y)$ fails only at $W{=}0,X{=}1,Y{=}1$ (any $Z$) — that is index $0{\cdot}8+1{\cdot}4+1{\cdot}2+Z=6,7$, minterms $\{6,7\}$; $(\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,6,7,9,11,13,15\}$ (10 cells), so $F=1$ on the complement: $$F=\boxed{\Sigma m(2,3,8,10,12,14)}$$ (6 minterms out of 16.)
2. Part (b) — minimize $F$ by K-map grouping. Plotting the 6 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 XY$; it cannot extend to a quad with $\{6,7\}$ because those two cells are NOT in the $F=1$ set. Minterm $2$ is covered only by $\overline W\,\overline XY$ and minterm $8$ only by $W\overline Z$, so both are essential and together cover all six cells: $$F=\boxed{W\overline Z+\overline W\,\overline XY}$$.
3. Part (c) — minimize $\overline F$ from its own minterm set. $\overline F$'s minterms are the 10 rejected in part (a): $\{0,1,4,5,6,7,9,11,13,15\}$. K-map grouping: $\{0,1,4,5\}$ ($W{=}0,Y{=}0$, $X,Z$ free) is a quad giving $\overline W\,\overline Y$; $\{4,5,6,7\}$ ($W{=}0,X{=}1$, $Y,Z$ free) is a quad giving $\overline WX$; $\{9,11,13,15\}$ ($W{=}1,Z{=}1$, $X,Y$ free) is a quad giving $WZ$. Essentiality: minterm $0$ is covered only by $\overline W\,\overline Y$ (not by $\overline WX$, which needs $X{=}1$); minterms $6,7$ are covered only by $\overline WX$ (not by $\overline W\,\overline Y$, which needs $Y{=}0$); minterms $9,11,13,15$ are covered only by $WZ$ — all three terms are essential (minterms $4,5$ happen to be covered by both $\overline W\,\overline Y$ and $\overline WX$, which does not make either term droppable, since each is independently essential elsewhere) and together the three cover exactly the ten target cells: $$\overline F=\boxed{\overline W\,\overline Y+\overline WX+WZ}$$ verified against all 16 rows (this is the complement of the part-(a)/(b) 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)}$$