Database Reference
In-Depth Information
Die Erfullungsrelation wird mit Hilfe der Wahrheitswertefunktion definiert: Eine
Interpretation I erfullt eine Formel F genau dann, wenn ihr Wahrheitswert in I
wahr ist.
Definition 3.10 (Erfullungsrelation)
Fur I
∈
Int
(Σ) und F
∈
Formel
(Σ) gilt:
I
|
=
Σ
F
gdw. [[F ]]
I
=
true
3.3.2
Modelle und logische Folgerung
Definition 3.11 (Modell)
Sei F
∈
Formel
(Σ) eine Σ-Formel und I
∈
Int
(Σ) eine
Σ-Interpretation. Fur “I erfullt F ”, geschrieben I
|
=
Σ
F , sagen wir auch
•
“F gilt in I”,
•
“F ist wahr fur I”oder
•
“I ist ein
(
Σ
-)Modell
von F ”.
Die Menge
Mod
Σ
(F)
⊆
Int
(Σ) bezeichnet die Menge aller Σ-Modelle von F .Die
Bezeichnungen I
=
Σ
FM
und Mod
Σ
(
FM
) verwenden wir auch, wenn
FM
eine
Menge von Formeln ist. Dabei gilt
|
I
|
=
Σ
FM
gdw.
I
|
=
Σ
F
fur jedes F
∈
FM
.
Besonders interessant sind solche Formeln, die fur alle moglichen Interpretationen,
d.h. in allen denkbaren Welten, wahr sind. Beispielsweise ist
“Die Ampel ist grun oder die Ampel ist nicht grun”
fur jede mogliche Interpretation wahr. (Jede Formel der Art A
A ist in allen
moglichen Interpretationen wahr.) Derartige Formeln heißen allgemeingultig.
∨¬
Definition 3.12 (erfullbar, unerfullbar, allgemeingultig, falsifizierbar)
Eine Formel F ist
•
erfullbar
(konsistent, Konsistenz) gdw. Mod
Σ
(F )
=
∅
, d.h., wenn sie von
wenigstens einer Interpretation erfullt wird.
•
unerfullbar
(widerspruchlich, inkonsistent, Kontradiktion) gdw. Mod
Σ
(F )=
∅
, d.h., wenn sie von keiner Interpretation erfullt wird.
•
allgemeingultig
(Tautologie) gdw. Mod
Σ
(F )=
Int
(Σ), d.h., wenn sie von jeder
Interpretation erfullt wird.
•
falsifizierbar
gdw. Mod
Σ
(F )
=
Int
(Σ), d.h., wenn sie von wenigstens einer
Interpretation nicht erfullt (d.h. falsifiziert) wird.
Wie zuvor werden diese Begriffe in analoger Weise auch fur Formelmengen verwen-
det.
