Logikoptimierung

Startseite
Zweistufige Logik: Expansion und Reduktion             Ausdruck: a + a b a b a + ab   0 0 0 1 1 0 1 1 0 1 1 1 a b a b a b Expansion: Hinzufügen von Mintermen, um dann zu vereinfachen. Zum Ausdruck a+ab können die Minterme ab und/oder ab ohne Veränderung der Wahrheitstabellehinzugefügt werden, da sie durch den Implikanten a bereits abgedeckt sind.   Durch hinzufügen von abkann der Ausdruck vereinfacht werden: a + ab + ab a + b     Reduktion ist der umgekehrte Vorgang. Es wird nichtvereinfacht, sondern erweitert, um lokale Minimazu vermeiden.

Expandieren

Durch das Expandieren einer Funktion durch weitere Implikanten ohne die Funktion und damit die Wahrheitstabelle zu verändern, kann sich die Möglichkeit ergeben Literale zu entfernen. Zum Beispiel kann durch Expansion folgender Ausdruck minimiert werden:

a+ab

Die Wahrheitstabelle hierfür ist

a b a+ab
0 0 0
0 1 1
1 0 1
1 1 1

Zu diesem Ausdruck gehören also die Minterme ab , ab und ab . Es können Minterme hinzugefügt werden, die durch vorhandene Implikanten bereits abgedeckt werden, z.B. können in dem obigen Ausdruck Minterme hinzugefügt werden, die durch den Implikanten a abgedeckt werden, wie z.B. ab oder ab . Wird der Ausdruck mit ab expandiert, vereinfacht sich der Ausdruck wegen ab+ab=b zu a+b . Beide Ausdrücke stellen die gleiche Funktion dar.

Reduktion

Reduktion dagegen liefert vom Ausdruck a+b den Ausdruck a+ab . Die Reduktion erhöht zwar die Kosten der Funktion, indem sie Literale hinzufügt, kann aber notwendig sein, um lokale Minima bei der Optimierung verlassen zu können.