Die Wahrheit der Formeln

Wenn wir einige atomare Aussagen haben, die wir in eine Formel einsetzen, können wir versuchen zu entscheiden, ob die gesamte Formel wahr oder falsch ist.

Die Wahrheit der Aussage

Als Erstes legen wir fest, welchen Wahrheitswert eine Aussage hat. Bei einer Aussage p sollten wir in der Lage sein zu entscheiden, ob sie wahr oder falsch ist. Eine wahre Aussage hat einen Wahrheitswert von 1 und eine falsche Aussage hat einen Wahrheitswert von 0.

Der Wahrheitswert ist dann eine Regel e, die einer gegebenen Aussage entweder 0 oder 1 zuordnet. Wenn wir e(p) schreiben, wollen wir den Wahrheitswert der Aussage p bestimmen. Wenn p gleich der Aussage "zwei mal zwei ist vier" ist, dann e(p) = 1, denn es ist eine wahre Aussage. Wenn q gleich der Aussage "Václav Klaus ist eine Frau" ist, dann e(q) = 0, denn Vasek ist keine Frau. e ist also eine Funktion, die zurückgibt, ob die Aussage wahr ist.

Dabei ist zu beachten, dass e keine magische Funktion ist, die alles auf der Welt weiß. Sie verhält sich so, wie wir es ihr sagen. Sie weiß nicht, ob Václav Klaus ein Mann oder eine Frau ist. Wir sollten zu Beginn der Berechnung angeben, wie sich die Auswertungsfunktion verhalten soll. Wenn wir ihr sagen, dass Václav Klaus eine Frau ist, wird sie e(q) = 1 zurückgeben.

Die Wahrheit von Satzkonjunktionen

Um den Wahrheitsgehalt einer Formel zu bestimmen, müssen wir wissen, wie man den Wahrheitsgehalt von Aussagenkonjunktionen auswertet. Das heißt, wenn wir die Auswertung von e(p) und e(q) kennen, wie lautet dann der Wahrheitswert der Formeln p ∧ q, $p \Rightarrow q$ usw.

Jede Aussagekonjunktion verhält sich anders und wird für etwas anderes verwendet, daher werden wir jede Konjunktion separat behandeln.

Der Wahrheitswert der Konjunktion

Die Konjunktion wird mit p ∧ q bezeichnet und lautet "p und auch q". Betrachten wir als Beispiel die Formel "Die Tschechische Republik liegt in Mitteleuropa und gleichzeitig ist ihre Hauptstadt Prag". Wann wird der ganze Satz wahr sein?

Allein die Konjunktion "und gleichzeitig" hilft uns, die Wahrheit zu bestimmen. Sie sagt uns ausdrücklich, dass sie will, dass die beiden Aussagen links und rechts wahr sind. Wenn also beide Aussagen p und q wahr sind, d. h. e(p) = 1 und e(q) = 1, dann ist die gesamte Konjunktion wahr. Andernfalls, wenn entweder eine der Aussagen falsch ist oder beide falsch sind, ist die gesamte Formel falsch.

Ein Beispiel für eine Konjunktion, die nicht wahr ist, wäre "Die Moldau ist ein Fluss und gleichzeitig fließt die Moldau durch Russland". Es ist wahr, dass die Moldau ein Fluss ist, aber es ist nicht wahr, dass sie durch Russland fließt, also ist die gesamte Konjunktion nicht wahr.

Die folgende Tabelle zeigt dies deutlich:

$$\begin{array}{ccc} p&q&p \wedge q\\ 1&1&1\\ 1&0&0\\ 0&1&0\\ 0&0&0 \end{array}$$

Die ersten beiden Spalten sind die Wahrheitswerte der Aussagen p und q und die dritte Spalte ist der Wahrheitswert der Formel p ∧ q.

Der Wahrheitswert der Disjunktion

Die Disjunktion wird mit p ∨ q bezeichnet und lautet "p oder q". Beispiel: "Russland liegt in Europa oder Asien." Wann wird der ganze Satz wahr sein?

