Pergunta

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? :)

Nenhuma solução correta

Licenciado em: CC-BY-SA com atribuição
Não afiliado a cs.stackexchange
scroll top