GATE CS 2014 Set 3 Q7 — Minimization (K-Maps etc.)

To find the minimal sum-of-products (SOP) form, we map the given minterms and don't-care conditions onto a 4-variable Karnaugh map (K-map) with variables $P, Q$ representing the rows and $R, S$ representing the columns:

• Minterms ($F=1$): $\{0, 5, 10, 15\}$
• Don't-care terms ($d$): $\{2, 7, 8, 13\}$

We can form two quads (groups of 4) to cover all the $1$s optimally:

1. Corner Quad: Combining the four corners $\{0, 2, 8, 10\}$.
   The common literals are $Q = 0$ and $S = 0$, which simplifies to $\bar{Q}\bar{S}$.
2. Center Quad: Combining the middle block $\{5, 7, 13, 15\}$.
   The common literals are $Q = 1$ and $S = 1$, which simplifies to $QS$.

Combining these two essential prime implicants, the minimal SOP expression is:
$$F = \bar{Q}\bar{S} + QS$$