Wahrheitswert von Formeln

Wenn wir einige atomare Aussagen haben, die wir zu einer Formel zusammensetzen, können wir versuchen zu entscheiden, ob die ganze Formel wahr oder falsch ist.

Wahrheit einer Aussage

Zuerst präzisieren wir, was der Wahrheitswert einer Aussage ist. Haben wir eine Aussage p, sollten wir entscheiden können, ob sie wahr oder falsch ist. Eine wahre Aussage hat den Wahrheitswert 1 und eine falsche 0.

Die Belegung ist dann eine Vorschrift e, die der gegebenen Aussage entweder 0 oder 1 zuordnet. Wenn wir e(p) schreiben, wollen wir die Wahrheit der Aussage p herausfinden. Ist p gleich der Aussage „zweimal zwei ist vier“, dann ist e(p) = 1, weil es sich um eine wahre Aussage handelt. Ist q gleich der Aussage „Max ist eine Frau“, dann ist e(q) = 0, weil Max keine Frau ist. e ist also eine Funktion, die uns zurückgibt, ob die Aussage wahr ist.

Hier muss man sich klarmachen, 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 Max ein Mann oder eine Frau ist. Wir sollten zu Beginn der Rechnung festlegen, wie sich die Belegungsfunktion verhalten soll. Wenn wir ihr sagen, dass Max eine Frau ist, gibt sie uns e(q) = 1 zurück.

Wahrheit der Junktoren

Um den Wahrheitswert einer Formel bestimmen zu können, müssen wir wissen, wie man den Wahrheitswert von Junktoren auswertet. Wenn wir also die Belegung e(p) und e(q) kennen, welchen Wahrheitswert haben dann die Formeln p ∧ q, p ⇒ q usw.

Jeder Junktor verhält sich anders und wird für etwas anderes verwendet, deshalb gehen wir jeden Junktor einzeln durch.

Wahrheit der Konjunktion

Die Konjunktion wird mit p ∧ q bezeichnet und als „p und gleichzeitig q“ gelesen. Nehmen wir als Beispiel die Formel „Deutschland liegt in Mitteleuropa und gleichzeitig ist seine Hauptstadt Berlin“. Wann ist dieser ganze Satz wahr?

Beim Bestimmen der Wahrheit hilft uns schon der Junktor „und gleichzeitig“ selbst. Er sagt uns ausdrücklich, dass beide Aussagen links und rechts wahr sein sollen. Sind also beide Aussagen p und q wahr, also e(p) = 1 und e(q) = 1, dann ist auch die ganze Konjunktion wahr. Im anderen Fall, wenn entweder eine der Aussagen falsch ist oder beide falsch sind, ist die ganze Formel falsch.

Ein Beispiel für eine Konjunktion, die nicht wahr ist, kann sein: „Die Elbe ist ein Fluss und gleichzeitig fließt die Elbe durch Russland“. Es stimmt, dass die Elbe ein Fluss ist, aber es stimmt nicht, dass sie durch Russland fließt, also ist die ganze Konjunktion nicht wahr.

Übersichtlich zeigt das die folgende Tabelle:

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

In den ersten beiden Spalten stehen die Wahrheitswerte der Aussagen p und q und in der dritten der Wahrheitswert der Formel p ∧ q.

Wahrheit der Disjunktion

Die Disjunktion wird mit p ∨ q bezeichnet und als „p oder q“ gelesen. Beispiel: „Russland liegt in Europa oder in Asien.“ Wann ist der ganze Satz wahr?

Bei der Disjunktion genügt es, wenn mindestens eine der Möglichkeiten wahr ist. Der Junktor „oder“ lässt uns die Wahl, es genügt, wenn sein linker oder sein rechter Teil wahr ist. Der einzige kleine Unterschied zur Alltagssprache ist, dass das logische Oder auch dann wahr ist, wenn beide Aussagen zugleich erfüllt sind. Das ist nicht unbedingt üblich, in der Alltagssprache verwenden wir „oder“ oft ausschließend, also „entweder … oder …“.

Dazu gibt es einen klassischen Witz: Eine Familie sucht im Autohaus ein neues Auto aus. Der Vater sagt zum Verkäufer: „Wir haben uns entschieden, dass wir ein blaues oder ein rotes Auto nehmen.“ Der Verkäufer hat ihnen beide Autos verkauft. Das ist eine Illustration des Unterschieds zwischen dem logischen und dem umgangssprachlichen Oder: Der Vater meinte wohl, dass sie von diesen Autos genau eines auswählen, während der Verkäufer es für eine gültige Möglichkeit 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 die Sieben eine Primzahl ist. Zwar ist sie nicht durch drei teilbar, aber das stört uns nicht mehr. Wahrheitstabelle:

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

Wahrheit der Implikation

