0
$\begingroup$

I was doing a practice question. As you can see below there is an Implication graph. To check whether the problem is satisfiable, I checked whether there were any 'bad loops'. To do so, for each literal/variable in the boolean formula, I see if there is a path from X --->-X and from -X---->X if both exist then a 'bad loop' exists and thus the problem is not satisfiable. I did that and saw that there were no such loops and thus I came to the conclusion that the 2SAT problem was satisfiable. See below: enter image description here

I realized that option d (The 2SAT problem is satisfiable if a,b,c and d are set to false. I'm struggling to come to this conclusion by looking at the graph. My understanding is that you take all the paths in the graph, and see if you come to a contradiction? Can someone please let me understand how to understand option d being correct.

enter image description here

Thanks in advance!

The method I have come up with is to write out the arcs/edges for each implication and work backwards to derive the 2SAT boolean formula and see if it works. Does anyone know a quicker way? :)

$\endgroup$
  • $\begingroup$ An implication $p\rightarrow q$ is unsatisfied only if $p$ becomes True and $q$ becomes False. If $a,b,c,d$ are set to false, then we will only need to check those implications with antecedent like $\lnot a, \lnot b, \lnot c, \lnot d$, all of which are on the bottom line. However, all those implications has consequent among themselves, i.e., all are set to true. So we cannot find any unsatisfied implications. That is, the 2SAT is satisfied. $\endgroup$ – Apass.Jack Nov 13 '18 at 8:16
0
$\begingroup$

For any variable $X$, if there is a path from $X$ to $\neg X$ then you cannot set $X$ to $True$, since otherwise you would end up with a $True \Rightarrow False$ implication somewhere along the path. For the same reason, if there is a path from $\neg X$ to $X$ you cannot set $X$ to $False$.

Hence, in the first case you must set $X$ to $False$, in the second you must set it to $True$. If there are paths in both directions, as you already know, the formula is not satisfiable.

In your example, there are only paths from $X$ to $\neg X$ for all variables, hence the only assignment that satisfies the instance is the one where all variables are $False$.

$\endgroup$

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.