Kurs:Einführung in die mathematische Logik (Osnabrück 2021)/Vorlesung 10



Ableitungskalkül der Prädikatenlogik

Gegeben sei ein Symbolalphabet einer Sprache erster Stufe und damit die zugehörige Termmenge und die zugehörige Ausdrucksmenge . Wir möchten die logisch wahren Aussagen einer solchen Sprache syntaktisch charakterisieren. Mathematische Aussagen sind im Allgemeinen „wenn-dann“-Aussagen, d.h. sie behaupten, dass, wenn gewisse Voraussetzungen erfüllt sind, dann auch eine gewisse Folgerung erfüllt ist.

Wenn man einen Beweis eines Satzes der Gruppentheorie oder der elementaren Arithmetik entwirft, so sind dabei die Axiome der Gruppentheorie bzw. die Peano-Axiome stets präsent. Wenn die Gruppenaxiome bezeichnen und die Aussage, dass das inverse Element eindeutig bestimmt ist, bezeichnet, so folgt aus . Mit der Folgerungsbeziehung kann man dies als

formulieren. Dies kann man auch so ausdrücken, dass

allgemeingültig ist, also dass

gilt. So kann man jede Folgerung aus einer endlichen Ausdrucksmenge „internalisieren“, also durch einen allgemeingültigen Ausdruck der Form

wiedergegeben, wobei vorne die Ausdrücke aus konjugiert werden. Die Folgerungsbeziehung (zumindest aus endlichen Ausdrucksmengen) kann also vollständig durch allgemeingültige Ausdrücke verstanden werden.

Wir besprechen nun die syntaktische Variante der allgemeingültigen Ausdrücke, nämlich die syntaktischen prädikatenlogischen Tautologien. Über den soeben besprochenen Zusammenhang ergibt sich daraus auch ein Ableitungskalkül, der das syntaktische Analogon zur Folgerungsbeziehung ist. Da wir Ausdrücke der Form als Grundtyp für eine mathematische Aussage ansehen, arbeiten wir allein mit den Junktoren und lesen und als Abkürzungen. Man könnte auch noch bzw. eliminieren und durch die verbleibenden beiden Junktoren ausdrücken, doch würde dies zu recht unleserlichen Formulierungen führen.

Der prädikatenlogische Kalkül, den wir vorstellen wollen, soll es erlauben, „alle“ prädikatenlogischen allgemeingültigen Ausdrücke formal abzuleiten. Der Aufbau dieses Kalküls geschieht (wie für den Ableitungskalkül der Aussagenlogik) rekursiv (und für beliebige Symbolalphabete gleichzeitig). D.h. man hat eine Reihe von Anfangstautologien (oder Grundtautologien) und gewisse Schlussregeln, um aus schon nachgewiesenen Tautologien neue zu produzieren. Sowohl die Anfangstautologien als auch die Schlussregeln sind aus der mathematischen Beweispraxis vertraut.

Zur Formulierung dieses Kalküls verwenden wir die Schreibweise
Sie bedeutet, dass der Ausdruck in der Prädikatenlogik

(erster Stufe zu einem gegebenen Alphabet) ableitbar ist, also eine Tautologie (im syntaktischen Sinne) ist. Wir beschreiben nun rekursiv die syntaktischen Tautologien in der Prädikatenlogik, die sich in aussagenlogische Tautologien, Gleichheitstautologien und Quantorentautologien und zwei Ableitungsregeln untergliedern. Wir beginnen mit den schon bekannten, allerdings in einer anderen Sprache formulierten aussagenlogischen Tautologien.


Axiom  

Zu einem beliebigen Symbolalphabet und beliebige Ausdrücke legt man folgende (syntaktische) Tautologien axiomatisch fest.

  1. und

Als (erste) Schlussregel erlaubt man wieder den Modus Ponens, so dass die Prädikatenlogik in einem gewissen Sinne die Aussagenlogik umfasst. Die Einschränkung in dieser Formulierung beruht darauf, dass es in der Sprache der Prädikatenlogik keine Aussagenvariablen gibt. Man kann sich vorstellen, dass die oben angeführten Tautologien aus den entsprechenden aussagenlogischen (in Aussagenvariablen formulierten) Tautologien entstehen, indem man für die Aussagenvariablen beliebige prädikatenlogische Ausdrücke einsetzt. Dies führt zu folgendem Einsetzungsprinzip. Wir schreiben , wenn in einem aussagenlogischen Ausdruck die darin vorkommenden Aussagenvariablen durch prädikatenlogische Ausdrücke ersetzt werden (diese Ersetzung ist deutlich einfacher als die Ersetzung von Variablen durch Terme.)



Lemma  

Es sei eine in den Aussagenvariablen formulierte aussagenlogische Tautologie und es seien prädikatenlogische Ausdrücke über einem Symbolalphabet .

Dann ist auch der prädikatenlogische Ausdruck , der entsteht, wenn man in jedes Auftreten der Aussagenvariablen durch ersetzt, eine prädikatenlogische Tautologie.

Beweis  

