# Aussagenlogik/Syntaktische Tautologien/Ableitungen und Regeln/Textabschnitt
## Lemma

Es ist

### Beweis

Es ist
    $\vdash {\left(\alpha \rightarrow {\left(\alpha \rightarrow \alpha \right)}\right)}\wedge {\left(\neg \alpha \rightarrow {\left(\alpha \rightarrow \alpha \right)}\right)}\rightarrow {\left(\alpha \rightarrow \alpha \right)}$
nach Axiom (6), woraus sich nach Axiom (4) mit Modus Pones auch
    $\vdash {\left(\alpha \rightarrow {\left(\alpha \rightarrow \alpha \right)}\right)}\rightarrow {\left({\left(\neg \alpha \rightarrow {\left(\alpha \rightarrow \alpha \right)}\right)}\rightarrow {\left(\alpha \rightarrow \alpha \right)}\right)}$
ergibt. Wegen Axiom (1) ist
    $\vdash \alpha \rightarrow {\left(\alpha \rightarrow \alpha \right)}$
und daher mit Modus ponens auch
    $\vdash {\left(\neg \alpha \rightarrow {\left(\alpha \rightarrow \alpha \right)}\right)}\rightarrow {\left(\alpha \rightarrow \alpha \right)}.$
Wegen Axiom (5) ist
    $\vdash \neg \alpha \wedge \alpha \rightarrow \alpha$
und damit mit Axiom (4) auch
    $\vdash \neg \alpha \rightarrow {\left(\alpha \rightarrow \alpha \right)},$
sodass sich
    $\vdash \alpha \rightarrow \alpha$
ergibt.
$\Box$

## Lemma

Für $\alpha ,\beta \in L^{V}$ ist

### Beweis

Nach Axiom (4) ist
    $\vdash {\left(\alpha \rightarrow {\left(\beta \rightarrow \alpha \right)}\right)}\rightarrow {\left(\alpha \wedge \beta \rightarrow \alpha \right)}$
und wegen Axiom (1) ist
    $\vdash \alpha \rightarrow {\left(\beta \rightarrow \alpha \right)},$
sodass mit Modus ponens auch
    $\vdash \alpha \wedge \beta \rightarrow \alpha$
gilt. Für die andere Behauptung gehen wir von Fakt aus, was
    $\vdash \beta \rightarrow \beta$
liefert. Wegen Axiom (1) haben wir
    $\vdash {\left(\beta \rightarrow \beta \right)}\rightarrow {\left(\alpha \rightarrow {\left(\beta \rightarrow \beta \right)}\right)},$
also mit Modus ponens auch
    $\vdash \alpha \rightarrow {\left(\beta \rightarrow \beta \right)}.$
Nach Axiom (4) ist
    $\vdash {\left(\alpha \rightarrow {\left(\beta \rightarrow \beta \right)}\right)}\rightarrow {\left(\alpha \wedge \beta \rightarrow \beta \right)},$
woraus sich nach dem bisher Bewiesenen
    $\alpha \wedge \beta \rightarrow \beta$
ergibt.
$\Box$

## Bemerkung

Die aussagenlogischen Axiome der Form $\vdash \alpha \rightarrow \beta$ führen zu entsprechenden Schlussregeln, d.h. Vorschriften, wie man aus (schon etablierten) syntaktischen Tautologien neue Tautologien erhält. Wir gehen unter diesem Gesichtspunkt die Axiome durch.
Aus $\vdash \alpha$ folgt $\vdash \beta \rightarrow \alpha$.
Dies ergibt sich aus der Voraussetzung $\vdash \alpha$ aus $\vdash \alpha \rightarrow (\beta \rightarrow \alpha )$ und dem Modus ponens.
Aus $\vdash \alpha \wedge \beta$ folgt $\vdash \alpha$ (und ebenso $\vdash \beta$).
Dies ergibt sich aus $\vdash \alpha \wedge \beta \rightarrow \alpha$ nach Fakt und der Voraussetzung $\vdash \alpha \wedge \beta$ mittels Modus ponens. Umgekehrt gilt die sogenannte Konjunktionsregel, d.h. aus $\vdash \alpha$ und $\vdash \beta$ folgt auch $\vdash \alpha \wedge \beta$. Dies ergibt sich aus
    $\vdash \alpha \rightarrow (\beta \rightarrow \alpha \wedge \beta )$
