Wir sind im Rahmen unseres Logikstudiums an einen Wendepunkt gelangt, denn hier beginnen wir mit der Betrachtung der deduktiven Systeme der Aussagenlogik. An diesem Punkt wird alles bisher Erarbeitete operativ und der wahre Geist der Logik tritt zutage, denn wir studieren das Wesen der Beweise. Es wird vorausgesetzt, dass du bereits gelernt hast, wie man logische Ausdrücke schreibt, und ein grundlegendes Verständnis der Aussagenlogik hast; falls dies nicht der Fall ist, empfiehlt es sich, die vorhergehenden Lektionen nochmals durchzugehen.

Anschließend werden wir untersuchen, wie sich die Ausdrücke der Aussagenlogik zueinander verhalten, um eine Ableitung zu bilden. Der Mechanismus, durch den diese Beziehungen konstruiert werden, ist das formale deduktive System.

Was ist ein formales deduktives System?

Formale deduktive Systeme, oder auch Kalkülsysteme genannt, bestehen aus drei grundlegenden Komponenten:

1. Eine formale Sprache.
2. Ein axiomatisches Schema.
3. Elementare Schlussregeln.

Wir haben bereits alles im Zusammenhang mit formalen Sprachen betrachtet. Jetzt ist es an der Zeit, die axiomatischen Schemata und die elementaren Schlussregeln einzuführen.

Für den Aufbau des deduktiven Systems des Aussagenkalküls beginnen wir mit dem Aufbau des deduktiven Systems basierend auf den Axiomen von Łukasiewicz, und als elementare Schlussregel verwenden wir den Modus Ponens.

Die Axiome von Łukasiewicz für die Aussagenlogik

Wenn \alpha, \beta und \gamma Ausdrücke des Aussagenkalküls sind, dann gelten die folgenden Ausdrücke als Axiome des Aussagenkalküls:

Der Modus Ponens: Das deduktive Antriebswerk des Aussagenkalküls

Wenn \alpha und \beta gültige Ausdrücke des Aussagenkalküls sind, dann besagt der Modus Ponens, dass sich aus \alpha und (\alpha \rightarrow \beta) \beta ableiten lässt. In Form einer Argumentation wird dies wie folgt dargestellt:

Hier wurde der Modus Ponens zwischen den Schritten (1) und (2) abgekürzt dargestellt durch die Schreibweise „MP(1,2)“, und die Zusammenfassung dessen wird durch die folgende Notation repräsentiert:

Daher gilt: \{\alpha, (\alpha \rightarrow \beta)\}\vdash \beta

Bald werden wir sehen, dass sich aus den Axiomen von Łukasiewicz und dem Modus Ponens sämtliche Ableitungstechniken des Aussagenkalküls konstruieren lassen. Diese fassen die grundlegenden Regeln des alltäglichen logischen Schließens zusammen und bilden die Fundamentbasis für die klassische Logik.

Argumentationen, Theoreme und Prämissen

In den deduktiven Systemen der Aussagenlogik werden Argumentationen (oder Ableitungen) ausgeführt, und diese bestehen aus einer Abfolge von Ausdrücken, bei denen jeder Ausdruck entweder eine Prämisse ist oder aus den Prämissen unter ausschließlicher Verwendung der Axiome von Łukasiewicz und des Modus Ponens abgeleitet wurde. Ein Theorem ist das Ergebnis einer Ableitung ohne Prämissen. Eine Prämisse kann jeder Ausdruck sein, der weder ein Axiom ist noch aus diesen abgeleitet wird. Im Allgemeinen, wenn wir eine Menge von Prämissen \Gamma und einen Ausdruck \alpha haben, der unter Verwendung eines Elements von \Gamma, der Axiome und des Modus Ponens gewonnen wird, schreibt man „\Gamma \vdash \alpha“ und man sagt:

aus \Gamma wird \alpha hergeleitet

Wenn \Gamma eine leere Menge ist, dann schreibt man anstelle von „\emptyset\vdash \alpha“ einfach „ \vdash \alpha „. Dies wird gelesen als „\alpha ist ein Theorem“. Diese Art, Theoreme darzustellen, kann auch auf die Darstellung der Axiome ausgeweitet werden, sodass, wenn \alpha, \beta und \gamma Ausdrücke sind, dann die Axiome von Łukasiewicz in folgender Form geschrieben werden können:

Deshalb sagt man, dass Axiome Aussagen sind, die aus sich selbst heraus offensichtlich sind, oder dass Theoreme Ausdrücke sind, die aus der leeren Menge abgeleitet werden, oder dass Axiome und Theoreme Eigenschaften des Aussagenkalküls sind.

