KNF und Klauselform < Prädikatenlogik < Logik < Logik+Mengenlehre < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) überfällig  | | Datum: | 16:07 So 08.02.2009 | | Autor: | RalU |
| Aufgabe | Hallo!
Es geht um folgende Aufgabenstellung:
Bringen Sie folgende Formeln auf konjunktive und Klauselnormalform
1)
[mm] \neg \exists [/mm] y [mm] \forall [/mm] z [mm] \forall [/mm] x N(y,z) [mm] \Rightarrow [/mm] L(y,f(z,x))
2)
[mm] \exists [/mm] x [mm] \forall [/mm] y [mm] ((\exists [/mm] x Q(x)) [mm] \Rightarrow \exists [/mm] y P(x,y)) [mm] \wedge [/mm] LT(x,y)
3)
[mm] \forall [/mm] x [mm] \forall [/mm] y [mm] \forall [/mm] z R(x,y,z) [mm] \Rightarrow((\exists [/mm] x Q(x,z)) [mm] \gdw (\exists [/mm] y P(z,y))) |
zu 1)
[mm] \gdw \neg \exists [/mm] y [mm] \forall [/mm] z [mm] \forall [/mm] x [mm] \neg [/mm] N(y,z) [mm] \vee [/mm] L(y,f(z,x))
[mm] \gdw \forall [/mm] y [mm] \exists [/mm] z [mm] \exists [/mm] x [mm] \neg \neg [/mm] N(y,z) [mm] \vee [/mm] L(y,f(z,x))
[mm] \gdw \forall [/mm] y [mm] \exists [/mm] z [mm] \exists [/mm] x N(y,z) [mm] \wedge \neg [/mm] L(y,f(z,x))
[mm] \gdw \forall [/mm] g(y) h(y) N(y,g(y)) [mm] \wege \neg [/mm] L(y,f(g(y), h(y)))
(Quantoren fallen nun weg)
Klauselform: { { N(y,g(y)) },{ [mm] \wege [/mm] L(y,f(g(y),h(y))) } }
zu 2)
[mm] \gdw \exists [/mm] x [mm] \forall [/mm] y [mm] (\neg(\exists [/mm] x Q(x)) [mm] \vee \exists [/mm] y P(x,y)) [mm] \wedge [/mm] LT(x,y)
[mm] \gdw \exists [/mm] x [mm] \forall [/mm] y [mm] ((\forall [/mm] x [mm] \neg [/mm] Q(x)) [mm] \vee \exists [/mm] y P(x,y)) [mm] \wedge [/mm] LT(x,y)
| [mm] Subst.:\forall [/mm] x = z , [mm] \exists [/mm] y = v
[mm] \gdw \exists [/mm] x [mm] \forall [/mm] y [mm] (\forall [/mm] z [mm] \neg [/mm] Q(z) [mm] \vee \exists [/mm] v P(x,v)) [mm] \wedge [/mm] LT(x,y)
| [mm] Subst.:\exists [/mm] v=f(y,z), [mm] \exists [/mm] x=c
[mm] \gdw \exists [/mm] c [mm] \forall [/mm] y [mm] \forall [/mm] z [mm] \neg [/mm] Q(z) [mm] \vee [/mm] P(c,f(y,z)) [mm] \wedge [/mm] LT(x,y)
(Quantoren fallen nun weg)
Klauselform:
{ { [mm] \neg [/mm] Q(z),P(c,f(y,z)) },{ LT(c,y) }}
zu 3)
[mm] \gdw \forall [/mm] x [mm] \forall [/mm] y [mm] \forall [/mm] z R(x,y,z) [mm] \Rightarrow((\exists [/mm] x Q(x,z)) [mm] \Rightarrow (\exists [/mm] y P(z,y)) [mm] \wedge (\exists [/mm] y P(z,y)) [mm] \Rightarrow (\exists [/mm] x Q(x,z)))
[mm] \gdw \forall [/mm] x [mm] \forall [/mm] y [mm] \forall [/mm] z [mm] \neg [/mm] R(x,y,z) [mm] \vee (\neg (\exists [/mm] x Q(x,z)) [mm] \vee(\exists [/mm] y P(z,y)) [mm] \wedge \neg(\exists [/mm] y P(z,y)) [mm] \vee (\exists [/mm] x Q(x,z)))
Jetz weiß ich nicht, wie man die Quantoren am besten nach vorne ziehen kann, bzw. wie es an der Stelle weitergeht...
Sind die anderen Lösungen korrekt?
Gruß, Ralf
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 16:20 Di 10.02.2009 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
