Database Reference
In-Depth Information
Im Folgenden wollen wir etwas naher auf die einzelnen Aquivalenzen in Theo-
rem 3.58 eingehen und auf ihre jeweilige Bedeutung hinweisen.
Die unter (1) aufgefuhrten Aquivalenzen stellen die Quantoren in Beziehung
zueinander. Ein negierter, allquantifizierter Satz wie “Nicht alle Studenten haben
eine Matrikelnummer” ist aquivalent zu dem existentiell quantifizierten Satz “Es
gibt einen Studenten, der keine Matrikelnummer hat”. Tatsachlich kame man daher
mit nur einem der beiden Quantoren aus, da man jeden der beiden immer durch
den anderen ausdrucken kann. Die folgenden Aquivalenzen folgen unmittelbar aus
den in Theorem 3.58 angegebenen:
∀
xF
≡¬∃
x
¬
F
∃
xF
≡¬∀
x
¬
F
Insbesondere gestatten es diese Aquivalenzen, eine Negation vor einem Quantor
in die quantifizierte Aussage “hineinzuziehen”, so dass das Negationszeichen nur
unmittelbar vor den Atomen steht.
Selbsttestaufgabe 3.59 (Umformung)
Wandeln Sie die folgende Formel F se-
mantisch aquivalent so um, dass das Negationszeichen
¬
nur unmittelbar vor Ato-
men steht:
F =
def
¬
(P (x)
⇒¬∀
yQ(y))
∨
R(z)
Die Aquivalenzen unter (2.) in Theorem 3.58 erlauben es, einen Quantor in einer
Teilformel, die Teil einer Konjunktion oder einer Disjunktion ist, “nach außen” zu
ziehen, falls die quantifizierte Variable in dem anderen Teil nicht auftritt.
Die Aquivalenzen unter (3.) sollten Sie besonders beachten. Die Aquivalenz
(3.1) druckt aus, dass der Allquantor mit der Konjunktion “vertraglich ist”. Intui-
tiv kann man sich das dadurch klarmachen, dass man eine Formel ∀xP als eine
Abkurzung fur eine (im Allgemeinen unendliche) Formel der Art
P [x/c
1
]
∧
P [x/c
2
]
∧
P [x/c
3
]
∧
...
ansieht, wobei c
1
,c
2
,c
3
, ... genau alle Objekte des Universums bezeichnen. Dual
dazu kann man eine Formel ∃xP als Abkurzung fur eine Formel der Art
P [x/c
1
]
∨
P [x/c
2
]
∨
P [x/c
3
]
∨
...
ansehen, woraus deutlich wird, dass der Existenzquantor wie in der Aquivalenz (3.2)
mit der Disjunktion vertraglich ist. Ebenso wichtig wie die beiden gerade genannten
Aquivalenzen sind die folgenden Nichtaquivalenzen:
(
∀
xF)
∨
(
∀
xG)
≡∀
x(F
∨
G)
(
∃
xF)
∧
(
∃
xG)
≡∃
x(F
∧
G)
Selbsttestaufgabe 3.60 (Quantorenunvertraglichkeit)
Konstruieren Sie aus-
gehend von den oben gemachten Analogien Interpretationen, die aufzeigen, dass
der Allquantor nicht mit der Disjunktion und der Existenzquantor nicht mit der
Konjunktion vertraglich ist.
