Aussagenlogik/Syntaktische Tautologien/Axiomatik/Einführung/Textabschnitt

Axiom

Für eine Aussagenvariablenmenge ${}V$ und beliebige Ausdrücke ${}\alpha ,\beta ,\gamma$ 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 \neg \alpha \wedge \alpha \rightarrow \beta .$

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

Man spricht häufig auch genauer von Axiomenschemata, da jedes Axiom bei unterschiedlichen Einsetzungen eine Vielzahl von Axiomen representiert. Das Kettenschlussaxiom (2) besagt die Transitivität der Implikation, Axiom (5) heißt Widerspruchsaxiom und Axiom (6) heißt Fallunterscheidungsaxiom. Diese Tautologien sind die axiomatisch fixierten Grundtautologien und fungieren als die Startglieder im rekursiven Aufbau der syntaktischen Tautologien. Um überhaupt aus diesen Axiomen weitere Tautologien generieren zu können, braucht man Ableitungsregeln. Davon gibt es lediglich eine.

Modus ponens

Aus ${}\vdash \alpha$ und ${}\vdash (\alpha )\rightarrow (\beta )$ folgt ${}\vdash \beta$.

Definition

Unter einer syntaktischen Tautologie versteht man einen Ausdruck ${}\alpha \in L^{V}$ (zu einer Aussagenvariablenmenge ${}V$), den man aus den {{ Axiomlink Grundtautologien|Axiomseitenname= Aussagenlogik/Syntaktische Tautologien/Implikation, Negation, Konjunktion/Axiom |Nr= |SZ= }} rekursiv mittels Modus ponens erhalten kann.

Die Menge aller syntaktischen Tautologien bilden also eine rekursiv definierte Teilmenge von ${}L^{V}$.

Bemerkung  

Eine Durchsicht der Grundtautologien zeigt, dass es sich jeweils auch um semantische Tautologien handelt, siehe Aufgabe. Wenn ferner ${}\alpha$ und ${}(\alpha )\rightarrow (\beta )$ semantische Tautologien sind, so ist auch ${}\beta$ eine semantische Tautologie. D.h. die semantischen Tautologien sind unter Modus ponens abgeschlossen. Dies bedeutet insgesamt, dass syntaktische Tautologien stets semantische Tautologien sind. Diese Eigenschaft nennt man auch die Korrektheit des syntaktischen Kalküls, er leitet ausschließlich semantische Tautologien, also wahre Aussagen ab. Die umgekehrte Aussage, dass sich jede semantische Tautologie auch syntaktisch in dem angegebenen Kalkül ableiten lässt, nennt man die Vollständigkeit des Kalküls.