In diesem Kapitel haben wir eine Reihe verschiedener Ansätze zur
Formalisierung nichtmonotoner Schlußweisen kennengelernt. Die damit
verbundene Vielfalt ist für den Leser und Anwender eher verwirrend. Deshalb
wollen wir in diesem letzten Teil des Kapitels eine vergleichende und ordnende
Zusammenfassung der verschiedenen Ansätze versuchen. Alle diese Ansätze
verfolgen mehr oder weniger das gleiche Ziel, der Formalisierung eines
bestimmten Aspekts des alltäglichen Schließens. Statt einer minutiösen
Beschreibung aller Details der Welt beschränken wir uns in der natürlichen
Kommunikation auf die Beschreibung charakteristischer Merkmale in einer
Situation und ersparen uns die Erwähnung von solchen Einzelheiten, die in
gleicher Weise auch in anderen Situationen vorliegen. Dies erfordert von einem
derartigen Formalismus die Fähigkeit, bei gegebener Weltbeschreibung
über die klassisch ableitbaren Aussagen hinaus Wissen abzuleiten, das
``normalerweise'' in
gilt.
Die Ansätze zum nichtmonotonen Schließen sind durch verschiedene Ausprägungen des alltäglichen Schließens motiviert. Diese haben zu den drei folgenden Hauptformen des nichtmonotonen Schließens geführt: Weltabgeschlossenheitsschließen, Ermangelungsschließen und autoepistemisches Schließen.
Das
Weltabgeschlossenheitsschließen
bedient sich festgelegter Konventionen, um von dem gegebenen auch auf
die nichtgenannten Details schließen zu können. Die reinste Form des
Weltabgeschlossenheitsschließens findet sich bei der in Abschnitt 3.1
vorgestellten Annahme der Weltabgeschlossenheit (oder kurz AWA): jede nicht
explizit gegebene Grundaussage wird kategorisch als falsch angenommen. Dem
gegenüber wird bei der in Abschnitt 3.5 vorgestellten Zirkumskription
diese Annahme immer nur für bestimmte Grundaussagen getroffen.
Beim
Ermangelungsschließen
wird versucht, unvollständiges Wissen mit Hilfe von Standardannahmen zu
vervollständigen. Solche Standardannahmen resultieren aus Erfahrungswerten
und beschreiben das typische oder gewöhnliche Verhalten von Objekten.
Ermangelungsschlüsse sind daher Schlüsse, die in Ermangelung von Information
gezogen werden. Die übliche Lesart einer Ermangelungsregel ist dabei: ``
A's sind typischerweise (oder normalerweise) B's''. Die
bislang wohl erfolgreichste Formalisierung des Ermangelungsschließens stellt
die in Abschnitt 3.7 eingeführte Ermangelungslogik (oder kurz
E-Logik) dar. Der Schluß von
auf
wird hier gezogen, falls sich durch die Hinzunahme von
zur Menge der Schlußfolgerungen kein Widerspruch ergibt. Dem
gegenüber wird in den in Abschnitt 3.9 vorgestellten konditionalen
Logiken (oder kurz K-Logiken)
zusätzlich zu oder anstelle der klassischen Implikation noch die
konditionale Implikation eingeführt und entweder als zusätzlicher Operator
verwendet oder auf die klassische Implikation zurückgeführt.
Beim autoepistemischen Schließen
wird versucht, die
Schlüsse einer selbstreflektierenden Person zu formalisieren. In dieser Sicht
schließt ein Akteur sowohl über die betrachtete Weltbeschreibung als auch
-- durch Introspektion -- über sein eigenes Wissen darüber. In der in
Abschnitt 3.8 vorgestellten autoepistemischen Logik (oder kurz AE-Logik)
wird ein Schluß von auf
gezogen, falls der Akteur nicht
glaubt bzw. nicht weiß, daß
gilt.
Allen Ansätzen zum nichtmonotonen Schließen ist gemeinsam, daß sie eine
Qualifizierung der gegebenen formalen Weltbeschreibung durchführen.
wird dabei als der wesentliche Kern aufgefaßt, der durch geeignete
Mechanismen noch zu vervollständigen ist. Die verschiedenen Ansätze
unterscheiden sich in der Art dieser Vervollständigungsmechanismen und der
entsprechenden, zugrundeliegenden Repräsentation von
. Wir führen
nun den Vergleich der verschiedenen nichtmonotonen Ansätze anhand einer
Reihe von Merkmalen aus, die solche Mechanismen charakterisieren. Die
Quintessenz der nachfolgenden Diskussion sammeln wir in
Tabelle 3.1 am Schluß dieses Abschnitts. Wir konzentrieren
uns dabei auf die schon oben genannten Hauptvertreter, nämlich die AWA und
die Zirkumskription für das Weltabgeschlossenheitsschließen, die E- und
die K-Logik für das Ermangelungsschließen, sowie die AE-Logik für
das autoepistemische Schließen. Weitere in diesem Kapitel präsentierte
Ansätze lassen sich auf einen der Hauptvertreter zurückführen. So ist
beispielsweise die in Abschnitt 3.6 vorgestellte Theoriebildung von Poole
ein Spezialfall der E-Logik und die AE-Logik eine Weiterentwicklung der im
Abschnitt 3.8 diskutierten nichtmonotonen Logik von McDermott und Doyle.
Alle Ansätze zum nichtmonotonen Schließen erweitern die klassische
Prädikatenlogik und erlauben, Schlüsse zu ziehen, die über die klassischen
Prädikatenlogik hinausgehen. In diesem Sinne können wir die den Ansätzen
gemeinsame Idee wie folgt beschreiben. Ist eine Weltbeschreibung und
eine Formel (die üblicherweise nicht aus
herleitbar ist), so
stellt ein solcher Ansatz, auf eine für ihn spezifische Weise, eine Menge von
Annahmen
zur Verfügung, so daß
eine konsistente
Erweiterung unseres Weltwissens darstellt und
aus
herleitbar ist. Diese Sichtweise wurde auch schon in Abschnitt 3.2 zur
Illustration der AWA verwendet und in Abbildung 3.1 veranschaulicht.
Wir führen uns nun noch einmal vor Augen, welche Formeln überhaupt sinnvoll
als Annahmen verwendet und damit zu hinzugenommen werden sollten.
Zunächst stellen wir fest, daß durch das Hinzufügen von Formeln, die
bereits in
enthalten oder aus
klassisch herleitbar sind,
keinerlei Effekt hinsichtlich der Ableitbarkeit erzielt wird. Gleichwohl ist
dies
in manchen Ansätzen (wie etwa dem der E-Logik) nicht ausgeschlossen, da ja
nur redundante Information hinzugenommen wird. Letzteres gilt natürlich nicht
für Formeln, deren Negate in
enthalten oder aus
klassisch
herleitbar sind, denn solche Annahmen würden der zugrundeliegenden
Weltbeschreibung widersprechen. Also kommen als sinnvolle und nützliche
Annahmen insgesamt nur solche
Formeln in Frage, für die weder sie selbst noch ihre Negation aus
herleitbar sind. Formal ist damit eine sinnvolle Annahmenmenge
bezüglich
wie folgt eingeschränkt.
Betrachten wir nun die jeweiligen Mechanismen zur Generierung der
Annahmenmenge . Häufig werden hier die Ansätze zum nichtmonotonen
Schließen in zwei Klassen eingeteilt. Zum einen haben wir die
Minimierungsansätze, zu denen das
Weltabgeschlossenheitsschließen zählt, bei dem nur die klassisch aus
der Weltbeschreibung ableitbaren Formeln als gültig und alle anderen
Aussagen als falsch betrachtet werden. Zum anderen haben wir die
konsistenzbasierten Ansätze, zu denen das
Ermangelungsschließen und das autoepistemische Schließen zählt,
bei denen Annahmen aufgrund der Konsistenz von Formeln und damit der
Nichtableitbarkeit der jeweiligen Negation generiert werden.
Bei den in den ersten Abschnitten dieses Kapitels behandelten nichtmonotonen
Formalismen handelt es sich durchweg um Minimierungsansätze. Diese
zeichnen sich dadurch aus, daß nur die in einem gewissen Sinne minimalen
oder sogar kleinsten Modelle betrachtet werden. Während bei der klassischen
Inferenz --
Vollständigkeit vorausgesetzt -- jede Formel ableitbar ist, die in
allen
Modellen gilt, betrachtet man hier eine Art
Minimalinferenz
[Bib87a] in dem Sinne, daß eine Formel dann ableitbar
ist, wenn sie in allen minimalen Modellen gilt. Durch die Eliminierung
nichtminimaler Modelle werden dann mehr und insbesondere auch negative
Formeln ableitbar. Wie dies im einzelnen technisch realisiert wird, wurde in
den jeweiligen Abschnitten dieses Kapitels gezeigt. Wir erinnern lediglich
noch einmal an die Vorgehensweise bei der AWA
(vgl.
Abschnitt 3.2) und bei der Zirkumskription (vgl.
Abschnitt 3.5). Bei der AWA werden negative Grundatome zur
Weltbeschreibung hinzugefügt, falls die Grundatome selbst nicht aus
der Weltbeschreibung ableitbar sind. Man erhält dadurch eine vollständige
Theorie, die jedoch nur dann konsistent ist, wenn
ein kleinstes Modell
besitzt. Dies ist insbesondere bei Hornformeln der Fall. Bei der
Zirkumskription beschränkt man die Folgerbarkeitsbeziehung
auf
diejenigen Modelle der Weltbeschreibung
, in welchen die wenigsten
Objekte (oder Tupel von Objekten) das zirkumskribierte Prädikat erfüllen.
In den konsistensbasierten Ansätzen wird, wie oben schon erwähnt, eine
Annahme dann zur Weltbeschreibung hinzugefügt, wenn die
Negation bestimmter Formeln nicht aus
ableitbar ist. Dabei wird in der
E-Logik die Konsequenz
einer Ermangelungsregel
nur dann zu einer Extension von hinzugefügt, wenn
bereits in der Extension enthalten ist und
mit der Extension
konsistent ist.
In den modalen Ansätzen werden Annahmemengen aufgrund von
Konsistenzbedingungen spezifiziert und explizit in die Weltbeschreibung
aufgenommen. So wird in der AE-Logik die Menge
(neben der zur Introspektion verwendeten Annahmenmenge
)
als Konsistenzannahmen zur Weltbeschreibung hinzugefügt, bevor der
Ableitungsmechanismus in Gang gesetzt wird. Eine modale Propositionen der Form
wird also nur dann hinzugefügt, wenn
nicht
schon ein der Extension
. In der K-Logik von Delgrande wird
eine konditionale Implikation
dann als materiale
Implikation
zur speziellen Weltbeschreibung
hinzugefügt, wenn die so erhaltene Menge konsistent ist (und
die im Abschnitt 3.9.1 genannten
Spezifizitätskriterien erfüllt).
Bei der Unterscheidung zwischen konsistenz- und minimierungsbasierten
Ansätzen handelt es sich allerdings lediglich um eine mögliche Sichtweise.
In der Literatur finden sich auch andere Klassifikationen (siehe zB.
[Rei87a, Bre87]). Auch ist die Trennung in konsistenz- und
minimierungsbarierte Ansätze nicht so strikt, wie sie vielleicht auf den
ersten Blick aussieht. Betrachten wir beispielsweise die in Abschnitt 3.3
vorgestellte Prädikatsvervollständigung, ein zur Klasse des
Weltabgeschlossenheitsschließens gehörender und damit
minimierungsbasierter Ansatz. Für die (semantische)
Prädikatsvervollständigung existiert ein für solitäre Klauselmengen
korrekter, syntaktischer Mechanismus, nämlich die in Abschnitt 3.4
präsentierte Negation als Mißerfolg (oder kurz NaM). Dabei wird das
Negat eines Grundatoms dann als ableitbar angenommen, wenn der Versuch das
Atom selbst zu beweisen in endlicher Zeit fehlschlägt. Wie in [GL91]
gezeigt, ist die NaM ein Spezialfall der E-Logik und somit auch
konsistenzbasiert. Deshalb führen wir die NaM in der
Tabelle 3.1 auch unter der E-Logik an. Aber auch die AWA und
die Zirkumskription können als konsistenzbasierte Ansätze angesehen werden.
Dies ist
bei der AWA noch offensichtlicher, da hier die Negation eines Grundatoms
hinzugenommen wird, falls das Atom selbst nicht ableitbar ist, was als
Konsistenzbedingung angesehen werden kann. Bei der Zirkumskription ist die
Möglichkeit einer Sicht als Konsistenzansatz hingegen nicht ganz so
offensichtlich. Betrachten wir dazu die Zirkumskriptionsformel für ein
Prädikat in
so beobachten wir, daß
nur für solche Prädikatsausdrücke
gefordert wird, die auch
erfüllen, dh. für die
gilt. Interpretieren wir diese Bedingung als eine Art Konsistenztest, dann
wird damit die Minimalitätsforderung
nur auf solche Prädikatsausdrücke
angewendet, die mit der
Weltbeschreibung
(in diesem Sinne) konsistent sind.
Auf der anderen Seite aber unterscheiden sich minimierungs- und
konsistenzbasierte
Ansätze in der Frage, ob die durch die Anwendung des zugrundeliegenden
Mechanismus auf eine konsistente Weltbeschreibung
erhaltenen
Extensionen selbst wieder konsistent sind. Für alle
konsistenzbasierten Ansätze kann diese Frage positiv
beantwortet werden, während dies für Minimierungsansätze nicht der Fall
ist. So haben wir bereits in
Abschnitt 3.1 festgestellt, daß die AWA zu einer
inkonsistenten Theorie führen kann, falls die ihr zugrundeliegende
Weltbeschreibung kein kleinstes Modell besitzt.
Dasselbe Problem taucht auch in der Zirkumskription auf. Besitzt eine
Weltbeschreibung keine minimalen Modelle, so führt die Zirkumskription zu
einer inkonsistenten Theorie.
In den letzten Absätzen haben wir Möglichkeiten zur Klassifizierung der Ansätze zum nichtmonotonen Schließen aufgezeigt. Im folgenden wollen wir anhand einiger Kriterien weitere Unterschiede zwischen den einzelnen Ansätzen herausarbeiten und in der Tabelle 3.1 festhalten. Zunächst wenden wir uns der Repräsentation sowie der Behandlung von Ermangelungswissen zu.
In der E-Logik werden Ermangelungsregeln als Kalkülregeln der Gestalt (3.2) formalisiert. In unserem Beispiel der Eiscreme-liebenden Kinder haben wir in Abschnitt 3.7 die (normale) Ermangelungsregel
verwendet. Ist eine solche Kalkülregel anwendbar, so wird ihre Folgerung
als Annahme zur Extension der Weltbeschreibung hinzugefügt.
In der K-Logik von Delgrande werden Ermangelungsregeln als konditionale Implikationen repräsentiert, wie dies durch unser Beispiel
veranschaulicht wird. Grundinstantiierte materiale Implikationen der Form
werden dann zur speziellen Weltbeschreibung
hinzugenommen, wenn sie mit ihr konsistent sind und die in
Abschnitt 3.9.1 genannten Spezifizitätskriterien
erfüllen.
In der AE-Logik werden Ermangelungsregeln mittels modaler Formeln formalisiert. So lautet die Ermangelungsregel in unserem Eiscreme-Beispiel 3.2 hier
Modale Formeln der Gestalt werden als
Annahmen zur Extension der Weltbeschreibung dann hinzugefügt, wenn (wie oben
bereits angesprochen)
nicht schon in der Extension
enthalten ist.
Ein ähnliches Vorgehen ist auch bei der AWA
gegeben. Ist ein Grundatom nicht aus der Weltbeschreibung
ableitbar, so wird deren Negat, nämlich
, als
Annahme hinzugefügt, bevor der Ableitungsmechanismus in Gang gesetzt wird.
Bei dieser Vorgehensweise werden also nur Formeln der Prädikatenlogik erster
Stufe betrachtet.
Dagegen wird zur Zirkumskription eine Sprache der Prädikatenlogik zweiter Stufe verwendet. Ermangelungsregeln selbst werden allerdings weiterhin in der Prädikatenlogik erster Stufe formuliert. So haben wir in Abschnitt 3.5 die Ermangelungsregel unseres Eiscreme-Beispiel 3.2 mittels der Formel
formalisiert, wobei das Prädikat das Attribut ``abnormal''
bezeichnet. Durch die Hinzunahme des Axioms der Form (3.3) wird dann die
Zugehörigkeit von Objekten zu bestimmten ausgezeichneten Prädikaten, den
sogenannten zirkumskribierten Prädikaten, minimiert. Beispielsweise kann man
so durch Zirkumskription des Prädikats
in der letzten Formel
ableiten, also für
zeigen, daß es ``normal'' ist.
Die Wahl des jeweils verwendeten Mechanismus hat zahlreiche Konsequenzen. Zunächst bestimmt der Mechanismus die syntaktische Gestalt der Annahmen, so daß mit seiner Wahl auch die Wahl der dem Ansatz zugrundeliegenden Sprache eng verknüpft ist. Bei der vorangegangenen Diskussion haben wir implizit die jeweils zugrundegelegte Sprache bereits mit besprochen. Bei der E-Logik handelt es sich hierbei um beliebige Formeln der Prädikatenlogik erster Stufe, die als Annahmen hinzugenommen werden. Auch bei der AWA wird eine Sprache der Prädikatenlogik erster Stufe zugrundegelegt. Allerdings werden hier als Annahmen nur negative Grundatome verwendet.
Obwohl eine Weltbeschreibung in der Zirkumskription üblicherweise auch in der
Prädikatenlogik erster Stufe formuliert wird, muß prinzipiell eine
Sprache der Prädikatenlogik zweiter Stufe betrachtet werden, da das
Zirkumskriptionsaxiom (3.3) eine Formel zweiter Stufe darstellt.
Wie wir allerdings in Abschnitt 3.5.1 gesehen haben, existieren große
Formelklassen, für die man auch ein Zirkumskriptionsaxiom in der
Prädikatenlogik erster Stufe angeben kann, so daß für diese Klassen die
gesamte Behandlung in der Sprache erster Stufe durchführbar ist.
Wie bei der AWA ist auch bei der Zirkumskription
die Gestalt der Annahmen beschränkt. Es können nur neue negative
Grundatome von zirkumskribierten Prädikaten (wie in unserem
obigen Beispiel) abgeleitet werden. Dies wird bei der variablen
Zirkumskription insoweit verallgemeinert, als dort auch beliebige Literale von
variierten Prädikaten abgeleitet werden können (vgl. Abschnitt 3.5.2).
Die AE-Logik bedient sich als modale Logik einer modalen Sprache erster
Stufe. Auch hier ist diese Erweiterung auf die Gestalt der hinzuzufügenden
Annahmenmenge zurückzuführen, die wir -- wie oben gezeigt -- für
eine gegebene Extension
auch exakt angeben können.
Weitere Kriterien zum Vergleich der nichtmonotonen Formalismen sind die
Möglichkeit zur Revision einer Weltbeschreibung
und die Frage,
inwieweit ein Ansatz die Widerspruchsfreiheit der Weltbeschreibung
gewährleistet.
Die im Kontext der nichtmonotonen Logiken wohl interessanteste
Revisionsoperation ist das Hinzufügen neuer Information, wie sie etwa durch
Beobachtungen auftreten kann. Trivialerweise erlauben alle Ansätze die
Hinzunahme von bereits mit oder ohne Hilfe von Ermangelungswissen abgeleiteten
Aussagen. In den meisten Ansätzen wird eine solche Operation ganz einfach
durch eine Erweiterung der Weltbeschreibung bzw. der darin
ausgezeichneten Menge von Fakten realisiert. Eine Ausnahme bildet hierbei die
Zirkumskription, bei der das Zirkumskriptionsaxiom
(3.3) und darin insbesondere die Teilformel
geeignet modifiziert werden müssen.
Ein interessanter Fall tritt ein, wenn etwa eine Beobachtung einer zuvor
getroffenen Annahme widerspricht. Eine solche Situation führt jedoch in
keinem der betrachteten Ansätze zu Problemen. Widerspricht eine Beobachtung
einer getroffenen Annahme, so wird letztere zurückgenommen, was sich formal
in der Eigenschaft der Nichtmonotonie widerspiegelt.
Ein weiterer Unterschied der verschiedenen Ansätze ist durch die Möglichkeit zur Bildung alternativer Extensionen einer gegebenen Weltbeschreibung gegeben. Die Bildung alternativer Extensionen ist insbesondere in allen konsistenzbasierten Ansätzen möglich. Man hat daher die Möglichkeit, zwischen einem skeptischen und einem leichtgläubigen Theoriebegriff zu wählen. Im ersteren Fall akzeptiert man eine Aussage nur dann, wenn sie in allen alternativen Extensionen der Weltbeschreibung enthalten ist, wohingegen man im zweiten Fall eine Aussage schon dann als herleitbar betrachtet, wenn sie in mindestens einer solchen Extension vorkommt. Dagegen ermöglichen die Minimierungsansätze, wie die AWA oder die Zirkumskription, nur einen skeptischen Theoriebegriff. Semantisch gesehen ist dies auch sinnvoll, da man sich bei diesen Ansätzen auf die Folgerbarkeit in allen minimalen Modellen oder sogar in einem kleinsten Modell beschränkt. Damit ist die Menge der ableitbaren Formeln eindeutig durch die in den minimalen Modellen gültigen Formeln gegeben.
Die K-Logiken von Delgrande und von Geffner und Pearl erlauben ebenfalls mehrere Extensionen. Jedoch werden hier spezifischere Informationen ausgenutzt, um Präferenzen zwischen Extensionen auszurechnen. Sind bei einer gegebenen Weltbeschreibung mehrere konditionale Implikationen anwendbar, dann wird die Implikation bevorzugt, deren Prämissen am spezifischsten sind. Die Spezifizität folgt dabei aus der Weltbeschreibung. Im Gegensatz dazu können solche Präferenzen in der E-Logik oder der Zirkumskription erst dann bestimmt werden, wenn weitere Standardannahmen bzw. Ordnungen auf den zirkumskribierten Prädikaten explizit zur Weltbeschreibung hinzugefügt werden.
Ein komplexitätstheoretischer Vergleich der auf Fixpunktkonstruktionen beruhenden Ansätze zum nichtmonotonen Schließen (Ermangelungslogik, nichtmonotone Logik und autoepistemische Logik) findet sich in [Got92a], auf den wir hier nicht mehr eingehen können. Wir erwähnen lediglich in diesem Zusammenhang, daß die konditionalen Ansätze besonders aus komplexitätstheoretischen Gründen Vorteile zu bieten scheinen.
Auch wollen wir an dieser Stelle nicht unerwähnt lassen, daß alle in den vorangegangenen Abschnitten vorgestellten Ansätze zur Formalisierung nichtmonotoner Schlußweisen im allgemeinen Fall nicht entscheidbar sind. Die Prädikatenlogik erster Stufe ist semi-entscheidbar, dh. nur die gültigen Formeln einer betrachteten Theorie sind rekursiv aufzählbar, dh. der Nachweis der Gültigkeit kann für jede gültige Formel in endlicher Zeit mechanisch erbracht werden. Ein Nachweis der Falsifizierbarkeit ist dagegen im allgemeinen nicht durchführbar, da dieser nicht terminieren muß. Bezieht man sich nun beim Ableiten von Formeln auf die Konsistenz von Aussagen und damit auf die Nichtableitbarkeit der Negation dieser Aussagen, so muß dieser Nachweis nicht terminieren. Damit verlieren alle Logiken, die sich beim Inferenzprozeß auf die Konsistenz von Aussagen berufen, die Eigenschaft der Semi-Entscheidbarkeit. Es ist folglich nicht einmal mehr entscheidbar, ob eine in einer nichtmonotonen Logik gültige Aussage auch ableitbar ist.
Beschränkt man sich allerdings auf entscheidbare Theorien, etwa solche mit endlichem Herbranduniversum, so verursacht eine Konsistenzprüfung grundsätzlich keine Probleme. Denn ist eine Formel falsifizierbar, dann kann auch der Nachweis dafür nach endlich vielen Schritten erbracht werden. Demnach ist es dann auch für eine konsistenzbasierte nichtmonotone Logik entscheidbar, ob eine Aussage zur Theorie gehört oder nicht.
Aber auch bei anderen nichtmonotonen Logiken, die wie die Zirkumskription ohne explizite Konsistenzbedingungen arbeiten, ist die Semi-Entscheidbarkeit oder gar die Entscheidbarkeit nur durch die Einschränkung auf spezielle Formelklassen gewährleistet. Bei der Zirkumskription ist man durch die Verwendung von Formeln der Prädikatenlogik zweiter Stufe vor etliche Probleme gestellt. Da die Prädikatenlogik zweiter Stufe nicht mehr semi-entscheidbar ist, ist es auch nicht möglich, den Nachweis der Gültigkeit einer gültigen Formel mechanisch zu erbringen. Die hieraus erwachsenden Probleme sind vielfältig. Zum einen stimmen in der Prädikatenlogik zweiter Stufe die Begriffe der Erfüllbarkeit und Konsistenz nicht mehr überein, und zum anderen gilt der Kompaktheitssatz nicht mehr. Der letztere ist unter anderem sehr wichtig für das Erbringen von mechanischen Beweisen, denn er besagt, daß eine Theorie genau dann erfüllbar ist, wenn jede ihrer endlichen Teilmengen erfüllbar ist. Bei Widerspruchsbeweisen genügt es dann zu zeigen, daß eine endliche Teilmenge unerfüllbar ist, um die Unerfüllbarkeit der gesamten Menge nachzuweisen. In der Prädikatenlogik zweiter Stufe ist die Existenz einer endlichen inkonsistenten Teilmenge zwar eine hinreichende, aber nicht notwendige Bedingung für die Inkonsistenz. Aber auch bei Vernachlässigung dieser Probleme bleibt die Schwierigkeit, die geeigneten Formeln für die Substitution der Variablen zweiter Stufe in der Formel (3.3) anzugeben. Die meisten in den vorigen Abschnitten angegebenen Beispiele ermöglichten es, durch eine geschickte Wahl der Substitution der Prädikatsvariablen auch die gewünschten Resultate zu erhalten. Doch verbirgt sich dahinter im allgemeinen eine vielschichtige Heuristik, die in den Inferenzprozeß eingeht und dementsprechend auch formuliert werden muß.
Das Problem der Unentscheidbarkeit ist darauf zurückzuführen, daß auf ganze Theorien Bezug genommen wird. Ob man die Konsistenz einer Aussage bezüglich einer Theorie fordert oder versucht, sich auf die klassisch ableitbaren und damit auch folgerbaren Aussagen einer Theorie zu beschränken, immer muß man sich dabei auf die Theorie als Ganzes beziehen. Die Zirkumskription verwendet dazu ein Axiom der Prädikatenlogik zweiter Stufe, wodurch hier die Semi-Entscheidbarkeit verloren wird. Die konsistenzbasierten Ansätze fordern explizit die Konsistenz einer Theorie.
Das Problem der mangelnden Entscheidbarkeitseigenschaften ist zwar schwerwiegend, doch sollte es nicht dazu führen, die nichtmonotonen Logiken pauschal zu disqualifizieren. Zum Vergleich erwähnen wir, daß auch die Nichtentscheidbarkeit der Prädikatenlogik erster Stufe zunächst als ein schwerwiegender Nachteil angesehen wurde, ohne der erfolgreichen Entwicklung von Beweissystemen Abbruch zu tun. Ist man sich des Problems bewußt und lernt damit umzugehen, so können die damit verbundenen Probleme durchaus bis zu einem gewissen Grade gemeistert werden.
Abschließend weisen wir darauf hin, daß im letzten Teil des Abschnittes 4.2.4 weitere Vergleiche nichtmonotoner Logiken gezogen werden, die in diesem Sinne auch als Fortsetzung des vorliegenden Abschnittes angesehen werden können. Auch erwähnen wir noch, daß sich in der Literatur eine Reihe von Arbeiten über paarweise Vergleiche nichtmonotoner Ansätze finden, die wir hier im einzelnen nicht mehr berücksichtigen konnten [Lif85a, GPP89, Rei82, Lif89, QI91, Kon88, Tru91].
AWA | Zirkumskription | E-Logik [NaM] | K-Logik | AE-Logik | |
Klassifikation | minimierungsbasiert | minimierungsbasiert | konsistenzbasiert | konsistenzbasiert | konsistenzbasiert |
Regelform | -- | ![]() ![]() ![]() | ![]() [B :- A, not C] | ![]() | ![]() |
Lesart | -- | ![]() ![]() | ![]() ![]() ![]()
[ | ![]() ![]() | ![]() ![]() ![]() |
Sprachebene | erste Stufe | zweite Stufe | erste Stufe | erste Stufe | erste Stufe |
Logik | Prädikatenlogik erster Stufe | Prädikatenlogik zweiter Stufe | Prädikatenlogik erster Stufe [A,B,C Grundatomformeln] | Konditionale Logik erster Stufe | Modallogik erster Stufe |
Annahmen | Negative Grundatomformeln | Negative Literale der zirkumskribierten Prädikate, sowie beliebige Literale der variierten Prädikate (bei variabler Zirkumskription) | Beliebige Formeln der Prädikatlogik erster Stufe, die als Konsequenzen von Ermangelungsregeln gegeben sind. | Klassische Varianten der Konditionalsätze | Modale Propositionen der Gestalt ![]() ![]() |
Mechanismus | Metaaussage | Axiom zweiter Stufe | Fixpunktberechnung mittels Kalkülregeln | Vorberechnung der intendierten Formeln | Fixpunktberechnung mittels modaler Propositionen |
Revision | Ja | Ja, bei Modifikation des Zirkumskriptionsaxioms | Ja | Ja | Ja |
Widerspruchsfreiheit | Nein | Nein | Ja | Ja | Ja |
Alternative Extensionen | Nein | Nein | Ja | Ja | Ja |
Spezifizität | Nein | Nein | Nein | Ja | Nein |
Christoph Quix, Thomas List, René Soiron