Was heisst minimieren?
Sie haben bis anhin die logischen Ausdrucke immer in kanonischer Form angeschrieben. Mit den Regeln der boolschen Algebra können aber gewisse Ausdrucke minimiert werden. Hier ein einfaches und wohl einleuchtendes Beispiel.
Es liegt die Aussage X = (\(\neg\)A \(\wedge\) B) \(\vee\) (A \(\wedge\) B) vor. In die Wahrheitstabelle übertragen ergibt dies:

Vergleichen wir nun die Eingangsvariabel B mit der Ausgangsvariable X so sehen wir, dass die Werte identisch sind. Es gilt demnach X = B. Die Variable A spielt keine Rolle, kann also gekürzt werden. Das Ergebnis ist ein minimierter Term.
Zufall oder nicht? Dem gehen wir in der Folge etwas auf den Grund.

Gesetze der boolschen Algebra
Aus der “normalen” Mathematik sind verschieden Regeln wie z.B. “Punkt vor Strich”, das Assoziativ- und Distributivgesetz und vieles mehr bekannt.
Auch in der binären Logik gibt es solche Regeln. Eine erste davon haben Sie bereits kennegelernt, nämlich “UND vor ODER”. Weitere boolschen Gesetzte finden Sie hier in einer Übersicht. Diese Regeln benötigen wir, um komplexe Terme zu minimieren.

Wir werden nun den Regeln folgend obiges Beispiel schrittweise auflösen.
1. Anwendung des Distributivgesetztes

Mittels Substitution (ersetzen einer Variablen) wandeln wir den Ausdruck (\(\neg\)A \(\wedge\) B) \(\vee\) (A \(\wedge\) B) in (C \(\wedge\) B) \(\vee\) (A \(\wedge\) B) um. Wir haben also \(\neg\)A durch C ersetzt und sehen nun eine bekannte Form, die wir umwandeln können.
(C \(\wedge\) B) \(\vee\) (A \(\wedge\) B) = B \(\wedge\) (C \(\vee\) A)
Nun ersetzen wir C wieder durch das Original (\(\neg\)A), was zu folgendem Ausdruck führt: X = B \(\wedge\) (\(\neg\)A \(\vee\) A)

2. Anwendung des Komplementärgesetzes

Der Ausdruck \(\neg\)A \(\vee\) A ergibt immer eine 1.

3. Anwendung des Neutralitätsgesetzes

Die Erkenntnis aus Schritt 2 eingesetzt in die Formal aus Schrirtt 1 ergibt nun X = B \(\wedge\) 1.
Dem Neutralitätsgesetz folgend ergibt sich somit die Formel X = B, was der oben hergeleiteten Überlegung entspricht.

Das Minimiern von Termen mittels boolscher Algebra ist möglich, bedarf aber einer grossen Präzision und genauen Überlegungen, der zu verwendenden Gesetze. Mit dem Karnaugh-Veitch-Diagramm (KV-Diagramm) lassen sich Ausdrucke mit bis zu 4 Variablen mit einem grafischen Verfahren minimieren.

Aufbau des KV-Diagramms
Das KV-Diagramm basiert auf einer n·n Matrix, wobei n für die Anzahl der Eingansgvariablen steht. In unserem Fall also 2, 3 oder 4. Jedem Feld des KV-Diagramms ist somit eine Bitkombination zugeordnet. Es wird also die Wahrheitstabelle in eine Matrix überführt.

2 Eingangsvariable

KV-Matrix mit Eingangsvariablen A und B.

Die Matrix ist wie folgt zu lesen:
Im Feld 0 wird der Ausgangswert zum Bitmuster 00 angeschrieben, im Feld 1 jener des Musters 01 usw. Die Felder sind mit den entsprechenden Dezimalzahlen beschriftet, so dass die Zuordnung einfacher fällt. Es braucht lediglich das Wissen, welches Bitmuster welcher Dezimalzahl entspricht.

