MGU und variable Standardisierung - CNF

Question

Ich habe beim Konvertieren erster Ordnung in logische Sätze in die konjunktive normale Form gelesen und dann die Auflösung durchgeführt.

Einer der Schritte für die Konvertierung in CNF ist die Standardisierung von Variablen: Benennen Sie alle Variablen um, sodass jeder Quantifizierer seinen eigenen eindeutigen Variablennamen hat.

Die meisten allgemeinen Einfasser sind die am wenigsten spezialisierte Vereinigung von zwei Klauseln.

Frage 1: Ich habe gesucht, um ein Beispiel zu finden, das zeigt, was die potenziellen Probleme sind, wenn ich Variablen nicht standardisiere, aber alle Online -Ressourcen, die ich gefunden habe, erklären nur das "Wie" und nicht das "Warum". Könnten Sie mir ein Beispiel für ein potenzielles Problem geben?

Frage 2: Das gleiche Problem wie die erste Frage. Was ist, wenn wir MGU nicht verwenden und einen spezielleren Unifier verwenden? Was sind die potenziellen Probleme? Könnten Sie mir ein Beispiel geben?

Mein aufrichtiger Dank. Felipe

Answer 1

1. Sehen Diese Antwort - Es ist ein Beispiel für eine widersprüchliche Reihe von Klauseln, in denen wir keinen Widerspruch abgeben können, ohne Variablen zu umbenennen. Beachten Sie, dass es nicht ausreicht, Variablen nach der Umwandlung in CNF nur umzubenennen. Wir müssen Variablen umbenennen, um vorher unterschiedlich zu sein jeder Anwendung der Auflösungsregel. Sie können es wie folgt betrachten: Eine Variable, die in zwei unterschiedlichen Klauseln erscheint, hat in jedem von ihnen eine andere Bedeutung, da sie implizit universell quantifiziert werden. Wenn wir die Variable in einem der Klauseln nicht umbenennen, gehen wir falsch an, dass die Variable in beiden Klauseln dasselbe bedeutet.

2. Durch die Verwendung von MGU leiten wir die allgemeinste Klausel in einem Auflösungsschritt ab. Wenn wir ein Unifier verwenden, der spezialisierter ist als ihre MGU, ist die resultierende Klausel schwächer. Dies bedeutet, dass wir nicht all das Wissen geschlossen haben, das wir konnten, und wir können eine Ableitung einer leeren Klausel verpassen, auch wenn sie existiert. Zum Beispiel: begin {array} {c} p (x, y) lor q (y) lnot q (d) lnot p (c, d) end {Array}, wenn wir a machen Resolvent von den ersten beiden Klauseln mit MGU, die $ y bis d $ sendet, erhalten wir $ P (x, d) $ und können mit der dritten Klausel fortfahren. Wenn wir einen schwächeren Unifier nehmen, wie es auch einen $ x bis d $ sendet, erhalten wir $ P (D, D) $ und wir können mit der dritten Klausel kein Resolvent machen. Dies bedeutet, dass die Methode nicht mehr abgeschlossen ist.