The following resolution rule is used in logic programming. Derive clause $(P ∨ Q)$ from clauses $(P ∨ R), (Q ∨ ¬R) $ Which of the following statements related to this rule is FALSE?

a:) $((P ∨ R) ∧ (Q ∨ ¬R)) ⇒ (P ∨ Q)$ is logically valid

b:) $(P ∨ Q) ⇒ ((P ∨ R)) ∧ (Q ∨ ¬R))$ is logically valid

c:) $(P ∨ Q)$ is satisfiable if and only if $(P ∨ R) ∧ (Q ∨ ¬R)$ is satisfiable

d:) $(P ∨ Q) ⇒ FALSE\,$ if and only if both $P$ and $Q$ are unsatisfiable

I am able to prove a and d are true. For proving $b$ as false$:- P=1, Q=0, R=1$ Now $LHS$ becomes true,but $RHS$ is $0$, hence invalid implication.

But i can also prove c is not valid as:- $(P ∨ Q)$ is satisfiable $\iff (P ∨ R) ∧ (Q ∨ ¬R)$ is satisfiable

Here if I take, $P=1,\,Q=0,\,R=1$ then LHS becomes true,but RHS is false. So it is also false.

But my book has given b as the answer.Can someone tell where i am wrong in proving that c is also false?

  • $\begingroup$ "my book has given b as the answer" To what ? To question b) ? If so, what are the proposed answers ? $\endgroup$ – Mauro ALLEGRANZA Nov 7 '17 at 13:13
  • $\begingroup$ Its a single question having 4 options.Book has given option b as the answer,but i am getting both b and c.If i have to choose one then i will choose b as its a pretty straight forward.But for c i am think my approach is correct,but i am not sure $\endgroup$ – rahul sharma Nov 7 '17 at 13:16
  • $\begingroup$ sorry,It was a typo $\endgroup$ – rahul sharma Nov 7 '17 at 13:17
  • $\begingroup$ Thanks for confirming. $\endgroup$ – rahul sharma Nov 7 '17 at 13:30
  • 2
    $\begingroup$ @MauroALLEGRANZA Note that (c) is not about being satisfied by a particular truth assignment but about satisfiability. $\endgroup$ – Andreas Blass Nov 7 '17 at 16:24

The Resolution rule:

in propositional logic is a single valid inference rule that produces a new clause implied by two clauses containing complementary literals. A literal is a propositional variable or the negation of a propositional variable. Two literals are said to be complements if one is the negation of the other. The resulting clause contains all the literals that do not have complements.

Thus, applying the resolution rule to the clauses $(P∨R),(Q∨¬R)$ we derive $(P∨Q)$.

The rule is valid, that means that the conclusion is a logical consequence of the premise, i.e.

$(P∨R),(Q∨¬R) \vDash (P∨Q)$,

or, that is equivalent:

$\vDash ((P∨R) \land (Q∨¬R)) \to (P∨Q)$ (i.e. the formula is a tautology or logically valid).

Thus, regarding the proposed answers: a) is correct while b) is wrong.

Why c) is wrong, i.e. it is not FALSE ? (Thanks to @Andreas Blass !)

By the previous argument, the validity of the rule implies that if $(P∨R)∧(Q∨¬R)$ is TRUE, also $(P∨Q)$ is.

Thus if $(P∨R)∧(Q∨¬R)$ is satisfiable, also $(P∨Q)$ is.

For the other direction of the "iff", we have that if $P \lor Q$ is satisfiable, there is a valuation $v$ such that at least one of $P,Q$ is evaluated to TRUE by $v$.

Assume that $v(P)=$ TRUE and $v(Q)=$ FALSE.

Then it is enough to consider the valuation $v'$ that agrees with $v$ on $P$ and $Q$ and such that $v'(R)=$ FALSE, and thus $v'((P∨R)∧(Q∨¬R))=$ TRUE.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.