Logik: Aussagenlogik

Einleitung

Die Aussagenlogik ist ein erster Schritt, die in der Mathematik – aber nicht nur da! – verwendeten logischen Schlussweisen zu rechtfertigen. Sind beispielsweise die Aussagen (1) und (2)

(1)   ${\boldsymbol {\alpha }}$

(2)   ${\mathsf {wenn}}\;{\boldsymbol {\alpha }}\;{\mathsf {dann}}\;{\boldsymbol {\beta }}$

bereits bewiesen, so gilt auch die Aussage (3):

(3)   ${\boldsymbol {\beta }}$

(1) und (2) sind die Prämissen des Schlusses, (3) die Konklusion. Der Schluss selbst heisst Modus Ponens. Üblich sind auch andere Schreibweisen, zum Beispiel als sogenannte Schnittregel:

${\frac {\vdash \alpha \qquad \alpha \vdash \beta }{\vdash \beta }}$

Ein anderes Beispiel ist das Beweisverfahren durch Widerspruch. Angenommen ${\boldsymbol {\alpha }}$ soll bewiesen werden. Man nimmt nun das Gegenteil an, also dass ${\mathsf {nicht}}\;{\boldsymbol {\alpha }}$ richtig sei. Daraus wird solange weiter geschlossen, bis man auf einen Widerspruch stößt, beispielsweise auf ${\boldsymbol {1=2}}$. Also muss doch ${\boldsymbol {\alpha }}$ richtig sein. Solche Beweise werden indirekte Beweise genannt.

Die Aussagenlogik ist ein einfaches System und die Grundlage für weitere logische Systeme, auch für solche, die in der Mathematik zwar behandelt, aber in der Regel nicht verwendet werden.

Geschichte

Schon im 4. Jahrhundert vor Christus formulierte der griechische Philosoph Aristoteles den Satz vom Widerspruch, der besagt, dass eine Aussage und ihr Gegenteil nicht beide wahr sein können, und den Satz vom ausgeschlossenen Dritten, der besagt, dass eine beliebige Aussage oder ihre Verneinung wahr ist. Auch der indirekten Beweis findet sich in seinen Schriften. Chrysoppis von Soloi definierte im 3. Jahrhundert vor Christus Aussagen als Wahr oder Falsch und verwendete eine Semantik, die den heutigen Wahrheitstafeln entspricht. Die erste Formalisierung der Aussagenlogik entwickelte 1847 der englische Mathematiker George Boole. Den ersten Kalkül entwickelte 1879 Gottlob Frege. 1910 verwendete Bertrand Russell die heute noch übliche Notation.

Eine formale Sprache (Syntax)

Eine formale Sprache besteht aus einem Alphabet und einer Grammatik. Das Alphabet bestimmt dabei, welche Zeichen Bestandteil der Sprache sind; es wird manchmal auch als Vokabular oder Lexikon bezeichnet. Die Grammatik bestimmt hingegen, wie die Zeichen zu Wörtern zusammengesetzt werden können.

Alphabet

In der Aussagenlogik gibt es 3 Arten von Zeichen:

1. Aussagenkonstante $\alpha$, $\beta$, $\gamma$, ...
2. Junktoren $\top$, $\bot$, $\neg$, $\land$, $\lor$, $\rightarrow$, $\leftrightarrow$
3. Klammern $($, $)$

Die Junktoren heissen Verum ($\top$), Falsum ($\bot$), Negation ($\neg$), Konjunktion ($\land$), Disjunktion ($\lor$), Subjunktion ($\rightarrow$) und Bijunktion ($\leftrightarrow$).

Grammatik

Genauso wenig wie in einer natürlichen Sprache wie Deutsch ergibt nicht jede beliebige Zeichenreihe ein korrektes Wort. Zeichenreihen, die nach den Regeln der Grammatik aufgebaut sind, heissen wohlgeformt. Die Wörter der Aussagenlogik werden Aussagen oder Formeln genannt. Damit eine Anordnung von Zeichen eine Formel in der Aussagenlogik bildet, muss sie nach den folgenden Regeln aufgebaut sein:

1. Jede Aussagenkonstante ist eine Formel, $\top$ und $\bot$ sind Formeln.
2. Ist $\varphi$ eine Formel, so ist auch $\neg \varphi$ eine Formel.
3. Sind sowohl $\varphi \,$ als auch $\psi \,$ Formeln, so sind auch $(\varphi \wedge \psi )$, $(\varphi \vee \psi )$, $(\varphi \rightarrow \psi )$ und $(\varphi \leftrightarrow \psi )$ Formeln.

Es gibt keine weiteren Zeichenreihen, die Formeln sind, alle Formeln sind schrittweise nach diesen Regeln aufgebaut!

Die Anzahl der Formeln, die auf diese Weise gebildet werden können, hängt von der Anzahl der Aussagenkonstanten ab. Wenn diese höchstens abzählbar ist, gibt es auch nur abzählbar viele Formeln. Gibt es mehr, nämlich $\kappa$-viele mit $\kappa >\omega$, dann hat die Sprache $\kappa$-viele Formeln.

Beispiele

Keine Formeln

Die folgenden Zeichenreihen sind keine Formeln, denn sie lassen sich nicht nach den Regeln der Grammatik erzeugen:

$\neg$, $\land \lor$, $\alpha \beta \gamma$, $\alpha \land \beta$.

Zeichenreihe	Begründung
$\neg$	nach Regel 2 muss auf das Zeichen $\neg$ eine Formel folgen
$\land \lor$	nach Regel 3 treten $\land$ und $\lor$ immer zusammen mit Klammern auf
$\alpha \beta \gamma$	mehrere Aussagenkonstante können nicht hintereinander stehen
$\alpha \land \beta$	hier fehlen die Aussenklammern

Formeln

Die folgenden Zeichenreihen sind Formeln:

$\neg \delta$, $(\alpha \rightarrow \beta )$, $(\alpha \land (\beta \lor \gamma ))$, $((\alpha \land \beta )\lor \gamma )$.

Formel	Begründung
$\neg \delta$	$\delta$ ist eine Aussagenkonstante, also nach Regel 1 eine Formel, Regel 2 liefert dann $\neg \delta$
$(\alpha \rightarrow \beta )$	$\alpha$ und $beta$ sind Aussagenkonstanten, Regel 2 liefert $(\alpha \rightarrow \beta )$
$(\alpha \land (\beta \lor \gamma ))$	$\alpha$, $\beta$ und $\gamma$ sind Aussagenkonstanten, nach Regel 2 ist $(\beta \lor \gamma )$ Formel und somit auch $(\alpha \land (\beta \lor \gamma ))$
$((\alpha \land \beta )\lor \gamma )$	$\alpha$, $\beta$ und $\gamma$ sind Aussagenkonstanten, nach Regel 2 ist $(\alpha \land \beta )$ Formel und daher auch $((\alpha \land \beta )\lor \gamma )$

Klammerersparnis

Wie die letzten beiden Beispiele zeigen, sind Klammern erforderlich, um eindeutig festzustellen, wie eine Formel aufgebaut ist. Einige Klammern können aber eingespart werden, ohne die Lesbarkeit zu beeinträchtigen. Es werden folgende Regeln vereinbart:

1. Aussenklammern können weggelassen werden,
2. $\land$ und $\lor$ binden stärker als $\rightarrow$ und $\leftrightarrow$,
3. $\rightarrow$ bindet stärker als $\leftrightarrow$.

