GATE 2022 EC Q.27: solution and answer

GATE 2022 · ECQ.27 · 1 mark · MSQ

Select the Boolean function(s) equivalent to $x + y z$ , where $x$ , $y$ , and $z$ are Boolean variables, and $+$ denotes logical OR operation.

(A)
$x + z + x y$
(B)
$(x + y) (x + z)$
(C)
$x + x y + y z$
(D)
$x + x z + x y$

See the question in the paper

Tap to open full size

Answer and solution

ANSWER

Options B and C are equivalent to $x + y z$ : $(x + y) (x + z)$ is the distributive law of OR over AND, and in $x + x y + y z$ the term $x y$ is absorbed by $x$ .

Official answer: B, CSource: Official answer key, GATE 2022 EC (IIT Kharagpur)

Target function: $F = x + y z$ . It is 1 when $x = 1$ , or when $y = z = 1$ . (No complements appear anywhere in this question.)
(A) Absorption ( $x + x y = x$ ) gives $x + z + x y = x + z$ . Test $x = 0, y = 0, z = 1$ : $x + z = 1$ , but $x + y z = 0 + 0 = 0$ . Not equivalent.
(B) Multiply out (AND distributes over OR) and use idempotence $x \cdot x = x$ : $(x + y) (x + z) = xx + x z + x y + y z = x + x z + x y + y z = x (1 + z + y) + y z = x + y z$ since $1 + z + y = 1$ . This is exactly the distributive law of OR over AND, $x + y z = (x + y) (x + z)$ . Equivalent.
(C) Absorption: $x + x y = x (1 + y) = x$ , so $x + x y + y z = x + y z$ . Equivalent.
(D) Absorption: $x + x z + x y = x (1 + z + y) = x$ . Test $x = 0, y = 1, z = 1$ : the option gives $0$ , but $x + y z = 0 + 1 = 1$ . Not equivalent.
Only (B) and (C) reduce to $x + y z$ , so the correct options are B and C.

KEY IDEA

Reduce each option with absorption ( $x + x y = x$ ) and the OR-over-AND distributive law ( $x + y z = (x + y) (x + z)$ ). To prove an option is NOT equivalent, give one input where it differs from $x + y z$ .

WATCH OUT FOR

Rejecting (B) because it looks like a product of sums rather than a sum of products. In Boolean algebra, unlike ordinary algebra, OR distributes over AND, so $(x + y) (x + z) = x + y z$ . A second slip: in (C), dropping the $y z$ term along with $x y$ when applying absorption. Only $x y$ is absorbed by $x$ .

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

GATE 2022 EC Q.27: solution and answer

Answer and solution

More Boolean logic questions