Database Reference
In-Depth Information
Selbsttestaufgabe 3.49 (Wahrheitswerte atomarer Formeln in PL1)
Welchen Wahrheitswert hat jeweils die atomare Formel LT (b, nf(nf(b))) in den
beiden Interpretationen aus der Selbsttestaufgabe 3.42?
der Aussagenlogik werden auch in PL1 benutzt,
um komplexe Formeln zu bilden. Die charakteristischste Eigenschaft von PL1 ist
jedoch die Moglichkeit, Aussagen uber Mengen von Objekten ausdrucken zu konnen,
ohne diese Objekte einzeln aufzahlen zu mussen. Dafur stellt PL1 zwei Quantoren
-den
Allquantor
Die Junktoren
¬
,
∧
,
∨
,
⇒
,
⇔
∀
und den
Existenzquantor
∃
-zurVerfugung:
∀
xF
“Fur alle x gilt F ”
∃
xF
“Es gibt ein x,fur das F gilt”
Definition 3.50 (Formeln)
Die Menge
Formel
Σ
(V)
der Formeln uber einer Si-
gnatur Σ = (
Func
,
Pred
) und einer Menge V von Variablen ist die kleinste Menge,
die die folgenden Elemente gemaß (1) - (3) enthalt:
(1)
P ,
falls P ein Atom uber Σ und V ist
(2)
(
¬
F ), (F
1
∧
F
2
), (F
1
∨
F
2
), (F
1
⇒
F
2
), (F
1
⇔
F
2
)
(3)
(
∃
xF ), (
∀
xF )
wobei x
∈
V und F, F
1
,F
2
∈
Formel
Σ
(V)
sind. Ein
Literal
ist ein Atom A oder
ein negiertes Atom
A als
negatives
Lite-
ral bezeichnet wird. Ein
Ausdruck
uber Σ (und V ) ist ein Term oder eine Formel
uber Σ (und V ). Eine Formel ohne Variablen heißt
Grundatom
,
Grundliteral
bzw.
Grundformel
.
¬
A,wobeiA als
positives
Literal und
¬
Eine Formel gemaß Definition 3.50 heißt
wohlgeformt
(engl.
well-formed formula
).
Die Bindungsprioritaten, die wir zum Einsparen von Klammern bereits fur die
Aussagenlogik eingefuhrt hatten (Seite 43), erweitern wir so, dass die Junktoren
starker binden als die Quantoren und
∀
starker bindet als
∃
.
Selbsttestaufgabe 3.51 (Darstellung in PL1)
Stellen Sie die Pramissen und
Konklusionen der Schlussfolgerungen 1 - 7 aus Selbsttestaufgabe 3.1 (Seite 25) unter
Verwendung geeigneter Funktions- und Pradikatensymbole als PL1-Formeln dar.
Wird eine Formel mit Junktoren gebildet, die auch in der Aussagenlogik ver-
wendet werden, so ist ihr Wahrheitswert unter einer Variablenbelegung α definiert
durch die klassisch-logische, wahrheitsfunktionale Interpretation, wie sie in Defini-
tion 3.9 (Seite 34) angegeben ist.
Eine allquantifizierte Formel erhalt den Wahrheitswert
true
,wennfur die quan-
tifizierte Variable
jedes
Element des Universums eingesetzt werden kann und die
Formel dann jeweils
true
liefert. Fur eine existentiell quantifizierte Formel wird le-
diglich die Existenz mindestens
eines
“passenden” Elements aus dem Universum
verlangt.
Definition 3.52 (Wahrheitswert einer quantifizierten Formel unter
α
)
Gegeben sei eine quantifizierte Formel F
∈
Formel
Σ
(V)
, eine Σ-Interpretation I
und eine Variablenbelegung α : V
U
I
.Der
Wahrheitswert von
F
in
I
unter
α
(oder:
Wert von
F
in
I
unter
α), geschrieben [[F ]]
I,α
, ist definiert durch
→
