8.5

[jamironico]

Hier ist mal meine antwort...

K={{A,B}, {¬A,B,C}, {A,C}, {A,B,¬C}, {¬A,¬B,C}, {A,¬B,¬C}, {¬A,B,¬C}, {¬A,¬B,¬C}}

Da es keine einerklauseln gibt kann mann einfach eine Variable aussuchen. Ich waehle A

Reduce(K,A) liefert...

K={{B,C}, {¬B,C}, {B,¬C}, {¬B,¬C}}

Wieder gibt es keine einerklauseln also waehle ich diesmal B

Reduce(K, B) liefert...

K={{C}, {¬C}}

Jetzt enthaelt K zwei einerklauseln, also kann ich entweder C oder ¬C waehlen, ich waehle halt C

Reduce(K, C) liefert...

K= {{}}

Da K eine Lehre menge enthaelt ist es unerfuellbar.

ich hoffe dass ich das richtig verstanden habe. bitte um ueberpruefung..

[Mr.Anderson]

Ja nach deiner Vorgehensweise hab ichs genauso!
Nur was ich nicht genau verstehe ist die Zeile: "if L ? K then K':=K' U {}"
in der function Reduce. Also wenn L enthalten ist in K, dann wird doch die Leermenge {} statt K eingefügt oder?
Wäre die Klauselmenge nicht dann schon unerfüllbar weil {} ? K?? (2. Zeile in function DPLL)

[Plantschkuh!]

Nur was ich nicht genau verstehe ist die Zeile: "if L ? K then K':=K' U {}"
in der function Reduce.
Diese Zeile sagt: Wenn das Literal L in der Klauselmenge K vorkommt, dann vereinige die Klauselmenge K' mit der leeren Menge. Das heißt nicht, daß die leere Menge in K' eingefügt wird, sondern alle Elemente der leeren Menge werden in K' übernommen. Damit bleibt K' natürlich gleich.
Die Vereinigung mit der leeren Menge hat also keinen Effekt und steht nur aus zwei Gründen da: Erstens ist nach dem if syntaktisch irgendein Befehl nötig, wenn auch ein sinnloser; und zweitens soll das wohl verdeutlichen, daß in diesem Fall die von {L} subsumierte Klausel K nicht mehr interessant ist und ganz unter den Tisch fallen kann.

[5piritus]

wörscht blabla

[Murmel]

Da K eine Lehre menge enthaelt ist es unerfuellbar.

Ich bin mir nicht sicher, aber im Beispiel im Skriptum auf S. 96 steht
"Aus der Tatsache, dass dieser Berechnungsast zu einer unerfüllbaren Klauselmenge führt, können wir noch nicht die Unerfüllbarkeit von K schliessen. Wir müssen noch den Berechnungsast, der mit !A beginnt, untersuchen."Ist das hier nicht auch der Fall, dass wir auch nochmal das Ganze mit Reduce(K, !A) machen müssen?

