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

Ableitungskalkül der Prädikatenlogik

Gegeben sei ein Symbolalphabet ${}S$ einer Sprache erster Stufe und damit die zugehörige Termmenge und die zugehörige Ausdrucksmenge ${}L^{S}$. 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 ${}\alpha _{1},\alpha _{2},\alpha _{3}$ die Gruppenaxiome bezeichnen und ${}\alpha$ die Aussage, dass das inverse Element eindeutig bestimmt ist, bezeichnet, so folgt ${}\alpha$ aus ${}\alpha _{1},\alpha _{2},\alpha _{3}$. Mit der Folgerungsbeziehung kann man dies als

$\{\alpha _{1},\alpha _{2},\alpha _{3}\}\vDash \alpha$

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

$\alpha _{1}\wedge \alpha _{2}\wedge \alpha _{3}\rightarrow \alpha$

allgemeingültig ist, also dass

$\vDash \alpha _{1}\wedge \alpha _{2}\wedge \alpha _{3}\rightarrow \alpha$

gilt. So kann man jede Folgerung ${}\Gamma \vDash \alpha$ aus einer endlichen Ausdrucksmenge ${}\Gamma$ „internalisieren“, also durch einen allgemeingültigen Ausdruck der Form

$\vDash \alpha _{1}\wedge \ldots \wedge \alpha _{n}\rightarrow \alpha$

wiedergegeben, wobei vorne die Ausdrücke aus ${}\Gamma$ 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 ${}\alpha _{1}\wedge \ldots \wedge \alpha _{n}\rightarrow \alpha$ als Grundtyp für eine mathematische Aussage ansehen, arbeiten wir allein mit den Junktoren ${}\neg ,\wedge ,\rightarrow$ und lesen ${}\vee$ und ${}\leftrightarrow$ als Abkürzungen. Man könnte auch noch ${}\wedge$ bzw. ${}\rightarrow$ 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

$\vdash \alpha .$

Sie bedeutet, dass der Ausdruck ${}\alpha$ 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 ${}S$ und beliebige Ausdrücke ${}\alpha ,\beta ,\gamma \in L^{S}$ legt man folgende (syntaktische) Tautologien axiomatisch fest.

1. $\vdash \alpha \rightarrow (\beta \rightarrow \alpha ).$

2. $\vdash (\alpha \rightarrow \beta )\wedge (\beta \rightarrow \gamma )\rightarrow (\alpha \rightarrow \gamma ).$

3. $\vdash (\alpha \rightarrow \beta )\wedge (\alpha \rightarrow \gamma )\rightarrow (\alpha \rightarrow \beta \wedge \gamma ).$

4. $\vdash (\alpha \wedge \beta \rightarrow \gamma )\rightarrow (\alpha \rightarrow (\beta \rightarrow \gamma ))$

   und

   $\vdash (\alpha \rightarrow (\beta \rightarrow \gamma ))\rightarrow (\alpha \wedge \beta \rightarrow \gamma ).$

5. $\vdash \alpha \wedge \neg \alpha \rightarrow \beta .$

6. $\vdash (\alpha \rightarrow \beta )\wedge (\neg \alpha \rightarrow \beta )\rightarrow \beta .$

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 ${}\varphi {\frac {\beta _{1},\ldots ,\beta _{n}}{p_{1},\ldots ,p_{n}}}$, wenn in einem aussagenlogischen Ausdruck ${}\varphi$ die darin vorkommenden Aussagenvariablen ${}p_{i}$ durch prädikatenlogische Ausdrücke ${}\beta _{i}$ ersetzt werden (diese Ersetzung ist deutlich einfacher als die Ersetzung von Variablen durch Terme.)

Lemma Lemma 10.2 ändern

Es sei ${}\varphi$ eine in den Aussagenvariablen ${}p_{1},\ldots ,p_{n}$ formulierte aussagenlogische Tautologie und es seien ${}\beta _{1},\ldots ,\beta _{n}\in L^{S}$ prädikatenlogische Ausdrücke über einem Symbolalphabet ${}S$.

Dann ist auch der prädikatenlogische Ausdruck ${}\varphi '$, der entsteht, wenn man in ${}\varphi$ jedes Auftreten der Aussagenvariablen ${}p_{i}$ durch ${}\beta _{i}$ ersetzt, eine prädikatenlogische Tautologie.

Beweis

Wir führen Induktion über den Aufbau der aussagenlogischen Tautologien. Es sei ${}\varphi$ eines der aussagenlogischen Axiome in den Ausdrücken ${}\alpha ,\beta ,\gamma$ und es seien ${}p_{1},\ldots ,p_{n}$ die darin auftretenden Aussagenvariablen. Wir schreiben die zugrunde liegende aussagenlogische Tautologie in den Aussagenvariablen ${}p,q,r$ und nennen diese ${}\psi$. Dann ist

