KV-Diagramme

Optimierung der disjunktiven und konjunktive Normalform

Boolesche Funktionen werden in der Regel durch Wahrheitstabellen dargestellt. In den Wahrheitstabellen werden Eingangs- und Ausgangsinformationen eines Schaltkreises definiert. Diese können, abhängig von der Anzahl der Eingangs- und Ausgangsvariablen sehr groß und unübersichtlich sein. Häufig können solche Funktionen durch das Auflösen und Zusammenfassen von Variablen vereinfacht werden.

Mit Hilfe von KV-Diagrammen (Karnaugh-Veitch-Diagramm) können Funktionsgleichungen bzw. deren Terme, die in der disjunktiven oder der konjunktiven Normalform vorliegen, anschaulich zusammengefasst werden. Ein KV-Diagramm ist im Grunde genommen nur eine andere Schreibweise für eine Wertetabelle. Es weist immer genau so viele Felder auf, wie die Wertetabelle Zeilen hat. Ein KV Diagramm für eine Wertetabelle mit 3 Eingangsvariablen hat also Acht Felder.

Damit die Vereinfachung bzw. Optimierung funktioniert müssen die Felder  in einer ganz bestimmten Weise zueinander angeordnet sein. Die Eingangsvariablen werden außen an die Kanten des Diagramms gesetzt. Jeder Eingangsvariable ist eine Kante zugeordnet, und zwar zur Hälfte für die nicht negierte Variable und zur Hälfte für die negierte Variable. Gegenüberliegende Kanten müssen unterschiedlich aufgeteilt, und es können nur 2er, 4er, 8er usw. Blöcke gebildet werden. Die Blöcke sollten dabei immer so groß wie möglich sein. Gegenüberliegende Kanten gelten als benachbart, so dass sie als Blöcke zusammengefasst werden könne. Hierzu gleich mehr in den Beispielen. Zur graphischen Vereinfachung mit Hilfe des KV-Diagramms muss eine Boolesche Funktion immer in Form einer KNF oder einer DNF vorliegen.

Disjunktive Normalform (DNF)

Bei der disjunktiven Normalform werden alle Terme aus der Wahrheitstabelle mit dem Wahrheitswert "1" betrachtet und anschließend durch das KV-Diagramm zusammengefasst. Die Terme setzen sich bei der DNF aus ODER Verknüpfungen zusammen (X ∨ Y ∨ Z). Die einzelnen Elemente der ODER Verknüpfung (X, Y, Z) können Variablen, negierte Variablen oder UND Verknüpfungen sein. 

Beispiel:(A ∧ B) ∨ (¬A ∧ C)

Konjunktive Normalform (KNF)

Die konjunktive Normalform betrachtet alle Terme mit dem Wahrheitswert "0". Die Terme setzen sich hierbei aus UND Verknüpfungen zusammen (X ∧ Y ∧ Z). Die einzelnen Elemente der UND Verknüpfung (X, Y, Z) können Variablen, negierte Variablen oder ODER Verknüpfungen sein. 

Beispiel:(A ∨ B) ∧ (¬A ∨ C)

KV-Diagramm Beispiel mit 2 Eingangsvariablen

Im folgenden Beispiel wird zunächst anhand der Wertetabelle die konjunktive und disjunktive Normalform gebildet. Die Wertetabelle und die daraus resultierende Schaltung hat 2 Eingangsvariablen. Anschließend werden die beiden Normalformen mit Hilfe eines KV Diagramms vereinfacht / optimiert. Durch die Optimierung der Terme, verkürzen sich die Gleichungen der DNF und der KNF erheblich.

KV-Diagramme Beispiel mit 3 Eingangsvariablen

Im folgenden Beispiel wird zunächst anhand der Wertetabelle die konjunktive und disjunktive Normalform gebildet. Die Wertetabelle und die daraus resultierende Schaltung hat 3 Eingangsvariablen. Anschließend werden die beiden Normalformen mit Hilfe eines KV Diagramms vereinfacht / optimiert.

KV-Diagramme Beispiel mit 4 Eingangsvariablen

Im folgenden Beispiel wird ein KV Diagramm mit 4 Variablen erstellt. Zusammenhängende Blöcke sind durch farbige Kreise umrandet. Es gibt häufig unterschiediche Lösungswege eine vereinfachte boolesche Funktion zu ermitteln. Man hätte auch die 4 vertikal angeordneten Einsen rechts zusammenfassen können. Um alle Möglichkeiten der "Block-Zusammenfassung" zu demonstrieren, wurden allerdings die 4 Eckblöcke gewählt.


Boolesche Algebra und Grundgatter

Schaltsymbole, Gesetze / Rechenregeln, Schaltnetze, Halbaddierer, Volladdierer
keyboard_arrow_right

Werbung

Maconline
Maconline