GATE 2026 CS (CS1) – Question 48
Consider a Boolean function $F$ with the following minterm expression:
$$F(P, Q, R, S) = \sum m(1, 2, 3, 4, 5, 7, 10, 12, 13, 14)$$
Which of the following expressions is/are minimal sum-of-products (SOP) of $F$?
Practise this question in The GATE Grind →
Show answer and explanation
Correct answer: (B) $\overline{P}S + Q\overline{R} + \overline{P}\overline{Q}R + PR\overline{S}$; (D) $\overline{P}S + Q\overline{R} + PQ\overline{S} + \overline{Q}R\overline{S}$
Explanation
Minterms: $1,2,3,4,5,7,10,12,13,14$ (index $=8P+4Q+2R+S$).
**Essential prime implicants**
- $\overline{P}S$ covers $\{1,3,5,7\}$ (the only cover for 1, 3, 7).
- $Q\overline{R}$ covers $\{4,5,12,13\}$ (the only cover for 4, 12, 13).
**Left to cover:** $2,\ 10,\ 14$.
- 2: $\overline{P}\overline{Q}R$ (2,3) or $\overline{Q}R\overline{S}$ (2,10)
- 10: $\overline{Q}R\overline{S}$ (2,10) or $PR\overline{S}$ (10,14)
- 14: $PQ\overline{S}$ (12,14) or $PR\overline{S}$ (10,14)
Two extra terms are needed in any cover. The ways to cover $\{2,10,14\}$ with two terms are $\{\overline{P}\overline{Q}R,\ PR\overline{S}\}$, $\{\overline{Q}R\overline{S},\ PQ\overline{S}\}$ and $\{\overline{Q}R\overline{S},\ PR\overline{S}\}$.
Check the options:
- (A) $\overline{P}S+Q\overline{R}+\overline{P}\overline{Q}R+Q\overline{R}\overline{S}$: the last term only repeats minterms 4 and 12, so 10 and 14 are **not covered**. Not equal to $F$.
- (B) $\overline{P}S+Q\overline{R}+\overline{P}\overline{Q}R+PR\overline{S}$: covers 2 and 10, 14. **Valid and minimal** (4 terms, 10 literals).
- (C) $\overline{P}S+Q\overline{R}+PQ\overline{S}+PR\overline{S}$: minterm 2 is **not covered**.
- (D) $\overline{P}S+Q\overline{R}+PQ\overline{S}+\overline{Q}R\overline{S}$: covers 2, 10 and 14. **Valid and minimal** (4 terms, 10 literals).
Answer: B, D.