GATE 2024 EE Q.24: solution and answer

GATE 2024 · EEQ.24 · 1 mark · MCQ

Simplified form of the Boolean function

F (P, Q, R, S) = \overline{P} \overline{Q} + \overline{P} QS + P \overline{Q} \overline{R} \overline{S} + P \overline{Q} R \overline{S}

(Complement is written with .)

(A)
$\overline{P} S + \overline{Q} \overline{S}$
(B)
$\overline{P} \overline{Q} + \overline{Q} \overline{S}$
(C)
$\overline{P} Q + R \overline{S}$
(D)
$P \overline{S} + Q \overline{R}$

See the question in the paper

Tap to open full size

Answer and solution

ANSWER

(A): $F = \overline{P} S + \overline{Q} \overline{S}$ , which covers $\sum m (0, 1, 2, 3, 5, 7, 8, 10)$ .

Official answer: ASource: Official answer key, GATE 2024 EE (IISc Bengaluru)

Complement is written as $\overline{X}$ throughout. The last two terms differ only in $R$ , so by adjacency ( $X R + X \overline{R} = X$ ): $P \overline{Q} \overline{R} \overline{S} + P \overline{Q} R \overline{S} = P \overline{Q} \overline{S}$ .
Take $\overline{P}$ out of the first two terms and use the redundancy rule $\overline{Q} + QS = \overline{Q} + S$ (the form $X + \overline{X} Y = X + Y$ ): $\overline{P} \overline{Q} + \overline{P} QS = \overline{P} (\overline{Q} + S) = \overline{P} \overline{Q} + \overline{P} S$ .
So $F = \overline{P} \overline{Q} + \overline{P} S + P \overline{Q} \overline{S}$ . As a check, list the minterms of the original terms (bit order $P QR S$ ): $\overline{P} \overline{Q} = m (0, 1, 2, 3)$ , $\overline{P} QS = m (5, 7)$ , $P \overline{Q} \overline{R} \overline{S} = m 8$ , $P \overline{Q} R \overline{S} = m 10$ . This gives $F = \sum m (0, 1, 2, 3, 5, 7, 8, 10)$ .
Group the 1s on a K-map (rows $P Q$ , columns $R S$ , both in Gray order $00, 01, 11, 10$ ). The quad $m (1, 3, 5, 7)$ is a $2 \times 2$ block where $P = 0$ and $S = 1$ , so it is $\overline{P} S$ . The four corner cells $m (0, 2, 8, 10)$ are where $Q = 0$ and $S = 0$ , so they form $\overline{Q} \overline{S}$ . Together the two quads cover all eight 1s and nothing else.
$F = \overline{P} S + \overline{Q} \overline{S}$
Checking the other options: (B) $\overline{P} \overline{Q} + \overline{Q} \overline{S} = \sum m (0, 1, 2, 3, 8, 10)$ misses $m 5$ and $m 7$ . (C) $\overline{P} Q + R \overline{S}$ contains $m 4$ ( $\overline{P} Q \overline{R} \overline{S}$ ), which is not in $F$ . (D) $P \overline{S} + Q \overline{R}$ also contains $m 4$ . So option (A) is the answer.

KEY IDEA

Expand the function to its minterm list, $\sum m (0, 1, 2, 3, 5, 7, 8, 10)$ in the order $P QR S$ , and group the 1s on a 4-variable K-map. The $\overline{P} S$ quad $m (1, 3, 5, 7)$ and the four-corner quad $m (0, 2, 8, 10) = \overline{Q} \overline{S}$ cover every 1. Algebraically, $\overline{P} \overline{Q}$ splits into $\overline{P} \overline{Q} S$ and $\overline{P} \overline{Q} \overline{S}$ . The first part is absorbed by $\overline{P} S$ , and the second combines with $P \overline{Q} \overline{S}$ to give $\overline{Q} \overline{S}$ .

WATCH OUT FOR

The usual mistake is to miss that the four corner cells $m (0, 2, 8, 10)$ are adjacent (the K-map wraps around both ways), so $\overline{Q} \overline{S}$ never gets formed. Another is to keep $\overline{P} \overline{Q}$ as a prime implicant and pick (B). But (B) leaves out $m 5$ and $m 7$ , which come from $\overline{P} QS$ . Always check a chosen option against the full minterm list.

From the GATE 2024 EE paper. Every question of this paper · Download the full paper · All 22 Boolean logic questions, with notes

GATE 2024 EE Q.24: solution and answer

Answer and solution

More Boolean logic questions