4 Fragen - Ich brauche dringend Hilfe

dripper
Windoof-User
Windoof-User
Beiträge: 40
Registriert: 25. Mär 2009 14:01

4 Fragen - Ich brauche dringend Hilfe

Beitrag 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

h4ck4
Mausschubser
Mausschubser
Beiträge: 91
Registriert: 18. Mai 2009 20:50
Kontaktdaten:

Re: 4 Fragen - Ich brauche dringend Hilfe

Beitrag 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)

memo_star
Mausschubser
Mausschubser
Beiträge: 58
Registriert: 11. Nov 2006 16:06
Wohnort: Darmstadt

Re: 4 Fragen - Ich brauche dringend Hilfe

Beitrag 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!

dripper
Windoof-User
Windoof-User
Beiträge: 40
Registriert: 25. Mär 2009 14:01

Re: 4 Fragen - Ich brauche dringend Hilfe

Beitrag von dripper »

Ah ja das war so. Ich habe mich verwirrt. Danke :)
Eine Frage weniger.

quanz
BASIC-Programmierer
BASIC-Programmierer
Beiträge: 103
Registriert: 1. Okt 2007 19:32

Re: 4 Fragen - Ich brauche dringend Hilfe

Beitrag 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.

dripper
Windoof-User
Windoof-User
Beiträge: 40
Registriert: 25. Mär 2009 14:01

Re: 4 Fragen - Ich brauche dringend Hilfe

Beitrag von dripper »

Tautologische Herbranddisjunktion - Kann mir jemand zeigen wir es bei der Aufgabe 3c von der Klausur gemacht wird?

quanz
BASIC-Programmierer
BASIC-Programmierer
Beiträge: 103
Registriert: 1. Okt 2007 19:32

Re: 4 Fragen - Ich brauche dringend Hilfe

Beitrag 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!

empe
BASIC-Programmierer
BASIC-Programmierer
Beiträge: 118
Registriert: 14. Jan 2008 14:24

Re: 4 Fragen - Ich brauche dringend Hilfe

Beitrag 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.

dripper
Windoof-User
Windoof-User
Beiträge: 40
Registriert: 25. Mär 2009 14:01

Re: 4 Fragen - Ich brauche dringend Hilfe

Beitrag 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.

Antworten

Zurück zu „Archiv“