Wahrheitstabelle

Animation zur Erstellung einer Wahrheitstafel

Eine Wahrheitstabelle oder Wahrheitstafel, auch Wahrheitswert-Tabelle oder Wahrheitsmatrix genannt, ist eine tabellarische Aufstellung des Wahrheitswertverlaufs einer logischen Aussage.

Die Wahrheitstabelle zeigt für alle möglichen Zuordnungen von endlich vielen (häufig zwei) Wahrheitswerten zu den aussagenlogisch nicht weiter zerlegbaren Teilaussagen, aus denen die Gesamtaussage zusammengesetzt ist, welchen Wahrheitswert die Gesamtaussage unter der jeweiligen Zuordnung annimmt. Die Wahrheitstabelle wird genutzt, um Wahrheitswertefunktionen beziehungsweise boolesche Funktionen darzustellen oder zu definieren und um einfache aussagenlogische Nachweise zu führen. Beispielsweise werden Wahrheitstabellen verwendet, um die Bedeutung von Junktoren festzulegen.

Darstellung boolescher Funktionen

Für den zweiwertigen Fall wird der Wahrheitswert „wahr“ im Folgenden als und „falsch“ als bezeichnet.

Für mehrwertige Fälle werden oft numerische Werte im Bereich von $0$ bis verwendet (im dreiwertigen Fall z.B. die Werte $0$ , ${\tfrac {1}{2}}=0{,}5$ und , im fünfwertigen Fall die Werte $0$ , ${\tfrac {1}{4}}=0{,}25$ , ${\tfrac {1}{2}}=0{,}5$ , ${\tfrac {3}{4}}=0{,}75$ und ). Im mehrwertigen Fall wird oft nicht von Wahrheitswerten, sondern von Quasiwahrheitswerten oder von Pseudowahrheitswerten gesprochen.

Allgemein gibt es für eine m-wertige Logik, d.h. für eine Logik mit endlich vielen Wahrheitswerten, deren Anzahl m ist, $m^{m^{n}}$ n-stellige wahrheitsfunktionale Junktoren bzw. boolesche Funktionen. Für die zweiwertige Aussagenlogik gibt es also $2^{2^{1}}=4$ einstellige Junktoren und $2^{2^{2}}=16$ zweistellige Junktoren. Schon für die dreiwertige Aussagenlogik gibt es $3^{3^{1}}=27$ einstellige und $3^{3^{2}}=19\,683$ zweistellige Junktoren.

Negation
	$\lnot a$
w	f
f	w

Als ein Beispiel für eine einstellige Wahrheitswertefunktion einer zwei-wertigen Logik dient hier die nebenstehende Wahrheitstafel, die das Ergebnis der Anwendung der Negation auf die Aussage in der klassischen Aussagenlogik zeigt.

Die folgende Tabelle gibt für jeden Wahrheitswert der Aussagen und das Resultat einiger zweiwertiger Verknüpfungen an:

Belegung		Konjunktion	Disjunktion	materiale Implikation	Äquivalenz Bikonditional
		AND	OR	Konditional	XNOR
w	w	w	w	w	w
w	f	f	w	f	f
f	w	f	w	w	f
f	f	f	f	w	w

Eine besondere Stellung haben folgende nach Henry Maurice Sheffer bzw. Charles Sanders Peirce benannte zweiwertige Funktionen (siehe hierzu Funktionale Vollständigkeit Shefferscher Strich), denen das NAND- und das NOR-Gatter entsprechen:

		Shefferscher Strich (NAND, )	Peirce-Pfeil (NOR, $\downarrow$ )
w	w	f	f
w	f	w	f
f	w	w	f
f	f	w	w

In einer dreiwertigen Logik sind 19 683 zweistellige Verknüpfungen möglich. In der folgenden Tabelle sind zwei von ihnen dargestellt: Die Konjunktion aus der logischen Sprache Ł3 von Jan Łukasiewicz (1920) und die Konjunktion aus dem Kalkül B3 von Dmitrij Anatol'evič Bočvar (1938).

Belegung		Konjunktion
		in Ł3	in B3
1	1	1	1
1	½	½	½
1	0	0	0
½	1	½	½
½	½	½	½
½	0	0	½
0	1	0	0
0	½	0	½
0	0	0	0

