Seite 1 von 1

4 Fragen - Ich brauche dringend Hilfe

Verfasst: 30. Sep 2009 00:49
von dripper
E3.3b - Geben Sie eine FO-Formel an, die besagt, dass die Trägermenge genau n Elemente enthält.
In der Musterlösung steht, dass die Menge "Ex1......Exn /\ Xi != Xj" mindestens n Elemente enthält. Aber ich kann nicht verstehen, warum diese Menge mindestens und nicht genau n Elemente enthält?

H3.3 - Beweisen Sie "Ex(Px --> AyPy)" mit Resolution.
In der Musterlösung wird zuerst die Formel negiert und danach mit der Resulution bewiesen. Ich denke, dass die Formel negiert wird, weil sie in KNF sein muss, aber ist das schon nicht eine andere Formel - ich meine nur mit einer Negation und nicht mit doppelter Negation wie wir es im TGDI1 gemacht haben.

Tautologische Herbranddisjunktion - Wie wird das eigentlich gemacht? Es steht etwas darüber im Forum, aber ich habe es nicht verstanden.

Grundinstanzresolution - Wie ich verstanden habe falls wir eine Formel der Gestalt "(Rc \/ Rxy)" haben, können wir "Rc" mit nichts ersätzen, da "c" eine Konstante ist. Können wir aber "Rxy" belegen?

"Ex" steht für "existiert x" und "Ay" steht für "für alle y".


Danke im Voraus

Re: 4 Fragen - Ich brauche dringend Hilfe

Verfasst: 30. Sep 2009 01:08
von h4ck4
zu H3.3:
Um zu zeigen, dass \(\varphi\) allgemeingültig ist, leitet man mittels Resolution die leere Klausel von der Klauselmenge(\(\neg \varphi\)) ab! (siehe Musterlösung Aufgabe E2.1)

Re: 4 Fragen - Ich brauche dringend Hilfe

Verfasst: 30. Sep 2009 01:22
von memo_star
Eine Formel ist allgemeingültig wenn nicht diese Formel nicht erfüllbar ist !

das heißt du negierst deine Formel und beweist durch Res. dass diese Formel nicht erfüllbar ist genauso wie war das immer machen und wenn du die leere Klauseln am ende ableiten kannst , ist diese formal dann allgemeingültig!

Re: 4 Fragen - Ich brauche dringend Hilfe

Verfasst: 30. Sep 2009 09:56
von dripper
Ah ja das war so. Ich habe mich verwirrt. Danke :)
Eine Frage weniger.

Re: 4 Fragen - Ich brauche dringend Hilfe

Verfasst: 30. Sep 2009 11:49
von quanz
dripper hat geschrieben:Tautologische Herbranddisjunktion - Wie wird das eigentlich gemacht? Es steht etwas darüber im Forum, aber ich habe es nicht verstanden.
Das ist schon gut im Forum erklärt, anders kann ich es auch nicht.
Es geht darum zu zeigen, dass die Aussage war ist, egal bei welcher Belegung.
dripper hat geschrieben:Grundinstanzresolution - Wie ich verstanden habe falls wir eine Formel der Gestalt "(Rc \/ Rxy)" haben, können wir "Rc" mit nichts ersätzen, da "c" eine Konstante ist. Können wir aber "Rxy" belegen?
Rc bleibt, wie es ist. Bei Rxy sind x und y variabel. D.h. x und y können \(c, fc, ffc, \dots , f^nc : n \in \mathbb N\) annehmen.

Re: 4 Fragen - Ich brauche dringend Hilfe

Verfasst: 30. Sep 2009 12:32
von dripper
Tautologische Herbranddisjunktion - Kann mir jemand zeigen wir es bei der Aufgabe 3c von der Klausur gemacht wird?

Re: 4 Fragen - Ich brauche dringend Hilfe

Verfasst: 30. Sep 2009 13:15
von quanz
\(\varphi^H = \exists x (Px \rightarrow Pa \wedge Pb) = \exists x (\neg Px \vee (Pa \wedge Pb))\)
\(t_1 = a, t_2 = b\)

Disjunktion:
\((\neg Pa \vee (Pa \wedge Pb)) \vee ((\neg Pb \vee (Pa \wedge Pb)))\)
\(= \neg Pa \vee (Pa \wedge Pb) \vee \neg Pb \vee (Pa \wedge Pb)\)

Ist also immer wahr!

Re: 4 Fragen - Ich brauche dringend Hilfe

Verfasst: 30. Sep 2009 14:14
von empe
dripper hat geschrieben:E3.3b - Geben Sie eine FO-Formel an, die besagt, dass die Trägermenge genau n Elemente enthält.
In der Musterlösung steht, dass die Menge "Ex1......Exn /\ Xi != Xj" mindestens n Elemente enthält. Aber ich kann nicht verstehen, warum diese Menge mindestens und nicht genau n Elemente enthält?
Weil diese Formel auch erfüllbar ist, wenn in der Trägermenge mehr als n Elemente sind. Mach dir doch einfach mal ein Beispiel mit n=2 und dann versuchst du es mit Trägermengen {1}, {1, 2}, {1, 2, 3}
Dann sollte es schnell klar werden.

Re: 4 Fragen - Ich brauche dringend Hilfe

Verfasst: 30. Sep 2009 14:30
von dripper
quanz hat geschrieben:\(\varphi^H = \exists x (Px \rightarrow Pa \wedge Pb) = \exists x (\neg Px \vee (Pa \wedge Pb))\)
\(t_1 = a, t_2 = b\)

Disjunktion:
\((\neg Pa \vee (Pa \wedge Pb)) \vee ((\neg Pb \vee (Pa \wedge Pb)))\)
\(= \neg Pa \vee (Pa \wedge Pb) \vee \neg Pb \vee (Pa \wedge Pb)\)

Ist also immer wahr!
Was bedeutet "t1" und "t2"? und warum ist im ersten Teil "x" durch "a" und im zweiten Teil durch "b" ersätzt?
Warum unterscheiden sich die Lösungen für c und b? Ich meine, dass bei "b" wurden noch "f" und "g" überall hingefügt.


P.S. Ahhhh ich habe es verstanden. Also weil "x" abhängig von "Existiert x" ist wird es mit den anderen Funktionen oder Konstanten ersätzt.