GATE CS 1989 Q3-v — Propositional and First Order Logic

To find which formulas are logically equivalent, let's analyze each option using standard propositional logic equivalences:

• Formula A: $P \rightarrow Q$
• Formula B: $\neg Q \rightarrow \neg P$
  By the law of contraposition, an implication is logically equivalent to its contrapositive:$$\neg Q \rightarrow \neg P \equiv \neg(\neg P) \rightarrow \neg(\neg Q) \equiv P \rightarrow Q$$Thus, A $\equiv$ B.
• Formula C: $\neg P \vee Q$
  By the material implication rule:$$P \rightarrow Q \equiv \neg P \vee Q$$Thus, A $\equiv$ C.
• Formula D: $\neg Q \rightarrow P$
  Applying the material implication rule:$$\neg Q \rightarrow P \equiv \neg(\neg Q) \vee P \equiv Q \vee P$$This is not logically equivalent to $P \rightarrow Q$.

Therefore, the formulas in A, B, and C are all logically equivalent to each other.