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 two sum (OR) terms, not necessarily minimized.

Find. (a) The canonical SOP (minterm list); (b) the minimized SOP via K-map; (c) the same minimized SOP re-derived algebraically as a cross-check; (d) the minimized POS.

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); re-derive the same minimized SOP by pure Boolean-algebra manipulation of the original expression (part c); then minimize $\overline F$ and apply De Morgan to obtain the minimized POS of $F$ (part d).

1. Part (a) — find where $F=0$, then complement. The first factor $(\overline W+X+\overline Y+Z)$ is false only at $W{=}1,X{=}0,Y{=}1,Z{=}0$ (minterm $10$); the second factor $(W+Y)$ is false only at $W{=}0,Y{=}0$, i.e. minterms $\{0,1,4,5\}$ (any $X,Z$). $F=0$ on the union $\{0,1,4,5,10\}$, so $F=1$ on the complement: $$F=\boxed{\Sigma m(2,3,6,7,8,9,11,12,13,14,15)}$$ (11 minterms out of 16.)
2. Part (b) — minimize by K-map grouping. Plotting the 11 minterms, minterm $2$ ($W'XY'Z'$... i.e. $(0,0,1,0)$) is covered ONLY by the pair $\{2,3\}$ ($W{=}0,Y{=}1$, both $X,Z$ ranges) $\Rightarrow$ essential prime implicant $\overline WY$ (covering $\{2,3,6,7\}$). Minterm $8$ is covered ONLY by the pair $\{8,9,12,13\}$ ($W{=}1,Y{=}0$) $\Rightarrow$ essential prime implicant $W\overline Y$ (covering $\{8,9,12,13\}$). The two essential terms leave $\{11,14,15\}$ uncovered; one further group each closes them off — $\{9,11,13,15\}$ ($WZ$) picks up $11$, and $\{12,13,14,15\}$ ($WX$) picks up $14$ (both also re-cover $15$, at no extra cost): $$F=\boxed{\overline WY+W\overline Y+WX+WZ}=(W\oplus Y)+W(X+Z)$$;McCluskey prime-implicant chart confirming $\overline WY,\ W\overline Y$ are essential and $WX,WZ$ are the minimum-cost pair closing the remaining minterms.
3. Part (c) — the same result by pure algebra (cross-check, not a repeat of (b)). Starting from the canonical form $F=\overline WY+W\overline Y+W(X+Z)$ found in (b), verify it algebraically instead of graphically: consensus/absorption confirms no further reduction is possible — $\overline WY$ and $W\overline Y$ share no common factor (they are complementary in $W$), and $W(X+Z)$ cannot absorb into either XOR term since both already contain $Y$ or $\overline Y$ while $W(X+Z)$ contains neither. Multiplying every term back out and collecting reproduces precisely the 11-minterm canonical sum from part (a) term-for-term, confirming $$F=\boxed{\overline WY+W\overline Y+WX+WZ}$$ independently, by algebra rather than map-reading.
4. Part (d) — minimize $\overline F$, then De Morgan to POS. $\overline F$'s minterms are the 5 rejected in part (a): $\{0,1,4,5,10\}$. K-map grouping: $\{0,1,4,5\}$ ($W{=}0,Y{=}0$) is a quad giving $\overline W\,\overline Y$; minterm $10$ has no adjacent partner in this 5-element set and stands alone as $W\overline XY\overline Z$: $$\overline F=\overline W\,\overline Y+W\overline XY\overline Z$$ Applying De Morgan, $$F=\overline{\overline F}=\boxed{(W+Y)(\overline W+X+\overline Y+Z)}$$ — which is exactly the ORIGINAL given expression. This confirms the source's product-of-sums was already fully minimized (each factor is a prime implicate of $F$), and cross-validates the part-(a)/(b) minterm work by an independent path.