Die Implikation wird mit p ⇒ q bezeichnet und als „wenn p, dann q“ gelesen. Ein Beispiel für eine Implikation kann der Satz „wenn wir viel Wodka trinken, dann müssen wir uns übergeben“ sein. Wann ist der Satz wahr?

Die logische Implikation ist der heimtückischste aller Junktoren und wird auch in der Alltagssprache oft nicht verstanden und mit der Äquivalenz verwechselt. Versuchen wir die Frage zu beantworten, ob zugleich auch die umgekehrte Implikation gilt: q ⇒ p.

Wir wissen: Wenn wir viel Wodka trinken, dann müssen wir uns übergeben. Gilt zugleich auch, dass wir viel Wodka getrunken haben, wenn wir uns übergeben müssen? Das gilt sicher nicht, wir könnten ganz anderen Alkohol getrunken haben und trotzdem könnte uns schlecht geworden sein, oder uns kann von etwas ganz anderem schlecht sein. Die umgekehrte Implikation muss also nicht automatisch gelten. Wenn p ⇒ q gilt und zugleich q ⇒ p gilt, handelt es sich um eine Äquivalenz, siehe weiter unten.

Ein anderes Beispiel: „Wenn es morgen regnet, dann nimmt Max einen Regenschirm mit.“ Und jetzt sage ich dir, dass Max einen Regenschirm mitgenommen hat. Die Frage lautet: Hat es an diesem Tag geregnet? Viele Leute neigen dazu zu sagen: natürlich ja, schließlich hat Max einen Regenschirm mitgenommen, als es regnen sollte. Aber so ist der ursprüngliche Satz nicht aufgebaut!

Max kann in Wirklichkeit den Regenschirm wegen etwas anderem mitgenommen haben, wovon wir keine Ahnung haben. Vielleicht nimmt Max immer einen Regenschirm mit, wenn er seine Schwiegermutter besuchen geht, um ihr ein Auge auszustechen. Oder er hat beschlossen, sich einen neuen Regenschirm zu kaufen, und will den alten wegwerfen. Das sind alles legitime Gründe, warum Max einen Regenschirm mitgenommen haben kann, obwohl es nicht geregnet haben muss.

Jetzt können wir die Frage beantworten, wann die Implikation wahr ist. Wenn beide Aussagen wahr sind, dann ist die Implikation auf jeden Fall wahr: „Wenn 42 eine natürliche Zahl ist, dann ist sie positiv.“ Beide Aussagen sind wahr, also ist die ganze Implikation wahr. Ein weiteres Beispiel kann die Implikation „wenn 42 eine natürliche Zahl ist, dann ist sie negativ“ sein. Diese Implikation ist nicht wahr, weil wir versuchen, aus einer Wahrheit etwas abzuleiten, was nicht wahr ist.

Schließlich bleiben die Fälle, in denen die erste Aussage falsch ist. In diesem Fall interessiert uns der Wahrheitswert der zweiten Aussage nicht mehr. Wenn wir von einer Unwahrheit ausgehen, können wir danach beliebigen Unsinn reden. Das sind Sätze wie „wenn 1 eine negative Zahl ist, dann sind wir der chinesische Gott des Spaßes“ oder „wenn Pinguine bekannte Bauunternehmer sind, dann ist die Sonne blau“. In solchen Fällen ist die Implikation automatisch wahr, weil sie schlicht von einer Unwahrheit ausgeht. Tabelle:

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

Wahrheit der Äquivalenz

Die Äquivalenz wird p ⇔ q geschrieben und als „p genau dann, wenn q“ gelesen. Ein Beispiel für eine Äquivalenz kann „die Zahl x ist durch zwei teilbar genau dann, wenn sie gerade ist“ sein. Wann ist der ganze Satz wahr?

Bei der Äquivalenz erwarten wir, dass beide Aussagen in solcher Symbiose stehen, dass entweder beide gelten oder keine. Also ist die Zahl x entweder gerade und zugleich durch zwei teilbar, oder sie ist keines von beidem. Es kann nicht der Fall eintreten, dass x gerade wäre, aber nicht durch zwei teilbar.

Beispiel: „Jonas liest ein Buch genau dann, wenn er auf der Toilette sitzt.“ Damit die Äquivalenz erfüllt ist, muss Jonas immer, wenn er auf der Toilette sitzt, ein Buch lesen. Und zugleich muss er immer, wenn er ein Buch liest, auf der Toilette sitzen. Es darf nicht passieren, dass er das Buch zum Beispiel im Bett liest.

Die Äquivalenz können wir mithilfe zweier Implikationen ausdrücken. Also könnten wir p ⇔ q umschreiben als p ⇒ q und zugleich q ⇒ p. Tabelle:

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

Negation