Beispiele: nach 1 ist $\alpha \land \beta$ eine Abkürzung für die Formel $(\alpha \land \beta )$, nach 1 und 2 lesen wir $\alpha \land \beta \rightarrow \alpha \lor \beta$ als $((\alpha \land \beta )\rightarrow (\alpha \lor \beta ))$.

Die Bedeutung (Semantik)

Den Formeln der Aussagenlogik haben eine Bedeutung: sie sind Wahr oder Falsch. Dabei hängt die Bedeutung der mit Junktoren gebildeten Formeln von den beiden Teilformeln ab, aus denen sie gebildet ist. Da alle Formeln letztlich aus Aussagenkonstanten aufgebaut sind, hängt der Wahrheitswert einer Formel von den Wahrheitswerten ihrer Aussagenkonstanten ab. Eine Interpretation ordnet jeder Aussagenkonstante einen der beiden Wahrheitswerte Wahr oder Falsch zu. Eine solche Zuordnung wird auch Bewertung oder Modell genannt.

Interpretation, Bewertung

Sei ${\mathcal {J}}$ eine Zuordnung der Aussagenkonstanten zu den Werten Wahr (kurz: W) und Falsch (kurz: F) gegeben. Dann wird diese Zuordnung wie folgt auf die Formeln fortgesetzt:

Verum, Falsum

$\top$ ist Wahr zugeordnet, $\bot$ ist Falsch zugeordnet.

Negation

Ist $\varphi$ Wahr, so ist $\neg \varphi$ Falsch, ist $\varphi$ Falsch so ist $\neg \varphi$ Wahr. Das lässt sich in einer sogenannten Wahrheitstafel wie folgt darstellen:

$\varphi$	$\neg \varphi$
W	F
F	W

Konjunktion

$\varphi \land \psi$ ist nur dann Wahr, wenn beide Teilformeln $\varphi$ und $\psi$ wahr sind:

$\varphi$	$\psi$	$\varphi \land \phi$
W	W	W
W	F	F
F	W	F
F	F	F

Disjunktion

$\varphi \lor \psi$ ist schon dann Wahr, wenn eine der beiden Teilformeln $\varphi$ und $\psi$ Wahr ist:

$\varphi$	$\psi$	$\varphi \lor \psi$
W	W	W
W	F	W
F	W	W
F	F	F

Subjunktion

$\varphi \rightarrow \psi$ ist Wahr, wenn die Formel $\varphi$ Falsch ist oder wenn die Formel $\psi$ Wahr ist:

$\varphi$	$\psi$	$\varphi \rightarrow \psi$
W	W	W
W	F	F
F	W	W
F	F	W

Bijunktion

$\varphi \leftrightarrow \psi$ ist nur dann Wahr, wenn beide Formeln $\varphi$ und $\psi$ den gleichen Wahrheitswert haben:

$\varphi$	$\psi$	$\varphi \leftrightarrow \psi$
W	W	W
W	F	F
F	W	F
F	F	W

Zusammenfassung

Die so erweiterte Zuordnung ${\mathcal {J}}$ wird Interpretation oder Bewertung, in manchen Zusammenhängen auch Modell genannt.

Definition:

Eine Bewertung ${\mathcal {J}}$ ordnet allen Formeln wie folgt einen Wahrheitswert aus $\{{\mathsf {W}},{\mathsf {F}}\}$ zu:

1. ${\mathcal {J}}(\alpha )\in \{{\mathsf {W}},{\mathsf {F}}\}$ für alle Aussagkonstanten $\alpha$
2. ${\mathcal {J}}(\top )={\mathsf {W}}$   und   ${\mathcal {J}}(\bot )={\mathsf {F}}$
3. ${\mathcal {J}}(\neg \varphi )={\begin{cases}{\mathsf {W}},&{\text{wenn }}{\mathcal {J}}(\varphi )={\mathsf {F}}\\{\mathsf {F}},&{\text{sonst}}\end{cases}}$
4. ${\mathcal {J}}(\varphi \land \psi )={\begin{cases}{\mathsf {W}},&{\text{wenn }}{\mathcal {J}}(\varphi )={\mathsf {W}}{\text{ und }}{\mathcal {J}}(\psi )={\mathsf {W}}\\{\mathsf {F}},&{\text{sonst}}\end{cases}}$
5. ${\mathcal {J}}(\varphi \lor \psi )={\begin{cases}{\mathsf {W}},&{\text{wenn }}{\mathcal {J}}(\varphi )={\mathsf {W}}{\text{ oder }}{\mathcal {J}}(\psi )={\mathsf {W}}\\{\mathsf {F}},&{\text{sonst}}\end{cases}}$
6. ${\mathcal {J}}(\varphi \rightarrow \psi )={\begin{cases}{\mathsf {W}},&{\text{sonst}}\\{\mathsf {F}},&{\text{wenn }}{\mathcal {J}}(\varphi )={\mathsf {W}}{\text{ und }}{\mathcal {J}}(\psi )={\mathsf {F}}\end{cases}}$
7. ${\mathcal {J}}(\varphi \leftrightarrow \psi )={\begin{cases}{\mathsf {W}},&{\text{wenn }}{\mathcal {J}}(\varphi )={\mathcal {J}}(\psi )\\{\mathsf {F}},&{\text{sonst}}\end{cases}}$

Redeweisen:

${\mathcal {J}}$ erfüllt eine Formel $\varphi$, wenn ${\mathcal {J}}$ der Formel $\varphi$ den Wert Wahr zuordnet. ${\mathcal {J}}$ erfüllt die Formelmenge $\Gamma$, wenn ${\mathcal {J}}$ alle Formeln aus $\Gamma$ mit Wahr belegt. Eine andere Redeweise lautet: ${\mathcal {J}}$ ist ein Modell von $\varphi$ bzw. von $\Gamma$.

${\mathcal {J}}$ widerlegt eine Formel $\varphi$, wenn ${\mathcal {J}}$ die Formel $\varphi$ mit Falsch bewertet. ${\mathcal {J}}$ wird dann auch Gegenbeispiel für $\varphi$ genannt.

Logische Folgerung

Definition: Seien $\Gamma$ und $\Delta$ Formelmengen.

Dann folgt $\Delta$ aus $\Gamma$, wenn für alle Bewertungen gilt: sind alle Formeln aus $\Gamma$ Wahr, dann ist wenigstens eine Formel aus $\Delta$ Wahr.

Schreibweisen: $\Gamma \models \Delta$ (aus $\Gamma$ folgt $\Delta$) und $\Gamma \nvDash \Delta$ (aus $\Gamma$ folgt nicht $\Delta$).

Damit $\Gamma \nvDash \Delta$ gilt, muss es also eine Bewertung ${\mathcal {J}}$ geben, die alle Formeln aus $\Gamma$ mit ${\mathsf {W}}$ und alle Formeln aus $\Delta$ mit ${\mathsf {F}}$ belegt.

Schreibweisen

Statt $\lbrace \varphi _{1},\varphi _{2},...,\varphi _{n}\rbrace \models \lbrace \psi _{1},\psi _{2},...,\psi _{m}\rbrace$ schreiben wir einfach $\varphi _{1},\varphi _{2},...,\varphi _{n}\models \psi _{1},\psi _{2},...,\psi _{m}$, lassen also die Klammern $\lbrace \;\rbrace$ weg.

