Nächste Seite: 3.5.3 Punktweise Zirkumskription Vorige Seite: 3.5.1 Prädikatszirkumskription

3.5.2 Allgemeinere Formen der Prädikatszirkumskription

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].

impliziert , .

In dem angekündigten Spezialfall haben wir dann die Umkehrung [Lif87].

Sind alle Vorkommen von in positiv, so ist äquivalent mit .

In 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.

Der Beweis für das folgende auf Lifschitz zurückgehende Resultat findet sich in [GN89].

Enthält kein positives Auftreten von und tritt in nicht auf, so ist äquivalent mit .

Zur Illustration wenden wir dieses Ergebnis auf unser Standardbeispiel mit der Eiscreme an. Die Formel

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 auch konsistent.

Universelle Theorien (die in pränexer Normalform keine Existenzquantoren haben) zB. sind immer wohlfundiert. Für weitere Klassen siehe [Lif86a, MR90].