Wahrheitstabelle

Begriff und Zweck

Eine Wahrheitstabelle, auch Wahrheitstafel, Wahrheitswert-Tabelle oder Wahrheitsmatrix genannt, ist eine tabellarische Darstellung des Wahrheitswertverlaufs einer logischen Aussage. Sie zeigt für jede mögliche Zuordnung von Wahrheitswerten zu den nicht weiter zerlegbaren Teilaussagen, welchen Wahrheitswert die gesamte zusammengesetzte Aussage annimmt.

Wahrheitstabellen werden verwendet, um Wahrheitswertefunktionen beziehungsweise boolesche Funktionen darzustellen oder zu definieren. Außerdem ermöglichen sie einfache aussagenlogische Nachweise. So lässt sich beispielsweise die Bedeutung logischer Verknüpfungen, der sogenannten Junktoren, durch die Zuordnung von Eingangs- zu Ergebniswerten festlegen.

Boolesche Funktionen und Verknüpfungen

In der zweiwertigen Logik werden die Wahrheitswerte „wahr“ und „falsch“ häufig mit w und f bezeichnet. Für eine m-wertige Logik mit endlich vielen Wahrheitswerten gibt es für n-stellige wahrheitsfunktionale Junktoren insgesamt m^(m^n) Möglichkeiten. In der zweiwertigen Aussagenlogik existieren daher 2^(2^1) = 4 einstellige und 2^(2^2) = 16 zweistellige Junktoren. In der dreiwertigen Logik gibt es 3^(3^1) = 27 einstellige und 3^(3^2) = 19 683 zweistellige Junktoren.

Ein einfaches einstellige Beispiel ist die Negation ¬a: Ist a wahr, so ist ¬a falsch; ist a falsch, so ist ¬a wahr.

Für zwei Aussagen a und b gelten bei den im Artikel aufgeführten zweiwertigen Verknüpfungen folgende Ergebnisse:

• Konjunktion (AND): Sie ist nur bei a = w und b = w wahr.
• Disjunktion (OR): Sie ist nur bei a = f und b = f falsch.
• Materiale Implikation (Konditional): Sie ist nur bei a = w und b = f falsch.
• Äquivalenz beziehungsweise Bikonditional (XNOR): Sie ist wahr, wenn a und b denselben Wahrheitswert haben, und falsch, wenn sie verschieden sind.

Der Sheffersche Strich | entspricht NAND. Er ist nur bei a = w und b = w falsch. Der Peirce-Pfeil ↓ entspricht NOR. Er ist nur bei a = f und b = f wahr. Diese beiden Funktionen haben eine besondere Stellung; ihnen entsprechen NAND- beziehungsweise NOR-Gatter.

Wahrheitstabellen können auch mehrwertige Logiken darstellen. Dabei werden oft Zahlen zwischen 0 und 1 verwendet. Im dreiwertigen Fall sind dies beispielsweise 0, 1/2 = 0,5 und 1; im fünfwertigen Fall 0, 1/4 = 0,25, 1/2 = 0,5, 3/4 = 0,75 und 1. Solche Werte werden häufig Quasiwahrheitswerte oder Pseudowahrheitswerte genannt.

In der dreiwertigen Logik sind 19 683 zweistellige Verknüpfungen möglich. Der Artikel zeigt als Beispiele die Konjunktion in der Sprache Ł3 von Jan Łukasiewicz (1920) und im Kalkül B3 von Dmitrij Anatol'evič Bočvar (1938). Beide Systeme verwenden die Werte 1, 1/2 und 0, ordnen den Kombinationen aber teilweise unterschiedliche Ergebnisse zu. Eine vierwertige Logik hat bis zu 4^(4^2) = 4 294 967 296 mögliche zweistellige Operatoren. Als Beispiel wird das Konditional im logischen System G4 von Kurt Gödel (1932) mit den Werten 1, 2/3, 1/3 und 0 angegeben.

Beweise und Entscheidungsverfahren