Mit   $\Gamma ,\varphi \models \Delta ,\psi$   ist   $\Gamma \cup \lbrace \varphi \rbrace \models \Delta \cup \lbrace \psi \rbrace$   gemeint.

Ein wichtiger Spezialfall ist   $\Gamma \models \varphi$   (aus $\Gamma$ folgt $\varphi$).

$\models \varphi$   steht für   $\varnothing \models \varphi$   ($\varnothing$ ist die leere Menge).

Beweis:
Es gelte $\Gamma ,\varphi \models \psi ,\Delta$ und es sei ${\mathcal {J}}$ eine Bewertung, die alle Formeln aus $\Gamma$ Wahr macht.
Wenn ${\mathcal {J}}$ die Formel $\varphi$ mit Falsch bewertet, sind wir fertig, weil dann ${\mathcal {J}}$ die Formel $\varphi \rightarrow \psi$ erfüllt. Wenn ${\mathcal {J}}$ die Formel $\varphi$ mit Wahr bewertet, ist es nach Voraussetzung die Formel $\psi$ oder eine Formel aus $\Delta$ Wahr. Im zweiten Fall ist nichts weiter zu zeigen und im ersten Fall ist auch $\varphi \rightarrow \psi$ Wahr.

Gelte nun umgekehrt $\Gamma \models \varphi \rightarrow \psi ,\Delta$ und ${\mathcal {J}}$ erfülle alle Formeln aus $\Gamma$.
Wenn ${\mathcal {J}}$ eine Formel aus $\Delta$ Wahr macht, sind wir fertig. Wenn ${\mathcal {J}}$ die Formel $\varphi \rightarrow \psi$ Wahr macht, gibt es zwei Möglichkeiten: ${\mathcal {J}}$ bewertet $\varphi$ mit Falsch, dann ist alles klar. Bewertet ${\mathcal {J}}$ die Formel $\varphi$ mit Wahr, bewertet sie auch die Formel $\psi$ mit Wahr. Also gilt $\Gamma ,\varphi \models \psi ,\Delta$. ✔

Tautologien

Eine Formel $\varphi$ ist eine Tautologie, wenn sie bei allen Bewertungen Wahr ist, symbolisch: $\models \varphi$. Man sagt auch $\varphi$ ist logisch wahr oder allgemeingültig.

Folgende Sätze gelten, wie man leicht mit Hilfe der Wahrheitstafeln nachprüft:

$\models \top$

$\models \neg \neg \varphi \leftrightarrow \varphi$

$\models \neg (\varphi \land \neg \varphi )$ (Satz vom Widerspruch)

$\models \varphi \lor \neg \varphi$ (Satz vom ausgeschlossenen Dritten)

$\models \varphi \land (\varphi \rightarrow \psi )\rightarrow \psi$ (Modus ponens)

$\models (\varphi \rightarrow \psi )\leftrightarrow (\neg \psi \rightarrow \neg \varphi )$ (Kontraposition)

$\models \bot \rightarrow \varphi$ (Ex falso Quodlibet, aus Falschem folgt alles)

Als Beispiel hier die Wahrheitstafel für die Kontraposition, die häufig für Beweise genutzt wird:

$(\varphi$	$\rightarrow$	$\psi )$	$\leftrightarrow$	$(\neg$	$\psi$	$\rightarrow$	$\neg$	$\varphi )$
W	W	W	W	F	W	W	F	W
W	F	F	W	W	F	F	F	W
F	W	W	W	F	W	W	W	F
F	W	F	W	W	F	W	W	F
1	7	2	9	5	3	8	6	4

In der letzten Zeile ist die Reihenfolge angegeben, in der die Spalten ausgefüllt werden. Sie entspricht dem Aufbau der Formeln!

Boolesche Algebra

Weitere Sätze für die Junktoren $\top$,$\bot$, $\land$, $\lor$ und $\neg$:

$\models (\varphi \land \varphi )\leftrightarrow \varphi$ (Idempotenz)

$\models (\varphi \land \psi )\leftrightarrow (\psi \land \varphi )$ (Kommutativität)

$\models (\varphi \land \psi )\land \theta \leftrightarrow \varphi \land (\psi \land \theta )$ (Assoziativität)

$\models \varphi \land (\psi \lor \theta )\leftrightarrow (\varphi \land \psi )\lor (\varphi \land \theta )$ (Distributivität)

$\models \neg (\varphi \land \psi )\leftrightarrow \neg \varphi \lor \neg \psi$ (De Morgansche Gesetze)

$\models \varphi \land \top \leftrightarrow \varphi$ (Neutrales Element)

$\models \varphi \land \neg \varphi \leftrightarrow \bot$ (Komplement)

Diese Sätze gelten ebenfalls, wenn man die Junktoren $\land$ mit $\lor$ und $\top$ mit $\bot$ vertauscht. Eine Struktur, in der diese Sätze gelten, wird Boolesche Algebra genannt. Die Potenzmenge ${\mathcal {P}}(G)$ ist die Menge aller Teilmengen der Grundmenge $G$. Sie bildet zusammen mit $G$, $\varnothing$, $\cap$, $\cup$ und ${\mathcal {C}}$ (Grundmenge, leere Menge, Durchschnitt, Vereinigung und Komplement relativ zu $G$) ebenfalls eine Boolesche Algebra. Die Wirkung der Operatoren kann in sogenannten Venn-Diagrmmen veranschaulicht werden:

Grundmenge	Leere Menge	Durchschnitt	Vereinigung	Komplement
$\top$	$\bot$	$\land$	$\lor$	$\neg$

In der letzten Zeile haben wir den entsprechenden Junktor notiert. Hat $G$ nur ein Element ist ${\mathcal {P}}(G)$ auch ein Modell der Aussagenlogik!

Weitere Junktoren

Es gibt weitere Junktoren ausser denen, die wir bisher behandelt haben.

Definierbarkeit von Junktoren

Die Junktoren unserer Sprache lassen sich teilweise aufeinander zurückführen. So gilt beispielsweise, wie man mit einer Wahrheitstafel leicht beweist:

$\models (\varphi \rightarrow \psi )\leftrightarrow (\neg \varphi \lor \psi )$

Wir könnten also die Subjunktion zunächst aus der Sprache der Aussagenlogik weglassen und durch die folgende Definition wieder einführen:

Definition: $\varphi \rightarrow \psi :=\neg \varphi \lor \psi$

Auch die Bijunktion und sogar die Disjunktion sind mit Hilfe von $\neg$ und $\land$ definierbar:

Definition: $\varphi \leftrightarrow \psi :=(\varphi \rightarrow \psi )\land (\psi \rightarrow \varphi )$

Definition: $\varphi \lor \psi :=\neg (\neg \varphi \land \neg \psi )$

Hätten wir in unserer Sprache nur $\neg$ und $\land$, würden wir zunächst $\lor$ definieren, dann $\rightarrow$ und schliesslich $\leftrightarrow$.

Es ist auch möglich, weitere Junktoren zu definieren, beispielsweise die umgekehrte Subjunktion $\leftarrow$:

Definition: $\varphi \leftarrow \psi :=\psi \rightarrow \varphi$

Entweder-Oder

$\varphi \veebar \psi$ ist nur dann Wahr, wenn genau eine der beiden Teilformeln Wahr ist. Es wird daher auch Exklusives Oder genannt. Als Symbol für diesen Junktor wird auch $\nleftrightarrow$ oder ${\dot {\lor }}$ verwendet.

