GATE 2024 DA Q.29: solution and answer

GATE 2024 · DAQ.29 · 1 mark · MSQ

Let $x$ and $y$ be two propositions. Which of the following statements is a tautology/are tautologies?

(A)
$(\neg x \land y) \Rightarrow (y \Rightarrow x)$
(B)
$(x \land \neg y) \Rightarrow (\neg x \Rightarrow y)$
(C)
$(\neg x \land y) \Rightarrow (\neg x \Rightarrow y)$
(D)
$(x \land \neg y) \Rightarrow (y \Rightarrow x)$

See the question in the paper

Tap to open full size

Answer and solution

ANSWER

The tautologies are (B), (C) and (D).

Official answer: B, C, DSource: Official answer key, GATE 2024 DA (IISc Bengaluru)

An implication $P \Rightarrow Q$ is a tautology exactly when no assignment makes $P$ true and $Q$ false. So for each option, assume the antecedent is true and check whether the consequent can be false.
(A) The antecedent $\neg x \land y$ is true only for $x = F, y = T$ . Then $y \Rightarrow x = T \Rightarrow F = F$ . The antecedent is true and the consequent false, so (A) is not a tautology.
(B) The antecedent $x \land \neg y$ is true only for $x = T, y = F$ . Then $\neg x = F$ , so $\neg x \Rightarrow y$ has a false premise and is true. No falsifying assignment exists, so (B) is a tautology.
(C) The antecedent $\neg x \land y$ is true only for $x = F, y = T$ . Then $\neg x \Rightarrow y = T \Rightarrow T = T$ . No falsifying assignment exists, so (C) is a tautology. Equivalently, the consequent is $x \lor y$ , which follows from $y$ .
(D) The antecedent $x \land \neg y$ is true only for $x = T, y = F$ . Then $y \Rightarrow x = F \Rightarrow T = T$ . In fact $y \Rightarrow x$ is true whenever $x$ is true. No falsifying assignment exists, so (D) is a tautology.
Only (A) has a falsifying assignment, so the tautologies are (B), (C) and (D).

KEY IDEA

An implication fails only when its antecedent is true and its consequent false. So make the antecedent true, which here fixes both $x$ and $y$ , and test the consequent at that single assignment.

WATCH OUT FOR

Writing $y \Rightarrow x$ when the converse $x \Rightarrow y$ is meant, or the reverse. In (A) the antecedent forces $y = T$ and $x = F$ , which makes $y \Rightarrow x$ false. In (D) the antecedent forces $x = T$ , which makes $y \Rightarrow x$ true.

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

GATE 2024 DA Q.29: solution and answer

Answer and solution

More Logic questions