I know that the the resolution rule of inference states that

$(p \lor r)\wedge (q \lor \lnot r) \to (p \lor q)$

Based on this, my textbook says that below statement is true:

$(p \vee q)$ is satisfiable if and only if $(p \lor r)\wedge (q \lor \lnot r)$ is satisfiable.

However if we look at the resolution rule, it says LHS implies RHS. Thus even if LHS is false, RHS can be true. Doesn't that mean, RHS can be satisfied even if LHS is unsatisfiable and thus not only when LHS is satisfiable?

  • $\begingroup$ The statement is quite "misleading" ... $p \lor q$ is not a contradiction; thus it is satisfiable, and the same for the second formula. $\endgroup$ – Mauro ALLEGRANZA Dec 28 '15 at 21:43
  • $\begingroup$ so do you mean to say that they are independently satisfiable and is it like there is nothing like "$x$ is satisfiable if (and only if) $y$ is satisfiable". Because now I feel I dont understand what does it mean by $x$ is satisfiable if (and only if) $y$ is satisfiable. Does it mean $y \to x$? $\endgroup$ – anir123 Dec 28 '15 at 21:47
  • $\begingroup$ As per @Arthur's answer, they are not equivalent; thus the rule means that if the LHS is satisfiable by some truth assignment $v$, then the same $v$ satisfy also the RHS. But the other "direction" is not true. If we do not ask for satisfiability by the same truth assignment, then the two formulae are satisfiable. $\endgroup$ – Mauro ALLEGRANZA Dec 28 '15 at 22:00

Note that the claim is just that they're both satisfiable, not necessarily in the very same models (assignments of truth values ot variables). In particular, there's no claim that the converse is a valid inference rule -- it isn't, as the converse of the implication is not valid.

Because the given formula $$ \vdash (p \lor r)\wedge (q \lor \lnot r) \to (p \lor q)\tag{1} $$ is valid (a tautology, provable), certainly it's clear that if $(p \lor r)\wedge (q \lor \lnot r)$ is satisfiable then so is $(p \lor q)$. In fact, any assignment of truth values to propositional variables that satisfies the former, also satisfies the latter, because it has to assign true to at least one of $p, q$.

Now suppose $(p \lor q)$ is satisfiable. Then under some assignment $v$ of truth values to variables, $v(p) = 1$ or $v(q) = 1 = true$ — without loss of generality, say $v(p) = 1$. Let $v'$ agree with $v$ on all variables except possibly $r$, where $v'(r) = 0 = false$. Then $$ v'((p \lor r)\wedge (q \lor \lnot r)) = 1, $$ so $(p \lor r)\wedge (q \lor \lnot r)$ is satisfiable too.

  • $\begingroup$ (1) I feel it hard to understand what does it mean $x$ is satisfiable if and only $y$ is satisfiable. Does that mean $y \to x$? (2) Does "$(p \vee q)$ is satisfiable if and only if $(p \lor r)\wedge (q \lor \lnot r)$ is satisfiable" means the converse, i.e. $(p \lor q) \to (p \lor r)\wedge (q \lor \lnot r)$? (3) and very sorry I didnt get the explanation with $v()$, may be a truth table might help me, if thats easy to form, may be with wolframalpha $\endgroup$ – anir123 Dec 28 '15 at 21:40
  • $\begingroup$ (1) No, it does NOT mean that. It means (there's some assignment of values to variables in $x$ making $x$ true) if and only if (there's some assignment of values to variables in $y$ making $y$ true). (2) No, $(p\lor q)\to (p\lor r)\land(q\lor \neg r)$ is not provable, and is not valid. (3) $v$ IS the truth table. $v(p) = true, v(q) = false, v(r) = false$ satisfies $(p\lor r)\land(q\lor \neg r)$ $\endgroup$ – BrianO Dec 28 '15 at 21:59
  • $\begingroup$ Did my last comment clarify? $\endgroup$ – BrianO Dec 29 '15 at 16:23
  • $\begingroup$ Very sorry for late response. That was actually easy, but your sentence formation in last paragraph of answer confused me, especially because I didn't came across $v()$ stuff earlier. But now it looks normal that I get it, only if following summary I get is correct: "the converse $(p\vee q)\to (p\vee r)\wedge(q\vee \lnot r)$ is not valid/tautology, but its satisfiable for values $p=1, q=1, r=0$". Thats it there right?...And lastly about your response to my question (1) Just curious if you can give me example of: "$x$ is satisifiable if and only if $y$ is satisifiable, but $y \not \to x$" $\endgroup$ – anir123 Dec 31 '15 at 13:43
  • $\begingroup$ I just cleaned up the language a bit, hopefully it's an improvement. As for your last question asking for an example of $x$ satisfiable iff $y$ satisfiable, but $x\leftrightarrow y$ not valid (= provable), now we know one: $x := (p\lor q)$, $y := (p\lor r)\land(q\lor \neg r)$. $\endgroup$ – BrianO Dec 31 '15 at 15:45

The second statement (with the "if and only if") is false (consider what would happen if we had $p$ and $r$ true and $q$ false). The two formulae are not equivalent.


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.