GATE CS 2004 Q59 — Minimization (K-Maps etc.)

To find the essential prime implicants (EPIs), we first express the Boolean function $f(a, b, c) = a'c + ac' + b'c$ in terms of its minterms:

• $a'c = a'b'c + a'bc \implies m_1, m_3$
• $ac' = ab'c' + abc' \implies m_4, m_6$
• $b'c = a'b'c + ab'c \implies m_1, m_5$

Thus, the minterms are $\Sigma m(1, 3, 4, 5, 6)$. We can plot these on a 3-variable K-map:

From the K-map, the Prime Implicants (PIs) are:

1. $\{m_1, m_3\} \implies a'c$
2. $\{m_4, m_6\} \implies ac'$
3. $\{m_1, m_5\} \implies b'c$
4. $\{m_4, m_5\} \implies ab'$

An Essential Prime Implicant (EPI) is a prime implicant that covers at least one minterm not covered by any other prime implicant:

• Minterm $m_3$ is covered only by the prime implicant $a'c$. Hence, $a'c$ is an EPI.
• Minterm $m_6$ is covered only by the prime implicant $ac'$. Hence, $ac'$ is an EPI.

Therefore, the essential prime implicants are $a'c$ and $ac'$.