GATE CS 2017 Set 1 Q01 — Propositional and First Order Logic

To find the logical equivalent of the statement $(\neg p) \Rightarrow (\neg q)$, we can use standard propositional logic equivalences.

Recall the implication rule: $$A \Rightarrow B \equiv \neg A \vee B$$

Applying this rule to the given statement: $$\begin{align*} (\neg p) \Rightarrow (\neg q) &\equiv \neg(\neg p) \vee (\neg q) \\ &\equiv p \vee \neg q \\ &\equiv \neg q \vee p \quad \text{(by commutativity of } \vee\text{)} \end{align*}$$

Now, let's analyze the given statements:

• I. $p \Rightarrow q$
  $\equiv \neg p \vee q$ (Not equivalent to $p \vee \neg q$)
• II. $q \Rightarrow p$
  $\equiv \neg q \vee p$ (Equivalent)
• III. $(\neg q) \vee p$
  $\equiv \neg q \vee p$ (Equivalent)
• IV. $(\neg p) \vee q$
  $\equiv \neg p \vee q$ (Not equivalent to $p \vee \neg q$)

Thus, statements II and III are logically equivalent to the given statement.