Wie wird ein Beweis in der Aussagenlogik ausgeführt?

An dieser Stelle verlassen wir die Theorie und gehen zur Praxis über. Denn über die Durchführung eines Beweises lässt sich vieles sagen; aber so brillant auch die Aussagen über deduktive Systeme und Aussagenlogik sein mögen – und selbst wenn sie alle verstanden wurden –, heißt das nicht zwangsläufig, dass man auch die nötigen Kompetenzen zur Durchführung eines Beweises entwickelt hat. Aus diesem Grund werden wir zur Veranschaulichung der Vorgehensweise einen einfachen Theorembeweis untersuchen.

Theorem

Wenn \alpha ein Ausdruck der Aussagenlogik ist, dann gilt:

\vdash (\alpha\rightarrow \alpha)

Beweis

Daher gilt: \vdash (\alpha\rightarrow\alpha)

Ende des Beweises.

Wie man sehen kann, sind Beweise in deduktiven Systemen und der Aussagenlogik alles andere als trivial, aber sobald sie erstellt wurden, lassen sie sich leicht reproduzieren.

Bevor wir uns jedoch kopfüber in die Anwendung dieser Techniken stürzen, werden wir zunächst einige Eigenschaften und Definitionen entwickeln, die für diese Aufgabe äußerst nützlich sein werden, denn wenn wir nur mit diesen Mitteln argumentieren, stoßen wir schnell auf erhebliche Schwierigkeiten.

Das Konzept der bewiesenen Äquivalenz

Wenn \alpha und \beta beliebige Ausdrücke sind und gleichzeitig gilt: \{\alpha\}\vdash \beta und \{\beta\} \vdash \alpha, dann sagt man, dass \alpha und \beta bewiesenermaßen äquivalent sind, und man schreibt \alpha \dashv \vdash \beta. Dies lässt sich symbolisch wie folgt zusammenfassen:

\left(\{\alpha\}\vdash\beta \wedge \{\beta\}\vdash\alpha \right) \Leftrightarrow \left(\alpha\dashv\vdash\beta\right)

Dies wird gelesen als: Aus \alpha folgt \beta, und aus \beta folgt \alpha, genau dann, wenn \alpha und \beta bewiesenermaßen äquivalent sind.

Dies ist eine Meta-Eigenschaft der Aussagenlogik.

Der (Meta)Deduktionstheorem

Wenn \alpha und \beta Ausdrücke des Aussagenkalküls sind, und \Gamma eine Menge von Prämissen ist, dann gilt: Wenn sich aus \Gamma \cup \{\alpha\} \beta ableiten lässt, dann folgt aus \Gamma der Ausdruck (\alpha \rightarrow \beta). Symbolisch lässt sich dies wie folgt ausdrücken:

\left(\Gamma \cup \{\alpha\}\vdash \beta \right) \Rightarrow \left( \Gamma\vdash(\alpha\rightarrow\beta)\right)

Beweis:

Damit \Gamma \cup \{\alpha\}\vdash \beta erfüllt ist, muss eine Ableitung der folgenden Form existieren:

Daher gilt: \Gamma\cup\{\alpha\} \vdash \beta

Damit dies möglich ist, muss mindestens einer der Ausdrücke \gamma_1, \cdots \gamma_n,\overline{\gamma_1},\cdots,\overline{\gamma_m} von der Form (\alpha\rightarrow \beta) sein. Aber alle diese Zeilen beinhalten nur Elemente aus \Gamma und die Łukasiewicz-Axiome in ihrer Herleitung. Daher muss gelten: \Gamma\vdash (\alpha \rightarrow \beta). Damit ist der Satz bewiesen.

Ende des Beweises.

Die Umkehrung des Deduktionstheorems

Unter denselben Voraussetzungen wie beim Deduktionstheorem gilt:

\left(\Gamma\vdash(\alpha \rightarrow \beta)\right) \Rightarrow \left( \Gamma \cup \{\alpha\}\vdash \beta \right)

Beweis:

Wenn \Gamma\vdash (\alpha\rightarrow \beta) erfüllt ist, dann existiert eine Ableitung der Form:

Wenn wir nun \alpha als zusätzliche Prämisse zu diesem Argument hinzufügen, erhalten wir folgende Zeilen:

Daher gilt: \Gamma \cup \{\alpha\} \vdash \beta

Was zu zeigen war.

Ende des Beweises.

Schlussfolgerungen über Ausdrücke und Schlussfolgerungen über Schlussfolgerungen

