Beginnen wir mit der (logisch) einfachen Welt einer Datenbank. Als Beispiel betrachten wir das folgende Fragment eines Fahrplans der Bundesbahn.
W = { | Zugverbindung ![]() ![]() |
Zugverbindung ![]() ![]() | |
Zugverbindung ![]() ![]() |
SeiWenneine Menge von Formeln der Prädikatenlogik erster Stufe über einem Alphabet
. Die unter der Annahme der Weltabgeschlossenheit erhaltene Theorie
ist definiert durch
![]()
wobei
![]()
Abbildung 3.1: Die Hinzunahme von Annahmen
Eine Theorie heißt vollständig
, wenn für jedes Grundatom
über der gegebenen Sprache entweder
oder
gilt. Die Annahme der Weltabgeschlossenheit macht jede
Datenbanktheorie zu einer vollständigen Theorie. Sie führt insgesamt zu
einem nichtmonotonen Verhalten, denn die Hinzunahme eines weiteren Atoms
erfordert die Entfernung einer impliziten Annahme, die dann nicht mehr
zur Theorie gehört.
Wir haben schon in Abschnitt 3.1 erwähnt, daß die Inferenzrelation
selbst als Wissen aufgefaßt werden kann. Genauer würde man hier von
Meta-Wissen sprechen. Bei gegebenem
(und
) ist die Menge
der durch die AWA gemachten Annahmen eindeutig bestimmt, und zwar
durch Wissen, das man ebenfalls der Meta-Ebene zuordnen würde. Es ist daher
nicht überraschend, daß man die AWA nicht nur durch die bislang
besprochene Erweiterung der Weltbeschreibung durch zusätzliche Annahmen,
sondern äquivalent auch durch eine Modifikation von
beschreiben kann.
Für beliebige FormelnNur die zweite dieser drei Regeln zur Definition von, Grundatome
und für jede beliebige Menge
von Formeln der Prädikatenlogik erster Stufe über einem Alphabet
sei die Relation
induktiv wie folgt definiert.
Dann nennen wir
- Gilt
, so auch
.
- Gilt
, so gelte
.
- Gilt
und
, so auch
.
![]()
In einem entsprechenden Kalkül für die Prädikatenlogik ergibt sich eine
zusätzliche Kalkülregel, die der zweiten Regel entspricht und von der
folgenden Gestalt ist.
Kalkülregeln dieser Gestalt werden uns in Abschnitt 3.7 im Zusammenhang mit der Reiterschen Ermangelungslogik in verallgemeinerter Form wieder begegnen.
Die AWA ist zwar einfach und scheint in einfachen Fällen genau den
gewünschten Effekt zu haben. Leider löst sie das Phänomen des
nichtmonotonen Schließens nicht in der gewünschten umfassenden Weise.
Zunächst erkennen wir, daß wegen der Unentscheidbarkeit der
Prädikatenlogik
die Anwendbarkeit der oben gezeigten zweiten Regel
unentscheidbar ist. Es ergibt sich also ein Problem im Hinblick auf ein
mögliches Berechnungsverfahren; jedoch stoßen wir bei allen Ansätzen
zur Nichtmonotonie auf Probleme von dieser Natur, durch die Grenzen der
Berechenbarkeit sichtbar werden; sie besagen uns, daß wir nur innerhalb
solcher Grenzen auf Erfolg hoffen können. Weiter ist die AWA von der Wahl
der Prädikatsbezeichnungen abhängig; benennt man zB. ein Prädikat
zu
um, so ergibt sich offensichtlich ein anderes
Verhalten der AWA. Darüber hinaus ergeben sich bei der AWA die durch die
folgenden beiden Beispiele illustrierten Konsistenzprobleme.
Angenommen, unsere Welt sei allein durch die Formel
beschrieben. Dann läßt sich hieraus klassisch weder
noch
folgern. Also besteht
aus den Literalen
. Die so entstehende Theorie ist nun offensichtlich
widersprüchlich, während die ursprüngliche Welt konsistent ist. Die AWA
kann also ausgehend von konsistenten Formelmengen zu inkonsistenten Theorien
führen. Ein Verfahren, das Widersprüche generiert, die vorher nicht
vorhanden waren, kann nicht als tauglich angesehen werden.
Auch in diesem Beispiel, das nur eine Variante des vorangegangenen Beispiels darstellt, führt die AWA zu einem Widerspruch.
![]()
Dann aber wird die Regel des Beispiels anwendbar und Liebt_Eiscreme(Larissa) also ableitbar, so daß der Widerspruch offensichtlich ist.
Man beachte in diesem Beispiel, das wir oft auch kurz als formulieren werden, die hier mit einem
Abnormalitätsprädikat
realisierte Technik, Regeln mit
Ausnahmen logisch korrekt darzustellen, die
wir in diesem und den
nächsten beiden Abschnitten immer einsetzen werden.
Natürlichsprachlich sind solche Regeln dadurch charakterisiert, daß sie
in der Form ``normalerweise lieben Kinder Eiscreme'' formuliert (oder
zumindest gedacht) werden. Semantisch läßt sich eine solche Regel wie in
Abbildung 3.2 dargestellt illustrieren.
Abbildung 3.2: Die Interpretation einer Regel mit Ausnahmen
Die meisten Elemente der Extension von , also der Kinder, liegen
in der
Extension von
, lieben also Eiscreme. Nur ein kleiner Teil der Kinder
ist abnormal
, auf den also die Regel nicht
zutrifft.
Nach den enttäuschenden Einsichten, die sich aus diesen beiden Beispielen ergeben, stellt sich die Frage, ob es vielleicht Teilklassen von Formeln gibt, bei denen sich durch die AWA keine derartigen Widersprüche einschleichen. Eine solche Teilklasse werden wir nun angeben. Dies erfordert einige Vorbereitungen, wobei wir den Modellbegriff der Prädikatenlogik entsprechend unserer generellen Verabredung in Abschnitt 1.6 als bekannt voraussetzen.
SeienIn den meisten Anwendungsfällen lassen sich prädikatenlogische Formeln ohne wesentliche Einschränkung der Allgemeinheit auf Klauselform bringen. Klauselmengen haben die besonders angenehme Eigenschaft, daß eine Klauselmenge genau dann ein Modell hat, wenn sie ein Herbrandmodell hat. Ein Herbrandmodell ist dabei bekanntlich über den Zeichen des Alphabets der zugrundeliegenden Sprache gebildet. Es wird als eine Menge von Grundatomformeln repräsentiert. Dadurch reduziert sich die in der voranstehenden Definition eingeführte Untermodellbeziehung auf die Teilmengenbeziehung zwischen zwei Grundatomformelmengen. Für die nachfolgende Aussage 3.2 müssen wir uns auf diesen Fall von Herbrandmodellen beschränken (da er im allgemeinen nicht gilt).eine Formelmenge der Prädikatenlogik erster Stufe und
sowie
Modelle von
. Dann ist
ein Untermodell von
bezüglich des Prädikats
, geschrieben
, genau dann, wenn die folgenden Bedingungen erfüllt sind:
- D = D',
,
und
stimmen im übrigen überein.
heißt ein Untermodell von
bezüglich einer Menge
von im zugrundegelegten Alphabet enthaltenen Prädikatszeichen,
, wenn die Bedingung (2) für alle
gilt.
Bestehtaus allen im Alphabet enthaltenen Prädikatszeichen oder ist die Prädikatsmenge eindeutig aus dem Kontext klar, so schreiben wir auch kurz
.
Ein Modelleiner Formelmenge
wird als minimal bezeichnet genau dann, wenn für alle Modelle
von
gilt
![]()
Ein Modell
einer Formelmenge
wird als das kleinste Modell von
bezeichnet genau dann, wenn für alle Modelle
von
mit
gilt
![]()
Die letzten beiden Begriffe sind für Teilmengen der Prädikatszeichen entsprechend definiert.
Betrachtet man eine Formelmenge unter der AWA, so eliminiert man damit
eine große Anzahl von Modellen -- nämlich all jene Modelle, die
Grundatome aus der Menge
der negierten nichtfolgerbaren
Grundatome erfüllen. Tatsächlich besitzt eine konsistente Formelmenge
unter der AWA dann nur noch ein einziges Herbrandmodell. Wenn die Formelmenge
ein kleinstes Herbrandmodell besitzt, so kann man allgemein beweisen,
daß dieses auch das einzige Herbrandmodell unter der AWA ist, was
wir im folgenden Satz festhalten.
IstEine syntaktische Variante dieses Satzes ist die folgende Aussage [GN89].eine konsistente Formelmenge, so ist
konsistent genau dann, wenn
ein kleinstes Herbrandmodell hat.
IstHornformeln zeichnen sich genau durch die Eigenschaft aus, immer ein kleinstes Herbrandmodell zu haben [Llo84]. Somit ergibt sich aus dem vorletzten Satz das erstmals in [Rei77] erzielte Ergebnis.eine konsistente Formelmenge, so ist
konsistent genau dann, wenn es für jede Disjunktion
von Grundatomen
mit
mindestens ein
mit
gibt,
.
IstIn der Tat sind die beiden Beispiele oben, die zu Widersprüchen geführt haben, eben keine Hornformeln, ebensowenig wie sie die Aussage des vorangegangenen Satzes erfüllen. Auch haben sie kein kleinstes Modell. So hat zB.eine konsistente Menge von Hornformeln, so ist
konsistent.
Wir stehen natürlich nun immer noch vor der Frage, wie Nicht-Hornformeln
hinsichtlich der AWA zu behandeln sind. Eine Möglichkeit, auch in diesem
Fall Inkonsistenzen zu vermeiden, besteht in einer Anwendung der AWA nur auf
eine Teilmenge der auftretenden Prädikatszeichen, so daß
eine
Theorie
resultiert.
Denken wir zur Illustration hierfür nochmal an das oben geschilderte Beispiel mit der Eiscreme. Wir haben ja nun gesehen, daß die AWA die Minimierung der Interpretationsbereiche (im mengentheoretischen Sinne) der auftretenden Prädikate zum Ziel hat. Das Beispiel illustriert aber, daß es einem oft nur um die Minimierung (in diesem Sinne) von einigen der Prädikate geht. Hier ist es das Prädikat ``Abnormal'', das es zu minimieren gilt, weil wir grundsätzlich zunächst von normalen Dingen ausgehen und Abnormalität nur annehmen, wenn sie zwingend erforderlich ist, also in diesem Sinne Abnormalität minimieren. Beim Prädikat ``Liebt_Eiscreme'' hingegen gibt es (abgesehen von gesundheitlichen Bedenken) keine Veranlassung zu einer Minimierung. In der Tat ergibt sich in diesem Beispiel kein Widerspruch mehr, wenn die AWA nur auf Grundformeln mit dem Prädikat ``Abnormal'' angewendet wird.
Dieses Beispiel mag die Idee nahelegen, man müsse nur eine Untermenge der auftretenden Prädikate derart bestimmen und minimieren, daß dann die Formel ohne diese minimierten Atome Horn wird. Leider gibt es aber auch hierfür Gegenbeispiele [Sch90].
Wir haben bislang noch nicht darüber gesprochen, wie bei gegebener
Wissensbank die Berücksichtigung der AWA tatsächlich realisiert
wird. In [Rei77] hat Reiter ein Verfahren angegeben, das im Falle einer
quantorenfreien Anfrage an die Wissensbank
nur die in
selbst
enthaltenen Formeln berücksichtigt (vorausgesetzt
ist konsistent). Es muß also die Menge der negierten nichtfolgerbaren
Grundatomformeln
nicht explizit aufgezählt werden.
Besteht die Wissensbank nur aus Hornformeln, dann haben negative Klauseln (wie
die Elemente von
) keinen Einfluß auf den
Ableitungsprozess unter der Annahme der Weltabgeschlossenheit.
Die diskutierten Probleme des ursprünglichen Formalismus zur Modellierung der Annahme der Weltabgeschlossenheit haben zu etlichen Weiterentwicklungen geführt. Einer der ersten Ansätze wurde von Minker in [Min82] vorgestellt. Sein Ansatz wird als generalisierte Annahme der Weltabgeschlossenheit bezeichnet. Dieser Ansatz wurde in Form der vorsichtigen Annahme der Weltabgeschlossenheit von Gelfond und Przymusinska in [GP86] verallgemeinert. Die bisher allgemeinste Form der AWA stellt die von Gelfond, Przymusinska und Przymusinski in [GPP89] entwickelte erweiterte Annahme der Weltabgeschlossenheit dar. Insbesondere subsumiert diese die drei zuvor entwickelten Ansätze. In [Kat90] werden Modifikationen der AWA betrachtet, bei denen unter den Prädikatszeichen eine Präzedenzordnung angenommen wird. Dies führt zu einer partiellen, einer hierarchischen und einer schrittweisen AWA .
Wir erwähnen abschließend, daß die Annahme der Namenseindeutigkeit (engl. unique name assumption) als derjenige Spezialfall der AWA angesehen werden kann, bei der das Gleichheitsprädikat minimiert wird [Lif85a]. In den folgenden Abschnitten wird sich nun zeigen, daß die hier besprochenen Ideen und Konzepte in variierter, meist komplizierterer Form immer wieder auftauchen. Es ist besonders auch aus diesem Grunde, daß wir der AWA einen solch breiten Raum gewidmet haben.
Christoph Quix, Thomas List, René Soiron