Vollständigkeit und Schlüssigkeit in der Aussagenlogik
ZUSAMMENFASSUNG
In dieser Unterrichtseinheit wird das Verhältnis zwischen Vollständigkeit und Schlüssigkeit in der Aussagenlogik behandelt. Obwohl die Deduktionstechniken und die Semantik in der Aussagenlogik ausführlich diskutiert wurden, wurde der Zusammenhang zwischen beiden Aspekten bisher wenig beachtet. Die Schlüssigkeit bezieht sich auf die Eigenschaft eines logischen Systems, einen Ausdruck G aus einer Menge von Ausdrücken Γ abzuleiten. Die Vollständigkeit hingegen bezeichnet die Eigenschaft eines logischen Systems, bei der, wenn G eine semantische Konsequenz aus einer Menge von Ausdrücken Γ ist, dann ein formaler Beweis mit Prämissen Γ existiert, aus dem G abgeleitet werden kann. Es wird gezeigt, dass die Aussagenlogik sowohl schlüssig als auch vollständig ist, und es wird eine ausführliche Erklärung jeder Eigenschaft gegeben. Insbesondere wird erläutert, wie sich die Schlüssigkeit aus dem Aufbau des deduktiven Systems der Aussagenlogik ergibt und wie die Vollständigkeit auf einfache Weise gefolgert werden kann. Diese Analyse ist von großer Bedeutung, um zu verstehen, wie die Aussagenlogik funktioniert, und um sie wirksam in verschiedenen Wissensgebieten anzuwenden.
LERNZIELE:
Am Ende dieser Unterrichtseinheit wird der Studierende in der Lage sein:
- Zu unterscheiden zwischen Schlüssigkeit und Vollständigkeit in einem logischen System.
- Die Wahrheitstabelle für die Axiome von Łukasiewicz anzuwenden, um die Schlüssigkeit der Aussagenlogik zu demonstrieren.
- Zu erklären, wie der Modus Ponens mithilfe der semantischen Version des Deduktionstheorems umgeschrieben werden kann.
- Zu verstehen, dass Schlüssigkeit und Vollständigkeit miteinander verbunden sind und voneinander abgeleitet werden können.
- Zu analysieren, was eine Tautologie ist und wie sie mit Theoremen in der Aussagenlogik zusammenhängt.
INHALTSVERZEICHNIS
VOLLSTÄNDIGKEIT UND SCHLÜSSIGKEIT IN DER AUSSAGENLOGIK
DIE AUSSAGENLOGIK IST SCHLÜSSIG
DIE AUSSAGENLOGIK IST VOLLSTÄNDIG
Vollständigkeit und Schlüssigkeit in der Aussagenlogik
An diesem Punkt ist es an der Zeit, über die Vollständigkeit und Schlüssigkeit der Aussagenlogik zu sprechen. Bisher wurde viel über Deduktionstechniken und die Semantik der Aussagenlogik gesprochen, allerdings auf eine Weise, die den Eindruck erwecken könnte, dass es sich um zwei völlig unabhängige Aspekte ohne jede Verbindung handelt. Die Realität ist jedoch genau das Gegenteil.
SCHLÜSSIGKEIT: Ein logisches System wird als schlüssig bezeichnet, wenn gilt: Immer wenn ein Ausdruck G aus einer Menge von Ausdrücken \Gamma hergeleitet werden kann, dann ist G auch eine (semantische) Konsequenz aus \Gamma. |
VOLLSTÄNDIGKEIT: Andererseits wird ein System als vollständig bezeichnet, wenn gilt: Wenn G eine semantische Konsequenz aus einer Menge von Ausdrücken \Gamma ist, dann existiert ein formaler Beweis mit den Prämissen \Gamma, aus dem G hergeleitet werden kann. |
Wenn wir diese Konzepte betrachten, werden wir feststellen, dass sowohl die Vollständigkeit als auch die Schlüssigkeit für die Aussagenlogik erfüllt sind.
Die Aussagenlogik ist schlüssig
Die Schlüssigkeit der Aussagenlogik lässt sich leicht zeigen, wenn man die Struktur ihres deduktiven Systems betrachtet. Wenn wir die Wahrheitstabelle für die Axiome von Łukasiewicz erstellen, werden wir sehen, dass sie so aufgebaut sind, dass sie immer den Wahrheitswert „wahr“ ergeben, das heißt:
| \models (\alpha \rightarrow (\beta \rightarrow \alpha)) |
| \models ((\alpha \rightarrow (\beta \rightarrow \gamma))\rightarrow ((\alpha \rightarrow \beta) \rightarrow (\alpha \rightarrow \gamma))) |
| \models ((\neg\beta \rightarrow \neg\alpha)\rightarrow(\alpha \rightarrow \beta)) |
In ähnlicher Weise kann der Modus Ponens in der Form \{\alpha,(\alpha\rightarrow \beta)\}\models \beta. umgeschrieben werden, was mithilfe der semantischen Version des Deduktionstheorems abgeleitet werden kann. Tatsächlich erhalten wir auf diesem Weg \{(\alpha\rightarrow \beta)\}\models (\alpha\rightarrow \beta), und dann \models ((\alpha\rightarrow \beta)\rightarrow (\alpha\rightarrow \beta)), was selbstverständlich eine völlig offensichtliche Tautologie ist.
Die Aussagenlogik ist vollständig
Die Vollständigkeit der Aussagenlogik besagt, dass, wenn B eine semantische Konsequenz aus A ist, dann kann B aus A hergeleitet werden. Mit anderen Worten: Alle wahren Ausdrücke besitzen einen Beweis. Dies ist es, was wir als Vollständigkeit bezeichnen. Und das lässt sich auf einfache Weise folgern.
Dies lässt sich auf einfache Weise folgern. Angenommen, aus A lässt sich B nicht herleiten, das heißt genauer: \neg(A\vdash B). Nach dem Deduktionstheorem ist dies äquivalent zu: \neg (\vdash A\rightarrow B); wenn wir nun auf die Schlüssigkeit zurückgreifen, führt uns dies zu \neg(\models A \rightarrow B), was wiederum nach dem Umkehrschluss des Deduktionstheorems (semantische Version) äquivalent ist zu \neg(A\models B). Zusammengefasst ergibt sich also:
\neg(A\vdash B) \Rightarrow \neg(A\models B)
Was äquivalent ist zu der Aussage:
(A\models B) \Rightarrow (A\vdash B)
Das bedeutet: Wenn A B modelliert, dann kann B aus A hergeleitet werden. Und wenn wir die jeweiligen Deduktionstheoreme anwenden, erhalten wir:
(\models A\rightarrow B) \Rightarrow (\vdash A \rightarrow B)
Das heißt: Wenn ein Ausdruck eine Tautologie ist, dann ist er ein Theorem; und wie wir gesehen haben, sind Theoreme das Ergebnis eines Beweises.