Pergunta

I am trying to convert the following 2-sat clauses to implications and then draw the implication graph.

The clauses are: {¬xvy}, {¬yvz}, {¬zvw} ,{¬wvu},{¬uv¬x},{xvw},{¬wvx}

I converted the boolean literals into implications so I could construct the implication graph:

{¬xvy}: I have x-->y and ¬x -->¬y

{¬yvz} : I have y-->z and ¬y-->¬z

{¬zvw} : I have z-->w and ¬z-->¬w

{¬wvu} : I have w-->u and ¬w--->¬u

{¬uv¬x} : I have u-->¬x and ¬x-->¬u

{xvw} : I have ¬x-->w and ¬w-->x

{¬wvx} : I have w-->x and ¬w-->¬x

Am I doing this right? If so, I have constructed this implication graph to prove it is not satisfiable.

enter image description here

I would argue that these literals are not satisfiable because of the infinite loops you can have from ¬w ¬x ¬y ¬z ¬w and w x y z w. Is this a sufficient enough explanation?

Thanks in advance!

Nenhuma solução correta

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