8.4

[Septic.exe]

Ich mach mal einen Ansatz, nicht hauen, wenn er falsch is ;):

Die Resolvente aus {A, B, !C} und {A, !B, C} ergibt doch {A}.
Die Resolvente aus {!A, !B, C} und {!A, B, !C} sollte {!A} ergeben.

Tja ... und die Resolvente aus diesen beiden "Dingern" ergibt {} ... damit sollte das ganze unerfüllbar laut Skriptum Seite 90, Folgerung 3.58 sein ... sollte doch so stimmen ... oder?

[jamironico]

ich habe genau das gleiche bekommen. hoffentlich stimmts auch.

[Kugelfisch]

Ahm und was ist mit {!A, !B} passiert?

Wie hast du das wegegeben?

[Cassandra]

Die Resolvente aus {A, B, !C} und {A, !B, C} ergibt doch {A}.
Die Resolvente aus {!A, !B, C} und {!A, B, !C} sollte {!A} ergeben.


Das geht so sicher nicht. Die Resolutionsregel besagt, dass immer nur über eine Variable auf einmal resolviert werden darf.

[Murmel]

hmmm aber macht es das nicht unlösbar, wenn man nicht 2 gleichzeitig verwenden kann? in dem Bsp gibt es nämlich keine Klausel mit nur einer Variable, dh es müssen letztlich immer Klauseln zu 2 Variablen rauskommen, wenn du immer nur mit einer auflöst.

Und logisch wärs auch, vielleicht ist diese Resolutionsregel einfach nicht allgemein genug gefasst?

oder man könnte Variablenumbenennung durchführen, also sagen, dass F=B^!C , daher erste Klausel {A,F} und zweite {A, !F}. Aber letztendlich kommt es auf dasselbe raus, wie die Regel auch für mehrere gleichzeitig anzuwenden (wodurch auch dies der Beweis dafür wäre, dass es für mehrere anwendbar ist)

überzeugt? ;)

lG,
Murmel

edit: hab nochmal drüber nachgedacht, es machts doch nicht unmöglich, vielleicht gibts auch eine alternative Lösungsvariation. Ich bin aber trotzdem überzeugt, dass die Variante auch stimmt.

[Plantschkuh!]

in dem Bsp gibt es nämlich keine Klausel mit nur einer Variable, dh es müssen letztlich immer Klauseln zu 2 Variablen rauskommen, wenn du immer nur mit einer auflöst.
Echt? Na dann resolvier mal {A, !B} mit {A, B} und erzähl, wie deine Resolvente mit zwei Variablen aussieht.

Und logisch wärs auch, vielleicht ist diese Resolutionsregel einfach nicht allgemein genug gefasst?
Ja, vielleicht. Sie ist ja nur vollständig und korrekt. Ist das deine auch? Und was heißt "logisch"?

oder man könnte Variablenumbenennung durchführen, also sagen, dass F=B^!C , daher erste Klausel {A,F} und zweite {A, !F}.
!F wäre dann !B oder C.

überzeugt? ;)
Erfinden von Regeln ist nicht überzeugender als das Lesen des Skriptums, nein.

[Murmel]

hmmm ok stimmt, war ein Rechenfehler von mir

Also ich hab bis jetzt folgendes, vielleicht hat ja noch wer andere Klauseln gefunden, die zur Lösung führen:
1. {A, B, !C}
2. {A, !B, C}
3. {!A, !B, C}
4. {!A, B, !C}
5. {!A, !B}

Aus 2&3 folgt: 6. {!B, C}
Aus 1&4: 7. {B, !C}
Aus 4&5: 8. {!A, !C}

Vielleicht hab ich irgendwie eine Denkblockade aber ich glaub, mehr mögliche Ableitungen gibt es nicht (Mit den As kann man nichts mehr anfangen, da die einzigen Klauseln mit A "verbraucht" sind, die beiden Klauseln die weder A noch !A beinhalten lassen sich nicht kombinieren), und daher ist das Ganze auch erfüllbar, aber kann auch sein, dass ich mich schon wieder irre. Ich würde das jedenfalls als Beweis für eine Erfüllbarkeit ansehen.

