KV-Diagramme und Logikgatter
Computer rechnen mit nur zwei Werten: 1 (Strom, wahr) und 0 (kein Strom, falsch). Die Bausteine dafür heißen Logikgatter. Eine Schaltung beschreibt man mit einer Wahrheitstafel – und mit dem KV-Diagramm (Karnaugh-Veitch-Diagramm) findet man die kürzeste Formel und damit die Schaltung mit den wenigsten Gattern.
Die wichtigsten Logikgatter
Die Schaltzeichen sind nach der Norm DIN EN 60617 Rechtecke mit einem Kennzeichen: & für UND, ≥1 für ODER, =1 für XOR. Ein kleiner Kreis am Ausgang bedeutet „nicht“.
$Q = A \land B$
$Q = A \lor B$
$Q = \neg A$
$Q = A \oplus B$
$Q = \neg (A \land B)$
$Q = \neg (A \lor B)$
$Q = A \Leftrightarrow B$
| $A$ | $B$ | UND | ODER | XOR | NAND | NOR | XNOR |
|---|---|---|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 | 1 | 1 | 1 |
| 0 | 1 | 0 | 1 | 1 | 1 | 0 | 0 |
| 1 | 0 | 0 | 1 | 1 | 1 | 0 | 0 |
| 1 | 1 | 1 | 1 | 0 | 0 | 0 | 1 |
- UND (AND) ($A \land B$): Ausgang 1, nur wenn beide Eingänge 1 sind.
- ODER (OR) ($A \lor B$): Ausgang 1, wenn mindestens ein Eingang 1 ist.
- NICHT (NOT) ($\neg A$): Ausgang 1, kehrt den Eingang um.
- XOR (exklusives Oder) ($A \oplus B$): Ausgang 1, wenn genau ein Eingang 1 ist.
- NAND ($\neg (A \land B)$): Ausgang 1, außer wenn beide Eingänge 1 sind.
- NOR ($\neg (A \lor B)$): Ausgang 1, nur wenn beide Eingänge 0 sind.
- XNOR (Äquivalenz) ($A \Leftrightarrow B$): Ausgang 1, wenn beide Eingänge gleich sind.
Gut zu wissen
Aus NAND-Gattern allein lässt sich jede Schaltung bauen: $\neg A = \operatorname{NAND}(A, A)$, $A \land B = \neg\operatorname{NAND}(A, B)$ und $A \lor B = \operatorname{NAND}(\neg A, \neg B)$ (De Morgan). Deshalb bestehen viele Computerchips im Kern aus NAND-Gattern.
Vom Term zum KV-Diagramm
Im KV-Diagramm steht jede Zeile der Wahrheitstafel in einem eigenen Feld. Bei drei Variablen gibt es 8 Felder (2 Zeilen × 4 Spalten), bei vier Variablen 16 (4 × 4). Die Spalten und Zeilen sind so angeordnet, dass sich benachbarte Felder in genau einer Variablen unterscheiden: 00, 01, 11, 10 (Gray-Code). Auch der linke und rechte Rand sowie der obere und untere Rand gelten als benachbart.
So vereinfachst Du mit dem KV-Diagramm
- Trage für jede Belegung mit $f = 1$ eine 1 ins passende Feld ein, sonst 0.
- Fasse benachbarte Einsen zu möglichst großen Rechteck-Blöcken aus 1, 2, 4, 8 oder 16 Feldern zusammen. Blöcke dürfen sich überlappen und über den Rand gehen.
- Nimm so wenige Blöcke wie möglich, aber jede 1 muss in einem Block liegen.
- Jeder Block wird zu einem UND-Glied: Variablen, die im Block ihren Wert wechseln, fallen weg. Ein 2er-Block spart eine Variable, ein 4er-Block zwei, ein 8er-Block drei.
- Alle Glieder werden mit ODER verbunden – das ist die kürzeste disjunktive Form.
Beispiel mit drei Variablen: $f = (A \land \neg C) \lor (B \land C) \lor (A \land B)$
| A ↓ BC → | $\neg B\,\neg C$ | $\neg B\,C$ | $B\,C$ | $B\,\neg C$ |
|---|---|---|---|---|
| $\neg A$ | 0 | 0 | 1 | 0 |
| $A$ | 1 | 0 | 1 | 1 |
- $B \land C$
- $A \land \neg C$
Zwei Blöcke reichen: $f = (B \land C) \lor (A \land \neg C)$. Das Glied $A \land B$ ist überflüssig – seine beiden Einsen liegen schon in den anderen Blöcken (in der Logik heißt das Konsensregel).
Beispiel mit vier Variablen: Einsen in den Zeilen 0, 1, 2, 4, 5, 6, 8, 9, 12, 13 und 14
Die Zeilennummer ist die Dualzahl $ABCD$, Zeile 13 = 1101 heißt also $A = 1$, $B = 1$, $C = 0$, $D = 1$.
| AB ↓ CD → | $\neg C\,\neg D$ | $\neg C\,D$ | $C\,D$ | $C\,\neg D$ |
|---|---|---|---|---|
| $\neg A\,\neg B$ | 1 | 1 | 0 | 1 |
| $\neg A\,B$ | 1 | 1 | 0 | 1 |
| $A\,B$ | 1 | 1 | 0 | 1 |
| $A\,\neg B$ | 1 | 1 | 0 | 0 |
- $\neg C$
- $B \land \neg D$
- $\neg A \land \neg D$
Ein 8er-Block (alle Felder mit $C = 0$) und zwei 4er-Blöcke, einer davon über den Rand: $f = \neg C \lor (B \land \neg D) \lor (\neg A \land \neg D)$. Aus 11 Gliedern mit je 4 Variablen werden 3 kurze.
Die Schaltung dazu: je Glied ein UND-Gatter (ein Glied mit nur einer Variablen braucht keins), alle zusammen in ein ODER-Gatter.
Selbst ausprobieren
Klicke Felder an, um sie zwischen 0 und 1 umzuschalten. Das Diagramm sucht die kürzeste Form und markiert die Blöcke farbig.
Hast Du eine Formel statt eines Diagramms? Der Wahrheitstafel-Rechner erstellt zu jeder Formel mit 2 bis 4 Aussagen die Wahrheitstafel, das KV-Diagramm mit Blöcken und die passende Schaltung.
Typische Fehler
- Falsche Reihenfolge: Die Spalten heißen 00, 01, 11, 10 – nicht 00, 01, 10, 11. Sonst sind Nachbarfelder keine Nachbarn mehr.
- Blöcke mit 3 oder 6 Feldern: Erlaubt sind nur Zweierpotenzen (1, 2, 4, 8, 16) in Rechteckform.
- Rand vergessen: Felder ganz links und ganz rechts (und oben/unten) sind benachbart, die vier Ecken bilden einen 4er-Block.
- Zu kleine Blöcke: Lieber einen 4er-Block als zwei 2er-Blöcke – je größer der Block, desto kürzer das Glied.
- Überflüssige Glieder: Ein Block, dessen Einsen schon alle in anderen Blöcken liegen, kann weg.
Die Grundlagen der Aussagenlogik (Junktoren, De Morgan, Normalformen) stehen unter Mengen und Logik. Die Felder des KV-Diagramms entsprechen den Bereichen eines Venn-Diagramms, Dualzahlen erklärt die Seite Zahlensysteme.
Wie aus XOR-, UND- und ODER-Gattern eine Schaltung wird, die Dualzahlen addiert, zeigt die Seite Halbaddierer und Volladdierer – mit Schaltern zum Ausprobieren.
Online üben
Gatter-Aufgaben beantwortest Du mit 0 oder 1. Bei „Glieder; Literale“ gibst Du zwei Zahlen an, z. B. 2; 4 für $(A \land \neg C) \lor (B \land C)$: zwei Glieder mit zusammen vier Variablen.
Stufe 2: KV-Diagramm mit drei Variablen
-
Aufgabe 1
\(f = \textstyle\sum m(0,\,4,\,6):\) Glieder; Literale?\(Glieder; Literale\)\(f = (\neg B \land \neg C) \lor (A \land \neg C)\ \ (2\) Glieder, \(4\) Literale\()\)
-
Aufgabe 2
\(f(A, B, C) = \neg B \lor (A \land C):\) Anzahl der Einsen?\(5\ \ (f = \textstyle\sum m(0,\,1,\,4,\,5,\,7))\)
-
Aufgabe 3
\(f = \textstyle\sum m(2,\,4,\,6,\,7):\) Glieder; Literale?\(Glieder; Literale\)\(f = (B \land \neg C) \lor (A \land \neg C) \lor (A \land B)\ \ (3\) Glieder, \(6\) Literale\()\)
-
Aufgabe 4
\(f(A, B, C) = (B \land \neg C) \lor (A \land \neg C):\) Anzahl der Einsen?\(3\ \ (f = \textstyle\sum m(2,\,4,\,6))\)
-
Aufgabe 5
\(f = \textstyle\sum m(1,\,2,\,3,\,5,\,6):\) Glieder; Literale?\(Glieder; Literale\)\(f = (B \land \neg C) \lor (\neg B \land C) \lor (\neg A \land C)\ \ (3\) Glieder, \(6\) Literale\()\)
-
Aufgabe 6
\(f = \textstyle\sum m(0,\,3,\,4,\,5,\,7):\) Glieder; Literale?\(Glieder; Literale\)\(f = (B \land C) \lor (\neg B \land \neg C) \lor (A \land C)\ \ (3\) Glieder, \(6\) Literale\()\)
Tippe Deine Lösung ein und klicke auf „Prüfen“ (oder drücke Enter). Brüche als 3/4, Dezimalzahlen mit Komma, mehrere Lösungen mit ; trennen, Potenzen als x^2, Wurzeln als sqrt(5). Punkte: 10 für richtig beim ersten Versuch, 6 nach einem Fehlversuch, 5 mit Tipp, 0 wenn Du Dir vorher die Lösung anschaust. Deine Punkte und Abzeichen siehst Du unter Mein Training.
Arbeitsblatt: Logikgatter und KV-Diagramme
Eine volle DIN-A4-Seite Aufgaben mit Lösungsblatt zum Ausdrucken – bei jedem Klick neue Aufgaben. Klasse 11–13.
Weiterlesen: Karnaugh-Veitch-Diagramm, Logikgatter bei Wikipedia