FISI // KV-Tafeln: digitale Schaltungen vereinfachen

Aus einer Wahrheitstabelle eine Schaltung zu bauen ist einfach: Du nimmst jede Zeile mit Ausgang 1, machst daraus einen UND-Term und verknüpfst alles mit ODER. Das Ergebnis ist die disjunktive Normalform. Sie stimmt immer, ist aber oft unnötig groß. Bei vier Eingängen und zehn Einsen landest du schnell bei zehn UND-Gattern mit je vier Eingängen plus einem riesigen ODER-Gatter.

Die KV-Tafel (Karnaugh-Veitch-Diagramm) ist das Werkzeug, mit dem du so eine Gleichung auf Papier vereinfachst, ohne seitenweise Boolesche Algebra umzuformen. In Klassenarbeiten zur Digitaltechnik ist sie Standard: Tafel ausfüllen, Gruppen einkreisen, Gleichung ablesen, Schaltung zeichnen.

Dieser Beitrag baut auf Logische Grundfunktionen & Normalformen auf. Wenn dir UND, ODER, NICHT und die DNF noch nicht sicher sitzen, lies den zuerst.

Ziel

Nach diesem Beitrag kannst du

• eine KV-Tafel für 2, 3 und 4 Eingänge aufbauen,
• Einsen aus einer Wahrheitstabelle oder einer Gleichung richtig eintragen,
• Gruppen nach den Regeln bilden, auch über den Rand hinweg,
• aus jeder Gruppe den vereinfachten Term ablesen,
• eine gegebene Schaltung über die KV-Tafel minimieren und dein Ergebnis mit PowerShell prüfen.

Die Idee hinter der KV-Tafel

Die Vereinfachung beruht auf einer einzigen Regel der Booleschen Algebra:

(A ∧ B) ∨ (A ∧ ¬B) = A ∧ (B ∨ ¬B) = A ∧ 1 = A

Wenn sich zwei UND-Terme nur in einer Variablen unterscheiden, und zwar so, dass sie einmal normal und einmal negiert vorkommt, dann ist diese Variable egal. Sie fällt weg.

Die KV-Tafel ordnet alle Zeilen der Wahrheitstabelle so in einem Raster an, dass benachbarte Felder sich immer in genau einer Variablen unterscheiden. Damit siehst du solche Paare sofort: Zwei Einsen nebeneinander bedeuten, dass eine Variable verschwindet. Vier Einsen in einem Block bedeuten, dass zwei Variablen verschwinden.

Aufbau der Tafel

Eine KV-Tafel hat so viele Felder, wie die Wahrheitstabelle Zeilen hat: 2ⁿ bei n Eingängen. Also 4 Felder bei zwei Eingängen, 8 bei drei und 16 bei vier.

Die Beschriftung folgt dem Gray-Code. Die Reihenfolge an der Kante ist 00, 01, 11, 10 und nicht 00, 01, 10, 11. Nur so ändert sich von Feld zu Feld genau ein Bit. Zwischen 01 und 10 würden sich zwei Bits ändern, und die Nachbarschaft wäre kaputt.

Zwei Eingänge

Drei Eingänge

Vier Eingänge

Die Zahlen in den Feldern sind die Zeilennummern der Wahrheitstabelle, wenn A das höchstwertige Bit ist. Feld 13 ist also ABCD = 1101. Du musst dir die Anordnung nicht auswendig merken. Es reicht, die Gray-Code-Reihenfolge an die Kanten zu schreiben, dann ergibt sich jedes Feld aus seiner Zeile und Spalte.

In vielen Schulunterlagen sieht die Tafel etwas anders aus: Statt 0 und 1 stehen Balken an den Kanten, die zeigen, in welchem Bereich eine Variable 1 ist (E₁) und wo sie negiert ist (Ē₁). Die Eingänge heißen dort oft E₀ bis E₃ statt A bis D. Das ist nur eine andere Schreibweise. Entscheidend ist in beiden Fällen, dass benachbarte Felder sich in genau einer Variablen unterscheiden. Halte dich in der Prüfung an die Darstellung, die dein Lehrer verwendet, und prüfe bei einer vorgegebenen Tafel zuerst die Beschriftung.

