GATE 2024 EC Q.19: solution and answer

GATE 2024 · ECQ.19 · 1 mark · MCQ

For the Boolean function

F (A, B, C, D) = \sum m (0, 2, 5, 7, 8, 10, 12, 13, 14, 15),

the essential prime implicants are ________.

(A)
$B D, \overline{B} \overline{D}$
(B)
$B D, A B$
(C)
$A B, \overline{B} \overline{D}$
(D)
$B D, \overline{B} \overline{D}, A B$

See the question in the paper

Tap to open full size

Answer and solution

ANSWER

The essential prime implicants are $B D$ and $\overline{B} \overline{D}$ , which is option (A).

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

Complement is written with throughout. Put the minterms on a 4-variable K-map, with rows $A B$ and columns $C D$ , both in Gray order 00, 01, 11, 10. Row $A B = 00$ has $m_{0}, m_{2}$ . Row $01$ has $m_{5}, m_{7}$ . Row $11$ has $m_{12}, m_{13}, m_{15}, m_{14}$ , which is the whole row. Row $10$ has $m_{8}, m_{10}$ . The 0 cells are $m_{1}, m_{3}, m_{4}, m_{6}, m_{9}, m_{11}$ .
List every prime implicant, meaning every largest group of adjacent 1s. They are $\overline{B} \overline{D} = {0, 2, 8, 10}$ (the four corners), $B D = {5, 7, 13, 15}$ , $A B = {12, 13, 14, 15}$ and $A \overline{D} = {8, 10, 12, 14}$ . None of these fits inside a group of 8: $A$ needs $m_{9}, m_{11}$ and $\overline{D}$ needs $m_{4}, m_{6}$ , and all four are 0. Every 1 lies in at least one of the four quads, so there are no other prime implicants.
Essential-PI test: a prime implicant is essential if it is the only one that covers some minterm. $m_{0}$ is adjacent to $m_{1}, m_{2}, m_{4}, m_{8}$ . Since $m_{1}$ and $m_{4}$ are 0, any group containing $m_{0}$ must lie inside ${0, 2, 8, 10}$ . The same holds for $m_{2}$ , whose 0 neighbours are $m_{3}, m_{6}$ . So $m_{0}$ and $m_{2}$ are covered only by $\overline{B} \overline{D}$ , which makes $\overline{B} \overline{D}$ essential.
$m_{5}$ is adjacent to $m_{1}, m_{4}, m_{7}, m_{13}$ , and $m_{1}, m_{4}$ are 0. $m_{7}$ is adjacent to $m_{3}, m_{5}, m_{6}, m_{15}$ , and $m_{3}, m_{6}$ are 0. So any group containing $m_{5}$ or $m_{7}$ must lie inside ${5, 7, 13, 15}$ . They are covered only by $B D$ , which makes $B D$ essential.
Check the rest. $m_{12}$ and $m_{14}$ are each covered by both $A B$ and $A \overline{D}$ . $m_{13}$ and $m_{15}$ are covered by $B D$ as well as $A B$ . $m_{8}$ and $m_{10}$ are covered by $\overline{B} \overline{D}$ as well as $A \overline{D}$ . No minterm is covered by $A B$ alone, so $A B$ is not essential, and for the same reason neither is $A \overline{D}$ .
The essential prime implicants are therefore $B D$ and $\overline{B} \overline{D}$ . Together they cover every minterm except $m_{12}$ and $m_{14}$ . To finish the minimum SOP you still need one of $A B$ or $A \overline{D}$ , giving $F = B D + \overline{B} \overline{D} + A B$ or $F = B D + \overline{B} \overline{D} + A \overline{D}$ . That third term is a selective choice, not an essential one. This matches option (A).

KEY IDEA

A prime implicant is essential only if some minterm is covered by that prime implicant and by no other. Here $m_{0}, m_{2}$ can only be grouped into the corner quad $\overline{B} \overline{D}$ , and $m_{5}, m_{7}$ only into $B D$ . The remaining minterms $m_{12}, m_{14}$ are covered equally well by $A B$ or by $A \overline{D}$ , so neither of those is essential.

WATCH OUT FOR

Picking (D) because $A B$ appears in a minimum SOP. $A B$ is needed only to cover $m_{12}$ and $m_{14}$ , and $A \overline{D}$ covers them just as well, so $A B$ is a selective prime implicant, not an essential one. A second mistake is to miss $A \overline{D}$ altogether: with only three prime implicants in view, $A B$ looks like the sole cover of $m_{12}, m_{14}$ and wrongly seems essential.

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

GATE 2024 EC Q.19: solution and answer

Answer and solution

More Boolean logic questions