Équivalence des formules KROM APPLIQUES?

Question

supposer que j'ai deux KROM Formulas $ \ psi_1, \psi_2 $ .Les formules KROM sont des formules propositionnelles dans le CNF qui ont 2 littéraux dans chaque clause.Chaque littéral peut être annulé ou non préparé.En d'autres termes, $ \ PSI_1, \ PSI_2 $ sont des formules 2-CNF.Par exemple:

$ (x_1 \ vee \ neg x_2) \ terre (\ neg x_2 \ vee x_3) \ terres (x_3 \ vee x_4) $

Je veux décider si $ \ psi_1, \ psi_2 $ sont logiquement équivalents, c'est-à-dire, $ \ psi_1 \ Leftrightarrow\ psi_2 $ .Équivalent, je veux vérifier si $ f= (\ psi_1 \ vee \ neg \ psi_2) \ wedge (\ nge \ psi_1 \ vee \ psi_2) $ est vrai pourToutes les affectations de $ x_1, \ dots, x_n $ .

Ce problème est-il traitable?

Answer 1

Oui, l'équivalence peut être vérifiée en temps polynomial (en fait, dans le temps quadratique).

Je vais décrire comment tester si $ \ psi_1 \ lor \ neg \ psi_2 $ est vrai pour toutes les missions. Vous pouvez faire la même chose pour $ \ neg \ psi_1 \ lor \ psi_2 $ et utilisez-le pour tester si $ f $ est une tautologie, c'est-à-dire si $ \ psi_1, \ psi_2 $ est logiquement équivalent.

Je vais le faire en vérifiant si $ \ psi_1 \ lor \ neg \ psi_2 $ est faux pour n'importe quelle affectation, ou en d'autres termes, que $ \ nge (\ psi_1 \ lor \ neg \ psi_2) $ est satisfible. Notez que

$$ \ nge (\ psi_1 \ lor \ neg \ psi_2)=neg \ psi_1 \ terres \ psi_2, $$

Il suffit donc de tester sa satisfaction de $ \ neg \ psi_1 \ terres \ psi_2 $ où $ \ psi_1, \ PSI_2 $ sont des formules KROM (2-CNF).

Supposons que $ \ PSI_1= C_1 \ Land \ CDOT \ Land C_K $ Où $ C_I $ est la i $ i $ ème clause dans $ \ psi_1 $ . Alors

$$ \ NEG \ psi_1= (\ neg c_1) \ lor \ CDOT \ lor (\ nge c_k). $$

donc

