DIGITAL ELECTRONICS · BOOLEAN LOGIC

GATE 2018 EC, question 9: Boolean logic — solution and answer

GATE 2018 · ECQ.9 · 1 mark · MCQ Checked against the official key

A function $F (A, B, C)$ defined by three Boolean variables $A$ , $B$ and $C$ when expressed as sum of products is given by
$F = \overline{A} \cdot \overline{B} \cdot \overline{C} + \overline{A} \cdot B \cdot \overline{C} + A \cdot \overline{B} \cdot \overline{C}$
where, $\overline{A}$ , $\overline{B}$ , and $\overline{C}$ are the complements of the respective variables. The product of sums (POS) form of the function F is

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

See it as printed in the paper

Tap to open full size

Answer and worked solution

ANSWER

(C) $F = (A + B + \overline{C}) \cdot (A + \overline{B} + \overline{C}) \cdot (\overline{A} + B + \overline{C}) \cdot (\overline{A} + \overline{B} + C) \cdot (\overline{A} + \overline{B} + \overline{C})$ , which is $\prod M (1, 3, 5, 6, 7)$ .

Official key: C · Official answer key printed with the GATE 2018 EC paper (IIT Guwahati)

Complements are written with throughout. Turn each product term into its minterm by reading an uncomplemented variable as 1 and a complemented one as 0: $\overline{A} \overline{B} \overline{C} = (000)_{2} = m_{0}$ , $\overline{A} B \overline{C} = (010)_{2} = m_{2}$ , $A \overline{B} \overline{C} = (100)_{2} = m_{4}$ .
So $F = \sum m (0, 2, 4)$ . $F$ is 1 on exactly these three input combinations and 0 on the other five: $m_{1}, m_{3}, m_{5}, m_{6}, m_{7}$ .
The canonical POS is the product of the maxterms at which $F = 0$ : $F = \prod M (1, 3, 5, 6, 7)$ .
Write each maxterm by reading a 0 as the plain variable and a 1 as its complement (the opposite of the minterm rule): $M_{1} = (001)_{2} \to (A + B + \overline{C})$ , $M_{3} = (011)_{2} \to (A + \overline{B} + \overline{C})$ , $M_{5} = (101)_{2} \to (\overline{A} + B + \overline{C})$ , $M_{6} = (110)_{2} \to (\overline{A} + \overline{B} + C)$ , $M_{7} = (111)_{2} \to (\overline{A} + \overline{B} + \overline{C})$ .
$F = (A + B + \overline{C}) (A + \overline{B} + \overline{C}) (\overline{A} + B + \overline{C}) (\overline{A} + \overline{B} + C) (\overline{A} + \overline{B} + \overline{C})$ This is option (C), with the factors in the same order.
Check the others. Every factor in every option contains all three variables, so each factor is a single maxterm, and a product of maxterms is 0 exactly at those maxterm numbers. (A) is $(A + B + C) (A + \overline{B} + C) (\overline{A} + B + C) = \prod M (0, 2, 4)$ , which is 0 at $m_{0}, m_{2}, m_{4}$ , exactly where $F$ should be 1. (B) is $(\overline{A} + \overline{B} + \overline{C}) (\overline{A} + B + \overline{C}) (A + \overline{B} + \overline{C}) = \prod M (7, 5, 3)$ , which is 0 only at 3, 5 and 7. It is 1 at $m_{1}$ and $m_{6}$ , where $F = 0$ . (D) is $\prod M (6, 4, 2, 1, 0)$ , which is 0 at $m_{0}, m_{2}, m_{4}$ , where $F = 1$ . So only (C) works.
Quick algebraic check. Simplify the SOP: $F = \overline{C} (\overline{A} \overline{B} + \overline{A} B + A \overline{B}) = \overline{C} (\overline{A} + A \overline{B}) = \overline{C} (\overline{A} + \overline{B})$ .
Now simplify option (C) with the adjacency rule $(X + Y) (X + \overline{Y}) = X$ , reusing $M_{7}$ where needed (allowed because $X \cdot X = X$ ). $M_{1} M_{3} = (A + \overline{C} + B) (A + \overline{C} + \overline{B}) = A + \overline{C}$ . $M_{5} M_{7} = (\overline{A} + \overline{C} + B) (\overline{A} + \overline{C} + \overline{B}) = \overline{A} + \overline{C}$ . $M_{6} M_{7} = (\overline{A} + \overline{B} + C) (\overline{A} + \overline{B} + \overline{C}) = \overline{A} + \overline{B}$ . Then $(A + \overline{C}) (\overline{A} + \overline{C}) = \overline{C}$ , so option (C) $= \overline{C} (\overline{A} + \overline{B})$ , the same as $F$ . The answer is (C).

KEY IDEA

For a function of $n$ variables, the minterms and maxterms split the $2^{n}$ input numbers between them. If $F = \sum m (S)$ , then its canonical POS is $\prod M$ over every number not in $S$ . Here $F = \sum m (0, 2, 4)$ , so the POS is $\prod M (1, 3, 5, 6, 7)$ . For a maxterm, a 0 bit gives the plain variable and a 1 bit gives its complement.

COMMON MISTAKE

The usual mistake is to keep the same indices and write $\prod M (0, 2, 4)$ , which is option (A). Its factors are 0 exactly where $F$ should be 1. The other is writing each maxterm with the minterm literal rule (a 1 bit as the plain variable). That turns $\prod M (1, 3, 5, 6, 7)$ into the wrong-looking option (D) and is a quick way to lose the mark.

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

GATE 2018 EC, question 9: Boolean logic — solution and answer

Answer and worked solution

More Boolean logic questions