T10 2SAT e grafos dirigidos
Considere a seguinte fórmula booleana:
\( \phi=(x_0\vee x_2)\wedge(x_0\vee\neg x_3)\wedge(x_0\vee\neg x_5) \wedge(x_1\vee\neg x_3)\wedge(x_1\vee\neg x_4)\wedge(x_1\vee\neg x_5) \wedge(x_2\vee\neg x_4)\wedge(x_2\vee\neg x_5) \wedge(x_3\vee x_6) \wedge(x_4\vee x_6) \wedge(x_5\vee x_6). \)
Lembre que $a\vee b$ é equivalente a ambos $\neg a\Rightarrow b$ e $\neg b\Rightarrow a$. Usando esse fato, monte o "grafo de implicações" de $\phi$, que aparece na página 8 de https://www.ime.usp.br/~yoshi/Sedgewick/Algs4th/Slides/42DirectedGraphs.pdf
Nesse grafo dirigido, para cada variável $x$ que ocorre em $\phi$, os literais $x$ e $\neg x$ devem ocorrer como vértice. Ademais, para cada cláusula $a\vee b$ que ocorre em $\phi$, o grafo de implicações de $\phi$ deve conter as arestas $\neg a\Rightarrow b$ e $\neg b\Rightarrow a$.
(i) Encontre uma atribuição de valores-verdade ("true" e "false") às variáveis que ocorrem em $\phi$ para que $\phi$ torne-se verdadeira.
Sugestão. Considere uma ordenação topológica dos vértices do grafo de implicações, como, por exemplo, \( \neg x_6, x_5, x_4, x_3, x_1, \neg x_0, x_2, \neg x_2, x_0, \neg x_1, \neg x_3, \neg x_4, \neg x_5, x_6 \).
(ii) Considere agora a fórmula booleana $\psi=\phi\wedge(\neg x_1\vee\neg x_2)\wedge(\neg x_6\vee x_5)$ onde $\phi$ é como acima. Prove que $\psi$ não é satisfatível, isto é, que não existe uma atribuição de valores-verdade às variáveis que ocorrem em $\psi$ de forma que $\psi$ torne-se verdadeira.
Sugestão. Considere o grafo de implicações de $\psi$.