$\varphi$	$\psi$	$\varphi \veebar \psi$
W	W	F
W	F	W
F	W	W
F	F	F

Satz: $\models (\varphi \veebar \psi )\leftrightarrow \neg (\varphi \leftrightarrow \psi )$

Satz: $\models (\varphi \veebar \psi )\leftrightarrow (\varphi \land \neg \psi )\lor (\neg \varphi \land \psi )$

Shefferstrich

$\varphi \mid \psi$ ist Wahr, wenn einer der beiden Teilformeln nicht Wahr ist. Dieser Junktor wird auch Nand (nicht und) genannt und mit dem Symbol $\uparrow$ bezeichnet.

$\varphi$	$\psi$	$\varphi \mid \psi$
W	W	F
W	F	W
F	W	W
F	F	W

Satz: $\models (\varphi \mid \psi )\leftrightarrow \neg (\varphi \land \psi )$

Der Shefferstrich wurde benannt nach dem amerikanischen Mathematiker Henry Maurice Sheffer, der zeigte, dass sich die anderen Junktoren mit Hilfe des Shefferstrich definieren lassen. Es gilt nämlich:

$\models \neg \varphi \leftrightarrow (\varphi \mid \varphi )$

$\models \varphi \land \psi \leftrightarrow \neg (\varphi \mid \psi )$

Damit lassen sich $\neg$ und $\land$ definieren und somait auch die anderen Junktoren.

Weder-Noch

$\varphi \downarrow \psi$ ist Wahr, wenn beide Teilformeln Falsch ist. Dieser Junktor wird nach dem amerikanischen Mathematiker Charles S. Peirce Peircepfeil oder Nor (nicht oder) genannt.

$\varphi$	$\psi$	$\varphi \downarrow \psi$
W	W	F
W	F	F
F	W	F
F	F	W

Satz: $\models (\varphi \downarrow \psi )\leftrightarrow \neg (\varphi \lor \psi )$

Auch mit dem Peircepfeil lassen sich $\neg$ und $\land$ definieren:

$\models \neg \varphi \leftrightarrow (\varphi \downarrow \varphi )$

$\models \varphi \land \psi \leftrightarrow \neg (\varphi \downarrow \psi )$

Zweistellige Junktoren

Junktoren verbinden unterschiedlich viele Teilformeln zu einer neuen Formel. Bei $\land$, $\lor$, $\rightarrow$ und $\leftrightarrow$ sind es zwei, bei $\neg$ nur eine. Man sagt ein Junktor ist 2-stellig bzw. 1-stellig. $\top$ und $\bot$ sind 0-stellig, sie haben überhaupt keine Teilformeln.

Es gibt vier verschiedene einstellige Junktoren. Von diesen ist nur die Negation in Spalte 3 von Interesse.

${\boldsymbol {\phi }}$	1	2	3	4
W	W	W	F	F
F	W	F	W	F
Junktor:			${\boldsymbol {\neg }}$

Die folgende Wahrheitstafel zeigt, dass es genau 16 verschiedene zweistellige Junktoren gibt. Soweit es ein gebräuchliches Symbol für einen Junktor gibt, ist es in der letzten Zeile eingetragen:

${\boldsymbol {\varphi }}$	${\boldsymbol {\psi }}$	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16
W	W	W	W	W	W	W	W	W	W	F	F	F	F	F	F	F	F
W	F	W	W	W	W	F	F	F	F	W	W	W	W	F	F	F	F
F	W	W	W	F	F	W	W	F	F	W	W	F	F	W	W	F	F
F	F	W	F	W	F	W	F	W	F	W	F	W	F	W	F	W	F
Junktor:			${\boldsymbol {\lor }}$	${\boldsymbol {\leftarrow }}$		${\boldsymbol {\rightarrow }}$		${\boldsymbol {\leftrightarrow }}$	${\boldsymbol {\land }}$	${\boldsymbol {\mid }}$	${\boldsymbol {\veebar }}$					${\boldsymbol {\downarrow }}$

Für die bisher nicht behandelten Junktoren geben wir im Folgenden eine Definition an. Dabei steht $\odot$ als Platzhalter für den Junktor, wenn kein Symbol angegeben ist.

Definition für Spalte 1: $\varphi \odot \psi :=\top$

Definition für Spalte 4: $\varphi \odot \psi :=\varphi$

Definition für Spalte 6: $\varphi \odot \psi :=\psi$

Definition für Spalte 11: $\varphi \odot \psi :=\neg \psi$

Definition für Spalte 12: $\varphi \odot \psi :=\neg (\varphi \rightarrow \psi )$

Definition für Spalte 13: $\varphi \odot \psi :=\neg \varphi$

Definition für Spalte 14: $\varphi \odot \psi :=\neg (\varphi \leftarrow \psi )$

Definition für Spalte 16: $\varphi \odot \psi :=\bot$

Beweis: Sei $\odot$ ein beliebiger Junktor mit den Teilformeln $\varphi _{1}$,$\varphi _{2}$, ..., $\varphi _{n}$. Für jede Zeile i, mit i = 1, ..., m, in denen $\odot$ wahr wird, bilden wir die Formel

$\psi _{i}:=\vartheta _{1}\land \vartheta _{2}\land ...\land \vartheta _{n}$, wobei

$\vartheta _{x}:={\begin{cases}\varphi _{x},&{\mathsf {wenn}}\;\varphi _{x}\;{\mathsf {mit\;W\;belegt\;wird,}}\\\neg \varphi _{x},&{\mathsf {wenn}}\;\varphi _{x}\;{\mathsf {mit\;F\;belegt\;wird.}}\end{cases}}$

Dann definieren wir $\odot (\varphi _{1},\varphi _{2},...,\varphi _{n}):=\psi _{1}\lor \psi _{2}\lor ...\lor \psi _{m}$ ✔

Als Beispiel zeigen wir, wie das dreistellige Entweder-Oder definiert werden kann, das nur dann Wahr ist wenn genau eine der drei Teilformeln $\varphi$, $\psi$ oder $\vartheta$ Wahr ist:

$\odot (\varphi ,\psi ,\vartheta ):=(\varphi \land \neg \psi \land \neg \vartheta )\lor (\neg \varphi \land \psi \land \neg \vartheta )\lor (\neg \varphi \land \neg \psi \land \vartheta )$

Der Sequenzenkalkül

Ein Kalkül ist ein formalisiertes Regelsystem, in dem aus Zeichenreihen mit Hilfe von Regeln weitere Zeichenreihen erzeugt werden können. Beispielsweise ist die eingangs definierte aussagenlogische Sprache ein Kalkül. Mit Hilfe der Grammatik werden die Zeichenreihen erzeugt, die Formeln sind. Wichtig dabei ist, dass die Regeln ohne Kenntnis irgend einer Bedeutung angewendet werden können. Die Anwendung einer Regel erfolgt rein schematisch und sollte auch von einer Maschine durchgeführt werden können.

Auch die Ermittlung der Wahrheitswerte von mit Junktoren zusammengesetzten Formeln mit Hilfe von Wahrheitstafeln ist ein Kalkül.

In diesem Abschnitt werden wir einen Kalkül vorstellen, mit dem die gültigen Formeln der Aussagenlogik erzeugt werden können. Er wurde 1934 vom deutschen Mathematiker Gerhard Gentzen entwickelt, der ihn als "Kalkül des natürlichen Schliessens" bezeichnete. Er wird Sequenzenkalkül genannt, weil die Zeichenreihen ursprünglich als Folgen von Formeln notiert werden.