(was aus den Axiomen folgt, siehe Aufgabe) aus den Voraussetzungen durch eine zweifache Anwendung des Modus ponens.
Aus $\vdash \alpha \rightarrow \beta$ und $\vdash \beta \rightarrow \gamma$ ergibt sich $\vdash \alpha \rightarrow \gamma$. Diese Regel heißt Kettenschlussregel. Nach der obigen abgeleiteten Konjunktionsregel folgt aus den Voraussetzungen direkt $\vdash (\alpha \rightarrow \beta )\wedge (\beta \rightarrow \gamma )$ und daraus und dem Kettenschlussaxiom mit dem Modus ponens $\vdash \alpha \rightarrow \gamma$.

## Lemma

Es ist

### Beweis

Nach Axiom (3) ist
    $\vdash ((\alpha \wedge \beta )\rightarrow \beta )\wedge ((\alpha \wedge \beta )\rightarrow \alpha )\rightarrow (\alpha \wedge \beta \rightarrow \beta \wedge \alpha ).$
Die beiden Bestandteile des Vordersatzes gelten nach Fakt, sodass auch ihre Konjunktion ableitbar ist. Daher ist auch der Nachsatz ableitbar.
$\Box$

## Lemma

Es ist

### Beweis

$\Box$

## Lemma
### Beweis

* Nach Axiom (2) ist und daher mit Axiom (4) auch Der Vordersatz ist nach Fakt ableitbar, also auch der Nachsatz.
    $\vdash {\left(\alpha \wedge \gamma \rightarrow \alpha \right)}\wedge {\left(\alpha \rightarrow \beta \right)}\rightarrow {\left(\alpha \wedge \gamma \rightarrow \beta \right)}$
    $\vdash (\alpha \wedge \gamma \rightarrow \alpha )\rightarrow ((\alpha \rightarrow \beta )\rightarrow (\alpha \wedge \gamma \rightarrow \beta )).$
* Nach Teil (1) ist und (unter Verwendung von Fakt und Aufgabe) Daher gilt auch (nach der Regelversion zu Teil (1)) und bzw. unter Verwendung von Axiom (4) und der Assoziativität der Konjunktion und Nach Axiom (3) ist mit der Abkürzung $\varphi =(\alpha \rightarrow \beta )\wedge (\gamma \rightarrow \delta )\wedge \alpha \wedge \gamma$ Da die beiden Teilaussagen im Vordersatz ableitbar sind, ist auch der Nachsatz ableitbar, was unter Verwendung von Axiom (4) zur Behauptung umformulierbar ist.
    $\vdash (\alpha \rightarrow \beta )\rightarrow (\alpha \wedge \gamma \rightarrow \beta )$
    $\vdash (\gamma \rightarrow \delta )\rightarrow (\alpha \wedge \gamma \rightarrow \delta ).$
    $\vdash (\alpha \rightarrow \beta )\wedge (\gamma \rightarrow \delta )\rightarrow (\alpha \wedge \gamma \rightarrow \beta )$
    $\vdash (\alpha \rightarrow \beta )\wedge (\gamma \rightarrow \delta )\rightarrow (\alpha \wedge \gamma \rightarrow \delta )$
    $\vdash (\alpha \rightarrow \beta )\wedge (\gamma \rightarrow \delta )\wedge \alpha \wedge \gamma \rightarrow \beta$
    $\vdash (\alpha \rightarrow \beta )\wedge (\gamma \rightarrow \delta )\wedge \alpha \wedge \gamma \rightarrow \delta .$
    $\vdash (\varphi \rightarrow \beta )\wedge (\varphi \rightarrow \delta )\rightarrow (\varphi \rightarrow \beta \wedge \delta ).$
$\Box$
Die folgende Aussage gibt eine „interne Version“ des Modus ponens, der ja nach Definition eine Schlussregel ist.

## Lemma

Es ist

### Beweis

Nach Axiom (6) ist
    $\vdash (\alpha \rightarrow \beta )\wedge (\neg \alpha \rightarrow \beta )\rightarrow \beta ,$
und Axiom (5) kann man wegen Axiom (4) zu
    $\vdash \alpha \rightarrow (\neg \alpha \rightarrow \beta )$
umformulieren. Daraus und aus (Fakt)
    $\vdash {\left(\alpha \rightarrow \beta \right)}\rightarrow {\left(\alpha \rightarrow \beta \right)}$
ergibt sich mit der Regelversion zu Fakt (2)
    $\vdash \alpha \wedge {\left(\alpha \rightarrow \beta \right)}\rightarrow {\left(\neg \alpha \rightarrow \beta \right)}\wedge {\left(\alpha \rightarrow \beta \right)}$
