© 1999 Franšois Bry
Dieses Lehrmaterial wird ausschlie▀lich zur privaten Verwendung angeboten. Eine nichtprivate Nutzung (z.B. im Unterricht oder eine Ver÷ffentlichung von Kopien oder ▄bersetzungen) dieses Lehrmaterials bedarf der Erlaubnis des Autors.


2.10 Exkurs: Prädikatenlogik zweiter Stufe

In der Prädikatenlogik erster Stufe beziehen sich Quantoren auf Objekte. Manche Aussagen, zum Beispiel in der Mathematik, quantifizieren aber nicht nur über Objekte, sondern über Eigenschaften von Objekten. Ein Beispiel dafür stellt der Satz 2.1.4 (Prinzip der strukturellen Induktion für aussagenlogische Formeln) dar:

Andere Beispiele dieser Art sind
Derartige Aussagen lassen sich nicht in der Prädikatenlogik erster Stufe formulieren. Dort werden Eigenschaften von Objekten und Beziehungen zwischen Objekten durch Relationssymbole repräsentiert. Rein syntaktisch kann aber an der Stelle eines Relationssymbols in einer Formel nie eine Variable stehen, und Quantoren kommen nur in Verbindung mit Variablen vor.

Die Prädikatenlogik zweiter Stufe (PL2S) ist eine Erweiterung der PL1S um Relations- und Funktionsvariablen, mit denen Quantifizierungen der obigen Art möglich sind. Damit ist die Prädikatenlogik zweiter Stufe ausdrucksstärker als die Prädikatenlogik erster Stufe.

Gegeben seien Mengen von Funktions- und von Relationsvariablen wie folgt. Die bisherigen Variablen entsprechen den nullstelligen Funktionsvariablen. Sprache [PL2S]

Definition 2.10.1 (Sprache [PL2S])
Eine Sprache der Prädikatenlogik zweiter Stufe ist gegeben durch ihre Signatur. Zusätzlich gehören zu die logischen Symbole der Prädikatenlogik zweiter Stufe.
Alle erwähnten Mengen sind abzählbar (üblicherweise sogar aufzählbar) und paarweise disjunkt, und kein Symbol einer dieser Mengen besteht aus einer Sequenz von Symbolen, in der ein Symbol aus einer der anderen Mengen vorkommt.
Es wird vorausgesetzt, dass mindestens eine Konstante enthält.

Terme werden ähnlich wie für eine Sprache der Prädikatenlogik erster Stufe definiert. Der einzige Unterschied ist, dass auch Funktionsvariablen anstelle von Funktionssymbolen zum Termaufbau verwendet werden können.

Definition 2.10.2 (Term [PL2S])
Sei eine Sprache der Prädikatenlogik zweiter Stufe. Die Menge der -Terme, kurz Terme, ist die kleinste Menge, die die folgenden Bedingungen erfüllt:
  1. Jede nullstellige Funktionsvariable von ist ein -Term.
  2. Jede Konstante von ist ein -Term.
  3. Sind t1,...tn -Terme, n ≥ 1, und ist f ein n-stelliges Funktionssymbol von oder eine n-stellige Funktionsvariable von , so ist auch f(t1,...tn) ein -Term.

Bei den Formeln ist der Aufbau ebenfalls analog zur PL1S. Die Unterschiede sind zum einen, dass auch Relationsvariablen anstelle von Relationssymbolen zum Aufbau von atomaren Formeln verwendet werden können, zum anderen, dass Quantoren auch mit Relations- und Funktionsvariablen erlaubt sind.

Definition 2.10.3 (Formel [PL2S])
Sei eine Sprache der Prädikatenlogik zweiter Stufe.

Die Eindeutigkeitssätze für Terme und Formeln gelten natürlich ebenfalls für Sprachen der Prädikatenlogik zweiter Stufe. Teilformeln und die Menge der in einem Term frei oder nicht frei vorkommenden Relationsvariablen und Funktionsvariablen werden ähnlich definiert wie für Sprachen der Aussagenlogik bzw. PL1S.

Das dritte der eingangs genannten Beispiele kann jetzt (mit vereinfachter Klammerung) folgendermaßen dargestellt werden.

¬∃X2(X2(a,b)
         ∧∀xy[X2(x,y) ⇒ X2(y,x)]
         ∧∀xy[X2(x,y) ∧ X2(y,x) ⇒ x y])

Bemerkung:  Es erscheint vielleicht naheliegend, anstelle der ausgeschriebenen Definitionen für symmetrisch und antisymmetrisch entsprechende Bezeichner einzuführen und etwa so zu definieren:

X2 (symmetrisch(X2) ⇔ ∀xy[X2(x,y) ⇒ X2(y,x)])

Das wäre aber keine Formel der PL2S, weil X2 kein Term und folglich symmetrisch(X2) keine Formel ist.

Die Logik ist bezüglich der Syntax erheblich strikter als zum Beispiel die Programmiersprache Prolog, deren Formalisierung zwar eigentlich nur auf einem Fragment der Prädikatenlogik erster Stufe beruht, die aber andererseits ähnliche Ausdrücke wie den obigen erlaubt, die über die Prädikatenlogik erster Stufe hinausgehen.

In dem unerlaubten Ausdruck symmetrisch(X2) steht symmetrisch für eine Relation über Relationen. Das ist erst in einer Sprache der dritten Stufe zugelassen. Sprachen höherer Stufen sind Sprachen, in denen Relationen über Relationen über Relationen usw. ausgedrückt werden können.

Validierung