Nächste Seite: 3.4 Negation als Mißerfolg Vorige Seite: 3.2 Annahme der Weltabgeschlossenheit

3.3 Prädikatsvervollständigung

Die im vorangegangenen Abschnitt behandelte Annahme der Weltabgeschlossenheit ist ein Beispiel der dort ebenfalls beschriebenen allgemeineren Idee, zu einer gegebenen Weltbeschreibung noch eine Reihe von zusätzlichen Annahmen hinzuzunehmen, wie es die Abbildung 3.1 bereits illustriert hat. In diesem Fall bestehen diese Annahmen nur aus negierten Grundatomen. Im vorliegenden Abschnitt werden wir ein weiteres Beispiel dieser allgemeinen Idee kennenlernen, in dem auch allgemeinere Formeln als Annahmen zur Weltbeschreibung hinzugefügt werden.

Betrachten wir zur Illustration zunächst als einfachstes Beispiel eine Welt, die allein durch die Formel charakterisiert ist. Unser Alphabet dagegen enthalte noch zusätzlich die Konstante . Als Universum bei der Modellierung dieser Formel betrachten wir die Menge . Wie bei der AWA bereits illustriert, möchte man in diesen Ansätzen bei dem so gewählten Universum nur solche Modelle zulassen, die all diejenigen (und keine weiteren) Konstanten in der Interpretation von enthalten, für die die entsprechende Atomformel (wie hier ) auch ableitbar ist. Rein logisch wäre dagegen auch als Interpretation für unser möglich. In diesem Sinne strebt man also eine Minimierung der Menge der möglichen Modelle an. Dies läßt sich außer mit der AWA auch wie folgt realisieren.

Wir formen äquivalent zu um. Diese Implikation betrachten wir als den ``wenn''-Teil einer Definition des Prädikats . Um nun andere Objekte als aus einer Interpretation von auszuschließen, müssen wir nur den ``nur-wenn''-Teil dieser Definition, also die Formel als Annahme hinzufügen, so daß sich insgesamt ergibt. Wir nennen diese Erweiterungsoperation Prädikatsvervollständigung und die hinzugefügte Formel die Vervollständigungsformel. Sie ist in [Cla78] eingeführt worden.

Würde unsere Welt noch zusätzlich durch charakterisiert sein, so ergäbe sich die Vervollständigungsformel . Ist in dieser Weise ein Prädikat nur durch Grundatome definiert, so hat die Prädikatsvervollständigung genau den gleichen Effekt wie die AWA. Wie wir gleich sehen werden, ist das im allgemeinen nicht mehr der Fall. Wieder müssen wir auf Konsistenzprobleme achten. Betrachten wir zB. die sehr einfache Formel , die äquivalent zu ist, so erhält man mit der Prädikatsvervollständigung die inkonsistente Formel  [She84]. Wie bei der AWA müssen wir uns auf die Suche nach einer Formelklasse machen, bei der sich durch diese Operation keine Inkonsistenzen einschleichen. Diesem Ziel dient die folgende Definition.

Eine Menge von Klauseln heißt solitär in , wenn jede Klausel mit einem (in negativer Repräsentation) positiven Auftreten von kein weiteres Auftreten von enthält.

Die Klausel ist in diesem Sinne nicht solitär in , weil neben dem positiven Auftreten in noch zusätzlich das negative Auftreten in vorhanden ist. Sie ist aber solitär in , weil es überhaupt kein positives Auftreten von gibt. Im übrigen handelt es sich um eine Hornklausel, wie auch allgemein solitäre Klauseln Horn (in den betreffenden Prädikaten) sind. Auch die obige Formel, die bei der Prädikatsvervollständigung eine Inkonsistenz erzeugte, ist nicht solitär. Nur für solitäre Klauselmengen werden wir nun die Prädikatsvervollständigung definieren, bei denen sich dann keine Inkonsistenzen ergeben können. Dies geschieht wie folgt.

Sei also eine Klauselmenge, die solitär in ist. Diejenigen unter diesen Klauseln, die ein positives Auftreten von enthalten, lassen sich in der folgenden Form schreiben.

