Erfüllbarkeit < Prädikatenlogik < Logik < Logik+Mengenlehre < Hochschule < Mathe < Vorhilfe
|
| Aufgabe | Sind die folgenden prädikatenlogischen Formeln erfüllbar? Wenn ja, geben Sie eine erfüllende Interpretation I an. Ansonsten begründen Sie, warum die Formel nicht erfüllbar ist.
(a) [mm] \alpha [/mm] = $ [mm] \forall [/mm] x [mm] \forall [/mm] y [mm] \forall [/mm] z (P(x,y) [mm] \wedge [/mm] P(y,z) [mm] \Rightarrow [/mm] P(x,z)) [mm] \wedge \forall [/mm] x [mm] \exists [/mm] y [mm] \neg [/mm] P(x,y) [mm] \wedge \forall [/mm] x [mm] \neg [/mm] P(x,x) [mm] \wedge \exists [/mm] x [mm] \exists [/mm] y P(x,y) $
(b) [mm] \beta [/mm] = [mm] $\forall [/mm] x [mm] \neg [/mm] P(x,x) [mm] \wedge \forall [/mm] x [mm] \exists [/mm] y P(x,y) [mm] \wedge \forall [/mm] x [mm] \forall [/mm] y [mm] \forall [/mm] z (P(x,y) [mm] \wedge [/mm] P(y,z) [mm] \Rightarrow [/mm] P(x,z)) [mm] \wedge \forall [/mm] x [mm] \forall [/mm] y (P(x,y) [mm] \Rightarrow \neg [/mm] P(y,x))$
(c) [mm] \gamma [/mm] = [mm] $ \forall x \forall y \forall z (P(x,y) \wedge P(y,z) \Rightarrow P(x,z)) \wedge \forall x \exists y (\neg P(x,y) \vee P(y,x)) \wedge \forall x \neg P(x,x) \wedge \exists x \forall y P(x,y) $ [/mm]
(d) [mm] \delta [/mm] = [mm] $\forall [/mm] x P(x,x) [mm] \wedge \forall [/mm] x [mm] \exists [/mm] y P(x,y) [mm] \wedge \forall [/mm] x [mm] \forall [/mm] y [mm] \forall [/mm] z (P(x,y) [mm] \wedge [/mm] P(y,z) [mm] \Rightarrow [/mm] P(x,z)) [mm] \wedge \forall [/mm] x [mm] \forall [/mm] y [mm] (\neg [/mm] P(x,y) [mm] \Rightarrow [/mm] P(y,x))$ |
Hallo,
wie löst man diese Aufgaben? Uns wurde gesagt, dass man erst schauen muss, was transitiv usw. ist, aber ich habe leider schon dabei Schwierigkeiten. Erst anschließend kann man diese Aufgaben lösen?
Ich wäre sehr froh, wenn mir jemand dabei helfen könnte.
Ich habe diese Frage in keinem anderen Forum gestellt.
Vielen Dank im Voraus,
mastermoney
|
|
| |
|
> Sind die folgenden prädikatenlogischen Formeln erfüllbar?
> Wenn ja, geben Sie eine erfüllende Interpretation I an.
> Ansonsten begründen Sie, warum die Formel nicht erfüllbar
> ist.
>
> (a) [mm]\alpha[/mm] = [mm]\forall x \forall y \forall z (P(x,y) \wedge P(y,z) \Rightarrow P(x,z)) \wedge \forall x \exists y \neg P(x,y) \wedge \forall x \neg P(x,x) \wedge \exists x \exists y P(x,y)[/mm]
>
> (b) [mm]\beta[/mm] = [mm]\forall x \neg P(x,x) \wedge \forall x \exists y P(x,y) \wedge \forall x \forall y \forall z (P(x,y) \wedge P(y,z) \Rightarrow P(x,z)) \wedge \forall x \forall y (P(x,y) \Rightarrow \neg P(y,x))[/mm]
>
> (c) [mm]\gamma[/mm] = [mm]$ \forall x \forall y \forall z (P(x,y) \wedge P(y,z) \Rightarrow P(x,z)) \wedge \forall x \exists y (\neg P(x,y) \vee P(y,x)) \wedge \forall x \neg P(x,x) \wedge \exists x \forall y P(x,y) $[/mm]
>
> (d) [mm]\delta[/mm] = [mm]\forall x P(x,x) \wedge \forall x \exists y P(x,y) \wedge \forall x \forall y \forall z (P(x,y) \wedge P(y,z) \Rightarrow P(x,z)) \wedge \forall x \forall y (\neg P(x,y) \Rightarrow P(y,x))[/mm]
>
> Hallo,
>
> wie löst man diese Aufgaben? Uns wurde gesagt, dass man
> erst schauen muss, was transitiv usw. ist, aber ich habe
> leider schon dabei Schwierigkeiten. Erst anschließend kann
> man diese Aufgaben lösen?
Hallo mastermoney,
es geht hier jeweils um eine Relation P (wohl in der Art
einer Ordnungsrelation), aber mit jeweils unterschied-
lichen Forderungen. Um die Zeilen richtig zu verstehen,
muss man sehr pingelig auf die Beklammerung achten.
Zu einer solchen Relation muss man sich eine Grund-
menge M denken, aus welcher die Elemente x,y,z,....
stammen.
Formel [mm] \alpha [/mm] , in Worte übersetzt:
1.) P ist transitiv,
2.) zu jedem Element x von M gibt es
(mindestens) ein [mm] y\in [/mm] M so dass für das
Paar (x,y) die Relation P nicht gilt,
3.) kein Element steht zu sich selber in
der Relation P, und
4.) P ist nicht leer, d.h. es gibt mindestens ein
Paar (x,y) mit P(x,y).
Nun kann man versuchen, eine Interpretation
zu "basteln", also eine Menge M und eine darauf
definierte Relation P mit den besagten Eigen-
schaften zu "erfinden".
Man kann z.B. versuchen, eine Menge M mit
möglichst wenigen Elementen zu nehmen.
Im Beispiel [mm] \alpha [/mm] darf M jedoch sicher nicht leer
sein; nur ein Element geht auch nicht, dass es
auch mit zwei oder drei Elementen nicht funk-
tioniert, kann man sich ebenfalls klar machen
(ich hoffe, mich dabei nicht geirrt zu haben ...)
Ist es am Ende gar unmöglich, so eine Inter-
pretation I=(M,P) zu finden ?
Ich denke nicht, denn ich habe eine ziemlich
einfache Interpretation mit weniger als zehn
Elementen gefunden.
LG Al-Chwarizmi
|
|
|
|
