The GATE Grind

GATE 2026 CS (CS1) – Question 48

Digital Logic · Boolean Algebra and Minimization · 2 marks · Multiple select

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$?

  1. $\overline{P}S + Q\overline{R} + \overline{P}\overline{Q}R + Q\overline{R}\overline{S}$
  2. $\overline{P}S + Q\overline{R} + \overline{P}\overline{Q}R + PR\overline{S}$
  3. $\overline{P}S + Q\overline{R} + PQ\overline{S} + PR\overline{S}$
  4. $\overline{P}S + Q\overline{R} + PQ\overline{S} + \overline{Q}R\overline{S}$

Practise this question in The GATE Grind →

Show answer and explanation

Correct answer: (A) $\overline{P}S + Q\overline{R} + \overline{P}\overline{Q}R + Q\overline{R}\overline{S}$; (B) $\overline{P}S + Q\overline{R} + \overline{P}\overline{Q}R + PR\overline{S}$

Explanation

Plotting the minterms $\{1, 2, 3, 4, 5, 7, 10, 12, 13, 14\}$ on a 4-variable K-map:
- Essential prime implicants:
- $\overline{P}S$ covers minterms $\{1, 3, 5, 7\}$
- $Q\overline{R}$ covers minterms $\{4, 5, 12, 13\}$
- The remaining uncovered minterms are $m(2), m(10), m(14)$:
- Minterm 2 can be covered by $\overline{P}\overline{Q}R$ or $\overline{Q}R\overline{S}$.
- Minterm 10 can be covered by $\overline{Q}R\overline{S}$ or $PR\overline{S}$.
- Minterm 14 can be covered by $PQ\overline{S}$ or $PR\overline{S}$.
Selecting minimal combinations of 4 prime implicants to cover all minterms yields valid minimal SOP expressions corresponding to options (A) and (B).