GATE 2023 IN Q.40: solution and answer

GATE 2023 · INQ.40 · 2 marks · MCQ

The simplified form of the Boolean function $F (W, X, Y, Z) = Σ (4, 5, 10, 11, 12, 13, 14, 15)$ with the minimum number of terms and smallest number of literals in each term is ________.

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

See the question in the paper

Tap to open full size

Answer and solution

ANSWER

The minimal sum of products is $F = X \overline{Y} + W Y$ , which is option (C).

Official answer: CSource: Official answer key, GATE 2023 IN (IIT Kanpur)

Write the minterms in binary, with $W$ as the MSB: $4 = (0100)_{2}$ , $5 = (0101)_{2}$ , $10 = (1010)_{2}$ , $11 = (1011)_{2}$ , $12 = (1100)_{2}$ , $13 = (1101)_{2}$ , $14 = (1110)_{2}$ , $15 = (1111)_{2}$ . Complement is written with an overline throughout, e.g. $\overline{Y}$ .
First quad: ${4, 5, 12, 13}$ . All four have $X = 1$ and $Y = 0$ , while $W$ and $Z$ take every combination. This quad gives $X \overline{Y}$ .
Second quad: ${10, 11, 14, 15}$ . All four have $W = 1$ and $Y = 1$ , while $X$ and $Z$ take every combination. This quad gives $W Y$ .
Coverage and minimality. ${4, 5, 12, 13} \cup {10, 11, 14, 15}$ is exactly the eight given minterms, so $X \overline{Y} + W Y$ covers $F$ with nothing extra. Both terms are essential prime implicants: minterm $4$ has $W = 0$ and $Y = 0$ , so only $X \overline{Y}$ covers it, and minterm $10$ has $X = 0$ , so only $W Y$ covers it. No single literal can equal $F$ . $X = 1$ would also include $6$ and $7$ , and $W = 1$ would include $8$ and $9$ , none of which are in $F$ . So no implicant has fewer than 2 literals, and fewer than 2 terms is impossible.
Therefore $F = X \overline{Y} + W Y$ This is 2 terms of 2 literals each.
Eliminate the other options. (A) $W X + \overline{W} X \overline{Y} + W \overline{X} Y$ covers ${12, 13, 14, 15} \cup {4, 5} \cup {10, 11}$ , which equals $F$ , but it uses 3 terms, two of them with 3 literals, so it is not minimal. (B) adds $W X$ , which is redundant: ${12, 13, 14, 15}$ is already covered by the two quads. This is the consensus theorem, $X \overline{Y} + W Y + W X = X \overline{Y} + W Y$ . (D) $\overline{X} Y + \overline{W} \overline{Y}$ is true at minterm $0 = (0000)_{2}$ through $\overline{W} \overline{Y}$ , and $0$ is not in $F$ , so (D) is a different function.
Answer: (C) $X \overline{Y} + W Y$ .

KEY IDEA

Plot the 8 minterms on a 4-variable K-map. They form exactly two non-overlapping quads: ${4, 5, 12, 13}$ gives $X \overline{Y}$ and ${10, 11, 14, 15}$ gives $W Y$ . Both are essential prime implicants, and together they cover every minterm. The third prime implicant, $W X$ , is the consensus of these two and is redundant.

WATCH OUT FOR

Choosing (B) because the quad ${12, 13, 14, 15}$ ( $W X$ ) is a valid prime implicant. It is the consensus term of $X \overline{Y}$ and $W Y$ , so it adds no coverage. Choosing (A) is the same kind of error: it describes the correct function but is not the minimal form the question asks for.

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

GATE 2023 IN Q.40: solution and answer

Answer and solution

More Boolean logic questions