Im Weiteren legen wir eine Sprache mit $\kappa$-vielen Formeln zu Grunde und betrachten die Implikation $\rightarrow$ und die Bijunktion $\leftrightarrow$ als definierte Junktoren, siehe Abschnitt "Eine formale Sprache (Syntax)"

Definitionen

Sequenz

Definition: Seien $\Gamma$ und $\Delta$ Formelmengen.

Dann nennen wir $\Gamma \vdash \Delta$ eine Sequenz oder Beweiszeile.

Schreibweisen

Statt $\lbrace \varphi _{1},\varphi _{2},\dotsc ,\varphi _{n}\rbrace \vdash \lbrace \psi _{1},\psi _{2},\dotsc ,\psi _{m}\rbrace$ schreiben wir einfach $\varphi _{1},\varphi _{2},\dotsc ,\varphi _{n}\vdash \psi _{1},\psi _{2},\dotsc ,\psi _{m}$, lassen also die Klammern $\lbrace \;\rbrace$ weg.

Mit   $\Gamma ,\varphi \vdash \Delta ,\psi$   ist   $\Gamma \cup \lbrace \varphi \rbrace \vdash \Delta \cup \lbrace \psi \rbrace$   gemeint.

Ein wichtiger Spezialfall ist   $\Gamma \vdash \varphi$   (aus $\Gamma$ folgt $\varphi$).

$\vdash \varphi$   steht für   $\varnothing \vdash \varphi$   ($\varnothing$ ist die leere Menge).

Anmerkung: Die Ähnlichkeit von $\vdash$ und $\models$ ist kein Zufall, sondern beabsichtigt!

Grundregeln

Der Kalkül für die Aussagenlogik hat folgende Regeln:

Annahmenregel
$\Gamma ,\varphi \vdash \varphi ,\Delta$

Regeln für Verum und Falsum
$\Gamma ,\bot \vdash \Delta$	$\Gamma \vdash \top ,\Delta$

Regeln für die Negation
${\frac {\Gamma \vdash \varphi ,\Delta }{\Gamma ,\neg \varphi \vdash \Delta }}$	${\frac {\Gamma ,\varphi \vdash \Delta }{\Gamma \vdash \neg \varphi ,\Delta }}$

Regeln für die Konjunktion
${\frac {\Gamma ,\varphi ,\psi \vdash \Delta }{\Gamma ,\varphi \land \psi \vdash \Delta }}$	${\frac {\Gamma \vdash \varphi ,\Delta \qquad \Gamma \vdash \psi ,\Delta }{\Gamma \vdash \varphi \land \psi ,\Delta }}$

Regeln für die Disjunktion
${\frac {\Gamma ,\varphi \vdash \Delta \qquad \Gamma ,\psi \vdash \Delta }{\Gamma ,\varphi \lor \psi \vdash \Delta }}$	${\frac {\Gamma \vdash \varphi ,\psi ,\Delta }{\Gamma \vdash \varphi \lor \psi ,\Delta }}$

Ableitbarkeit

Definition: Eine Sequenz $\Gamma \vdash \Delta$ heisst ableitbar, wenn es eine endliche Folge von Sequenzen

1.   $\Gamma _{1}\vdash \Delta _{1}$

2.   $\Gamma _{2}\vdash \Delta _{2}$

3.   $\Gamma _{3}\vdash \Delta _{3}$

$\dotsm$

n.   $\Gamma _{n}\vdash \Delta _{n}$

mit endlichen Formelmengen $\Gamma _{i}$ und $\Delta _{i}$ gibt, bei der jede Zeile aus den vorangehenden Zeilen durch eine Regel entsteht und für die letzte Zeile $\Gamma _{n}\subseteq \Gamma$ und $\Delta _{n}\subseteq \Delta$ gilt.
Eine solche Folge heisst ein Beweis für $\Gamma \vdash \Delta$.

Strukturregeln

Nach Definition von $\vdash$ sind $\Gamma$ und $\Delta$ Mengen. Daraus ergeben sich einige Regeln, die Strukturregeln genannt werden. Von diesen Regeln werden wir im Weiteren stillschweigend Gebrauch machen.

Satz:

Verdünnungsregel
${\frac {\Gamma \vdash \Delta }{\Gamma ,\varphi \vdash \Delta }}$	${\frac {\Gamma \vdash \Delta }{\Gamma \vdash \varphi ,\Delta }}$

Beweis: Nach Voraussetzung gibt es eine Ableitung für $\Gamma \vdash \Delta$. In dieser Ableitung können wir überall $\Gamma$ durch $\Gamma \cup \lbrace \varphi \rbrace$ ersetzen und erhalten so $\Gamma ,\phi \vdash \Delta$. Die andere Regel wird entsprechend bewiesen. ✔

Satz:

Vertauschung
${\frac {\Gamma ,\varphi ,\psi \vdash \Delta }{\Gamma ,\psi ,\varphi \vdash \Delta }}$	${\frac {\Gamma \vdash \varphi ,\psi ,\Delta }{\Gamma \vdash \psi ,\varphi ,\Delta }}$

Beweis: Links von $\vdash$ steht immer dieselbe Menge $\Gamma \cup \lbrace \varphi ,\psi \rbrace$. Im anderen Fall steht rechts $\lbrace \varphi ,\psi \rbrace \cup \Delta$.✔

Satz:

Wiederholung
${\frac {\Gamma ,\varphi ,\varphi \vdash \Delta }{\Gamma ,\varphi \vdash \Delta }}$	${\frac {\Gamma \vdash \varphi ,\varphi ,\Delta }{\Gamma \vdash \varphi ,\Delta }}$

Beweis: Links von $\vdash$ steht immer dieselbe Menge $\Gamma \cup \lbrace \varphi \rbrace$. Im anderen Fall steht rechts $\lbrace \varphi \rbrace \cup \Delta$.✔

Weitere Regeln

Wir zeigen einige Regeln, die aus den gegebenen Regeln abgeleitet werden können. Auch diese Regeln können dann in weiteren Beweisen verwendet werden, ohne dass die Menge der ableitbaren Sequenzen zu vergrössern.

Die Subjunktion betrachten wir als definierten Junktor $\varphi \rightarrow \psi :=\neg \varphi \lor \psi$. Für sie gelten folgende Regeln:

Regeln für die Subjunktion
${\frac {\Gamma ,\psi \vdash \Delta \qquad \Gamma \vdash \varphi ,\Delta }{\Gamma ,\varphi \rightarrow \psi \vdash \Delta }}$	${\frac {\Gamma ,\varphi \vdash \psi ,\Delta }{\Gamma \vdash \varphi \rightarrow \psi ,\Delta }}$

Beweis:

1.	$\Gamma ,\psi \vdash \Delta$	Voraussetzung
2.	$\Gamma \vdash \varphi ,\Delta$	Voraussetzung
3.	$\Gamma ,\neg \varphi \vdash \Delta$	linke Negationsregel
4.	$\Gamma ,\neg \varphi \lor \psi \vdash \Delta$	linke Disjunktionsregel auf 3. und 1.
5.	$\Gamma ,\varphi \rightarrow \psi \vdash \Delta$	Definition von $\rightarrow$

