Semantik der Aussagenlogik
ZUSAMMENFASSUNG
In dieser Lektion wird die Semantik der Aussagenlogik untersucht, insbesondere die Zuordnung von Wahrheitswerten zu Ausdrücken und wie sich diese durch logische Junktoren von einem Ausdruck auf einen anderen übertragen. Es wird das Konzept der Wahrheitstabellen eingeführt, und die Wahrheitstabellen der abgeleiteten Junktoren wie Negation, Disjunktion, Konjunktion, Implikation, Bikonditionalität und exklusives Oder werden dargestellt. Darüber hinaus wird die Definition einer Belegung über einer Menge atomarer Ausdrücke präsentiert und erklärt, wie sich diese natürlich auf alle Ausdrücke erstreckt, die aus dieser Menge konstruiert werden können. Schließlich werden die Definitionen gültiger, erfüllbarer und unerfüllbarer Ausdrücke eingeführt, sowie Beispiele für Tautologien und Kontradiktionen dargestellt. Es wird jedoch erkannt, dass die Berechnung von Wahrheitstabellen für komplexe Ausdrücke ineffizient sein kann, weshalb alternative Methoden zur Prüfung von Gültigkeit oder Erfüllbarkeit angesprochen werden.
LERNZIELE:
Am Ende dieser Lektion wird der/die Studierende in der Lage sein:
- Die Semantik der Aussagenlogik zu erklären
- Wahrheitstabellen zu verwenden, um die Wahrheitswertbelegungen von Ausdrücken in der Aussagenlogik darzustellen
- Einen Ausdruck mit einer Belegung in der Aussagenlogik zu modellieren
- Die semantischen Regeln der Aussagenlogik anzuwenden, um zu bestimmen, ob ein Ausdruck eine Tautologie, eine Kontradiktion oder eine Kontingenz ist
INHALTSVERZEICHNIS
ÜBER DIE ZUORDNUNG VON WAHRHEITSWERTEN
SEMANtik DER JUNKTOREN DER AUSSAGENLOGIK
BELEGUNGEN IN DER AUSSAGENLOGIK
MODELLE IN DER AUSSAGENLOGIK
EFFIZIENZPROBLEM DER SEMANTIK DER AUSSAGENLOGIK
Über die Zuordnung von Wahrheitswerten
Früher haben wir die Syntax und die deduktiven Systeme der Aussagenlogik behandelt. Auch wenn dies uns geholfen hat zu verstehen, wie man gewisse Ausdrücke aus anderen ableiten kann, wurde dabei noch nichts über die Zuordnung von Wahrheitswerten ausgesagt. Da wir nun alles Relevante über die deduktiven Techniken der Aussagenlogik behandelt haben, beginnen wir unser Studium der Semantik der Aussagenlogik, in der untersucht wird, wie sich Wahrheitswertbelegungen von einem Ausdruck auf einen anderen übertragen.
Semantik der Junktoren der Aussagenlogik
Die Semantik der Junktoren wird durch Wahrheitstabellen eingeführt, da sie eine einfache und geordnete Möglichkeit bieten, alle möglichen Belegungen eines Ausdrucks darzustellen.
Wahrheitstabelle der konjunktiven Negation
Zunächst beginnen wir mit dem grundlegendsten aller Junktoren, nämlich der konjunktiven Negation. Ihre Wahrheitstabelle lautet wie folgt:
| \alpha | \beta | (\alpha\downarrow\beta) |
| 0 | 0 | 1 |
| 0 | 1 | 0 |
| 1 | 0 | 0 |
| 1 | 1 | 0 |
Die Werte „1“ und „0“ entsprechen „Wahr“ und „Falsch“. Jede Zeile in der Wahrheitstabelle stellt eine mögliche Belegung der Variablen (oder atomaren Ausdrücke) dar, aus denen der Ausdruck (oder die Ausdrücke) besteht, die untersucht werden sollen. Ebenso enthält jede Spalte mit einem aus diesen Variablen gebildeten Ausdruck die möglichen Ergebnisse dieser Belegungen. Auf diese Weise zeigt uns die Interpretation dieser Tabelle, dass \alpha\downarrow\beta genau dann wahr ist, wenn sowohl \alpha als auch \beta gleichzeitig falsch sind, und in allen anderen Fällen falsch ist. Aus diesem Grund wird der Junktor \downarrow als konjunktive Negation bezeichnet.
Wahrheitstabellen der abgeleiteten Junktoren
Ausgehend von der Semantik der konjunktiven Negation kann die Semantik der übrigen Junktoren über deren Definitionen hergeleitet werden. Diese lauten:
| Negation: | \neg \alpha | := | (\alpha\downarrow\alpha) |
| Inklusive Disjunktion: | (\alpha \vee \beta) | := | \neg(\alpha\downarrow\beta) |
| Konjunktion: | (\alpha \wedge \beta) | := | \neg(\neg\alpha\vee \neg\beta) |
| Implikation: | (\alpha \rightarrow \beta) | := | (\neg\alpha\vee \beta) |
| Äquivalenz: | (\alpha \leftrightarrow \beta) | := | ((\alpha\rightarrow \beta)\wedge(\beta \rightarrow \alpha)) |
| Exklusive Disjunktion: | (\alpha \underline{\vee} \beta) | := | \neg(\alpha\leftrightarrow \beta) |
Auf der Grundlage dieser Definitionen ist es möglich, die Wahrheitstabellen der übrigen Junktoren zu berechnen:
Negation
| \alpha | \neg \alpha |
| 0 | 1 |
| 1 | 0 |
Daher kommt die Eigenschaft des Negationsjunktors, den Wahrheitswert des Ausdrucks, auf den er angewendet wird, umzukehren.
Inklusive Disjunktion
| \alpha | \beta | (\alpha\vee\beta) |
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 1 |
Daher gilt: Die inklusive Disjunktion (oder einfach „Disjunktion“) zwischen zwei Ausdrücken ist wahr, wenn mindestens einer der Ausdrücke wahr ist, und sie ist falsch, wenn beide Ausdrücke gleichzeitig falsch sind.
Konjunktion
| \alpha | \beta | (\alpha\wedge\beta) |
| 0 | 0 | 0 |
| 0 | 1 | 0 |
| 1 | 0 | 0 |
| 1 | 1 | 1 |
Daraus ergibt sich, dass die Konjunktion zweier Ausdrücke genau dann wahr ist, wenn beide Ausdrücke gleichzeitig wahr sind, und sonst falsch. Aus diesem Grund kann dieser Junktor auch treffend als „gemeinsame Bejahung“ bezeichnet werden.
Implikation
| \alpha | \beta | (\alpha\rightarrow\beta) |
| 0 | 0 | 1 |
| 0 | 1 | 1 |
| 1 | 0 | 0 |
| 1 | 1 | 1 |
Daraus ergibt sich, dass die Wahrheitstabelle der Implikation die Vorstellung zusammenfasst, dass ein wahrer Ausdruck nur einen wahren Ausdruck implizieren kann, während ein falscher Ausdruck alles implizieren kann.
Bikonditional (Doppelte Implikation)
| \alpha | \beta | (\alpha\leftrightarrow\beta) |
| 0 | 0 | 1 |
| 0 | 1 | 0 |
| 1 | 0 | 0 |
| 1 | 1 | 1 |
Die doppelte Implikation bildet genau dann einen wahren Ausdruck, wenn beide beteiligten Ausdrücke denselben Wahrheitswert haben, und ist in allen anderen Fällen falsch.
Exklusive Disjunktion
| \alpha | \beta | (\alpha\underline{\vee}\beta) |
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 0 |
Die exklusive Disjunktion zwischen zwei Ausdrücken ist genau dann wahr, wenn einer und nur einer der Ausdrücke wahr ist, und sonst falsch.
Belegungen in der Aussagenlogik
Aus dem zuvor Beschriebenen ergibt sich eine einfache Vorstellung davon, was eine Belegung ist; jedoch benötigen wir für die weiteren Ausführungen eine präzisere Definition. Ist S=\{A_1, A_2, \cdots, A_n\} eine Menge atomarer Ausdrücke und \mathcal{F}(S) die Menge aller Ausdrücke, die sich aus den Elementen von S bilden lassen, so gilt folgende Definition:
DEFINITION: Eine Belegung über S ist eine Funktion \mathcal{A}: S \longrightarrow \{0,1\}
Mit anderen Worten: Eine Belegung über S weist jedem atomaren Ausdruck aus S einen Wahrheitswert zu. Eine Belegung \mathcal{A} von S lässt sich auf natürliche Weise auf alle Elemente von \mathcal{F}(S) erweitern. Ist F\in \mathcal{F}(S) ein Ausdruck, so entspricht eine Belegung \mathcal{A} über S genau einer Zeile der Wahrheitstabelle von F, und \mathcal{A}(F) ist dann der Wahrheitswert von F in dieser Zeile.
Eine Belegung \mathcal{A} von S kann auch auf gewisse Ausdrücke außerhalb von \mathcal{F}(S) erweitert werden. Ist F_0 ein Ausdruck, der nicht zu \mathcal{F}(S) gehört, und sei S_0 die Menge der atomaren Teilformeln von F_0, so wird \mathcal{A}(F_0) als dieser Wert definiert, falls alle Erweiterungen von \mathcal{A} auf S\cup S_0 denselben Wert für F_0 ergeben.
BEISPIEL: Sind A und B atomare Ausdrücke und \mathcal{A} eine Belegung über \{A,B\} mit \mathcal{A}(A)=1 und \mathcal{A}(B)=0, so gilt:
\mathcal{A}(A\wedge B)=0 und \mathcal{A}(A\vee B)=1
Und obwohl keine Belegung für die Variable C definiert wurde, kann man dennoch sagen:
\mathcal{A}(A\wedge (C\vee \neg C))=1 und \mathcal{A}(B\vee (C\wedge \neg C))=0
Dies ist bei den letzten beiden Ausdrücken der Fall, weil unabhängig von der Belegung von C stets gilt:
\mathcal{A}(C\vee\neg C)=1 und \mathcal{A}(C\wedge\neg C)=0
Dies lässt sich schnell überprüfen, indem man ihre Wahrheitstabellen berechnet.
| C | \neg C | (C\wedge \neg C) | (C \vee \neg C) |
| 0 | 1 | 0 | 1 |
| 1 | 0 | 0 | 1 |
■ Ende des Beispiels
Modelle in der Aussagenlogik
Betrachten wir eine Belegung \mathcal{A} über einer Menge von Ausdrücken S. Wenn F\in S und \mathcal{A}(F)=1, dann sagt man, dass die Belegung \mathcal{A} ein Modell von F ist, oder dass der Ausdruck F von der Belegung \mathcal{A} getragen wird, und man schreibt
\mathcal{A}\models F.
Daraus ergeben sich folgende Definitionen:
DEFINITION: Ein Ausdruck heißt gültig, wenn er unter jeder Belegung gilt. Ist F gültig, so schreibt man \models F . Gültige Ausdrücke nennt man auch Tautologien.
BEISPIEL: Der Ausdruck (C\vee \neg C), den wir bereits gesehen haben, ist eine Tautologie.
■ Ende des Beispiels
DEFINITION: Ein Ausdruck heißt erfüllbar, wenn es mindestens eine Belegung gibt, unter der er gilt. Erfüllbare Ausdrücke, die keine Tautologien sind, nennt man Kontingenzen.
DEFINITION: Ein Ausdruck heißt unerfüllbar, wenn es keine Belegung gibt, unter der er gilt. Unerfüllbare Ausdrücke nennt man Kontradiktionen. Ist F eine Kontradiktion, so schreibt man \not\models F .
BEISPIEL: Der Ausdruck (C\wedge \neg C), den wir bereits gesehen haben, ist eine Kontradiktion.
■ Ende des Beispiels
Beispiele für Tautologien und Kontradiktionen
Angenommen, wir möchten herausfinden, ob ein Ausdruck gültig ist oder nicht. Diese Fragestellung stellt ein Entscheidungsproblem in der Semantik der Aussagenlogik dar. Ein Entscheidungsproblem ist ein Problem, bei dem eine gegebene Eingabe mit „ja“ oder „nein“ beantwortet wird. Wenn uns ein Ausdruck F gegeben ist und wir fragen, ob er gültig ist, dann handelt es sich um das Gültigkeitsproblem. Analog dazu sprechen wir vom Erfüllbarkeitsproblem, wenn wir wissen möchten, ob der Ausdruck erfüllbar ist. In der Aussagenlogik bieten Wahrheitstabellen eine systematische Methode zur Lösung solcher Entscheidungsprobleme: Wenn alle möglichen Wahrheitswerte von F „1“ sind, dann ist F gültig; wenn nur einige „1“ sind, ist er erfüllbar; und wenn alle „0“ sind, ist er unerfüllbar.
BEISPIEL: Betrachten wir den Ausdruck ((A\wedge (A \rightarrow B)) \rightarrow B). Um festzustellen, ob dieser Ausdruck gültig, erfüllbar oder widersprüchlich ist, erstellen wir seine Wahrheitstabelle.
| A | B | (A\rightarrow B) | (A\wedge(A\rightarrow B)) | ((A\wedge(A\rightarrow B))\rightarrow B) |
| 0 | 0 | 1 | 0 | 1 |
| 0 | 1 | 1 | 0 | 1 |
| 1 | 0 | 0 | 0 | 1 |
| 1 | 1 | 1 | 1 | 1 |
Daraus ergibt sich, dass ((A\wedge(A\rightarrow B))\rightarrow B) für alle möglichen Belegungen den Wahrheitswert „1“ hat. Somit handelt es sich bei dem Ausdruck um eine Tautologie.
■ Ende des Beispiels
BEISPIEL: Betrachten wir nun den Ausdruck (((A\rightarrow B)\rightarrow A)\wedge \neg A). Die Berechnung der Wahrheitstabelle ergibt Folgendes:
| A | B | (A\rightarrow B) | ((A\rightarrow B)\rightarrow A) | \neg A | (((A\rightarrow B)\rightarrow A)\wedge \neg A) |
| 0 | 0 | 1 | 0 | 1 | 0 |
| 0 | 1 | 1 | 0 | 1 | 0 |
| 1 | 0 | 0 | 1 | 0 | 0 |
| 1 | 1 | 1 | 1 | 0 | 0 |
Daraus ergibt sich, dass es sich um eine Kontradiktion handelt.
Ein Effizienzproblem bedroht die Semantik der Aussagenlogik
Theoretisch können wir feststellen, ob ein Ausdruck gültig, kontingent oder unerfüllbar ist, indem wir einfach seine Wahrheitstabelle berechnen – was an sich nicht besonders schwierig ist; leider bezahlt man diese Einfachheit mit einem hohen Preis in puncto Effizienz. Wenn ein Ausdruck F aus n atomaren Ausdrücken besteht, dann umfasst seine Wahrheitstabelle 2^n Zeilen. Wenn also beispielsweise F aus 23 atomaren Ausdrücken besteht, dann hat die zugehörige Wahrheitstabelle 8.388.608 Zeilen, die berechnet werden müssen. Ein derartiges Vorgehen – so mechanisch und einfach es auch sein mag – wird rasch unpraktikabel, sobald die Komplexität der Ausdrücke steigt. Aus diesem Grund wird eines unserer zukünftigen Ziele sein, eine Methode zu finden, mit der sich Gültigkeits- oder Erfüllbarkeitsprobleme lösen lassen, ohne dass die Wahrheitstabelle vollständig berechnet werden muss. Die Suche nach solchen Methoden ist eines der zentralen Probleme jeder Logik.