GATE CS 2026 Set 1 Q38 — Minimization (K-Maps etc.)

To find the minimal sum-of-products (SOP) expressions for the Boolean function $F(P, Q, R, S) = \sum m(1,2,3,4,5,7,10,12,13,14)$, we construct the K-map:

Step 1: Identify Essential Prime Implicants (EPIs)

• Quad 1: $\{m_1, m_3, m_5, m_7\} \implies \bar{P}S$
• Quad 2: $\{m_4, m_5, m_{12}, m_{13}\} \implies Q\bar{R}$

These two EPIs cover the minterms $\{1, 3, 4, 5, 7, 12, 13\}$. The remaining uncovered minterms are $\{2, 10, 14\}$.

Step 2: Cover the remaining minterms $\{2, 10, 14\}$

We can choose from the following prime implicants of size 2:

• $I_1 = \{m_2, m_3\} \implies \bar{P}\bar{Q}R$
• $I_2 = \{m_2, m_{10}\} \implies \bar{Q}R\bar{S}$
• $I_3 = \{m_{10}, m_{14}\} \implies PR\bar{S}$
• $I_4 = \{m_{12}, m_{14}\} \implies PQ\bar{S}$

To cover $\{2, 10, 14\}$ minimally, we need exactly two of these prime implicants:

1. Combination 1: Selecting $I_1$ and $I_3$ covers all three remaining minterms.
   $$\text{SOP}_1 = \bar{P}S + Q\bar{R} + \bar{P}\bar{Q}R + PR\bar{S} \quad \text{(Option B)}$$
2. Combination 2: Selecting $I_2$ and $I_4$ covers all three remaining minterms.
   $$\text{SOP}_2 = \bar{P}S + Q\bar{R} + PQ\bar{S} + \bar{Q}R\bar{S} \quad \text{(Option D)}$$