Seite parallel anzeigen





Du befindest dich hier: Aussagenlogik / Semantik

Formeln & Interpretationen

(Aussagenlogik Kapitel 4.5)

Diese Seite nimmt Bezug auf

(Seite parallel anzeigen)
Liste überspringen

Weitere Themen dieses Kapitels

Liste der weiteren Themen überspringen
Zum Seitenanfang

Wir wissen, wie wir eine Formel bewerten, und ihren Wahrheitsgehalt unter allen möglichen Interpretationen berechnen können.

Nun wollen wir die allgemeinen Definitionen bezüglich Formeln und Interpretationen auf die Aussagenlogik umlegen.

Wir sagen:

Eine Interpretation I erfüllt eine Formel γ, wenn I(γ)=1.
I erfüllt eine Formelmenge Γ, wenn I(γ)=1 für alle Formeln γ ∈ Γ.

Beispiel - Eine Interpretation erfüllt eine Formelmenge

Betrachten wir die Formelmenge Γ bestehend aus den Formeln
  • zug_b_1->falle_c_1|falle_b_2
  • zug_a_2->falle_b_2
  • !zug_b_1
und die Interpretation I = {
  • zug_b_1→0
  • zug_a_2→0
  • falle_b_2→0
  • falle_c_1→1
}

Wie man an den folgenden Tabellen sieht, evaluieren alle Formeln γ ∈ Γ unter I zu wahr - d.h. I erfüllt Γ:

falle_b_2 falle_c_1 zug_b_1 falle_c_1|falle_b_2 zug_b_1->falle_c_1|falle_b_2
0  1  0  1  1 

falle_b_2 zug_a_2 zug_a_2->falle_b_2
0  0  1 

zug_b_1 !zug_b_1
0  1 
I ist ein Modell einer Formel γ, wenn I γ erfüllt, also I(γ)=1.
Mit Mod(γ) bezeichnen wir die Menge aller Modelle von γ

I ist ein Modell einer Formelmenge Γ, wenn I Γ erfüllt.
Mod(Γ) ist die Menge aller Modelle von Γ.

Beispiel - Modelle einer Formel

Betrachten wir wieder das obige Beispiel.
Da I Γ erfüllt, ist I ist ein Modell von Γ

Betrachten wir die Wahrheitstabelle der Formel
  • γ = zug_b_1<->falle_c_1|falle_b_2

falle_b_2 falle_c_1 zug_b_1 falle_c_1|falle_b_2 zug_b_1<->falle_c_1|falle_b_2
0  0  0  0  1 
0  0  1  0  0 
0  1  0  1  0 
0  1  1  1  1 
1  0  0  1  0 
1  0  1  1  1 
1  1  0  1  0 
1  1  1  1  1 

so sehen wir, dass die Menge aller Modelle folgende Elemente enthält:
Mod(γ) = {
  • { falle_b_2→0, falle_c_1→0, zug_b_1→0 }
  • { falle_b_2→0, falle_c_1→1, zug_b_1→1 }
  • { falle_b_2→1, falle_c_1→0, zug_b_1→1 }
  • { falle_b_2→1, falle_c_1→1, zug_b_1→1 }
}
Stimmen die Modelle zweier Formeln γ und δ überein, gilt also Mod(γ)=Mod(δ), sagen wir, diese Formeln seien äquivalent, und schreiben γ ≡ δ.

Beispiel - Äquivalente Formeln

Betrachten wir die beiden Formeln
  • γ = !(a&b) und
  • δ = !a|!b

An den Wahrheitstabellen
a b a&b !(a&b)
0  0  0  1 
0  1  0  1 
1  0  0  1 
1  1  1  0 
a b !a !b !a|!b
0  0  1  1  1 
0  1  1  0  1 
1  0  0  1  1 
1  1  0  0  0 

sehen wir, dass Mod(γ) = Mod(δ) = {
  • { a→0, b→0 }
  • { a→0, b→1 }
  • { a→1, b→0 }
} gilt.

Die beiden Formeln sind also äquivalent, und wir schreiben
  • !(a&b) ≡ !a|!b

Im Folgenden werden wir einige Beispiele zum Verhältnis zwischen Formeln und Interpretationen anführen.