GATE 2025 DA Q.15: solution and answer

GATE 2025 · DAQ.15 · 1 mark · MCQ

Let $p$ and $q$ be any two propositions. Consider the following propositional statements.

$S_{1} : p \to q$ , $S_{2} : \neg p \land q$ , $S_{3} : \neg p \lor q$ , $S_{4} : \neg p \lor \neg q$ ,

where $\land$ denotes conjunction (AND operation), $\lor$ denotes disjunction (OR operation), and $\neg$ denotes negation (NOT operation). Which one of the following options is correct?

(Note: $\equiv$ denotes logical equivalence)

(A)
$S_{1} \equiv S_{3}$
(B)
$S_{2} \equiv S_{3}$
(C)
$S_{2} \equiv S_{4}$
(D)
$S_{1} \equiv S_{4}$

See the question in the paper

Tap to open full size

Answer and solution

ANSWER

The correct option is (A): $S_{1} \equiv S_{3}$ .

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

Implication elimination: $p \to q \equiv \neg p \lor q$ . So $S_{1} \equiv S_{3}$ , which is option (A).
To rule out the other options, evaluate the statements at $p = F, q = F$ : $S_{1} = T$ , $S_{2} = \neg F \land F = F$ , $S_{3} = \neg F \lor F = T$ , $S_{4} = \neg F \lor \neg F = T$ .
(B) $S_{2} \equiv S_{3}$ is false: at $p = F, q = F$ , $S_{2} = F$ but $S_{3} = T$ .
(C) $S_{2} \equiv S_{4}$ is false: at $p = F, q = F$ , $S_{2} = F$ but $S_{4} = T$ .
(D) $S_{1} \equiv S_{4}$ is false: at $p = T, q = T$ , $S_{1} = T$ but $S_{4} = \neg T \lor \neg T = F$ .
Only (A) holds for every assignment, so the answer is (A).

KEY IDEA

An implication is equivalent to a disjunction: $p \to q \equiv \neg p \lor q$ . To refute a claimed equivalence, find one assignment where the two statements differ.

WATCH OUT FOR

Confusing $\neg p \lor \neg q$ (which equals $\neg (p \land q)$ ) with $\neg p \lor q$ . Another slip is to read $\neg p \land q$ as the negation of the implication. The negation of $p \to q$ is $p \land \neg q$ .

From the GATE 2025 DA paper. Every question of this paper · Download the full paper · All 7 Logic questions, with notes

GATE 2025 DA Q.15: solution and answer

Answer and solution

More Logic questions