Auf Datenbanken und deren Verallgemeinerung, den deduktiven Wissensbasen, sind wir in diesem Buch schon mehrfach zu sprechen gekommen (zB. in den Abschnitten 2.11.1 und 3.2). Wegen ihrer herausragenden Bedeutung wollen wir in diesem Abschnitt zwei Ansätze zur Behandlung metasprachlicher Anfragen an deduktive Wissensbasen vorstellen, die als Anwendung der in den vorangegangenen Teilen dieses Abschnittes diskutierten Methoden der Formalisierung der Metaebene angesehen werden können. Inbesondere beschäftigen wir uns dabei mit der Frage, wie man Wissen über das Vorhandensein von Information in einer Wissensbasis formalisieren kann. Wir beginnen mit einer Motivation anhand von Beispielen.
Herkömmliche relationale Datenbanken bestehen aus logischer Sicht aus einer Menge von Grundatomformeln. Eine Anfrage an eine solche Datenbank ist dann ein Test, ob eine gegebene Grundatomformel in der Datenbank vorhanden ist oder nicht. Dagegen wollen wir unter einer deduktiven Wissensbasis eine Menge von Sätzen (also nicht nur Grundatomen) der Prädikatenlogik erster Stufe verstehen. In diesem Sinne handelt es sich also um eine klassische Weltbeschreibung, wie wir sie bisher in diesem Buch auch schon verwendet haben. Im Unterschied zu einer herkömmlichen Datenbank enthält eine deduktive Wissensbasis also auch generisches Wissen, etwa in Form von Regeln, sowie einen Inferenzmechanismus, mit dessen Hilfe man weiteres Wissen ableiten kann. Andererseits wird im Unterschied zu allgemeinen Theorien der Prädikatenlogik erster Stufe die einer Wissensbasis zugrunde liegende Sprache oft eingeschränkt. Sie enthält, wie wir weiter unten noch sehen werden, oft keine Funktionssymbole und nur endlich viele Konstantensymbole. Eine Anfrage an eine deduktive Wissensbasis ist dann ein Test, ob eine gegebene Formel aus der Wissensbasis ableitbar ist oder nicht. Insbesondere werden wir weiter unten einen Ansatz vorstellen, in dem Anfragen mit epistemischen Modaloperatoren versehen werden, um auch Metaanfragen formulieren zu können (vgl. Abschnitt 4.2.1 ).
Betrachten wir zunächst das folgende Beispiel von Studenten in
Vorlesungen. Jeder Student, der eine Vorlesung besucht, ist soweit wie
möglich in der Wissensbasis mittels des zweistelligen Prädikats
Hört erfaßt. Betrachten wir dazu die folgende Wissensbasis 
:
Die ersten beiden Fakten dieser Wissensbasis entsprechen einer herkömmlichen Datenbank, da sie jeweils Grundatomformeln sind. Die drei letzten Einträge der Wissensbasis übersteigen allerdings die Ausdrucksmöglichkeiten herkömmlicher Datenbanken. Der dritte und vierte Eintrag stellen unbestimmtes Wissen dar. Die Disjunktion sagt uns, daß Stefan entweder die Vorlesung zur Informatik oder zur Psychologie oder sogar beide besucht. Es liegt also keine bestimmte Information über die von Stefan besuchte Vorlesung vor. Der vierte Eintrag wird im Datenbankjargon als ``Nullwert'' bezeichnet. Er besagt, daß die Vorlesung Psychologie zwar Zuhörer hat, diese aber nicht erfaßt worden sind. Der letzte Eintrag unserer Wissensbasis ist eine Regel, die aussagt, daß jeder Student, der eine Vorlesung zur Informatik besucht, auch eine Vorlesung zur Mathematik besucht, aber nicht notwendigerweise auch umgekehrt.
Wir können nun diverse Anfragen an diese Wissensbasis stellen.
Eine Anfrage wird dabei mit Ja beantwortet, falls sie aus der Wissensbasis
herleitbar ist, mit Nein, falls ihr Negat aus herleitbar ist.
Ansonsten wird mit Unbekannt geantwortet.
Die Anfrage 4, ob Eva die Vorlesung zur Mathematik besucht, ist nicht direkt aus der Wissensbasis abrufbar. Um diese Anfrage zu beantworten, muß der der Wissensbasis zugrundeliegende Inferenzmechanismus verwendet werden. Konkret wird dabei aus dem zweiten Fakt der Wissensbasis Hört( inf,eva) sowie der Regel
mittels modus ponens geschlossen, daß Eva auch die Vorlesung zur Mathematik besucht, nämlich Hört(mat,eva).
Die letzten drei Anfragen zeigen, wie unbestimmtes Wissen in deduktiven Wissensbasen behandelt wird. Es ist weder bekannt, daß Stefan die Informatik-Vorlesung, noch daß er die Psychologie-Vorlesung hört. Allerdings kann man ableiten, daß er zumindest eine von beiden Vorlesungen besucht (Anfrage 7 -- natürlicherweise würde man jedoch eher mit Vielleicht antworten).
Üblicherweise werden deduktive Wissensbasen allerdings gegenüber allgemeinen Theorien der Prädikatenlogik erster Stufe noch etwas eingeschränkt. Zunächst unterscheidet sich eine deduktive Wissensbasis von einer allgemeinen Theorie durch eine eingeschränkte Sprache, die insbesondere keine Funktionssymbole und oft nur endlich viele Konstantensymbole enthält. Auch wir wollen uns im folgenden dieser Einschränkung anschließen und nur eine Sprache mit endlich vielen Konstantensymbolen betrachten.
Zudem werden für deduktive Wissensbasen häufig, wie etwa in
[GMN84], die Namenseindeutigkeit, die
Bereichsabgeschlossenheit sowie
die Annahme der Weltabgeschlossenheit gefordert, auf die wir im folgenden zu
sprechen kommen. Die Annahme der Weltabgeschlossenheit haben wir bereits in
Abschnitt 3.2 kennengelernt und dort anhand von Datenbanken erläutert:
Ist eine Grundatomformel nicht in einer Datenbank enthalten, so wird unter
Annahme der Weltabgeschlossenheit ihre Negation angenommen. Dementsprechend
würden wir in unserem Beispiel unter Annahme der Weltabgeschlossenheit als
Antwort auf unsere Anfrage 2, Hört(inf,
antje), ein Nein erhalten. Dagegen würde die Negation der Anfrage 2,
nämlich
unter der Annahme der Weltabgeschlossenheit mit Ja beantwortet werden.
Die Namenseindeutigkeit und die Bereichsabgeschlossenheit werden bei Wissensbasen axiomatisch beschrieben. Dazu muß eine Wissensbasis mit einem geeigneten Axiom versehen werden.
Das Axiom der Namenseindeutigkeit fordert, daß die Konstantensymbole unserer
Sprache paarweise verschiedene Objekte (oder Universumselemente) bezeichnen.
Sind
die in unserer Sprache auftretenden Konstantensymbole, so ist das Axiom der
Namenseindeutigkeit durch die folgende Formel gegeben:
Das Axiom der Bereichsabgeschlossenheit fordert, daß die Konstantensymbole
unserer Sprache sämtliche betrachteten Objekte (oder Universumselemente)
bezeichnen. Sind
die in unser Sprache auftretenden Konstantensymbole, so ist das Axiom der
Bereichsabgeschlossenheit durch die folgende Formel gegeben:
Dem interessierten Leser wird an dieser Stelle die unterschiedliche Realisierung der Namenseindeutigkeit und der Bereichsabgeschlossenheit auf der einen Seite, und der Realisierung der Weltabgeschlossenheit in Abschnitt 3.2 auf der anderen Seite aufgefallen sein. In der Tat handelt es sich bei der Annahme der Weltabgeschlossenheit um eine Metaannahme, während die Namenseindeutigkeit und die Bereichsabgeschlossenheit axiomatisch und daher objektsprachlich beschrieben worden sind.
Wir wollen diesen Unterschied kurz anhand der Forderung nach Namenseindeutigkeit erläutern. In Abschnitt 3.2 haben wir die Namenseindeutigkeit als Metaannahme kennengelernt. Sie kann nämlich als ein Spezialfall der Annahme der Weltabgeschlossenheit angesehen werden, indem man unter ihr von der Ungleichheit zweier Terme ausgeht, solange nicht das Gegenteil bewiesen werden kann. Realisiert man dagegen die Namenseindeutigkeit objektsprachlich in Form des oben angegebenen Axioms, so wird explizit gefordert, daß alle in einer Wissensbasis auftretenden Terme paarweise verschieden sind.
Wir wollen uns im folgenden auf die Forderungen nach Namenseindeutigkeit und Bereichsabgeschlossenheit beschränken und diese als Axiome zu einer Wissensbasis hinzufügen.
In unserem Beispiel müssen wir also zur Formulierung der Namenseindeutigkeit
und der Bereichsabgeschlossenheit die beiden folgenden Axiome zur Wissensbasis
hinzufügen.
Wir wollen die so erhaltene Wissensbasis als 
bezeichnen.
Nun wenden wir uns Beispielen von Anfragen zu, die nicht nur nach dem Inhalt
einer Wissensbasis, sondern auch nach dem Kenntnisstand der
Wissensbasisfragen. Hierzu wird die Anfragesprache um einen epistemischen
Modaloperator 
erweitert (vgl. Abschnitt 4.2.1 ). Eine Formel
der Gestalt
wird dann als
``die Wissensbasis weiß 
''
interpretiert. Der Modaloperator erlaubt es daher, Aussagen
über das Wissen, dh. metasprachliche Aussagen, auf der Objektebene zu
formulieren.
Anstelle einer Aussage
``die Wissensbasis weiß, daß gilt'',
können wir nun sagen, daß
gilt, bzw.
``die Wissensbasis weiß ''
gilt.
Dementsprechend werden Aussagen wie
``die Wissensbasis weiß nicht, daß gilt''
zu objektsprachlichen Aussagen der Form
Die Gültigkeit einer Metaaussage wird damit auf die in der Logik übliche
Gültigkeit einer objektsprachlichen Aussage zurückgeführt.
Wollen wir nun an unsere obige Wissensbasis die Anfrage stellen, ob man weiß,
daß Hört(mat,antje) wahr ist, dh. ob wir
wissen, daß Antje die Mathematikvorlesung hört, so können wir dies
mit Hilfe des epistemischen Modaloperators in der Form
als Anfrage formulieren. Als Antwort müssen wir dann ein klares Ja erhalten, da wir wissen, daß Antje die Mathematikvorlesung besucht, wie wir bereits in der Anfrage 1 gesehen haben. Allerdings wissen wir nicht, ob Antje auch die Informatikvorlesung besucht, was dazu führt, daß wir eine Anfrage der Gestalt
verneinen müssen, aber die Anfrage
bejahen können. In analoger Weise werden wir auch die Anfragen
und
mit Ja beantworten.
Nicht ganz so einfach ist die Fragestellung, wie wir Metaaussagen über unbestimmtes Wissen behandeln sollen. Dazu konzentrieren wir uns im folgenden auf Anfragen zum unbestimmten Wissen in unserer obigen Wissensbasis.
So können wir dann mit Hilfe des epistemischen Modaloperator
die folgenden Anfragen an unsere Wissensbasis stellen:
noch
aus unserer Wissensbasis herleitbar ist, wissen wir weder, daß Stefan die
Informatikvorlesung besucht, noch das Gegenteil hiervon. Dementsprechend werden die
Anfragen 8,
und 9,
verneint. Dagegen wird die Anfrage 10, ob wir nicht wissen,
daß Stefan die Informatikvorlesung hört, bejaht. Obwohl sich die Anfrage 10
von der Anfrage 9 syntaktisch nur durch die Umstellung des
Negationszeichens 
und des Modaloperators
unterscheidet, erhalten wir eine entgegengesetzte Antwort.
Ein ähnliches Phänomen ist bei den Anfragen 11 und 12 sowie 13 und 14 zu
beobachten. Hier wurde jeweils der Modaloperator mit dem
Existenzquantor der Variablen 
vertauscht. In der Anfrage 11 fragen wir
an, ob man weiß, daß Stefan eine Vorlesung hört. Dies wird auch bejaht;
denn wir wissen, daß er die Psychologie- oder Informatikvorlesung besucht.
Im Gegensatz zur Anfrage 8 haben wir nun also ein Ja erhalten, da wir uns bei
unserer Anfrage nicht auf eine bestimmte Vorlesung festgelegt haben.
Demgegenüber legen wir uns in der Anfrage 12 sozusagen zunächst auf eine
Vorlesung fest, bevor wir unser Wissen reflektieren. Wir fragen, ob es eine
Vorlesung gibt, von der wir wissen, daß Stefan sie besucht. Da wir dies von
keiner bestimmten Vorlesung wissen, müssen wir dementsprechend mit Nein
antworten. Die Behandlung der Anfragen 13 und 14 geschieht analog.
Auch die letzten beiden Anfragen sind interessant zu vergleichen. Müssen wir
die vorletzte Anfrage, ob es jemanden gibt, der Informatik hört und nicht
Psychologie, noch verneinen, so können wir die letzte Anfrage, ob es jemanden
gibt, der Informatik hört und von dem wir nicht wissen, ob er Psychologie
hört, bejahen und Eva nennen. Müssen wir also zur Beantwortung der
Anfrage 15 noch beweisen, daß Eva nicht die Psychologievorlesung hört, so
genügt es, in der Anfrage 16 festzustellen, daß wir nicht wissen, daß Eva
die Psychologievorlesung besucht. Diese Vorgehensweise ist sehr stark mit dem
in Abschnitt 3.4 vorgestellten Prinzip der Negation-als-Mißerfolg
verwandt. Insbesondere wird nun klar, daß der betrachtete Ansatz nichtmonoton
ist. Erfahren wir etwa, daß Eva die Psychologievorlesung besucht und fügen
dazu das Faktum
zu unserer Wissensbasis, so können wir nun die Anfrage 16 nicht mehr mit Ja
beantworten.
Bisher haben wir lediglich an die Intuition des Lesers appelliert. Wir wollen nun das bisher Beschriebene präzisieren und formal definieren, wann eine Anfrage aus einer gegebenen Wissensbasis folgt. Wir beginnen mit einem Ansatz zur Behandlung von Metaaussagen und Metawissen, der von Levesque in [Lev81, Lev84] vorgeschlagen und von Reiter in [Rei90b, Rei90a] weiterentwickelt wurde. In diesem Ansatz werden Wissensbasen mit Hilfe einer Sprache der Prädikatenlogik erster Stufe beschrieben, während in Anfragen ein modaler Operator zugelassen ist.
Zunächst erinnern wir nochmals an die Semantik der Prädikatenlogik (vgl. Abschnitt 2.3). Eine Struktur zusammen mit einer Abbildung der Zeichen einer logischen Sprache auf die Elemente der Struktur heißt dort eine Interpretation. Wenn die Interpretation eine Formel wahr macht, dann heißt sie ein Modell der Formel. Weiter folgt eine Aussage aus einer Formelmenge, wenn sie in allen Modellen der Formelmenge gilt. Daher müssen wir für die nun anvisierte epistemische Logik zunächst ebenfalls erklären, wie sich der Wahrheitswert einer Aussage in einem Modell bestimmt.
Der Einfachheit halber wollen wir uns dabei, wie schon in
Abschnitt 3.2 geschehen, auf sogenannte
Herbrandinterpretationen
beschränken. Wie dort auf Seite 
beschrieben, wird eine
Herbrandinterpretation über den Zeichen des Alphabets der zugrundeliegenden
Sprache gebildet und durch eine Menge von Grundatomformeln repräsentiert.
Die Menge der mit den Zeichen des Alphabets bildbaren Terme wird dabei als
Herbranduniversum bezeichnet. Eine Herbrandinterpretation wird dann
ein Herbrandmodell für eine Formel genannt, wenn sie der Formel den
Wahrheitswert wahr zuordnet.
Die Beschränkung auf Herbrandinterpretationen macht in unserem Fall auch Sinn, da infolge der mit der Namenseindeutigkeit und der Bereichsabgeschlossenheit gemachten Einschränkungen sowieso nur Modelle auftreten können, die isomorph zu Herbrandmodellen sind. Insbesondere wird durch das Bereichsabgeschlossenheitsaxiom erreicht, daß das Universum eines jeden Modells von der Kardinalität des Herbranduniversums ist. Das Namenseindeutigkeitsaxiom verhindert dabei, daß verschiedenen Konstantensymbolen gleiche Universumselemente zugeordnet werden.
Ein Herbrandmodell unserer obigen (mit den Axiomen der Namenseindeutigkeit und
Bereichsabgeschlossenheit versehenen) Wissensbasis enthält daher
unter anderem die Grundatomformeln
Hört(mat,antje),
Hört(inf,eva),
Hört(mat,eva)
sowie
, 
, 
, 
, 
, 
als einzige Grundatomformeln für das Gleichheitsprädikat 
.
Der Wahrheitswert eines Satzes wird nun bezüglich einer
Interpretation
und einer Menge 
von
Interpretationen definiert, während der Wahrheitswert einer Formel der
Prädikatenlogik erster Stufe bezüglich einer einzigen Interpretation
definiert ist (vgl. Abschnitt 2.3). Das den Interpretationen
gemeinsame Universum wollen wir mit 
bezeichnen.
eine Grundatomformel, so ist wahr in und
genau dann, wenn 
.
ist wahr in und genau dann, wenn
nicht in und wahr ist.
ist wahr in und genau dann, wenn
und 
in und wahr sind.
ist wahr in und genau dann,
wenn für jedes 
, 
in und wahr ist.
ist wahr in und genau dann, wenn
für jedes 
, in 
und wahr ist.
gebildete Formel, nur von der Interpretation und nicht
von der Menge der Interpretationen bestimmt wird. Insbesondere
genügen die ersten vier Bedingungen, um den Wahrheitswert einer Formel der
Prädikatenlogik erster Stufe zu beschreiben. Die fünfte Bedingung beschreibt
den Wahrheitwert von Formeln, die mit dem Modaloperator versehen
sind. Ihr Wahrheitwert wird ausschließlich von den Interpretationen in der
Menge bestimmt.
Ein Paar 
von Interpretationen ist nun ein
Modell
einer Formel genau dann, wenn in und wahr
ist.
Eine so gegebene Struktur kann auch als eine modallogische Interpretation im
Sinne von Kripke (vgl. mit Tabelle 2.3 in
Abschnitt 2.11.7) verstanden werden. Man kann dann zeigen (siehe
Aufgabe 6.3.2 in Abschnitt 6.3), daß ein solches Paar
von Interpretationen eine Interpretation der schwachen
Variante der Modallogik S5 ist.
In der Prädikatenlogik wird der Folgerungsbegriff üblicherweise wie folgt
definiert. Eine Aussage folgt aus einer Formelmenge genau
dann, wenn in allen Modellen von wahr ist. Wie schon in der
Zirkumskription oder der Ermangelungslogik (vgl. Abschnitt 3.5
und 3.7) geschehen, wird auch hier der Folgerungsbegriff auf
bestimmte Modelle in der folgenden Weise eingeschränkt. Da wir nur
Wissensbasen der Prädikatenlogik erster Stufe betrachten, definieren wir den
Folgerungsbegriff zunächst nur zwischen Mengen von Formeln der
Prädikatenlogik erster Stufe und Formeln, die zusätzlich den Modaloperator
enthalten dürfen. Sei 
nun die Menge aller Modelle
einer Formelmenge (dh. ist die Menge aller
Interpretationen, die jede prädikatenlogische Formel in wahr machen),
so folge aus genau dann, wenn für alle 
,
in und im Sinne der vorherigen Definition wahr
ist. Damit wird also der Folgerungsbegriff auf Modelle der Form
eingeschränkt.
Bevor wir die hinter dieser Konstruktion liegenden Idee erläutern, wollen wir zunächst formal definieren, was eine Antwort auf eine Anfrage an eine Wissensbasis ist.
SeiMit der soeben betrachteten Beschränkung auf Modelle der Formbesitzt.
Ein Tupel
von Termen ist dann eine Antwort auf
,
in
Besitzt
Ja wenn für alle gilt.
Nein wenn für alle in
gilt.
Unbekannt ansonsten.
mit beschränken wir uns auf maximale
Mengen von Interpretationen, und zwar aus dem Blickwinkel einer jeden solchen
Interpretation . Dies hat den folgenden Grund. Die Menge der
Interpretationen in einem Modell dient zur
Charakterisierung von Formeln der Gestalt 
und damit zur
Beschreibung von Metaaussagen, dh. Aussagen über die betrachtete
Wissensbasis. Je größer die Menge der Interpretationen ist, desto
weniger Aussagen werden von ihr erfüllt. Man beschränkt sich damit auf den
absolut minimalen Wissenstand.
Ist eine Formel der Prädikatenlogik, so ist aufgrund der Definition
eine Aussage der Gestalt genau dann aus einer Wissensbasis
folgerbar, wenn ``klassisch'' aus folgt, dh. daß in
allen (prädikatenlogischen) Interpretationen von gilt. Ist dies nicht
der Fall, dh. gilt nicht in allen (prädikatenlogischen)
Interpretationen von , so können wir 
aus
folgern. Formal gelten daher die folgenden Beziehungen.
Ist
eine Menge von Formeln der Prädikatenlogik erster Stufe, die das
Namenseindeutigkeits- und Bereichsabgeschlossenheitsaxiom enthalten, und
eine Formel der Prädikatenlogik erster Stufe, so gilt:
Dabei bezeichnet 
wie immer die Folgerungsbeziehung der Prädikatenlogik erster Stufe.
Der obige Zusammenhang zeigt, daß sich der Modaloperator bezüglich
der Folgerungsbeziehung 
wie ein Beweisbarkeitsprädikat
verhält.
Wir wollen nun auf eine wichtige Anwendung des im Vorangegangenen besprochenen Ansatzes von Levesque und Reiter zu sprechen kommen. Sowohl in herkömmlichen Datenbanken als auch in deduktiven Wissensbasen spielt das Konzept von Integritätsbedingungen eine wichtige Rolle. Da sowohl Datenbanken als auch Wissensbasen häufig verändert werden, muß sichergestellt werden, daß sich jede nach einer Modifikation erhaltene Wissensbasis in einem ``legalen'' Zustand befindet. Dies wird mit Hilfe von Integritätsbedingungen gewährleistet.
Beispielsweise muß jeder Student eine Matrikelnummer haben. Eine solche Forderung kann man mit Hilfe eines einstelligen Prädikats Student und eines zweistelligen Prädikats Mat# wie folgt formalisieren:
In der Literatur finden sich allerdings zwei unterschiedliche
Behandlungsweisen solcher Integritätsbedingungen. Die erste derartige Definition
stammt von Kowalski [Kow78]. Ist eine Wissensbasis und 
eine Integritätsbedingung, dann sagt man,
erfülle genau dann, wenn 
konsistent ist.
und
wie oben gegeben, dann sagt man,
erfülle genau dann, wenn 
.
Betrachten wir dazu die obige Integritätsbedingung über die
Matrikelnummern von Studenten, die wir mit 
abkürzen wollen. Nehmen wir
an, die Wissensbasis bestehe aus dem Fakt student(stefan), dh.
Da keine Aussage über Stefans Matrikelnummer enthält, müßte
die Integritätsbedingung verletzt sein. 
ist jedoch
konsistent, so daß die Integritätsbedingung in der Version von Kowalski
[Kow78] erfüllt ist. Also scheint diese Formulierung nicht adäquat zu
sein.
Betrachten wir nun eine leere Wissensbasis
im Zusammenhang mit der Integritätsbedingung . In diesem Fall
sollte trivialerweise erfüllt sein. Es gilt jedoch 
, so daß auch die Formulierung von Reiter in [Rei83] sich als
nicht adäquat erweist.
Wie man leicht sieht, stellen Integritätsbedingungen Aussagen über
den Inhalt eine Wissensbasis dar. Sie sind also Metaaussagen. Angesichts des
von uns zuvor betrachteten Ansatzes liegt es daher nahe, die Erfüllbarkeit
von Integritätsbedingungen auf die Beantwortung metasprachlicher Anfragen an
eine Wissensbasis abzubilden. Insbesondere gibt uns der Modaloperator ein weiteres Ausdrucksmittel zur Formulierung von
Integritätsbedingungen an die Hand.
Eine sehr natürliche Lesart unserer Integritätsbedingung über die Matrikelnummern von Studenten ist die folgende: Jeder der Wissensbasis bekannte Student muß eine der Wissensbasis bekannte Matrikelnummer haben. Formal kann dies durch die folgende Formel ausgedrückt werden:
Stellen wir nun diese Formel als Anfrage an die Wissensbasis
so erhalten wir nach der weiter oben gegebenen Definition ein Nein als
Antwort. Da student(stefan) zu den Fakten unserer Wissensbasis
zählt, läßt sich
ableiten. Damit ist die Prämisse unserer Integritätsbedingung erfüllt, nicht
aber deren Konklusion, ergo ist die Integritätsbedingung nicht erfüllt.
Stellen wir nun dieselbe Anfrage an die leere Wissensbasis, so erhalten wir
ein Ja als Antwort. Die Wissensbasis weiß von keinem Studenten. Die Prämisse der
Integritätsbedingung ist daher nicht erfüllbar. Ergo ist unsere
Integritätsbedingung erfüllt.
In beiden Fällen erhalten wir also die erwarteten Resultate.
Die zuletzt gegebene Formulierung der Integritätsbedingung zu unserem
Beispiel ist allerdings nicht die einzig mögliche. Wir können etwa auch die
folgende schwächere Formulierung wählen: Jeder der Wissensbasis bekannte
Student muß eine Matrikelnummer haben, ohne daß diese der Wissensbasis
explizit bekannt ist. Formal kann dies durch eine Umstellung des
Negationszeichens 
und des Modaloperators erreicht werden:
Der Leser möge sich davon überzeugen, daß diese Version immer noch das Gewünschte leistet. Formal läßt sich nun die Erfüllbarkeit von Integritätsbedingungen also wie folgt fassen.
Sei
.
Wir wollen nun eine Erweiterung des Ansatzes von Levesque und Reiter vorstellen. Bisher haben wir nur Wissensbasen betrachtet, die aus Formeln der Prädikatenlogik erster Stufe bestanden. In [Lif91, Lif92] wird diese Einschränkung fallen gelassen. Vielmehr darf eine Wissensbasis nun neben Formeln der Prädikatenlogik auch Formeln enthalten, die selbst wieder Modaloperatoren enthalten. Durch die Verwendung epistemischer oder metasprachlicher Operatoren in der Wissensbasis, können wir nun auch innerhalb der Wissensbasis zwischen objektsprachlichen und metasprachlichen Aussagen unterscheiden. Insbesondere kann eine Wissensbasis nun auch Aussagen über sich selbst enthalten.
Dazu werden nun zwei unabhängige Modaloperatoren 
und 
eingeführt. Der Modaloperator ist
eng verwandt mit dem von Levesque und Reiter verwendeten Modaloperator , allerdings wird eine etwas andere Intuition unterlegt,
nämlich die des ``Glaubens an eine Aussage''. Finden wir daher eine Aussage
der Gestalt
in einer Wissensbasis, so können wir sie auch als `` wird geglaubt''
oder `` zählt zu den Überzeugungen der Wissensbasis'' interpretieren.
Dadurch vermag die Wissensbasis zwischen wahren Aussagen, in Form von Sätzen
der Prädikatenlogik erster Stufe, und geglaubten Aussagen, die mit dem
Modaloperator versehen sind, zu unterscheiden.
Der neue Modaloperator dient der Formalisierung des schon in
Abschnitt 3.4 vorgestellten Prinzips der Negation-als-Mißerfolg,
während die klassische Negation bezeichnet.
Dementsprechend wird dann eine Aussage der Form
als `` ist nicht beweisbar'' oder `` ist konsistent''
interpretiert.
Insbesondere können wir nun auch Ermangelungswissen mit Hilfe des
Modaloperators in einer Wissensbasis darstellen. Betrachten
wir dazu wieder das Beispiel 3.2, das wir mit diesen neuen
Operatoren nun in der folgenden Weise
formulieren.
Die Aussage Kind(Larissa) stellt gesichertes Wissen über den
betrachteten Weltausschnitt dar. Sie ist deshalb als prädikatenlogische
Formel formalisiert. Die zweite Formel in stellt eine
Ermangelungsregel dar. Sie beschreibt die Vorstellung, daß ``wir glauben,
daß Kinder Eiscreme lieben, solange nichts Gegenteiliges bekannt ist''.
Können wir also für ein Objekt ableiten, daß es ein Kind ist, und
ist es für dieses Objekt konsistent anzunehmen, daß es Eiscreme liebt, so
glauben wir, daß es Eiscreme liebt.
Doch wie interpretieren wir nun solche Aussagen in formaler Weise? In
Abschnitt 3.7 haben wir die Semantik der Ermangelungslogik mittels
möglicher Welten beschrieben. Ein solches Modell besteht aus einer
Menge möglicher Welten, unter denen eine aktuelle Welt ausgezeichnet ist.
Auch die oben angegebene Semantik für Levesque und Reiters Ansatz kann als
eine mögliche Welten Semantik verstanden werden. Ein Modell
besteht in diesem Sinne aus einer aktuellen Welt und
einer Menge möglicher Welten .
Auch in Lifschitz' Ansatz werden Formeln mit Hilfe einer mögliche Welten
Semantik interpretiert. Eine Aussage der Prädikatenlogik
erster Stufe wie zB. Kind(Larissa) gilt dann, wie schon bei Levesque und Reiter, wenn sie in der
aktuellen Welt gilt, dh. wenn Larissa in der aktuellen Welt ein
Kind ist. Dagegen ist eine Aussage der Gestalt
genau dann wahr, wenn Larissa in allen möglichen Welten ein Kind ist.
Demgegenüber gilt eine Aussage
schon, wenn Larissa in einer möglichen Welt ein Kind ist.
Wir wollen nun wieder definieren, wann eine Anfrage aus einer erweiterten Wissensbasis in diesem Ansatz folgt. Dazu müssen wir zunächst wieder beschreiben, was wir uns unter einem Modell einer Wissensbasis vorstellen.
Formal wird der Wahrheitswert einer Formel bezüglich eines Tripels
definiert, wobei
wieder eine Herbrandinterpretation und
und
Mengen von Herbrandinterpretationen sind. Wie im Ansatz von Levesque und
Reiter dient die einzelne Interpretation zur Charakterisierung der
Wahrheit von Formeln der Prädikatenlogik erster Stufe. Die Mengen von
Interpretationen 
und 
bestimmen dagegen den
Wahrheitswert von Formeln, die mit einem bzw. einem versehen sind.
Der Wahrheitswert eines Satzes wird dann bezüglich einer
Interpretation und zweier Mengen von Interpretationen und
wie folgt definiert, wobei das den Interpretationen gemeinsame
Herbranduniversum wieder mit bezeichnet wird.
eine Grundatomformel, so ist wahr in genau dann, wenn .
ist wahr in genau dann, wenn
nicht in wahr ist.
ist wahr in genau dann, wenn
und in wahr sind.
ist wahr in genau dann,
wenn für jedes die Formel in wahr ist.
ist wahr in genau dann, wenn für
jedes 
die Formel in 
wahr ist.
ist wahr in genau dann, wenn für
ein 
, nicht in wahr ist.
Der Modellbegriff wird nun noch weiter eingeschränkt. Zunächst wird er nur
für solche Tripel definiert, für die
gilt. Dazu führt Lifschitz Strukturen der Form ein, die
syntaktisch den im Ansatz von Levesque und Reiter betrachteten Modellen
entsprechen, dh. ist eine Interpretation und 
ist eine Menge
von Interpretationen, die nun gleichzeitig für und
steht. Des weiteren ist man wie zuvor an einer Minimierung des Wissens
interessiert, was wieder durch eine Maximierung der betrachteten Menge von
Interpretationen erreicht wird. Eine Struktur wird
dabei als größer als eine Struktur 
bezeichnet, wenn
gilt. Die so erhaltenen maximalen Modellstrukturen entsprechen dann dem
Grundgedanken des ``minimalen Wissens'': Je größer die Menge der
Interpretationen ist, desto weniger Aussagen werden geglaubt.
Formal wird ein Modell in Lifschitz' Ansatz mit Hilfe eines Fixpunktoperators
beschrieben. Ist 
eine Formelmenge und eine Menge von
Interpretationen, so ist
die Menge aller maximalen Modellstrukturen 
, so daß in
wahr ist.
Eine Struktur ist dann ein Modell von
genau dann, wenn
Die sich zunächst aufdrängende Frage ist: Warum werden Modelle einer
Wissensbasis mittels einer Fixpunktdefinition beschrieben?
In Abschnitt 3 wurden Fixpunktdefinitionen zur Beschreibung von
Extensionen verschiedener nichtmonotoner Logiken verwendet. Der Grund hierfür
war eine zirkuläre Definition der Ableitbarkeit. Etwa ist die Ableitbarkeit
über Ermangelungsregeln (vgl. 3.7) durch die Nicht-Ableitbarkeit
und diese natürlich wieder durch die Ableitbarkeit selbst bedingt. Ein
solcher Zirkel wird mit Hilfe einer Fixpunktgleichung gelöst. Dieselbe
Zirkularität tritt nun auch in Wissensbasen auf, da diese durch die
Verwendung der Modaloperatoren und nun auch
Aussagen über sich selbst enthalten können. Insbesondere können wir auch
Ermangelungswissen in Wissensbasen modellieren, was zwangsläufig zu den aus
den Ermangelungslogiken bekannten Problemen führt.
Bevor wir allerdings einen Folgerungsbegriff definieren, wollen wir noch
einmal kurz den soeben eingeführten Modellbegriff illustrieren. Ist etwa
eine Menge von Formeln der Prädikatenlogik erster Stufe, so erhalten wir in
einem gewissen Sinne den klassischen Modellbegriff; denn die Modelle von
sind dann die Paare
wobei ein Modell von ist und die Menge aller
Interpretationen darstellt. Ist eine Formel der Prädikatenlogik erster
Stufe, so ist
ein Modell von 
genau dann, wenn
dh. die Menge aller Modelle von ist, und eine
beliebige Interpretation ist. Die beiden letzten Fälle zeigen, daß es keine
notwendige Beziehung zwischen dem Wahrheitswert einer Formel der
Prädikatenlogik erster Stufe und einer mit dem Modaloperator
versehenen Formel geben muß.
Im ersten Fall haben wir eine Formel der Prädikatenlogik betrachtet, deren
Wahrheitswerte nur von den jeweiligen aktuellen Welten in der Struktur
abhängig ist. Im
zweiten Fall haben wir eine mit dem Modaloperator versehene Formel
betrachtet, deren Wahrheitswert nur von der Menge der möglichen Welten abhängig ist.
Die Unabhängigkeit der Wahrheitswert von Formeln mit und ohne Modaloperator
ist auch daraus ersichtlich, daß bei der Definition des Modellbegriffes für
eine aktuelle Welt nie gefordert wird, daß sie zu den möglichen
Welten , bzw. oder , gehören muß.
Betrachten wir noch die Formel
,
wobei und 
Formeln der Prädikatenlogik sind. Wie wir weiter
unten noch sehen werden, sind Formeln dieser Gestalt von ganz besonderem
Interesse, da sie in einem engen Zusammenhang mit der logischen Programmierung
stehen.
Die Formel
gilt in einem Tripel
genau dann, wenn die folgende Bedingung gilt: Wenn es eine Interpretation
gibt, so daß
dann gilt
für alle
Dies ist äquivalent zu: Wenn
,
dann
Demnach können wir die Menge
wie folgt charakterisieren: Wenn
,
dann besteht
aus allen Strukturen der Form
wobei die Menge aller Interpretationen ist.
Ansonsten besteht
aus allen Strukturen der Form
Damit können wir die Modelle der Formel
wie folgt charakterisieren.
eine Tautologie, dann sind alle Modelle von der Form
wobei die Menge aller Interpretationen ist.
keine Tautologie, aber eine logische Konsequenz von , dann
gibt es keine Modelle.
keine logische Konsequenz von , dann sind alle Modelle von
der Form
wobei eine beliebige Interpretation ist.
und enthalten können, und Formeln, die mit Hilfe der Sprache der
Prädikatenlogik und dem Modaloperator gebildet worden sind.
Sieht man einmal von der unterschiedlichen Bezeichnungsweise der
Modaloperatoren und ab, so ist die Anfragesprache
in Lifschitz' Ansatz dieselbe wie in dem von Levesque und Reiter. Eine Formel
folgt nun aus einer Wissensbasis genau dann, wenn in allen
Modellen von gilt.
Bestehen und lediglich aus Formeln der Prädikatenlogik, so erhalten
wir den dort üblichen Folgerungsbegriff. Ist eine Formelmenge der
Prädikatenlogik und eine Formel, die den Modaloperator
enthalten darf, so stehen wir vor derselben Ausgangssituation wie im Ansatz
von Levesque und Reiter. Insbesondere ist die aus durch Ersetzung aller
Vorkommen des Modaloperators durch hervorgehende
Anfrage A' nach Levesque und Reiters Definition 4.2.4 aus
folgerbar genau dann, wenn
aus
nach Lifschitz'
Definition folgt. Dementsprechend übertragen sich alle Anfragen 1 bis 16 an
unsere obige Wissensbasis samt ihrer Beantwortung auf Lifschitz Ansatz.
Es ist im allgemeinen Fall interessant zu beobachten, daß, wenn eine Formel
aus folgt, nicht jedes Modell von auch ein Modell von ist.
Ist zum Beispiel
so ist
aus folgerbar, da 
in allen Modellen von wahr ist.
Jedoch ist kein Modell von ein Modell von , da keines
von ihnen maximal ist unter den Modellen, die erfüllen. Dieser
Sachverhalt hat zur Folge, daß wir sehr sorgfältig zwischen Formeln
unterscheiden müssen, die zu einer betrachteten Wissensbasis gehören, und
solchen, die an diese Wissensbasis als Anfrage gestellt werden.
Die Verwendung der Modaloperatoren und innerhalb
einer Wissensbasis führt zu einer enormen Ausdrucksstärke. Insbesondere
kann man zeigen, daß eine Reihe der in Kapitel 3 besprochenen
nichtmonotonen Logiken mit Hilfe der Modaloperatoren und modellierbar sind, was wir für einige dieser Logiken nun noch kurz
andeuten werden. Der Einfachheit halber betrachten wir dabei weiterhin
Wissensbasen, die die Axiome der Namenseindeutigkeit und
Bereichsabgeschlossenheit enthalten.
Als erstes wollen wir auf die schon weiter oben behandelte Annahme der
Weltabgeschlossenheit (vgl. Abschnitt 3.2) zurückkommen, die eine
häufig verwendete Metaannahme in Datenbanken darstellt: Ist eine
Grundatomformel nicht aus einer Wissensbasis ableitbar, so wird aufgrund
dieser Annahme ihre Negation hinzugenommen. Im Beispiel der in diesem
Abschnitt betrachteten Wissensbasis läßt sich diese Annahme
etwa für das Prädikat Hört durch Hinzufügen des Axioms
modellieren. Für jede Instantiierung der Variablen und 
leiten
wir so 
ab, wann immer wir 
nicht ableiten können. Ein damit sehr eng verwandtes Konzept ist das
Prinzip der Negation-als-Mißerfolg, das wir als nächstes
diskutieren
wollen.
Das Prinzip der Negation-als-Mißerfolg stellt eine (nichtklassische) Form der Negation dar, die zB. in der Programmiersprache PROLOG mit Hilfe des Metaprädikats not realisiert ist (vgl. Abschnitt 3.4). Ein logisches Programm besteht allgemein aus einer Menge von Implikationen der Gestalt
wobei
jedes 
eine Grundatomformel ist, 
. In [Lif92] wird nun
gezeigt, daß ein solches Programm einer Wissenbasis
entspricht, die nur aus Formeln der Gestalt
besteht. Haben wir etwa das Programm
so entspricht dies der Wissensbasis
Die Modelle von sind dann alle Strukturen der Form
wobei eine beliebige Interpretation darstellt.
Logische Programme können auch als ein Spezialfall der Ermangelungslogik (vgl. Abschnitt 3.7) angesehen werden. In der Ermangelungslogik werden zur Prädikatenlogik erster Stufe Ermangelungsregeln der Form
hinzugefügt,
wobei 
und Formeln der Prädikatenlogik erster
Stufe sind.
Wie in [GL91] gezeigt wurde, entspricht eine solche Ermangelungsregel
einer Regel eines generellen logischen Programms der Gestalt (4.1) genau
dann, wenn
und
wobei 
für das zu 
komplementäre Literal steht, dh.
und
Haben wir nun eine allgemeine Ermangelungsregel der Form (4.2), so entspricht diese dem (universellen Abschluß) der Formel
Betrachten wir nun eine Ermangelungstheorie 
, wobei 
eine Menge von geschlossenen Formeln ist, die mit den Axiomen der
Namenseindeutigkeit und Bereichsabgeschlossenheit versehen ist, und 
eine Menge von Ermangelungsregeln ist, so ergibt sich der
folgende allgemeine Zusammenhang.
Zu wie oben beschrieben sei 
eine Menge von
Formeln, die durch die oben beschriebene Transformation aus den
Ermangelungsregeln der Gestalt (4.2) in in Formeln der
Gestalt (4.3) hervorgegangen ist, dann ist eine prädikatenlogische
Formel in allen Extensionen der Ermangelungstheorie
genau dann, wenn
aus
folgt.
Des weiteren haben wir in Abschnitt 3.7 gezeigt, daß die
Zirkumskription (vgl. Abschnitt 3.5) unter gewissen Bedingungen als ein
Spezialfall der Ermangelungslogik angesehen werden kann. Grob gesprochen,
entspricht die (variable) Zirkumskription eines Prädikats 
in bei
Variation aller anderen Prädikate dem skeptischen Schließen mittels
Ermangelungstheorien, die die Gestalt
haben. Dabei ist eine Formel skeptisch ableitbar, wenn sie in allen
Extensionen der betrachteten Ermangelungstheorie gilt. Durch den soeben
skizzierten Zusammenhang zwischen Lifschitz' Ansatz und der Ermangelungslogik
reduziert sich die auf Seite definierte variable Zirkumskription
, wobei 
das Tupel aller in vorkommenden Prädikatszeichen
mit Ausnahme von bezeichnet, auf die folgende Formel in Lifschitz Ansatz.
was äquivalent ist zu
Für eine prädikatenlogische Formel gilt dann
genau dann, wenn aus (4.4) folgt.
Christoph Quix, Thomas List, René Soiron