1.	$\Gamma ,\varphi \vdash \psi ,\Delta$	Voraussetzung
2.	$\Gamma \vdash \neg \varphi ,\psi ,\Delta$	rechte Negationsregel
3.	$\Gamma \vdash \neg \varphi \lor \psi ,\Delta$	rechte Disjunktionssregel
4.	$\Gamma \vdash \varphi \rightarrow \psi ,\Delta$	Definition von $\rightarrow$

Beweis beendet. ✔

Die Bijunktion betrachten wir als definierten Junktor $\varphi \leftrightarrow \psi :=(\varphi \rightarrow \psi )\land (\psi \rightarrow \varphi )$.

Für sie gelten folgende Regeln:

Regeln für die Bijunktion
${\frac {\Gamma ,\varphi ,\psi \vdash \Delta \qquad \Gamma \vdash \varphi ,\psi ,\Delta }{\Gamma ,\varphi \leftrightarrow \psi \vdash \Delta }}$	${\frac {\Gamma ,\varphi \vdash \psi ,\Delta \qquad \Gamma ,\psi \vdash \varphi ,\Delta }{\Gamma \vdash \phi \leftrightarrow \psi ,\Delta }}$

Beweis:

1.	$\Gamma ,\varphi ,\psi \vdash \Delta$	Voraussetzung
2.	$\Gamma \vdash \varphi ,\psi ,\Delta$	Voraussetzung
3.	$\Gamma ,\varphi \vdash \varphi ,\Delta$	Annahmenregel
4.	$\Gamma ,\psi \rightarrow \varphi \vdash \varphi ,\Delta$	Linke Subjunktionsregel auf 3. und 2.
5.	$\Gamma ,\psi \vdash \psi ,\Delta$	Annahmenregel
6.	$\Gamma ,\psi ,\psi \rightarrow \varphi \vdash \Delta$	Linke Subjunktionsregel auf 1. und 5.
7.	$\Gamma ,\phi \rightarrow \psi ,\psi \rightarrow \varphi \vdash \Delta$	Linke Subjunktionsregel auf 6. und 4.
8.	$\Gamma ,(\varphi \rightarrow \psi )\land (\psi \rightarrow \varphi )\vdash \Delta$	Linke Konjunktionsregel auf 7.
9.	$\Gamma ,\varphi \leftrightarrow \psi \vdash \Delta$	Definition von $\leftrightarrow$

1.	$\Gamma ,\varphi \vdash \psi ,\Delta$	Voraussetzung
2.	$\Gamma ,\psi \vdash \varphi ,\Delta$	Voraussetzung
3.	$\Gamma \vdash \varphi \rightarrow \psi ,\Delta$	Rechte Subjunktionsregel auf 1.
4.	$\Gamma \vdash \psi \rightarrow \varphi ,\Delta$	Rechte Subjunktionsregel auf 2.
5.	$\Gamma \vdash \varphi \rightarrow \psi \land \psi \rightarrow \varphi ,\Delta$	Rechte Konjunktionsregel auf 3. und 4.
6.	$\Gamma \vdash \varphi \leftrightarrow \psi ,\Delta$	Definition von $\leftrightarrow$

Beweis beendet. ✔

Korrektheit

Definition: Eine Sequenz $\Gamma \vdash \Delta$ heisst korrekt, wenn auch $\Gamma \models \Delta$ gilt.

Beweis:

Wir führen den Beweis durch Induktion über den Aufbau der Grundregeln für den Sequenzenkalkül.

Induktionsanfang: Die Annahmenregel ist offensichtlich korrekt, also: $\Gamma ,\phi \models \phi ,\Delta$. Da alle Bewertungen ${\mathcal {J}}$ die Formel $\bot$ mit Falsch und $\top$ mit Wahr bewerten sind auch die Regeln für Falsum und Verum korrekt: $\Gamma ,\bot \models \Delta$ und $\Gamma \models \top ,\Delta$

Induktionsschluss: Zu zeigen ist, dass die Regeln für die Junktoren $\neg$, $\land$ und $\lor$ die Korrektheit erhalten: sind die Sequenzen korrekt, so auch die erzeugte Sequenz.

Negation:
Gelte nun $\Gamma \models \varphi ,\Delta$ und sei ${\mathcal {J}}$ eine beliebige Bewertung die $\Gamma \cup \lbrace \neg \phi \rbrace$ erfüllt. Dann erfüllt ${\mathcal {J}}$ auch $\Gamma$ und belegt $\varphi$ mit Falsch. Nach Voraussetzung gibt es daher eine Formel $\psi$ aus $\lbrace \varphi \rbrace \cup \Delta$, die ${\mathcal {J}}$ mit Wahr belegt. Das kann aber nicht $\varphi$ sein, also ist $\psi$ aus $\Delta$. Das zeigt $\Gamma ,\neg \varphi \models \Delta$.

Sei nun $\Gamma ,\varphi \models \Delta$ und ${\mathcal {J}}$ eine Bewertung die $\Gamma$ erfüllt. Belegt ${\mathcal {J}}$ $\varphi$ mit Falsch, sind wir fertig, denn dann belegt ${\mathcal {J}}$ $\neg \varphi$ mit Wahr. Wenn ${\mathcal {J}}$ $\varphi$ mit Wahr bewertet, gibt es nach Voraussetzung eine Formel $\psi$ aus $\Delta$ die ${\mathcal {J}}$ mit Wahr bewertet. Insgesamt gilt $\Gamma \models \neg \varphi ,\Delta$.

Konjunktion:
Sei nun $\Gamma ,\varphi ,\psi \models \Delta$ und ${\mathcal {J}}$ eine Bewertung die $\Gamma \cup \lbrace \varphi \land \psi \rbrace$ erfüllt. Dann belegt ${\mathcal {J}}$ auch $\varphi$ und $\psi$ mit Wahr, also gibt es nach Vorausstzung eine Formel $\vartheta$ aus $\Delta$ die ${\mathcal {J}}$ mit Wahr belegt. Das zeigt $\Gamma ,\varphi \land \psi \models \Delta$.

Sei nun $\Gamma \models \varphi ,\Delta$ und $\Gamma \models \psi ,\Delta$ und ${\mathcal {J}}$ erfüllt $\Gamma$. Erfüllt ${\mathcal {J}}$ eine Formel aus $\Delta$ ist nichts mehr zu zeigen. Ist das nicht der Fall, erfüllt ${\mathcal {J}}$ $\varphi$ und $\psi$ und somit auch $\varphi \land \psi$. Also ist $\Gamma \models \varphi \land \psi ,\Delta$.

Disjunktion:
Gelte nun $\Gamma ,\varphi \models \Delta$ und $\Gamma ,\psi \models \Delta$ und ${\mathcal {J}}$ erfüllt $\Gamma \cup \lbrace \varphi \lor \psi \rbrace$, Dann erfüllt ${\mathcal {J}}$ $\varphi$ oder $\psi$. In beiden Fällen ergibt sich mit der Voraussetzung, dass es eine Formel $\vartheta$ aus $\Delta$ gibt, die von ${\mathcal {J}}$ erfüllt wird. Daher gilt $\Gamma ,\varphi \lor \psi \models \Delta$.

