Doubt regarding the implications of a 2-SAT constraint Consider an example 2-SAT instance with the constraint (x1​ ∨ x2)​.
This CNF has these two implications:
¬x1​→x2​ and ¬x2​→x1​.
&quot;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.&quot;
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, &quot;$x_1$ is false then $x_2$ must be true&quot; 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.