Vereinfachung von logischen Funktionen mit KV-Diagrammen

Mit dem schematischen Vorgehen beim Ermitteln der KNF bzw. DNF erhält man zwar korrekte logische Terme, häufig sind diese jedoch lang und unhandlich.

Wie kann man effizient kurze Terme zu logischen Funktionen aus ihren Wahrheitstafeln erhalten?

Eine Methode dafür sind sogenannte "KV-Diagramme", benannt nach den nach Maurice Karnaugh und Edward W. Veitch (1952/53).

Beispiel 1: Zwei Variablen

Wir starten bei einer logischen Funktion, deren Wahrheitstafel gegeben ist:

Schritt 1: Wertetabelle als Matrix

Als erstes überführt man die Wertetabelle in eine Matrix: An den Seiten stehen die Variablen und alle möglichen Werte (also jeweils "wahr/1" und "falsch/0"). Im Inneren der Matrix wird für die jeweiligen Kombinationen der Eingabewerte der Funktionswert eingetragen:

Schritt 2: Zusammenhängende "wahr"-Bereiche finden

Nun sucht man in den Funktionswerten nach möglichst großen, zusammenhängenden rechteckigen Bereichen, die aus "wahr"-Werten (also "Einsen") bestehen.

Wir müssen alle wahr Werte einbeziehen

Es sind einige Regeln zu beachten, dazu später mehr.

Eine Möglichkeit für das gegebene Beispiel ist folgende:

Jetzt kann man gut ablesen, welche logischen Bedingungen jeweils die farbig markierten "wahr"-Werte festlegen:

Grün: A ist 0, B ist egal - die logische Bedingung, um alle "grünen" Einsen zu erhalten, lautet also .

Rot: A ist 1, B ist 0 - die Bedingung ist also .

Um alle "wahr"-Werte des Diagramms zu erhalten, muss man diese beiden Bedingungen mit "oder" verknüpfen - ein korrekter logischer Ausdruck für die gegebene Wahrheitstafel ist also .

Ergänzung: Überlappende Bereiche sind erlaubt

Ei der Regeln, die man anwenden kann ist, dass sich die rechteckigen Bereiche überlappen dürfen - dann wird durch die oder Verknüpfung aller Teilausdrücke am Ende zwar gelegentlich eine "1" mehrfach erfasst, der logische Ausdruck wird aber einfacher, da man weniger Bedingungen benötigt, um die Bereiche zu adressieren.

Grün: A ist 0, B ist egal - die logische Bedingung, um alle "grünen" Einsen zu erhalten, lautet also .

Rot: B ist 0, A ist egal - die Bedingung ist jetzt also - das ist kürzer als beim ersten Versuch!

Um alle "wahr"-Werte des Diagramms zu erhalten, muss man diese beiden Bedingungen mit "oder" verknüpfen - ein korrekter logischer Ausdruck für die gegebene Wahrheitstafel ist also .

Regeln

Wie angesprochen muss man bei der Auswahl der zusammenhängen Bereiche mit Einsen einige Regeln beachten:

Die Bereiche müssen rechteckig sein

Die Rechtecke dürfen sich überlappen (müssen aber nicht).

Die Anzahl der Einsen in einem Rechteck muss eine Zweierpotenz sein - also 1, 2, 4, 8 oder 16.

Rechteckige Bereiche können auch "über die Ränder hinaus" bestehen.

Beispiel 2: Drei Variablen

Schritt 1: Wertetabelle als Matrix

Da man nun 3 Eingabevariablen hat, muss man bei der Darstellung in einer zweidimensionalen Matrix zu einem kleinen "Trick" greifen:

Man schreibt die Kombination zweier Variablen auf eine Achse der Matrix, die dritte Variable auf die andere Achse:

Schritt 2: Zusammenhängende "wahr"-Bereiche finden

Damit erhält man für die gegebene Wahrheitstafel die folgende Matrix mit den markierten Rechtecken. Man sieh auch nochmal: Die drei benachbarten "wahr" Werte können nicht zu einem Rechteck zusammengefasst werden 1) Keine Zweierpotenz! , aber man kann zwei überlappende Rechtecke mit jeweils 2 Einsen bilden.

Nun ermitteln wir die Ausdrücke für die drei rechteckigen Bereiche:

Rot: Ist der kleinste Bereich, für diesen benötigt man die meisten Bedingungen, hier:

Blau: ( ist egal)

Grün: ( ist egal)

Alle drei Bereiche durch "oder" verknüpft:

Beispiel 3: Vier Variablen

Bei logischen Funktionen mit 4 Eingangsvariablen geht man genauso vor, wie bei solchen mit 3 Variablen - jetzt stehen auf beiden Achsen jeweils die Kombination zweier Variablen. Dabei ist auch die Regel zu beachten, dass man jeweils nur ein Bit zwischen den benachbarten Kombinationen verändern darf.

(A1)

Lies die Funktionswerte für die Eingabewerte 1010, 1110 und 0101 aus der Matrix ab.

Lösung

Filename	Filesize	Last modified
2024-09-25_11-47.png	3.9 KiB	25.09.2024 09:47
2024-09-27_14-53.png	10.5 KiB	27.09.2024 12:53
kv01.png	68.8 KiB	25.09.2024 09:52
kv03.png	15.6 KiB	27.09.2024 07:50
kv05.png	15.6 KiB	27.09.2024 11:54
kv06.png	89.7 KiB	27.09.2024 12:03
kv07.png	154.6 KiB	27.09.2024 12:23
kv08.png	34.3 KiB	27.09.2024 12:33
kv09.png	25.6 KiB	27.09.2024 12:47
kv10.png	51.8 KiB	27.09.2024 12:58
kv11.png	52.5 KiB	27.09.2024 13:14
kvdiagramme.odp	107.1 KiB	24.09.2024 20:02
kvdiagramme.pdf	86.3 KiB	24.09.2024 20:02