Resolutionsregel

[landy]

Hallo Zusammen,

im Zuge meines Studiums wurde ich mit der Booleschen Algebra konfrontiert. Ich habe aber ein Problem mit dem Vereinfachen von Funktionen. Wir sollen bei der Aufgabe die Resolutionsregel anwenden. Nur mir kann niemand erklären wie die Regel richtig funktioniert. Zur Info, das ist ein halbes Fernstudium und irgendwie kann/will mein Prof und auch meine Ansprechpartner keine ordentliche Erklärung machen.

Vielleicht kann mir hier jemand helfen.

(-a && -b && -c && -d) ||
(-a && -b && c && d) ||
(-a && b && -c && -d) ||
(-a && b && c && d) ||
(a && -b && -c && -d) ||
(a && -b && c && d) ||
(a && b && -c && -d) ||
(a && b && c && d)

Anmerkungen:
- = Negation
&& = Und
|| = Oder

Ich habe bei der Aufgabe einfach Probleme mit dem Kürzen. Ich weiß nicht wie ich Kürzen soll. Man könnte nämlich alles wegkürzen. Ein Arbeitskollege sagte mir heute, dass man pro Zeile immer nur ein Element wegstreichen darf.
Die Musterlösung liegt mir auch vor, aber daraus werd ich nicht schlau.

Wenn jemand so freundlich wäre und mir erklärt wie ich vorgehen soll bzw. wie ich allgemein mit der Resolutionsregel Kürze. Das wär super.

Vielen Dank schon im Voraus.

Grüße,
landy

[blackberry]

Tut mir leid, aber so kannst du keine Resolventen bilden. Für Resolutionen muss deine Formel in KNF vorliegen.

Im Prinzip müssten hier also die &&s und ||s vertauscht sein. Hast du da evtl. beim Abschreiben einen Fehler gemacht und es war anders gemeint?

Ansonsten müsste man die Formel um die Resolutionsregel anwenden zu können nämlich erst von DNF in KNF umwandeln -- und das ist naturgemäß eine extrem hässliche Aufgabe.

P.S.: mir ist auch nicht ganz klar was Resolutionen hier genau bringen sollten, da Resolutionen zum Nachweis von Unerfüllbarkeit eingesetzt werden. Deine Formel ist ja offensichtlich erfüllbar (um genauer zu sein kann man an deiner Formel ihre Modelle sogar schon ablesen)

[landy]

Ich hab die Aufgabe lösen können. Der Professor hat, ich will jetzt nicht sagen er hat einen Fehler gemacht, aber er hat sich falsch ausgedrückt.

Bei meiner Recherche bin ich auch darauf gestoßen, dass man mit einer Resolution die Unerfüllbarkeit anzeigen kann.
Er wollte eigentlich, dass wir die DNF minimieren. Und er wollte, dass wir es mit der Resolutionsregel machen.

Wie man das System nennt, was ich im Endeffekt angewendet hab, ist mir zwar schleierhaft. Aber ich hab das richtige Ergebnis raus.

Ich sitz jetzt grade in einer Vorlesung und kann den Weg und das Ergebnis heut Abend mal posten.

[peppy]

jap, mach das mal bitte würde mich jetzt auch interesesieren :)

[landy]

So, jetzt hab ich mehr Zeit. Wie man den Lösungsweg offiziell nennt, weiß ich nicht. Mir ist er unter Resolutionsregel bekannt. Aber das Ziel ist es die Boolesche Funktion zu minimieren.

(-a && -b && -c && -d) ||
(-a && -b && c && d) ||
(-a && b && -c && -d) ||
(-a && b && c && d) ||
(a && -b && -c && -d) ||
(a && -b && c && d) ||
(a && b && -c && -d) ||
(a && b && c && d)

Diese disjunktive Normalform habe ich as der Wertetabelle rausgeschrieben.

Danach habe ich geschaut welche Terme sich nur in einem Element unterscheiden. Das waren einmal die Terme 1,3,5 und die Terme 4,6,8.

Zur verbesserten übersicht habe ich diese Terme untereinander geschrieben.
Terme 1,3,5:
(-a && -b && -c && -d) ||
(-a && b && -c && -d) ||
(a && -b && -c && -d) ||

Durch Kürzen fallen alle "a" und "b" weg. Auch die negierten. Also ergibt sich daraus:
(-c && -d)

Terme 4,6,8:
(-a && b && c && d) ||
(a && -b && c && d) ||
(a && b && c && d) ||

Hier wird auch wieder gekürzt und wieder fallen die "a" und die "b" weg.
Diesmal ergibt sich aber:
(c && d)

Die beiden übrigen Terme:
(-a && -b && c && d) ||
(a && b && -c && -d)
würden sich nachher wegkürzen, ich habe sie an diesem Punkt schon vernachlässigt.

Als Endergebnis habe ich dann raus (-c && -d) || (c && d)

Das Ergebnis stimmt mit em Ergebnis aus der Musterlösung, die mir vorliegt überein. Man könnte jetzt noch wegen der Notation meckern. Aber ich denke so reicht es auch ;-) In der Musterlösung wird das Kürzen als Resolutionsregel bezeichnet.

Ich hoffe ihr kommt mit meiner Schreibweise klar und könnt alles lesen und verstehen. Falls Fragen offen sind, einfach Fragen ;-)