Wahrheitstabelle
Eine Wahrheitstabelle ist eine Tabelle, die in der Aussagenlogik jeder Kombination einer bestimmten Anzahl von Wahrheitswerten (häufig zwei) einen bestimmten Resultatwert zuordnet. Sie wird genutzt um boolesche Funktionen darzustellen und um einfache aussagenlogische Beweise zu führen. Sie ordnet der rein beschreibenden Form (Syntax), einer Aussagenverknüpfung, eine Bedeutung (Semantik) zu.
Darstellung boolescher Funktionen
Die einfachste Wahrheitstabelle zeigt das Ergebnis der Negation einer Aussage:
| a | Negation NOT |
|---|---|
| w | f |
| f | w |
Die folgende Tabelle gibt für jeden Wahrheitswert der Aussagen a und b das Resultat der entsprechenden Verknüpfung an:
| a | b | Konjunktion AND | Disjunktion OR | Implikation | Äquivalenz XNOR |
|---|---|---|---|---|---|
| f | f | f | f | w | w |
| f | w | f | w | w | f |
| w | f | f | w | f | f |
| w | w | w | w | w | w |
Die oben dargestellten Verknüpfungen sind vier von, bei 2 Eingangsvariablen, 16 möglichen logischen Funktionen.
Wichtig sind auch noch folgende:
| a | b | Sheffer-Operation (NAND) | Peirce-Operation (NOR) |
|---|---|---|---|
| f | f | w | w |
| f | w | w | f |
| w | f | w | f |
| w | w | f | f |
Beweisverfahren
Wahrheitstabellen eignen sich dazu, einfache aussagenlogische Beweise zu führen, insbesondere für die Gültigkeit von grundlegenden Gesetzen, auf denen andere Beweisverfahren aufbauen. Z.B. zeigt die logische Äquivalenz der 3. und 4. Spalte in den folgenden Wahrheitstabellen die Gültigkeit der De Morganschen Gesetze:
- nicht (a und b) = (nicht a) oder (nicht b)
| a | b | nicht (a und b) | nicht (a) oder nicht (b) |
|---|---|---|---|
| f | f | w | w |
| w | f | w | w |
| f | w | w | w |
| w | w | f | f |
- nicht (a oder b) = (nicht a) und (nicht b)
| a | b | nicht (a oder b) | nicht (a) und nicht (b) |
|---|---|---|---|
| f | f | w | w |
| w | f | f | f |
| f | w | f | f |
| w | w | f | f |
Diese Art der Beweisführung eignet sich aber nur für Aussagen mit einer kleinen Anzahl von Aussagenvariablen, da die Größe exponentiell in der Anzahl der Variablen wächst.
Siehe auch: Charles Peirce, Logik