${}\varphi =\psi {\frac {\alpha ,\beta ,\gamma }{p,\,\,\,q,\,\,\,r}}\,.$

Somit ist insgesamt

${}\varphi '=\varphi {\frac {\beta _{1},\ldots ,\beta _{n}}{p_{1},\ldots ,p_{n}}}=\psi {\frac {\alpha {\frac {\beta _{1},\ldots ,\beta _{n}}{p_{1},\ldots ,p_{n}}},\beta {\frac {\beta _{1},\ldots ,\beta _{n}}{p_{1},\ldots ,p_{n}}},\gamma {\frac {\beta _{1},\ldots ,\beta _{n}}{p_{1},\ldots ,p_{n}}}}{p,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,q,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,r}}\,.$

D.h. ${}\varphi '$ 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 ${}\varphi$ eine aussagenlogische Tautologie, die durch Modens ponens erhalten wird. Dann gibt es also eine aussagenlogische Tautologie ${}\psi$ und ${}\psi \rightarrow \varphi$ ist ebenfalls eine aussagenlogische Tautologie. Nach Induktionsvoraussetzung sind dann ${}\psi {\frac {\beta _{1},\ldots ,\beta _{n}}{p_{1},\ldots ,p_{n}}}$ und ${}{\left(\psi \rightarrow \varphi \right)}{\frac {\beta _{1},\ldots ,\beta _{n}}{p_{1},\ldots ,p_{n}}}=\psi {\frac {\beta _{1},\ldots ,\beta _{n}}{p_{1},\ldots ,p_{n}}}\rightarrow \varphi {\frac {\beta _{1},\ldots ,\beta _{n}}{p_{1},\ldots ,p_{n}}}$ prädikatenlogische Tautologien. Da der Modus ponens eine erlaubte Schlussregel in der Prädikatenlogik ist, folgt, dass ${}\varphi {\frac {\beta _{1},\ldots ,\beta _{n}}{p_{1},\ldots ,p_{n}}}$ eine prädikatenlogische Tautologie ist.

$\Box$

Beispiel Referenznummer erstellen

Wir betrachten die aussagenlogische Tautologie der Form

$\alpha \rightarrow {\left(\beta \rightarrow \alpha \right)}$

mit

$\alpha =p_{1}\wedge p_{2}\,\,{\text{ und }}\,\,\beta =p_{3}\rightarrow p_{4},$

also, angelehnt an Lemma 10.2,

${}\varphi ={\left(q\rightarrow {\left(r\rightarrow q\right)}\right)}{\frac {p_{1}\wedge p_{2},\,p_{3}\rightarrow p_{4}}{q,\,r}}={\left(p_{1}\wedge p_{2}\right)}\rightarrow {\left({\left(p_{3}\rightarrow p_{4}\right)}\rightarrow {\left(p_{1}\wedge p_{2}\right)}\right)}\,.$

In diese aussagenlogische Tautologie soll

$p_{1}{\text{ durch }}\beta _{1}:=Rxy,\,p_{2}{\text{ durch }}\beta _{2}:=\forall uu=c,\,p_{3}{\text{ durch }}\beta _{3}:=\exists y\forall xfxz=y,\,p_{4}{\text{ durch }}\beta _{4}:=\neg Pu,\,$

ersetzt werden. Das ergibt die prädikatenlogische Tautologie

${\left(Rxy\wedge \forall uu=c\right)}\rightarrow {\left({\left({\left(\exists y\forall xfxz=y\right)}\rightarrow \neg Pu\right)}\rightarrow {\left(Rxy\wedge \forall uu=c\right)}\right)}.$

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 Referenznummer erstellen

Jede aussagenlogische Tautologie im Sinne von Axiom 10.1 ist

allgemeingültig in der Prädikatenlogik.

Beweis

Es sei ${}I$ eine Interpretation von ${}L^{S}$ und ${}\varphi$ eine aussagenlogische Grundtautologie in den prädikatenlogischen Ausdrücken ${}\alpha ,\,\beta ,\,\gamma$. Dann ist der Wahrheitswert von ${}\varphi$ in ${}I$ nur abhängig von den Wahrheitswerten von ${}\alpha ,\,\beta ,\,\gamma$ in ${}I$ und den Junktoren in ${}\varphi$. 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 ${}\varphi$ den Wahrheitswert ${}w$. Also ist ${}\varphi$ allgemeingültig.

$\Box$

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 ${}S$ ein Symbolalphabet, ${}s,t$ seien ${}S$- Terme und ${}\alpha$ sei ein ${}S$- Ausdruck. Dann sind die beiden folgenden Ausdrücke syntaktische Tautologien.

1. $\vdash t=t.$