Sei schliesslich $\Gamma \models \varphi ,\psi ,\Delta$ und ${\mathcal {J}}$ erfülle $\Gamma$. Dann folgt aus der Voraussetzung, dass ${\mathcal {J}}$ $\varphi$, $\psi$ oder eine Formel $\vartheta$ aus $\Delta$ erfüllt. ${\mathcal {J}}$ erfüllt aber dann auch eine Formel aus $\lbrace \varphi \lor \psi \rbrace \cup \Delta$ und somit gilt $\Gamma \models \varphi \lor \psi ,\Delta$. ✔

Der Vollständigkeitssatz

Die Korrektheit des Kalküls besagt, dass nur gültige Sequenzen abgeleitet werden können. Von grosser Bedeutung ist, dass auf diese Weise alle logischen Folgerungen abgeleitet werden können! Es gilt also auch die Umkehrung der Korrektheit:

Das Ableiten ist ein maschinell prüfbares Verfahren, das in endlich vielen Schritten aus endlich vielen Formeln eine korrekte Folgerung erzeugt. Das ist genau das, was in der Mathematik als Beweis gilt. Der Satz besagt also, dass sich alle logischen Folgerungen auf diese Weise beweisen lassen.

Wir beweisen den Satz nach einer Idee des amerikanischen Logikers Leon Henkin. Dazu nehmen wir an, dass $\Gamma \nvdash \Delta$ gilt und konstruieren ein Bewertung ${\mathcal {J}}$, die $\Gamma \nvDash \Delta$ zeigt: ${\mathcal {J}}$ macht also alle Formeln aus $\Gamma$ wahr und alle Formeln aus $\Delta$ falsch. Wir vergrössern $\Gamma$ und $\Delta$ zu $\Gamma ^{*}$ und $\Delta ^{*}$, so dass diese maximal sind aber weiterhin $\Gamma ^{*}\nvdash \Delta ^{*}$ gilt. Mit diesen Formelmengen wird dann die Bewertung definiert.

Beweis:

Wir zeigen die Kontraposition. Sei also $\Gamma \nvdash \Delta$, d.h. aus $\Gamma$ ist $\Delta$ nicht ableitbar, und $\kappa$ die Mächtigkeit der Sprache. Weiterhin sei $\varphi _{i}$ mit $i\leq \kappa$ eine Aufzählung aller Formeln. Wir definieren rekursiv $\Gamma _{i}$ und $\Delta _{i}$ für $i\leq \kappa$.

• $\Gamma _{0}:=\Gamma$ und $\Delta _{0}:=\Delta$.
• Für Limeszahlen $\lambda$ sei: $\Gamma _{\lambda }:=\bigcup \{\Gamma _{i}\,|\,i<\lambda \}$ und $\Delta _{i}:=\bigcup \{\Delta _{i}\,|\,i<\lambda \}$.
• Für Nachfolgerzahlen $i+1$ werden drei Fälle unterschieden:
  
  • wenn $\Gamma _{i},\varphi _{i}\nvdash \Delta _{i}$, dann $\Gamma _{i+1}:=\Gamma _{i}\cup \{\varphi _{i}\}$ und $\Delta _{i+1}:=\Delta _{i}$
  • wenn $\Gamma _{i},\varphi _{i}\vdash \Delta _{i}$ und $\Gamma _{i}\nvdash \varphi _{i},\Delta$, dann $\Gamma _{i+1}:=\Gamma _{i}$ und $\Delta _{i+1}:=\Delta _{i}\cup \{\varphi _{i}\}$
  • wenn $\Gamma _{i},\varphi _{i}\vdash \Delta _{i}$ und $\Gamma _{i}\vdash \varphi _{i},\Delta$, dann $\Gamma _{i+1}:=\Gamma _{i}$ und $\Delta _{i+1}:=\Delta _{i}$

Wir werden später sehen, dass der letzte Fall nicht auftritt und setzen nun: $\Gamma ^{*}:=\Gamma _{\kappa }$ und $\Delta ^{*}:=\Delta _{\kappa }$

Beweis: Durch Induktion über $\kappa$ folgt: $\Gamma _{i}\nvdash \Delta _{i}$ für alle $i\leq \kappa$. Für $i=0$ gilt das nach Voraussetzung und für Nachfolgerzahlen nach Konstruktion. Gälte für Limeszahlen $\Gamma _{\lambda }\vdash \Delta _{\lambda }$, dann gälte $\Gamma _{i}\vdash \Delta _{i}$ für ein $i<\lambda$, denn für die Ableitung werden nur endlich viele Formeln aus $\Gamma _{\lambda }$ und $\Delta _{\lambda }$ benötigt. Das widerspricht aber der Induktionsvoraussetzung für $\lambda$.

Insbesondere gilt also $\Gamma _{\kappa }=\Gamma ^{*}\nvdash \Delta ^{*}=\Delta _{\kappa }$.✔

Beweis: Die eine Richtung ($\Rightarrow$) folgt mit der Nichtableitbarkeit nach Lemma 1.

Sei $\varphi \notin \Gamma ^{*}$ und $i$ der Index von $\varphi$ in der Aufzählung aller Formeln. Dann ist $\Gamma _{i},\varphi \vdash \Delta _{i}$, sonst wäre $\phi \in \Gamma _{i+1}\subseteq \Gamma ^{*}$. Also gilt $\Gamma ^{*},\varphi \vdash \Delta ^{*}$.

Sei nun $\varphi \notin \Delta ^{*}$. Ist $\varphi \in \Gamma ^{*}$, dann folgt mit der Annahmenregel $\Gamma ^{*}\vdash \varphi ,\Delta ^{*}$. Sei also $\varphi \notin \Gamma ^{*}$ und $i$ der Index von $\varphi$. Dann ist $\Gamma _{i},\varphi \vdash \Delta _{i}$ und $\Gamma _{i}\vdash \varphi ,\Delta _{i}$, sonst wäre $\varphi \in \Delta _{i+1}\subseteq \Delta ^{*}$. Also gilt auch in diesem Fall $\Gamma ^{*}\vdash \varphi ,\Delta ^{*}$. ✔

Beweis:

