Ist die Auflösung vollständig oder nur Widerstandsvorgehen?

Question

Durchgehen Einige Tutorials für Wissensrepräsentation Im Moment bei der Lösung, und ich stieß auf Folie 05.KR, Nr. 77.

Dort wird erwähnt, dass "die Prozedur ebenfalls abgeschlossen ist".

Ich denke, diese Vollständigkeit kann nicht bedeuten, dass ein Satz von KB durch die Lösung abgeleitet wird. Beispielsweise kann die Auflösung $ (q lor neg q) $ aus einem KB mit einer einzelnen Klausel $ neg p $ nicht ableiten. (Beispiel von KRR, Brachman und Levesque, Seite 53).

Könnte mir jemand helfen, herauszufinden, was auf dieser Folie gemeint ist? Bezieht sich die Vollständigkeit der Folie auf Refutaton-Complete und kein vollständiges Beweisverfahren?

Answer 1

Die Auflösung ist abgeschlossen als Refutation -System. Das heißt, wenn $ s $ ein widersprüchlicher Satz von Klauseln ist, kann die Resolution $ s $, dh $ s vdash bot $, widerlegen.

Dies reicht aus, da $ t vdash a $ $ $ t cup { lnot a } vdash bot $ entspricht. Wenn wir also sehen möchten, dass eine Formel $ a $ von $ t $ abgeleitet ist, müssen wir nur überprüfen, ob es einen Refutationsnachweis für $ t cup { lnot a } $ gibt, das mit Auflösung überprüft werden kann.

Answer 2

Die Lösung ist, wie Sie bereits erwähnt haben, nur widerlegen. Das ist beabsichtigt und sehr nützlich, weil es den Suchraum drastisch reduziert. Anstatt schließlich jede mögliche Konsequenz abzuleiten (um einen Beweis für eine Vermutung zu finden), versucht die Lösung nur, die leere Klausel abzuleiten.

Answer 3

Es ist im folgenden Sinne auch implizit vollständig:

Wenn eine Reihe von Klauseln $ f $ eine nichttautologische Klausel $ C $ impliziert, ist es immer möglich, eine einzige Klausel $ C '$ abzuleiten, die $ C $ (dh $ c' subseteq c $) absumme.

Quelle:
Christian G. Fermüller, implizite Vollständigkeit der unterschriebenen Resolution, 2002

Beachten Sie, dass das ursprüngliche Ergebnis erwähnt wird:
RCT Lee. Ein Vollständigkeitstheorem und ein Computerprogramm für Nding -Theorems abgeleitet aus gegebenen Axiomen. Ph.D. These, University of California, Berkely, 1967.