The GATE Grind

GATE 2024 DA – Question 29

Artificial Intelligence · Logic: propositional and predicate · 1 mark · Multiple select

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

  1. $(\neg x \wedge y) \Rightarrow (y \Rightarrow x)$
  2. $(x \wedge \neg y) \Rightarrow (\neg x \Rightarrow y)$
  3. $(\neg x \wedge y) \Rightarrow (\neg x \Rightarrow y)$
  4. $(x \wedge \neg y) \Rightarrow (y \Rightarrow x)$

Practise this question in The GATE Grind →

Show answer and explanation

Correct answer: (B) $(x \wedge \neg y) \Rightarrow (\neg x \Rightarrow y)$; (C) $(\neg x \wedge y) \Rightarrow (\neg x \Rightarrow y)$; (D) $(x \wedge \neg y) \Rightarrow (y \Rightarrow x)$

Explanation

A: when $x$ is false and $y$ is true, the left side is true but $y \Rightarrow x$ is false, so it is not a tautology. B: the left side needs $x$ true, which makes $\neg x$ false, so $\neg x \Rightarrow y$ is true. C: the left side has $\neg x$ and $y$ both true, so $\neg x \Rightarrow y$ is true. D: the left side needs $y$ false, which makes $y \Rightarrow x$ true. So B, C and D hold in every case.