Question 2 of 6: Prime implicants and minimal SoP

Question 2: Prime implicants and minimal SoP (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. $f(A,B,C,D)=\sum m(0,1,2,4,5,6,7,8,10)$ over four inputs.

Find. The truth table, a classification of implicants (non-prime / prime-non-essential / essential), and the minimal SoP.

Approach. Plot the on-set, read every prime implicant off the map, mark the cells that a single implicant alone covers (these force the essential PIs), then check the essentials already cover every minterm.

(a) Truth table

(b) K-map and implicant classification

The complete set of prime implicants (largest legal groups) is

$$\overline{A}B\;(m_4,m_5,m_6,m_7),\quad \overline{A}\,\overline{C}\;(m_0,m_1,m_4,m_5),\quad \overline{A}\,\overline{D}\;(m_0,m_2,m_4,m_6),\quad \overline{B}\,\overline{D}\;(m_0,m_2,m_8,m_{10}).$$

1. (i) An implicant that is not prime. $\overline{A}\,\overline{B}\,\overline{C}\;(m_0,m_1)$ is a legal group but it sits wholly inside the larger $\overline{A}\,\overline{C}$, so it can still be enlarged — it is not prime.
2. (ii) A prime implicant that is not essential. $\overline{A}\,\overline{D}\;(m_0,m_2,m_4,m_6)$: every one of its cells is also covered by another PI ($m_0$ by all, $m_2$ by $\overline{B}\,\overline{D}$, $m_4,m_6$ by $\overline{A}B$), so no minterm forces it — it is prime but not essential.
3. (iii) The essential prime implicants. $m_1$ lies only in $\overline{A}\,\overline{C}$; $m_7$ only in $\overline{A}B$; $m_8,m_{10}$ only in $\overline{B}\,\overline{D}$. Hence $$\boxed{\overline{A}\,\overline{C},\;\; \overline{A}B,\;\; \overline{B}\,\overline{D}\ \text{are essential.}}$$

(c) Minimal SoP

The three essential PIs together cover $\{0,1,4,5\}\cup\{4,5,6,7\}\cup\{0,2,8,10\}$ = every minterm, so the non-essential $\overline{A}\,\overline{D}$ is not needed:

$$\boxed{f = \overline{A}B + \overline{A}\,\overline{C} + \overline{B}\,\overline{D}}$$ — three product terms, six literals.