lG,
Murmel

[kambo]

5. {!A, !B}
Aus 2&3 folgt: 6. {!B, C}

Aus 5&6: 8. {!A, C}
Falsch.....aber egal.......das ändert nichts.
Meiner Meinung nach ist die Formel erfüllbar

[Murmel]

hast Recht, somit fallen 8, 10 und 11 weg, habs oben korrigiert

lG,
Murmel

[ENDe]

aber muss man nicht die leere Menge {} herleiten?
Immerhin muss man ja die negation Widerlegen damit die original Formel stimmt?

[Murmel]

Ja, wenn man die leere Menge herleiten kann, ist es unerfüllbar. Aber da das nicht geht, ist das Ganze erfüllbar.

Ich weiss schon, der Beweis "es geht nicht mehr weiter abzuleiten" ist nicht ganz so elegant, aber da kann man halt nix machen :D

[Dasyno]

zurückgezogen

[jamironico]

ist nicht die 5 Klausel eine teilmenge von der 3ten, also eine subsumtion, dass heisst das man es einfach nicht mehr beruecksichtigen muesen. (seite 92 im Skriptum)

Also haben wir dann nur noch diese vier Klauseln.

1. {A, B, !C}
2. {A, !B, C}
3. {!A, !B, C}
4. {!A, B, !C}

Aus 2&3 folgt: 6. {!B, C}
Aus 1&4: 7. {B, !C}

weil man nur ein Variable resolvieren darf bekommt man entweder {C, !C} oder {!B, B} als den Resolvent. Und das bringt uns zu unser erfuellbarkeit. Oder? kann das irgendwie stimmen?

[Murmel]

So hier eine korrekte Lösung :thumb: :
...
2: {A,¬B,C} e K
4: {¬A,B,¬C} e K
7: {} Resolvente 2,4


Eben nicht, lies dir mal den ganzen Thread durch, man darf immer nur eine Variable ableiten, und nicht 2 oder gleich 3 wie du das hier machst.


¬ kriegt man durch "Alt Gr" + E (Euro Symbol)
Da kommt bei mir nur das €-Symbol raus.

lG,
Murmel

[Dasyno]

zurückgezogen --> Denkfehler

[Murmel]

bekommt man entweder {C, !C} oder {!B, B} als den Resolvent. Und das bringt uns zu unser erfuellbarkeit. Stimmt, an die beiden hab ich gar nicht gedacht.

lG,
Murmel

[Dasyno]

Da kommt bei mir nur das €-Symbol raus.

lG,
Murmel

nicht im Forum Posting Button "Alt Gr" und dazu das "E" drücken

¬ also bei mir gehts

[Murmel]

Mach ich ja, für die Variable B und dass A,C wegfallen ist ein Bonus
Nein, sie fallen eben nicht weg, es handelt sich um Av!A und Cv!C (also immer erfüllbar), nicht um A^!A und C^!C (nie erfüllbar) wie du es rechnest.

lG
Murmel

[5piritus]

hey ich glaub ich hab die lösung!!

http://stud3.tuwien.ac.at/~e0325411/thinf84.jpg


sers
5piritus

[mmp]

weil man nur ein Variable resolvieren darf bekommt man entweder {C, !C} oder {!B, B} als den Resolvent. Und das bringt uns zu unser erfuellbarkeit. Oder? kann das irgendwie stimmen?

Jo denke auch weil es heißt ja dann
K={{!B,B}} und hier kann man ja Tautologieelemination vornehme und {!B,B} eleminieren und dann ist K={} und somit erfüllbar.

Was würde eigentlich sein wenn in K noch was stehen würde? (was anderes als die leere Menge)

[Erendis]

@ mmp

wie kommst du auf K={!B,B} und K={!C,C} ??
ich erhalte nur {B,!C} und {!B,C}.
Kann ich da einfach einmal das B weglassen und die C's zusammenfassen oder auch umgekehrt?

[mmp]

@ mmp

wie kommst du auf K={!B,B} und K={!C,C} ??
ich erhalte nur {B,!C} und {!B,C}.
Kann ich da einfach einmal das B weglassen und die C's zusammenfassen oder auch umgekehrt?

