GATE CS 2014 Set 3 Q.17 (CS Q.7): Boolean Algebra and Logic Minimization

Consider the following minterm expression for $F$ :

F(P, Q, R, S) = \sum m(0, 2, 5, 7, 8, 10, 13, 15)

The minterms 2, 7, 8 and 13 are 'do not care' terms. The minimal sum-of-products form for $F$ is

$Q\overline{S} + \overline{Q}S$

$\overline{Q}\,\overline{S} + QS$

$\overline{Q}R\overline{S} + \overline{Q}R\overline{S} + Q\overline{R}S + QRS$

$\overline{P}\overline{Q}\overline{S} + \overline{P}QS + PQS + P\overline{Q}\overline{S}$

Official answer and solution

Solution

Map minterms and don't care conditions to a 4-variable Karnaugh map and group into largest implicants.

Minterm assignments:
- 1-minterms: $m = \{0, 5, 10, 15\}$ .
- Don't care minterms: $d = \{2, 7, 8, 13\}$ .
- Combined set of available cells: $\{0, 2, 5, 7, 8, 10, 13, 15\}$ .
Identify groupings on K-map ( $P, Q, R, S$ ):
- Group 1: Minterms $\{0, 2, 8, 10\}$ :
  Binary codes:
  $0 = 0000$ , $2 = 0010$ , $8 = 1000$ , $10 = 1010$ .
  Notice that in all four terms, $Q = 0$ and $S = 0$ , while $P$ and $R$ vary.
  This 4-cell corner group simplifies to $\overline{Q}\,\overline{S}$ .
  This covers 1-minterms $0$ and $10$ .
- Group 2: Minterms $\{5, 7, 13, 15\}$ :
  Binary codes:
  $5 = 0101$ , $7 = 0111$ , $13 = 1101$ , $15 = 1111$ .
  In all four terms, $Q = 1$ and $S = 1$ , while $P$ and $R$ vary.
  This 4-cell group simplifies to $QS$ .
  This covers 1-minterms $5$ and $15$ .
Both groups together cover all 1-minterms with minimum cost:
$F = \overline{Q}\,\overline{S} + QS.$

This matches option B.

Final answer

Common trap

Not utilizing the don't cares to form 4-cell quad groups, resulting in an unminimized expression.

The answer is the one in the official GATE answer key. The solution is this site's own explanation.

GATE questions are the work of the organising institutes. This site is independent and is not affiliated with them.