Eine vierwertige Logik hat bis zu $4^{4^{2}}=4\,294\,967\,296$ mögliche zweistelligen Operatoren. Hier als Beispiel die Wahrheitstafel für das Konditional bzw. die materiale Implikation im logischen System G4 von Kurt Gödel (1932).

Belegung		Konditional
		in G4
1	1	1
1	²⁄₃	²⁄₃
1	¹⁄₃	¹⁄₃
1	0	0
²⁄₃	1	1
²⁄₃	²⁄₃	1
²⁄₃	¹⁄₃	¹⁄₃
²⁄₃	0	0
¹⁄₃	1	1
¹⁄₃	²⁄₃	1
¹⁄₃	¹⁄₃	1
¹⁄₃	0	0
0	1	1
0	²⁄₃	1
0	¹⁄₃	1
0	0	1

Beweis- und Entscheidungsverfahren

Wahrheitstabellen eignen sich dazu, einfache aussagenlogische Beweise auf der semantischen Modellebene zu führen, insbesondere für die Gültigkeit von grundlegenden Gesetzen, auf denen logische Beweisverfahren aufbauen. Zum Beispiel zeigt die logische Äquivalenz der 3. und 4. Spalte in den folgenden Wahrheitstabellen die Gültigkeit der De Morganschen Gesetze:

$\lnot (a\land b)=(\lnot a)\lor (\lnot b)$

		$\lnot (a\land b)$	$(\lnot a)\lor (\lnot b)$
w	w	f	f
w	f	w	w
f	w	w	w
f	f	w	w

$\lnot (a\lor b)=(\lnot a)\land (\lnot b)$

		$\lnot (a\lor b)$	$(\lnot a)\land (\lnot b)$
w	w	f	f
w	f	f	f
f	w	f	f
f	f	w	w

In der Praxis eignet sich diese Art der Beweisführung allerdings nur für Aussagen mit einer kleinen Anzahl von Aussagenvariablen, da die Größe exponentiell in der Anzahl der Variablen wächst.

Für die Aussagenlogik mit endlich vielen Wahrheitswerten und klassischem Folgerungsbegriff (siehe Klassische Logik) sind Wahrheitstafeln ein Entscheidungsverfahren für viele wichtige Fragestellungen, das heißt ein Verfahren, mit dem sich die jeweilige Fragestellung für jede Aussage in endlicher Zeit mechanisch entscheiden lässt. So lässt sich mit Hilfe von Wahrheitstafeln die Frage entscheiden, ob eine gegebene Aussage erfüllbar, unerfüllbar oder tautologisch ist (siehe Erfüllbarkeitsproblem der Aussagenlogik); ebenso lässt sich entscheiden, ob ein Argument gültig oder ungültig ist.

Umformung in andere Darstellungsformen

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

Zur Geschichte

Wenn man unter einer Wahrheitstabelle die homomorphe Zuordnung von Wahrheitswerten zu den in einer Aussage vorkommenden atomaren Aussagen versteht, dann geht die Wahrheitstabelle auf Philon von Megara zurück, der auf diese Weise im 4. Jahrhundert vor unserer Zeitrechnung die Wahrheitsfunktion für die materiale Implikation definierte. Auch in der von Chrysippos von Soloi geprägten stoischen Logik wurden Wahrheitstabellen in diesem Sinn umfassend verwendet.

In der modernen Logik benutzte George Boole 1847 Wahrheitstafeln unter dem Namen „Module einer Funktion“ zur semantischen Entscheidbarkeit von logischen Termen (Funktionen). Später benützten auch Gottlob Frege und Charles Sanders Peirce dieses Entscheidungsverfahren, wobei Peirce den Zweck der Ermittlung von Tautologien deutlicher betonte. Wahrheitstabellen im wörtlichen Sinn als Tabellen wurden allerdings erst 1921 von Emil Leon Post und Ludwig Wittgenstein eingeführt; durch ihren Einfluss wurden Wahrheitstabellen als Verfahren zur Entscheidung für Tautologien Allgemeingut.

Basierend auf einem Artikel in:

Wikipedia.de