Einführung und Eliminierung von Konjunktionen und Disjunktionen

Eine der Techniken der klassischen Logik besteht in der Einführung und Eliminierung von Junktoren und Disjunktionen. Obwohl diese Techniken auf eine mehr oder weniger intuitive Weise ausgeführt werden, ist ihre Begründung nicht völlig trivial, doch sie lassen sich aus den Regeln der Aussagenlogik ableiten, die wir in früheren Lektionen bereits bewiesen haben. Formal lauten die Techniken zur Einführung und Eliminierung von Junktoren und Disjunktionen wie folgt:

Und ihre Herleitungen aus der Aussagenlogik sind wie folgt dargestellt:

∨-Einführung

∨-Eliminierung

∧-Einführung

∧-Eliminierung

Techniken der Widersprüche und Tautologien

Regel des ausgeschlossenen Dritten oder Tautologie (tau)

Ein weiteres auffälliges Merkmal der klassischen Logik ist die Eigenschaft des ausgeschlossenen Dritten (tertium non datur). Diese besagt, dass wenn zwei Aussagen vorliegen, von denen eine die andere verneint, notwendigerweise eine von beiden wahr sein muss; anders ausgedrückt: die Disjunktion zweier Aussagen, von denen eine die andere negiert, bildet notwendigerweise eine Tautologie. Formal wird dies wie folgt dargestellt:

\vdash (\neg\alpha \vee\alpha)

Und der Beweis ergibt sich leicht:

Eine andere Möglichkeit, das Prinzip des ausgeschlossenen Dritten zu formulieren, ist über das Gesetz des Widerspruchs, das besagt, dass eine Aussage nicht gleichzeitig wahr und falsch sein kann. Dieses wird formal wie folgt formuliert:

\vdash \neg(\neg\alpha \wedge \alpha)

Diese Eigenschaft bedarf keines Beweises – nicht, weil sie offensichtlich ist, sondern weil sie sich direkt aus der Definition der Konjunktion und dem Prinzip des ausgeschlossenen Dritten ergibt.

Widerspruchsregel oder Explosionsprinzip

Eine weitere bekannte Eigenschaft der klassischen Logik ist das Explosionsprinzip, das gewöhnlich durch den Satz „Aus widersprüchlichen Prämissen kann alles folgen“ ausgedrückt wird. Die Formulierung erfolgt meist in einer der folgenden beiden Varianten:

\{(\neg\alpha \wedge \alpha)\}\vdash \beta

\{\alpha, \neg\alpha\}\vdash \beta

Der Beweis dieser Regel ist einfach:

∨-Eliminierung3

Das Modus ponens kann auf zwei verschiedene Arten formuliert werden. Eine bekannte Form ist \{\alpha,(\alpha \rightarrow \beta)\}\vdash \beta. Die andere ist etwas weniger vertraut:

\{\alpha\}\vdash\beta \; \wedge \; \vdash \alpha \; \Longrightarrow \; \vdash \beta

Wenn wir uns auf diese zweite Form konzentrieren, lässt sich eine erweiterte Regel formulieren, die wir ∨-Eliminierung3 nennen, da sie einer Vereinfachung einer Disjunktion ähnelt. Diese Regel besagt: Wenn \gamma sowohl aus \alpha als auch aus \beta ableitbar ist (jeweils separat), und zusätzlich (\alpha \vee \beta) ein Theorem ist, dann ist auch \gamma ein Theorem. Formal lässt sich das so ausdrücken:

\{\alpha\}\vdash\gamma\; \wedge \; \{\beta\}\vdash\gamma \; \wedge \; \vdash (\alpha \vee \beta) \Longrightarrow \vdash \gamma

Der Beweis dieser Technik aus der klassischen Logik lautet wie folgt:

Beweise durch Fälle (cas)

Eine weitere Technik der klassischen Logik ist der Beweis durch Fälle. Wenn ein Ausdruck \beta sowohl aus einem anderen Ausdruck \alpha als auch aus dessen Negation hergeleitet werden kann, dann ist \beta notwendigerweise ein Theorem. Formal wird dies so dargestellt: \alpha \vdash \beta \; \wedge \; \neg\alpha \vdash \beta \Longrightarrow \vdash \beta. Der Beweis lautet wie folgt:

\begin{array}{rll} (1) & \alpha \vdash \beta &; Prämisse\\ (2) & \neg \alpha \vdash \beta &; Prämisse \\ (3) & \vdash \alpha \vee \neg\alpha &; TAU \\ (4) & \vdash \beta &; \vee-Eliminierung3(1,2,3) \end{array}

Reduktion ad absurdum (absurdo)

Eine der am häufigsten verwendeten Techniken der klassischen Logik in Beweisen, insbesondere in der Mathematik, ist die Reduktion ad absurdum. Sie besteht darin, dass wenn aus einem Ausdruck \alpha ein Widerspruch (eine Aussage und ihre Verneinung) abgeleitet werden kann, dann ist die Negation von \alpha eine Tautologie. Formal wird dies so formuliert: \{\alpha\}\vdash \beta \; \wedge \; \{\alpha\}\vdash \neg\beta \Longrightarrow \vdash \neg\alpha. Und dies lässt sich durch folgendes Argument zeigen: