The following resolution rule is used in logic programming. Derive clause (P^R, Q^R) from clauses (P^Q) and (Q^~R). Which of the following statements related to this rule is FALSE? A. ((P^Q) ^ (Q^~R)) => (P^R, Q^R) is logically valid B. ((P^Q) ^ (Q^~R)) => (P^R) is logically valid C. (P^R, Q^R) is satisfiable if and only if (P^Q) ^ (Q^~R) is satisfiable D. (P^R, Q^R) => FALSE if and only if both P and Q are unsatisfiable

GATE 2003 · Discrete Mathematics · Propositional Logic · medium

Answer: B. ((P^Q) ^ (Q^~R)) => (P^R) is logically valid — this is FALSE; the correct resolvent is (P v R), not merely P.

1. Correct resolution: derive (P v R) from (P v Q) and (~Q v R): With L=Q, X=P, Y=R: (P v Q) ^ (~Q v R) => (P v R). Option A checks (P v Q) ^ (~Q v R) => (P v R), which matches the resolution rule exactly — this is a tautology (TRUE).
2. Check option B: is (P v Q) ^ (~Q v R) => P logically valid?: Set P=F, Q=T, R=T. Then (P v Q)=T, (~Q v R)=(F v T)=T, so premises are both true. But P=F, so the consequent (just P) is False. Hence the implication is False under this assignment — option B is NOT logically valid.
3. Verify remaining options are TRUE (to confirm B is the unique FALSE one): Option C: (P v R) is satisfiable iff (P v Q)^(~Q v R) is satisfiable — since resolution preserves satisfiability (the resolvent is equisatisfiable), this is true. Option D: (P v R) => FALSE (unsatisfiable) iff both P and Q are unsatisfiable — with P=F, R comes only from (~Q v R), and if Q is also unsatisfiable (Q=F always) then ~Q=T forces R to be unrestricted, so checking the boundary shows D is stated correctly as a property.