Die erste Verallgemeinerung der Prädikatszirkumskription besteht in der parallelen Umschreibung von mehr als einem Prädikat. Sie ist gegeben durch exakt dieselbe Formel wie oben.
Nur steht hier nun für ein Tupel
,
für
und
für die Konjunktion dieser Ausdrücke in den einzelnen
Komponenten, dh. für
. Bevor wir auf die Bedeutung
dieser Verallgemeinerung zu sprechen kommen, betrachten wir noch eine weitere
Variante. Für sie gilt die folgende Zirkumskriptionsformel.
Wir wollen hier gleich den allgemeinsten Fall annehmen, daß sowohl
als auch
für Tupel von Prädikatszeichen stehen. Man beachte,
daß im Vergleich mit der vorangegangenen Formel noch mehr verlangt wird.
Nicht nur soll es kein minimaleres
wie vorher geben, sondern dies
auch dann nicht, wenn in
dabei auch die Ersetzung der Prädikatszeichen
durch andere Zeichen
erlaubt ist. Man spricht daher
hier von der Zirkumskription von
in
mit variablem
oder kurz von der variablen (Prädikaten-)Zirkumskription
.
Während vorher nur
diejenigen Prädikate verändert werden
konnten, über die minimiert wird, können hier noch weitere Prädikate variieren.
Daß diese letztere Verallgemeinerung in der Tat eine stärkere Form der Zirkumskription ergibt, läßt sich an unserem Beipiel 3.2 illustrieren. Wie wir im letzten Unterabschnitt gesehen haben, liefert die einfach Prädikatszirkumskription von ``Abnormal'' nicht das gewünschte Ergebnis. Wir lassen nun aber noch zusätzlich das Prädikat ``Liebt-Eiscreme'' variieren und erhalten dann in der Tat das gewünschte Ergebnis, daß nämlich Larissa Eiscreme liebt.
Warum variieren wir ``Liebt-Eiscreme'' und nicht ``Kind''? Semantisch leuchtet das sofort ein, denn an dem Kindsein von Larissa kann ja kein Zweifel bestehen; nur ihre Liebe zur Eiscreme ist unklar. Wir sehen also schon hier, daß bei der syntaktischen Formulierung der Aufgabe wichtige semantische Information dieser Art erforderlich ist, die syntaktisch in der beschriebenen Weise eingebracht wird.
Wir wollen zur
Illustration die Ableitung in diesem einfachen Beispiel einmal direkt, dh. ohne Verwendung
eines der Reduktionssätze skizzieren. Zur Abkürzung der Formeln wird nun
jedoch nur mehr der erste Buchstabe eines jeden konstanten Zeichens verwendet.
Unsere Ausgangsformel lautet also in diesem Fall wie folgt.
Hieraus ergibt sich die folgende Zirkumskriptionsformel .
Wie immer haben wir so viel Quantoren wie möglich eingespart, da sie bei
Bedarf unmißverständlich nachgetragen werden können (und erfahrungsgemäß den
``normalen'' Leser eher abschrecken). Wie in der Prädikatenlogik erster
Stufe ist auch in der zweiter und höherer Stufe die Instantiierung der
existenzquantifizierten Variablen eines der entscheidenden Probleme. Während
es dort die Unifikation in relativ einfacher Weise ermöglicht, ist ein solch
einfaches Verfahren hier im allgemeinen nicht mehr möglich. In diesem
Beispiel sieht man allerdings schnell, daß die Substitution von
durch
und von
durch
die Fortsetzung der Ableitung so ermöglicht, daß sich
schließlich
ergibt.
bedeutet
hierin das logische falsum, also die immer falsche Aussage. Das
Ergebnis besagt also, daß niemand abnormal ist. Dies in
eingesetzt, ergibt
, dh. Larissa liebt tatsächlich Eiscreme.
Wir erwähnen an dieser Stelle ausnahmsweise noch ein anderes Beispiel, das einige Berühmtheit erlangt hat. Es ist das sogenannte Yale shooting problem [HM87] und besteht aus den folgenden Formeln.
Es soll etwa besagen, daß eine Person namens Fred zum Zeitpunkt
lebt. Dann wird ein Gewehr geladen, wodurch wir in einen Zeitpunkt
weiterrücken. Dann warten wir einen Moment und kommen so zu dem Zeitpunkt
, ohne daß sich dazwischen etwas anderes aufgrund der Formeln
ereignet hätte. Schließlich wird geschossen, so daß zum Zeitpunkt
Fred normalerweise tot ist.
Hank und McDermott haben in Ihrer Arbeit gezeigt, daß eine Zirkumskription
des Prädikats unter variablem
nicht zu dem erwarteten
Ergebnis führt. Sie zeigen außerdem, daß auch andere nichtmonotone
Formalismen, die wir in diesem Kapitel noch behandeln werden, mit diesem
Beispiel ihre Probleme haben.
Das Beispiel kann als eines der produktivsten Beispiele dieses Gebietes
angesehen werden, weil es die Entwicklung einer Reihe von verbesserten
Varianten der in diesem Kapitel besprochenen Formalismen ausgelöst hat. Es
hat allerdings nicht den nichtmonotonen Ansatz als ganzes erschüttert, wie
es ursprünglich den Anschein hatte. Eine der einfachsten Lösungen dieses
Problems wird in [Bak91] dadurch gegeben, daß anstelle von
das Funktionszeichen
variiert wird, so daß am Formalismus der
Zirkumskription selbst nichts geändert werden muß. Die Arbeit enthält
auch eine Referenz auf die vielen anderen Lösungsvorschläge in der
Literatur, unter denen sich auch die im nächsten Unterabschnitt besprochene
punktweise Zirkumskription befindet.
Während nach dem Vorangegangenen die variable Zirkumskription also eine echte Verallgemeinerung ergibt, werden wir nun feststellen, daß die erstere Verallgemeinerung von einem auf mehrere Prädikate in einem wichtigen Spezialfall nicht wirklich eine echte Verallgemeinerung darstellt. Zuächst gilt der folgende Satz [Lif87].
In dem angekündigten Spezialfall haben wir dann die Umkehrung [Lif87].impliziert
,
.
Sind alle Vorkommen vonIn diesem Fall positiven Auftretens der Zirkumskriptionsprädikate läßt sich die Berechnung also auf den im letzten Unterabschnitt behandelten einfachen Fall zurückführen, wobei sich die dortigen Begriffe wie `solitär' und `separabel' in natürlicher Weise auf den vorliegenden Fall mehrerer Prädikate verallgemeinern. Zur Bewertung der Wichtigkeit des Spezialfalles sei erwähnt, daß in der Praxis die zu minimierenden Prädikate in der Tat so gut wie immer positiv auftreten. Die parallele Zirkumskription erweist sich in diesem Sinne von minderem Interesse. Auf ein in Theorem 6.11 von [GN89] formuliertes Ergebnis der Zurückführung der parallelen Zirkumskription im Spezialfall sogenannter geordneter Formeln auf eine Formel der Prädikatenlogik erster Stufe sei hier daher nur hingewiesen.in
positiv, so ist
äquivalent mit
.
Der Beweis für das folgende auf Lifschitz zurückgehende Resultat findet sich in [GN89].
EnthältZur Illustration wenden wir dieses Ergebnis auf unser Standardbeispiel mit der Eiscreme an. Die Formelkein positives Auftreten von
und tritt
in
nicht auf, so ist
äquivalent mit
.
besagt neben dem Kindsein von Larissa und dem Eiscremelieben von normalen Kindern,
daß (Zahn-) Schmerzen zur Abnormalität führen. Die Anwendung des
Satzes auf diese Formel ergibt
Hat daher Larissa Zahnschmerzen, dann läßt sich nicht ableiten, daß sie Eiscreme mag, ganz wie es der Aufgabenstellung entspricht.
In vielen Fällen einer Weltbeschreibung ergeben sich eine Reihe von Regeln,
die normalerweise gelten, deren Ausnahmen jedoch miteinander in einer
hierarchischen Beziehung stehen. Betrachten wir zur Illustration nochmals unser
Eiscremebeispiel mit der Zahnschmerzregel in der bereits am Ende des Abschnitts 3.3 betrachteten Fassung. Die
Zahnschmerzen verleiden in der Regel den Appetit auf Eiscreme, so daß das
Prädikat
mit oberster Priorität minimiert werden muß,
während
nur für die verbleibenden Fälle, also mit niedrigerer
Priorität, zu minimieren ist. Um dies formal zu realisieren, ist in der
Zirkumskriptionsformel lediglich der Anteil
in der lexikographischer
Weise zu interpretieren, die uns aus vielen Anwendungen (wie zB. der
Namensanordnung in Telefonbüchern) vertraut ist. Im Falle zweier
Prädikate
ergibt sich also in diesem Sinne für
die folgende Formel.
In Worten, ist , dann ist das erste Konjunktionsglied in jedem
Fall erfüllt, da es ja eine schwächere Aussage darstellt, während das
zweite Konjunktionsglied gilt, weil die Prämisse seiner Implikation falsch
ist; ist andernfalls
, dann muß
gelten, um
die Formel wahr zu machen, während die Formel sonst immer falsch ist. Die
Verallgemeinerung dieser Definition von
auf mehr als zwei Prädikate ist nun einfach.
Hierin lassen sich die 's auch noch zusätzlich wie oben als Mengen
von Prädikaten auffassen. Interpretiert man
in unserer
bisherigen Zirkumskriptionsformel durch diese Formel, so erhält man also die
Prioritätszirkumskription
,
wobei
die höchste Priorität hat. Sie
läßt sich vermöge der folgenden Formel [Lif87] auf die bisherige Form der
Zirkumskription zurückführen.
Es handelt sich also nicht wirklich um eine Verallgemeinerung der bisherigen Form.
Auch für die verallgemeinerten Formen der Zirkumskription sind die Fragen nach
der Konsistenz untersucht worden. Wie schon am Ende des letzten Unterabschnitts
erwähnt, spielen hierbei -minimale Modelle eine wichtige Rolle, also
Modelle, die minimal
bezüglich
sind, ein Begriff, für dessen exakte Definition
wir zB. auf [Eth88] (S. 133) verweisen. Hiermit ergibt sich der
folgende Konsistenzsatz [Eth88].
Z[W;P;X] ist in jedem (P,X)-minimalen Modell von W erfüllt.Unter welchen Bedingungen ist die Voraussetzung des Satzes erfüllt? Hierzu führen wir den folgenden Begriff ein.
Eine Theorie W heißt wohlfundiert bezüglich (P,X), wenn jedes Modell von W ein (P,X)-minimales Untermodell hat.Hiermit ergibt sich nun der auch praktisch anwendbare Konsistenzsatz [Eth88].
Ist W konsistent und bezüglich (P,X) wohlfundiert, so ist auchUniverselle Theorien (die in pränexer Normalform keine Existenzquantoren haben) zB. sind immer wohlfundiert. Für weitere Klassen siehe [Lif86a, MR90].konsistent.
Christoph Quix, Thomas List, René Soiron