GATE CS 2003 Q72 — Propositional and First Order Logic

To find the false statement, let us analyze each option:

• Option A: The resolution rule is sound. This means that if we can derive $(P \vee Q)$ from $(P \vee R)$ and $(Q \vee \neg R)$, then the implication $((P \vee R) \wedge (Q \vee \neg R)) \Rightarrow (P \vee Q)$ is a tautology (logically valid). Thus, this statement is TRUE.
• Option B: Consider the truth assignment: $P = \text{True}$, $Q = \text{False}$, and $R = \text{True}$.
  • The LHS is $P \vee Q = \text{True} \vee \text{False} = \text{True}$.
  • The RHS is $(P \vee R) \wedge (Q \vee \neg R) = (\text{True} \vee \text{True}) \wedge (\text{False} \vee \text{False}) = \text{True} \wedge \text{False} = \text{False}$.
  Since $\text{True} \Rightarrow \text{False}$ is $\text{False}$, the implication is not logically valid. Thus, this statement is FALSE.
• Option C: If $(P \vee Q)$ is satisfiable, we can always choose a truth value for $R$ to satisfy $(P \vee R) \wedge (Q \vee \neg R)$ (e.g., if $P$ is true and $Q$ is false, set $R = \text{False}$). Conversely, if the conjunction is satisfiable, then $(P \vee Q)$ must be satisfiable by soundness. Thus, this statement is TRUE.
• Option D: The formula $(P \vee Q) \Rightarrow \text{FALSE}$ is logically equivalent to $\neg(P \vee Q) \equiv \neg P \wedge \neg Q$. This is valid if and only if both $P$ and $Q$ are unsatisfiable (always false). Thus, this statement is TRUE.