Boolsche Ausdrücke vereinfachen

[jfheins]

Guten Abend

Ich würde gerne Boolsche Ausdrücke vereinfachen ...

Im Gegensatz zu Luckie habe ich jedoch keinen bestimmten Ausdruck da, sondern wüsste gerne mehr über das allgemene Verfahren, mit dem man solche Ausdrücke vereinfachen kann.

Mal schauen, vll. programmiere ich auch mal so n Tool dafür, wenn ichs verstanden hab
(Features wären dann wahrscheinlich sowas wie "Ausdruck as Tabelle generieren" oder "Ausdruck vereinfachen", aber das ist jetzt Nebensache ...)

Ich hab schon gesehen (in unserem Lehrbuch) dass es da "ein paar" Gleichen gibt, mit denen man rumsoielen kann, aber irgendwie ... greift das nicht so richtig

Wäre nett, wenn mir da wer helfen könnte ... *zu alcähh... Informatik Studenten im allgemeinen rüberschiel*

Danke schonmal

[Matze]

Moin,

ich bin zwar kein Informatik-Student (mehr), aber ich antworte trotzdem mal.

Vereinfachen kannst du die logische Ausdrücke, indem du die konjunktive und disjunktive Normalform ermittelst, doch diese Formen liefern nicht unbedingt den am weitest vereinfachten Ausdruck.

Aber das Karnaugh-Diagramm könnte dich interessieren und das Verfahren nach Quine und McCluskey ebenfalls.

[jfheins]

Zitat von Matze:

Moin,

ich bin zwar kein Informatik-Student (mehr), aber ich antworte trotzdem mal.

Macht nix, im Gegenteil

Ich weis zwar nicht, was diese ...junktiven Ausdrücke sind, aber dieses Diagram mit den Kreisen sieht schön aus (und inzwischen geht Wikipedia auch wieder ...)

Wenn ich also 3 Variablen hab (maximum für mich, mehr hab ich nicht ) dann mach is so ein Diagram
http://upload.wikimedia.org/wikipedi...agramm_ABC.png
Und mach Blöcke, die alle einsen abdecken. Dann gucke ich, was in jedem Block gleich ist, und kann dann den Ausdruck einfach zusammensetzen. Hab ich das richtig verstanden ?

[3_of_8]

Eine DNF ist schon recht nützlich dabei, auch ein binärer Entscheidungsbaum hilft da sehr.

Das funktioniert so:

Du nimmst dir eine aussagenlogische Formel (oder einen Booleschen Ausdruck) und schaust nach, welche Variable am häufigsten vorkommt. Die nennen wir dann V. Dann zeichnest du von der Formel aus zwei Zweige nach unten. Bei dem einen setzt du V:=0, beim anderen V:=1 bzw. V:=F(alse) und V:=T(rue) oder auch V:=O und V:=L.

Dann vereinfachst du nach einer Reihe von Regeln:
A and 0=0, A and 1=A, A or 0=A, A or 1=A für beliebige Terme A
not 0=1, not 1=0
A and A=A, A or A=A, A and not A=0, A or not A=1

Klammern darfst du auflösen, nach den De-Morgan-Formeln, Absorptionsgesetz usw.

Wenn du das hast, machst du bei den zwei Subknoten wieder das gleiche: Häufigste Variable suchen, einsetzen usw.

Irgendwann hast du dann lauter terminale Knoten, also Formeln, in denen keine Variable mehr vorkommt, die lassen sich dann vereinfachen als 0 oder 1.

Da kannst du dann eventuell ableiten, wie die Formel "funktioniert", also welche Variablen überhaupt wichtig sind, welche sich "rauskürzen", ob die Formel allgemeingültig ist oder unerfüllbar und wieviele Modelle sie hat.

EDIT: Disjunktive Normalform geht so:

Sei V eine Variable.
V und not V sind Literale.

Seien L(1) bis L(n) Variablen.
Ein Minterm ist L(1) and L(2) and ... and L(n).

Seien M(1) bis M(n) Minterme.
Eine Disjunktive Normalform, auch Boolesches Polynom genannt, ist M(1) or M(2) or ... or M(n).

Eine Disjunktive Normalform ist also die Oder-Verbindung der Und-Verbindung von verneinten oder nicht-verneinten Variablen.

[jfheins]

Ehrlich gesagt: Da finde ich das mit der coolen Tabelle einfacher

Zitat:

Klammern darfst du auflösen, nach den De-Morgan-Formeln, Absorptionsgesetz usw.

Da wollte ich ja grad drumherum kommen

[3_of_8]

Die sind nicht schwer.

De-Morgan-Gesetze:
not (A and B)=not A or not B
not (A or B)=not A and not B

Absorptionsgesetze:
A and (A or B)=A
A or (A and B)=A

Idempotenzgesetze:
A and A=A
A or A=A

Distributivgesetze:
A and (B or C)=(A and B) or (A and C)
A or (B and C)=(A or B) and (A or C)