Wahrheitstabellen eignen sich für einfache aussagenlogische Beweise auf der semantischen Modellebene. Insbesondere kann man prüfen, ob grundlegende logische Gesetze für jede mögliche Belegung gelten. Die De-Morganschen Gesetze werden dadurch bestätigt, dass die entsprechenden Spalten jeweils dieselben Wahrheitswerte besitzen:

¬(a ∧ b) = (¬a) ∨ (¬b)

¬(a ∨ b) = (¬a) ∧ (¬b)

Die Methode ist jedoch nur bei einer kleinen Anzahl von Aussagenvariablen praktisch, weil die Zahl der Tabellenzeilen exponentiell wächst.

Für eine Aussagenlogik mit endlich vielen Wahrheitswerten und klassischem Folgerungsbegriff sind Wahrheitstabellen ein Entscheidungsverfahren. Das bedeutet, dass eine Fragestellung für jede Aussage in endlicher Zeit mechanisch entschieden werden kann. Mit ihrer Hilfe lässt sich bestimmen, ob eine Aussage erfüllbar, unerfüllbar oder tautologisch ist. Ebenso kann geprüft werden, ob ein Argument gültig oder ungültig ist.

Wahrheitswertanalyse nach Quine

Bei n zweiwertigen Aussagenvariablen müssen Wahrheitstabellen 2^n Fälle berücksichtigen: Bei 2 Variablen sind es 4, bei 3 Variablen 8 und bei 4 Variablen 16 Fälle. Bei vielen Variablen kann die vollständige Tabelle deshalb aufwändig werden.

W. V. O. Quine schlägt in Grundzüge der Logik eine alternative Wahrheitswertanalyse vor. Dabei werden die Variablen beziehungsweise Satzbuchstaben schrittweise durch ihre Wahrheitswerte ersetzt. Die Fallunterscheidungen werden zeilenweise vorgenommen, sodass eine baumartige Struktur entsteht. Nicht immer müssen dabei alle möglichen Fälle verfolgt werden. Die Methode kann daher bei vielen Variablen gegenüber einer vollständigen Wahrheitstabelle vorteilhaft sein. Beide Verfahren ermitteln jedoch exakt die Fälle, in denen ein Term wahr oder falsch wird, und sind deshalb äquivalent.

Als Beispiel behandelt Quine den Term (P ∧ Q) ∨ (¬P ∧ ¬R) → (Q ↔ R) mit den Variablen P, Q und R. Die Analyse ergibt, dass der Term in zwei Fällen falsch ist: bei P = w, Q = w, R = f sowie bei P = f, Q = w, R = f.

Ein einfacheres Beispiel ist die Definition der Implikation:

(A → B) ↔ (¬A ∨ B)

Die Wahrheitstabelle zeigt, dass beide Seiten bei allen vier Belegungen von A und B denselben Wahrheitswert besitzen. Die schrittweise Analyse nach Quine führt ebenfalls zum Ergebnis, dass der gesamte Ausdruck wahr ist.

Umformung und historische Entwicklung

Der Inhalt einer Wahrheitstabelle kann zur weiteren Verarbeitung oder Vereinfachung in eine andere äquivalente Darstellungsform überführt werden, beispielsweise in ein Karnaugh-Veitch-Diagramm.

Historisch wird die Zuordnung von Wahrheitswerten zu atomaren Aussagen bereits Philon von Megara zugeschrieben, der im 4. Jahrhundert vor unserer Zeitrechnung die Wahrheitsfunktion der materialen Implikation definierte. Auch in der stoischen Logik, die besonders von Chrysippos von Soloi geprägt wurde, wurden solche Zuordnungen umfassend verwendet.

George Boole benutzte 1847 Wahrheitstafeln unter der Bezeichnung „Module einer Funktion“ zur semantischen Entscheidbarkeit logischer Terme. Später verwendeten auch Gottlob Frege und Charles Sanders Peirce dieses Entscheidungsverfahren; Peirce betonte besonders die Ermittlung von Tautologien. Wahrheitstabellen im wörtlichen Sinn als Tabellen wurden 1921 von Emil Leon Post und Ludwig Wittgenstein eingeführt. Dadurch wurden sie als Verfahren zur Entscheidung über Tautologien allgemein bekannt.