Jo, du kannst dann entweder C oder B resolvieren.
Wenn du B resolvierst bekommst du {C,!C} bzw. wenn du C resolvierst {B,!B}

[seg2]

Worauf muss man bei dem Bsp achten?

1) Man darf nur Mengen zusammenfassen, die EINE unterschiedliche Variable enthalten.

2) Man soll auf Tautologien achten - was bedeutet das?

3) worauf muss man noch achten?


Also:
1. {A, B, !C}
2. {A, !B, C}
3. {!A, !B, C}
4. {!A, B, !C}
5. {!A, !B}

2&3: 6. {!B, C}
1&4: 7. {B, !C}
4&5: 8. {!A, !C}

Dabei sieht man, dass 6. in 2. und 3. enthalten ist. - Was bedeutet das?
Könnte man nicht 5. und 6. kombinieren?

Das Beispiel scheint einfach zu sein, und trotzdem is es verwirrend :(

[derGloeckner]

1) Man darf nur Mengen zusammenfassen, die EINE unterschiedliche Variable enthalten.
Meine Tutorin wusste davon leider nichts und hat an der Tafel auch "Mehrfachelemination" durchgehen lassen, auf Nachfrage meinte Sie allerdings, das es an dem Beispiel nichts ändert, wenn man nur eine Variable eleminiert.


2) Man soll auf Tautologien achten - was bedeutet das?
Ich hab subsumiert (Folien Seite 170), da meiner Meinung nach Formel 5 die Formel 3 subsumiert (da 5 Teilmenge von 3) und nur mit den Formeln 1,2,4,5 weitergerechnet.

Aber "nach Gefühl" und systematisches Einsetzten sieht es so aus, als ob man eine Resolutionswiderlegung nicht gefunden werden kann, da sich die leere Menge nicht ableiten lässt => same as above

[Janine]

wie genau kommst du auf diese lösung derGloeckner?

:confused:

[Kitty]

4 & 8 kann nicht stimmen

[Murmel]

4 & 8 kann nicht stimmenDa stimm ich dir zu.

lG,
Murmel

[derGloeckner]

Da stimm ich dir zu.

lG,
Murmel Yup, habs geändert.

[JGoblin]

Also wenn nun Klausel Nr. 5 in Klausel 3 Enthalten (Subsumiert) ist können wir das getrost weglassen (wir haben ja KNF), außerdem stehts im Skriptum.
nun aus 1 und 4 {B,!C} = 6
und aus 2 und 3 {!B,C} = 7 gebastelt

kann ich nun aus
6 und 7 die leere klausel oder die leere menge basteln?
oder ist das verboten weil sich 2 Variablen untescheiden?

oder erhalte ich da keine aussage und muss anders weiterprobieren ?
mfg ich

[derGloeckner]

Also wenn nun Klausel Nr. 5 in Klausel 3 Enthalten (Subsumiert) ist können wir das getrost weglassen (wir haben ja KNF), außerdem stehts im Skriptum.
nun aus 1 und 4 {B,!C} = 6
und aus 2 und 3 {!B,C} = 7 gebastelt
Also so wie ich das Skriptum verstanden hab, und so wie ich das von meiner Tutorin danach noch verstanden hab, fliegt 3, da 5 eine Untermenge ist.
Macht ja auch mehr Sinn IHMO, da wohl C egal ist wenn A und B beide neigert sind, wir wollen ja schlieslich ne kürzere KNF und nicht ne längerer, die gleichbedeutend sind.


kann ich nun aus
6 und 7 die leere klausel oder die leere menge basteln?
oder ist das verboten weil sich 2 Variablen untescheiden?