Das Verfahren in vier Schritten

1. Einsen eintragen: Jede Zeile der Wahrheitstabelle mit Ausgang 1 bekommt in ihrem Feld eine 1. Die übrigen Felder bleiben leer oder bekommen eine 0.
2. Gruppen bilden: Benachbarte Einsen werden zu Blöcken zusammengefasst.
3. Terme ablesen: Jede Gruppe ergibt einen UND-Term. Alle Terme werden mit ODER verknüpft.
4. Schaltung zeichnen: Pro Term ein UND-Gatter (oder ein einzelner Eingang, wenn der Term nur aus einer Variablen besteht), dazu ein ODER-Gatter am Ausgang.

Die Regeln für Gruppen

• Eine Gruppe enthält 1, 2, 4, 8 oder 16 Felder, also immer eine Zweierpotenz. Drei oder sechs Einsen in einer Gruppe sind nicht erlaubt.
• Gruppen sind Rechtecke oder Quadrate. L-Formen und Diagonalen gibt es nicht.
• Gruppen sollen so groß wie möglich sein. Je größer die Gruppe, desto kürzer der Term.
• Es sollen so wenige Gruppen wie möglich sein. Jede Gruppe kostet ein Gatter.
• Gruppen dürfen sich überschneiden. Eine 1 darf in mehreren Gruppen stecken, wenn sie dadurch eine größere Gruppe ermöglicht.
• Jede 1 muss in mindestens einer Gruppe liegen.
• Die Tafel ist an den Rändern verbunden. Die linke Spalte ist Nachbar der rechten, die obere Zeile Nachbar der unteren. Bei vier Eingängen sind auch die vier Ecken zusammen eine gültige Vierergruppe.

So liest du eine Gruppe ab

Schau, welche Variablen innerhalb der Gruppe ihren Wert behalten. Nur die kommen in den Term. Ist die Variable in der ganzen Gruppe 1, schreibst du sie normal, ist sie überall 0, schreibst du sie negiert. Variablen, die innerhalb der Gruppe wechseln, fallen weg.

Beispiel mit drei Eingängen

Gegeben ist diese Wahrheitstabelle:

Die DNF hätte fünf Terme mit je drei Variablen. Jetzt die Einsen in die Tafel:

Gruppe 1: Die vier Einsen in den Spalten 00 und 01 bilden ein Quadrat. Innerhalb dieses Blocks wechseln A und C, nur B bleibt überall 0. Ergebnis: ¬B.

Gruppe 2: Die 1 in Feld 7 (A=1, B=1, C=1) ist noch nicht abgedeckt. Ihr linker Nachbar ist Feld 5, das schon in Gruppe 1 steckt. Du darfst es trotzdem noch einmal verwenden. Im Paar aus Feld 5 und 7 wechselt B, A und C bleiben 1. Ergebnis: A ∧ C.

Y = ¬B ∨ (A ∧ C)

Statt fünf UND-Gattern mit drei Eingängen brauchst du jetzt einen Inverter, ein UND-Gatter mit zwei Eingängen und ein ODER-Gatter mit zwei Eingängen.

Beispiel mit vier Eingängen und Randgruppen

Ein Ausgang Y ist in den Zeilen 0, 2, 5, 6, 7, 8, 10, 13, 14 und 15 gleich 1. Das sind zehn Minterme. In der Tafel sieht das so aus:

Die vier Ecken: Die Felder 0, 2, 8 und 10 liegen auf den ersten Blick weit auseinander. Weil die Tafel an allen Rändern verbunden ist, bilden sie aber eine Vierergruppe. In allen vier Ecken ist B = 0 und D = 0, A und C wechseln. Ergebnis: ¬B ∧ ¬D.

Der Block in der Mitte: Die Felder 5, 7, 13 und 15 bilden ein Quadrat. Dort ist überall B = 1 und D = 1. Ergebnis: B ∧ D.