edit: In diesem Fall kommt durch Reduce(K,!A), Reduce(K',B) und Reduce(K'',!C) nämlich die leere Menge raus -> doch erfüllbar mit I(A)=f , I(B)=t und I(C)=f

lG,
Murmel

[Veronika]

Ich bin mir nicht sicher, aber im Beispiel im Skriptum auf S. 96 steht
Ist das hier nicht auch der Fall, dass wir auch nochmal das Ganze mit Reduce(K, !A) machen müssen?

edit: In diesem Fall kommt durch Reduce(K,!A), Reduce(K',B) und Reduce(K'',!C) nämlich die leere Menge raus -> doch erfüllbar mit I(A)=f , I(B)=t und I(C)=f

lG,
Murmel
Also ich bekomme bei der Reduktion mit !A heraus:

Reduce (K,!A)
K'={{B},{C},{B,!C},{!B,!C}}
Reduce (K',B)
K'' = {{C},{!C}}
Reduce (K'',C)
K'''={{}}
Also wieder unerfüllbar. Wie kommst du auf die leere Menge?

[g3nfox]

jo, komm auch auf das wie veronika

[jamironico]

ich habs jetzt auch so wie veronika...

[Murmel]

Ihr habt Recht, ich hab beim 2ten Mal die Angabe falsch abgeschrieben. Also doch unerfüllbar.

lG,
Murmel

[Erendis]

wenn ich mit !A reduziere, wie komme ich dann auf:
K'= {B},{C},{B,!C},{!B,!C},
werden dann alle Klauseln, die ein !A enthalten einfach weggelassen?

[Murmel]

werden dann alle Klauseln, die ein !A enthalten einfach weggelassen?Genau, und alle, die das Gegenteil, also A enthalten, bleiben stehen, nur ohne A

lG,
Murmel

[kambo]

Irgendwie verstehe ich das noch immer nicht.
Warum muss man noch die Reduktion mit !A durchführen??


edit: In diesem Fall kommt durch Reduce(K,!A) , Reduce(K',B) und Reduce(K'',!C) nämlich die leere Menge raus -> doch erfüllbar mit I(A)=f , I(B)=t und I(C)=f
Also ich bekomme bei der Reduktion mit !A heraus:
Reduce (K,!A)
K'={{B},{C},{B,!C},{!B,!C}}
Reduce (K',B)
K'' = {{C},{!C}}
Reduce (K'',C)
K'''={{}}
Also wieder unerfüllbar. Wie kommst du auf die leere Menge?Ihr beide seid auf die leere Menge gekommen! Warum sind eure Ergebnisse unterschiedlich (erfüllbar und nicht erfüllbar). Bedeutet die leere Menge immer, dass die Formel "unerfüllbar" ist ??

Könnte wer kurz erklären?

[Murmel]

DIe Reduktion mit !A muss man auch machen, weil ja eine Lösung mit I(A)=f existieren könnte.

Zur anderen Frage:
Wenn K selbst die leere Menge ist (K={}), ist das ganze erfüllbar, wenn es jedoch die leere Menge enthält K={{}}, ist es unerfüllbar.

Dadurch, dass du am Schluss hier K={{C}{!C}} hast, wird daraus, wenn du es ableitest (egal ob mit C oder !C), K={{}} (unerfüllbar)
Wäre es zB nur K={{C}}, könntest du es durch eine Ableitung mit C auf K={} bringen (da die Menge dadurch ja ganz gestrichen wird) und es wäre erfüllbar.

lG,
Murmel

[kambo]

@Murmel

Supa Erklärung!! Alles klar! http://hades.gothic.at/iforum/images/smilies/thumb.gif

Danke

[Erendis]

ist es denn nicht in beiden Fällen, also Reduce (K,!A) und Reduce (K,A), unerfüllbar?

[Murmel]

jo, isses, deshalb ist das Ganze unerfüllbar, wenns nur bei einem davon erfüllbar wär, wäre das Ganze erfüllbar.

lG,
Murmel

[nautiLus]

Hallo, also entweder ich bin schon zu müde oder was weiß ich...

Kann mir wer erklären, wie es möglich ist mit der Klauselmenge
K={{A,B}, {¬A,B,C}, {A,C}, {A,B,¬C}, {¬A,¬B,C}, {A,¬B,¬C}, {¬A,B,¬C}, {¬A,¬B,¬C}}

und Reduce(K,A)
auf K'={{B,C}, {¬B,C}, {B,¬C}, {¬B,¬C}}
zu kommen?

In der Reduce Funktion gibt es ja jetzt 3 Fälle (2 davon):

1) enthält K (das sind jetzt meine einzelnen Klauseln in der gesamten Klauselmenge) das Literal L (also mein A), dann subsumiert {L} die Klausel K, letztere kann ersatzlos gestrichen werden (was immer auch das unterstrichene heißen mag) ...

Also die Klausl die ich mir jetzt mal anschaue ist {A,B}.
1) trifft zu oder? Das L mit dem ich Reduce aufgerufen habe (hier mein A), ist in der Klausel {A,B} => ich muss subsumieren. Subsumier ich das mit A kommt {B} heraus oder?

2) Wenn ich ein Komplement von L in einer Klausel der Klauselmenge habe, was in {!A,B,C} zutrifft weiß ich nicht genau was da zu machen ist.

Wie muss ich das bei den ersten 2 Schritten machen?

Ciao

[docsoft]

Hallo, also entweder ich bin schon zu müde oder was weiß ich...

Kann mir wer erklären, wie es möglich ist mit der Klauselmenge
K={{A,B}, {¬A,B,C}, {A,C}, {A,B,¬C}, {¬A,¬B,C}, {A,¬B,¬C}, {¬A,B,¬C}, {¬A,¬B,¬C}}

