The statement (not p) => (not q) is logically equivalent to which of the statements below? I. p => q ; II. q => p ; III. (not q) or p ; IV. (not p) or q ; A. I only B. I and IV only C. II only D. II and III only

GATE 2017 · Discrete Mathematics · Propositional Logic · easy

Answer: Only statements II (q => p) and III ((not q) or p) are equivalent to (not p) => (not q), giving option D.

1. Flatten the target conditional: (not p) => (not q) = not(not p) or (not q) = p or not q. Its contrapositive (not(not q)) -> (not(not p)) = q => p, so statement II is automatically equivalent.
2. Match statement III and reject I, IV: III: (not q) or p = p or not q = the target, so III is equivalent. I: p => q = not p or q, and IV: (not p) or q = not p or q; both equal not p or q, which is the negated-p arrangement and differs from p or not q. So I and IV are NOT equivalent.