2. $\vdash s=t\wedge \alpha {\frac {s}{x}}\rightarrow \alpha {\frac {t}{x}}.$

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

$\vdash s=t\rightarrow {\left(\alpha {\frac {s}{x}}\rightarrow \alpha {\frac {t}{x}}\right)}$

ist.

Lemma Referenznummer erstellen

Die Gleichheitsaxiome

sind korrekt.

Beweis

Es sei ${}I$ eine beliebige ${}S$- Interpretation. (1). Aufgrund der Bedeutung des Gleichheitszeichens unter jeder Interpretation gilt ${}I(t)=I(t)$, also

$I\vDash t=t.$

(2). Es gelte

$I\vDash s=t\wedge \alpha {\frac {s}{x}},$

also ${}I\vDash s=t$ und ${}I\vDash \alpha {\frac {s}{x}}$. Das bedeutet einerseits ${}I(s)=I(t)$. Andererseits gilt nach dem Substitutionslemma

$I{\frac {I(s)}{x}}\vDash \alpha .$

Wegen der Termgleichheit gilt somit auch

$I{\frac {I(t)}{x}}\vDash \alpha$

und daher, wiederum aufgrund des Substitutionslemmas, auch

$I\vDash \alpha {\frac {t}{x}}.$

$\Box$

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

Lemma Lemma 10.7 ändern

Aus den Gleichheitsaxiomen lassen sich folgende Gleichheitstautologien ableiten (dabei sind ${}r,s,t,s_{1},\ldots ,s_{n},t_{1},\ldots ,t_{n}$ Terme, ${}f$ ein ${}n$-stelliges Funktionssymbol und ${}R$ ein ${}n$-stelliges Relationssymbol).

1. $\vdash s=t\rightarrow t=s.$

2. $\vdash r=s\wedge s=t\rightarrow r=t.$

3. $\vdash s_{1}=t_{1}\wedge \ldots \wedge s_{n}=t_{n}\rightarrow fs_{1}\ldots s_{n}=ft_{1}\ldots t_{n}.$

4. $\vdash s_{1}=t_{1}\wedge \ldots \wedge s_{n}=t_{n}\wedge Rs_{1}\ldots s_{n}\rightarrow Rt_{1}\ldots t_{n}.$

Beweis

(1). Aufgrund der Gleichheitsaxiome haben wir

$\vdash s=s$

und

$\vdash s=t\wedge (x=s){\frac {s}{x}}\rightarrow (x=s){\frac {t}{x}},$

wobei ${}x$ eine Variable sei, die weder in ${}s$ noch in ${}t$ vorkomme. Daher sind die beiden substituierten Ausdrücke gleich ${}s=s$ bzw. ${}t=s$. Eine aussagenlogische Umstellung der zweiten Zeile ist

$\vdash s=s\rightarrow (s=t\rightarrow t=s),$

sodass sich aus der ersten Zeile mittels Modus ponens

$\vdash s=t\rightarrow t=s$

ergibt.
(2). Es sei wieder ${}x$ eine Variable, die weder in ${}r$ noch in ${}s$ noch in ${}t$ vorkomme. Eine Anwendung des Substitutionsaxioms liefert

$\vdash s=t\wedge (r=x){\frac {s}{x}}\rightarrow (r=x){\frac {t}{x}}.$

Nach Einsetzen und einer aussagenlogischen Umstellung ist dies die Behauptung.
Für (3) siehe Aufgabe 10.5.
(4). Es sei ${}u$ eine Variable, die weder in einem der ${}s_{i}$ noch in einem der ${}t_{i}$ vorkommt. Für jedes ${}i=1,\ldots ,n$ gilt nach Axiom 10.5  (2) (mit ${}\alpha =\alpha _{i}=Rt_{1}\ldots t_{i-1}us_{i+1}\ldots s_{n}$) dann

$\vdash s_{i}=t_{i}\rightarrow {\left(Rt_{1}\ldots t_{i-1}us_{i+1}\ldots s_{n}{\frac {s_{i}}{u}}\rightarrow Rt_{1}\ldots t_{i-1}us_{i+1}\ldots s_{n}{\frac {t_{i}}{u}}\right)},$

also

$\vdash s_{i}=t_{i}\rightarrow {\left(Rt_{1}\ldots t_{i-1}s_{i}s_{i+1}\ldots s_{n}\rightarrow Rt_{1}\ldots t_{i-1}t_{i}s_{i+1}\ldots s_{n}\right)}.$

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

$(s_{1}=t_{1})\wedge \ldots \wedge (s_{n}=t_{n})$

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

$\vdash (s_{1}=t_{1})\wedge \ldots \wedge (s_{n}=t_{n})\rightarrow {\left(Rs_{1}\ldots s_{n}\rightarrow Rt_{1}\ldots t_{n}\right)}.$

$\Box$