Kapitel 4 - Prädikatenlogik
 
 
 
4.1 Die Sprache der Prädikatenlogik zurück

Die Prädikatenlogik ist eine Erweiterung der Aussagenlogik in dem Sinne, als sie anstelle elementarer Aussagenvariablen nunmehr strukturierte Ausdrücke betrachtet. Aus der Aussagenlogik wissen wir bereits, wie ein logisches System einzuführen ist. Dieses wird in drei Schritten aufgebaut: Die Syntax legt fest, welches zulässige Ausdrücke der Sprache sind. Die Semantik bestimmt die Interpretationen der Ausdrücke, schließlich ist in einem abschließenden Schritt die Widerspruchsfreiheit und Vollständigkeit des Systems nachzuweisen.

Wir wollen uns der Prädikatenlogik zunächst informell nähern. Wir erinnern uns, dass Aristoteles elementare Aussagesätze als Ausdrücke bezeichnet hat, in denen etwas (mit Hilfe des Prädikats) von etwas (dem Subjekt) ausgesagt wird. Da auf der Stufe der Prädikatenlogik deiktische Ausdrücke (wie etwa Pronomina, Orts- und Zeitadverbien) nicht betrachtet werden, können wir zunächst (informell) das logische Prädikat durch denjenigen Teil des Satzes bezeichnet sehen, den man erhält, falls man den Subjektnamen (und eventuell auftretende Objektnamen) herausstreicht, als z. B. "Logik macht Spaß." oder " Trier liegt an der Mosel." Durch Herausstreichen von Subjekts- und Objektnamen erhält man Leerstellen im Satz, die als Bestandteile der Prädikate betrachtet werden. Ein Prädikat mit n Leerstellen wird als n-stelliges Prädikat bezeichnet. Eine Art Normalform für Prädikate erreichen wir, falls der Prädikatsname vorangestellt erscheint. Aus unseren Beispielen wir also: "macht Spaß (Logik)" sowie "liegt an (Trier, Mosel)". Natürlich ist die Reihenfolge der geklammerten Ausdrücke bedeutsam. In einem letzten Schritt werden die "sprechenden" Namen unserer prädikatenlogischen Ausdrücke durch Variablen und / oder spezielle Ausdrücke für Konstanten ersetzt, als etwa " P ( a ) " oder " G ( b, c ) ". Damit haben wir eine erste, rudimentäre Formalisierung der Struktur einfacher Aussagesätze erreicht. Die Leerstelle eines Prädikats, in welche die Konstanten eingesetzt werden, können durch Ausdrücke für Variablen markiert werden: Etwa " P ( x ) ". Für die Variable können dann Konstanten eingesetzt werden, um den Ausdruck wieder "eindeutig" zu machen. Die Bedeutung eines Prädikats ist eine Relation über dem betrachteten Universum, einstellige Prädikate bedeuten Eigenschaften.

