Seite parallel anzeigen





Du befindest dich hier: Aussagenlogik / Semantik

Wahrheitstabellen

(Aussagenlogik Kapitel 4.3)

Diese Seite nimmt Bezug auf

(Seite parallel anzeigen)
Liste überspringen
Zum Seitenanfang

Wahrheitstabellen sind eine einfache und übersichtliche Möglichkeit, den Wahrheitsgehalt einer Formel unter allen möglichen Interpretationen zu berechnen.

Die Spalten der Wahrheitstabelle

Da sich die Bewertung einer Formel aus den Bewertungen ihrer unmittelbaren Teilformeln ergibt, entsprechen die Spalten der Tabelle den Bewertungen der Teilformeln, wobei wir von links nach rechts mit den atomaren Formeln anfangen, und dann immer komplexer werdend in der rechten Spalte mit der Gesamtformel enden.

Stellen wir uns die Formel als Baum vor, bauen wir die Spalten der Tabelle auf, indem wir uns im Baum von den Blättern zur Wurzel hinauf arbeiten.
Den Spalten weisen wir von links nach rechts die Entsprechung der Teilbäume zu, die den aktuellen Knoten als Wurzel haben.
Redundante Spalten können wir selbstverständlich streichen.

Beispiel - Spalten der Wahrheitstabelle

Betrachten wir die Formel
  • a&!b->c

Der Formelbaum
schaut folgendermaßen aus
->
&
a !

b
c
Die Menge der Teilformeln
besteht aus
  • a
  • b
  • c
  • !b
  • a&!b
  • a&!b->c

Die Wahrheitstabelle hat also folgende Spalten

a b c !b a&!b a&!b->c

Die Zeilen der Wahrheitstabelle

Die Zeilen der Tabelle entsprechen den Bewertungen der Teilformeln bezüglich den Interpretationen.

Um die Tabelle mit Werten zu befüllen und so die Bewertungen der Gesamtformel zu erhalten, arbeiten wir uns pro Zeile von links nach rechts durch die Spalten:
Wir beginnen mit der Bewertung der Atome, und können dann aus den Werten der bereits befüllten Spalten leicht die Bewertung der aktuellen Teilformel bestimmen.

Beispiel - Eine Zeile der Wahrheitstabelle

Betrachten wir wieder die Formel
  • a&!b->c
und die Interpretation
Befüllen wir also zunächst die Spalten, die die Bewertung der Atome repräsentieren.
a b c !b a&!b a&!b->c
0  0  1       
Die nächste Spalte repräsentiert die Bewertung der Formel γ
  • γ = !b
Die unmittelbare Teilformel ist
  • b
deren Bewertung wir bereits in die Tabelle eingetragen haben.
Aus der Definition der Bewertungsfunktion ergibt sich daraus sofort die Bewertung von γ.
a b c !b a&!b a&!b->c
0  0  1  1     
Die nächste Spalte repräsentiert die Bewertung der Formel γ
  • γ = a&!b
Die unmittelbaren Teilformeln sind
  • a, und
  • !b
deren Bewertungen wir bereits in die Tabelle eingetragen haben.
Aus der Definition der Bewertungsfunktion ergibt sich daraus sofort die Bewertung von γ.
a b c !b a&!b a&!b->c
0  0  1  1  0   
Die nächste Spalte repräsentiert die Bewertung der Gesamtformel, also von
  • γ = a&!b->c
Die unmittelbaren Teilformeln sind
  • a&!b, und
  • c
deren Bewertungen wir bereits in die Tabelle eingetragen haben.
Aus der Definition der Bewertungsfunktion ergibt sich daraus sofort die Bewertung von γ.
a b c !b a&!b a&!b->c
0  0  1  1  0  1 

Wahrheitswertekombinationen

Da es für eine Formel mit n Atomen 2n mögliche Interpretationen gibt, hat die gesamte Wahrheitstabelle immer 2n Zeilen.

Eine einfache Methode, alle Wahrheitswertekombinationen aufzuzählen besteht darin, sich jede Kombination als n-stellige Binärzahl vorzustellen, wobei jeder Stelle dieser Zahl ein Atom zugeordnet ist.
Beginnen wir also bei der Darstellung von 0, addieren pro Zeile 1 und weisen den Atomen die Werte an den entsprechenden Positionen der Binärzahl zu, erhalten wir eine übersichtliche Aufzählung aller möglichen Kombinationen.

Beispiel - Die Wahrheitstabelle

Betrachten wir wieder die Formel
  • a&!b->c
Diese hat die 3 Atome
  • a
  • b
  • c
Jede Interpretation der Formel kann also als 3-stellige Binärzahl dargestellt werden: wir wollen hier
  • die 1. Stelle dem Atom 'a',
  • die 2. Stelle dem Atom 'b', und
  • die 3. Stelle dem Atom 'c'
zuordnen.

Es existieren 23=8 mögliche Interpretationen, und somit Zeilen der Wahrheitstabelle.
Nummerieren wir die Zeilen von 0 bis 7, können wir die 3-stellige binäre Darstellung der Zeilennummer als Interpretation betrachten:

Z.B. der Zeile 5 entspricht die 3-stellige Binärzahl 011.
Nach obiger Zuordnung erhalten wir
  • I = { a→ 1 , b→ 0 , c→ 1 }

Zeile binäre Darstellung a b c !b a&!b a&!b->c
5 101 1  0  1       


Somit erhalten wir folgende Wahrheitstabelle:

Zeile binäre Darstellung a b c !b a&!b a&!b->c
0 000 0  0  0  1  0  1 
1 001 0  0  1  1  0  1 
2 010 0  1  0  0  0  1 
3 011 0  1  1  0  0  1 
4 100 1  0  0  1  1  0 
5 101 1  0  1  1  1  1 
6 110 1  1  0  0  0  1 
7 111 1  1  1  0  0  1