Bei der Disjunktion muss nur mindestens eine der Optionen wahr sein. Die Konjunktion "oder" lässt uns die Wahl, ob der linke oder der rechte Teil der Konjunktion wahr ist. Der einzige kleine Unterschied zum normalen Sprachgebrauch besteht darin, dass das logische Oder auch dann wahr ist, wenn beide Aussagen gleichzeitig erfüllt sind. Das ist nicht ganz üblich; in der Alltagssprache verwenden wir "oder" oft in einer ausschließenden Weise, d. h. "entweder ... oder ...".

Dazu gibt es einen klassischen Witz: Eine Familie sucht sich in einem Gebrauchtwagenladen ein neues Auto aus. Der Vater sagt dem Verkäufer: "Wir haben uns für ein blaues oder ein rotes Auto entschieden". Der Verkäufer verkauft ihnen beide Autos. Dies veranschaulicht den Unterschied zwischen dem logischen und dem gesprochenen oder: Der Vater meinte wahrscheinlich, dass sie sich für eines der beiden Autos entscheiden würden, während der Verkäufer es für eine gültige Option hielt, ihnen beide Autos zu verkaufen.

Der vorherige Satz mit Russland ist wahr, weil beide Aussagen wahr sind. Der Satz "Die Zahl 7 ist durch 3 teilbar oder die Zahl 7 ist eine Primzahl" ist wahr, weil sieben eine Primzahl ist. Sie ist vielleicht nicht durch drei teilbar, aber das spielt keine Rolle mehr. Wahrheitswerttabelle:

$$\begin{array}{ccc} p&q&p \vee q\\ 1&1&1\\ 1&0&1\\ 0&1&1\\ 0&0&0 \end{array}$$

Wahrheitsgehalt der Implikation

Die Implikation wird mit $p \Rightarrow q$ bezeichnet und lautet "wenn p, dann q". Ein Beispiel für eine Implikation wäre der Satz "Wenn wir viel Wodka trinken, dann werden wir uns übergeben". Wann wird der Satz wahr sein?

Die logische Implikation ist die schwierigste aller Konjunktionen, und selbst in der Umgangssprache wird sie oft missverstanden und mit der Äquivalenz verwechselt. Versuchen wir, die Frage zu beantworten, ob die umgekehrte Implikation ebenfalls wahr ist: $q \Rightarrow p$.

Wir wissen, dass wir uns übergeben müssen, wenn wir viel Wodka trinken. Stimmt es auch, dass wir viel Wodka getrunken haben, wenn wir uns übergeben? Sicherlich nicht, wir könnten auch ganz anderen Alkohol getrunken haben und trotzdem krank sein, oder wir könnten von etwas ganz anderem krank sein. Der Umkehrschluss gilt also nicht automatisch. Wenn $p \Rightarrow q$ gilt und gleichzeitig $q \Rightarrow p$ gilt, handelt es sich um eine Äquivalenz, siehe unten.

Ein anderes Beispiel: "Wenn es morgen regnet, dann wird Honza einen Regenschirm mitnehmen". Nun, ich sage, dass Honza seinen Regenschirm mitgenommen hat. Die Frage ist: Hat es an diesem Tag geregnet? Viele Leute neigen dazu zu sagen, dass es natürlich regnete, weil Honza seinen Regenschirm mitnahm, als es regnen sollte. Aber so ist der ursprüngliche Satz nicht aufgebaut!

Vielleicht hat Honza den Regenschirm aus einem anderen Grund mitgenommen, von dem wir nichts wissen. Vielleicht nimmt Honza einen Regenschirm mit, wenn er seine Schwiegermutter besucht, damit er ihr ein Auge ausstechen kann. Oder er hat beschlossen, einen neuen Regenschirm zu kaufen und will den alten wegwerfen. Das sind alles legitime Gründe, warum Honza einen Regenschirm mitgenommen haben könnte, obwohl es vielleicht gar nicht regnet.

Nun können wir die Frage beantworten, wann die Implikation wahr sein wird. Wenn beide Aussagen wahr sind, dann wird die Implikation mit Sicherheit wahr sein: "Wenn 42 eine natürliche Zahl ist, dann ist sie positiv". Beide Aussagen sind wahr, also ist die gesamte Implikation wahr. Ein anderes Beispiel wäre die Implikation "wenn 42 eine natürliche Zahl ist, dann ist sie negativ". Diese Implikation ist nicht wahr, weil wir versuchen, von der Wahrheit auf etwas zu schließen, das nicht wahr ist.

