Question 1 of 6: Boolean minimization and hazards

Question 1: Boolean minimization and hazards (12 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 four-variable switching function $f(A,B,C,D)$ written as a five-term SoP, with $A$ the most-significant variable and $D$ the least.

Find. The truth table, the canonical $\Sigma m_i$ list, a minimal SoP cover, and a hazard-free SoP cover (if the minimal one is not already hazard-free).

Approach. Evaluate the five product terms over all sixteen input combinations to get the minterm list, plot them on a four-variable Karnaugh map, read the prime implicants, then test every adjacent pair of 1-cells for a shared product term (the static-1 hazard criterion).

1. Build the truth table (part a). Each term contributes its own cells: $\overline{A}CD\to\{3,7\}$, $A\overline{B}C\to\{10,11\}$, $ABD\to\{13,15\}$, $\overline{A}\,\overline{C}D\to\{1,5\}$, $\overline{A}\,\overline{B}C\overline{D}\to\{2\}$. No cell is produced twice, so $f=1$ for exactly the nine combinations tabulated below.

   Truth table for $f$

   #	A B C D	f	#	A B C D	f
   0	0 0 0 0	0	8	1 0 0 0	0
   1	0 0 0 1	1	9	1 0 0 1	0
   2	0 0 1 0	1	10	1 0 1 0	1
   3	0 0 1 1	1	11	1 0 1 1	1
   4	0 1 0 0	0	12	1 1 0 0	0
   5	0 1 0 1	1	13	1 1 0 1	1
   6	0 1 1 0	0	14	1 1 1 0	0
   7	0 1 1 1	1	15	1 1 1 1	1

2. Canonical SoP (part b). Reading the rows where $f=1$: $$\boxed{\,f = \Sigma m(1,2,3,5,7,10,11,13,15)\,}$$
3. Minimize on the K-map (part c). The nine 1-cells have exactly four prime implicants, all quads: $\overline{A}D$ (m1,3,5,7), $BD$ (m5,7,13,15), $\overline{B}C$ (m2,3,10,11, wrapping from the top row to the bottom row) and $CD$ (m3,7,11,15). Three are essential — m1 is covered only by $\overline{A}D$, m13 only by $BD$, m2 and m10 only by $\overline{B}C$ — and together they already cover all nine cells, so $CD$ is a non-essential prime implicant and is left out: $$\boxed{\,f = \overline{A}\,D + B\,D + \overline{B}\,C\,}$$ Three terms, six literals.
4. Hazard test (part d). A static-1 hazard exists only where two adjacent 1-cells (differing in one variable) are not both covered by a single product term. The adjacent 1-pairs are (m1,m3), (m1,m5), (m3,m7), (m5,m7) in $\overline{A}D$; (m5,m13), (m7,m15), (m13,m15) in $BD$; (m2,m3), (m2,m10), (m3,m11), (m10,m11) in $\overline{B}C$ — and (m11,m15), which differ only in $B$ with $A=C=D=1$. m11 lies only in $\overline{B}C$ and m15 only in $BD$, so on the change $B:0\to1$ (or back) the output can glitch low: the minimal SoP is not hazard-free (static-1 hazard). The cure is the consensus of $\overline{B}C$ and $BD$ on $B$, namely $CD$ — the non-essential prime implicant found in (c) — which spans m11 and m15. Re-running the adjacency test with $CD$ added leaves no uncovered pair, and one added two-literal term is the smallest possible fix: $$\boxed{\,f_{\text{HF}} = \overline{A}\,D + B\,D + \overline{B}\,C + C\,D\,}$$