Die Negation ist eine einstellige Verknüpfung, wir schreiben sie entweder mit einem Strich p' oder mit diesem Symbol: ¬p. Die Negation verneint die ursprüngliche Behauptung. Haben wir die Aussage „Anna ist Sängerin“, dann erhalten wir als Negation die Aussage „Es ist nicht wahr, dass Anna Sängerin ist“ oder kürzer „Anna ist keine Sängerin“. Praktisch immer können wir die Negation bilden, indem wir vor die Aussage „Es ist nicht wahr, dass …“ setzen.

Die Negation kehrt den Wahrheitswert um, d. h. aus 0 macht sie 1 und aus 1 macht sie 0. Wir können also ¬0 = 1 und ¬1 = 0 schreiben.

Vorsicht vor einigen heimtückischen Dingen. Nehmen wir die Behauptung „Kalk ist weiß“. Was ist die Negation? Jemand könnte auf die Idee kommen, dass es „Kalk ist schwarz“ ist, aber das stimmt nicht! Wenden wir die vorherige Regel an, ist die Negation die Aussage „es ist nicht wahr, dass Kalk weiß ist“. Bedeutet das zwingend, dass er schwarz sein muss? Nein, er kann zum Beispiel rosarot sein.

Tabelle aller Junktoren

$$\begin{array}{cccccc}p& q& p\wedge q& p\vee q& p\Rightarrow q& p\iff 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}$$

Wahrheitswert der ganzen Formel

Jetzt können wir schon den Wahrheitswert zweier Aussagen auswerten, die durch einen Junktor verbunden sind. Die ganze Formel werten wir völlig analog aus. Haben wir die Formel (p ⇒ q) ∧ r, dann erhalten wir in dem Moment, in dem wir die Formel (p ⇒ q) zum Beispiel zu 1 auswerten, die klassische Konjunktion 1 ∧ r, die wir schon lösen können.

Durch schrittweise Anwendung der einfachsten Junktoren gelangen wir zum resultierenden Wahrheitswert der ganzen Formel. Oft verwendet man dazu die sogenannte Wahrheitstafel, die weiter unten beschrieben wird.

Wahrheitstafel

Die Wahrheitstafel wird beim Auswerten komplizierterer Formeln verwendet. In die ersten n Spalten schreiben wir die n Aussagenvariablen, mit denen die Formel arbeitet, und in die weiteren Spalten setzen wir nach und nach die Teilformeln, die die Formel enthält. An einem Beispiel wird es klarer:

Nehmen wir die Formel (p ∨ q) ∧ (q ⇒ p). Zu Beginn schreiben wir in die Tabelle alle Aussagenvariablen, also p und q, und alle Kombinationen ihrer Belegungen:

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

Weiter schreiben wir Spalten für die einzelnen Teilformeln p ∨ q und q ⇒ p dazu.

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

Jetzt werten wir diese Formeln aus und tragen in die Spalten Nullen oder Einsen ein. In der Tabelle haben wir alle nötigen Informationen. Wir gehen so vor: Wenn wir p ∨ q in der ersten Zeile auswerten, setzen wir für p die 1 ein und für q ebenfalls 1. So erhalten wir den Term 1 ∨ 1. Das Ergebnis der Auswertung dieses Terms 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}$$

So füllen wir nach und nach die ganze Tabelle aus:

$$\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}$$

Jetzt bleibt noch, die ganze Formel auszuwerten. Bezeichnen wir sie zum Beispiel mit φ = (p ∨ q) ∧ (q ⇒ p). Wir fügen der Tabelle eine Spalte mit φ hinzu und werten sie aus, wobei wir zur Auswertung schon die beiden vorherigen Spalten verwenden.

$$\begin{array}{ccccc}p& q& p\vee q& q\Rightarrow p& \phi \\ 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 bestimmt den Wahrheitswert der Formel in allen möglichen Belegungen. Wenn zum Beispiel e(p) = 1 und zugleich e(q) = 1 ist, dann ist die Formel wahr. Ist e(p) = 0 und e(q) = 1, dann ist die Formel nicht wahr.

Beachte, dass wir nicht sagen können, „die Formel ist wahr“. Dieser Satz ergibt keinen Sinn, denn um sagen zu können, dass die Formel wahr ist, müssten wir sagen, in welcher Belegung die Formel wahr ist. Wir können also sagen, dass „die Formel φ in der Belegung e₁ wahr ist und in der Belegung e₂ nicht wahr ist“.

Der einzige Fall, in dem wir sagen könnten, dass die Formel wahr ist, ist, wenn sie in allen möglichen Belegungen wahr ist. Zum Beispiel ist die Formel p ∨ ¬p in allen Belegungen wahr, also können wir sagen, dass die Formel wahr ist. Ähnlich für den Fall, dass eine Formel in allen Belegungen falsch ist.

Solche Formeln haben dann ihre besondere Bezeichnung. Eine Formel, die in allen Belegungen wahr ist, heißt Tautologie. Eine Formel, die in keiner Belegung erfüllt ist, heißt Kontradiktion.