Problème 2SAT Utilisation du graphique d'implication
-
05-11-2019 - |
Question
Je faisais une question de pratique. Comme vous pouvez le voir ci-dessous, il existe un graphique d'implication. Pour vérifier si le problème est satisfaisant, j'ai vérifié s'il y avait des «mauvaises boucles». Pour ce faire, pour chaque littéral / variable dans la formule booléenne, je vois s'il y a un chemin de x ---> - x et de -x ----> x si les deux existent, alors une «mauvaise boucle» existe et existe et Ainsi, le problème n'est pas satisfait. Je l'ai fait et j'ai vu qu'il n'y avait pas de telles boucles et donc je suis arrivé à la conclusion que le problème 2SAT était satisfaisant. Voir ci-dessous:
J'ai réalisé que l'option D (le problème 2SAT est satisfaisable si A, B, C et D sont définis sur False. J'ai du mal à arriver à cette conclusion en regardant le graphique. Je comprends que vous empruntez tous les chemins du graphique et voyez si vous arrivez à une contradiction? Quelqu'un peut-il me laisser comprendre comment comprendre l'option D est correcte.
Merci d'avance!
La méthode que j'ai proposée est d'écrire les arcs / bords pour chaque implication et de travailler en arrière pour dériver la formule booléenne 2SAT et voir si cela fonctionne. Est-ce que quelqu'un connaît un moyen plus rapide? :)
Pas de solution correcte