oder erhalte ich da keine aussage und muss anders weiterprobieren ?
mfg ich Tja, das würde ich jetzt auch gern mal wissen, in der Übung wurde es anerkannt, und die "offizielle" Lösung, in die ich einen kurzen Blick werfen durfte sah genauso aus. Steht ja auch leider nur im Skriptum, das die beiden Variablen einaml negiert und einmal normal vorkommen müssen (in den Klauseln) aber steht leider nicht dabei was mit anderen Variablen sein muss/kann :(

derGloeckner

P.S.
Für alle Zweifler der Subsumtion, lest euch nochmal den Abschnitt "Heuristiken und Strategien" ab Seite 92 im Skriptum durch, dann sollte klar sein, das (5) (3) ersetzt und nicht andersrum.

[Variable]

Tja, das würde ich jetzt auch gern mal wissen, in der Übung wurde es anerkannt, und die "offizielle" Lösung, in die ich einen kurzen Blick werfen durfte sah genauso aus.
wie sah sie denn aus ?

[JGoblin]

Also wenn ich mir nun eine Wahrheitstabelle mach sehe ich das das ganze unerfüllbar ist, und das ist mir sogar klar wenn ich mir die ganzen Klauseln ansehe.
Eine der Klauseln wird immer f wenn ich die werte einsetze, und da die klauseln untereinander mit UND verknüft sind ist wenn eine f ist der ganze ausdruck auch f.
Nur bin ich mir bei dem Verfahren nicht sicher.
Wär nett wenn das nochmal wer erklären könnte.
Dankesehr JGoblin

[derGloeckner]

wie sah sie denn aus ?
{{}} durch {B,!C} und {!B,C}, sprich Doppelelemination
Woher die Resoventen gebildet wurden weiss ich aber nicht.

[Variable]

Leere Menge durch {B,!C} und {!B,C}, sprich Doppelelemination
Woher die Resoventen gebildet wurden weiss ich aber nicht.
dachte ich mir schon ....

ich stell mir das so vor ich wähle ien duales Literal
ich nehm mal B bzw !B

die Resolvente ist {C,!C}....das entspricht einer Tautologie also kommt {} heraus ....
kann man das so machen bzw sich so vorstellen ,ich finds so zumindest logisch (für den fall das ich die Resolvente immer nur aus einem bestimmern dualen Literal bilden darf )

[Cassandra]

Hallo! Ich glaube, ihr versteht hier was falsch.

Die Regel mit der "Mehrfachresolution" kann nicht stimmen. Beispiel: Die Klauselmenge {{ !A, B }, { !B, A }}. Als KNF geschrieben ist das (!A | B) & (!B | A), was nichts anderes ist als (A -> B) & (B -> A), und das ist (A nexor B), was offensichtlich erfüllbar ist. Wenn man hier aber eure Mehrfachresolution anwendet, kriegt man die leere Klausel raus, und die ist unerfüllbar! Daraus folgt ein Widerspruch, denn die Klauselmenge kann nicht gleichzeitig erfüllbar und unerfüllbar sein.

Weiters würde es allen guttun, wenn wir zwischen einer leeren Klauselmenge (erfüllbar) und einer Klauselmenge, die die leere Klausel enthält (unerfüllbar), unterscheiden. Einfach { } hinschreiben ist nicht eindeutig.

[Superwinki]

Gibts dazu jetzt eine korrekte Lösung??

Ich blicke da immer noch nicht so ganz durch :confused:

[IceBreaker]

noch immer keine "offizielle" Lösung?

mfg

ICE

[Cassandra]

1. {A, B, !C}
2. {A, !B, C}
3. {!A, !B, C}
4. {!A, B, !C}
5. {!A, !B}

Aus 2&3 folgt: 6. {!B, C}
Aus 1&4: 7. {B, !C}
Aus 4&5: 8. {!A, !C}

[..] mehr mögliche Ableitungen gibt es nicht [..] und daher ist das Ganze auch erfüllbar

Richtig! Man muß hier nicht krankhaft versuchen Himmel und Hölle in Bewegung zu setzen um unbedingt eine leere Klausel herleiten zu können und damit ein unerfüllbar zu erreichen. In diesem Fall ist die Klauselmenge ganz einfach erfüllbar.

Was man hier nur noch ein bisschen anders machen könnte: man kann gleich am Anfang die Klausel Nr.3 weglassen, da diese von Nr.5 subsumiert wird.
Bringt aber natürlich genau das gleiche Ergebnis.

[Murmel]

*g* Danke, find ich irgendwie lustig wie manche noch tagelang herumgrübeln obwohl die Lösung schon lange dasteht... :D

lG,
Murmel

[Cassandra]

ja...richtige Lösungen werden hier manchmal gerne ignoriert *gg*

[Superwinki]

Na ja, das soll jetzt nicht präpotent klingen, aber wenn man aus den Posts herauslesen könnte, dass sich der Poster sicher (!) ist, stellt das auch kein Problem dar.

In deinem Lösungsthread stehen aber Dinge wie, "würde", "könnte"... Wenn du dir 100%ig sicher bist schreibs hin, ansonsten darfst du dich über nachfragen und andere Ideen nicht wundern... :o

[Murmel]

Stimmt schon, da war ich mir ein bisschen unsicher, weil ich das Ganze am Anfang völlig falsch angegangen bin (s. ganz oben).

Aber man braucht ja trotzdem nicht gleich das Rad völlig neu erfinden wollen und kann von Lösungen, die schon da sind, ausgehen, bzw einfach nur sagen, ob dasselbe rauskommt.

Ist ja egal, wer jetzt die richtige Lösung postet, nur wären viele Threads einfacher zu lesen, wenn sie die Struktur "Meine Lösung 1 - ja, finde dasselbe - nein finde was anderes weil..., hier meine 2 - finde dasselbe wie 2 ..." hätten statt "meine Lösung - hier ist meine - ahja hier meine etc..." (Das ist jetzt arg übertrieben, aber ich glaub ihr wisst was ich meine.)

Einfach weil, wenn jetzt jemand hierherkommt der sich nicht auskennt, er sich noch weniger auskennt, wenn er mehrere verschiedene Lösungen sieht, die überhaupt keinen Bezug zueinander haben.

lG,
Murmel, für ein übersichtlicheres Forum schreibend ;)