Beweise wie der oben durchgeführte, der zum Ergebnis \vdash (\alpha\rightarrow \alpha) führte, sind Beispiele für Ableitungen auf Grundlage von Ausdrücken, da jeder Schritt einen konkreten Ausdruck enthält. In ähnlicher Weise ist es möglich, Ableitungen auf Grundlage anderer Ableitungen durchzuführen, wobei jeder Schritt selbst eine Ableitung ist. In der Praxis geschieht beides auf ähnliche Weise, doch die zweite Methode erlaubt es uns, das Deduktionstheorem und dessen Umkehrung zu verwenden, was der Argumentationstechnik große Flexibilität verleiht. Um dies zu veranschaulichen, beweisen wir erneut \vdash (\alpha \rightarrow \alpha), aber diesmal unter Verwendung von Ableitungen anstelle von Ausdrücken. Eine mögliche Variante ist die folgende:

Beachten wir, dass diese Argumentation zwar nicht kürzer ist als die vorherige, aber deutlich einfacher durchzuführen war – es genügte, das Deduktionstheorem, seine Umkehrung und das axiomatische Schema A1 zu verwenden, um den Beweis zu konstruieren.

Auf den ersten Blick scheint es, als hätten wir bei dieser Herleitung nur ein einziges Łukasiewicz-Axiom verwendet und sowohl andere Axiome als auch den Modus Ponens vollständig außer Acht gelassen. Bedeutet das, dass wir durch diese Art zu argumentieren die anderen Axiome und den Modus Ponens vergessen? Die Antwort lautet sowohl ja als auch nein. Einerseits können wir so tun, als ob wir manche Axiome und den Modus Ponens nicht benötigen, da wir sie nicht explizit verwenden. Andererseits muss man sich jedoch bewusst sein, dass sowohl das Deduktionstheorem als auch dessen Umkehrung genau Konsequenzen der Łukasiewicz-Axiome und des Modus Ponens sind. Das bedeutet, dass wir bei ihrer Anwendung – wie im eben gesehenen Beweis – diese implizit verwenden.

Monotonie-Regel

Wenn \tau ein Theorem ist, dann gilt: Für jeden beliebigen Ausdruck \beta erfüllt sich

\{\beta\}\vdash\tau

Dies ist in der Tat eine sehr leicht zu beweisende Regel, denn wenn \tau ein Theorem ist, gilt \vdash \tau. Das heißt, es existiert eine Argumentation, die ohne zusätzliche Prämissen zu dem Ausdruck \tau führt, sodass das Hinzufügen eines weiteren Ausdrucks zu den (leeren) Prämissen keinen Unterschied macht.

In ähnlicher Weise lässt sich das folgende Ergebnis formulieren: Wenn sich aus einer Prämissenmenge \Gamma \gamma ableiten lässt, dann gilt auch:

\Gamma\cup\{\alpha\}\vdash\gamma

Dabei ist \alpha ein beliebiger Ausdruck.

Zusammenfassung und Überlegungen zu deduktiven Systemen und Aussagenlogik

Wenn wir der Sprache der Aussagenlogik eine Schlussregel und Basisausdrücke geben: Den Modus Ponens und die Axiome von Łukasiewicz, dann ist das vergleichbar mit dem Bau einer „deduktiven Maschine“ und eines „Motors, der ihr Energie verleiht, um in Bewegung zu geraten“. Von hier aus beginnen alle grundlegenden Ableitungsregeln auf natürliche Weise zu entstehen, und genau diese werden wir in den unmittelbar folgenden Lektionen untersuchen.

Noch ein Detail: Die Ausdrücke der Aussagenlogik sind in Wirklichkeit Meta-Ausdrücke der zuvor betrachteten Sprache mit zwei Symbolen. Erinnern wir uns daran, dass der Vorteil dieser Meta-Ausdrücke darin besteht, dass wir ihre Metavariablen durch beliebige Ausdrücke der Sprache ersetzen können, um neue Ausdrücke zu erhalten, die dieselbe Struktur erfüllen. Wenn wir der Sprache der Aussagenlogik axiomatische Schemata und Schlussregeln verleihen, bauen wir das deduktive System der Aussagenlogik auf, das es ermöglicht, Ableitungen zu erzeugen, die Ausdrücke miteinander verbinden. Das Ergebnis ist ein deduktives Schema, das unendlich viele Ableitungen umfasst – nämlich alle, die wir erhalten können, indem wir Metavariablen durch beliebige Ausdrücke ersetzen. Die wahre Macht der Logik entfaltet sich, wenn wir erkennen, dass wir anstelle dieser ursprünglichen Ausdrücke der Zwei-Symbole-Sprache auch Ausdrücke unserer natürlichen Sprache einsetzen und beobachten können, was dabei geschieht.