Die Erweiterung der Ausdrucksstärke der Prädikatenlogik gegenüber der Aussagenlogik besteht nun im wesentlichen in der Einführung prädikatenlogischer Operatoren, die aus einstelligen Prädikaten (wahrheitsfunktionale) Sätze erzeugen. Hierzu existieren die Quantoren " ∀ " (Allquantor) und " ∃ " (Existenzquantor). Sei " (Allquantor) und " " (Existenzquantor). Sei P ein einstelliges Prädikat, dann lassen sich die Aussagen "Für alle Entitäten des betrachteten Universums U gilt P" und "Es existiert eine Entität im Universum mit der Eigenschaft P" formalisieren sich zu " ∀ x P ( x ) " bzw. " x P ( x ) ". Der Skopus eines Quantors wird durch entsprechende Klammerung angezeigt. In dem Ausdruck " ∀ ( ( F ( x ) G ( x, y )) P ( x ) " bezieht sich der Quantor nicht auf die dritte Okkurenz von x. Ferner gilt, dass Quantoren stärker binden als die logischen Funktoren " , , etc. Die Ersetzung einer Konstanten durch eine Variable, die anschließend durch einen Quantor gebunden wird, nennt man Quantifizierung.

Wir können nun einige natürlichsprachliche Sätze versuchsweise prädikatenlogisch formalisieren:

1. " Alle F sind G: " ∀ x ( F ( x ) G ( x )).

2. " Kein F ist G: " ∀ x ( F ( x ) ¬ G ( x)).

3. " Einige F sind G: " ( F ( x ) G ( x )).

4. " Einige F sind nicht G: " x ( F ( x ) ¬ G ( x )).

Betrachten wir den Satz "Jemand liebt jeden" (prädikatenlogisch " x y G ( x, y ) "). Bei Geltung dieses Satzes können wir folgern, dass jeder von jemanden geliebt wird; also

x y G ( x, y ) y x G ( x, y ).

Die Umkehrung dieses Schlusses gilt sicherlich nicht. Allerdings gilt jedoch die generelle Vertauschbarkeit von identischen Quantoren, so z. B.:

x y G [ ... x, ... y ... ] ∀ y x G [ ... x, ... y ... ]

Und selbstverständlich gilt, dass wenn nur eine Entität des Universums die Eigenschaft F besitzt, dann nicht alle Entitäten die Eigenschaft F nicht besitzen, also:

x F ( x ) ¬ x ¬ F ( x )

M. a. W.: Der Existenzquantor kann mit Hilfe des Allquantors definiert werden.

 
4.2 Die Syntax der Prädikatenlogik zurück

Das Alphabet der Prädikatenlogik (PL) ist die Vereinigung der Mengen PSYMB = { , , ¬, , , , , (, ) } GK (eine Menge abzählbar unendlich vieler Gegenstandskonstanten), GV (eine Menge von Gegenstandsvariablen), FK (eine Menge von Funktionskonstanten für Funktionen beliebiger Stelligkeit) sowie PK (eine Menge von Prädikatskonstanten jeder Stellenzahl n ≤ 1).

Für Konstanten und Variablen werden wir immer metasprachliche Ausdrücke a, b, c, ..., P, G, F, ... bzw. x, y, z, ... verwenden. Unsere Objektsprache ist die Sprache der Prädikatenlogik, unsere Metasprache ist das Deutsche. Ein Ausdruck der Art " F ( x ) G ( x, y )" ist also ein Ausdruck, der neben objektsprachlichen Symbolen metasprachliche Konstanten- und Variablen-Bezeichner enthält und als Bezeichnung für den objektsprachlichen Ausdruck " F ( x ) G ( x, y )" gewählt wird, falls F, G, x, y die objektsprachlichen Korrespondenzen der metasprachlichen F, G, x, bzw. y sind. Diese "Verkomplizierung" der Ausdruckstechnik wird dadurch notwendig, dass, wie wir sehen werden, die Semantik der Prädikatenlogik von dem Hintergrund eines Referenzuniversums erklärt wird. Prädikatskonstanten beziehen sich etwa auf spezifische Relationen über diesem Referenzuniversum. Letztere Ausdrucksvariante ermöglicht uns also eine Entkoppelung von der Spezifität des Referenzuniversums und den zugehörigen objektsprachlichen Bezeichnungen.

Wir verwenden weiterhin das metasprachliche Symbol " * ", zu dem es keine objektsprachliche Entsprechung gibt. Ist " A [ * ] " irgend eine endliche Folge von Grundzeichen der Sprache PL und " * ", so ist " A [ B ] derjenige Ausdruck aus PL, der entsteht, falls alle Vorkommnisse von " * " in " A [ * ] " durch B ersetzt werden. Wir definieren nun, was ein wohlgeformter Ausdruck der Sprache PL ist:

Definition 4.2.1 Die Menge TERM wird wie folgt definiert:

1. GK, GV TERM,

2. t1, ..., tn TERM und f FK f ( t1, ..., tn ) TERM.

Definition 4.2.2 Die Menge der atomaren Formeln ATOM ist definiert durch:

1. t1, t2 TERM ( t1 = t2 ) ATOM,

2. t1, ..., tn TERM und P PK (P ist ein n-stelliges Prädikat aus PK) P ( t1, ..., tn ) ATOM.

Definition 4.2.3 Die Menge PRAED der wohlgeformten Formeln der Prädikatenlogik ist definiert durch:

1. ATOM PRAED,

2. p, q PRAED ¬ p, ( p q ), ( p q ) PRAED,

3. Ist A [ a ] PRAED, a GK, und x GV eine Variable, die in A [ a ] nicht vorkommt, so gilt: x A [ x ], x A [ x ] PRAED. Der Ausdruck " A [ x ] wird als Satzform bezeichnet.

Ferner legen wir fest, dass äußere Klammern immer weggelassen werden können. Zwischen den Funktoren besteht folgende Bindungsordnung (bei abnehmender Bindung): ¬, , , , . Wir definieren:

Definition 4.2.4 Es gilt:

1. p q =def ¬ p q,

2. p q =def ( p q ) ( q p ),

3. x A [ x ] =def ¬ x ¬ A [ x ].

Definition 4.2.5 Die Menge FV der freien Variablen einer wohlgeformten Formel p PRAED ist:

1. p ATOM FV ( p ) = { x GV | x kommt in p vor },

2. FV ( ¬ p ) = FV ( p ),

3. FV ( p q ) = FV ( p q ) = FV ( p ) FV ( q ),

4. FV ( x p ) = FV ( ) x p ) = FV ( p ) - { x }.