und Reduce(K,A)
auf K'={{B,C}, {¬B,C}, {B,¬C}, {¬B,¬C}}
zu kommen?

In der Reduce Funktion gibt es ja jetzt 3 Fälle (2 davon):

1) enthält K (das sind jetzt meine einzelnen Klauseln in der gesamten Klauselmenge) das Literal L (also mein A), dann subsumiert {L} die Klausel K, letztere kann ersatzlos gestrichen werden (was immer auch das unterstrichene heißen mag) ...

Also die Klausl die ich mir jetzt mal anschaue ist {A,B}.
1) trifft zu oder? Das L mit dem ich Reduce aufgerufen habe (hier mein A), ist in der Klausel {A,B} => ich muss subsumieren. Subsumier ich das mit A kommt {B} heraus oder?

2) Wenn ich ein Komplement von L in einer Klausel der Klauselmenge habe, was in {!A,B,C} zutrifft weiß ich nicht genau was da zu machen ist.

Wie muss ich das bei den ersten 2 Schritten machen?

Ciao
Du hast Recht!
Es ist schon zu spät, geh lieber schlafen. :D

1.
Ein super Beispiel findest du auf der Seite 95(Skriptum->new)!

2.
Wieso machst du's dir zu kompliziert? Es ist ja ganz einfach, Mensch!
Bsp.1:
Reduktion mit A: {!A,B,C} -> {B,C}
Reduktion mit !A: {!A,B,C} -> {}

Bsp.2(aus dem Skriptum):
{{!R},{R}}
Reduktion mit {R}:
Ergebnis:
{{}}

finito!

Ciao

[nautiLus]

Man, sag das doch gleich :thumb: :engel:

Is ja eh einfach :D

[owaye]

:D :thumb: nicht schlecht nautilus *g* :shinner:

aber das problem ist, wenn man im skript allein nachschaut, sieht alles ur-kompliziert aus, obwohl das meiste wirklich einfach ist. nur bringt das einem keiner gscheit bei :( ...sux

[nautiLus]

Ja du hast wirklich recht. So wie das im Skriptum beschrieben ist, ist das echt der Witz.... Sowas einfaches so "dreckig" zu erklären suxx :D:D

n8 ich geh pennen :)

[derGloeckner]

Ja du hast wirklich recht. So wie das im Skriptum beschrieben ist, ist das echt der Witz.... Sowas einfaches so "dreckig" zu erklären suxx :D:D

n8 ich geh pennen :)
Also ich denke das Verfahren war anhand Beispiel 3.61 im Skriptum gut erklärt (was man halt für 8.5 braucht).
Was kann man da nicht verstehen, wenn man sich es ein oder zwei mal durchliest ?

[mmp]

Eines versteh ich aber noch nicht.
Angenommen ich bin jetzt in der unterste Stufe, nachdem ich A dann B und dann C gewählt habe.
So jetzt hat sich ja die DPLL Funktion 3 mal selber aufgerufen.

DPLL
1.DPLL nachdem A reduziert wurde
2.DPLL nachdem B reduziert wurde
3.DPLL nachdem C reduziert wurde

Wenn ich mir den Code auf Seite 93 anschaue, stehen aber jeweils bei jedem Aufruf noch die if Abfrage offen, richtig?
Das heißt aber der 3.DPLL aufruf liefert uns dann unerfüllbar und deshalb versucht der 2.DPLL das ganze mit dem negierten A (Variable A) also in unserem Fall mit !C.
Also wird ein vierter Aufruf getätigt.
4. DPLL nachdem !C reduziert wurde.

Das liefert dem 2.DPLL unerfüllbar und jetzt probierts dieser mit !B......... und so weiter.

Hab ich hier den Algorithmusa falsch verstanden?? Denn im Buch beim Bsp 3.61 werden diese !A (A Variable) nicht ausgeführt.

[nautiLus]

Also ich denke das Verfahren war anhand Beispiel 3.61 im Skriptum gut erklärt (was man halt für 8.5 braucht).
Was kann man da nicht verstehen, wenn man sich es ein oder zwei mal durchliest ?
Ja du hast schon recht, dass es einfach ist. Nachdem ich auf das BSP aufmerksam gemacht wurde, wars eh kein Problem mehr. Mein Skriptum ist etwas durcheinander, da es zum Teil auch nur Kopien sind. Deswegen war ich bissl verwirrt :D Aber jetzt passt ja alles hehe.