Wir führen Induktion über den Aufbau der aussagenlogischen Tautologien. Es sei eines der aussagenlogischen Axiome in den Ausdrücken und es seien die darin auftretenden Aussagenvariablen. Wir schreiben die zugrunde liegende aussagenlogische Tautologie in den Aussagenvariablen und nennen diese . Dann ist

Somit ist insgesamt

D.h. entsteht durch Einsetzung von prädikatenlogischen Ausdrücken in eine Basistautologie und gehört somit zu den in Axiom 10.1 gelisteten Tautologien. Es sei nun eine aussagenlogische Tautologie, die durch Modens ponens erhalten wird. Dann gibt es also eine aussagenlogische Tautologie und ist ebenfalls eine aussagenlogische Tautologie. Nach Induktionsvoraussetzung sind dann und prädikatenlogische Tautologien. Da der Modus ponens eine erlaubte Schlussregel in der Prädikatenlogik ist, folgt, dass eine prädikatenlogische Tautologie ist.



Beispiel  

Wir betrachten die aussagenlogische Tautologie der Form

mit

also, angelehnt an Lemma 10.2,

In diese aussagenlogische Tautologie soll

ersetzt werden. Das ergibt die prädikatenlogische Tautologie


Im Laufe der Einführung der prädikatenlogischen Tautologien und der zugehörigen Schlussregeln werden wir sogleich die Korrektheit feststellen, d.h., dass es sich auch um allgemeingültige Ausdrücke (semantische Tautologien) handelt. Für die aussagenlogischen Tautologien wurde die Korrektheit für aussagenlogische Modelle schon gezeigt, eine einfache Variante davon liefert die Korrektheit innerhalb von prädikatenlogischen Modellen.


Lemma  

Jede aussagenlogische Tautologie im Sinne von Axiom 10.1 ist

allgemeingültig in der Prädikatenlogik.

Beweis  

Es sei eine Interpretation von und eine aussagenlogische Grundtautologie in den prädikatenlogischen Ausdrücken . Dann ist der Wahrheitswert von in nur abhängig von den Wahrheitswerten von in und den Junktoren in . Da es sich um eine aussagenlogische Tautologie handelt und die Wahrheitsvorschrift für die Junktoren in einem prädikatenlogischen Modell mit der in einem aussagenlogischen Modell übereinstimmt, besitzt den Wahrheitswert . Also ist allgemeingültig.


Da allgemeingültige Aussagen unter Modus ponens abgeschlossen sind, folgt daraus, dass generell alle prädikatenlogisch formulierten aussagenlogischen Tautologien allgemeingültig sind.



Gleichheitstautologien

In der Prädikatenlogik gelten die beiden folgenden Tautologien für die Gleichheit.


Axiom  

Es sei ein Symbolalphabet, seien - Terme und sei ein - Ausdruck. Dann sind die beiden folgenden Ausdrücke syntaktische Tautologien.

Diese beiden Axiome (oder genauer Axiomenschemata) heißen Gleichheitsaxiom und Substitutionsaxiom. Mit einer aussagenlogischen Umformulierung sieht man, dass das Substitutionsaxiom äquivalent zu

ist.



Lemma  

Beweis  

Es sei eine beliebige - Interpretation. (1). Aufgrund der Bedeutung des Gleichheitszeichens unter jeder Interpretation gilt , also


(2). Es gelte

also und . Das bedeutet einerseits . Andererseits gilt nach dem Substitutionslemma

Wegen der Termgleichheit gilt somit auch

und daher, wiederum aufgrund des Substitutionslemmas, auch



Bei leerer Variablenmenge ist das Substitutionsaxiom aussagelos. In Hinblick auf Lemma 10.7 fordern wir, dass die Variablenmenge stets unendlich ist.


Lemma  

Aus den Gleichheitsaxiomen lassen sich folgende Gleichheitstautologien ableiten (dabei sind Terme, ein -stelliges Funktionssymbol und ein -stelliges Relationssymbol).

Beweis  

(1). Aufgrund der Gleichheitsaxiome haben wir

und

wobei eine Variable sei, die weder in noch in vorkomme. Daher sind die beiden substituierten Ausdrücke gleich bzw. . Eine aussagenlogische Umstellung der zweiten Zeile ist

so dass sich aus der ersten Zeile mittels Modus ponens

ergibt.
(2). Es sei wieder eine Variable, die weder in noch in noch in vorkomme. Eine Anwendung des Substitutionsaxioms liefert

Nach Einsetzen und einer aussagenlogischen Umstellung ist dies die Behauptung.
Für (3) siehe Aufgabe 10.5.
(4). Es sei eine Variable, die weder in einem der noch in einem der vorkommt. Für jedes gilt nach Axiom 10.5  (2) (mit ) dann

also

Diese Ableitbarkeiten gelten auch, wenn man die Vordersätze durch ihre Konjunktion

ersetzt. Durch die Transitivität der Implikation ergibt sich daher



<< | Kurs:Einführung in die mathematische Logik (Osnabrück 2021) | >>

PDF-Version dieser Vorlesung

Arbeitsblatt zur Vorlesung (PDF)