Utilisez 2Sat pour montrer qu'un graphique d'implication doit avoir un cycle si ce n'est pas satisfait.

Question

Utilisation de graphiques 2SAT et d'implication, comment pourrais-je prouver les propriétés suivantes des graphiques d'implication:

Supposons qu'il existe un chemin dirigé entre les littéraux L1 et L2 dans g_φ. Ensuite, il y a aussi un chemin dirigé entre leurs compléments. Ensuite, il y a τ, une assignation de vérité satisfaisant φ où τ (l1) est vrai, alors τ (L2) doit également être vrai.

Utilisation de cela, montrez que φ est insatisfait <=> Il existe un cycle dirigé dans g_φ contenant une variable X et son complément.

où g_φ est le graphique d'implication dirigé de 2SAT contenant une formule φ avec n variables. Par conséquent, 2n sommets avec un pour chaque littéral possible en φ et les bords (pas L1, L2) et (pas L2, L1) pour chaque clause (L1 L2) dans.

Ma première intuition était une preuve par contradiction, mais je n'ai pas construit une hypothèse suffisante générale. J'ai ensuite essayé de montrer que si l'affectation de vérité signifie que L1 et L2 sont vraies, alors en construisant un cycle reliant toutes les variables, l'affectation n'est valable que lorsque ces bords existent. Cependant, cela ne semble pas assez rigoureux car je ne comprends pas correctement pourquoi le cycle exige que le complément de x existe.

Je construis actuellement G en ajoutant un sommet pour chaque variable X et son complément. Ensuite, pour chaque clause (A v B), j'ajoute un bord entre non pas A et B et non B et A.

Cependant, je ne vois pas comment cela formerait spécifiquement un cycle.

Travailler du manuel SIPSER.

Answer 1

Voici une esquisse à la épreuve. Nous montrerons que la formule donnée est insatisfaite IFF existe un cycle contenant à la fois $ x x $ et $ \ lnot x $ < / span>, pour une variable $ x $ .

Supposons d'abord qu'il existe un cycle contenant à la fois $ x $ et $ \ lnot x $ . L'existence d'un chemin $ x \ to ^ * y $ dans le graphe d'implication signifie que dans une affectation satisfaisante, si $ x $ tient puis $ y $ (vous pouvez le prouver par induction sur la longueur du chemin). Comme il y a un cycle contenant à la fois $ x $ et $ \ lnot x $ , il y a des chemins $ x \ to ^ \ lnot x $ et $ \ lnot x \ to ^ * x $ . Dans n'importe quelle affectation satisfaisante, $ x $ ou $ \ lnot x $ est titulaire et les deux cas conduit à contradiction.

Supposons qu'il n'y ait pas de cycles contenant à la fois $ x $ et $ \ lnot x $ . Nous allons construire une affectation satisfaisante comme suit. Choisissez une variable $ x $ . S'il y a un chemin $ x \ to ^ \ lnot x $ , attribuer $ x= f $ et pour chaque littéral $ \ ell $ telle que $ \ lnot x \ to ^ * \ ell $ , Attribuez la valeur à la variable sous-jacente qui fait $ \ ELL $ vrai. Vous ne pouvez attribuer la même variable deux valeurs de vérité différentes, car si $ \ lnot x \ to ^ * y $ et $ \ lnot x \ to ^ * \ lnot y $ alors aussi $ y \ to ^ * x $ et donc aussi $ \ lnot x \ to ^ * x $ , terminant un cycle impliquant $ x $ et $ \ lnot x $ .

S'il y a un chemin $ \ lnot x \ to ^ * x $ , assignez $ x= t $ < / span> et continuer analoguer.

Si aucun de ces chemins n'existe, assignez $ x $ arbitrairement et continuez comme avant. Cela ne peut conduire à une contradiction, pour la raison suivante. Supposons que nous assignions $ x= f $ , et qu'il y a des chemins $ x \ to ^ * y $ et $ x \ to ^ * \ lnot y $ . Ensuite, il y a aussi un chemin $ y \ to ^ * \ lnot x $ et donc un chemin $ x \ to ^ * \ lnot x $ , contredisant l'hypothèse selon laquelle aucun des deux chemins n'existe.

Si, après ce processus, il y a une variable non attribuée à gauche, choisissez l'un d'entre eux et répétez jusqu'à ce que l'affectation couvre toutes les variables.