GATE CS 2015 Set 1 Q1 — Propositional and First Order Logic

The biconditional proposition $p \leftrightarrow q$ is true if and only if both $p$ and $q$ have the same truth value. Let us analyze each option to find which one is NOT equivalent to $p \leftrightarrow q$:

• Option A: $(\neg p \lor q) \land (p \lor \neg q)$
  Using the implication equivalence $x \to y \equiv \neg x \lor y$, we can rewrite this as:
  $(p \to q) \land (q \to p) \equiv p \leftrightarrow q$.
  (Equivalent)


• Option B: $(\neg p \lor q) \land (q \to p)$
  Replacing $(\neg p \lor q)$ with $(p \to q)$ gives:
  $(p \to q) \land (q \to p) \equiv p \leftrightarrow q$.
  (Equivalent)


• Option C: $(\neg p \land q) \lor (p \land \neg q)$
  This represents the Exclusive-OR (XOR) operation, $p \oplus q$, which is true when $p$ and $q$ have different truth values. Thus:
  $(\neg p \land q) \lor (p \land \neg q) \equiv \neg(p \leftrightarrow q)$.
  (NOT Equivalent)


• Option D: $(\neg p \land \neg q) \lor (p \land q)$
  This states that either both $p$ and $q$ are false, or both $p$ and $q$ are true, which is the definition of the biconditional:
  $(\neg p \land \neg q) \lor (p \land q) \equiv p \leftrightarrow q$.
  (Equivalent)

Therefore, Option C is the only expression that is not equivalent to $p \leftrightarrow q$.