GATE CS 2018 Q49 — Minimization (K-Maps etc.)

To find the number of Essential Prime Implicants (EPIs), we first map the minterms ($m$) and don't cares ($d$) on a 4-variable K-map with variables $P, Q, R, S$:

Next, we identify all the Prime Implicants (PIs) that cover the minterms:

• Quad 1: $\{0, 2, 8, 10\}$ (Expression: $Q'S'$)
• Quad 2: $\{8, 9, 10, 11\}$ (Expression: $PQ'$)
• Quad 3: $\{2, 3, 10, 11\}$ (Expression: $Q'R$)
• Pair 1: $\{5, 7\}$ (Expression: $P'QS$)
• Pair 2: $\{3, 7\}$ (Expression: $P'RS$)

An Essential Prime Implicant (EPI) is a PI that covers at least one minterm (excluding don't cares) that is not covered by any other PI:

1. Minterm $0$ is covered only by the PI $\{0, 2, 8, 10\}$. Thus, $\{0, 2, 8, 10\}$ is an EPI.
2. Minterm $5$ is covered only by the PI $\{5, 7\}$. Thus, $\{5, 7\}$ is an EPI.
3. Minterm $9$ is covered only by the PI $\{8, 9, 10, 11\}$. Thus, $\{8, 9, 10, 11\}$ is an EPI.

The remaining minterms ($2$, $7$, and $11$) are covered by multiple PIs. Therefore, the total number of essential prime implicants is 3.