[Superwinki]

Geb dir schon recht, kenne das auch aus dem Matheforum. Die beste Möglichkeit, Übersicht aufrecht zu erhalten, ist einfach Post für Post fragen zu beantworten und die eigene Lösung zu argumentieren/erweitern/verwerfen. Das kann aber recht mühsam sein, vor allem wenn der Thread schon ewig lang ist und man sich selber über die Lösung im Klaren ist.
Als Konsequenz postet man dann z.T. einfach gar nichts mehr, was die anderen Leser natürlich auch nicht bestätigt bzw. dazu bringt Dinge einzusehen...

Magische Schlussworte sind ja auch immer, "so wars in der UE" oder "der Prof. hat gmeint..." ;)

Auf jeden Fall trotzdem Danke fürs Lösung posten (und erklären!) :thumb:

[Murmel]

Stimmt, manchmal ist es mühsam, sich einen Thread durchzulesen, der schon so lang ist, manchmal wird er aber auch erst dadurch so lang, dass sich viele den Thread selbst wenn er noch kurz ist gar nicht erst durchlesen, bevor sie ihre Lösung posten, bestes Beispiel ist dieser Thread hier :D

lG,
Murmel

[kambo]

Heute hab ich erfahren, dass man bei der Resolution nicht alle Klauseln anwenden muss.

[Plantschkuh!]

ich glaub, mehr mögliche Ableitungen gibt es nicht
Eine Klarstellung, da das in diesem Thread, soweit ich sehen konnte, nicht explizit erwähnt wurde:
Es gibt sehr wohl noch mehr mögliche Ableitungen. Aus den ersten beiden Klauseln {A, B, !C} und {A, !B, C} kann man mittels Resolution über das Atom B die Klausel {A, !C, C} und über C die Klausel {A, B, !B} gewinnen. Im vorliegenden Beispiel können diese allerdings, sobald sie erzeugt worden sind, gleich wieder weggeworfen werden. Warum? Sie sind Tautologien und daher zur Herleitung der leeren Klausel sicher nicht nötig.
Prinzipiell kommt bei Resolution von zwei Klauseln, die sich in mindestens zwei Negationen unterscheiden, immer eine Tautologie raus; das müßte man aber eigentlich dazusagen. Der obige Satz sollte richtiger also "mehr nichtredundante Ableitungen gibt es nicht" lauten.