Aussagenlogik/Syntaktische Tautologien/Ableitungen und Regeln/Textabschnitt

Lemma

Es ist

$\vdash \alpha \rightarrow \alpha .$

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

$\vdash \alpha \wedge \beta \rightarrow \alpha$

und

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

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

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

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

$\vdash {\left(\alpha \wedge \beta \right)}\wedge \gamma \rightarrow \alpha \wedge {\left(\beta \wedge \gamma \right)}.$

Beweis

Siehe Aufgabe.

$\Box$

Lemma

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

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

Beweis

1. Nach Axiom  (2) ist

   $\vdash {\left(\alpha \wedge \gamma \rightarrow \alpha \right)}\wedge {\left(\alpha \rightarrow \beta \right)}\rightarrow {\left(\alpha \wedge \gamma \rightarrow \beta \right)}$

   und daher mit Axiom  (4) auch

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

   Der Vordersatz ist nach Fakt ableitbar, also auch der Nachsatz.
   

2. Nach Teil (1) ist

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

   und (unter Verwendung von Fakt und Aufgabe)

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

   Daher gilt auch (nach der Regelversion zu Teil (1))

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

   und

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

   bzw. unter Verwendung von Axiom  (4) und der Assoziativität der Konjunktion

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

   und

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

   Nach Axiom  (3) ist mit der Abkürzung ${}\varphi =(\alpha \rightarrow \beta )\wedge (\gamma \rightarrow \delta )\wedge \alpha \wedge \gamma$

   $\vdash (\varphi \rightarrow \beta )\wedge (\varphi \rightarrow \delta )\rightarrow (\varphi \rightarrow \beta \wedge \delta ).$

   Da die beiden Teilaussagen im Vordersatz ableitbar sind, ist auch der Nachsatz ableitbar, was unter Verwendung von Axiom  (4) zur Behauptung umformulierbar ist.
   

$\Box$

Die folgende Aussage gibt eine „interne Version“ des Modus ponens, der ja nach Definition eine Schlussregel ist.

Lemma

Es ist

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

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

1. Aus ${}\vdash \alpha \rightarrow (\beta \rightarrow \gamma )$ und ${}\vdash \gamma \rightarrow \delta$ folgt ${}\vdash \alpha \rightarrow (\beta \rightarrow \delta )$.
2. Aus ${}\vdash \alpha$ und ${}\vdash \alpha \wedge \beta \rightarrow \gamma$ ergibt sich ${}\vdash \beta \rightarrow \gamma$.

Beweis

1. Sei

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

   und

   $\vdash \gamma \rightarrow \delta .$

   Nach Bemerkung gilt auch

   $\vdash \alpha \rightarrow (\gamma \rightarrow \delta )$

   und daraus ergibt sich mit Axiom  (3), der Konjunktionsregel und dem Modus ponens

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

   Mittels des Kettenschlusses ergibt sich daraus und aus Axiom  (2) die Behauptung.
   

2. 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

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

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

3. $\vdash \alpha \rightarrow \neg \neg \alpha .$

4. $\vdash \neg \neg \alpha \rightarrow \alpha .$

5. $\vdash (\alpha \rightarrow \beta )\rightarrow (\neg \beta \rightarrow \neg \alpha ).$

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

Beweis

1. Die Fallunterscheidungstautologie liefert

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

   Aus (Fakt)

   $\vdash \alpha \rightarrow \alpha$

   ergibt sich daraus die Behauptung.
   

2. Nach Axiom  (3) gilt

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

   und nach Axiom  (5) gilt

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

   Nach Fakt  (1) folgt

   $\vdash (\neg \beta \rightarrow \neg \alpha )\wedge (\neg \beta \rightarrow \alpha )\rightarrow (\neg \beta \rightarrow \beta ),$

   woraus nach Teil (1) die Behauptung mit der Kettenschlussregel folgt.
   

3. Nach Axiom  (1) ist

   $\vdash \neg \neg \alpha \rightarrow (\alpha \rightarrow \neg \neg \alpha ).$

   Nach Axiom  (5) ist

   $\vdash \neg \alpha \wedge \alpha \rightarrow \neg \neg \alpha ,$

   was wir mit Axiom  (4) zu

   $\vdash \neg \alpha \rightarrow (\alpha \rightarrow \neg \neg \alpha ),$

   umformulieren können. Daraus ergibt sich

   $\vdash \alpha \rightarrow \neg \neg \alpha$

   mit der Fallunterscheidungsregel.
   

4. Nach Axiom  (1) ist

   $\vdash \alpha \rightarrow (\neg \neg \alpha \rightarrow \alpha ).$

   Nach Axiom  (5) ist

   $\vdash \neg \alpha \wedge \neg \neg \alpha \rightarrow \alpha ,$

   was wir zu

   $\vdash \neg \alpha \rightarrow (\neg \neg \alpha \rightarrow \alpha ),$

   umformulieren können. Daraus ergibt sich

   $\vdash \neg \neg \alpha \rightarrow \alpha$

   mit der Fallunterscheidungsregel.
   

5. Es ist nach Axiom  (1)

   $\vdash \neg \alpha \rightarrow (\neg \beta \rightarrow \neg \alpha )$

   und damit auch

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

   Ferner ist nach einer Variante von Axiom  (5)

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

   Nach Fakt ist

   $\vdash \alpha \rightarrow ((\alpha \rightarrow \beta )\rightarrow \beta ),$

   woraus sich

   $\vdash \alpha \rightarrow ((\alpha \rightarrow \beta )\rightarrow (\neg \beta \rightarrow \neg \alpha ))$

   ergibt. Mit der Fallunterscheidungsregel folgt die Behauptung.
   

6. Dies folgt aus (3), (4) und (5).
   

$\Box$