Der Block rechts: Übrig sind noch die Felder 6 und 14. Zusammen mit 7 und 15 ergibt das wieder ein Quadrat (Zeilen 01 und 11, Spalten 11 und 10). Hier gilt B = 1 und C = 1. Ergebnis: B ∧ C. Dass 7 und 15 schon im mittleren Block stecken, ist erlaubt und gewollt, sonst hättest du nur eine Zweiergruppe mit drei Variablen.

Y = (¬B ∧ ¬D) ∨ (B ∧ D) ∨ (B ∧ C)

Aus zehn UND-Termen mit je vier Variablen sind drei Terme mit je zwei Variablen geworden. Die Schaltung besteht aus drei UND-Gattern mit zwei Eingängen, einem ODER-Gatter mit drei Eingängen und den Invertern für B und D.

Rückwärts: eine gegebene Schaltung vereinfachen

Ein typischer Aufgabentyp läuft andersherum: Du bekommst eine fertige Schaltung und sollst sie vereinfachen. Der Weg ist immer gleich.

1. Funktionsgleichung der Schaltung aufstellen (jedes UND-Gatter ist ein Term, das ODER-Gatter verbindet sie).
2. Jeden Term in die KV-Tafel eintragen. Ein Term mit allen Variablen belegt genau ein Feld. Fehlt eine Variable im Term, belegt er mehrere Felder.
3. Gruppen bilden und neu ablesen.
4. Vereinfachte Schaltung zeichnen.

Übung: Eine Schaltung liefert

Y = (¬A ∧ B ∧ C) ∨ (A ∧ ¬B ∧ ¬C) ∨ (A ∧ ¬B ∧ C) ∨ (A ∧ B ∧ C)

Versuch es selbst, bevor du weiterliest.

Die vier Terme belegen die Felder 3, 4, 5 und 7:

Mögliche Paare sind 4+5 (A ∧ ¬B), 5+7 (A ∧ C) und 3+7 (B ∧ C). Wer alle drei nimmt, hat eine richtige, aber nicht minimale Lösung. Feld 4 lässt sich nur mit Feld 5 verbinden, Feld 3 nur mit Feld 7. Diese beiden Paare brauchst du also auf jeden Fall, und sie decken auch 5 und 7 schon ab. Das Paar 5+7 ist überflüssig.

Y = (A ∧ ¬B) ∨ (B ∧ C)

Merk dir dieses Vorgehen: Fang mit den Einsen an, die nur eine einzige Möglichkeit haben, und prüfe am Ende, ob jede Gruppe mindestens eine 1 enthält, die sonst niemand abdeckt. Eine Gruppe, auf die das nicht zutrifft, kann weg.

Wenn sich nichts vereinfachen lässt

Nicht jede Funktion wird kürzer. Liegen die Einsen wie auf einem Schachbrett, hat keine 1 eine benachbarte 1. Dann bleibt jede 1 eine Einzelgruppe, und die vereinfachte Gleichung ist identisch mit der DNF. Das klassische Beispiel ist XOR mit zwei Eingängen:

Auch einzelne verstreute Einsen in einer großen Tafel lassen sich nicht zusammenfassen. In der Prüfung ist „keine Vereinfachung möglich“ dann die richtige Antwort, du musst sie aber mit der Tafel begründen.

Don’t-Care-Felder

Manchmal gibt es Eingangskombinationen, die in der Praxis nie auftreten. Ein Beispiel ist eine Schaltung, die nur BCD-Ziffern 0 bis 9 verarbeitet: Die Kombinationen 1010 bis 1111 kommen nie vor. Solche Felder markierst du mit einem X (Don’t Care). Bei der Gruppenbildung darfst du ein X wie eine 1 behandeln, wenn die Gruppe dadurch größer wird, und es sonst ignorieren. Ein X muss nie abgedeckt werden.

Praxis: das Ergebnis mit PowerShell prüfen

In der Klassenarbeit hast du nur Papier. Beim Üben kannst du deine Lösung aber gegen die Wahrheitstabelle testen lassen. Das Skript geht alle 16 Kombinationen durch und vergleicht die vereinfachte Gleichung mit der Liste der Einsen, hier für das Beispiel mit vier Eingängen.

# Zeilen der Wahrheitstabelle, in denen der Ausgang Y = 1 ist
$einsen = 0, 2, 5, 6, 7, 8, 10, 13, 14, 15