Sie finden hier die Vorlagen für die Matrizen mit 2, 3 und 4 Eingangsvariablen. Sie können diese durch klicken auf Ihren Rechner laden und dann für die Bearbeitung von Aufgaben nutzen.

Handhabung des KV-Diagramms zur Minimierung von boolschen Aussagen

Beispiel: Gegeben ist folgende Wahrheitstabelle:

Dies führt zu folgendem KV-Diagramm:

Die farbliche Hervorhebung verdeutlicht, wie die Ausgangswerte in das KV-Diagramm zu übertragen sind.

Nun werden Gruppen benachbarter Zellen mit gleichem Wert (0 oder 1) gesucht und zusammengefasst. Die Gruppen umfassen dabei 2, 4 oder 8 Werte.
Werden 0er markiert, resultiert eine KNF, werden 1er markiert eine DNF.

Das Ergebnis ist X = B, was zu erwarten war, nachem wir Eingangs dieses Beispiel durch Überlegen und mittels boolscher Algebra bereits gelöst haben.

Es gilt folgendes Vorgehen, bei der Anwendung des KV-Diagramms:

1. WHT erstellen (wenn sie nicht schon gegeben ist)
2. KV-Diagramm gemäss der Anzahl der Eingangsvariablen erstellen bzw. passende Vorlage wählen (2×2, 2×4, 4×4)
3. Ergebnisterme aus der WHT ins KV-Diagramm übertragen. Dabei gilt Zeile 0 in Feld 0, Zeile 1 in Feld 1 usw.
4. Je nach Anzahl 0 oder 1 die Minterme bzw. Maxterme suchen.
5. Gruppen mit \(2^n\) (2, 4, 8) benachbarten 1 (Minterm) bzw. 0 (Maxterm) bilden und farblich umranden. Überscheidungen sind erlaubt. Es muss jede 1 bzw. 0 mindestens einmal markiert werden.
6. Pro Gruppe den Term (DNF oder KNF) anschreiben. Es sind nur die Eingansgvariablen beteilgt, die als 1 (bei DNF) bzw. 0 (bei KNF) vorkommen.
7. Den minimierten Gesamtausdruck anschreiben, wobei auch hier zu beachten ist, ob die DNF oder KNF gewählt wurde.

Hinweise:

• Steht eine 1 bzw. 0 alleine (ohne gleichen Nachbarn), so wird diese Stelle durch einen kanonischen Term beschrieben.
• Jede Stelle soll so wenig wie möglich - aber mindestens einmal - markiert werden.
• Es sind möglichst grosse aber so wenig wie möglich Gruppen zu bilden.

Beispiel:

Disjunktive-Normalform minimieren	Konjunktive-Normalform minimieren
übertragen der Terme ins KV-Diagramm
zusammenfassen aller 1er in Gruppen	zusammenfassen aller 0er in Gruppen
minimierte Aussagen für X
X = (\(\neg\)A\(\wedge\)\(\neg\)B\(\wedge\)\(\neg\)D)\(\vee\)(A\(\wedge\)\(\neg\)B)\(\vee\)(\(\neg\)B\(\wedge\)\(\neg\)C)\(\vee\)(\(\neg\)C\(\wedge\)\(\neg\)D)	X = (A\(\vee\)\(\neg\)C\(\vee\)\(\neg\)D)\(\wedge\)(\(\neg\)B\(\vee\)\(\neg\)C)\(\wedge\)(\(\neg\)B\(\vee\)\(\neg\)D)

Lösen Sie nun die Übung 8

Überprüfen Sie Ihre Antworten. Lösung 8
Sollten Sie Fehler haben, schauen Sie sich die Theorie noch einmal genau an, besprechen Sie offene Fragen mit Ihren Kolleginnen und/oder Kollegen. Fragen Sie auch Ihre Lehrperson, wenn Sie weiterführende Hilfe brauchen.

nächstes Kapitel

© René Probst