The GATE Grind

GATE 2017 CS – Question 11

Engineering Mathematics · Discrete Mathematics: Propositional and First Order Logic · 1 mark · Multiple choice

The statement $(\neg p) \Rightarrow (\neg q)$ is logically equivalent to which of the statements below?

I. $p \Rightarrow q$

II. $q \Rightarrow p$

III. $(\neg q) \vee p$

IV. $(\neg p) \vee q$

  1. I only
  2. I and IV only
  3. II only
  4. II and III only

Practise this question in The GATE Grind →

Show answer and explanation

Correct answer: (D) II and III only

Explanation

An implication $a \Rightarrow b$ is equivalent to $\neg a \vee b$. So $(\neg p) \Rightarrow (\neg q)$ is $p \vee \neg q$. Statement III is exactly this. Statement II, $q \Rightarrow p$, is $\neg q \vee p$, which is the same. Statements I and IV mean $\neg p \vee q$, which is different.