Which of the following well-formed formulas are equivalent? A. P -> Q B. not Q -> not P C. not P or Q D. not Q -> P

GATE 1989 · Discrete Mathematics · Propositional Logic · medium

Answer: A, B and C are logically equivalent (all equal P -> Q); D differs, so the equivalent set is A, B, C.

1. Rewrite A using material implication: P -> Q == not P or Q, which is exactly option C. So A == C.
2. Rewrite B (contrapositive) and confirm A == B: not Q -> not P is the contrapositive of P -> Q, hence not Q -> not P == P -> Q. So B == A. Combined with Step 1, A == B == C.
3. Check D against the group: not Q -> P simplifies to Q or P, which is False only when P=F and Q=F. There A=P->Q is True, so D differs from A on that row. D is not equivalent.