View Full Version : [Frage] Frage zu Bsp. 5 vom letzten Test
patricasso
18-08-2002, 21:00
Eine Frage zum 5. Beispiel vom letzten Test (28.6):
Man soll folgende Konsequenzrelation überprüfen, ob sie gültig ist:
(A ^ B) Teilmenge von (C ^ D), ...
Dazu lautet es weiter: Verwenden Sie dazu das DPLL-Verfahren, d.h., schreiben Sie das Problem als Formel deren Gültigkeit nachzuweisen ist, wandeln Sie die negierte Formel in eine KNF um und wenden Sie DPLL darauf an. Geben Sie ein Gegenbeispiel
an, falls die Konsequenzrelation nicht gilt.
Bei mir ist als Lösung folgende Klauselmenge rausgekommen:
{A,C}, {B,D}, {A, nonB}, {C,D}, {A,nonA}, {D,nonD}
darauf das DPLL angewendet ergibt eine UNERFÜLLBARE Lösung. Hab keine Ahnung ob ich das richtig gerechnet habe.
Muss man als ERSTES die Ausgangsformel negieren und DANACH erst in eine KNF bringen? Wie rechnet man das richtig und wie finde ich eigentlich ein Gegenbeispiel?
Wäre für eine Lösung des Beispiels sehr dankbar
;)
*boost*
ich komm gleich mal auf andere Klauseln....und zwar indem ich die beiden Formeln vor der logischen Konsequenz in KNFs umwandle. Die Behauptung aber zuerst negiere und dann in KNF bringe.
/edit vertippt
{not A, not B, C} {not A, not B, D} {not A, B} {not C, not D} {A} {D, not A}
nach DPLL bleibt {} --> unerfüllbar --> damit stimmt die Formel
hoffe es stimmt, meine vorlage war ein bsp. mit einem Halbaddiere, das wir in der VO gemacht hatten.
Wie man aus DPLL ein Gegenbeispiel ableiten kann, würd mich auch interessieren.....
patricasso
19-10-2002, 17:17
Genau das war mir ja unklar! Wann man das ganze Zeugs nun negieren soll. Ich habs nämlich genau umgekehrt gemacht. Also zuerst in ein KNF gebracht und DANN erst negiert.
/Edit: ah ja, jetzt seh' ichs erst - stand eh in der Angabe!
Trotzdem kommt bei mir auch "unerfüllbar" raus.
War (fast) nie in der VO., daher kenn ich das Beispiel mit dem Halbaddierer nicht. Wäre es vielleicht möglich, dieses hier zu posten?
Danke für die Hilfe!
ich hab das Bsp gestern auch gerechnet mir kommt aber folgende Klauselmenge raus:
{not A, not B, C} {not A, not B, D} {not A, B} {not C, not D} {A,D} {not D, not A}
man braucht ja nur den Teil hinter dem |= negieren (siehe Seite 81).
raus kommt dass die Klauselmenge erfüllbar ist, also die Formel ungültig ist.
Gegenbsp: {not A, not B, not C, D}, {not A, B, not C, D}
eine besondere Technik um ein Gegenbsp zu finden kenn ich auch nicht, einfach überlegen und rumprobieren.
@qmp
stimmt!
hatte mich beim KNFen der Behauptung vertan.
ad Gegenbeispiel: scheint so als würde die Folge der verwendeten Literale des DPLL Verfahrens ein Gegenbsp. bilden; wobei darin nicht vorkommende Variablen "don't cares" sind.
könnte mal jemand beschreiben, wie man die ersten drei schritte (also umwandlung in eine formel, negieren, in KNF umwandeln) am effizientesten durchführt ?
wäre nett, wenn das jemand vorrechnen könnte !
mfg, -z0nk-
jo, das wäre super, ich steh da auch ziemlich an ...
yeah ... nach ca. 2h ins skriptum starren bin ich wieder einen kleinen schritt weitergekommen ... die kleinen erfolgserlebnisse machens eben aus :).
die nächste unklarheit ließ leider nicht lang auf sich warten :) :
wie reduziere ich die klauselmenge am besten, wenn sie keine einerklauseln enthält ? im skript steht etwas von "eine beliebige variable wählen und damit reduzieren".
--> hm ... naja ... soll ich jetzt einfach eine variable hernehmen und so tun als wäre sie eh da ? :) bitte um hilfe, bin mir da nicht ganz sicher ;)
mfg, -z0nk-
patricasso
20-10-2002, 01:43
Ich denk schon, dass man jede Einerklausel nehmen kann die man will. Jedenfalls habs ich so gemacht. Muss mir das aber selbst nochmal anschauen ...
ja, DPLL nimmt (sofern keine Einerklausel vorhanden ist) 1 beliebiges Literal aus allen Klauseln. hauptsache die elimination wird richtig durchgeführt....
bitte um Hilfe ....
1.)
wie kommt man von:
(A^B)impliziert(C^D)
a.) auf die KNF
b.) auf die Kausalformeln {nA,nB,C} und {nA,nB,D}
ich hab da irgendwo nen denkfehler drin, wäre für hilfe dankbar ...
2.)
reduktion mittels dpll ... lat qmp habe ich jetzt folgende Kausalformeln:
{nA,nB,C} {nA,nB,D} {nA,B} {nC,nD} {A,D} {nA,nD}
da ich keine Einerklausel habe, nehme ich _irgendein_ Literal also zb: {A}
=> es bleibt übrig:
{nB,C} {nB,D} {B} {nC,nD} {nD}
Red mit {B}
=> es bleibt übrig:
{C} {D} {nC,nD} {nD}
Red mit {D}
=> es bleibt übrig:
{C} {nC}
Red mit {C}
=> es bleibt übrig:
{} => unerfüllbar .... aber ihr sagt doch es ist erfüllbar ????
mache ich einen Fehler ?
btw: wenn ich am Anfang als Reduktionsliteral {nA} nehme ist es tatsächlich erfüllbar ... also ist es wirklich EGAL welches ich nehme (glaub ich irgendwie net)
thx
Original geschrieben von Phlow
bitte um Hilfe ....
1.)
wie kommt man von:
(A^B)impliziert(C^D)
a.) auf die KNF
b.) auf die Kausalformeln {nA,nB,C} und {nA,nB,D}
ich hab da irgendwo nen denkfehler drin, wäre für hilfe dankbar ...
(A ^ B) => (C ^ D) =
= (notA v notB) v (C ^ D) = ..... (Distributivgesetz)
= (not A v notB v C) ^ (notA v notB v D)
... und diesen term kann man unverändert in die KNF übernehmen (warum, steht auf S.81 unter punkt 1: "transformiere notF in eine Klauselmenge")
Die Klauselmenge ist ja sozusagen nur eine andere (abgekürzte) Schreibweise für die KNF.
mfg, -z0nk-
:idea:
ok danke ... mir geht ein licht auf ;)
aber das ob es nun erfülbar ist oder nicht (siehe 2te frage meines postings oben) ist mir noch immer nicht klar ....
mit kommt nach dem reduziervorgang folgende klauselmenge heraus:
K = { {}, {} }
bedeutet das jetzt, dass sich die beiden leeren mengen selber nochmal gegenseitig reduzieren und am schluss K = {} herauskommt ?
mfg, -z0nk-
Original geschrieben von Phlow
btw: wenn ich am Anfang als Reduktionsliteral {nA} nehme ist es tatsächlich erfüllbar ... also ist es wirklich EGAL welches ich nehme (glaub ich irgendwie net)
Skript S. 87, 4. Punkt
...beliebige in K vorkommende Variable A gewählt. Diese kann entweder wahr oder falsch sein, was dem Hinzufügen der Klausel {A} oder {nA} entspricht....allerdings lediglich Hypthesen....Gelingt es unter dieser Annahme zu zeigen, dass die reduzierte Klauselmenge erfüllbar ist, ist auch K erfüllbar. Sonst muss auch die zweite Hypthese geprüft werden....
...und diese Verzweigung hast du am Anfang mit A und nA.
hoppla, lesen sollte man halt können :hewa:
danke Stiller ....
vBulletin® v3.7.1, Copyright ©2000-2008, Jelsoft Enterprises Ltd.