GATE 2018 EE Q.37: solution and answer

GATE 2018 · EEQ.37 · 2 marks · MCQ

Digital input signals $A, B, C$ with $A$ as the MSB and $C$ as the LSB are used to realize the Boolean function $F = m_{0} + m_{2} + m_{3} + m_{5} + m_{7}$ , where $m_{i}$ denotes the $i^{t h}$ minterm. In addition, $F$ has a don't care for $m_{1}$ . The simplified expression for $F$ is given by

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

See the question in the paper

Tap to open full size

Answer and solution

ANSWER

The simplified expression is $F = \overline{A} + C$ , which is option (B).

Official answer: BSource: Official answer key, GATE 2018 EE (IIT Guwahati)

Here a bar ( $\overline{X}$ ) means complement. With $A$ as the MSB and $C$ as the LSB, the minterms in $A B C$ order are $m_{0} = 000$ , $m_{2} = 010$ , $m_{3} = 011$ , $m_{5} = 101$ and $m_{7} = 111$ , where $F = 1$ . The minterm $m_{1} = 001$ is a don't care (X). That leaves $F = 0$ only for $m_{4} = 100$ and $m_{6} = 110$ .
Draw the 3-variable K-map with rows $A = 0, 1$ and columns $B C = 00, 01, 11, 10$ in Gray order. Row $A = 0$ : $m_{0} = 1$ , $m_{1} = X$ , $m_{3} = 1$ , $m_{2} = 1$ . Row $A = 1$ : $m_{4} = 0$ , $m_{5} = 1$ , $m_{7} = 1$ , $m_{6} = 0$ .
Take the don't care $m_{1}$ as 1. The whole row $A = 0$ ( $m_{0}, m_{1}, m_{3}, m_{2}$ ) is then a quad. Only $A$ is constant across it (it is 0), so the quad gives $\overline{A}$ .
The two middle columns $B C = 01$ and $B C = 11$ ( $m_{1}, m_{3}, m_{5}, m_{7}$ ) form a second quad. $C = 1$ in every one of these cells while $A$ and $B$ both change, so this quad gives $C$ .
The two quads together cover every 1 ( $m_{0}, m_{2}, m_{3}, m_{5}, m_{7}$ ), and neither includes a 0 ( $m_{4}$ or $m_{6}$ ). Each quad is the largest group possible, and one quad alone cannot cover all the 1s. So the minimal SOP is $F = \overline{A} + C$ Check: $\overline{A} + C = 0$ only when $A = 1$ and $C = 0$ , which is exactly $m_{4}$ and $m_{6}$ .
Checking the other options: (A) $\overline{A} \overline{C} + \overline{B} C + A C$ covers $m_{0}, m_{2}$ (from $\overline{A} \overline{C}$ ), $m_{1}, m_{5}$ (from $\overline{B} C$ ) and $m_{5}, m_{7}$ (from $A C$ ), but it misses $m_{3} = 011$ . (C) $\overline{C} + A$ equals 1 at $m_{4}$ and $m_{6}$ , where $F = 0$ . (D) $\overline{A} C + B C + A \overline{C}$ contains $A \overline{C}$ , which is 1 at $m_{4}$ and $m_{6}$ , and it also misses $m_{0}$ , $m_{2}$ and $m_{5}$ . Only (B) matches.

KEY IDEA

Set the don't care $m_{1}$ to 1 where it makes a group bigger. Here it completes two quads: the row $A = 0$ gives $\overline{A}$ , and the columns with $C = 1$ give $C$ . Before accepting the answer, check that $F$ is 0 exactly at $m_{4}$ and $m_{6}$ .

WATCH OUT FOR

Leaving the don't care $m_{1}$ as 0. The 1s then break into smaller groups, such as $\overline{A} \overline{C} + \overline{A} B + C$ or something close to option (A), and it looks as if no option simplifies far enough. Another slip is to use B's weight for A and get the minterm numbers wrong, which puts the 0s in the wrong cells and makes (C) look right.

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

GATE 2018 EE Q.37: solution and answer

Answer and solution

More Boolean logic questions