1. folgt mit der Annahmenregel und Lemma 1.
2. ergibt sich mit den Regeln für Verum und Falsum, sowie Lemma 1.
3. Sei $\varphi \notin \Delta ^{*}$. Mit Lemma 2 folgt $\Gamma ^{*}\vdash \varphi ,\Delta ^{*}$ und mit der Linken Negationsregel $\Gamma ^{*},\neg \varphi \vdash \Delta ^{*}$. Erneut mit Lemma 2 folgt $\neg \varphi \notin \Gamma ^{*}$.
4. Sei $\varphi \notin \Gamma ^{*}$. Mit Lemma 2 folgt $\Gamma ^{*},\varphi \vdash \Delta ^{*}$ und mit der Rechten Negationsregel $\Gamma ^{*}\vdash \neg \varphi ,\Delta ^{*}$. Erneut mit Lemma 2 folgt $\neg \varphi \notin \Delta ^{*}$.
5. Sei $\varphi \notin \Gamma ^{*}$ oder $\psi \notin \Gamma ^{*}$. Mit Lemma 2 folgt $\Gamma ^{*},\varphi \vdash \Delta ^{*}$ oder $\Gamma ^{*},\psi \vdash \Delta ^{*}$, also mit Verdünnung auch $\Gamma ^{*},\varphi ,\psi \vdash \Delta ^{*}$. Mit der Linken Konjunktionsregel folgt $\Gamma ^{*},\varphi \land \psi \vdash \Delta ^{*}$ und wieder mit Lemma 2: $\varphi \land \psi \notin \Gamma ^{*}$.
6. Sei $\varphi \notin \Delta ^{*}$ und $\psi \notin \Delta ^{*}$. Mit Lemma 2 folgt $\Gamma ^{*}\vdash \varphi ,\Delta ^{*}$ und $\Gamma ^{*}\vdash \psi ,\Delta ^{*}$. Mit der Rechten Konjunktionsregel folgt $\Gamma ^{*}\vdash \varphi \land \psi ,\Delta ^{*}$ und erneut mit Lemma 2: $\varphi \land \psi \notin \Delta ^{*}$.
7. Sei $\varphi \notin \Gamma ^{*}$ und $\psi \notin \Gamma ^{*}$. Mit Lemma 2 folgt $\Gamma ^{*},\varphi \vdash \Delta ^{*}$ und $\Gamma ^{*},\psi \vdash \Delta ^{*}$. Mit der Linken Disjunktionsregel folgt $\Gamma ^{*},\varphi \lor \psi \vdash \Delta ^{*}$ und mit Lemma 2; $\varphi \lor \psi \notin \Gamma ^{*}$.
8. Sei $\varphi \notin \Delta ^{*}$ oder $\psi \notin \Delta ^{*}$. Mit Lemma 2 folgt $\Gamma ^{*}\vdash \varphi ,\Delta ^{*}$ oder $\Gamma ^{*}\vdash \psi ,\Delta ^{*}$ und mit Verdünnng $\Gamma ^{*}\vdash \varphi ,\psi ,\Delta ^{*}$. Mit der Rechten Disjunktionsregel folgt $\Gamma ^{*}\vdash \varphi \lor \psi ,\Delta ^{*}$ und mit Lemma 2: $\varphi \lor \psi \notin \Delta ^{*}$.

Damit ist der Beweis beendet. ✔

Die eben gezeigten Eigenschaften reichen aus, um eine Bewertung ${\mathcal {J^{*}}}$ zu definieren, die $\Gamma ^{*}\nvDash \Delta ^{*}$ beweist:.

Definition der Bewertung ${\mathcal {J^{*}}}$:

Für alle Aussagenkonstanten $\alpha$ sei ${\mathcal {J^{*}}}(\alpha )$ Wahr genau dann, wenn $\alpha \in \Gamma ^{*}$.

Beweis durch Induktion über den Aufbau der Formeln:

• Für Aussagenkonstanten gilt die Behauptung nach Definition von ${\mathcal {J^{*}}}$.
• Für Verum und Falsum gilt die Behauptung wegen Lemma 3 Punkt 2.
• Gelte $\neg \varphi \in \Gamma ^{*}$. Dann gilt nach Lemma 3 Punkt 3. $\varphi \in \Delta ^{*}$ und nach Induktionsvoraussetzung ist ${\mathcal {J^{*}}}(\varphi )$ Falsch. Also ist ${\mathcal {J^{*}}}(\neg \varphi )$ Wahr.
  Ist $\neg \varphi \in \Delta ^{*}$, ist nach Lemma 3 Punkt 4. $\varphi \in \Gamma ^{*}$ und somit ${\mathcal {J^{*}}}(\varphi )$ Wahr. Also ist ${\mathcal {J^{*}}}(\neg \varphi )$ Falsch.
• Gelte $\varphi \land \psi \in \Gamma ^{*}$. Nach Lemma 3 Punkt 5. und Induktionsvoraussetzung sind dann ${\mathcal {J^{*}}}(\varphi )$ Wahr und ${\mathcal {J^{*}}}(\psi )$ Wahr. Also ist auch ${\mathcal {J^{*}}}(\varphi \land \psi )$ Wahr.
  Ist $\varphi \land \psi \in \Delta ^{*}$, ist nach Lemma 3 Punkt 6. und der Induktionsvoraussetzung ${\mathcal {J^{*}}}(\varphi )$ Falsch oder ${\mathcal {J^{*}}}(\psi )$ Falsch. Damit ist auch ${\mathcal {J^{*}}}(\phi \land \psi )$ Falsch.
• Gelte $\varphi \lor \psi \in \Gamma ^{*}$. Nach Lemma 3 Punkt 7. und Induktionsvoraussetzung ist dann ${\mathcal {J^{*}}}(\varphi )$ Wahr oder ${\mathcal {J^{*}}}(\psi )$ Wahr. Also ist auch ${\mathcal {J^{*}}}(\varphi \lor \psi )$ Wahr.
  Ist $\varphi \lor \psi \in \Delta ^{*}$, sind nach Lemma 3 Punkt 8. und der Induktionsvoraussetzung ${\mathcal {J^{*}}}(\varphi )$ Falsch und ${\mathcal {J^{*}}}(\psi )$ Falsch. Daher ist auch ${\mathcal {J^{*}}}(\varphi \lor \psi )$ Falsch.

Damit ist Lemma 4 bewiesen. ✔

Da ja $\Gamma \subseteq \Gamma ^{*}$ und $\Delta \subseteq \Delta ^{*}$ gilt auch:

Zusammen mit der Korrektheit des Kalküls gilt also:

Die Schnittregel

Eine Folgerung aus der Vollständigkeit unseres Kalküls ist, das wir die Schnittregel nutzen können, ohne die Menge der logischen Folgerungen zu vergrössern. Die Schnittregel erlaubt es, Formeln "herauszuschneiden", die in der Schlusszeile nicht mehr auftauchen:

Schnittregel
${\frac {\Gamma \vdash \varphi ,\Delta \qquad \Gamma ,\varphi \vdash \Delta }{\Gamma \vdash \Delta }}$

Beweis: Gelte also $\Gamma \vDash \varphi ,\Delta$ und $\Gamma \vDash \varphi ,\Delta$ und ${\mathcal {J}}$ efülle alle Formeln aus $\Gamma$. Dann erfüllt ${\mathcal {J}}$ wegen der ersten Voraussetzung $\varphi$ oder eine Formel aus $\Delta$. Im zweiten Fall sind wir fertig. Erfüllt ${\mathcal {J}}$ die Formel $\varphi$, so folgt aus der zweiten Voraussetzung, dass ${\mathcal {J}}$ eine Formel aus $\Delta$ erfüllt. Also gilt $\Gamma \vDash \Delta$. ✔

In der Mathematik wird die Schnittregel häufig in der folgenden Form verwendet: ${\frac {\Gamma \vdash \varphi \qquad \Gamma ,\varphi \vdash \psi }{\Gamma \vdash \psi }}$.

Kompaktheitssatz

Beweis: Die Richtung "$\Rightarrow$" ist trivial, denn wenn ${\mathcal {J}}$ alle Formeln von $\Gamma$ erfüllt, dann natürlich auch alle endlichen Teilmengen von $\Gamma$.

Für die Richtung "$\Leftarrow$" nehmen wir an, dass alle endlichen Teilmengen von $\Gamma$ erfüllbar sind, aber $\Gamma$ selbst nicht. Dann gilt $\Gamma \vDash \bot$ und nach dem Vollständigkeitssatz folgt $\Gamma \vdash \bot$. Für den Beweis werden aber nur endlich viele Formeln aus $\Delta \subseteq \Gamma$ benötigt, also gibt es eine endliche Teilmenge $\Delta$ mit: $\Delta \vdash \bot$ und $\Delta$ ist nicht erfüllbar. ↯