Schließlich bleiben noch die Fälle, in denen die erste Aussage falsch ist. In diesem Fall sind wir nicht mehr an der Wahrheit der zweiten Aussage interessiert. Wenn wir von einer Unwahrheit ausgehen, können wir weiter plappern, so viel wir wollen. Das sind Sätze wie "Wenn 1 eine negative Zahl ist, dann sind wir der chinesische Gott des Spaßes" oder "Wenn die Beatles eine berühmte Baufirma sind, dann ist die Sonne blau". In solchen Fällen ist die Implikation automatisch wahr, weil sie einfach auf einer Unwahrheit beruht. Tabelle:

$$\begin{array}{ccc} p&q&p \Rightarrow q\\ 1&1&1\\ 1&0&0\\ 0&1&1\\ 0&0&1 \end{array}$$

Wahrheitsgehalt der Äquivalenz

Äquivalenz wird mit p ⇔ q geschrieben und lautet "p nur wenn q". Ein Beispiel für eine Äquivalenz könnte lauten: "Die Zahl x ist nur dann durch zwei teilbar, wenn sie gerade ist". Wann wird der ganze Satz wahr sein?

Bei Äquivalenz erwarten wir, dass die beiden Aussagen in einer solchen Symbiose stehen, dass entweder beide wahr sind oder keine der beiden wahr ist. Entweder ist also die Zahl x gerade und durch zwei teilbar, oder sie ist es nicht. Es kann nicht der Fall sein, dass x gerade, aber nicht durch zwei teilbar ist.

Beispiel. Damit die Äquivalenz erfüllt ist, muss George jedes Mal, wenn er auf der Toilette sitzt, ein Buch lesen. Und immer, wenn er ein Buch liest, muss er gleichzeitig auf der Toilette sitzen. Es kann nicht sein, dass er im Bett ein Buch liest.

Die Äquivalenz kann durch zwei Implikationen ausgedrückt werden. So könnte p ⇔ q in $p \Rightarrow q$ und gleichzeitig $q \Rightarrow p$ umgeschrieben werden. Tabelle:

$$\begin{array}{ccc} p&q&p \Leftrightarrow q\\ 1&1&1\\ 1&0&0\\ 0&1&0\\ 0&0&1 \end{array}$$

Negation von

Die Negation ist eine unäre Operation, wir schreiben sie entweder mit dem Komma p' oder mit diesem Symbol: $\neg p$. Die Negation macht unsere ursprüngliche Aussage ungültig. Wenn wir die Aussage "Lucie Bílá ist eine Sängerin" haben, dann würden wir durch Negation die Aussage "Es ist nicht wahr, dass Lucie Bílá eine Sängerin ist" oder kurz "Lucie Bílá ist keine Sängerin" erhalten. Wir können fast immer eine Negation bilden, indem wir "Es ist nicht wahr, dass..." vor die Aussage setzen.

Die Negation kehrt den Wahrheitswert um, d. h. sie macht aus 0 1 und aus 1 0 . Wir können $\neg0=1$ und $\neg1=0$ schreiben.

Hüten Sie sich vor einigen kniffligen Dingen. Nehmen wir die Aussage "Kalk ist weiß". Was ist die Negation? Man könnte denken, dass "Kalk schwarz ist", aber das stimmt nicht! In Anlehnung an die vorangegangene Lektion wäre die Negation die Aussage "Es ist nicht wahr, dass Kalk weiß ist". Bedeutet das zwangsläufig, dass er schwarz sein muss? Nein, sie kann auch rosafarben sein.

Tabelle mit allen Konjunktionen

$$\begin{array}{cccccc} p&q&p \wedge q&p \vee q&p \Rightarrow q&p \Leftrightarrow q\\ 1&1&1&1&1&1\\ 1&0&0&1&0&0\\ 0&1&0&1&1&0\\ 0&0&0&0&1&1 \end{array}$$

Die Wahrheit der gesamten Formel

Wir können nun den Wahrheitsgehalt zweier Aussagen bewerten, die durch eine Satzkonjunktion verbunden sind. Wir werden die gesamte Formel auf völlig analoge Weise auswerten. Wenn wir die Formel $(p \Rightarrow q) \wedge r$ haben, dann erhalten wir in dem Moment, in dem wir die Formel $(p \Rightarrow q)$ bis 1 auswerten, zum Beispiel die klassische Konjunktion 1 ∧ r, deren Lösung wir bereits kennen.

