Which one of the following is NOT equivalent to p <-> q? A. (not p or q) and (p or not q) B. (not p or q) and (q -> p) C. (not p and q) or (p and not q) D. (not p and not q) or (p and q)

GATE 2015 · Discrete Mathematics · Propositional Logic · easy

Answer: Options A, B, D all equal 'p equals q' (the biconditional), while C equals 'p differs from q' (XOR), so C is NOT equivalent.

1. Pin down the target pattern: p <-> q is true on rows TT and FF and false on TF and FT. Equivalently (p -> q) and (q -> p) = (not p or q) and (not q or p) = (not p or q) and (p or not q).
2. Rewrite B and D and confirm they match: B: (not p or q) and (q -> p) = (not p or q) and (not q or p) = the same and-form as A, so B is equivalent. D: (not p and not q) or (p and q) lists exactly the FF and TT rows, which is again 'p equals q', so D is equivalent.
3. Expose C as exclusive-or: C = (not p and q) or (p and not q) is true on rows FT and TF, i.e. exactly when p and q DIFFER. That is the exclusive-or, the negation of the biconditional. Hence C is NOT equivalent to p <-> q.