# Die vereinfachte Gleichung aus der KV-Tafel als Scriptblock
# -not = NICHT, -and = UND, -or = ODER. Klammern setzen, weil -and und -or
# in PowerShell gleichrangig sind und einfach von links nach rechts laufen.
$vereinfacht = {
    param([bool]$A, [bool]$B, [bool]$C, [bool]$D)
    (-not $B -and -not $D) -or ($B -and $D) -or ($B -and $C)
}

$fehler = 0
foreach ($i in 0..15) {
    # Zeilennummer in die vier Eingänge zerlegen, A ist das höchstwertige Bit
    $A = [bool]($i -band 8)
    $B = [bool]($i -band 4)
    $C = [bool]($i -band 2)
    $D = [bool]($i -band 1)

    $soll = $einsen -contains $i
    $ist  = & $vereinfacht $A $B $C $D

    if ($soll -ne $ist) {
        $bits = [Convert]::ToString($i, 2).PadLeft(4, '0')
        Write-Host "Abweichung in Zeile $i (ABCD = $bits): soll $soll, ist $ist" -ForegroundColor Red
        $fehler++
    }
}

if ($fehler -eq 0) {
    Write-Host "Die vereinfachte Gleichung stimmt in allen 16 Zeilen." -ForegroundColor Green
}

Wenn du für drei Eingänge prüfen willst, nimm 0..7, entferne D und zerlege die Zeilennummer mit 4, 2 und 1. Lass zum Test ruhig einmal absichtlich eine Gruppe weg. Das Skript zeigt dir dann genau die Zeilen, die nicht mehr abgedeckt sind.

Stolperfallen

• Falsche Reihenfolge an der Kante: 00, 01, 10, 11 statt 00, 01, 11, 10. Dann sind die Nachbarschaften falsch, und du fasst Felder zusammen, die sich in zwei Variablen unterscheiden. Das ist der häufigste Fehler überhaupt.
• Gruppen mit drei oder sechs Feldern: Sieht nach einer schönen Gruppe aus, ist aber ungültig. Teile sie in zwei überlappende Zweier- oder Vierergruppen auf.
• Ränder vergessen: Einsen in der linken und rechten Spalte oder in den vier Ecken gehören oft zusammen. Wer nur im Inneren sucht, verschenkt große Gruppen.
• Zu kleine Gruppen aus Angst vor Überschneidung: Überlappen ist erlaubt. Eine 1 in zwei Gruppen ist kein Fehler, eine unnötig kleine Gruppe dagegen schon, weil sie einen längeren Term liefert.
• Überflüssige Gruppen: Jede Gruppe braucht mindestens eine 1, die nur sie abdeckt. Sonst ist das Ergebnis zwar richtig, aber nicht minimal, und das gibt Punktabzug.
• Negation falsch abgelesen: Ist eine Variable in der ganzen Gruppe 0, steht sie negiert im Term. Prüf das bei jeder Gruppe einzeln an den Kanten.
• Fremde Beschriftung übersehen: Bei vorgegebenen Tafeln mit Balken oder vertauschten Variablen erst die Kanten lesen, dann eintragen.
• Schaltung passt nicht zur Gleichung: Wenn ein Term nur aus einer einzelnen Variablen besteht, brauchst du dafür kein UND-Gatter. Die Leitung geht direkt ins ODER-Gatter, bei negierter Variable über einen Inverter.

Fazit

Die KV-Tafel ist eine grafische Abkürzung für die Regel (A ∧ B) ∨ (A ∧ ¬B) = A. Mit der Gray-Code-Beschriftung, den Gruppenregeln und etwas Übung beim Ablesen schaffst du jede Aufgabe mit bis zu vier Eingängen in wenigen Minuten. Am meisten bringt es, ein paar Tafeln selbst auszufüllen und das Ergebnis mit dem Skript zu kontrollieren, bis du die Randgruppen auf einen Blick siehst. Wer danach verstehen will, wie solche Schaltungen mit Zahlen rechnen, findet in Zahlensysteme umrechnen und im Beitrag zur Von-Neumann-Architektur die nächsten Bausteine.