Wahrheitstabellen

Wahrheitstabellen sind eine Methode der Logik, mit der der Wahrheitswert einer propositionalen Formel für alle möglichen Belegungen ihrer Variablen dargestellt wird. Für jede Variable gibt es zwei mögliche Werte (wahr oder falsch). Die Tabelle enthält eine Zeile pro möglicher Belegung der Variablen (bei n Variablen 2^n Zeilen) sowie Spalten für die Variablen, Zwischenformeln und die Endformel. Typischerweise werden Wahrheitswerte mit wahr/falsch oder 1/0 angegeben.

Aufbau und Vorgehen: Zunächst werden alle Variablen aufgelistet und dann alle möglichen Kombinationen dieser Werte erzeugt. In jeder Zeile wird die Formel bzw. deren Teilformen mit den in dieser Zeile gegebenen Variablenwerten ausgewertet. Das Ergebnis steht in der letzten Spalte. Aus der Tabelle lassen sich Eigenschaften der Formula ableiten: Eine Tautologie hat in allen Zeilen wahr, eine Kontradiktion ist in allen Zeilen falsch, und eine satisfiable Formel ist wahr in mindestens einer Zeile.

Beispiel: Für A und B mit der Konjunktion A ∧ B ergibt sich eine Tabelle mit vier Zeilen:

A B | A∧B

wahr wahr -> wahr

wahr falsch -> falsch

falsch wahr -> falsch

falsch falsch -> falsch

Anwendung und Bedeutung: Wahrheitstabellen dienen der Verifikation logischer Äquivalenzen, der Bestimmung von Tautologien und Erfüllbarkeiten sowie der Planung und Analyse digitaler Schaltungen (logische Gatter). Sie ermöglichen eine klare, visuelle Überprüfung von logischen Ausdrücken. Ihre Begrenzung liegt in der exponentiellen Zunahme der Zeilenanzahl bei zunehmender Zahl von Variablen; bei vielen Variablen werden andere methoden der logik benutzt. Trotzdem bleiben Wahrheitstabellen ein grundlegendes Lehr- und Hilfsmittel in Logik, Informatik und digitalen Systemen.