$$ \ commence {align *} \ NEG \ PSI_1 \ Land \ psi_2 &= (((\ ng c_1) \ lor \ CDOT \ lor (\ ng c_k)) \ Land \ psi_2 \\ &= (\ ng c_1 \ terres \ psi_2) \ lor \ CDOT \ lor (\ ng c_k \ terres \ psi_2). \ fin {align *} $$

MAINTENANT, $ \ NEG \ PSI_1 \ Land \ PSI_2 $ est satisfiatable IFF $ \ nge c_i \ terres \ psi_2 $ est satisfait pour certains $ i $ . Donc, nous pouvons itérer sur $ i $ et tester la satisfaction de chaque $ \ neg c_i \ terres \ psi_2 $ ; Si l'un d'entre eux sont satisfiables, alors $ \ neg \ psi_1 \ lor \ psi_2 $ est satisfiable et $ f $ n'est pas une tautologie et $ \ psi_1, \ psi_2 $ ne sont pas logiquement équivalents.

Comment tester la satisfaction de $ \ NEG C_I \ Land \ psi_2 $ ? Eh bien, $ C_I $ a la forme $ (\ ell_1 \ lor \ ell_2) $ où $ \ ell_1, \ ell_2 $ sont deux littéraux, donc $ \ ng c_i \ terres \ psi_2 $ a la forme < span class="math-conteneur"> $ \ neg \ ell_1 \ terres \ nge \ ell_2 \ terre \ psi_2 $ . Il s'agit également d'une formule KROM (2-CNF), de sorte que vous pouvez tester sa satisfaction à l'aide de l'algorithme de temps polynomial standard. Vous effectuez un nombre linéaire de tels tests, de sorte que le temps de fonctionnement total est polynomial. En fait, il est quadratique, car la satisfaction des tests peut être faite en temps linéaire.

Answer 2

Rappelez la solution 2-SAT qui utilise des composants fortement connectés: nous construisons un graphique avec des sommets $ x_1, \ ldots, x_n, \ lnot x_1, \ ldots, \ lnot x_n $ < / Span>, et nous remplaçons chaque clause $ x_i \ lor x_j $ avec bords $ \ lnot x_i \ to x_j $ < / span> et $ \ lnot x_j \ to x_i $ . Un exemple de ici :

Pour satisfaire la formule, il est nécessaire et suffisant d'attribuer des sommets de manière à ce qu'il n'y ait pas de contradiction dans le graphique (no edge $ true \ to false $ ). Nous utiliserons ces graphiques pour la vérification de l'équivalence.

1. Nous construisons ces graphiques $ g_1 $ et $ g_2 $ pour les deux formules $ f_1 $ et $ f_2 $ .
.
2. S'il y a un cycle $ x_i \ leadsto \ lnot x_i \ leadsto x_i $ Dans un graphique, sa formule n'a pas de solution. Nous vérifions que les deux formules sont solvables / insolubles.
3. S'il existe un chemin de forme $ x_i \ leadsto \ lnot x_i $ (de la même manière pour le cas $ \ lnot X_I \ Leadsto x_i $ ), nous savons que pour satisfaire la formule, nous devons sélectionner $ x_i $ pour être faux (sinon nous avons une contradiction). Nous nous souvenons de ce choix. En utilisant le graphique, nous pouvons affecter des valeurs à tous les sommets accessibles à partir de $ \ lnot x_i $ (ils doivent être vrais). Encore une fois, vérifiez que les deux formules ont fait exactement les mêmes décisions à la fin.
4. Retirez tous les bords vers / depuis tous les sommets connus des graphiques.
5. maintenant, $ f_1 $ et $ f_2 $ est équivalent $ \ iff $ Les graphiques restants sont équivalents au sens suivant: Pour tout $ V_1, V_2 $ chemin $ v_1 \ pladsto v_2 $ existe dans $ g_1 $ iff il existe dans $ g_2 $ . Cela peut être enregistré au plus $ o (| v | \ CDOT | e |) $ heure (il s'agit simplement de DFS de chaque sommet et vérifiez qu'il a visité la même chose sommets pour les deux graphiques). Peut-être que cela peut être fait plus vite.

Preuve :

$ \ wastearrow $ : évident, puisque après la fermeture transitive des graphiques, nous aurons les mêmes conséquences dans les deux formules.

$ \ RightARrow $ : par contradiction. Wlog nous supposons qu'il existe un chemin $ v_1 \ pladsto v_2 $ in $ g_1 $ qui ne existent dans $ g_2 $ . Cela signifie que l'affectation $ v_1:= true $ , $ v_2:= false $ est réalisable dans $ f_2 $ (car il n'y a pas de chemin $ v_1 \ pladsto v_2 $ ) mais est infaisable dans $ f_1 $ .

nommément, la mission suivante satisfait $ f_2 $ :

• $ vrai $ pour tous les sommets accessibles à partir de $ v_1 $ .
. . .
• $ false $ de tous les sommets pouvant atteindre $ v_2 $ .
. .
• Enlevez tous les sommets connus (mentionnés ci-dessus et leurs compléments) du graphique. Tous les sommets restants créent des composants connectés. Nous colorons des composants connectés dans $ true $ et des composants connectés correspondant à leurs compléments - dans $ false $ ( Voir la note ci-dessous).

Cette affectation n'a aucune contradiction, car il ne peut y avoir de bord $ u \ to v $ de formulaire $ vrai \ à faux $ :

• si $ u $ appartient à un composant coloré de couleur $ vrai $ , alors telle < span class="math-conteneur"> $ v $ doit également être vrai.
• sinon, cela signifie que u $ u $ est accessible à partir de $ v_1 $ , et donc $ V $ est également accessible à partir de $ v_1 $ et doit être vrai. $ \ blacksquare $

note technique : pour chaque variable $ x_i $ Il y a deux sommets:

une classe="math-conteneur"> $ v_i $ et $ \ lnot v_i $ - et on peut se demander si cela conduira à certains problèmes avecmissions.La réponse est qu'après l'étape 4), $ v_i $ et $ \ lnot v_i $ se situera en deuxDifférents composants (d'ailleurs, ils sont symétriques: $ u \ to v $ dans un moyen de composant $ \ to \ to \lnot v $ dans un autre).Par conséquent, quelle que soit la décision que nous faisons pour $ u $ dans un composant, nous pouvons faire la décision opposée pour $ \ lnot u $ dans un autre.