und daraus durch den Kettenschluss die Behauptung.
$\Box$

## Lemma

* Aus $\vdash \alpha \rightarrow (\beta \rightarrow \gamma )$ und $\vdash \gamma \rightarrow \delta$ folgt $\vdash \alpha \rightarrow (\beta \rightarrow \delta )$.
* Aus $\vdash \alpha$ und $\vdash \alpha \wedge \beta \rightarrow \gamma$ ergibt sich $\vdash \beta \rightarrow \gamma$.

### Beweis

* Sei und Nach Bemerkung gilt auch und daraus ergibt sich mit Axiom (3), der Konjunktionsregel und dem Modus ponens Mittels des Kettenschlusses ergibt sich daraus und aus Axiom (2) die Behauptung.
    $\vdash \alpha \rightarrow (\beta \rightarrow \gamma )$
    $\vdash \gamma \rightarrow \delta .$
    $\vdash \alpha \rightarrow (\gamma \rightarrow \delta )$
    $\vdash \alpha \rightarrow (\beta \rightarrow \gamma )\wedge (\gamma \rightarrow \delta ).$
* Siehe Aufgabe.
$\Box$
Die folgenden Tautologien machen wichtige Aussagen über das Negationszeichen. Die Tautologie (2) ist eine wichtige Variante der Widerspruchstautologie und die in (5) und (6) ausgedrückte Äquivalenz heißt Kontraposition.

## Lemma
### Beweis

* Die Fallunterscheidungstautologie liefert Aus (Fakt) ergibt sich daraus die Behauptung.
    $\vdash (\alpha \rightarrow \alpha )\wedge (\neg \alpha \rightarrow \alpha )\rightarrow \alpha .$
    $\vdash \alpha \rightarrow \alpha$
* Nach Axiom (3) gilt und nach Axiom (5) gilt Nach Fakt (1) folgt woraus nach Teil (1) die Behauptung mit der Kettenschlussregel folgt.
    $\vdash (\neg \beta \rightarrow \neg \alpha )\wedge (\neg \beta \rightarrow \alpha )\rightarrow (\neg \beta \rightarrow \neg \alpha \wedge \alpha )$
    $\vdash \neg \alpha \wedge \alpha \rightarrow \beta .$
    $\vdash (\neg \beta \rightarrow \neg \alpha )\wedge (\neg \beta \rightarrow \alpha )\rightarrow (\neg \beta \rightarrow \beta ),$
* Nach Axiom (1) ist Nach Axiom (5) ist was wir mit Axiom (4) zu umformulieren können. Daraus ergibt sich mit der Fallunterscheidungsregel.
    $\vdash \neg \neg \alpha \rightarrow (\alpha \rightarrow \neg \neg \alpha ).$
    $\vdash \neg \alpha \wedge \alpha \rightarrow \neg \neg \alpha ,$
    $\vdash \neg \alpha \rightarrow (\alpha \rightarrow \neg \neg \alpha ),$
    $\vdash \alpha \rightarrow \neg \neg \alpha$
* Nach Axiom (1) ist Nach Axiom (5) ist was wir zu umformulieren können. Daraus ergibt sich mit der Fallunterscheidungsregel.
    $\vdash \alpha \rightarrow (\neg \neg \alpha \rightarrow \alpha ).$
    $\vdash \neg \alpha \wedge \neg \neg \alpha \rightarrow \alpha ,$
    $\vdash \neg \alpha \rightarrow (\neg \neg \alpha \rightarrow \alpha ),$
    $\vdash \neg \neg \alpha \rightarrow \alpha$
* Es ist nach Axiom (1) und damit auch Ferner ist nach einer Variante von Axiom (5) Nach Fakt ist woraus sich ergibt. Mit der Fallunterscheidungsregel folgt die Behauptung.
    $\vdash \neg \alpha \rightarrow (\neg \beta \rightarrow \neg \alpha )$
    $\vdash \neg \alpha \rightarrow ((\alpha \rightarrow \beta )\rightarrow (\neg \beta \rightarrow \neg \alpha )).$
    $\vdash \beta \rightarrow (\neg \beta \rightarrow \neg \alpha ).$
    $\vdash \alpha \rightarrow ((\alpha \rightarrow \beta )\rightarrow \beta ),$
    $\vdash \alpha \rightarrow ((\alpha \rightarrow \beta )\rightarrow (\neg \beta \rightarrow \neg \alpha ))$
* Dies folgt aus (3), (4) und (5).
$\Box$