Frage zu Bsp. 5 vom letzten Test
Results 1 to 16 of 16
  1. #1
    patricasso's Avatar
    Title
    Baccalaureus
    Join Date
    Feb 2002
    Posts
    750
    Thanks
    1
    Thanked 2 Times in 2 Posts

    Question Frage zu Bsp. 5 vom letzten Test

    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
    http://www.svkukmirn.com + http://www.swc-kukmirn.com

    Topfield TF 5000 PVR 80GB (incl. Alphacrypt) + TF 3000 CIpro (incl. Cryptoworks) + D-BoxII (Sagem - Neutrino :-) + SAB-Explorer CISC + Panasonic DMR-EH52EG-S (80 GB HD/DVD Recorder)... 19,2°E, 13° E
    -----------SUCHE MÜNZTAUSCHPARTNER/INNEN-----------

  2. #2

    Title
    Principal
    Join Date
    Mar 2002
    Posts
    28
    Thanks
    0
    Thanked 0 Times in 0 Posts
    *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.....
    Last edited by Stiller; 19-10-2002 at 19:12.

  3. #3
    patricasso's Avatar
    Title
    Baccalaureus
    Join Date
    Feb 2002
    Posts
    750
    Thanks
    1
    Thanked 2 Times in 2 Posts
    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!
    Last edited by patricasso; 19-10-2002 at 17:20.
    http://www.svkukmirn.com + http://www.swc-kukmirn.com

    Topfield TF 5000 PVR 80GB (incl. Alphacrypt) + TF 3000 CIpro (incl. Cryptoworks) + D-BoxII (Sagem - Neutrino :-) + SAB-Explorer CISC + Panasonic DMR-EH52EG-S (80 GB HD/DVD Recorder)... 19,2°E, 13° E
    -----------SUCHE MÜNZTAUSCHPARTNER/INNEN-----------

  4. #4

    Title
    Principal
    Join Date
    Dec 2001
    Posts
    88
    Thanks
    0
    Thanked 0 Times in 0 Posts
    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.

  5. #5

    Title
    Principal
    Join Date
    Mar 2002
    Posts
    28
    Thanks
    0
    Thanked 0 Times in 0 Posts
    @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.

  6. #6
    -z0nk-'s Avatar
    Title
    Master
    Join Date
    Feb 2002
    Location
    Wien
    Posts
    169
    Thanks
    0
    Thanked 0 Times in 0 Posts
    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-
    zonked [zpnkt] - if someone is zonked or zonked out, they are not capable of doing anything because they are tired, drunk, or drugged; an informal word.

  7. #7

    Title
    Mag.rer.soc.oec
    Join Date
    Nov 2001
    Location
    dzt. München
    Posts
    1,270
    Thanks
    0
    Thanked 0 Times in 0 Posts
    jo, das wäre super, ich steh da auch ziemlich an ...

  8. #8
    -z0nk-'s Avatar
    Title
    Master
    Join Date
    Feb 2002
    Location
    Wien
    Posts
    169
    Thanks
    0
    Thanked 0 Times in 0 Posts
    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-
    zonked [zpnkt] - if someone is zonked or zonked out, they are not capable of doing anything because they are tired, drunk, or drugged; an informal word.

  9. #9
    patricasso's Avatar
    Title
    Baccalaureus
    Join Date
    Feb 2002
    Posts
    750
    Thanks
    1
    Thanked 2 Times in 2 Posts
    Ich denk schon, dass man jede Einerklausel nehmen kann die man will. Jedenfalls habs ich so gemacht. Muss mir das aber selbst nochmal anschauen ...
    http://www.svkukmirn.com + http://www.swc-kukmirn.com

    Topfield TF 5000 PVR 80GB (incl. Alphacrypt) + TF 3000 CIpro (incl. Cryptoworks) + D-BoxII (Sagem - Neutrino :-) + SAB-Explorer CISC + Panasonic DMR-EH52EG-S (80 GB HD/DVD Recorder)... 19,2°E, 13° E
    -----------SUCHE MÜNZTAUSCHPARTNER/INNEN-----------

  10. #10

    Title
    Principal
    Join Date
    Mar 2002
    Posts
    28
    Thanks
    0
    Thanked 0 Times in 0 Posts
    ja, DPLL nimmt (sofern keine Einerklausel vorhanden ist) 1 beliebiges Literal aus allen Klauseln. hauptsache die elimination wird richtig durchgeführt....

  11. #11

    Title
    Mag.rer.soc.oec
    Join Date
    Nov 2001
    Location
    dzt. München
    Posts
    1,270
    Thanks
    0
    Thanked 0 Times in 0 Posts
    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
    Last edited by phlow; 20-10-2002 at 12:17.

  12. #12
    -z0nk-'s Avatar
    Title
    Master
    Join Date
    Feb 2002
    Location
    Wien
    Posts
    169
    Thanks
    0
    Thanked 0 Times in 0 Posts
    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-
    Last edited by -z0nk-; 20-10-2002 at 13:08.
    zonked [zpnkt] - if someone is zonked or zonked out, they are not capable of doing anything because they are tired, drunk, or drugged; an informal word.

  13. #13

    Title
    Mag.rer.soc.oec
    Join Date
    Nov 2001
    Location
    dzt. München
    Posts
    1,270
    Thanks
    0
    Thanked 0 Times in 0 Posts


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

  14. #14
    -z0nk-'s Avatar
    Title
    Master
    Join Date
    Feb 2002
    Location
    Wien
    Posts
    169
    Thanks
    0
    Thanked 0 Times in 0 Posts
    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-
    zonked [zpnkt] - if someone is zonked or zonked out, they are not capable of doing anything because they are tired, drunk, or drugged; an informal word.

  15. #15

    Title
    Principal
    Join Date
    Mar 2002
    Posts
    28
    Thanks
    0
    Thanked 0 Times in 0 Posts
    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.

  16. #16

    Title
    Mag.rer.soc.oec
    Join Date
    Nov 2001
    Location
    dzt. München
    Posts
    1,270
    Thanks
    0
    Thanked 0 Times in 0 Posts
    hoppla, lesen sollte man halt können

    danke Stiller ....

Bookmarks

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •