Beispiel einer Wahrheitstafel
Wahrheitstafeln (oder auch Wahrheitswertetafeln) bieten eine Möglichkeit, die verschiedenen möglichen Interpretationen (vgl. Semantik und Interpretationen) für eine Formel aufzustellen. Dazu wird eine Tabelle angelegt in deren erste Spalten die in der Formel vorkommenden aussagenlogischen Variablen abgetragen werden. Die Zeilen der Tabelle bilden alle möglichen Wertekombinationen für diese Variablen ab. Dadurch wird ein großer Nachteil von Wahrheitstafeln offenbar: mit steigender Anzahl aussagenlogischer Variablen wird die Tabelle schnell sehr umfangreich. Die eigentliche Aufstellung der Interpretation erfolgt, indem man der Tabelle die Formel als letzte Spalte hinzufügt und dort das Ergebnis bezogen auf die jeweilige Variablenbelegung abträgt. Bei umfangreichen Formeln ist es sinnvoll, zusätzliche Spalten für Teilformeln einzufügen.
Mittels Wahrheitstafeln kann vergleichsweise einfach die (Un)erfüllbarkeit oder Allgemeingültigkeit einer Formel nachgewiesen werden. Das Verfahren an sich ist jedoch aufwändig, da alle Kombinationen für Variablenbelegungen aufgestellt werden müssen. Auch Umformungen verringern den Aufwand dieses "Brute-Force"-Ansatzes nur bedingt (nur, wenn durch Umformung Variablen komplett eliminiert werden können), da die Komplexität hauptsächlich von der Anzahl der vorkommenden Variablen abhängt.
Das Verfahren soll am folgenden Beispiel exemplarisch durchgeführt werden:
Ermittlung aller möglichen Interpretationen für die Formel $$ (a \land b) \land (\neg{a} \lor b) $$ mittels Wahrheitstafel.
| $$ a $$ | $$ b $$ | $$ \neg{a} $$ | $$ (a \land b) $$ | $$ (\neg{a} \lor b) $$ | $$ (a \land b) \land (\neg{a} \lor b) $$ |
| w | w | f | w | w | w |
| w | f | f | f | f | f |
| f | w | w | f | w | f |
| f | f | w | f | w | f |