Logik:Klausuren/28.02.2003/2.7 Aufgabe
Inhaltsverzeichnis
1. Aufgabenstellung[Bearbeiten]
Gegeben sei die Menge prädikatenlogischer Formeln $ \mathfrak{F}={F_1,...,F_4} $ in der Sprache $ \mathcal{L} = ({p\,/1, q\,/1, r\,/1, s\,/1}, \O, {a, b}) $ mit
$ F_1 = (\forall X)(p(X) \rightarrow q(X)) $
$ F_2 = (\forall X)(r(X) \rightarrow (q(X) \vee s(X))) $
$ F_3 = (\forall X)((q(X) \wedge \neg s(X)) \vee (s(X) \wedge \neg q(X))) $
$ F_4 = (p(a) \wedge (r(b) \wedge \neg p(b))). $
a) Geben Sie sämtliche Herbrandmodelle für die gegebene Formelmenge an.
b) Welche Herbrandmodelle hat $ \mathfrak{F} \cup \left\{ \neg r(a), \neg p(b), \neg q(b), \neg s(a), \neg s(b)\right\}? $
c) Gilt $ \mathfrak{F} \models (\exists X)s(X) ? $ Beweisen Sie Ihere Antwort.
d)Seien $ \mathfrak{F} $ und $ \mathfrak{H} $ zwei Mengen prädikatenlogischer Formeln. Bezeichne n die Anzahl
der Herbrandmodelle der Formelmenge $ \mathfrak{F} $ und $ m\ $ die Anzahl der Herbrandmodelle
der Formelmenge $ \mathfrak{F}\cup \mathfrak{H} $. Welche der folgenden Beziehungen gilt?
(1) $ n\leq m $
(2) $ n\geq m $
(3) Weder (1) noch (2) trifft im Allgemeinen zu.
Beweisen Sie Ihre Antwort.
