GATE 2025 EE Q.37: solution and answer

GATE 2025 · EEQ.37 · 2 marks · MCQ

A Boolean function is given as

f = (\overline{u} + \overline{v} + \overline{w} + \overline{x}) \cdot (\overline{u} + \overline{v} + \overline{w} + x) \cdot (\overline{u} + v + \overline{w} + \overline{x}) \cdot (\overline{u} + v + \overline{w} + x)

The simplified form of this function is represented by

GATE 2025 EE question 37: All four options are gate-level circuit figures. — Figure from the GATE 2025 EE paper. It is part of the question.

(A)
Figure — u and w each through a NOT gate, the two inverted signals into a 2-input OR gate, output f (i.e. $f = \overline{u} + \overline{w}$ )
(B)
Figure — u and w directly into a 2-input OR gate, output f (i.e. $f = u + w$ )
(C)
Figure — v and x each through a NOT gate, the two inverted signals into a 2-input OR gate, output f (i.e. $f = \overline{v} + \overline{x}$ )
(D)
Figure — v and x directly into a 2-input OR gate, output f (i.e. $f = v + x$ )

Answer and solution

ANSWER

$f = \overline{u} + \overline{w}$ , which is $u$ and $w$ each inverted and fed into a 2-input OR gate: option (A).

Official answer: ASource: Official answer key, GATE 2025 EE (IIT Roorkee)

Notation: $\overline{a}$ is the complement of $a$ . The dot between factors means AND. The function is a product of four sum terms (POS form): $f = (\overline{u} + \overline{v} + \overline{w} + \overline{x}) (\overline{u} + \overline{v} + \overline{w} + x) (\overline{u} + v + \overline{w} + \overline{x}) (\overline{u} + v + \overline{w} + x)$
Take the first two factors together. They differ only in $x$ . By the distributive law, $(A + \overline{x}) (A + x) = A + x \overline{x} = A + 0 = A$ . With $A = \overline{u} + \overline{v} + \overline{w}$ : $(\overline{u} + \overline{v} + \overline{w} + \overline{x}) (\overline{u} + \overline{v} + \overline{w} + x) = \overline{u} + \overline{v} + \overline{w}$
The last two factors also differ only in $x$ , so the same rule with $A = \overline{u} + v + \overline{w}$ gives $(\overline{u} + v + \overline{w} + \overline{x}) (\overline{u} + v + \overline{w} + x) = \overline{u} + v + \overline{w}$
Now $f = (\overline{u} + \overline{w} + \overline{v}) (\overline{u} + \overline{w} + v)$ . These two factors differ only in $v$ . Apply the rule again with $B = \overline{u} + \overline{w}$ : $f = (\overline{u} + \overline{w} + \overline{v}) (\overline{u} + \overline{w} + v) = \overline{u} + \overline{w}$
Check with maxterms. A sum term is $0$ only when every literal in it is $0$ . So the four factors are $0$ at $(u, v, w, x) = (1, 1, 1, 1)$ , $(1, 1, 1, 0)$ , $(1, 0, 1, 1)$ and $(1, 0, 1, 0)$ respectively, and $1$ everywhere else. Between them these are exactly the four inputs with $u = 1$ and $w = 1$ , taking every combination of $v$ and $x$ . So $f = 0 ⟺ u w = 1$ , which means $f = \overline{u w} = \overline{u} + \overline{w}$ (De Morgan). The result does not depend on $v$ or $x$ .
To build $f = \overline{u} + \overline{w}$ , pass $u$ and $w$ each through an inverter and feed both inverted signals into a 2-input OR gate. That is circuit (A). (This is the same as a 2-input NAND of $u$ and $w$ .) Circuit (B) gives $u + w$ , (C) gives $\overline{v} + \overline{x}$ and (D) gives $v + x$ , so none of them matches.

KEY IDEA

Adjacency, $(A + y) (A + \overline{y}) = A$ : when two sum terms differ only in one variable, that variable drops out. Use it twice here, first on $x$ and then on $v$ , to get $f = \overline{u} + \overline{w} = \overline{u w}$ . As a check, the four maxterms are exactly the inputs where $u = w = 1$ .

WATCH OUT FOR

Two mistakes are common. One is to drop the complements and pick (B) ( $u + w$ ), forgetting that every factor has $\overline{u}$ and $\overline{w}$ , never $u$ or $w$ . The other is to keep the wrong pair of variables and pick (C) or (D). Only $v$ and $x$ appear both complemented and uncomplemented across the factors, so those are the variables that cancel. The variables that are complemented in every factor, $u$ and $w$ , are the ones that stay.

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

GATE 2025 EE Q.37: solution and answer

Answer and solution

More Boolean logic questions