Durch die sukzessive Anwendung der einfachsten Satzkonjunktionen erhalten wir den endgültigen Wahrheitswert der gesamten Formel. Dies geschieht häufig mit der sogenannten Tabellenmethode, die im Folgenden beschrieben wird.

Die tabellarische Methode

Die tabellarische Methode wird verwendet, wenn komplexere Formeln ausgewertet werden sollen. In den ersten Spalten von n werden die Aussagesymbole n notiert, mit denen die Formel arbeitet, und in die nächsten Spalten werden nacheinander die Teilformeln eingetragen, die die Formel enthält. Ein Beispiel soll dies verdeutlichen:

Nehmen wir die Formel $(p \vee q) \wedge (q \Rightarrow p)$. Zu Beginn notieren wir alle Aussagesymbole, d. h. p und q, und alle ihre Auswertungskombinationen:

$$\begin{array}{cc} p&q\\ 1&1\\ 1&0\\ 0&1\\ 0&0 \end{array}$$

Als nächstes fügen wir Spalten für jede Teilformel p ∨ q und $q \Rightarrow p$ hinzu.

$$\begin{array}{cccc} p&q&p \vee q&q \Rightarrow p\\ 1&1\\ 1&0\\ 0&1\\ 0&0 \end{array}$$

Nun werten wir diese Formeln aus und fügen Nullen oder Einsen zu den Spalten hinzu. In der Tabelle haben wir nun alle notwendigen Informationen. Wir gehen vor, indem wir p ∨ q in der ersten Zeile auswerten, dann fügen wir 1 nach p und 1 nach q hinzu. So erhalten wir den Ausdruck 1 ∨ 1. Die Auswertung dieses Ausdrucks ist wieder 1, also schreiben wir eine Eins in die Tabelle:

$$\begin{array}{cccc} p&q&p \vee q&q \Rightarrow p\\ 1&1&1\\ 1&0\\ 0&1\\ 0&0 \end{array}$$

Damit ist die Tabelle eins zu eins vervollständigt:

$$\begin{array}{cccc} p&q&p \vee q&q \Rightarrow p\\ 1&1&1&1\\ 1&0&1&1\\ 0&1&1&0\\ 0&0&0&1 \end{array}$$

Nun müssen wir noch die gesamte Formel auswerten. Nennen wir sie zum Beispiel $\varphi=(p \vee q) \wedge (q \Rightarrow p)$. Wir fügen der Tabelle eine Spalte mit $\varphi$ hinzu und werten sie aus, indem wir die beiden vorherigen Spalten zur Auswertung verwenden.

$$\begin{array}{ccccc} p&q&p \vee q&q \Rightarrow p&\varphi\\ 1&1&1&1&1\\ 1&0&1&1&1\\ 0&1&1&0&0\\ 0&0&0&1&0 \end{array}$$

Die Tabelle ist nun vollständig und liefert uns den Wahrheitswert der Formel bei allen möglichen Auswertungen. Wenn zum Beispiel e(p) = 1 und gleichzeitig e(q) = 1, dann ist die Formel wahr. Wenn e(p) = 0 und e(q) = 1, dann ist die Formel nicht wahr.

Beachten Sie, dass wir nicht sagen können, dass "die Formel wahr ist". Dieser Satz macht keinen Sinn, denn um zu sagen, dass die Formel wahr ist, müssten wir sagen, in welcher Bewertung die Formel wahr ist. Wir können also sagen: "Die Formel $\varphi$ ist wahr in der Bewertung e₁ und ist nicht wahr in der Bewertung e₂".

Der einzige Fall, in dem wir sagen können, dass eine Formel wahr ist, ist, wenn sie in allen möglichen Bewertungen wahr ist. Zum Beispiel ist die Formel $p \vee \neg p$ in allen Bewertungen wahr, also können wir sagen, dass die Formel wahr ist. Ähnliches gilt für den Fall, dass die Formel in allen Auswertungen falsch ist.

Solche Formeln haben dann eine besondere Bezeichnung. Eine Formel, die in allen Auswertungen wahr ist, nennt man eine Tautologie. Eine Formel, die in keiner Auswertung erfüllt ist, nennt man einen Widerspruch.