GATE 2018 IN Q.43: solution and answer

GATE 2018 · INQ.43 · 2 marks · MCQ

The product of sum expression of a Boolean function $F (A, B, C)$ of three variables is given by

F (A, B, C) = (A + B + \overline{C}) \cdot (A + \overline{B} + \overline{C}) \cdot (\overline{A} + B + C) \cdot (\overline{A} + \overline{B} + \overline{C})

The canonical sum of product expression of $F (A, B, C)$ is given by

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

See the question in the paper

Tap to open full size

Answer and solution

ANSWER

$F = \prod M (1, 3, 4, 7) = \sum m (0, 2, 5, 6) = \overline{A} \overline{B} \overline{C} + \overline{A} B \overline{C} + A \overline{B} C + A B \overline{C}$ , which is option (B).

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

Complement is written with an overline, $\overline{X}$ . Each sum term contains all three variables, so it is a maxterm. A maxterm is 0 for exactly one input: the one that makes every literal 0. An uncomplemented variable must be 0 and a complemented variable ( $\overline{X}$ ) must be 1.
$(A + B + \overline{C}) = 0$ only at $A B C = 001$ , so it is $M_{1}$ . $(A + \overline{B} + \overline{C}) = 0$ only at $A B C = 011$ , so it is $M_{3}$ .
$(\overline{A} + B + C) = 0$ only at $A B C = 100$ , so it is $M_{4}$ . $(\overline{A} + \overline{B} + \overline{C}) = 0$ only at $A B C = 111$ , so it is $M_{7}$ .
So $F = \prod M (1, 3, 4, 7)$ : $F$ is 0 at inputs 1, 3, 4 and 7 and 1 at every other input. The canonical SOP therefore uses the complementary minterm set: $F = \sum m (0, 2, 5, 6)$ .
Write out each minterm. A 0 bit gives the complemented literal and a 1 bit gives the plain literal: $m_{0} = \overline{A} \overline{B} \overline{C}$ (000), $m_{2} = \overline{A} B \overline{C}$ (010), $m_{5} = A \overline{B} C$ (101), $m_{6} = A B \overline{C}$ (110).
$F = \overline{A} \overline{B} \overline{C} + \overline{A} B \overline{C} + A \overline{B} C + A B \overline{C}$ This is option (B). Check: at $A B C = 000$ the product is $(0 + 0 + 1) (0 + 1 + 1) (1 + 0 + 0) (1 + 1 + 1) = 1$ , which agrees with $m_{0}$ being present. The distractors: (A) is $\sum m (1, 3, 4, 7)$ , the maxterm indices wrongly used as minterms. (C) is $\sum m (0, 3, 4, 6)$ and (D) is $\sum m (0, 3, 6, 7)$ . Both include inputs where $F = 0$ .

KEY IDEA

In a canonical POS, each sum term is a maxterm and marks one input where $F = 0$ . Read off its index by setting plain variables to 0 and complemented ones to 1. The canonical SOP is the sum of the minterms with every other index: $\prod M (S) = \sum m (all indices not in S)$ .

WATCH OUT FOR

Using the maxterm indices directly as minterms, which gives $\sum m (1, 3, 4, 7)$ = option (A). A second mistake is reading a maxterm's index the minterm way ( $\overline{X} \to 0$ ). That turns $(A + B + \overline{C})$ into index 6 instead of 1, and the whole set comes out wrong.

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

GATE 2018 IN Q.43: solution and answer

Answer and solution

More Boolean logic questions