Seitenleiste
Inhaltsverzeichnis
Karnaugh-Veitch-Diagramm (KV-Diagramm)
Einführung
Das KV-Diagramm erleichtert das Finden eines vereinfachten Ausdrucks.
Ein KV-Diagramm hat wie die Wahrheitstabelle 2n Felder. Jeder Variablenkombination ist ein Feld zugeordnet. Benachbarte Felder unterscheiden sich nur durch ein Literal. Jedes Literal hat 4 Nachbarn (auch Eckfelder).
Zusammenhang zur Wahrheitstabelle
Um ein KV-Diagramm zu erstellen wird auch die Wahrheitstabelle des Ausdrucks benötigt. Um die Grundform des KVs herauszufinden wird für jedes Literal „wahr“ angenommen. Daraus folgt, dass negierte Variablen für „falsch“ stehen.
KVs können mit einer beliebigen Anzahl von Variablen verwendet werden. In diesem Beispiel sind es 4, es könnten aber genauso gut 1, 2, 3, 5 oder mehr sein.
| a | b | c | d | Binär (W = 1, F = 0) | Dezimal | |
|---|---|---|---|---|---|---|
| W | W | W | W | 1 1 1 1 | 15 | |
| W | W | W | F | 1 1 1 0 | 14 | |
| W | W | F | W | 1 1 0 1 | 13 | |
| W | W | F | F | 1 1 0 0 | 12 | |
| W | F | W | W | 1 0 1 1 | 11 | |
| W | F | W | F | 1 0 1 0 | 10 | |
| W | F | F | W | 1 0 0 1 | 9 | |
| W | F | F | F | 1 0 0 0 | 8 | |
| F | W | W | W | 0 1 1 1 | 7 | |
| F | W | W | F | 0 1 1 0 | 6 | |
| F | W | F | W | 0 1 0 1 | 5 | |
| F | W | F | F | 0 1 0 0 | 4 | |
| F | F | W | W | 0 0 1 1 | 3 | |
| F | F | W | F | 0 0 1 0 | 2 | |
| F | F | F | W | 0 0 0 1 | 1 | |
| F | F | F | F | 0 0 0 0 | 0 |
Nun stellen wir das in einem Diagramm dar. Stimmt die Variablenkombination mit der in der Wahrheitstabelle überein, so tragen wir den dezimalen Betrag ein:
| a | a | ¬a | ¬a | ||
|---|---|---|---|---|---|
| b | 12 | 14 | 6 | 4 | ¬d |
| b | 13 | 15 | 7 | 5 | d |
| ¬b | 9 | 11 | 3 | 1 | d |
| ¬b | 8 | 10 | 2 | 0 | ¬d |
| ¬c | c | c | ¬c |
Im ersten Feld ist die Kombination a ∧ b ∧ ¬c ∧ ¬d. Suchen wir diesen Ausdruck in der Wahrheitstabelle finden wir in der Zeile den Wert 12. Dieser Wert wird ins Diagramm eingetragen. Die anderen Felder sind nach dem gleichen Schema auszufüllen.
Bei aussagenlogischen Ausdrücken wird anstatt der dezimalen Werte der Wahrheitswert des Ausdrucks eingetragen.
Die Werte werden immer in dieser Ordnung eingetragen (unabhängig vom Wahrheitswert).
Für KV-Diagramme können außerdem verschiedene Variablenbelegungen verwendet werden, also z.B. die Variable a auf der linken Seite und b oben. Um Verwirrung zu vermeiden wird hier immer die gleiche Belegung verwendet.
Blöcke bilden
Der Hauptzweck des KVs ist die Vereinfachung von Ausdrücken. Dazu müssen möglichst große Blöcke gebildet werden, in denen aber jedes Feld vorkommt. Um mehrere Felder zu einem Block zusammenzufassen müssen sie den gleichen Wahrheitswert haben.
| a | a | ¬a | ¬a | ||
|---|---|---|---|---|---|
| b | W | W | F | W | ¬d |
| b | W | W | F | F | d |
| ¬b | F | W | F | F | d |
| ¬b | W | W | F | W | ¬d |
| ¬c | c | c | ¬c |
Nun muss man die größten W-Blöcke raussuchen.
Was man auf dem ersten Blick vielleicht nicht erkennt: die 4 Eckfelder lassen sich zu einem 4er-Block zusammenfassen.
Die Blöcke werden durch disjunktive verknüpfte Minterme beschrieben.
Bei unserem Beispiel ergibt das folgende Blöcke:
a ∧ b
| a | a | ¬a | ¬a | ||
|---|---|---|---|---|---|
| b | W | W | F | W | ¬d |
| b | W | W | F | F | d |
| ¬b | F | W | F | F | d |
| ¬b | W | W | F | W | ¬d |
| ¬c | c | c | ¬c |
a ∧ c
| a | a | ¬a | ¬a | ||
|---|---|---|---|---|---|
| b | W | W | F | W | ¬d |
| b | W | W | F | F | d |
| ¬b | F | W | F | F | d |
| ¬b | W | W | F | W | ¬d |
| ¬c | c | c | ¬c |
¬c ∧ ¬d
| a | a | ¬a | ¬a | ||
|---|---|---|---|---|---|
| b | W | W | F | W | ¬d |
| b | W | W | F | F | d |
| ¬b | F | W | F | F | d |
| ¬b | W | W | F | W | ¬d |
| ¬c | c | c | ¬c |
Damit haben wir alle W-Felder verwendet. Die Ausdrücke müssen jetzt noch disjunktive verknüpft werden:
(a ∧ b) ∨ (a ∧ c) ∨ (¬c ∧ ¬d)
Besondere Eigenschaften des KVs
Das KV vereinfacht auch die Bildung von Normalformen:
- beschreibt man die W-Felder mit einem möglichst großen Minterm erhält man die DNF
- beschreibt man die F-Felder mit einem möglichst großen Minterm und negiert den Ausdruck, erhält man die KNF
- beschreibt man jedes W-Feld mit einem eigenen Minterm, erhält man die KDNF
- beschreibt man jedes F-Feld mit einem eigenen Minterm und negiert den Ausdruck, erhält man die KKNF