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 exactly two 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 to find where $F=0$ (only 4 of the 16 cells here), complement that set to get the canonical SOP of $F$ (part a); K-map-minimize the resulting 12-cell $F$ directly (part b); because $F$ is given as a product of exactly two sum terms, De Morgan converts it directly into a 2-term SOP for $\overline F$ with no K-map needed at all (part c); then complement the part-(b) minimized SOP of $F$ term-by-term to obtain the minimized POS of $\overline F$ (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, converting each zero-condition to a minterm index with the weighting $m=8W+4X+2Y+Z$: $(\overline W+X+Z)$ fails only at $W{=}1,X{=}0,Z{=}0$ (any $Y$) — indices $8{+}0{+}\{0,2\}{+}0=\{8,10\}$; $(W+\overline X+Y)$ fails only at $W{=}0,X{=}1,Y{=}0$ (any $Z$) — indices $0{+}4{+}0{+}\{0,1\}=\{4,5\}$. $F=0$ on the union $\{4,5,8,10\}$ (just 4 of the 16 cells), so $F=1$ on the complement: $$F=\boxed{\Sigma m(0,1,2,3,6,7,9,11,12,13,14,15)}$$ (12 minterms out of 16.)
2. Part (b) — minimize $F$ by K-map grouping. The four cells $\{0,1,2,3\}$ share $W{=}0,X{=}0$ (a full quad over $Y,Z$), giving prime implicant $\overline W\,\overline X$; the four cells $\{12,13,14,15\}$ share $W{=}1,X{=}1$, giving $WX$ — both essential, since minterms $0$ and $12$ are each covered by only one of the two. The remaining four ones $\{6,7,9,11\}$ sit in the two mixed $W,X$ quadrants: $\{6,7\}$ ($W{=}0,X{=}1,Y{=}1$, $Z$ free) groups into $XY$; $\{9,11\}$ ($W{=}1,X{=}0,Z{=}1$, $Y$ free) groups into $WZ$ — both required, since no other prime implicant reaches these four cells without re-covering territory already claimed by the two essential quads: $$F=\boxed{\overline W\,\overline X+WX+XY+WZ}$$, with each of the four terms confirmed essential by dropping it and checking the match fails.
3. Part (c) — $\overline F$ directly by De Morgan of the GIVEN two-factor POS (no K-map needed). Because $F$ is handed to us as a product of exactly two sum terms, De Morgan converts it into a sum of two product terms with no grouping at all: complementing each factor and swapping the outer AND for an OR, $$\overline F=\overline{(\overline W+X+Z)}+\overline{(W+\overline X+Y)}=\boxed{W\overline X\,\overline Z+\overline WX\overline Y}$$ Each term is exactly the zero-condition of its parent OR-factor found in part (a) — $W\overline X\,\overline Z$ reproduces $\{8,10\}$ and $\overline WX\overline Y$ reproduces $\{4,5\}$ — so both are already prime (dropping either loses exactly its 2-cell pair) and no further minimization is possible; confirmed to equal $1-F$ at all 16 inputs.
4. Part (d) — De Morgan the part-(b) minimized SOP of $F$ to get the minimized POS of $\overline F$. Complementing each of the four product terms of part (b) term-by-term (AND$\to$OR of the complemented literals): $$\overline{\overline W\,\overline X}=W+X,\quad \overline{WX}=\overline W+\overline X,\quad \overline{XY}=\overline X+\overline Y,\quad \overline{WZ}=\overline W+\overline Z$$ $$\overline F=\boxed{(W+X)(\overline W+\overline X)(\overline X+\overline Y)(\overline W+\overline Z)}$$