Boolsche Ausdrücke vereinfachen

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