Beispiel 4.2.1 FV ( x y R ( x, y, z ) = { z }.

Definition 4.2.6 Eine Formel p PRAED heißt Satz, falls FV ( p ) = . SENT = { p PRAED | FV ( p ) = } ist die Menge aller Sätze.

Wir wollen an dieser Stelle zunächst die Semantik und dann erst syntaktische Ableitungen innerhalb der Prädikatenlogik betrachten. Diese Vorgehensweise empfiehlt sich, da der Ableitungsbegriff in der Prädikatenlogik um einiges komplizierter ist als in der Aussagenlogik. Die Semantik der Prädikatenlogik bietet aber ein leicht zu vermittelndes Verständnis der grundlegenden Konstrukte dieser formalen Sprache.

 
4.3 Die Semantik der Prädikatenlogik zurück

Die Semantik der PL wird mit Hilfe einer Interpretationsfunktion || || eingeführt, die eine Interpretation der prädikatenlogischen Terme, Funktionen und Relationen über einem Gegenstandsbereich U, den wir Universum nennen wollen, umfasst. Die Gegenstandskonstanten bezeichnen Objekte (Entitäten oder auch Einheiten) aus U, Prädikatskonstanten stehen für Begriffe, deren Umfänge mengentheoretisch über Teilmengen von Elementen aus n=0, ...∞ Un eingeführt werden. Funktionskonstanten stehen für Funktionen.

Der Umfang eines einstelligen Begriffs (i. e. einer Eigenschaft) umfasst alle Objekte aus U, die diese Eigenschaft haben. Der Umfang einer n-stelligen Relation ist gleich der Menge aller n-stelligen Folgen von Objekten, die in dieser Relation zueinander stehen. Eine Interpretation der PL über dem Universum U ist dann erklärt über eine Funktion || ||, die jeder Gegenstandskonstanten a ein Objekt || a || U, jeder Prädikatskonstanten P dessen Umfang || P || über U zuordnet. Schließlich wird die Interpretationsfunktion auf Sätze erweitert, indem diese jedem Satz, der keine ungebundenen Variablen enthält, einen Wahrheitswert zuordnet.

Beispiel 4.3.1 Sei U = die Menge aller natürlichen Zahlen beginnend mit 1. R sei die Relation aller Tupel < x, y >, x, y , mit der Eigenschaft, dass x ≤ y. G ist die Menge aller geraden Zahlen. Die Menge der Gegenstandskonstanten ist GK = { a, a', a'', ... }, die Menge der Prädikatskonstanten sei PK = { ..., G, R, ... }. || || sei folgendermaßen definiert: || a || = 1, || a' || = 2, || a'' || = 3, etc.; || R || = R und || G || = G. Ein Satz G ( a ) ist dann wahr, falls die durch a bezeichnete Gegenstandskonstante die durch G bezeichnete Eigenschaft aufweist, das heißt: || G ( a ) || = 1 iff || a || || G ||. Im vorliegenden Falle ist || G ( a ) || = 0, da || a || = 1 || G ||. Es ist nun || F ( a, a'' ) || = 1 iff das Zahlenpaar < || a ||, || a'' || > R iff 1 ≤ 3, was offensichtlich der Fall ist.

Anmerkung 4.3.1 Wie kann nun ein quantifizierter Satz der Art " ∀ x G ( x ) " interpretiert werden? Dieser Satz ist wahr, falls die durch G bezeichnete Eigenschaft auf alle Objekte des Universums zutrifft, das heißt falls G = U. Diese Deutung des Allquantors ist nicht dadurch zu formalisieren, dass man fordert: || ∀ x G ( x ) || = 1 iff für alle Gegenstandskonstanten a GK gilt: || G ( a ) || = 1. Da es nicht zu jedem Objekt aus U eine Bezeichnung aus GK geben muss, ist das Bild von || || u. U. nur eine Teilmenge von U. Ist z. B. || || derart definiert, dass || a || = 2, || a' || = 4, || a'' || = 6, ... und || G || = G, dann gilt für jede Gegenstandskonstante a GK: || a || || G ||, dennoch ist aber nicht jede natürliche Zahl gerade. M. a. W.: x G ( x ) ist nur dann wahr, falls G ( a ) wahr ist, unabhängig davon, welches Objekt aus U a bezeichnet. Insbesondere ist dann also eine Erklärung der Semantik des Allquantors über die Bestimmung

|| x P ( x ) || = 1 iff || P ( a ) || = 1,
aGK

falsch.

Eine Möglichkeit, diese Schwierigkeit zu lösen, besteht darin, dass wir zu einer gegebenen Interpretation || || eine Reihe anderer Interpretationen || ||', || ||'', || || ''', ... ableiten, die mit || || übereinstimmen bis auf höchstens die Werte für eine Gegenstandskonstante a. Diese Konstante kann durch die Folge der Interpretationen || ||', || ||'', || || ''', ... der Reihe nach auf alle Elemente des Universums U abgebildet werden. Unter dieser Voraussetzung kann die Semantik des Allquantors wie folgt formalisiert werden: || ∀ x P ( x ) || = 1 iff wenn für alle Interpretationen || ||' || || gilt: || P ( a ) ||' = 1. Der Ausdruck " || ||' || ||" besagt dabei, dass die Interpretationen || ||' und || || nur im Falle der Interpretation der Gegenstandskonstanten a voneinander abweichen können, sonst aber identisch sind. Das heißt für alle t TERM, mit t ≠ a, gilt: || t ||' = || t ||.

Anmerkung 4.3.2 Diese Formalisierung ist adäquat:

1. Haben alle Objekte aus U die mit P bezeichnete Eigenschaft — || ||' und || || unterscheiden sich nicht hinsichtlich der Interpretation von p —, dann gilt sicherlich || P ( a ) || = 1, unabhängig davon, welches Objekt a bezeichnet. Dann gilt aber für alle Interpretationen, mit || ||' || ||: || P ( a ) ||' = 1.

2. Gibt es umgekehrt ein Objekt c U, das die mit P bezeichnete Eigenschaft nicht besitzt, dann existiert eine Interpretation || ||', so dass || a ||' = c und also || P ( a ) ||' = 0. Dann gilt aber für nicht für alle Interpretationen || ||' mit || ||' = || ||: || P ( a ) ||' = 1, so dass auch gilt: || x P ( x ) || = 0 (Tertium non datur).

Wir wollen nun definieren, was unter der Semantik der Prädikatenlogik zu verstehen ist. Die Semantik der Prädikatenlogik wird relativ zu einer Struktur

M = < U, R1, ..., Rn, f1, ..., fm, c1, ..., ck >

erklärt, wobei wir wieder die Interpretationsfunktion || ||M zur Bestimmung der Bedeutung eines prädikatenlogischen Satzes einführen werden. Die Interpretationsfunktion weist nun den Index M auf, um die Abhängigkeit der Interpretation von der Wahl der Strukur M anzuzeigen. Zunächst müssen wir angeben, wie Termausdrücke zu interpretieren sind:

Definition 4.3.1 Die Interpretationsfunktion || ||M ist für Terme wie folgt definiert:

1. t GK { c1, ..., ck } || t ||M U,

2. sei f FK und t = f ( t1, ..., th ), dann ist || t || M = || f ||M ( t1 ||M, ..., | | th ||M ) U,

3. für alle R PK ist || R ||M Pot ( Un ), falls R ein n-stelliges Prädikat ist.

Wir erweitern nun || ||M auf Elemente der Menge PRAED:

Definition 4.3.2 Eine Interpretation von PRAED über dem nicht-leeren Universum U ist gegeben durch || ||M, wobei gilt:

1. || ( ti = tj ||M = 1 iff || ti ||M = || tj ||M,

2. || R ( ti, ..., tn ) ||M = 1 iff < || t1 ||M, ..., || tn ||M > || R ||M,

3. Die Semantik der Funktoren , , ¬ und wird genauso wie in der Aussagenlogik definiert.

4. || x A [ x ] ||M = 1 iff für alle Interpretationen || ||M', mit || ||M' || ||M, gilt: || A [ a ] ||M'

= 1, wobei a GK eine Gegenstandskonstante ist, die in A [ x ] nicht vorkommt.

Anmerkung 4.3.3 Die Bedingung (4) aus Definition 4.3.2 ist wesentlich. Sie besagt, dass der Satz " x A [ x ] ", A [ x ] ist ein Satzschema, wahr ist, falls die mit " A [ x ] " bezeichnete Relation auf jedes Individuum des betrachteten Universums U zutrifft. Die Bedingung, dass die Gegenstandskonstante a dabei nicht in " A [ x ] " vorkommen darf ist aber unabdingbar. Der Satz " x F ( x, a ) " ist wahr, wenn der Satz " F ( a', a ) " wahr ist, unabhängig davon, für welches Individuum aus U a ' steht. Dies gilt aber nicht für den Satz F ( a, a ), unabhängig davon, welches Individuum a bezeichnet. Falls " F " z. B. die Relation " x wählt y " bezeichnet, dann kann " x F ( x, a ) " gelesen werden als " Es gibt ein Individuum namens a, das alle wählen. " Würde nun die Existenzbedingung für || ||' derart, dass || ||M' || ||M, wobei a nicht in dem zu interpretierenden Ausdruck vorkommen darf, aufgegeben, so müsste auch die Interpretation || F ( a, a ) ||M', mit || a ||M ≠ || a ||M, wahr sein. Es kann aber nicht angenommen werden, dass jeder sich selbst wählt.

Anmerkung 4.3.4 Die Einschränkung der Interpretationsfunktion || ||M auf Elemente p, q SENT gemäß Definition 4.3.2 ist eine Funktion, mit || ||M : SENT .

Die Begriffe der Tautologie, Erfüllbarkeit, Kontradiktion und Äquivalenz von Sätzen aus PRAED werden analog zu den korrespondierenden Begriffen der Aussagenlogik eingeführt. Insbesondere gilt also:

Definition 4.3.3 Der semantische Ableitungsoperator " ": Für alle p, q PRAED gilt:

p q iff ( || p || = 1 ) ( || q || = 1 )

Anmerkung 4.3.5 Jeder aussagenlogisch wahre Satz ist gleichermaßen prädikatenlogisch wahr, da die Definition der prädikatenlogischen Interpretationsfunktion die Bestimmungen für aussagenlogische Bewertungen umfasst. Das Umgekehrte muss natürlich nicht gelten. Die selbe Überlegung gilt für aussagenlogisch gültige Schlüsse. Die Prädikatenlogik "enthält" also die Aussagenlogik.

Definition 4.3.4 Sei M = < U, R1, ..., Rn, f1, ..., fm, c1, ..., ck > eine Struktur und seien p SENT, P SENT. Sei ferner || ||M eine Interpretation von PRAED über dem Universum U. Dann gilt:

1. M p iff || p ||M = 1.

2. M P iff für alle p P gilt: M p.

3. p M q iff M p M q.

4. p iff jedes zu p passende Modell p wahr macht. Ein Modell M heißt passend zu p PRAED iff || ||M für alle in p vorkommenden Prädikats-, Funktions- und Gegenstandskonstanten ebenso definiert ist wie für alle freien Variablen von p.

Falls M p, dann heißt M Modell von p.

Beispiel 4.3.2 Sei 0 die Menge der natürlichen Zahlen beginnend mit 0. Dann gilt:

< 0, +, 0 > ∀ x y ( f ( x, y ) = f ( y, x )),

falls || f || = +. Denn für alle || a ||, || b || N0 gilt: || f ( a, b ) = f ( b, a ), || = 1 iff || a || + || b || = || b || + || a ||.

Satz 4.3.1 Koinzidenztheorien: Sei || ||' || ||, ferner komme die Gegenstandskonstante a nicht in A vor, dann gilt: || A ||' = || A ||.

Beweis: Wir beweisen das Koinzidenztheorem induktiv über den Aufbau von A. Hierzu sei festgelegt, dass der Grad einer Formel A gleich der Anzahl von Symbolen aus { , , ¬, , } in A sei.

1. Induktionsanfang: Sei A vom Grade 0, sei also A ATOM, dann hängt die Interpretation von A aber nur von den in diesem Satz vorkommenden Gegenstands-, Funktions- und Prädikatskonstanten ab, für die aber annahmegemäß || ||' und || || die gleiche Interpretation liefern.

2. Induktionsschritt: Seien nun Formeln vom Grade n > 0 betrachtet, dann gilt das Theorem auch für Formeln vom Grade n. Denn es gilt:

Hat A die Gestalt ¬ p, p q oder p q, dann gilt nach Voraussetzung || p ||' = || p || bzw. || q ||' = || q ||, da diese Formeln von Grade n - 1 sind. Dann gilt aber auch || ¬ p ||' = || ¬ p ||, || p q ||' = || p q || bzw. || p q ||' = || p q ||, denn || ||' und || || erfüllen annahmegemäß die selben Interpretationsbedingungen für die Negation, Konjunktion und Disjunktion.

Hat nun A die Gestalt ∀ x B [ x ] und ist || ∀ x B [ ] || = 0, dann existiert eine Interpretation || ||i || || mit || B [ b ] ||i = 0, wobei b ≠ a und weder b noch a kommen in B [ x ] vor. M. a. W.: || ||i und || || stimmen bezogen auf die Interpretation von a überein.

Wenn wir nun aber eine Interpretation || || i' || ||' konstruieren, so dass || b ||i' = || b ||i, dann gilt erstens, dass || ||i' und || ||' bezogen auf die Interpretation von a übereinstimmen, und damit zweitens: || ||i' || ||i. Die Bedingung des Induktionsschrittes kann also auf letztere beiden Interpretationsfunktionen angewandt werden.

Insbesondere gilt dann aber: || B [ b ] ||i' = || B [ b ] ||i = 0, denn beide Ausdrücke sind vom Grade n - 1 und es gilt ja bereits || B [ b ]i = 0. Hieraus folgt aber, dass es eine Interpretation || ||i' || ||' gibt, so dass || B [ b ] || i' = 0 und somit || ∀ x B [ x ] || = 0.

Ganz analog verfährt man für den Fall, dass || ∀ x B [ x ] = 0. Da aber ein beliebiger prädikatenlogischer Satz für eine gegebene Interpretation entweder wahr oder falsch ist (Tertium non datur), ist es also nicht mehr nötig, die Fälle || ∀ x B [ x ] ||' = 1 bzw. || x B [ x ] || = 1 zu betrachten.

Das Koinzidenztheorem besagt intuitiv gesprochen, dass die Verschiedenheit der Interpretationen eines Satzes (d. h. etwa von || || und || ||') wesentlich von den Interpretationen der Konstanten des Satzes abhängt.

Ein zweites Theorem, das wir hier nicht beweisen wollen, lautet:

Satz 4.3.2 Überführungstheorem: Gilt || ||' || || und ferner || a' || = || b || (annahmegemäß gilt || b' || = || b ||, das heißt || ||' ordnet a und b denselben Wert zu wie || || der Konstanten b), dann gilt für alle Sätze x A [ x ], in denen die Gegenstandskonstante a nicht vorkommt, || A [ a ] ||' = || A [ b ] || ( = || A [ b ] ||').

Mit anderen Worten: || ||' verhält sich wie || ||, nur im Falle von a existiert u. U. eine Abweichung beider Interpretationen, wobei hier || a ||' = || b || gilt. Mit diesen beiden Theoremen können wir nun folgende zwei Sätze beweisen:

Satz 4.3.3 Alle Sätze der Gestalt ∀ x a [ x ] A [ a ] sind prädikatenlogisch wahr, wobei a eine beliebige Gegenstandskonstante ist.

Beweis: Wenn wir zeigen, dass aus der Falschheit von ∀ A [ a ] die Falschheit von x A [ x ] folgt, dann kann letzterer Satz niemals wahr sein und der Satz A [ a ] zugleich falsch sein, womit der Satz bewiesen wäre.

Ist also || || eine beliebige Interpretation mit A [a ] = 0, so gilt, falls b eine beliebige Gegenstandskonstante ist, die in ∀ x A [ x ] nicht vorkommt, und || || eine Interpretation ist mit || ||' || || sowie || b ||' = || a || nach dem Überführungstheorem: || A [ b ] ||' = || A [ a ] = 0. Dann gibt es aber eine Interpretation || ||' || || mit || A [ b ] ||' = 0, so dass || ∀ x A [ x ] = 0.

Wir benötigen in letzterem Beweis das Überführungstheorem, da für || || nicht direkt die Richtigkeit eines quantifizierten Ausdrucks gezeigt werden kann, sondern nur über eine unendliche Menge von Interpretationen mit genannter Eigenschaft, also insbesondere auch über || ||'. || ||' ist aber so konstruiert, dass diese Interpretation in den Vordersatz ∀ x A [ x ] gerade das einsetzt, was die Konklusion A [ a ] falsch macht.

Satz 4.3.4 Ist A B [ a ] ein prädikatenlogisch wahrer Satz, das heißt eine Tautologie, so auch A x B [ x ], sofern die Gegenstandskonstante a in letzterem Satz nicht vorkommt.

Wir bemerken zunächst; A B [ a ] ist eine Tautologie, falls jede Interpretation diesen Satz erfüllt. Die ist genau dann der Fall, wenn jede Interpretation, die A erfüllt, auch B [ a ] erfüllt. Mit diesen Überlegungen haben wir das nötige Rüstzeug für den Beweis dieses Satzes.

Beweis: Falls der Satz A x B [ x ] prädikatenlogisch nicht wahr ist, so gibt es eine Interpretation || ||, die A erfüllt, aber nicht ∀ x B [ x ]. Es gibt dann aber eine Interpretation || ||' = || || (a kommt annahmegemäß nicht in A x B [ x ] vor), für die gilt || B [ a ] || = 0. Nach dem Koinzidenztheorem gilt aber || A' || = || A || = 1, da a annahmegemäß nicht in A vorkommt. Dann ist aber || ||' eine Interpretation, die A nicht erfüllt, im Gegensatz zur Annahme, dieser Satz sei eine Tautologie.

Letzterer Satz besagt also, dass A B [ a ] im Prinzip genau dasselbe ausdrückt, wie A x B [ x ], falls A B [ a ] eine Tautologie ist. Die Forderung, dass A B [ x ] eine Tautologie ist, ist aber unabdingbar, genauso wie die Forderung p q, falls man q in einem Schritt aus p mit Hilfe des MP ableiten will. Natürlich gilt aber nicht für jeden beliebigen Satz p q zugleich p q.

Wir benötigen letztere beiden Sätze, um im folgenden die Prädikatenlogik kalkülisieren zu können.

 

4.4 Syntaktische Ableitungen zurück

In der Aussagenlogik haben wir mit der Methode der Wahrheitstabellen ein Entscheidungsverfahren für die Frage der Gültigkeit aussagenlogischer Formeln kennen gelernt. Für die PL existiert ein derart einfaches Verfahren nicht. Wir sind also ganz auf die Kalkülisierung der PL angewiesen. Den im folgenden vorzustellenden Kalkül nennen wir L. Er umfasst folgende Axiome und Ableitungsregeln:

Definition 4.4.1 Die Menge AXIOM der Axiome der Prädikatenlogik enthält die folgenden Formeln aus SENT:

1. p ( q p ),

2. ( p ( q r )) (( p q ) ( p r )),

3. ( ¬ p ¬ q ) ( q p ),

4. x A [ x ] A [ a ].

Anmerkung 4.4.1 Die ersten drei Axiome wiederholen exakt die Axiome aus Anmerkung 3.2.3. M. a. W.: Sämtliche in Definition 3.2.1 aufgeführten Axiome der Aussagenlogik gelten in gleicher Weise für die Prädikatenlogik.

Definition 4.4.2 Im Kalkül L können zwei Deduktionsregeln verwendet werden:

1. MP ( siehe Definition 3.2.2 ),

2. R2: Seien A B [ a ], A ∀ x B [ x ] SENT, dann gilt — falls a GK eine Gegenstandskonstante ist, die in dem Satz A x B [ x ] nicht vorkommt —:

Anmerkung 4.4.2 Die in der PL zum MP hinzutretende Deduktionsregel ist selbstverständlich so zu lesen, dass nur bei Geltung des Satzes A B [ a ] in der genannten Weise geschlossen werden darf, falls also A B [ a ] selbst ein Axiom ist oder aber aus der Anwendung einer Schlussregel auf eine Folge von Sätzen resultiert, für die genau die selbe Existenzbedingung gilt. Man nennt diese Deduktionsregel auch die Regel der "hinteren Generalisierung": Sie erlaubt unter den genannten Bedingungen die Einführung des Allquantors im Hintersatz einer Implikation. Wir werden im folgenden diese Regel mit R2 bezeichnen.

Wir beachten weiter, dass der Satz A x B [ x ] aus dem Satz A B [ a ] hervorgeht, indem zunächst die Konstante a durch die Variable x ersetzt wird. Hierauf folgend wird die Variable x durch den Allquantor quantifiziert. Dieser Ersetzungsprozess ist aber nur dann zulässig, falls die Bedingung 3 aus Definition 4.2.3 erfüllt ist, falls also x eine Gegenstandsvariable ist, die in dem Satz A B [ a ] nicht vorkommt. Andernfalls würde der Ausdruck A x B [ x ] keine wohlgeformte prädikatenlogische Formel darstellen. Der gesamte Ausdruck A B [ a ] entspricht dem Satzschema A [a ], so wie es in der genannten Bedingung aufgeführt wird. Da es unendlich viele Gegenstandvariablen geben soll, kann diese Bedingung immer erfüllt werden.

Wir benutzen wieder den Ableitungsoperator , um zu signalisieren, dass eine gegebene Formel prädikatenlogisch ableitbar ist.

Beispiel 4.4.1 Es gilt:

x A [ x ] y A [ y ]

Denn:

1. Axiom (4): ∀ x A [ x ] A [ a ],

2. R2 aus 1: ∀ x A [ x ] y A [ y ].

Beispiel 4.4.2 Es gilt:

A [ a ] x A [ x ],

wobei a in x A [ x ] nicht vorkommt. Denn:

1. Annahmeformel: A [ a ];

2. Axiom (1): A [ a ] (( p p ) A [ a ] ) (a soll in p nicht vorkommen),

3. MP aus 1 und 2: ( p p ) A [ a ],

4. R2 aus 3: ( p p ) x A [ x ],

5. aussagenlogisches Axiom: p p,

6. MP aus 4 und 5: x A [ x ].

In der PL gilt das Deduktionstheorem nicht mit der Allgemeinheit wie in der Aussagenlogik. Betrachten wir eine Interpretation über der Menge { 0, 1 }. Sei || || eine Interpretation mit | < a || = 0, || a' || = 1 sowie || F || = {< 0 >}. Es gilt dann || F ( a ) || = 1, hingegen gilt: || ∀ x F ( x ) || = 0, denn es existiert eine Interpretation || ||' || || mit || b ||' = 1 und somit || F ( b ) ||' = 0. Dann ist aber auch || F ( a ) x F ( x ) || = 0, während F ( a ) x F ( x ) sehr wohl, wie gesehen, ableitbar ist. Wir haben also folgendes, eingeschränktes Deduktionstheorem:

Satz 4.4.1 Falls P { p } q im Kalkül L beweisbar ist, dann auch P p q, sofern innerhalb der Annahmeformel p keine Gegenstandskonstante eliminiert wird. M. a. W. gilt unter der genannten Bedingung:

P { p } q iff P p q

Satz 4.4.2 Der Kalkül L der Prädikatenlogik ist widerspruchsfrei und vollständig.

Beweis: Zur Widerspruchsfreiheit: Die Widerspruchsfreiheit der Axiome (1) bis (3) wurde bereits gezeigt. Axiom (a) ist mit Theorem 4.3.3 identisch, welches wir bereits bewiesen haben. Die Widerspruchsfreiheit des MP wurde ebenfalls schon für die Aussagenlogik gezeigt. Die Regel R2 entspricht wiederum Theorem 4.3.4, welches wir gleichermaßen bereits nachgewiesen haben.

 
4.5 Normalformen zurück

Genauso wie in der Aussagenlogik lassen sich auch in der PL Normalformen von Sätzen dieser Sprache bilden. Die Bildung einer Normalform bedarf der Anwendung einer Reihe von Äquivalenzen. Für die hier besprochenen Normalformen werden dies vor allem die folgenden Äquivalenzen sein:

Satz 4.5.1 Seien p, q PRAED beliebige Formeln. Dann gilt:

1. ¬ x p ≡ x ¬ p,

¬ x p ≡ x ¬ p.

Falls x in q nicht frei (also ungebunden) vorkommt, dann gilt:

2. ( x p q ) ≡ x ( p q ),

( x p q ) ≡ x ( p q ),

( x p q ) ≡ x ( p q ),

( x p q ) ≡ x ( p q ),

3. ( x p x q ) ≡ x ( p q ),

( x p x q ) ≡ x ( p q ),

4. x y p ≡ y x p,

x y p ≡ y x p.

Es gilt aber:

( x A [ x ] x B [ x ] )     x ( A [ x ] B [ x ] ),

( x A [ x ] x B [ x ] )      x ( A [ x ] B [ x ] ),

Denn falls A das Prädikat "männlich" und B das Prädikat "weiblich" symbolisiert, und falls ferner als Referenzuniversum alle derzeit lebenden Menschen gewählt werden, dann lassen sich leicht Beispiele für das Behauptete konstruieren.

Die Äquivalenzen aus Satz 4.5.1 "treiben" gewissermaßen, von links nach rechts angewandt, die Quantoren einer Formel nach "außen". Die Quantorenreihenfolge der Zielformel hängt dabei entscheidend von der Reihenfolge der Anwendung der Regeln ab. Sie ist also nicht eindeutig. Gleichartige Quantoren können aber immer vertauscht werden. Um die unter Punkt 2 der Satzes 4.5.1 genannten Äquivalenzen anwenden zu können, bedürfen wir unter Umständen der Möglichkeit einer Umbenennung von Variablen:

Definition 4.5.1 Sei eine Formel p PRAED gegeben, ferner sei x eine Variable und t ein Term. p [ x / t ] bezeichnet dann diejenige Formel, die man aus p erhält, indem jedes freie Vorkommen der Variablen x in p durch t ersetzt wird. [ x / t ] ist dann eine Substitution. Substitutionen können konkateniert werden. Die Folge [ x / t1 ] [ y / t 2 ] symbolisiert diejenige Substitution, die in einer Formel jedes freie Vorkommen von x durch t1 und dann jedes freie Vorkommen von y durch t2 ersetzt, wobei t1 auch y enthalten darf.

Über die Ersetzung freier Variablen hinaus ist auch eine "gebundene Umbenennung" möglich. Falls nämlich F = Q x G eine Formel ist, wobei Q { , }, und y eine Variable ist, die in G nicht vorkommt, dann ist F ≡ Q y G [ x / y ].

Satz 4.5.2 Eine Formel ist in Pränex-Normalform, falls sie von der Gestalt

Q1 x1 Q2 x2 ... Qn xn A

ist, wobei Q { , }, n ≥ 0, und xi GV für alle i { 0, ..., n }. Ferner kommt kein Quantor in A vor.

Anmerkung 4.5.1 Die Pränex-Normalform läßt sich wieder algorithmisch herleiten. Hier die einzelnen Schritte:

1. Eliminierung von und .

2. Anwendung von ¬ ¬ p ≡ p sowie der de Morganschen Gesetze, falls nötig (falls also ein Negator in das Innere einer Formel zu bringen ist).

3. Substitution / Umbenennung von Variablen, falls nötig.

4. Verwendung der Äquivalenzen aus Satz 4.5.1.

Beispiel 4.5.1

x y ( z ( P ( x, z ) P ( y, z )) q Q ( x, y, u )) ≡ x y ( ¬ z ( P ( x, z ) P ( y, z )) u Q ( x, y, u ))

                                                                                            ≡ ∀ x y ( z ( ¬ P ( x, z ) ¬ P ( y, z )) u Q ( x, y, u ))

                                                                                            ≡ ∀ x y z u ( ¬ P ( x, z ) ¬ P ( y, z ) Q ( x, y, u ))

Für die Einführung der Skolem-Normalform benötigen wir noch folgende Definition:

Definition 4.5.2 Eine Formel heißt bereinigt, falls keine Variable in dieser Formel gebunden als auch ungebunden vorkommt und weiterhin keine zwei Quantoren innerhalb der Formel dieselbe Variable quantifizieren.

Es läßt sich zeigen, dass es zu jeder Formel eine äquivalente Formel in bereinigter Form gibt. Man hat nun die Definition

Definition 4.5.3 Zu jeder prädikatenlogischen Formel p in Pränex-Normalform erhält man eine ihr zugehörige Formel in Skolem-Normalform (SNF) als das des folgenden Algorithmus:

while p enthält eine Existenzquantor do

begin

p habe die Form p = ∀ y1, y2 ... yn x q für eine Formel in bereinigter Pränex-Normalform. Sei ferner n ≥ 0, das heißt der Allquantorenblock kann auch leer sein. Sei f ein in p nicht vorkommendes n-stelliges Funktionssymbol. Man substituiert dann:

p =def y1 y2 ... y n q [ x / f ( y1, ..., yn)].

M. a. W.: Der Existenzquantor wird aus p herausgestrichen und jedes Vorkommen von x in p wird durch den Ausdruck f ( y1, ..., yn ) ersetzt, dessen Variablen allesamt durch Allquantoren gebunden sind.

end

Satz 4.5.3 Für jede prädikatenlogische Formel p gilt: p ist erfüllbar iff die p entsprechende Skolem-Formel erfüllbar ist.

Beweisidee: Der Algorithmus letzterer Definition ersetzt systematisch jedes Vorkommen eines Existenzquantors in p. Hierbei erhält man durch jeden dieser Schritte eine Formel, die wir p' nennen wollen. Für jede solche Formel p' zeigt man allgemein, dass gilt: p ist erfüllbar iff p' erfüllbar ist. Dies erreicht man im wesentlichen dadurch, dass man für die Funktion || f || über dem Referenzuniversum festlegt, dass || f || ( u1, ..., un = v, mit || yj || = uj für j { 1, ..., n }. v ist gerade dasjenige Element des Referenzuniversums, das annahmegemäß die Existenzquantorfizierung erfüllt.

Letzterer Satz besagt also, dass die Erfüllbarkeitseigenschaft einer Formel gleichermaßen an der ihr entsprechenden Formel in SNF beobachtet werden kann.

Wir wollen nun von einer beliebigen prädikatenlogischen Formel p ausgehen (eventuell auch mit Vorkommen freier Variablen) und die Schritte betrachten, die diese durchlaufen muss, um zu ihrer SNF zu gelangen:

1. Bereinige p durch systematisches Umbenennen gebundener Variablen (Voraussetzung für die spätere Voranstellung von Quantoren). Es entsteht die Formel p1.

2. Seien y1 ... yn die in p vorkommenden freien Variablen. Ersetze p1 durch p2 = y1 ... y n p1. p2 ist dann erfüllbarkeitsäquivalent zu p1 und enthält keine freien Variablen mehr.

3. Bestimme zu p2 eine äquivalente (und damit auch erfüllbarkeitsäquivalente) Formel p3 in Pränex-Normalform.

4. Eliminiere alle Existenzquantoren in p3: Bestimmung der zugehörigen Formel p4 in SNF, die erfüllbarkeitsäquivalent zu p3 und damit auch zu p ist.

5. Überführe die Matrix von p4 (d. h. den hinteren Teil von p4 ohne Quantoren-Vordersatz) in KNF.

Beispiel 4.5.2 Sei

p = [ ¬ x ( p ( x, z ) y Q ( x, f ( y ))) y P ( g ( z, y ), z ) ]

p ist nicht bereinigt: y wird an zwei verschiedenen Stellen gebunden. Also: Substitution von y durch w im zweiten Disjunktionsglied:

p1 = [ ¬ x ( P ( x, z ) y Q ( x, f ( y ))) w P ( g ( z, w ), z ) ]

Die Variable z kommt in p1 frei vor. Also bildet man:

p2 = z [ ¬ x ( P ( x, z ) y Q ( x, f ( y ))) w P ( g ( z, w ), z ) ]

Umformen in Pränex-NF liefert:

p3 = z x y w [ ( ¬ P ( x, z ) ¬ Q ( x, f ( y ))) P ( g ( z, w ), z ) ]

Wir erhalten nun eine zu p3 korrespondierende Formel in SNF, indem wir eine nullstellige Funktion a (das heißt eine Gegenstandskonstante) für z sowie h ( x ) für y substituieren:

p4 x w [ ( ¬ P ( x, a ) ¬ Q ( x, f ( h ( x )))) P ( g ( a, w ) , a )) ]

p5 = x w [ ( ¬ P ( x, a ) P ( g ( a, w ), a )) ( ¬ Q ( x, f ( h ( x ))) P ( g ( a, w ), a )) ]

Die Formel p5 läßt sich, wie wir sehen werden, unmittelbar in die sog. Klauselform übertragen, die für die Resolution unabdingbar ist.