Database Reference
In-Depth Information
2. Gegeben seien die Signatur und die drei Interpretationen aus Beispiel 3.41.
Welchen Wahrheitswert haben in den drei Interpretationen I
1
, I
2
und I
3
jeweils
die folgenden Formeln:
(a)
Großvater
(
Max
,
Moritz
)
(b)
∀
x
∃
y
Großvater
(x, y)
(c)
∃
y
∀
x
Großvater
(x, y)
Beachten Sie, dass mit der Festlegung der Wahrheitswertefunktion der allgemei-
ne Rahmen der klassisch-logischen Systeme, wie wir ihn in Abschnitt 3.3 vorgestellt
haben, genutzt werden kann. Das bedeutet u.a., dass die Begriffe wie Erfullungsre-
lation, Modell, allgemeingultig, inkonsistent, logische Folgerung etc. damit auch fur
PL1 zur Verfugung stehen.
Aquivalenzen
3.5.4
Analog zur Aussagenlogik konnen wir auch in PL1-Formeln Teilformeln durch ande-
re, semantisch aquivalente ersetzen, ohne dass sich der logische Status der Formeln
andert. Jetzt mussen wir fordern, dass die ersetzte und die ersetzende Teilformel
nicht nur in allen Interpretationen, sondern auch unter allen Belegungen den je-
weils gleichen Wahrheitswert liefern. Das Ersetzbarkeitstheorem der Aussagenlogik
(Theorem 3.34) gilt damit in analoger Weise auch fur die Pradikatenlogik.
Zusatzlich zu den in Theorem 3.35 (Seite 46) aufgefuhrten Aquivalenzen, die
auch fur die Pradikatenlogik 1. Stufe gelten, gelten die folgenden Aquivalenzen, die
sich auf das Auftreten von Quantoren beziehen:
Theorem 3.58 ( Aquivalenzen fur PL1-Formeln)
Es gelten:
1.1
1.2
¬∀
xF
≡∃
x
¬
F
¬∃
xF
≡∀
x
¬
F
⎫
⎬
2.1
2.2
2.3
2.4
(
∀
xF)
∧
G
≡∀
x(F
∧
G)
falls x nicht
frei in G
vorkommt
(
∀
xF)
∨
G
≡∀
x(F
∨
G)
(
∃
xF)
∧
G
≡∃
x(F
∧
G)
⎭
(
∃
xF)
∨
G
≡∃
x(F
∨
G)
3.1
3.2
(
∀
xF)
∧
(
∀
xG)
≡∀
x(F
∧
G)
(
∃
xF)
∨
(
∃
xG)
≡∃
x(F
∨
G)
4.1
4.2
∀
x
∀
yF
≡∀
y
∀
xF
∃
x
∃
yF
≡∃
y
∃
xF
falls y nicht
in F vorkommt
5.1
5.2
∀
xF
≡∀
yF [x/y]
(gebundenes
Umbenennen)
∃
xF
≡∃
yF [x/y]
Die verwendete Notation
F [x/y]
bezeichnet die Formel, die aus
F
entsteht, wenn
man alle freien Vorkommen von
x
in
F
durch
y
ersetzt.