Wie oben bereits im speziellen Fall illustriert, gehen wir von dieser Form über zu der folgenden äquivalenten Form.

Nehmen wir an, in der Prämisse treten außer den noch die Variablen auf. Dann ist der Allabschluß dieser Formel äquivalent mit der folgenden Formel.

Auf diese Gestalt bringen wir nun alle Klauseln mit einem positiven Auftreten von . Nehmen wir an, es gibt Stück hiervon. Jede hat also die Gestalt

. Ihre Konjunktion ist wiederum äquivalent mit

Die Vervollständigungsformel hierzu ist gegeben durch

Zu einer in solitären Klauselmenge ist die unter der Prädikatsvervollständigung bezüglich erhaltene Theorie definiert durch

Aus [GN89] übernehmen wir den folgenden Satz.

Ist konsistent, so auch .

Die Prädikatsvervollständigung führt ebenfalls zu einem nichtmonotonen Verhalten; denn ergänzt man eine Weltbeschreibung mit neuen Klauseln, die solitär in sind, dann erweitert man im allgemeinen damit auch den Interpretationsbereich von . Ein einfaches Beispiel ist die Welt erweitert mit .

Die Prädikatsvervollständigung läßt sich natürlich auch auf den Fall mehrerer Prädikate anwenden. Wir betrachten hierzu das folgende Beispiel.

Wendet man nun die Prädikatsvervollständigung auf die Prädikate und an, so erhält man die beiden Vervollständigungsformeln

in denen mit den Regeln von der Pfeil auch in die andere Richtung hinzugefügt werden kann. Über irgendwelche Abnormalitäten von Larissa verrät uns die Prädikatsvervollständigung nichts; somit ist weder Liebt_Eiscreme(Larissa) noch Liebt_Eiscreme(Larissa) ableitbar (was durchaus Sinn in dieser Situation macht). Im Gegensatz dazu führt die AWA in diesem Beispiel zu einem Widerspruch, da mit ihr beide Literale ableitbar werden. Die beiden Vervollständigungsmechanismen zeigen also tatsächlich ein unterschiedliches Verhalten. Alle Beispiele, die wir aber im vorangegangenen Abschnitt mit der AWA erfolgreich behandelt haben, führen auch mit der Prädikatsvervollständigung zum gleichen Ergebnis.

Damit die Zusammenhänge nicht übersehen werden, weisen wir anhand dieses Beispiels auf den Bezug zu den in Abschnitt 2.6 behandelten Vererbungsnetzen hin. Unser Beispiel ist offensichtlich von genau der dort behandelten Form. Um Widersprüche beim Vorliegen von Ausnahmen zu vermeiden, wurde hier in die Regeln jeweils ein Abnormalitäts-Prädikat eingeführt. Diese Technik ist als Alternative zu der dort besprochenen Lösung anzusehen. Über die Beziehung unter diesen beiden Alternativen ist wenig bekannt. Nur sieht man, daß hier die Regeln nicht wie dort immer nur auf eine Prämisse beschränkt sein müssen. Andererseits gewährleistet die Einführung von Abnormalitätsprädikaten für sich allein nicht die Bevorzugung von spezifischerer Information.

Die Vervollständigung in bezug auf mehr als ein Prädikat ist nicht immer so problemlos wie in dem gegebenen Beispiel. Die jeweiligen Klauseln können sich zB. überlappen, dh. eine Klausel kann je ein positives Literal zweier verschiedener Prädikate enthalten; oder die Vervollständigung bezüglich der einen Klausel kann sich auf die der anderen auswirken (in möglicherweise zirkulärer Weise). Mit einigen Vorsichtsmaßnahmen, wie parallele Vervollständigung und Ordnung der Prädikate , so daß in den Definitionsklauseln für nur Prädikate mit auftreten, läßt sich unsere Definition auch im allgemeinen auf mehrere Prädikate erweitern [GN89]. In dieser verallgemeinerten Form wurde die Prädikatsvervollständigung von Clark auf die PROLOG Programmierung zur Rechtfertigung der Negation als Mißerfolg angewandt, die wir im folgenden Abschnitt 3.4 behandeln.