4.3 KV-Diagramme 79
4.3 KV-Diagramme
4.3.1 Ableitung der disjunktiven Minimalform aus KV-
Diagrammen
Im Folgenden wollen wir eine alternative Möglichkeit kennenlernen, Boolesche Funktionen
zu minimieren. Diese Möglichkeit basiert auf einer Darstellung der Funktion in Tabellen-
form, den sogenannten Karnaugh-Veitch-Diagrammen, kurz KV-Diagramme genannt. Ge-
hen wir zunächst von folgendem Beispiel aus.
Gegeben sei eine Abbildung f:
2
durch folgende Wertetabelle
a b f(a, b)
00 1
01 0
10 1
11 0
Als kDN lässt sich die Funktion unmittelbar aus dem Diagramm ablesen:
f(a, b) = a’b’ ab’
Die Darstellung dieser Funktion kann nun auf folgende Art und Weise in ein KV-Diagramm
umgesetzt werden:
a
0 1
0
f(0,0)
1
f(1,0)
1
b
1
f(0,1)
0
f(1,1)
0
Die Tabellenspalten nehmen hierbei die möglichen Belegungen der Variablen a und die
Tabellenzeilen die Belegungen der Variablen b auf. In diese Matrix werden dann die ent-
sprechenden Funktionswerte eingetragen.
Wir vereinfachen die Tabellendarstellung dadurch, dass wir nur noch die Einsen eintragen.
Leere Zellen werden automatisch als mit „Null“ belegt angesehen. Die Möglichkeit des Aus-
klammerns von b’ und das Eliminieren von a durch die Umformungsschritte
a’b’ ab’ = (a a)b’ = b’
80 4 Boolesche Algebra und Schaltalgebra
erkennt man in der tabellarischen Darstellungsweise dadurch, dass a sowohl in negierter wie
auch in nichtnegierter Form vorkommt. Wir sehen dies in der folgenden Tabelle am grau
unterlegten „Einserblock“:
a
0 1
0 1 1
b
1
Die Identifikation dieses „Einserblocks“ erlaubt uns, die DM f(a, b) = b’ sofort aus der tabel-
larischen Darstellung abzulesen. Diese Vorgehensweise lässt sich verallgemeinern auf alle
Variablen, in denen „Einserblöcke“ entweder in Zeilen nebeneinander oder in Spalten unter-
einander stehen. Betrachten wir hierzu folgende Matrix für eine Funktion f(a, b).
a
0 1
0 1 1
b
1 1
Diese Matrix entspricht der Funktion
f(a, b) = a’b’ a’b ab’
Im Verfahren nach Quine-McCluskey wäre hier eine Reduktion einmal von a’b’ a’b = a’
und von a’b’ ab’ = b’ möglich gewesen. Die DM für f(a, b) ist somit f(a, b) = a’ b’.
In der Matrix erkennt man diese Möglichkeit durch folgende „Einserblöcke“:
a
0 1
0 1 1
b
1 1
Dies entspricht b’, weil a sowohl in negierter wie auch in nichtnegierter Form vorkommt und
damit eliminiert werden kann.
a
0 1
0 1 1
b
1
1
4.3 KV-Diagramme 81
Dies entspricht a’, weil b sowohl in negierter wie auch in nichtnegierter Form vorkommt und
damit eliminiert werden kann.
Somit kann aus der Tabelle:
a
0 1
0 1 1
b
1
1
f(a, b) = a’ babgelesen werden.
Wir können also Folgendes festhalten: Immer, wenn in der Spalte oder Zeile der Matrix ein
„Einserblock“ auftaucht, können gemäß der Vorgehensweise, die auch beim QMA ange-
wandt wurde, Variablen ausgeklammert und eliminiert werden.
Nun stellt sich allerdings die Frage, wie Funktionen mit mehr als zwei Variablen in Matrix-
form aufgeschrieben werden können und ob sich die oben gewonnenen Erkenntnisse auch
auf diese Fälle übertragen lassen.
Nehmen wir zunächst eine Funktion in drei Variablen f(a, b, c). Hier können wir die Variab-
len gemäß folgender Struktur in die Matrix eintragen:
a, b
00 01 11 10
0 f(0,0,0) f(0,1,0) f(1,1,0) f(1,0,0)
c
1 f(0,0,1) f(0,1,1) f(1,1,1) f(1,0,1)
Die logische Erweiterung dieser Struktur für eine Funktion in vier Variablen f(a, b, c, d)
ergibt sich durch die folgende Tabellenstruktur:
a, b
00 01 11 10
00 f(0,0,0,0) f(0,1,0,0) f(1,1,0,0) f(1,0,0,0)
01 f(0,0,0,1) f(0,1,0,1) f(1,1,0,1) f(1,0,0,1)
11 f(0,0,1,1) f(0,1,1,1) f(1,1,1,1) f(1,0,1,1)
c, d
10 f(0,0,1,0) f(0,1,1,0) f(1,1,1,0) f(1,0,1,0)

Get Logik und Algebra, 2nd Edition now with O’Reilly online learning.

O’Reilly members experience live online training, plus books, videos, and digital content from 200+ publishers.