[Variable]

ist es denn nicht in beiden Fällen, also Reduce (K,!A) und Reduce (K,A), unerfüllbar?
Hi !

bin ich fertig wenn ich einmal für A und einmal fur nichtA nachgewiesem hab das es unerfüllbar ist ?
wenn also zweimal PI ={{}} rauskommt ?

theoretisch könnt man es ja so interpretiern das nach A und nicht A (es wurde zweimal auf unerfüllbar reduziert ) man mit dem zweiten aller Aufrufe weitermacht nähmlich mit reduce (PI`,B) ( der der nach reduce(PI,A) gekommen ist ) und , der liefert ja logischer weise auch unerfüllbar wenns der reduce (PI, A ) auch schon liefert,.....
Jetzt nehm ich da ebenfalls: reduce (PI`,nichtB) und schau was sich da weiteregibt ?

kann mir jemand folgen ? .....
gegenargumente ?
her damit ! ;)http://hades.gothic.at/iforum/images/smilies/coolsmile.gif

[derGloeckner]

Hi !

bin ich fertig wenn ich einmal für A und einmal fur nichtA nachgewiesem hab das es unerfüllbar ist ?
wenn also zweimal PI ={{}} rauskommt ?

Yup, so hab ich das auch verstanden.

theoretisch könnt man es ja so interpretiern das nach A und nicht A (es wurde zweimal auf unerfüllbar reduziert ) man mit dem zweiten aller Aufrufe weitermacht nähmlich mit reduce (PI`,B) ( der der nach reduce(PI,A) gekommen ist ) und , der liefert ja logischer weise auch unerfüllbar wenns der reduce (PI, A ) auch schon liefert,.....

Naja nich unbedingt, da die Klauselmengen sich ja unterscheiden die mir Reduce zurückliefert, je nachdem ich A oder !A entferne.

DPLL(K)
K' := Reduce(K,A)
K'' := Reduce(K',B)
K''' := Reuce(K'',C)
K'''' := Reduce(K'',!C)
K''''' := Reduce(K',!B)
K'''''' := Reduce(K,!A)

...usw...
d.h K' != K''''''
oder bin ich falsch ?

P.S.
Der obige Code bildet nicht genau das was der Alogithmus macht, da er nicht auf Einer-Klauselmengen prüft, aber ich hoffe es ist verständlich warum sich die Klauselmengen unterscheiden können.

[Variable]

Yup, so hab ich das auch verstanden.


Naja nich unbedingt, da die Klauselmengen sich ja unterscheiden die mir Reduce zurückliefert, je nachdem ich A oder !A entferne.

ja schon klar ich reduce dann mit nichtB statt mit B und es könnte dann eventuell was anderes rauskommen ...
ich hab reduce(PI,A) und reduce (PI`,B) etc...unerfüllbar
dann das selbe mit reduce (PI,nichtA) --> also die allererste if abfrage...wieder unerfüllbar ..
dann eben mit reduce (PI`,nichtB) weiter gemacht ....reduce (PI`,B) liefert ja auch unerfüllbar ....so müsst ich alle aufrufe von reduce austesten

weist du wie ichs mein ?
stimmt das ?

[derGloeckner]

weist du wie ichs mein ?
nope :confused:

[Variable]

nope :confused:
egal http://hades.gothic.at/iforum/images/smilies/wink.gif

war die lösung richtig mit zwei mal unerfüllbar zeigen ?

[derGloeckner]

egal http://hades.gothic.at/iforum/images/smilies/wink.gif

war die lösung richtig mit zwei mal unerfüllbar zeigen ?
naja,
Sie hat dann noch gemeint, das man das alles mit B und C machen müsste, aber ich bin mir da nicht so ganz sicher...
Jedenfalls wollte Sie das hören :)
Aber ehrlich gesagt hätte ich das Skriptum anders verstanden :ahhh:

total verwirrt

[meagain02]

Hallo,

Was versteht man unter UNIT Resolution? In welchem Schritt wird sie bei Reduce (K,B) druchgeführt, kann bitte jmd. 1 Beispiel aus Bsp. 8.5. dafür angeben?

zb. nach Reduce (K',B) uas K'{ {B}, {C}, {!C,B}, {!B,!C}} wird wo genau die UNIT Res. angewendet?

Mfg