Consider an example 2-SAT instance with the constraint (x1​ ∨ x2)​. This CNF has these two implications:

¬x1​→x2​ and ¬x2​→x1​.

"They actually mean, if x1​ is false then x2​ must be true, and if x2​ is false then x1 must be true, respectively. Any other case would make the 2-sat problem unsatisfiable."

My doubt is regarding this statement. I can understand the above written two implications, but I don't understand how only those two values of x1 and x2 make this 2-SAT instance satisfiable. Clearly setting both x1 and x2 to true can also satisfy this constraint. I don't see that case being captured in the two implications written above.

Can someone explain this to me? Apologies if this is a stupid question, I haven't formally studied logic.


$A\rightarrow B$ doesn't necessarily mean that $B\rightarrow A$. In your example, "$x_1$ is false then $x_2$ must be true" doesn't imply that if $x_2$ is true, $x_1$ must be false. Therefore, setting both $x_1$ and $x_2$ to true would not contradict the statement.

Also, as a side note, $\lnot x_1\rightarrow x_2$ is logically equivalent to $\lnot x_2 \rightarrow x_1$, so the two implications you described are identical.

  • $\begingroup$ Did you mean ¬x2 → x1 and ¬x1​→x2​ ? $\endgroup$ – ashishmax31 Mar 12 at 19:32
  • $\begingroup$ yes, this is what I meant. $\endgroup$ – nir shahar Mar 12 at 20:40
  • $\begingroup$ thanks for pointing out $\endgroup$ – nir shahar Mar 12 at 20:40

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.