Gymnasium OttweilerSkript zum MINT-Zweig
Logische SchaltungenKapitel 2

Kapitel 2

Logische Schaltungen und Aussagenlogik

Skript Informatik · Klasse 10 · MINT

Notebooks in diesem Kapitel DS15–DS22

Alle Notebooks der Klasse · Das grüne Schild an einer Überschrift zeigt, zu welchem Notebook der Abschnitt gehört.

PDF zum Ausdrucken zusammenstellen

Kreuze an, welche Abschnitte du brauchst. Die PDF hat dasselbe Aussehen wie das gedruckte Skript, mit Platz zum Schreiben. Jeden Abschnitt gibt es auch einzeln unter seiner Überschrift, das ganze Kapitel unten auf der Seite.

Jeder Computer rechnet am Ende mit nur zwei Zuständen: Strom an oder Strom aus, 1 oder 0. In diesem Kapitel siehst du, wie man aus ganz einfachen Bausteinen, den Gattern, Schaltungen baut, die Zahlen addieren und sich sogar ein Bit merken können. Danach lernst du die Aussagenlogik kennen: eine Schreibweise, mit der man solche Schaltungen genau beschreiben und vereinfachen kann. Eine einfachere Schaltung braucht weniger Bauteile, ist billiger und schneller.

Zum Ausprobieren der Schaltungen benutzt du den Online-Simulator CircuitVerse. Python brauchst du in diesem Kapitel nur als Hilfsmittel, um Ergebnisse nachzuprüfen.

Das erwartet dich in diesem Kapitel:

  1. Grundgatter und Belegungstabellen – die Bausteine UND, ODER, XOR und NICHT und wie man ihr Verhalten in Tabellen festhält.
  2. Schaltungen entwerfen – aus einer Beschreibung in Worten wird Schritt für Schritt eine Schaltung.
  3. Addition im Binärsystem und Halbaddierer – schriftlich rechnen mit 0 und 1 und die erste rechnende Schaltung.
  4. Volladdierer und Carry-Ripple-Addierer – wie ein Computer ganze Binärzahlen addiert.
  5. Das Flipflop – eine Schaltung, die sich durch Rückkopplung ein Bit merkt.
  6. Aussagenlogik – Schaltungen als Terme schreiben und als Termbaum darstellen.
  7. Äquivalenz und disjunktive Normalform – wann zwei Terme dasselbe leisten und wie man zu jeder Tabelle einen Term findet.
  8. KV-Diagramme – Terme vereinfachen, damit Schaltungen mit weniger Gattern auskommen.
So kannst du es sagen

Mit diesen Satzanfängen beschreibst und begründest du deine Ergebnisse in diesem Kapitel:

Am Ende hilft dir ein Rückblick mit den wichtigsten Begriffen und einem Kompetenz-Check beim Wiederholen.

2.1Grundgatter und Belegungstabellen DS15

Diesen Abschnitt als PDF (S. 2–19)

Das Jupyter-Notebook aus dem Unterricht: DS15_Grundgatter_Belegungstabellen.ipynb. Herunterladen und in VS Code oder Jupyter öffnen.

Leitidee

Ein Computer kennt in seinem Innersten nur zwei Zustände: Auf einer Leitung liegt Spannung an, oder es liegt keine Spannung an. Man schreibt dafür 1 und 0. Trotzdem kann ein Computer rechnen, vergleichen und Entscheidungen treffen. Möglich machen das winzige elektronische Bausteine, die Gatter. Jedes Gatter bekommt einen oder zwei Werte 0 oder 1 und liefert daraus nach einer festen Regel wieder eine 0 oder eine 1. Der amerikanische Mathematiker und Ingenieur Claude Shannon hat gezeigt, dass man mit solchen Schaltungen logisch denken und sogar rechnen kann. In diesem Abschnitt lernst du die vier Grundgatter kennen. In den nächsten Abschnitten baust du daraus eine Alarmanlage und ein Rechenwerk.

Lernziele

Nach diesem Abschnitt kannst du

2.1.1Nur zwei Zustände: 0 und 1

Denk an eine Taschenlampe. Der Schalter ist entweder aus oder an, die Lampe ist entweder dunkel oder hell. Einen dritten Zustand gibt es nicht. Genau so arbeitet die Elektronik in einem Computer. Jede Leitung hat zu jedem Zeitpunkt einen von zwei Werten: 0 (keine Spannung, „aus“, „falsch“) oder 1 (Spannung, „an“, „wahr“). Einen solchen Wert, der nur 0 oder 1 sein kann, nennt man ein Bit.

Eine logische Schaltung wandelt Eingangswerte in Ausgangswerte um. In den Zeichnungen gehen die Leitungen für die Eingänge links hinein, die Leitungen für die Ausgänge kommen rechts heraus. Die Eingänge bezeichnen wir mit Großbuchstaben wie AA, BB, CC, den Ausgang oft mit QQ.

Die kleinsten Bausteine einer logischen Schaltung heißen Gatter. Ein Gatter ist ein elektronisches Bauteil mit einem oder mehreren Eingängen und einem Ausgang. Welcher Wert am Ausgang herauskommt, hängt nur davon ab, welche Werte an den Eingängen anliegen. Vier Gatter sind so wichtig, dass man sie Grundgatter nennt: UND, ODER, XOR und NICHT. Oft verwendet man die englischen Namen AND, OR, XOR und NOT.

Definition: Grundgatter

Ein Gatter ist ein Baustein einer logischen Schaltung, der die Werte 0 oder 1 an seinen Eingängen nach einer festen Regel in einen Ausgangswert 0 oder 1 umwandelt. Die Grundgatter sind UND (AND), ODER (OR), XOR und NICHT (NOT).

So sehen Gatter aus

In deutschen Schulbüchern zeichnet man Gatter nach der Norm IEC 60617: Jedes Gatter ist ein Rechteck. Im Rechteck steht ein Kennzeichen, das die Regel des Gatters verrät, zum Beispiel & für UND. In diesem Skript werden alle Schaltungen so gezeichnet. Die Abbildung zeigt in der oberen Reihe die vier Grundgatter in dieser Form. Was die Kennzeichen bedeuten, erfährst du gleich bei den einzelnen Gattern.

Die vier Grundgatter: oben die IEC-Symbole (so zeichnest du sie im Heft und in Klassenarbeiten), unten die US-Symbole, die der Simulator CircuitVerse zeigt
Tipp: CircuitVerse zeigt andere Symbole

Zum Ausprobieren benutzt du den kostenlosen Online-Simulator CircuitVerse. Du findest ihn unter der Adresse circuitverse.org/simulator. CircuitVerse zeichnet die Gatter nicht nach IEC, sondern mit den in den USA üblichen Symbolen (Norm ANSI/IEEE): UND hat die Form eines „D“, ODER ist vorn spitz, XOR sieht aus wie ODER mit einem zusätzlichen Bogen, NICHT ist ein Dreieck mit einem kleinen Kreis an der Spitze (untere Reihe in der Abbildung).

Beide Schreibweisen bedeuten genau dasselbe, nur die Zeichnung ist anders. In CircuitVerse geht es nur um das Verhalten der Schaltung. Im Heft und in Klassenarbeiten verwendest du die IEC-Symbole.

2.1.2Das UND-Gatter (AND)

In einer Werkstatt steht eine Papierschneidemaschine. Damit niemand mit der Hand unter das Messer gerät, gibt es zwei Starttasten, eine links und eine rechts. Das Messer fährt nur herunter, wenn die linke Taste und die rechte Taste gedrückt sind. Ist auch nur eine Taste losgelassen, passiert nichts.

Genau diese Regel erfüllt das UND-Gatter: Sein Ausgang ist nur dann 1, wenn alle Eingänge 1 sind. Das Kennzeichen im Rechteck ist &, das Zeichen für „und“.

Mit zwei Eingängen gibt es genau vier Möglichkeiten, die Eingänge mit 0 und 1 zu belegen. Für jede dieser Belegungen schreibt man in einer Tabelle auf, welcher Wert am Ausgang herauskommt (rechts neben dem Symbol):

UND-Gatter: Die Eingänge A und B gehen links hinein, rechts kommt der Ausgang Q heraus
AA BB A∧BA \land B
0 0 0
0 1 0
1 0 0
1 1 1

Jede Zeile beschreibt einen Fall. Die dritte Zeile besagt zum Beispiel: Liegt an AA eine 1 und an BB eine 0 an, dann liefert das UND-Gatter eine 0. Nur in der letzten Zeile sind beide Eingänge 1, nur dort ist der Ausgang 1.

Über der Ausgangsspalte steht A∧BA \land B (gelesen: „A und B“). Das Zeichen ∧\land ist die mathematische Schreibweise für UND. Ein solcher Ausdruck heißt logischer Term. Er beschreibt, was die Schaltung mit den Eingängen macht. Die UND-Verknüpfung heißt in der Logik auch Konjunktion.

Belegungstabellen

Eine Tabelle wie die oben heißt Belegungstabelle (manchmal auch Wahrheitstabelle). Sie ist das wichtigste Werkzeug in diesem Kapitel, denn sie beschreibt das Verhalten einer Schaltung vollständig.

Definition: Belegungstabelle

Eine Belegungstabelle (Wahrheitstabelle) listet für jede mögliche Kombination von Eingangswerten den zugehörigen Ausgangswert auf.

Wie viele Zeilen braucht man? Jeder Eingang kann 0 oder 1 sein, hat also 2 Möglichkeiten. Bei einem Eingang gibt es 2 Zeilen. Bei zwei Eingängen kann man jede der 2 Möglichkeiten von AA mit jeder der 2 Möglichkeiten von BB kombinieren: 2⋅2=42 \cdot 2 = 4 Zeilen. Jeder weitere Eingang verdoppelt die Anzahl:

Anzahl der Eingänge nn 1 2 3 4 5
Anzahl der Belegungen 2n2^n 2 4 8 16 32

Damit du keinen Fall vergisst, schreibst du die Zeilen immer in derselben Reihenfolge auf. Fange mit lauter Nullen an. In der letzten Eingangsspalte wechseln sich 0 und 1 in jeder Zeile ab. In der Spalte davor wechseln sie alle 2 Zeilen, davor alle 4 Zeilen und so weiter. Die erste Spalte besteht also aus einer Hälfte Nullen und einer Hälfte Einsen. Die letzte Zeile besteht aus lauter Einsen.

Merke
Arbeitsauftrag 1: Zeilen zählen
  1. Wie viele Zeilen hat die Belegungstabelle einer Schaltung mit 3 Eingängen, wie viele bei 6 Eingängen?
  2. Schreibe die Eingangsspalten AA, BB, CC einer Belegungstabelle mit 3 Eingängen in der richtigen Reihenfolge auf.

Deine Antwort:

Lösung vergleichen
  1. Bei 3 Eingängen sind es 23=82^3 = 8 Zeilen, bei 6 Eingängen 26=642^6 = 64 Zeilen.
  2. In der Spalte CC wechseln 0 und 1 in jeder Zeile, in der Spalte BB alle zwei Zeilen, in der Spalte AA alle vier Zeilen:
AA BB CC
0 0 0
0 0 1
0 1 0
0 1 1
1 0 0
1 0 1
1 1 0
1 1 1

2.1.3Das ODER-Gatter (OR)

Im Auto geht die Innenbeleuchtung an, wenn die Fahrertür geöffnet ist oder die Beifahrertür geöffnet ist. Sie leuchtet natürlich auch, wenn beide Türen offen sind. Nur wenn beide Türen geschlossen sind, bleibt es dunkel.

Das ist die Regel des ODER-Gatters: Sein Ausgang ist 1, wenn mindestens ein Eingang 1 ist. Daher kommt das Kennzeichen ≥1 („größer oder gleich 1“): Mindestens eine 1 muss an den Eingängen anliegen. Überlege zuerst selbst, wie die Belegungstabelle aussieht. Lies dann weiter.

ODER-Gatter: Das Kennzeichen \geq 1 bedeutet „mindestens ein Eingang ist 1“
AA BB A∨BA \lor B
0 0 0
0 1 1
1 0 1
1 1 1

Das Zeichen ∨\lor steht für ODER; A∨BA \lor B liest man „A oder B“. Die ODER-Verknüpfung heißt in der Logik auch Disjunktion.

Stolperstein

Im Alltag bedeutet „oder“ oft „das eine oder das andere, aber nicht beides“: „Willst du Tee oder Kaffee?“ Das logische ODER ist anders. Es liefert auch dann eine 1, wenn beide Eingänge 1 sind (letzte Zeile der Tabelle). Wenn du in einer Aufgabe „oder“ liest, überlege genau, ob „beides“ erlaubt sein soll.

2.1.4Das XOR-Gatter

Für das „entweder … oder“ gibt es ein eigenes Gatter: das XOR-Gatter. XOR ist die Abkürzung für exclusive or, auf Deutsch „ausschließendes Oder“ oder Exklusiv-Oder. Sein Ausgang ist 1, wenn die beiden Eingänge unterschiedlich sind, also wenn genau einer der beiden Eingänge 1 ist. Das Kennzeichen =1 bedeutet: Es muss genau eine 1 anliegen.

Ein Beispiel aus dem Alltag ist die Flurbeleuchtung mit zwei Schaltern, einem an jedem Ende des Flurs. Man stellt die Schaltung so ein, dass das Licht aus ist, wenn beide Schalter unten stehen. Kippt man einen der beiden Schalter um, geht das Licht an. Kippt man danach auch den anderen um, geht es wieder aus. Das Licht brennt also genau dann, wenn die beiden Schalter unterschiedlich stehen.

XOR-Gatter: Das Kennzeichen =1 bedeutet „genau ein Eingang ist 1“
AA BB A⊕BA \oplus B
0 0 0
0 1 1
1 0 1
1 1 0

Das Zeichen ⊕\oplus steht für XOR. Vergleiche die Tabelle mit der Tabelle des ODER-Gatters: Nur die letzte Zeile ist anders. Wenn beide Eingänge 1 sind, liefert ODER eine 1, XOR aber eine 0.

2.1.5Das NICHT-Gatter (NOT)

Das NICHT-Gatter hat nur einen Eingang. Es dreht den Wert einfach um: Aus 0 wird 1, aus 1 wird 0. Sein Ausgang ist also immer das Gegenteil des Eingangs. Man nennt das auch Negation (Verneinung). Ein Beispiel ist das Licht im Kühlschrank: Es ist an, wenn die Tür nicht geschlossen ist.

Im IEC-Symbol steht eine 1 im Rechteck, denn das Gatter gibt den einen Eingangswert weiter. Dass der Wert umgedreht wird, zeigt ein kleiner Kreis direkt am Ausgang. In manchen Büchern steht an seiner Stelle ein kleiner Schrägstrich. Beide Zeichen bedeuten dasselbe: Der Wert wird verneint.

NICHT-Gatter: Der kleine Kreis am Ausgang zeigt, dass der Eingangswert umgedreht wird
AA ¬A\lnot A
0 1
1 0

Das Zeichen ¬\lnot steht für NICHT; ¬A\lnot A liest man „nicht A“.

2.1.6Die Grundgatter im Überblick

Die folgende Tabelle fasst die vier Grundgatter zusammen. Lerne sie auswendig. Du brauchst sie in allen weiteren Abschnitten dieses Kapitels.

Merke
Gatter IEC-Symbol Verhalten
UND (AND, Konjunktion) & Ausgang ist 1, wenn alle Eingänge 1 sind.
ODER (OR, Disjunktion) ≥1 Ausgang ist 1, wenn mindestens ein Eingang 1 ist.
XOR (Exklusiv-Oder) =1 Ausgang ist 1, wenn die Eingänge unterschiedlich sind.
NICHT (NOT, Negation) 1 mit Kreis am Ausgang Ausgang ist das Gegenteil des Eingangs.
So kannst du es sagen

So beschreibst du ein Gatter in Fachsprache – vom einfachen zum genauen Satz:

Arbeitsauftrag 2: Grundgatter skizzieren

Skizziere die vier Grundgatter UND, ODER, XOR und NICHT mit ihren IEC-Symbolen. Beschrifte jeweils die Eingänge mit AA und BB (beim NICHT-Gatter nur AA) und den Ausgang mit QQ. Schreibe unter jedes Gatter seinen Namen und in einem kurzen Satz, wann sein Ausgang 1 ist.

Tipp

Skizzieren heißt: einen Sachverhalt auf das Wesentliche reduzieren und grafisch oder sprachlich darstellen. Du brauchst also kein Lineal und keine schöne Zeichnung. Wichtig sind das Rechteck, das richtige Kennzeichen, der Kreis beim NICHT-Gatter und die beschrifteten Leitungen.

Deine Skizze:

Lösung vergleichen
Die vier Grundgatter mit beschrifteten Ein- und Ausgängen
  • UND (&): QQ ist 1, wenn AA und BB beide 1 sind.
  • ODER (≥1): QQ ist 1, wenn mindestens einer der Eingänge 1 ist.
  • XOR (=1): QQ ist 1, wenn AA und BB unterschiedlich sind.
  • NICHT (1 mit Kreis am Ausgang): QQ ist das Gegenteil von AA.

Typische Fehler: beim ODER-Gatter nur 1 statt ≥1 schreiben (das wäre dann kein ODER), beim NICHT-Gatter den Kreis am Ausgang vergessen.

2.1.7Gatter in CircuitVerse ausprobieren

Im Simulator CircuitVerse kannst du Schaltungen am Bildschirm zusammenstecken und testen. Du brauchst nur einen Browser. Ein Login ist nicht nötig, aber praktisch: Dann kannst du deine Schaltungen speichern und später weiterbearbeiten. So baust du ein einzelnes Gatter auf:

  1. Öffne die Seite circuitverse.org/simulator.
  2. Im linken Bereich findest du unter Input den Baustein Input. Das ist ein Schalter, der 0 oder 1 liefert. Ziehe zwei davon ins Arbeitsfeld.
  3. Unter Output findest du den Baustein Output. Er zeigt den Wert an, der bei ihm ankommt (bei einer Lampe: leuchtet = 1). Ziehe einen davon ins Arbeitsfeld.
  4. Unter Gates findest du AND, OR, XOR und NOT. Ziehe ein Gatter zwischen die Schalter und die Anzeige.
  5. Verbinde die Bausteine mit Leitungen: Klicke auf einen Anschluss, halte die Maustaste gedrückt und ziehe zum anderen Anschluss.
  6. Klicke auf einen Input-Schalter. Er wechselt zwischen 0 und 1. Beobachte, was die Anzeige am Ausgang zeigt.
Arbeitsauftrag 3: Alle vier Grundgatter testen

Baue in CircuitVerse nacheinander je eine Schaltung mit einem AND-, einem OR-, einem XOR- und einem NOT-Gatter (beim NOT-Gatter reicht ein Eingang). Teste alle Eingangskombinationen und trage deine Beobachtungen in die Tabellen ein. Vergleiche danach mit den Tabellen weiter vorn in diesem Abschnitt.

AA BB Ausgang AND Ausgang OR Ausgang XOR
0 0
0 1
1 0
1 1
AA Ausgang NOT
0
1
Lösung vergleichen
AA BB AND OR XOR
0 0 0 0 0
0 1 0 1 1
1 0 0 1 1
1 1 1 1 0
AA NOT
0 1
1 0

Wenn deine Beobachtung in CircuitVerse anders aussieht, prüfe zuerst die Leitungen: Ist jeder Schalter wirklich mit einem Eingang des Gatters verbunden? Ein Eingang ohne Leitung hat keinen festen Wert.

2.1.8Belegungstabellen mit Python nachprüfen

Belegungstabellen kannst du auch mit Python erzeugen und so deine Ergebnisse kontrollieren. Python kennt die logischen Operatoren and, or und not schon. Für XOR gibt es keinen eigenen Operator, aber der Vergleich != („ungleich“) tut genau das Richtige: a != b ist wahr, wenn a und b unterschiedlich sind.

Werkzeug

Python behandelt die Zahl 0 wie False und die Zahl 1 wie True. Du kannst deshalb and, or und not direkt auf die Werte 0 und 1 anwenden. Das Ergebnis ist manchmal eine Zahl und manchmal ein Wahrheitswert. Damit am Ende immer 0 oder 1 herauskommt, wandeln wir es mit int(...) um: int(True) ergibt 1, int(False) ergibt 0.

Für jedes Gatter schreiben wir eine Funktion. Zwei ineinander geschachtelte for-Schleifen gehen alle vier Belegungen von a und b durch:

def und(a, b):
    return int(a and b)

def oder(a, b):
    return int(a or b)

def xor(a, b):
    return int(a != b)

print("A B | UND ODER XOR")
for a in [0, 1]:
    for b in [0, 1]:
        print(f"{a} {b} |  {und(a, b)}   {oder(a, b)}   {xor(a, b)}")
A B | UND ODER XOR
0 0 |  0   0   0
0 1 |  0   1   1
1 0 |  0   1   1
1 1 |  1   1   0

Das NICHT-Gatter hat nur einen Eingang. Hier genügt eine Schleife:

def nicht(a):
    return int(not a)

for a in [0, 1]:
    print(a, "->", nicht(a))
0 -> 1
1 -> 0

2.1.9Schaltungen aus mehreren Gattern

Ein einzelnes Gatter kann nicht viel. Spannend wird es, wenn man Gatter hintereinanderschaltet: Der Ausgang eines Gatters wird zum Eingang des nächsten. Die folgende Schaltung hat drei Eingänge AA, BB, CC und einen Ausgang ZZ.

Eine Schaltung aus drei Gattern. Sie berechnet den Term (A \land \lnot B) \lor C

Um die Belegungstabelle aufzustellen, gehst du die Schaltung von links nach rechts durch, Gatter für Gatter. Für jede Zwischenleitung legst du eine eigene Spalte an. Solche Spalten heißen Hilfsspalten.

  1. Das NICHT-Gatter dreht BB um. Die erste Hilfsspalte ist ¬B\lnot B.
  2. Das UND-Gatter verknüpft AA mit dem Ausgang des NICHT-Gatters. Die zweite Hilfsspalte ist A∧¬BA \land \lnot B. Sie ist nur dort 1, wo AA und ¬B\lnot B beide 1 sind.
  3. Das ODER-Gatter verknüpft diese Leitung mit CC. Das ergibt den Ausgang Z=(A∧¬B)∨CZ = (A \land \lnot B) \lor C. Er ist 1, wo die zweite Hilfsspalte oder CC eine 1 enthält.
AA BB CC ¬B\lnot B A∧¬BA \land \lnot B (A∧¬B)∨C(A \land \lnot B) \lor C
0 0 0 1 0 0
0 0 1 1 0 1
0 1 0 0 0 0
0 1 1 0 0 1
1 0 0 1 1 1
1 0 1 1 1 1
1 1 0 0 0 0
1 1 1 0 0 1

Lies zur Kontrolle eine Zeile in Worten: Die fünfte Zeile besagt, dass zu der Belegung A=1A = 1, B=0B = 0, C=0C = 0 der Ausgangswert Z=1Z = 1 gehört. Das stimmt: ¬B\lnot B ist 1, also ist auch A∧¬BA \land \lnot B gleich 1, und damit ist das ODER-Gatter erfüllt.

Merke

Zu einer Schaltung aus mehreren Gattern erstellt man die Belegungstabelle von links nach rechts: Für den Ausgang jedes Gatters legt man eine Hilfsspalte an und berechnet sie aus den Spalten, die schon da sind.

Stolperstein

Der häufigste Fehler bei Belegungstabellen ist, eine Zeile auszulassen oder doppelt zu schreiben. Halte dich deshalb immer an die feste Reihenfolge der Zeilen (letzte Eingangsspalte wechselt in jeder Zeile). Zähle am Ende nach: Bei 3 Eingängen müssen es genau 8 Zeilen sein.

Arbeitsauftrag 4: Belegungstabelle zu einer Schaltung

Erstelle die Belegungstabelle zur folgenden Schaltung. Fülle dazu die Hilfsspalten von links nach rechts aus. Mit welchem Grundgatter stimmt die letzte Spalte überein?

Schaltung mit zwei Eingängen und vier Gattern
AA BB A∨BA \lor B A∧BA \land B ¬(A∧B)\lnot (A \land B) QQ
0 0
0 1
1 0
1 1

Die letzte Spalte stimmt überein mit:

Lösung vergleichen

Die Schaltung berechnet Q=(A∨B)∧¬(A∧B)Q = (A \lor B) \land \lnot (A \land B):

AA BB A∨BA \lor B A∧BA \land B ¬(A∧B)\lnot (A \land B) (A∨B)∧¬(A∧B)(A \lor B) \land \lnot (A \land B)
0 0 0 0 1 0
0 1 1 0 1 1
1 0 1 0 1 1
1 1 1 1 0 0

Die letzte Spalte ist genau die Spalte des XOR-Gatters. Das passt zur Bedeutung: „mindestens eine 1 (A∨BA \lor B), aber nicht beide (¬(A∧B)\lnot (A \land B))“ heißt „genau eine 1“. Ein XOR-Gatter lässt sich also aus UND, ODER und NICHT zusammensetzen.

Arbeitsauftrag 5: Mehrheitsschaltung

Baue in CircuitVerse eine Schaltung mit drei Eingängen AA, BB, CC, die genau dann 1 ausgibt, wenn mindestens zwei der drei Eingänge 1 sind (Mehrheitsentscheidung, englisch majority). Verwende dafür mehrere AND- und OR-Gatter.

  1. Fülle die Belegungstabelle aus.
  2. Skizziere die Schaltung mit IEC-Symbolen.
  3. Teste deine Schaltung in CircuitVerse mit allen acht Belegungen.

Tipp: Die Schaltung lässt sich als (A∧B)∨(B∧C)∨(A∧C)(A \land B) \lor (B \land C) \lor (A \land C) beschreiben: Entweder sind AA und BB beide 1, oder BB und CC, oder AA und CC. In CircuitVerse kannst du beim OR-Gatter die Anzahl der Eingänge auf 3 stellen oder zwei OR-Gatter hintereinanderschalten.

AA BB CC A∧BA \land B B∧CB \land C A∧CA \land C QQ
0 0 0
0 0 1
0 1 0
0 1 1
1 0 0
1 0 1
1 1 0
1 1 1

Deine Skizze:

Lösung vergleichen
AA BB CC A∧BA \land B B∧CB \land C A∧CA \land C QQ
0 0 0 0 0 0 0
0 0 1 0 0 0 0
0 1 0 0 0 0 0
0 1 1 0 1 0 1
1 0 0 0 0 0 0
1 0 1 0 0 1 1
1 1 0 1 0 0 1
1 1 1 1 1 1 1
Mehrheitsschaltung: Jedes UND-Gatter prüft ein Paar von Eingängen, das ODER-Gatter fasst die drei Ergebnisse zusammen

Wichtig: Jeder Eingang wird für zwei UND-Gatter gebraucht. Die Leitungen verzweigen sich deshalb. An jeder Verzweigung steht ein Punkt. Wo sich zwei Leitungen nur kreuzen, steht kein Punkt.

Kontrolle mit Python:

def mehrheit(a, b, c):
    return int((a and b) or (b and c) or (a and c))

for a in [0, 1]:
    for b in [0, 1]:
        for c in [0, 1]:
            print(a, b, c, "->", mehrheit(a, b, c))
0 0 0 -> 0
0 0 1 -> 0
0 1 0 -> 0
0 1 1 -> 1
1 0 0 -> 0
1 0 1 -> 1
1 1 0 -> 1
1 1 1 -> 1

Für drei Eingänge braucht man drei ineinander geschachtelte Schleifen. Die Zeilen erscheinen wieder in der üblichen Reihenfolge.

2.1.10Übungen

Arbeitsauftrag 6: Welches Gatter ist das?

Zu vier unbekannten Gattern mit den Eingängen AA und BB wurden die Ausgangswerte Q1Q_1 bis Q4Q_4 gemessen. Gib jeweils an, um welches Gatter es sich handelt. Eine der vier Spalten passt zu keinem Grundgatter. Begründe, woran du das erkennst.

AA BB Q1Q_1 Q2Q_2 Q3Q_3 Q4Q_4
0 0 0 0 0 1
0 1 1 0 1 1
1 0 1 0 1 1
1 1 1 1 0 0

Deine Antwort:

Lösung vergleichen
  • Q1Q_1 ist nur bei 0 0 eine 0, sonst 1: ODER.
  • Q2Q_2 ist nur bei 1 1 eine 1: UND.
  • Q3Q_3 ist 1, wenn die Eingänge unterschiedlich sind: XOR.
  • Q4Q_4 ist genau das Gegenteil von Q2Q_2, also das Gegenteil von UND. Das ist kein Grundgatter, sondern ein UND-Gatter mit einem NICHT-Gatter dahinter: Q4=¬(A∧B)Q_4 = \lnot (A \land B).

Am schnellsten erkennst du ein Gatter an der ersten und der letzten Zeile: Bei 0 0 liefern UND, ODER und XOR eine 0. Bei 1 1 unterscheiden sich ODER (1) und XOR (0).

2.1.11Weitere Übungen

Hier kannst du das Gelernte weiter üben. Die Punkte im Titel zeigen, wie schwer eine Aufgabe ist: ●○○ leicht, ●●○ mittel, ●●● knifflig. Fang mit den leichten an.

Arbeitsauftrag 7: Gatter erkennen ●○○

Die Abbildung zeigt vier Gatter in IEC-Darstellung. Nenne zu jedem Gatter den Namen und beschreibe in einem kurzen Satz, wann sein Ausgang 1 ist.

Vier Gatter, durchnummeriert von (1) bis (4)

Deine Antwort:

Lösung vergleichen
  1. XOR (Kennzeichen =1): Der Ausgang ist 1, wenn die beiden Eingänge unterschiedlich sind.
  2. UND (Kennzeichen &): Der Ausgang ist 1, wenn alle Eingänge 1 sind.
  3. NICHT (Kennzeichen 1 mit Kreis am Ausgang): Der Ausgang ist das Gegenteil des Eingangs.
  4. ODER (Kennzeichen ≥1): Der Ausgang ist 1, wenn mindestens ein Eingang 1 ist.

Achte auf das Kennzeichen im Rechteck. =1 und ≥1 werden leicht verwechselt: =1 heißt „genau eine 1“, ≥1 heißt „mindestens eine 1“.

Arbeitsauftrag 8: Ausgang bestimmen ●○○

Bestimme für jede Zeile den Ausgangswert des Gatters. Beim NICHT-Gatter gibt es nur den Eingang AA.

Gatter AA BB Ausgang
UND 1 0
ODER 1 0
XOR 1 0
UND 1 1
ODER 1 1
XOR 1 1
ODER 0 0
NICHT 1 –
Lösung vergleichen
Gatter AA BB Ausgang
UND 1 0 0
ODER 1 0 1
XOR 1 0 1
UND 1 1 1
ODER 1 1 1
XOR 1 1 0
ODER 0 0 0
NICHT 1 – 0

Der häufigste Fehler steckt in der Zeile XOR mit A=1A = 1, B=1B = 1: Die Eingänge sind gleich, deshalb liefert XOR eine 0. Das ODER-Gatter liefert dagegen eine 1.

Arbeitsauftrag 9: Gatter im Alltag ●○○

Gib zu jeder Situation das passende Grundgatter an. Begründe kurz.

  1. Ein Handy lässt sich entsperren, wenn der Fingerabdruck erkannt wird oder die richtige PIN eingegeben wird.
  2. Ein Online-Spiel startet nur, wenn du eingeloggt bist und das Internet verbunden ist.
  3. Bei einem Quiz hat jedes der beiden Teams einen Buzzer. Die Lampe „Antwort“ leuchtet, wenn genau ein Team gedrückt hat. Drücken beide gleichzeitig, bleibt sie aus.
  4. Die Warnleuchte am Wasserkocher leuchtet, wenn kein Wasser im Kocher ist. (Eingang: 1 = Wasser ist im Kocher.)

Deine Antwort:

Lösung vergleichen
  1. ODER: Eines von beiden genügt. Wenn Fingerabdruck und PIN beide stimmen, wird das Handy natürlich auch entsperrt.
  2. UND: Beide Bedingungen müssen erfüllt sein.
  3. XOR: Die Lampe leuchtet nur, wenn die beiden Eingänge unterschiedlich sind. Bei zwei gedrückten Buzzern bleibt sie aus. Das unterscheidet XOR von ODER.
  4. NICHT: Die Leuchte zeigt das Gegenteil des Eingangs. Ist Wasser im Kocher (1), ist sie aus (0).
Arbeitsauftrag 10: Welche Zeile fehlt? ●○○

Bei dieser Belegungstabelle für drei Eingänge fehlt eine Zeile.

  1. Gib an, wie viele Zeilen die Tabelle haben muss.
  2. Bestimme die fehlende Belegung und gib an, an welcher Stelle sie eingefügt werden muss.
AA BB CC
0 0 0
0 0 1
0 1 0
0 1 1
1 0 0
1 1 0
1 1 1

Deine Antwort:

Lösung vergleichen
  1. Bei 3 Eingängen gibt es 23=82^3 = 8 Belegungen, also 8 Zeilen. Hier sind es nur 7.
  2. Es fehlt die Belegung A=1A = 1, B=0B = 0, C=1C = 1. Sie gehört zwischen die Zeilen 1 0 0 und 1 1 0.

So findest du die Lücke schnell: In der Spalte CC müssen sich 0 und 1 in jeder Zeile abwechseln. Nach 1 0 0 steht aber wieder eine 0 in der Spalte CC.

Arbeitsauftrag 11: Zwei kleine Schaltungen ●●○

Erstelle zu beiden Schaltungen die Belegungstabelle. Fülle die Hilfsspalten aus. Beschreibe danach in Worten, wann Q2=1Q_2 = 1 ist.

Links Schaltung a) mit dem Ausgang Q_1, rechts Schaltung b) mit dem Ausgang Q_2
AA BB ¬A\lnot A Q1Q_1 A⊕BA \oplus B Q2Q_2
0 0
0 1
1 0
1 1

Deine Beschreibung:

Lösung vergleichen

Schaltung a) berechnet Q1=¬A∧BQ_1 = \lnot A \land B, Schaltung b) berechnet Q2=¬(A⊕B)Q_2 = \lnot (A \oplus B):

AA BB ¬A\lnot A Q1=¬A∧BQ_1 = \lnot A \land B A⊕BA \oplus B Q2=¬(A⊕B)Q_2 = \lnot (A \oplus B)
0 0 1 0 0 1
0 1 1 1 1 0
1 0 0 0 1 0
1 1 0 0 0 1

Q1Q_1 ist nur bei A=0A = 0, B=1B = 1 gleich 1. Q2Q_2 ist das Gegenteil von XOR: Q2Q_2 ist 1, wenn die beiden Eingänge gleich sind. Die Schaltung b) prüft also, ob AA und BB übereinstimmen.

Typischer Fehler bei a): das NICHT-Gatter übersehen und einfach A∧BA \land B ausrechnen. Rechne immer zuerst die Hilfsspalte ¬A\lnot A aus.

Arbeitsauftrag 12: Eine Schaltung mit drei Eingängen ●●○

Erstelle die Belegungstabelle zur folgenden Schaltung. Gib danach alle Belegungen an, für die Q=1Q = 1 ist.

Schaltung mit drei Eingängen: ein ODER-Gatter und ein UND-Gatter
AA BB CC A∨BA \lor B QQ
0 0 0
0 0 1
0 1 0
0 1 1
1 0 0
1 0 1
1 1 0
1 1 1

Deine Antwort:

Lösung vergleichen

Die Schaltung berechnet Q=(A∨B)∧CQ = (A \lor B) \land C:

AA BB CC A∨BA \lor B Q=(A∨B)∧CQ = (A \lor B) \land C
0 0 0 0 0
0 0 1 0 0
0 1 0 1 0
0 1 1 1 1
1 0 0 1 0
1 0 1 1 1
1 1 0 1 0
1 1 1 1 1

Q=1Q = 1 gilt bei den Belegungen 0 1 1, 1 0 1 und 1 1 1. In Worten: CC muss 1 sein, und außerdem muss mindestens einer der Eingänge AA, BB eine 1 haben.

Arbeitsauftrag 13: Kontrolle mit Python ●●○

Überprüfe deine Tabellen aus den Aufträgen Zwei kleine Schaltungen und Eine Schaltung mit drei Eingängen mit Python. Schreibe für jede der drei Schaltungen eine Funktion (q1(a, b), q2(a, b) und q3(a, b, c)), die 0 oder 1 zurückgibt. Gib die Belegungstabellen mit geschachtelten for-Schleifen aus.

Tipp

XOR schreibst du in Python als a != b. Ein NICHT-Gatter hinter dem XOR-Gatter wird dann zu not (a != b). Die Klammern sind wichtig, damit not sich auf das ganze Ergebnis bezieht.

Lösung vergleichen
def q1(a, b):
    return int(not a and b)

def q2(a, b):
    return int(not (a != b))

def q3(a, b, c):
    return int((a or b) and c)

print("A B -> Q1 Q2")
for a in [0, 1]:
    for b in [0, 1]:
        print(a, b, "->", q1(a, b), " ", q2(a, b))

print("A B C -> Q")
for a in [0, 1]:
    for b in [0, 1]:
        for c in [0, 1]:
            print(a, b, c, "->", q3(a, b, c))
A B -> Q1 Q2
0 0 -> 0   1
0 1 -> 1   0
1 0 -> 0   0
1 1 -> 0   1
A B C -> Q
0 0 0 -> 0
0 0 1 -> 0
0 1 0 -> 0
0 1 1 -> 1
1 0 0 -> 0
1 0 1 -> 1
1 1 0 -> 0
1 1 1 -> 1

not a and b bedeutet in Python dasselbe wie die Schaltung a): Das not gilt nur für a. In q3 sind die Klammern um a or b nötig, denn sonst würde Python zuerst b and c ausrechnen.

Arbeitsauftrag 14: Zwei XOR-Gatter hintereinander ●●●

In der folgenden Schaltung ist der Ausgang eines XOR-Gatters mit einem zweiten XOR-Gatter verbunden.

  1. Erstelle die Belegungstabelle mit der Hilfsspalte A⊕BA \oplus B.
  2. Zähle in jeder Zeile, wie viele der drei Eingänge 1 sind, und trage die Anzahl in die Spalte „Einsen“ ein. Beschreibe damit in einem Satz, wann Q=1Q = 1 ist.
Zwei XOR-Gatter hintereinander
AA BB CC A⊕BA \oplus B QQ Einsen
0 0 0
0 0 1
0 1 0
0 1 1
1 0 0
1 0 1
1 1 0
1 1 1

Deine Beschreibung:

Lösung vergleichen
AA BB CC A⊕BA \oplus B Q=(A⊕B)⊕CQ = (A \oplus B) \oplus C Einsen
0 0 0 0 0 0
0 0 1 0 1 1
0 1 0 1 1 1
0 1 1 1 0 2
1 0 0 1 1 1
1 0 1 1 0 2
1 1 0 0 0 2
1 1 1 0 1 3

QQ ist 1, wenn eine ungerade Anzahl der Eingänge 1 ist, also genau eine oder alle drei. Bei null oder zwei Einsen ist Q=0Q = 0.

Achtung, die letzte Zeile: A⊕BA \oplus B ist 0, weil AA und BB gleich sind. Das zweite XOR-Gatter bekommt also 0 und 1 und liefert Q=1Q = 1. Wer hier „XOR heißt genau eine 1“ auf alle drei Eingänge anwendet, bekommt fälschlich eine 0.

2.1.12Das Wichtigste in Kürze

Selbstcheck

2.2Schaltungen entwerfen: vom Text zur Schaltung DS16

Diesen Abschnitt als PDF (S. 20–31)

Das Jupyter-Notebook aus dem Unterricht: DS16_Entwurf_Schaltungen.ipynb. Herunterladen und in VS Code oder Jupyter öffnen.

Leitidee

Im letzten Abschnitt hast du Schaltungen untersucht, die schon fertig gezeichnet waren. Jetzt drehst du den Spieß um: Du bekommst eine Beschreibung in Worten, zum Beispiel „Die Alarmanlage soll losgehen, wenn …“, und entwirfst selbst die passende Schaltung. Genau so arbeiten Ingenieurinnen und Ingenieure, wenn sie die Steuerung für eine Alarmanlage, einen Fahrstuhl oder eine Waschmaschine bauen. Damit dabei nichts schiefgeht, gehst du immer in denselben Schritten vor: von der Beschreibung über die Belegungstabelle zum Term und zur Schaltung. Am Ende testest du die Schaltung im Simulator.

Lernziele

Nach diesem Abschnitt kannst du

2.2.1Das Vorgehen beim Schaltungsentwurf

Eine Anforderung in Worten ist oft ungenau. Bevor du Gatter zeichnest, übersetzt du sie deshalb Schritt für Schritt in eine genaue Form. Die Belegungstabelle ist dabei das Herzstück: Sie legt für jeden möglichen Fall fest, was die Schaltung tun soll.

Merke

Beim Schaltungsentwurf übersetzt man eine Anforderung in Textform zunächst in eine Belegungstabelle, danach in eine passende Gatterkombination. Vorgehen:

  1. Eingangs- und Ausgangsgrößen benennen (und festlegen, was 0 und 1 jeweils bedeuten).
  2. Belegungstabelle aufstellen: alle Fälle durchgehen und markieren, in welchen der Ausgang 1 sein soll.
  3. Passende Gatter auswählen und verschalten. Dabei hilft ein logischer Term.
  4. Schaltung testen: alle Belegungen durchprobieren und mit der Tabelle vergleichen.

Bei Schritt 3 hilft dir die Sprache der Aufgabe. Die Wörter „und“, „oder“ und „nicht“ in der Beschreibung passen oft direkt zu den Gattern UND, ODER und NICHT. Ob das wirklich stimmt, prüfst du immer an der Belegungstabelle.

2.2.2Beispiel: eine Alarmanlage

Eine Alarmanlage soll auslösen, wenn die Tür geöffnet ist und die Anlage scharfgeschaltet ist, oder wenn der Rauchmelder anschlägt. Bei Rauch soll der Alarm also immer losgehen, egal ob die Anlage scharfgeschaltet ist oder nicht.

Schritt 1: Eingänge und Ausgang benennen

Lies den Text und frage dich: Welche Informationen bekommt die Anlage? Das sind die Eingänge. Was soll sie tun? Das ist der Ausgang. Für jede Größe legst du fest, was 0 und was 1 bedeutet.

Größe Art Bedeutung von 1 Bedeutung von 0
Tür Eingang Tür ist geöffnet Tür ist geschlossen
Scharf Eingang Anlage ist scharfgeschaltet Anlage ist aus
Rauch Eingang Rauchmelder schlägt an kein Rauch
Alarm Ausgang Alarm wird ausgelöst kein Alarm

Die Schaltung hat also drei Eingänge und einen Ausgang.

Schritt 2: Belegungstabelle aufstellen

Drei Eingänge bedeuten 23=82^3 = 8 Zeilen. Schreibe die Eingangsspalten in der gewohnten Reihenfolge auf. Gehe dann jede Zeile durch und frage: Soll hier Alarm sein? Die Hilfsspalte für „Tür offen und scharf“ macht das leichter.

Tür Scharf Rauch Tür∧Scharf\text{Tür} \land \text{Scharf} Alarm
0 0 0 0 0
0 0 1 0 1
0 1 0 0 0
0 1 1 0 1
1 0 0 0 0
1 0 1 0 1
1 1 0 1 1
1 1 1 1 1

Lies einige Zeilen in Worten, um die Tabelle zu prüfen:

Schritt 3: Term und Schaltung

Jetzt übersetzt du die Beschreibung in einen logischen Term. Der Satz hat zwei Teile, die durch „oder“ verbunden sind:

Beide Teile werden mit ODER verknüpft. Weil das UND zuerst ausgewertet werden soll, kommt es in Klammern:

Alarm=(Tür∧Scharf)∨Rauch\text{Alarm} = (\text{Tür} \land \text{Scharf}) \lor \text{Rauch}

Der Term sagt dir direkt, welche Gatter du brauchst: ein UND-Gatter für die Klammer und ein ODER-Gatter, das den Ausgang des UND-Gatters mit dem Rauchmelder verknüpft. Was in der Klammer steht, liegt in der Schaltung weiter links, denn es wird zuerst berechnet.

Schaltung der Alarmanlage: \text{Alarm} = (\text{Tür} \land \text{Scharf}) \lor \text{Rauch}

Vergleiche die Schaltung mit der Tabelle: Die Leitung zwischen den beiden Gattern führt genau die Werte der Hilfsspalte Tür∧Scharf\text{Tür} \land \text{Scharf}.

Schritt 4: Testen

Eine Schaltung ist erst fertig, wenn sie getestet ist. Dazu baust du sie in CircuitVerse nach und probierst alle acht Belegungen aus.

Arbeitsauftrag 15: Alarmanlage in CircuitVerse

Baue die Schaltung der Alarmanlage in CircuitVerse nach. Verwende drei Input-Schalter für Tür, Scharf und Rauch, ein AND-Gatter, ein OR-Gatter und einen Output für Alarm. Teste alle acht Belegungen und vergleiche mit der Belegungstabelle oben. Notiere, welche Zeilen du getestet hast.

Getestete Zeilen und Auffälligkeiten:

Lösung vergleichen

Alle acht Zeilen müssen mit der Tabelle übereinstimmen: Alarm ist 1, sobald Rauch 1 ist, und außerdem in der Zeile Tür = 1, Scharf = 1, Rauch = 0. Weicht eine Zeile ab, liegt es meist an einer Leitung, die am falschen Gattereingang hängt, zum Beispiel Rauch am UND-Gatter statt am ODER-Gatter.

Tipp

In CircuitVerse kannst du jedem Input und Output einen Namen geben (Feld Label in den Eigenschaften des Bausteins). Mit beschrifteten Schaltern verwechselst du beim Testen keine Eingänge.

Auch Python kann die Belegungstabelle zur Kontrolle ausgeben. Für drei Eingänge brauchst du drei ineinander geschachtelte Schleifen:

def alarm(tuer, scharf, rauch):
    return int((tuer and scharf) or rauch)

print("Tür Scharf Rauch -> Alarm")
for tuer in [0, 1]:
    for scharf in [0, 1]:
        for rauch in [0, 1]:
            ergebnis = alarm(tuer, scharf, rauch)
            print(f" {tuer}    {scharf}      {rauch}   -> {ergebnis}")
Tür Scharf Rauch -> Alarm
 0    0      0   -> 0
 0    0      1   -> 1
 0    1      0   -> 0
 0    1      1   -> 1
 1    0      0   -> 0
 1    0      1   -> 1
 1    1      0   -> 1
 1    1      1   -> 1

Die Ausgabe stimmt Zeile für Zeile mit der Belegungstabelle überein. Die Schaltung erfüllt also die Anforderung.

Stolperstein

Achte auf die Klammern. Der Term Tür∧(Scharf∨Rauch)\text{Tür} \land (\text{Scharf} \lor \text{Rauch}) sieht ähnlich aus, beschreibt aber eine andere Schaltung. Vergleiche die beiden Terme in der Belegungstabelle (hier abgekürzt: T = Tür, S = Scharf, R = Rauch):

TT SS RR (T∧S)∨R(T \land S) \lor R T∧(S∨R)T \land (S \lor R)
0 0 0 0 0
0 0 1 1 0
0 1 0 0 0
0 1 1 1 0
1 0 0 0 0
1 0 1 1 1
1 1 0 1 1
1 1 1 1 1

In der zweiten und vierten Zeile unterscheiden sie sich: Es brennt, aber die Tür ist geschlossen. Mit dem falschen Term bliebe die Anlage stumm. Ein Test mit allen Belegungen deckt solche Fehler auf.

So kannst du es sagen

So beschreibst du eine Schaltung in Fachsprache – vom einfachen zum genauen Satz:

2.2.3Typische Fehler beim Entwurf

2.2.4Übungen

Arbeitsauftrag 16: Fahrstuhltür

Eine Fahrstuhltür darf sich nur schließen (Ausgang Schließen = 1), wenn beide Lichtschranken LS1 und LS2 frei sind und der Zeitgeber Zeit abgelaufen ist. Bei den Lichtschranken bedeutet 0 „blockiert“ und 1 „frei“. Beim Zeitgeber bedeutet 1 „abgelaufen“.

  1. Stelle die Belegungstabelle auf.
  2. Gib einen logischen Term an und skizziere die Schaltung.
  3. Baue die Schaltung in CircuitVerse und teste sie.
  4. Kontrolliere dein Ergebnis mit Python. Ergänze dazu die Funktion schliessen im folgenden Programm:
def schliessen(ls1, ls2, zeit):
    return ...   # hier ergänzen

for ls1 in [0, 1]:
    for ls2 in [0, 1]:
        for zeit in [0, 1]:
            ergebnis = schliessen(ls1, ls2, zeit)
            print(ls1, ls2, zeit, "->", ergebnis)
LS1 LS2 Zeit Schließen
0 0 0
0 0 1
0 1 0
0 1 1
1 0 0
1 0 1
1 1 0
1 1 1

Term und Skizze:

Lösung vergleichen
LS1 LS2 Zeit Schließen
0 0 0 0
0 0 1 0
0 1 0 0
0 1 1 0
1 0 0 0
1 0 1 0
1 1 0 0
1 1 1 1

Die Tür darf sich nur schließen, wenn alle drei Eingänge 1 sind. Das ist ein UND mit drei Eingängen:

Schließen=LS1∧LS2∧Zeit\text{Schließen} = \text{LS1} \land \text{LS2} \land \text{Zeit}

Fahrstuhltür: ein UND-Gatter mit drei Eingängen

Genauso richtig sind zwei UND-Gatter mit je zwei Eingängen hintereinander: Das erste verknüpft LS1 und LS2, das zweite verknüpft dessen Ausgang mit Zeit. In CircuitVerse kannst du beim AND-Gatter die Anzahl der Eingänge einstellen.

def schliessen(ls1, ls2, zeit):
    return int(ls1 and ls2 and zeit)

for ls1 in [0, 1]:
    for ls2 in [0, 1]:
        for zeit in [0, 1]:
            ergebnis = schliessen(ls1, ls2, zeit)
            print(ls1, ls2, zeit, "->", ergebnis)
0 0 0 -> 0
0 0 1 -> 0
0 1 0 -> 0
0 1 1 -> 0
1 0 0 -> 0
1 0 1 -> 0
1 1 0 -> 0
1 1 1 -> 1

Typischer Fehler: 0 und 1 bei den Lichtschranken vertauschen. Hier bedeutet 1 „frei“. Lies die Festlegung in der Aufgabe immer genau.

Arbeitsauftrag 17: Abstimmungsschaltung mit Vetorecht

Drei Personen A, B und C stimmen ab (0 = dagegen, 1 = dafür). Ein Antrag ist angenommen (Ausgang Q=1Q = 1), wenn die Mehrheit dafür ist. Aber: Stimmt Person A dagegen, ist der Antrag in jedem Fall abgelehnt (Vetorecht).

  1. Überlege dir zunächst in Worten, wann der Ausgang 1 sein muss.
  2. Stelle die Belegungstabelle auf. Die Hilfsspalte „Mehrheit“ gibt an, ob mindestens zwei Personen dafür sind.
  3. Gib einen Term an, skizziere die Schaltung und baue sie in CircuitVerse.
  4. Vergleiche mit einer Python-Kontrolle. Schreibe dazu eine Funktion antrag_angenommen(a, b, c).
AA BB CC Mehrheit QQ
0 0 0
0 0 1
0 1 0
0 1 1
1 0 0
1 0 1
1 1 0
1 1 1
Tipp

Die Mehrheitsschaltung kennst du schon aus dem letzten Abschnitt: (A∧B)∨(B∧C)∨(A∧C)(A \land B) \lor (B \land C) \lor (A \land C). Überlege, wie das Vetorecht von A mit diesem Ergebnis verknüpft werden muss.

In Worten, Term, Skizze und Python-Funktion:

Lösung vergleichen

In Worten: Der Antrag ist angenommen, wenn die Mehrheit dafür ist und A dafür ist. Weil A dann schon eine Stimme ist, reicht es, wenn außerdem B oder C dafür ist.

AA BB CC Mehrheit Mehrheit∧A\text{Mehrheit} \land A A∧(B∨C)A \land (B \lor C)
0 0 0 0 0 0
0 0 1 0 0 0
0 1 0 0 0 0
0 1 1 1 0 0
1 0 0 0 0 0
1 0 1 1 1 1
1 1 0 1 1 1
1 1 1 1 1 1

Die Zeile 0, 1, 1 zeigt das Vetorecht: B und C sind dafür, das ist eine Mehrheit. Weil A dagegen ist, wird der Antrag trotzdem abgelehnt.

Ein möglicher Term ist Q=((A∧B)∨(B∧C)∨(A∧C))∧AQ = ((A \land B) \lor (B \land C) \lor (A \land C)) \land A: die Mehrheitsschaltung mit einem zusätzlichen UND-Gatter für A. Die letzte Spalte zeigt, dass der kürzere Term Q=A∧(B∨C)Q = A \land (B \lor C) zu genau derselben Tabelle führt. Er braucht nur zwei Gatter:

Abstimmung mit Vetorecht: Q = A \land (B \lor C)

Beide Schaltungen sind richtig. Die kürzere ist billiger, weil sie weniger Gatter braucht. Wie man Terme systematisch vereinfacht, lernst du später in diesem Kapitel.

def antrag_angenommen(a, b, c):
    mehrheit = (a and b) or (b and c) or (a and c)
    return int(mehrheit and a)

for a in [0, 1]:
    for b in [0, 1]:
        for c in [0, 1]:
            ergebnis = antrag_angenommen(a, b, c)
            print(f"A={a}, B={b}, C={c} -> Angenommen={ergebnis}")
A=0, B=0, C=0 -> Angenommen=0
A=0, B=0, C=1 -> Angenommen=0
A=0, B=1, C=0 -> Angenommen=0
A=0, B=1, C=1 -> Angenommen=0
A=1, B=0, C=0 -> Angenommen=0
A=1, B=0, C=1 -> Angenommen=1
A=1, B=1, C=0 -> Angenommen=1
A=1, B=1, C=1 -> Angenommen=1
Arbeitsauftrag 18: Gartenbewässerung

Eine Pumpe bewässert einen Garten. Sie soll laufen (Pumpe = 1), wenn der Boden trocken ist und es nicht regnet. Außerdem gibt es einen Handschalter: Ist er eingeschaltet, läuft die Pumpe immer.

  1. Benenne die Eingänge und den Ausgang und lege fest, was 0 und 1 bedeuten.
  2. Stelle die Belegungstabelle auf (mit Hilfsspalten).
  3. Gib einen Term an und skizziere die Schaltung.

Deine Lösung:

Lösung vergleichen
  1. Eingänge: Trocken (1 = Boden ist trocken), Regen (1 = es regnet), Hand (1 = Handschalter ein). Ausgang: Pumpe (1 = Pumpe läuft).
  2. Belegungstabelle (abgekürzt: T = Trocken, R = Regen, H = Hand):
TT RR HH ¬R\lnot R T∧¬RT \land \lnot R (T∧¬R)∨H(T \land \lnot R) \lor H
0 0 0 1 0 0
0 0 1 1 0 1
0 1 0 0 0 0
0 1 1 0 0 1
1 0 0 1 1 1
1 0 1 1 1 1
1 1 0 0 0 0
1 1 1 0 0 1
  1. „Nicht regnet“ wird zu ¬Regen\lnot \text{Regen}, also brauchst du ein NICHT-Gatter. Der Term lautet Pumpe=(Trocken∧¬Regen)∨Hand\text{Pumpe} = (\text{Trocken} \land \lnot \text{Regen}) \lor \text{Hand}.
Gartenbewässerung: \text{Pumpe} = (\text{Trocken} \land \lnot \text{Regen}) \lor \text{Hand}

Die Schaltung ist wie die Alarmanlage aufgebaut. Neu ist nur das NICHT-Gatter vor dem UND-Gatter.

2.2.5Weitere Übungen

Hier kannst du das Gelernte weiter üben. Die Punkte im Titel zeigen, wie schwer eine Aufgabe ist: ●○○ leicht, ●●○ mittel, ●●● knifflig. Fang mit den leichten an.

Arbeitsauftrag 19: Eingänge und Ausgang benennen ●○○

Ein Ventilator im Zimmer soll laufen, wenn es im Zimmer warm ist und eine Person im Zimmer ist. Ein Temperaturfühler und ein Bewegungsmelder liefern die Eingangswerte.

Ergänze die Tabelle: Ist die Größe ein Eingang oder ein Ausgang? Was bedeuten 1 und 0?

Größe Art Bedeutung von 1 Bedeutung von 0
Warm
Person
Ventilator
Lösung vergleichen
Größe Art Bedeutung von 1 Bedeutung von 0
Warm Eingang Es ist warm im Zimmer. Es ist nicht warm.
Person Eingang Eine Person ist im Zimmer. Niemand ist im Zimmer.
Ventilator Ausgang Der Ventilator läuft. Der Ventilator ist aus.

Eingänge sind die Informationen, die die Schaltung bekommt (hier von Fühler und Melder). Der Ausgang ist das, was die Schaltung tut.

Arbeitsauftrag 20: Schaltung für den Ventilator ●○○

Setze den Auftrag Eingänge und Ausgang benennen fort.

  1. Stelle die Belegungstabelle auf.
  2. Gib einen logischen Term an und skizziere die Schaltung mit IEC-Symbolen.
Warm Person Ventilator
0 0
0 1
1 0
1 1

Term und Skizze:

Lösung vergleichen
Warm Person Ventilator
0 0 0
0 1 0
1 0 0
1 1 1

Der Ventilator läuft nur, wenn beide Eingänge 1 sind. Das ist ein UND: Ventilator=Warm∧Person\text{Ventilator} = \text{Warm} \land \text{Person}.

Ventilator: ein einziges UND-Gatter
Arbeitsauftrag 21: Sätze in Terme übersetzen ●○○

Übersetze jeden Satz in einen logischen Term. Nenne die Gatter, die du für die Schaltung brauchst.

  1. Das Tablet lädt (LL), wenn das Kabel steckt (KK) und die Steckdose Strom hat (SS).
  2. Die Klingel tönt (TT), wenn an der Haustür (HH) oder an der Gartentür (GG) jemand drückt.
  3. Der Bildschirm des Laptops ist an (DD), wenn der Deckel nicht zugeklappt ist. (Z=1Z = 1 bedeutet: Der Deckel ist zugeklappt.)
  4. Die Handykamera blitzt (BB), wenn es dunkel ist (NN) und der Blitz nicht ausgeschaltet ist. (X=1X = 1 bedeutet: Der Blitz ist ausgeschaltet.)

Deine Terme:

Lösung vergleichen
  1. L=K∧SL = K \land S, ein UND-Gatter.
  2. T=H∨GT = H \lor G, ein ODER-Gatter. Drücken an beiden Türen gleichzeitig Personen, tönt die Klingel auch.
  3. D=¬ZD = \lnot Z, ein NICHT-Gatter.
  4. B=N∧¬XB = N \land \lnot X, ein NICHT-Gatter für XX und ein UND-Gatter.

Bei c) und d) steckt das „nicht“ in der Festlegung von 0 und 1. Lies diese Festlegung immer genau.

Arbeitsauftrag 22: Welcher Term passt? ●○○

Das Licht auf dem Pausenhof geht an (L=1L = 1), wenn es dunkel ist (D=1D = 1) und der Bewegungsmelder etwas meldet (B=1B = 1), oder wenn der Hausmeister den Schalter einschaltet (H=1H = 1).

Welcher der drei Terme beschreibt die Anlage richtig? Begründe deine Wahl.

① (D∧B)∨H(D \land B) \lor H ② D∧(B∨H)D \land (B \lor H) ③ (D∨B)∧H(D \lor B) \land H

Deine Antwort:

Lösung vergleichen

Richtig ist ① (D∧B)∨H(D \land B) \lor H. „Dunkel und Bewegung“ gehört zusammen in eine Klammer. Der Hausmeisterschalter allein genügt, deshalb wird er mit ODER angehängt.

Die anderen Terme liefern in manchen Fällen das Falsche:

  • ② Am Tag (D=0D = 0) schaltet der Hausmeister ein (H=1H = 1). Laut ② bleibt es dunkel, denn das UND mit D=0D = 0 ergibt 0.
  • ③ Nachts meldet der Bewegungsmelder etwas (D=1D = 1, B=1B = 1, H=0H = 0). Laut ③ bleibt das Licht aus, denn das UND mit H=0H = 0 ergibt 0.

Ein einziger Fall, in dem ein Term das Falsche liefert, genügt, um ihn auszuschließen.

Arbeitsauftrag 23: Einlass ins Kino ●●○

Am Eingang eines Kinosaals öffnet sich eine Schranke (Auf=1\text{Auf} = 1), wenn ein gültiges Ticket gescannt wurde (T=1T = 1) und außerdem die Person mindestens 16 Jahre alt ist (S=1S = 1) oder von einer erwachsenen Person begleitet wird (E=1E = 1).

  1. Stelle die Belegungstabelle auf. Die Hilfsspalte gibt an, ob die Altersregel erfüllt ist.
  2. Gib einen logischen Term an.
  3. Skizziere die Schaltung mit IEC-Symbolen.
TT SS EE S∨ES \lor E Auf
0 0 0
0 0 1
0 1 0
0 1 1
1 0 0
1 0 1
1 1 0
1 1 1

Term und Skizze:

Lösung vergleichen
TT SS EE S∨ES \lor E Auf=T∧(S∨E)\text{Auf} = T \land (S \lor E)
0 0 0 0 0
0 0 1 1 0
0 1 0 1 0
0 1 1 1 0
1 0 0 0 0
1 0 1 1 1
1 1 0 1 1
1 1 1 1 1

Ohne Ticket öffnet die Schranke nie (obere Hälfte). Mit Ticket muss zusätzlich die Altersregel erfüllt sein. Der Term lautet Auf=T∧(S∨E)\text{Auf} = T \land (S \lor E). Die Klammer ist nötig, weil „16 oder begleitet“ zusammengehört.

Kinoeinlass: \text{Auf} = T \land (S \lor E)

Typischer Fehler: (T∧S)∨E(T \land S) \lor E. Dann würde die Schranke auch ohne Ticket öffnen, sobald eine erwachsene Begleitung dabei ist (Zeile 0 0 1).

Arbeitsauftrag 24: Kinoeinlass mit Python prüfen ●●○

Schreibe eine Funktion schranke(t, s, e), die den Term aus dem Auftrag Einlass ins Kino berechnet und 0 oder 1 zurückgibt. Gib mit drei geschachtelten for-Schleifen die Belegungstabelle aus und vergleiche sie mit deiner Tabelle.

Lösung vergleichen
def schranke(t, s, e):
    return int(t and (s or e))

print("T S E -> Auf")
for t in [0, 1]:
    for s in [0, 1]:
        for e in [0, 1]:
            print(t, s, e, "->", schranke(t, s, e))
T S E -> Auf
0 0 0 -> 0
0 0 1 -> 0
0 1 0 -> 0
0 1 1 -> 0
1 0 0 -> 0
1 0 1 -> 1
1 1 0 -> 1
1 1 1 -> 1

Die Klammern in Zeile 2 stehen genau wie im Term. Ohne sie würde Python t and s zuerst ausrechnen, und die Tabelle wäre falsch.

Arbeitsauftrag 25: Wasserspiel mit Sturmabschaltung ●●●

Ein Wasserspiel im Freizeitpark spritzt (W=1W = 1), wenn Musik läuft (M=1M = 1) oder ein Kind auf die Bodenplatte tritt (K=1K = 1). Bei Sturm (S=1S = 1) bleibt es aber in jedem Fall aus.

  1. Stelle die Belegungstabelle auf (mit Hilfsspalten).
  2. Gib einen Term an und skizziere die Schaltung.
  3. Jonas schlägt den Term M∨K∨¬SM \lor K \lor \lnot S vor. Gib eine Belegung an, bei der sein Term das Falsche liefert, und erkläre seinen Fehler.

Tabelle, Term, Skizze und Antwort zu Jonas:

Lösung vergleichen
MM KK SS M∨KM \lor K ¬S\lnot S W=(M∨K)∧¬SW = (M \lor K) \land \lnot S
0 0 0 0 1 0
0 0 1 0 0 0
0 1 0 1 1 1
0 1 1 1 0 0
1 0 0 1 1 1
1 0 1 1 0 0
1 1 0 1 1 1
1 1 1 1 0 0

Das Wort „aber“ bedeutet hier: Die Bedingung „kein Sturm“ muss zusätzlich erfüllt sein. Der Term lautet W=(M∨K)∧¬SW = (M \lor K) \land \lnot S. Das ist dasselbe Muster wie beim Vetorecht: Ein Eingang kann alles verhindern.

Wasserspiel: W = (M \lor K) \land \lnot S

Jonas’ Term liefert zum Beispiel bei M=1M = 1, K=0K = 0, S=1S = 1 eine 1: Das Wasserspiel würde bei Sturm spritzen. Auch bei M=0M = 0, K=0K = 0, S=0S = 0 liefert sein Term eine 1, obwohl weder Musik läuft noch ein Kind auf der Platte steht. Sein Fehler: Er hat „kein Sturm“ mit ODER angehängt. Dann genügt schon „kein Sturm“ allein. Richtig ist ein UND, denn kein Sturm ist eine Bedingung, die immer zusätzlich gelten muss.

2.2.6Das Wichtigste in Kürze

Selbstcheck

2.3Addition im Binärsystem und Halbaddierer DS17

Diesen Abschnitt als PDF (S. 32–45)

Das Jupyter-Notebook aus dem Unterricht: DS17_Binaeraddition_Halbaddierer.ipynb. Herunterladen und in VS Code oder Jupyter öffnen.

Leitidee

Jeder Taschenrechner, jedes Handy und jeder Computer kann in Bruchteilen einer Sekunde Millionen von Zahlen addieren. Dabei kennt die Elektronik nur 0 und 1, und rechnen können ihre Gatter eigentlich gar nicht: Sie verknüpfen nur Bits nach festen Regeln. Wie kann daraus ein Rechenwerk werden? Der Trick ist, Zahlen im Binärsystem zu schreiben, also nur mit den Ziffern 0 und 1. Dann funktioniert die Addition genau wie die schriftliche Addition aus der Grundschule. In diesem Abschnitt rechnest du zuerst selbst im Binärsystem. Danach baust du aus zwei Gattern eine Schaltung, die zwei Bits addiert: den Halbaddierer.

Lernziele

Nach diesem Abschnitt kannst du

2.3.1Zahlen im Binärsystem

Im Alltag schreiben wir Zahlen im Dezimalsystem (Zehnersystem). Es gibt zehn Ziffern, 0 bis 9. Welchen Wert eine Ziffer hat, hängt von ihrer Stelle ab. In der Zahl 347 steht die 3 an der Hunderterstelle, die 4 an der Zehnerstelle und die 7 an der Einerstelle: 347=3⋅100+4⋅10+7⋅1347 = 3 \cdot 100 + 4 \cdot 10 + 7 \cdot 1. Von Stelle zu Stelle wird der Stellenwert zehnmal so groß.

Das Binärsystem (Zweiersystem) funktioniert genauso, nur mit zwei Ziffern: 0 und 1. Von Stelle zu Stelle wird der Stellenwert doppelt so groß. Von rechts nach links sind die Stellenwerte also 1, 2, 4, 8, 16, 32 und so weiter. Jede Stelle einer Binärzahl ist ein Bit.

Definition: Binärsystem

Im Binärsystem (Zweiersystem) werden Zahlen nur mit den Ziffern 0 und 1 geschrieben. Die Stellenwerte sind von rechts nach links 1, 2, 4, 8, 16, …; jeder ist doppelt so groß wie der vorige.

Von binär nach dezimal

Um eine Binärzahl in eine Dezimalzahl umzurechnen, schreibst du sie in eine Stellenwerttabelle. Dann addierst du die Stellenwerte, unter denen eine 1 steht. Beispiel: die Binärzahl 1101.

Stellenwert 8 4 2 1
Ziffer 1 1 0 1

Unter 8, 4 und 1 steht eine 1. Also ist die Binärzahl 1101 gleich 8+4+1=138 + 4 + 1 = 13. Damit man die Zahlensysteme nicht verwechselt, schreibt man manchmal das System klein dahinter: 11012=13101101_2 = 13_{10}.

Von dezimal nach binär

Für den umgekehrten Weg füllst du die Stellenwerttabelle von links nach rechts. Beginne mit dem größten Stellenwert, der in die Zahl passt. Beispiel: die Dezimalzahl 22.

  1. Die Stellenwerte sind 1, 2, 4, 8, 16, 32, … Der größte, der in 22 passt, ist 16. Schreibe unter 16 eine 1. Es bleiben 22−16=622 - 16 = 6.
  2. Passt 8 in 6? Nein. Schreibe unter 8 eine 0.
  3. Passt 4 in 6? Ja. Schreibe unter 4 eine 1. Es bleiben 6−4=26 - 4 = 2.
  4. Passt 2 in 2? Ja. Schreibe unter 2 eine 1. Es bleibt 0.
  5. Unter 1 kommt eine 0, denn es ist nichts mehr übrig.
Stellenwert 16 8 4 2 1
Ziffer 1 0 1 1 0

Also ist 2210=10110222_{10} = 10110_2. Zur Probe rechnest du zurück: 16+4+2=2216 + 4 + 2 = 22.

Nullen am Anfang ändern den Wert einer Zahl nicht: 0101 und 101 sind beide gleich 5. Im Folgenden schreiben wir Binärzahlen oft mit vier Stellen, also 0101 statt 101. Dann stehen beim Rechnen alle Stellen schön untereinander.

Merke

Im Binärsystem gibt es nur die Ziffern 0 und 1. Die Stellenwerte sind von rechts nach links 1, 2, 4, 8, 16, … Den Dezimalwert einer Binärzahl erhält man, indem man die Stellenwerte addiert, unter denen eine 1 steht.

Arbeitsauftrag 26: Umrechnen

Rechne um. Mache jeweils die Probe.

dezimal 6 9 12 15
binär
binär 0111 1010 1011 10000
dezimal
Lösung vergleichen
dezimal 6 9 12 15 7 10 11 16
binär 0110 1001 1100 1111 0111 1010 1011 10000

Zum Beispiel 12=8+412 = 8 + 4, also stehen Einsen unter 8 und 4: 1100. Bei 10000 steht nur unter dem Stellenwert 16 eine 1. Mit vier Stellen kommt man also nur bis 8+4+2+1=158 + 4 + 2 + 1 = 15.

Werkzeug

Python kann Zahlen zwischen Dezimal- und Binärsystem umrechnen. Diese beiden Befehle brauchst du nur zum Nachprüfen:

print(int("1101", 2))
print(bin(22))
13
0b10110

2.3.2Schriftliche Addition im Binärsystem

Erinnere dich an die schriftliche Addition im Dezimalsystem. Du rechnest Stelle für Stelle von rechts nach links. Wird eine Stelle 10 oder größer, schreibst du nur die Einerziffer hin und nimmst eine 1 als Übertrag in die nächste Stelle mit:

      4 7
    + 3 8
  Ü   1
    -----
      8 5

Rechts: 7+8=157 + 8 = 15. Du schreibst 5 und überträgst 1. Links: 4+3+1=84 + 3 + 1 = 8. Die Zeile mit dem Ü enthält die Überträge. Jeder Übertrag steht genau unter der Stelle, zu der er addiert wird.

Im Binärsystem ist es genauso, nur dass schon bei 2 ein Übertrag entsteht. Denn eine Ziffer 2 gibt es nicht; 2 schreibt man binär als 10. Für zwei Bits gibt es nur vier Fälle:

Rechnung Ergebnis (binär) schreibe Übertrag
0+00 + 0 0 0 0
0+10 + 1 1 1 0
1+01 + 0 1 1 0
1+11 + 1 10 0 1

Kommt ein Übertrag aus der Stelle davor dazu, können auch drei Einsen zusammenkommen: 1+1+1=31 + 1 + 1 = 3, binär 11. Dann schreibst du 1 und überträgst 1.

Merke
Beispiel: 0101 + 0011

Wir addieren 0101 (das ist 5) und 0011 (das ist 3):

      0 1 0 1     (= 5)
    + 0 0 1 1     (= 3)
  Ü   1 1 1
    ---------
      1 0 0 0     (= 8)

Von rechts nach links:

Stelle Rechnung schreibe Übertrag in die nächste Stelle
1 (ganz rechts) 1+1=101 + 1 = 10 0 1
2 0+1+1=100 + 1 + 1 = 10 0 1
3 1+0+1=101 + 0 + 1 = 10 0 1
4 0+0+1=10 + 0 + 1 = 1 1 0

Ergebnis: 1000. Probe: 10002=81000_2 = 8 und 5+3=85 + 3 = 8. ✓

In diesem Beispiel entsteht in fast jeder Stelle ein Übertrag. Ab der zweiten Stelle werden deshalb drei Bits addiert: die beiden Ziffern der Zahlen und der Übertrag. Das wird im nächsten Abschnitt wichtig.

Stolperstein

Typische Fehler bei der Binäraddition:

Mache immer die Probe im Dezimalsystem.

Arbeitsauftrag 27: Von Hand rechnen

Berechne von Hand Schritt für Schritt mit Überträgen die folgenden binären Additionen. Kontrolliere anschließend mit der Probe im Dezimalsystem und mit Python (siehe Werkzeug-Kasten oben).

  1. 0110+01010110 + 0101
  2. 1011+01111011 + 0111
  3. 1111+00011111 + 0001

Deine Rechnungen:

Lösung vergleichen
      0 1 1 0     (= 6)
    + 0 1 0 1     (= 5)
  Ü   1
    ---------
      1 0 1 1     (= 11)
      1 0 1 1     (= 11)
    + 0 1 1 1     (=  7)
  Ü 1 1 1 1
    ---------
    1 0 0 1 0     (= 18)
      1 1 1 1     (= 15)
    + 0 0 0 1     (=  1)
  Ü 1 1 1 1
    ---------
    1 0 0 0 0     (= 16)
  1. Nur in der dritten Stelle von rechts entsteht ein Übertrag (1+1=101 + 1 = 10). Ergebnis: 1011.
  2. In jeder Stelle entsteht ein Übertrag. In der zweiten Stelle von rechts addierst du drei Einsen: 1+1+1=111 + 1 + 1 = 11, also 1 schreiben und 1 übertragen. Ergebnis: 10010.
  3. Der Übertrag wandert durch alle Stellen. Das Ergebnis hat fünf Stellen: 10000.

Kontrolle mit Python:

def pruefe(a_text, b_text):
    a = int(a_text, 2)
    b = int(b_text, 2)
    print(a_text, "+", b_text, "=", bin(a + b))

pruefe("0110", "0101")
pruefe("1011", "0111")
pruefe("1111", "0001")
0110 + 0101 = 0b1011
1011 + 0111 = 0b10010
1111 + 0001 = 0b10000

2.3.3Eine Schaltung, die zwei Bits addiert

Jetzt soll eine Schaltung die Arbeit übernehmen. Wir beginnen mit der einfachsten Aufgabe: der Stelle ganz rechts. Dort werden nur zwei Bits addiert, nennen wir sie AA und BB. Das Ergebnis besteht aus zwei Bits: der Ziffer, die man hinschreibt, und dem Übertrag. Man nennt sie Summe SS und Übertrag CC (vom englischen carry, „tragen“).

AA BB A+BA + B (dezimal) Übertrag CC Summe SS
0 0 0 0 0
0 1 1 0 1
1 0 1 0 1
1 1 2 1 0

Liest man CC und SS zusammen als zweistellige Binärzahl, steht dort genau die Summe: 00, 01, 01, 10, also 0, 1, 1, 2.

Schau dir die beiden Ausgangsspalten genau an. Kommen sie dir bekannt vor?

Mehr braucht man nicht. Eine Schaltung aus einem XOR-Gatter und einem UND-Gatter addiert zwei Bits. Sie heißt Halbaddierer.

2.3.4Der Halbaddierer

Halbaddierer: Das XOR-Gatter liefert die Summe S, das UND-Gatter den Übertrag C

So ist der Halbaddierer aufgebaut:

Die Belegungstabelle des Halbaddierers fasst das zusammen:

AA BB S=A⊕BS = A \oplus B C=A∧BC = A \land B
0 0 0 0
0 1 1 0
1 0 1 0
1 1 0 1

Funktionsweise an einem Beispiel: Liegt an AA und an BB je eine 1 an, dann sind die Eingänge gleich. Das XOR-Gatter liefert also S=0S = 0. Das UND-Gatter liefert C=1C = 1, weil beide Eingänge 1 sind. Zusammen ergibt das die Binärzahl 10, also 2. Das ist richtig, denn 1+1=21 + 1 = 2.

Definition: Halbaddierer

Ein Halbaddierer ist eine Schaltung mit zwei Eingängen AA, BB und zwei Ausgängen. Er addiert die beiden Bits und liefert die Summe S=A⊕BS = A \oplus B (XOR-Gatter) und den Übertrag C=A∧BC = A \land B (UND-Gatter).

Warum heißt er „halb“? Schau noch einmal auf das Beispiel 0101+00110101 + 0011. In der Stelle ganz rechts werden zwei Bits addiert; das schafft der Halbaddierer. Ab der zweiten Stelle muss aber zusätzlich der Übertrag aus der Stelle davor addiert werden. Dafür hat der Halbaddierer keinen Eingang. Er erledigt also nur die halbe Arbeit. Eine Schaltung, die auch den eingehenden Übertrag verarbeitet, lernst du im nächsten Abschnitt kennen: den Volladdierer.

Merke

Wenn man den Halbaddierer in größere Schaltungen einbaut, zeichnet man oft nicht jedes Gatter, sondern nur einen Kasten mit der Aufschrift HA. So ein vereinfachtes Bild heißt Blockschaltbild. Es zeigt nur, was hineingeht und was herauskommt.

Blockschaltbild des Halbaddierers: zwei Eingänge, zwei Ausgänge
So kannst du es sagen

So beschreibst du den Halbaddierer in Fachsprache – vom einfachen zum genauen Satz:

Arbeitsauftrag 28: Halbaddierer in CircuitVerse
  1. Lege zwei Input-Schalter AA und BB an.
  2. Füge ein XOR-Gatter hinzu (Eingänge: AA, BB). Sein Ausgang ist die Summe SS.
  3. Füge ein AND-Gatter hinzu (Eingänge: AA, BB). Sein Ausgang ist der Übertrag CC.
  4. Verbinde beide Gatterausgänge mit je einem Output.
  5. Teste alle vier Belegungen, trage die Werte ein und vergleiche mit der Belegungstabelle oben.
AA BB SS CC
0 0
0 1
1 0
1 1
Lösung vergleichen
AA BB SS CC
0 0 0 0
0 1 1 0
1 0 1 0
1 1 0 1

In CircuitVerse kann von einem Input-Schalter mehr als eine Leitung abgehen. Ziehe also von AA eine Leitung zum XOR-Gatter und eine zweite zum AND-Gatter, ebenso von BB. Speichere die Schaltung: Du brauchst sie im nächsten Abschnitt für den Volladdierer.

Arbeitsauftrag 29: Halbaddierer in Python

Schreibe eine Funktion halbaddierer(a, b), die die Summe und den Übertrag als Liste [summe, uebertrag] zurückgibt. Teste sie für alle vier Belegungen.

Tipp

Mit return gibt eine Funktion einen Wert zurück. Wenn du zwei Ergebnisse brauchst, packst du sie in eine Liste: return [summe, uebertrag]. An die einzelnen Werte kommst du später mit dem Index heran: ergebnis[0] ist die Summe, ergebnis[1] der Übertrag.

Lösung vergleichen
def halbaddierer(a, b):
    summe = int(a != b)        # XOR
    uebertrag = int(a and b)   # UND
    return [summe, uebertrag]

for a in [0, 1]:
    for b in [0, 1]:
        print(a, b, "->", halbaddierer(a, b))
0 0 -> [0, 0]
0 1 -> [1, 0]
1 0 -> [1, 0]
1 1 -> [0, 1]

Die Zeile 2 entspricht dem XOR-Gatter, die Zeile 3 dem UND-Gatter. Die Ausgabe stimmt mit der Belegungstabelle des Halbaddierers überein. Wer summe = int(a or b) schreibt, erhält in der letzten Zeile die Summe 1 statt 0. Das wäre falsch, denn 1+11 + 1 ergibt binär 10.

2.3.5Übungen

Arbeitsauftrag 30: Halbaddierer erläutern
  1. Erläutere den Aufbau und die Funktionsweise eines Halbaddierers. Gehe dabei auf die Belegung A=0A = 0, B=1B = 1 ein.
  2. Begründe am Beispiel 0101+00110101 + 0011, warum ein Halbaddierer für die zweite Stelle von rechts nicht ausreicht.

Deine Antwort:

Lösung vergleichen
  1. Ein Halbaddierer hat zwei Eingänge AA und BB und zwei Ausgänge, die Summe SS und den Übertrag CC. Beide Eingänge sind mit einem XOR-Gatter und mit einem UND-Gatter verbunden. Das XOR-Gatter liefert die Summe S=A⊕BS = A \oplus B, das UND-Gatter den Übertrag C=A∧BC = A \land B. Bei A=0A = 0, B=1B = 1 sind die Eingänge unterschiedlich, also liefert das XOR-Gatter S=1S = 1. Das UND-Gatter liefert C=0C = 0, weil nicht beide Eingänge 1 sind. Zusammen ergibt das 01, also 0+1=10 + 1 = 1.
  2. In der Stelle ganz rechts entsteht der Übertrag 1 (1+1=101 + 1 = 10). In der zweiten Stelle müssen deshalb drei Bits addiert werden: 0+1+10 + 1 + 1. Der Halbaddierer hat aber nur zwei Eingänge und kann den eingehenden Übertrag nicht berücksichtigen.
Arbeitsauftrag 31: Ergebnis vorhersagen

An einem Halbaddierer liegt A=1A = 1 und B=0B = 0 an. Gib ohne Tabelle an, welche Werte SS und CC haben, und begründe mit den beiden Gattern. Welche Belegung führt zu C=1C = 1?

Deine Antwort:

Lösung vergleichen

S=1S = 1, denn die Eingänge sind unterschiedlich, und das XOR-Gatter liefert dann eine 1. C=0C = 0, denn das UND-Gatter liefert nur eine 1, wenn beide Eingänge 1 sind. Nur die Belegung A=1A = 1, B=1B = 1 führt zu C=1C = 1.

2.3.6Weitere Übungen

Hier kannst du das Gelernte weiter üben. Die Punkte im Titel zeigen, wie schwer eine Aufgabe ist: ●○○ leicht, ●●○ mittel, ●●● knifflig. Fang mit den leichten an.

Arbeitsauftrag 32: Bits addieren ●○○

Bestimme für jede Rechnung, welche Ziffer man hinschreibt und welcher Übertrag entsteht.

Rechnung Ergebnis (binär) schreibe Übertrag
1+01 + 0
1+11 + 1
0+0+10 + 0 + 1
1+0+11 + 0 + 1
1+1+11 + 1 + 1
Lösung vergleichen
Rechnung Ergebnis (binär) schreibe Übertrag
1+01 + 0 1 1 0
1+11 + 1 10 0 1
0+0+10 + 0 + 1 1 1 0
1+0+11 + 0 + 1 10 0 1
1+1+11 + 1 + 1 11 1 1

Die rechte Ziffer des Ergebnisses schreibst du hin, die linke ist der Übertrag. Bei drei Einsen ist das Ergebnis 11: Du schreibst 1 und überträgst 1.

Arbeitsauftrag 33: Addieren ohne Übertrag ●○○

Berechne von Hand. Die Dezimalwerte stehen zur Kontrolle in Klammern.

  1. 0100+00110100 + 0011 \quad (4 + 3)
  2. 1010+01011010 + 0101 \quad (10 + 5)
  3. 1000+01101000 + 0110 \quad (8 + 6)

Woran erkennst du schon vor dem Rechnen, dass kein Übertrag entsteht?

Deine Rechnungen und deine Antwort:

Lösung vergleichen
      0 1 0 0     (= 4)
    + 0 0 1 1     (= 3)
    ---------
      0 1 1 1     (= 7)
      1 0 1 0     (= 10)
    + 0 1 0 1     (=  5)
    ---------
      1 1 1 1     (= 15)
      1 0 0 0     (=  8)
    + 0 1 1 0     (=  6)
    ---------
      1 1 1 0     (= 14)

Ein Übertrag entsteht nur bei 1+11 + 1. In keiner Spalte stehen zwei Einsen untereinander, also gibt es keinen Übertrag. Man kann die Ziffern einfach Spalte für Spalte hinschreiben.

Arbeitsauftrag 34: Addieren mit einem Übertrag ●○○

Berechne von Hand. Schreibe den Übertrag in die Ü-Zeile.

  1. 0010+00100010 + 0010 \quad (2 + 2)
  2. 0101+00010101 + 0001 \quad (5 + 1)
  3. 0110+01000110 + 0100 \quad (6 + 4)

Deine Rechnungen:

Lösung vergleichen
      0 0 1 0     (= 2)
    + 0 0 1 0     (= 2)
  Ü     1
    ---------
      0 1 0 0     (= 4)
      0 1 0 1     (= 5)
    + 0 0 0 1     (= 1)
  Ü       1
    ---------
      0 1 1 0     (= 6)
      0 1 1 0     (=  6)
    + 0 1 0 0     (=  4)
  Ü   1
    ---------
      1 0 1 0     (= 10)

Der Übertrag steht immer unter der Stelle links von der Stelle, an der er entstanden ist, denn dort wird er dazuaddiert.

Arbeitsauftrag 35: Lückentext zum Halbaddierer ●○○

Ergänze die Lücken (1) bis (7).

Ein Halbaddierer hat (1) Eingänge und (2) Ausgänge. Die Summe SS liefert ein (3)-Gatter, den Übertrag CC ein (4)-Gatter. Liegt an beiden Eingängen eine 1 an, ist S=S = (5) und C=C = (6). „Halb“ heißt er, weil er keinen (7) aus der Stelle davor verarbeiten kann.

Deine Lösungen:

Lösung vergleichen
  1. zwei, (2) zwei, (3) XOR, (4) UND, (5) 0, (6) 1, (7) Übertrag (eingehenden Übertrag).

Zu (5) und (6): 1+1=101 + 1 = 10 im Binärsystem. Die 0 ist die Summe, die 1 ist der Übertrag.

Arbeitsauftrag 36: Addieren mit mehreren Überträgen ●●○

Berechne von Hand Schritt für Schritt. Schreibe alle Überträge in die Ü-Zeile. Prüfe dein Ergebnis anschließend mit Python.

  1. 0111+00110111 + 0011 \quad (7 + 3)
  2. 0110+01100110 + 0110 \quad (6 + 6)
  3. 1110+00111110 + 0011 \quad (14 + 3)

Deine Rechnungen:

Lösung vergleichen
      0 1 1 1     (=  7)
    + 0 0 1 1     (=  3)
  Ü   1 1 1
    ---------
      1 0 1 0     (= 10)
      0 1 1 0     (=  6)
    + 0 1 1 0     (=  6)
  Ü   1 1
    ---------
      1 1 0 0     (= 12)
      1 1 1 0     (= 14)
    + 0 0 1 1     (=  3)
  Ü 1 1 1
    ---------
    1 0 0 0 1     (= 17)
  1. In der zweiten Stelle von rechts kommen drei Einsen zusammen: 1+1+1=111 + 1 + 1 = 11, also 1 schreiben, 1 übertragen.
  2. Der letzte Übertrag macht das Ergebnis fünfstellig. Vergiss ihn nicht.
Arbeitsauftrag 37: Fehler finden ●●○

Lena und Tim haben gerechnet. Beide Ergebnisse sind falsch.

  Lena:   0 1 0 1          Tim:   0 1 1 0
        + 0 0 0 1               + 0 1 1 1
        ---------               ---------
          0 1 0 2                 0 0 0 1
  1. Beschreibe jeweils den Fehler.
  2. Rechne beide Aufgaben richtig.
  3. Tim hat in jeder Spalte dasselbe Gatter „nachgespielt“. Welches Gatter ist das?

Deine Antwort und die richtigen Rechnungen:

Lösung vergleichen
  1. Lena hat 1+1=21 + 1 = 2 geschrieben. Die Ziffer 2 gibt es im Binärsystem nicht. Tim hat alle Überträge vergessen. Er hat bei 1+11 + 1 nur die 0 hingeschrieben.
  2. Richtig ist:
      0 1 0 1     (= 5)
    + 0 0 0 1     (= 1)
  Ü       1
    ---------
      0 1 1 0     (= 6)
      0 1 1 0     (=  6)
    + 0 1 1 1     (=  7)
  Ü   1 1
    ---------
      1 1 0 1     (= 13)
  1. Tim hat in jeder Spalte eine 1 geschrieben, wenn die Ziffern unterschiedlich sind, und sonst eine 0. Das ist das XOR-Gatter, also genau die Summe SS des Halbaddierers. Was ihm fehlt, ist der Übertrag CC und dessen Weitergabe an die nächste Stelle.
Arbeitsauftrag 38: Rechnungen mit Python prüfen ●●○

Schreibe eine Funktion addiere(a_text, b_text), die zwei Binärzahlen als Zeichenketten bekommt. Sie soll die Summe als Binärzahl ausgeben und zur Kontrolle auch die Rechnung im Dezimalsystem. Prüfe damit deine Ergebnisse aus dem Auftrag Addieren mit mehreren Überträgen.

Für addiere("0111", "0011") soll die Ausgabe so aussehen:

0111 + 0011 = 0b1010 | dezimal: 7 + 3 = 10
Tipp

Die Befehle int("0111", 2) und bin(...) kennst du aus dem Werkzeug-Kasten im Abschnitt über das Binärsystem.

Lösung vergleichen
def addiere(a_text, b_text):
    a = int(a_text, 2)
    b = int(b_text, 2)
    summe = a + b
    print(a_text, "+", b_text, "=", bin(summe),
          "| dezimal:", a, "+", b, "=", summe)

addiere("0111", "0011")
addiere("0110", "0110")
addiere("1110", "0011")
0111 + 0011 = 0b1010 | dezimal: 7 + 3 = 10
0110 + 0110 = 0b1100 | dezimal: 6 + 6 = 12
1110 + 0011 = 0b10001 | dezimal: 14 + 3 = 17

Python lässt führende Nullen weg: 0b1010 bedeutet 1010. Ein langer print-Befehl darf auf zwei Zeilen verteilt werden, solange die Klammer noch offen ist.

Arbeitsauftrag 39: Fehlende Ziffern ●●●

In jeder Rechnung ist eine Ziffer durch x ersetzt. Bestimme x und begründe, Spalte für Spalte von rechts.

  1. 1x01+0110=100111\text{x}01 + 0110 = 10011
  2. 01x1+0101=110001\text{x}1 + 0101 = 1100

Deine Begründung:

Lösung vergleichen
  1. x = 1. Rechts: 1+0=11 + 0 = 1 ✓, dann 0+1=10 + 1 = 1 ✓. In der dritten Stelle von rechts steht im Ergebnis eine 0. Aus x+1\text{x} + 1 wird nur dann 0, wenn x=1\text{x} = 1 ist: 1+1=101 + 1 = 10, also 0 schreiben, 1 übertragen. Links: 1+0+1=101 + 0 + 1 = 10, das ergibt die Ziffern 1 und 0 ganz links im Ergebnis 10011 ✓.
      1 1 0 1     (= 13)
    + 0 1 1 0     (=  6)
  Ü 1 1
    ---------
    1 0 0 1 1     (= 19)
  1. x = 1. Rechts: 1+1=101 + 1 = 10, also 0 schreiben ✓ und 1 übertragen. Zweite Stelle: x+0+1\text{x} + 0 + 1 muss eine 0 ergeben. Das geht nur mit x=1\text{x} = 1: 1+0+1=101 + 0 + 1 = 10, also 0 schreiben ✓, 1 übertragen. Dritte Stelle: 1+1+1=111 + 1 + 1 = 11, also 1 schreiben ✓, 1 übertragen. Links: 0+0+1=10 + 0 + 1 = 1 ✓.
      0 1 1 1     (=  7)
    + 0 1 0 1     (=  5)
  Ü   1 1 1
    ---------
      1 1 0 0     (= 12)

Mit x=0\text{x} = 0 ginge es jeweils nicht: In a) erhielte man 1111, in b) 1010.

2.3.7Das Wichtigste in Kürze

Selbstcheck

2.4Volladdierer und Carry-Ripple-Addierer DS18

Diesen Abschnitt als PDF (S. 46–59)

Das Jupyter-Notebook aus dem Unterricht: DS18_Volladdierer_CarryRipple.ipynb. Herunterladen und in VS Code oder Jupyter öffnen.

Leitidee

Mit dem Halbaddierer kann eine Schaltung zwei Bits addieren. Das reicht aber nur für die Stelle ganz rechts. Schon in der zweiten Stelle kommt der Übertrag aus der ersten Stelle dazu, und dann müssen drei Bits addiert werden. Dafür gibt es den Volladdierer. Er lässt sich aus zwei Halbaddierern und einem ODER-Gatter zusammensetzen. Schaltet man mehrere Volladdierer hintereinander, erhält man ein Rechenwerk, das ganze Binärzahlen addiert. Es arbeitet genau so, wie du schriftlich addierst: Stelle für Stelle, und der Übertrag wird jeweils an die nächste Stelle weitergereicht.

Lernziele

Nach diesem Abschnitt kannst du

2.4.1Drei Bits addieren

Erinnere dich an die Rechnung 0101+00110101 + 0011 aus dem letzten Abschnitt:

      0 1 0 1     (= 5)
    + 0 0 1 1     (= 3)
  Ü   1 1 1
    ---------
      1 0 0 0     (= 8)

In der zweiten Stelle von rechts rechnest du 0+1+10 + 1 + 1: die Ziffer der ersten Zahl, die Ziffer der zweiten Zahl und den Übertrag aus der ersten Stelle. Eine Schaltung für diese Stelle braucht also drei Eingänge:

Die Summe von drei Bits ist höchstens 1+1+1=31 + 1 + 1 = 3, binär 11. Das Ergebnis passt also wieder in zwei Bits: die Summe SS, die an dieser Stelle hingeschrieben wird, und den ausgehenden Übertrag CausC_{\mathrm{aus}}, der an die nächste Stelle links weitergegeben wird. Im Englischen heißen die Überträge carry in und carry out, kurz CinC_{\mathrm{in}} und CoutC_{\mathrm{out}}.

AA BB CeinC_{\mathrm{ein}} Einsen CausC_{\mathrm{aus}} SS
0 0 0 0 0 0
0 0 1 1 0 1
0 1 0 1 0 1
0 1 1 2 1 0
1 0 0 1 0 1
1 0 1 2 1 0
1 1 0 2 1 0
1 1 1 3 1 1

Die Spalte „Einsen“ gibt an, wie viele der drei Eingänge 1 sind. Liest man CausC_{\mathrm{aus}} und SS zusammen als Binärzahl, steht dort genau diese Anzahl: 00, 01, 10 oder 11. Zwei Beobachtungen helfen beim Merken:

Definition: Volladdierer

Ein Volladdierer ist eine Schaltung mit drei Eingängen und zwei Ausgängen. Er addiert die beiden Bits AA und BB und den eingehenden Übertrag CeinC_{\mathrm{ein}} und liefert die Summe SS und den ausgehenden Übertrag CausC_{\mathrm{aus}}.

So kannst du es sagen

So beschreibst du den Volladdierer in Fachsprache – vom einfachen zum genauen Satz:

2.4.2Der Volladdierer aus zwei Halbaddierern

Wie baut man eine solche Schaltung? Du musst keine neuen Gatter erfinden. Denk daran, wie du drei Zahlen im Kopf addierst: Erst addierst du zwei davon, dann addierst du die dritte zum Zwischenergebnis. Genauso arbeitet der Volladdierer mit zwei Halbaddierern:

  1. Halbaddierer 1 addiert AA und BB. Er liefert eine Zwischensumme S1S_1 und einen Übertrag C1C_1.
  2. Halbaddierer 2 addiert die Zwischensumme S1S_1 und den eingehenden Übertrag CeinC_{\mathrm{ein}}. Er liefert die endgültige Summe SS und einen zweiten Übertrag C2C_2.
  3. Ist bei einem der beiden Schritte ein Übertrag entstanden, gibt es einen ausgehenden Übertrag. Ein ODER-Gatter verknüpft deshalb C1C_1 und C2C_2: Caus=C1∨C2C_{\mathrm{aus}} = C_1 \lor C_2.
Volladdierer aus zwei Halbaddierern und einem ODER-Gatter

Jeder Halbaddierer besteht aus einem XOR- und einem UND-Gatter. Zeichnet man alle Gatter einzeln, sieht der Volladdierer so aus. Diese Zeichnung brauchst du, wenn du ihn in CircuitVerse aufbaust:

Volladdierer aus Gattern: oben links Halbaddierer 1, rechts Halbaddierer 2, ganz rechts das ODER-Gatter

Die Belegungstabelle mit den Zwischenergebnissen als Hilfsspalten zeigt, dass der Aufbau stimmt. Die beiden letzten Spalten sind genau die Spalten SS und CausC_{\mathrm{aus}} aus der Tabelle oben.

AA BB CeinC_{\mathrm{ein}} S1S_1 C1C_1 C2C_2 SS CausC_{\mathrm{aus}}
0 0 0 0 0 0 0 0
0 0 1 0 0 0 1 0
0 1 0 1 0 0 1 0
0 1 1 1 0 1 0 1
1 0 0 1 0 0 1 0
1 0 1 1 0 1 0 1
1 1 0 0 1 0 0 1
1 1 1 0 1 0 1 1

Dabei gilt S1=A⊕BS_1 = A \oplus B, C1=A∧BC_1 = A \land B, C2=S1∧CeinC_2 = S_1 \land C_{\mathrm{ein}}, S=S1⊕CeinS = S_1 \oplus C_{\mathrm{ein}} und Caus=C1∨C2C_{\mathrm{aus}} = C_1 \lor C_2.

Funktionsweise an einem Beispiel (letzte Zeile): An allen drei Eingängen liegt eine 1 an. Halbaddierer 1 rechnet 1+1=101 + 1 = 10, also S1=0S_1 = 0 und C1=1C_1 = 1. Halbaddierer 2 rechnet S1+Cein=0+1=1S_1 + C_{\mathrm{ein}} = 0 + 1 = 1, also S=1S = 1 und C2=0C_2 = 0. Das ODER-Gatter liefert Caus=1∨0=1C_{\mathrm{aus}} = 1 \lor 0 = 1. Zusammen ergibt das 11, also 3. Das stimmt: 1+1+1=31 + 1 + 1 = 3.

Tipp

Warum genügt am Ende ein ODER-Gatter? Könnten nicht beide Halbaddierer gleichzeitig einen Übertrag liefern? Nein: C1=1C_1 = 1 heißt, dass AA und BB beide 1 sind. Dann ist aber S1=0S_1 = 0, und der zweite Halbaddierer addiert höchstens 0+10 + 1. Er liefert also keinen Übertrag. In der Tabelle sind C1C_1 und C2C_2 nie gleichzeitig 1.

Merke
Arbeitsauftrag 40: Volladdierer in CircuitVerse
  1. Baue zwei Halbaddierer wie im letzten Abschnitt (je ein XOR- und ein AND-Gatter).
  2. Verbinde den Summenausgang des ersten Halbaddierers mit einem Eingang des zweiten Halbaddierers. Der zweite Eingang ist CeinC_{\mathrm{ein}}.
  3. Verknüpfe die beiden Übertragsausgänge C1C_1 und C2C_2 mit einem OR-Gatter. Dessen Ausgang ist CausC_{\mathrm{aus}}.
  4. Teste alle acht möglichen Belegungen von AA, BB und CeinC_{\mathrm{ein}}, trage die Werte ein und vergleiche mit der Belegungstabelle oben.
AA BB CeinC_{\mathrm{ein}} SS CausC_{\mathrm{aus}}
0 0 0
0 0 1
0 1 0
0 1 1
1 0 0
1 0 1
1 1 0
1 1 1
Tipp

In CircuitVerse gibt es auch einen fertigen Volladdierer-Baustein (englisch Full Adder bzw. Adder). Baue den Volladdierer aber zuerst selbst aus Gattern, damit du verstehst, wie er funktioniert. Den fertigen Baustein kannst du danach zum Vergleichen und für größere Schaltungen verwenden.

Lösung vergleichen
AA BB CeinC_{\mathrm{ein}} SS CausC_{\mathrm{aus}}
0 0 0 0 0
0 0 1 1 0
0 1 0 1 0
0 1 1 0 1
1 0 0 1 0
1 0 1 0 1
1 1 0 0 1
1 1 1 1 1

Wenn eine Zeile nicht stimmt, prüfe vor allem die Leitung S1S_1: Sie muss zu beiden Gattern des zweiten Halbaddierers führen, und CeinC_{\mathrm{ein}} ebenso.

Kontrolle mit Python

Die Funktion volladdierer bildet die Schaltung Gatter für Gatter nach. Wie beim Halbaddierer gibt sie ihre beiden Ergebnisse als Liste zurück.

def volladdierer(a, b, c_ein):
    s1 = int(a != b)          # Halbaddierer 1: Summe
    c1 = int(a and b)         # Halbaddierer 1: Übertrag
    s = int(s1 != c_ein)      # Halbaddierer 2: Summe
    c2 = int(s1 and c_ein)    # Halbaddierer 2: Übertrag
    c_aus = int(c1 or c2)     # ODER-Gatter
    return [s, c_aus]

for a in [0, 1]:
    for b in [0, 1]:
        for c_ein in [0, 1]:
            erg = volladdierer(a, b, c_ein)
            print(f"A={a} B={b} Cein={c_ein} -> {erg}")
A=0 B=0 Cein=0 -> [0, 0]
A=0 B=0 Cein=1 -> [1, 0]
A=0 B=1 Cein=0 -> [1, 0]
A=0 B=1 Cein=1 -> [0, 1]
A=1 B=0 Cein=0 -> [1, 0]
A=1 B=0 Cein=1 -> [0, 1]
A=1 B=1 Cein=0 -> [0, 1]
A=1 B=1 Cein=1 -> [1, 1]

2.4.3Der Carry-Ripple-Addierer

Ein Volladdierer kümmert sich um eine Stelle. Für vierstellige Binärzahlen nimmst du vier Volladdierer, einen für jede Stelle. Die Bits der beiden Zahlen nummeriert man von rechts nach links mit 0, 1, 2, 3: A0A_0 ist das Bit ganz rechts von AA, A3A_3 das Bit ganz links. Der Volladdierer VA0_0 ist für die Stelle 0 zuständig, VA1_1 für die Stelle 1 und so weiter.

Die Volladdierer werden wie eine Kette verbunden: Der ausgehende Übertrag einer Stelle wird zum eingehenden Übertrag der nächsthöheren Stelle. Ganz rechts gibt es keinen Übertrag von vorher, deshalb ist dort C0=0C_0 = 0. Der Übertrag C4C_4, der ganz links herauskommt, ist die fünfte Stelle des Ergebnisses.

Carry-Ripple-Addierer für vier Bit: Der Übertrag wandert von rechts nach links durch die Volladdierer

Das ist nichts anderes als die schriftliche Addition, nur als Schaltung: Jeder Volladdierer rechnet eine Spalte, und die Leitungen zwischen ihnen sind die Ü-Zeile.

Eine Rechnung durch alle Stufen verfolgen

Wir lassen den Carry-Ripple-Addierer 0101+00110101 + 0011 rechnen. Es ist A3A2A1A0=0101A_3 A_2 A_1 A_0 = 0101 und B3B2B1B0=0011B_3 B_2 B_1 B_0 = 0011. Die Stufen arbeiten von rechts nach links. (Achtung: S1S_1 bezeichnet hier das Summenbit der Stelle 1, nicht die Zwischensumme im Inneren eines Volladdierers.)

Stufe AiA_i BiB_i Übertrag ein Summe SiS_i Übertrag aus
VA0_0 1 1 C0=0C_0 = 0 S0=0S_0 = 0 C1=1C_1 = 1
VA1_1 0 1 C1=1C_1 = 1 S1=0S_1 = 0 C2=1C_2 = 1
VA2_2 1 0 C2=1C_2 = 1 S2=0S_2 = 0 C3=1C_3 = 1
VA3_3 0 0 C3=1C_3 = 1 S3=1S_3 = 1 C4=0C_4 = 0
Der Carry-Ripple-Addierer rechnet 0101 + 0011. Die roten Zahlen sind die Werte auf den Leitungen

Das Ergebnis liest man von links nach rechts ab: C4S3S2S1S0=01000C_4 S_3 S_2 S_1 S_0 = 01000, also 8. Die Rechnung stimmt: 5+3=85 + 3 = 8.

Achte auf die Spalte „Übertrag ein“: Jede Stufe braucht den Übertrag der Stufe rechts davon. VA1_1 kann sein endgültiges Ergebnis erst liefern, wenn VA0_0 fertig ist; VA2_2 muss auf VA1_1 warten, und so weiter. Der Übertrag wandert wie eine Welle von rechts nach links durch die Kette. Daher kommt der Name: Englisch carry heißt Übertrag, ripple heißt „rieseln“ oder „sich wellenförmig ausbreiten“.

Das hat einen Nachteil: Je mehr Stellen, desto länger dauert es, bis der Übertrag ganz links angekommen ist. Ein Computer, der 64-stellige Binärzahlen addiert, müsste im schlimmsten Fall warten, bis der Übertrag durch alle 64 Volladdierer gewandert ist. Echte Prozessoren verwenden deshalb geschicktere, aber auch aufwendigere Addierschaltungen.

Merke

Ein Carry-Ripple-Addierer verkettet mehrere Volladdierer: Der ausgehende Übertrag CausC_{\mathrm{aus}} einer Stelle wird zum eingehenden Übertrag CeinC_{\mathrm{ein}} der nächsthöheren Stelle. So werden mehrstellige Binärzahlen addiert. Der Übertrag „rieselt“ (englisch ripple) von Stelle zu Stelle durch.

So kannst du es sagen

So erläuterst du den Carry-Ripple-Addierer:

Arbeitsauftrag 41: Carry-Ripple-Addierer skizzieren und erläutern

Skizziere das Blockschaltbild eines 4-Bit-Carry-Ripple-Addierers: vier Volladdierer-Blöcke nebeneinander mit den Eingängen A0A_0 bis A3A_3 und B0B_0 bis B3B_3, den Summenausgängen S0S_0 bis S3S_3 sowie Pfeilen, die zeigen, wie der ausgehende Übertrag jeder Stelle zum eingehenden Übertrag der nächsten Stelle wird. Erläutere in ein bis zwei Sätzen, warum die Bezeichnung „Ripple“ (rieseln) passend ist.

Deine Skizze und Erläuterung:

Lösung vergleichen
Blockschaltbild eines 4-Bit-Carry-Ripple-Addierers

Erläuterung: Jeder Volladdierer addiert die beiden Bits seiner Stelle und den Übertrag aus der Stelle rechts daneben. Sein ausgehender Übertrag wird an die nächste Stelle links weitergegeben. Weil jede Stufe auf den Übertrag der vorherigen Stufe warten muss, „rieselt“ der Übertrag Stufe für Stufe von rechts nach links durch die ganze Kette. Deshalb passt der Name Ripple.

Wichtig in der Skizze: Ganz rechts liegt am Übertragseingang eine 0 an. Der Übertrag ganz links (C4C_4) ist die fünfte Stelle des Ergebnisses. Statt VA0_0 darf man auch einen Halbaddierer verwenden, weil dort kein Übertrag ankommt.

Arbeitsauftrag 42: Eine Addition verfolgen

Verfolge die Addition 1011+01101011 + 0110 durch alle Stufen eines 4-Bit-Carry-Ripple-Addierers. Fülle die Tabelle aus, lies das Ergebnis ab und mache die Probe im Dezimalsystem.

Stufe AiA_i BiB_i Übertrag ein Summe SiS_i Übertrag aus
VA0_0
VA1_1
VA2_2
VA3_3

Ergebnis und Probe:

Lösung vergleichen

Es ist A3A2A1A0=1011A_3 A_2 A_1 A_0 = 1011 und B3B2B1B0=0110B_3 B_2 B_1 B_0 = 0110.

Stufe AiA_i BiB_i Übertrag ein Summe SiS_i Übertrag aus
VA0_0 1 0 C0=0C_0 = 0 S0=1S_0 = 1 C1=0C_1 = 0
VA1_1 1 1 C1=0C_1 = 0 S1=0S_1 = 0 C2=1C_2 = 1
VA2_2 0 1 C2=1C_2 = 1 S2=0S_2 = 0 C3=1C_3 = 1
VA3_3 1 0 C3=1C_3 = 1 S3=0S_3 = 0 C4=1C_4 = 1

Ergebnis: C4S3S2S1S0=10001C_4 S_3 S_2 S_1 S_0 = 10001, also 17. Probe: 10112=111011_2 = 11, 01102=60110_2 = 6, 11+6=1711 + 6 = 17. ✓

Häufiger Fehler: mit der Stufe VA0_0 beim linken Bit anfangen. Die Stufe 0 gehört immer zum Bit ganz rechts.

Arbeitsauftrag 43: 4-Bit-Carry-Ripple-Addierer in Python

Schreibe eine Funktion carry_ripple_addierer(a_bits, b_bits). Sie bekommt zwei 4-Bit-Zahlen als Listen mit vier Bits, zum Beispiel [0, 1, 0, 1] für 0101. Sie soll die Zahlen mithilfe der Funktion volladdierer (siehe oben) stellenweise von rechts nach links addieren und das Ergebnis als Liste mit fünf Bits zurückgeben (einschließlich des Übertrags ganz links).

Test: carry_ripple_addierer([0, 1, 0, 1], [0, 0, 1, 1]) soll [0, 1, 0, 0, 0] liefern, denn 5+3=85 + 3 = 8.

Tipp

Der eingehende Übertrag der niedrigsten Stelle ist 0. Verarbeite die Listen von hinten nach vorn: Das Bit ganz rechts hat den Index 3, das Bit ganz links den Index 0. Eine Schleife, die rückwärts zählt, kennst du: for i in range(3, -1, -1). Mit liste.insert(0, wert) fügst du einen Wert vorn in eine Liste ein.

Lösung vergleichen
def volladdierer(a, b, c_ein):
    s1 = int(a != b)
    c1 = int(a and b)
    s = int(s1 != c_ein)
    c2 = int(s1 and c_ein)
    c_aus = int(c1 or c2)
    return [s, c_aus]

def carry_ripple_addierer(a_bits, b_bits):
    ergebnis = []
    c = 0
    for i in range(len(a_bits) - 1, -1, -1):
        va = volladdierer(a_bits[i], b_bits[i], c)
        ergebnis.insert(0, va[0])
        c = va[1]
    ergebnis.insert(0, c)
    return ergebnis

print(carry_ripple_addierer([0, 1, 0, 1], [0, 0, 1, 1]))
print(carry_ripple_addierer([1, 0, 1, 1], [0, 1, 1, 0]))
[0, 1, 0, 0, 0]
[1, 0, 0, 0, 1]
  • Zeilen 10–11: Die Ergebnisliste ist am Anfang leer. Die Variable c ist der Übertrag, der von Stufe zu Stufe weitergegeben wird. Am Anfang ist er 0.
  • Zeile 12: i läuft rückwärts: 3, 2, 1, 0. So wird die Stelle ganz rechts zuerst bearbeitet. len(a_bits) - 1 statt 3 sorgt dafür, dass die Funktion auch für längere Listen funktioniert.
  • Zeile 13: Ein Volladdierer addiert die beiden Bits an der Stelle i und den Übertrag c.
  • Zeile 14: Die Summe wird vorn in die Ergebnisliste eingefügt, weil die Stellen von rechts nach links entstehen.
  • Zeile 15: Der ausgehende Übertrag wird zum eingehenden Übertrag der nächsten Stufe. Diese eine Zeile ist das „Rieseln“ des Übertrags.
  • Zeile 16: Nach der Schleife kommt der letzte Übertrag als fünfte Stelle ganz nach vorn.

So ändern sich die Werte beim ersten Aufruf nach jedem Schleifendurchlauf:

Durchlauf i va c danach ergebnis danach
1 3 [0, 1] 1 [0]
2 2 [0, 1] 1 [0, 0]
3 1 [0, 1] 1 [0, 0, 0]
4 0 [1, 0] 0 [1, 0, 0, 0]

Zum Schluss wird c = 0 vorn eingefügt: [0, 1, 0, 0, 0]. Die Werte von c sind genau die Überträge C1C_1 bis C4C_4 aus der Tabelle im Abschnitt über den Carry-Ripple-Addierer.

Achtung: Der Listenindex zählt von links (Index 0 ist das Bit ganz links), die Stufen des Addierers zählen von rechts (Stufe 0 ist das Bit ganz rechts). Beim Index i = 3 arbeitet also die Stufe VA0_0.

Arbeitsauftrag 44 (Zusatz): 2-Bit-Carry-Ripple-Addierer in CircuitVerse

Baue in CircuitVerse einen 2-Bit-Carry-Ripple-Addierer aus zwei Volladdierern (oder aus einem Halbaddierer für die niedrigste Stelle und einem Volladdierer). Teste ihn mit mehreren Zahlenpaaren und notiere die Ergebnisse.

Getestete Zahlenpaare und Ergebnisse:

Lösung vergleichen
2-Bit-Carry-Ripple-Addierer aus einem Halbaddierer und einem Volladdierer

Für die Stelle 0 genügt ein Halbaddierer, weil dort kein Übertrag ankommt. Wer zwei Volladdierer verwendet, legt an den Übertragseingang der Stelle 0 eine feste 0 an (in CircuitVerse zum Beispiel mit einem Input, der auf 0 bleibt). Mögliche Tests (C2S1S0C_2 S_1 S_0):

A1A0A_1 A_0 B1B0B_1 B_0 Ergebnis dezimal
01 01 010 1+1=21 + 1 = 2
10 01 011 2+1=32 + 1 = 3
11 01 100 3+1=43 + 1 = 4
11 11 110 3+3=63 + 3 = 6

2.4.4Weitere Übungen

Hier kannst du das Gelernte weiter üben. Die Punkte im Titel zeigen, wie schwer eine Aufgabe ist: ●○○ leicht, ●●○ mittel, ●●● knifflig. Fang mit den leichten an.

Arbeitsauftrag 45: Was liefert der Volladdierer? ●○○

Bestimme für jede Belegung die Summe SS und den ausgehenden Übertrag CausC_{\mathrm{aus}}. Addiere dazu die drei Bits wie bei der schriftlichen Addition.

AA BB CeinC_{\mathrm{ein}} SS CausC_{\mathrm{aus}}
1 0 0
0 1 1
1 1 0
0 0 1
1 1 1
Lösung vergleichen
AA BB CeinC_{\mathrm{ein}} Rechnung SS CausC_{\mathrm{aus}}
1 0 0 1+0+0=11 + 0 + 0 = 1 1 0
0 1 1 0+1+1=100 + 1 + 1 = 10 0 1
1 1 0 1+1+0=101 + 1 + 0 = 10 0 1
0 0 1 0+0+1=10 + 0 + 1 = 1 1 0
1 1 1 1+1+1=111 + 1 + 1 = 11 1 1

Das Ergebnis der Rechnung ist eine zweistellige Binärzahl CausSC_{\mathrm{aus}} S: Die rechte Ziffer ist die Summe, die linke der Übertrag. Der eingehende Übertrag zählt genauso mit wie AA und BB.

Arbeitsauftrag 46: Richtig oder falsch? ●○○

Entscheide, ob die Aussage richtig oder falsch ist. Verbessere die falschen Aussagen.

  1. Ein Volladdierer hat drei Eingänge und zwei Ausgänge.
  2. Ein Volladdierer besteht aus zwei Halbaddierern und einem UND-Gatter.
  3. Beim Carry-Ripple-Addierer wird der ausgehende Übertrag einer Stelle zum eingehenden Übertrag der nächsthöheren Stelle.
  4. In der Stelle ganz rechts ist der eingehende Übertrag immer 1.
  5. Die Summe zweier vierstelliger Binärzahlen kann fünf Stellen haben.

Deine Antwort:

Lösung vergleichen
  1. Richtig: die Eingänge AA, BB, CeinC_{\mathrm{ein}} und die Ausgänge SS, CausC_{\mathrm{aus}}.
  2. Falsch: Die beiden Überträge werden mit einem ODER-Gatter verknüpft: Caus=C1∨C2C_{\mathrm{aus}} = C_1 \lor C_2.
  3. Richtig: So entsteht die Kette, durch die der Übertrag „rieselt“.
  4. Falsch: Ganz rechts kommt kein Übertrag an. Der eingehende Übertrag ist dort immer 0.
  5. Richtig: zum Beispiel 1111+0001=100001111 + 0001 = 10000. Die fünfte Stelle ist der letzte Übertrag.
Arbeitsauftrag 47: Blick ins Innere ●○○

An einem Volladdierer liegt A=1A = 1, B=0B = 0 und Cein=1C_{\mathrm{ein}} = 1 an. Bestimme alle Zwischenwerte. Die Abbildung des Volladdierers aus zwei Halbaddierern weiter vorn in diesem Abschnitt hilft dir.

Wert so wird er berechnet Ergebnis
S1S_1 A⊕BA \oplus B (Halbaddierer 1)
C1C_1 A∧BA \land B (Halbaddierer 1)
SS S1⊕CeinS_1 \oplus C_{\mathrm{ein}} (Halbaddierer 2)
C2C_2 S1∧CeinS_1 \land C_{\mathrm{ein}} (Halbaddierer 2)
CausC_{\mathrm{aus}} C1∨C2C_1 \lor C_2 (ODER-Gatter)
Lösung vergleichen
Wert so wird er berechnet Ergebnis
S1S_1 1⊕01 \oplus 0 1
C1C_1 1∧01 \land 0 0
SS 1⊕11 \oplus 1 0
C2C_2 1∧11 \land 1 1
CausC_{\mathrm{aus}} 0∨10 \lor 1 1

Probe: 1+0+1=101 + 0 + 1 = 10, also S=0S = 0 und Caus=1C_{\mathrm{aus}} = 1. ✓ Hier entsteht der Übertrag im zweiten Halbaddierer.

Arbeitsauftrag 48: Bausteine zählen ●○○

Ein Carry-Ripple-Addierer soll zwei achtstellige Binärzahlen addieren. Alle Stellen werden mit Volladdierern gebaut.

  1. Wie viele Volladdierer braucht man?
  2. Wie viele Stellen kann das Ergebnis höchstens haben?
  3. Wie viele Gatter stecken in einem Volladdierer, wenn man ihn aus zwei Halbaddierern und einem ODER-Gatter baut? Wie viele sind es dann im ganzen Addierer?

Deine Antwort:

Lösung vergleichen
  1. Für jede Stelle einen, also 8 Volladdierer.
  2. 9 Stellen: acht Summenbits und der Übertrag ganz links.
  3. Jeder Halbaddierer hat ein XOR- und ein UND-Gatter. Ein Volladdierer hat also 2+2+1=52 + 2 + 1 = 5 Gatter. Der ganze Addierer hat 8⋅5=408 \cdot 5 = 40 Gatter.
Arbeitsauftrag 49: Eine Addition verfolgen ●●○

Verfolge die Addition 0110+01110110 + 0111 durch alle Stufen eines 4-Bit-Carry-Ripple-Addierers. Fülle die Tabelle aus und lies das Ergebnis ab. Zur Probe: 6+7=136 + 7 = 13.

Stufe AiA_i BiB_i Übertrag ein Summe SiS_i Übertrag aus
VA0_0
VA1_1
VA2_2
VA3_3

Ergebnis:

Lösung vergleichen

Es ist A3A2A1A0=0110A_3 A_2 A_1 A_0 = 0110 und B3B2B1B0=0111B_3 B_2 B_1 B_0 = 0111.

Stufe AiA_i BiB_i Übertrag ein Summe SiS_i Übertrag aus
VA0_0 0 1 C0=0C_0 = 0 S0=1S_0 = 1 C1=0C_1 = 0
VA1_1 1 1 C1=0C_1 = 0 S1=0S_1 = 0 C2=1C_2 = 1
VA2_2 1 1 C2=1C_2 = 1 S2=1S_2 = 1 C3=1C_3 = 1
VA3_3 0 0 C3=1C_3 = 1 S3=1S_3 = 1 C4=0C_4 = 0

Ergebnis: C4S3S2S1S0=01101C_4 S_3 S_2 S_1 S_0 = 01101, also 1101. Das ist 13. ✓ In der Stufe VA2_2 werden drei Einsen addiert: 1+1+1=111 + 1 + 1 = 11.

Arbeitsauftrag 50: Ein 3-Bit-Addierer ●●○

Skizziere das Blockschaltbild eines 3-Bit-Carry-Ripple-Addierers. Verwende für die Stelle ganz rechts einen Halbaddierer und für die anderen Stellen Volladdierer. Beschrifte alle Ein- und Ausgänge. Gib an, welche Ausgänge zusammen das Ergebnis bilden.

Deine Skizze:

Lösung vergleichen
Blockschaltbild eines 3-Bit-Carry-Ripple-Addierers

Das Ergebnis lautet C3S2S1S0C_3 S_2 S_1 S_0, es hat also bis zu vier Stellen. Der Halbaddierer genügt ganz rechts, weil dort kein Übertrag ankommt. Wichtig sind die Pfeile von rechts nach links: Jeder ausgehende Übertrag führt in die nächsthöhere Stelle.

Arbeitsauftrag 51: Acht Bit mit Python ●●○

Nimm die Funktionen volladdierer und carry_ripple_addierer aus der Lösung zum Auftrag 4-Bit-Carry-Ripple-Addierer in Python.

  1. Teste sie mit zwei achtstelligen Binärzahlen: 00010110+0000111100010110 + 00001111 (also 22+1522 + 15) und 11111111+0000000111111111 + 00000001 (also 255+1255 + 1).
  2. Erkläre, warum die Funktion ohne Änderung auch für acht Stellen funktioniert.

Deine Erklärung zu 2.:

Lösung vergleichen
def volladdierer(a, b, c_ein):
    s1 = int(a != b)
    c1 = int(a and b)
    s = int(s1 != c_ein)
    c2 = int(s1 and c_ein)
    c_aus = int(c1 or c2)
    return [s, c_aus]

def carry_ripple_addierer(a_bits, b_bits):
    ergebnis = []
    c = 0
    for i in range(len(a_bits) - 1, -1, -1):
        va = volladdierer(a_bits[i], b_bits[i], c)
        ergebnis.insert(0, va[0])
        c = va[1]
    ergebnis.insert(0, c)
    return ergebnis

print(carry_ripple_addierer([0, 0, 0, 1, 0, 1, 1, 0],
                            [0, 0, 0, 0, 1, 1, 1, 1]))
print(carry_ripple_addierer([1, 1, 1, 1, 1, 1, 1, 1],
                            [0, 0, 0, 0, 0, 0, 0, 1]))
[0, 0, 0, 1, 0, 0, 1, 0, 1]
[1, 0, 0, 0, 0, 0, 0, 0, 0]
  1. Das erste Ergebnis ist 000100101. Das ist 100101, also 37 ✓. Beim zweiten Ergebnis wandert der Übertrag durch alle acht Stufen. Es entsteht 100000000, also 256 ✓.
  2. Die Schleife läuft von len(a_bits) - 1 bis 0. Bei einer Liste mit acht Bits beginnt sie also beim Index 7 statt beim Index 3. Die Funktion verwendet für jede Stelle denselben Volladdierer und gibt den Übertrag einfach weiter, egal wie viele Stellen es sind. Genauso kann man in Hardware beliebig viele Volladdierer aneinanderhängen.
Arbeitsauftrag 52: Wie weit rieselt der Übertrag? ●●●
  1. Bestimme für jede Addition die Überträge C1C_1 bis C4C_4 zwischen den Stufen und das Ergebnis.
Rechnung C1C_1 C2C_2 C3C_3 C4C_4 Ergebnis
0101+00100101 + 0010
0111+00010111 + 0001
1010+01101010 + 0110
  1. Gib eine Addition zweier vierstelliger Binärzahlen an, bei der alle vier Überträge C1C_1 bis C4C_4 gleich 1 sind.
  2. Erkläre, warum ein Carry-Ripple-Addierer bei deiner Addition aus 2. am längsten braucht.

Deine Antworten zu 2. und 3.:

Lösung vergleichen
  1. Die Überträge, von rechts nach links:
Rechnung C1C_1 C2C_2 C3C_3 C4C_4 Ergebnis
0101+00100101 + 0010 0 0 0 0 0111
0111+00010111 + 0001 1 1 1 0 1000
1010+01101010 + 0110 0 1 1 1 10000
  1. Zum Beispiel 1111+0001=100001111 + 0001 = 10000: Ganz rechts ist 1+1=101 + 1 = 10, und in jeder weiteren Stelle ist 1+0+1=101 + 0 + 1 = 10. Jede Stufe erzeugt also einen Übertrag. Auch 1111+11111111 + 1111 ist eine richtige Antwort.
  2. Jede Stufe kann ihr Ergebnis erst liefern, wenn der Übertrag der Stufe rechts davon da ist. Bei 1111+00011111 + 0001 hängt jede Stufe von der vorigen ab: Der Übertrag muss von VA0_0 bis ganz nach links durch alle vier Stufen „rieseln“. Bei 0101+00100101 + 0010 entsteht dagegen nirgends ein Übertrag, der von Stufe zu Stufe weitergereicht werden muss.

2.4.5Das Wichtigste in Kürze

Selbstcheck

2.5Rückkopplung: Das Flipflop speichert ein Bit DS19

Diesen Abschnitt als PDF (S. 60–74)

Das Jupyter-Notebook aus dem Unterricht: DS19_Flipflop.ipynb. Herunterladen und in VS Code oder Jupyter öffnen.

Leitidee

Stell dir die Alarmanlage aus dem Abschnitt über Schaltungsentwurf vor: Ein Einbrecher öffnet die Tür, und der Alarm geht los. Dann schließt er die Tür wieder – und der Alarm hört sofort auf. Das ist keine gute Alarmanlage! Die Schaltung hat kein Gedächtnis: Sie reagiert nur auf das, was gerade jetzt an den Eingängen anliegt. Ein Computer muss sich aber ständig etwas merken: Zahlen, Buchstaben, Zwischenergebnisse. In diesem Abschnitt lernst du eine Schaltung kennen, die sich ein Bit merken kann: das Flipflop. Der Trick dahinter heißt Rückkopplung.

Lernziele

Nach diesem Abschnitt kannst du

2.5.1Schaltungen ohne Gedächtnis

Alle Schaltungen, die du bisher gebaut hast, funktionieren nach demselben Prinzip: Die Eingangswerte laufen von links nach rechts durch die Gatter, und am Ende kommt ein Ausgangswert heraus. Die Alarmanlage zum Beispiel berechnet

Alarm=(Tür∧Scharf)∨Rauch.\text{Alarm} = (\text{Tür} \land \text{Scharf}) \lor \text{Rauch}.

Welcher Wert am Ausgang anliegt, hängt nur davon ab, welche Werte jetzt gerade an den Eingängen anliegen. Was vor einer Sekunde war, spielt keine Rolle. Genauso ist es beim Halbaddierer und beim Volladdierer: Sie rechnen mit den Bits, die gerade anliegen. Ändert sich ein Eingang, ändert sich sofort auch das Ergebnis.

Definition: Kombinatorische Schaltung

Eine kombinatorische Schaltung ist eine Schaltung, deren Ausgangswerte nur von den aktuellen Eingangswerten abhängen. Zu jeder Kombination von Eingangswerten gehört immer derselbe Ausgangswert.

Für die Alarmanlage heißt das: Sobald die Tür wieder zu ist (Tür = 0) und kein Rauch da ist, ist auch der Alarm aus. Wir wollen aber eine Anlage, die weiter heult, bis jemand sie mit einer Taste ausschaltet. Der Ausgang soll also auch davon abhängen, was vorher passiert ist – von der Vorgeschichte. Dafür brauchen wir eine Schaltung, die sich etwas merken kann.

Merke

2.5.2Ein neues Gatter: das NOR-Gatter

Für das Flipflop brauchst du ein Gatter, das du noch nicht kennst: das NOR-Gatter. Der Name ist eine Abkürzung für „NOT OR“, also NICHT-ODER: Das Gatter rechnet zuerst ein ODER und dreht das Ergebnis dann um. Im IEC-Symbol steht deshalb ≥1\geq 1 wie beim ODER-Gatter, und am Ausgang sitzt ein kleiner Kreis. Dieser Kreis bedeutet „umdrehen“. In manchen Büchern steht an seiner Stelle ein kleiner Schrägstrich. Das bedeutet dasselbe.

Das NOR-Gatter (IEC-Symbol): ein ODER-Gatter mit dem Zeichen für „umdrehen“ am Ausgang
AA BB A∨BA \lor B NOR: ¬(A∨B)\lnot (A \lor B)
0 0 0 1
0 1 1 0
1 0 1 0
1 1 1 0

Für das Flipflop ist eine Eigenschaft besonders wichtig. Lies sie direkt aus der Tabelle ab:

Tipp

Merke dir für die folgenden Abschnitte den kurzen Satz: „Eine 1 am Eingang macht den NOR-Ausgang zu 0.“ Damit kannst du jedes Flipflop-Rätsel lösen.

2.5.3Die Idee: Rückkopplung

Bisher liefen alle Leitungen nur in eine Richtung: von den Eingängen zum Ausgang. Jetzt machen wir etwas Neues: Wir führen den Ausgang eines Gatters zurück auf einen seiner eigenen Eingänge. Das nennt man Rückkopplung.

Ein ganz einfaches Beispiel ist ein ODER-Gatter, dessen Ausgang ZZ auf den zweiten Eingang zurückgeführt wird:

Ein ODER-Gatter mit Rückkopplung: Der Ausgang Z wird auf den unteren Eingang zurückgeführt

Wir nehmen an, dass am Anfang E=0E = 0 und Z=0Z = 0 ist. Dann passiert Folgendes:

  1. Solange E=0E = 0 ist, rechnet das Gatter 0∨0=00 \lor 0 = 0. Der Ausgang bleibt 0.
  2. Jetzt wird EE kurz auf 1 gestellt. Das Gatter rechnet 1∨0=11 \lor 0 = 1, also wird Z=1Z = 1.
  3. Diese 1 läuft über die Rückkopplung zurück an den unteren Eingang.
  4. Nun wird EE wieder auf 0 gestellt. Das Gatter rechnet 0∨1=10 \lor 1 = 1. Der Ausgang bleibt 1!

Die Schaltung hat sich gemerkt, dass EE einmal 1 war. Der Ausgang hält sich über die Rückkopplung selbst fest. Leider hat diese Schaltung einen Haken: Die 1 lässt sich nie wieder löschen. Für einen brauchbaren Speicher brauchen wir also noch einen zweiten Eingang, mit dem man den Wert wieder auf 0 setzen kann. Genau das leistet das Flipflop, das du gleich kennenlernst.

Definition: Rückkopplung

Bei einer Rückkopplung wird der Ausgang einer Schaltung auf einen ihrer eigenen Eingänge zurückgeführt. Dadurch hängt der Ausgang auch von seinem eigenen früheren Wert ab.

Merke

Möglich wird das Speichern durch Rückkopplung: Der Ausgang einer Schaltung wird auf einen ihrer eigenen Eingänge zurückgeführt.

2.5.4Das SR-Flipflop aus zwei NOR-Gattern

Das einfachste Flipflop besteht aus nur zwei NOR-Gattern. Der Ausgang jedes Gatters wird an einen Eingang des anderen Gatters zurückgeführt. Man sagt: Die Gatter sind über Kreuz zurückgekoppelt.

SR-Flipflop aus zwei NOR-Gattern: Die Ausgänge sind über Kreuz zurückgekoppelt

Schau dir die Abbildung in Ruhe an und verfolge jede Leitung mit dem Finger:

Die Namen kommen aus dem Englischen:

Name englisch Bedeutung
SS Set (setzen) setzt den gespeicherten Wert auf 1
RR Reset (zurücksetzen) setzt den gespeicherten Wert auf 0
QQ – der gespeicherte Wert, also das Bit, das sich das Flipflop merkt
Q¯\overline{Q} – gesprochen „Q quer“; im Normalfall das Gegenteil von QQ

In CircuitVerse und vielen Büchern schreibt man statt Q¯\overline{Q} auch Q'.

Definition: Flipflop

Ein Flipflop ist eine Schaltung mit Rückkopplung, die ein Bit speichern kann. Der gespeicherte Wert bleibt erhalten, bis er über einen Eingang geändert wird.

Die vier Fälle

Je nachdem, welche Werte an SS und RR anliegen, macht das Flipflop etwas anderes:

SS RR QQ danach Name des Zustands
1 0 1 Setzen
0 1 0 Rücksetzen
0 0 wie vorher Speichern
1 1 – verboten

Neu ist die Zeile mit S=0S = 0 und R=0R = 0. Dort steht kein fester Wert, sondern „wie vorher“. Das gibt es bei einer kombinatorischen Schaltung nie! Das Flipflop behält einfach den Wert, den es zuletzt hatte. Genau das ist der Speicher-Effekt.

Merke

Das einfachste Beispiel ist das SR-Flipflop (Set-Reset), gebaut aus zwei über Kreuz rückgekoppelten NOR-Gattern:

Arbeitsauftrag 53: SR-Flipflop skizzieren

Decke die Abbildung des SR-Flipflops ab. Skizziere das SR-Flipflop dann aus dem Gedächtnis: zwei NOR-Gatter, deren Ausgang jeweils auf einen Eingang des anderen Gatters zurückgeführt wird. Beschrifte die freien Eingänge mit SS und RR und die beiden Ausgänge mit QQ und Q¯\overline{Q}. Vergleiche zum Schluss mit der Abbildung.

Meine Skizze:

Lösung vergleichen
SR-Flipflop aus zwei NOR-Gattern

Prüfe deine Skizze an diesen Punkten:

  • Es sind zwei NOR-Gatter (Symbol ≥1\geq 1 mit dem kleinen Kreis am Ausgang).
  • RR geht in das Gatter, dessen Ausgang QQ ist. SS geht in das Gatter, dessen Ausgang Q¯\overline{Q} ist.
  • QQ ist auf den zweiten Eingang des Gatters mit SS zurückgeführt, Q¯\overline{Q} auf den zweiten Eingang des Gatters mit RR.
  • An den Stellen, wo sich die Ausgangsleitungen verzweigen, sitzt ein Punkt.

Ob SS oben oder unten gezeichnet ist, spielt keine Rolle. Wichtig ist nur, wer mit wem verbunden ist.

2.5.5Schritt für Schritt: Was in der Rückkopplung passiert

Warum merkt sich die Schaltung wirklich etwas? Das siehst du, wenn du die Gatter nacheinander ausrechnest. In echt geht das blitzschnell, aber eben nicht gleichzeitig: Jedes Gatter reagiert erst, wenn sich einer seiner Eingänge geändert hat.

Ausgangslage: S=0S = 0, R=0R = 0, Q=0Q = 0 und Q¯=1\overline{Q} = 1. Prüfe, dass das zusammenpasst: Das obere Gatter bekommt R=0R = 0 und Q¯=1\overline{Q} = 1. Eine 1 am Eingang macht den Ausgang zu 0, also Q=0Q = 0. ✓ Das untere Gatter bekommt S=0S = 0 und Q=0Q = 0. Beide Eingänge sind 0, also Q¯=1\overline{Q} = 1. ✓ Die Schaltung ist stabil – nichts ändert sich. Sie speichert die 0.

Jetzt wird SS kurz auf 1 gestellt und danach wieder auf 0:

Schritt SS RR Was passiert? QQ Q¯\overline{Q}
0 0 0 Ausgangslage: Das Flipflop speichert 0. 0 1
1 1 0 SS wird 1. Das untere Gatter hat eine 1 am Eingang, also wird Q¯=0\overline{Q} = 0. 0 0
2 1 0 Das obere Gatter bekommt jetzt R=0R = 0 und Q¯=0\overline{Q} = 0. Beide sind 0, also wird Q=1Q = 1. 1 0
3 1 0 Das untere Gatter bekommt S=1S = 1 und Q=1Q = 1: Q¯\overline{Q} bleibt 0. Nichts ändert sich mehr. 1 0
4 0 0 SS wird wieder 0. Das untere Gatter bekommt aber noch Q=1Q = 1 über die Rückkopplung: Q¯\overline{Q} bleibt 0. Also bleibt auch Q=1Q = 1. 1 0

Schritt 4 ist der entscheidende: Der Eingang SS ist wieder 0, trotzdem bleibt Q=1Q = 1. Die 1 an QQ hält über die Rückkopplung das untere Gatter auf 0 fest, und diese 0 hält wiederum das obere Gatter auf 1. Die beiden Gatter stützen sich gegenseitig. Das Flipflop hat sich die 1 gemerkt.

So kannst du es sagen

So beschreibst du das Flipflop in Fachsprache – vom einfachen zum genauen Satz:

Arbeitsauftrag 54: Rücksetzen Schritt für Schritt

Das Flipflop speichert jetzt die 1: S=0S = 0, R=0R = 0, Q=1Q = 1, Q¯=0\overline{Q} = 0. Nun wird RR kurz auf 1 gestellt und danach wieder auf 0. Fülle die Tabelle aus. Gehe vor wie im Beispiel oben: Rechne immer nur ein Gatter aus und beschreibe kurz, was passiert.

Schritt SS RR Was passiert? QQ Q¯\overline{Q}
0 0 0 Ausgangslage: Das Flipflop speichert 1. 1 0
1 0 1
2 0 1
3 0 1
4 0 0
Lösung vergleichen
Schritt SS RR Was passiert? QQ Q¯\overline{Q}
0 0 0 Ausgangslage: Das Flipflop speichert 1. 1 0
1 0 1 RR wird 1. Das obere Gatter hat eine 1 am Eingang, also wird Q=0Q = 0. 0 0
2 0 1 Das untere Gatter bekommt S=0S = 0 und Q=0Q = 0. Beide sind 0, also wird Q¯=1\overline{Q} = 1. 0 1
3 0 1 Das obere Gatter bekommt R=1R = 1 und Q¯=1\overline{Q} = 1: QQ bleibt 0. Nichts ändert sich mehr. 0 1
4 0 0 RR wird wieder 0. Das obere Gatter bekommt aber noch Q¯=1\overline{Q} = 1: QQ bleibt 0. 0 1

Das Rücksetzen läuft genau spiegelbildlich zum Setzen ab: Diesmal reagiert zuerst das obere Gatter, weil sich dort ein Eingang (RR) geändert hat. Am Ende speichert das Flipflop die 0, und sie bleibt erhalten, obwohl RR wieder 0 ist.

Der verbotene Zustand

Was passiert, wenn S=1S = 1 und R=1R = 1 gleichzeitig anliegen? Beide Gatter haben dann eine 1 am Eingang, also sind beide Ausgänge 0: Q=0Q = 0 und Q¯=0\overline{Q} = 0. Das widerspricht der Idee, dass Q¯\overline{Q} das Gegenteil von QQ ist. Findest du also in einer Tabelle Q=0Q = 0 und Q¯=0\overline{Q} = 0, dann liegt (oder lag gerade) S=R=1S = R = 1 an.

Schlimmer ist, was danach kommt: Werden SS und RR gleichzeitig wieder 0, sehen beide Gatter nur noch Nullen und wollen beide auf 1 springen. Welches Gatter „gewinnt“, hängt von winzigen Unterschieden in der Geschwindigkeit der Bauteile ab. Was danach gespeichert ist, lässt sich nicht vorhersagen. Deshalb nennt man S=R=1S = R = 1 den verbotenen Zustand. Eine Schaltung, die ein SR-Flipflop benutzt, muss dafür sorgen, dass er nie vorkommt.

2.5.6Das Flipflop in Python nachbilden

Eine Python-Funktion, wie du sie im Kapitel über Programmierung kennengelernt hast, hat kein Gedächtnis: Zu denselben Argumenten liefert sie immer dasselbe Ergebnis – genau wie eine kombinatorische Schaltung. Ein Flipflop lässt sich deshalb nicht einfach als Funktion von SS und RR schreiben. Man kann den Speicher-Effekt aber nachbilden, wenn man den alten Wert von QQ in einer Variablen aufbewahrt und ihn der Funktion jedes Mal wieder mitgibt:

def sr_flipflop(s, r, q):
    if s == 1 and r == 0:
        return 1
    elif s == 0 and r == 1:
        return 0
    elif s == 0 and r == 0:
        return q
    else:
        print("Achtung: S = 1 und R = 1 ist der verbotene Zustand!")
        return 0

s_folge = [1, 0, 0, 0]
r_folge = [0, 0, 1, 0]
q = 0
for i in range(4):
    q = sr_flipflop(s_folge[i], r_folge[i], q)
    print(f"S={s_folge[i]} R={r_folge[i]} -> Q={q}")
S=1 R=0 -> Q=1
S=0 R=0 -> Q=1
S=0 R=1 -> Q=0
S=0 R=0 -> Q=0

Wichtig: Das Programm simuliert nur das Verhalten des Flipflops, nicht die einzelnen Gatter. Das Gedächtnis steckt hier in der Variablen q, in der echten Schaltung dagegen in der Rückkopplung.

Versuch: Probiere es aus

Ändere die beiden Listen so, dass einmal S=1S = 1 und R=1R = 1 gleichzeitig vorkommt. Was gibt das Programm aus? Setze danach zweimal hintereinander S=1S = 1, R=0R = 0. Ändert sich beim zweiten Mal etwas?

Arbeitsauftrag 55: Zustandsfolge vorhersagen

Das Flipflop speichert am Anfang die 0. Dann liegen nacheinander diese Werte an:

Schritt 1 2 3 4 5 6 7 8
SS 0 1 0 1 0 0 0 1
RR 0 0 0 0 1 0 1 0
QQ danach
  1. Trage ein, welchen Wert QQ nach jedem Schritt hat.
  2. Überprüfe deine Lösung mit dem Python-Programm oben. Ändere dazu die beiden Listen und die Anzahl der Schritte.
Lösung vergleichen
Schritt 1 2 3 4 5 6 7 8
SS 0 1 0 1 0 0 0 1
RR 0 0 0 0 1 0 1 0
QQ danach 0 1 1 1 0 0 0 1
def sr_flipflop(s, r, q):
    if s == 1 and r == 0:
        return 1
    elif s == 0 and r == 1:
        return 0
    elif s == 0 and r == 0:
        return q
    else:
        print("Achtung: S = 1 und R = 1 ist der verbotene Zustand!")
        return 0

s_folge = [0, 1, 0, 1, 0, 0, 0, 1]
r_folge = [0, 0, 0, 0, 1, 0, 1, 0]
q = 0
for i in range(8):
    q = sr_flipflop(s_folge[i], r_folge[i], q)
    print(f"S={s_folge[i]} R={r_folge[i]} -> Q={q}")
S=0 R=0 -> Q=0
S=1 R=0 -> Q=1
S=0 R=0 -> Q=1
S=1 R=0 -> Q=1
S=0 R=1 -> Q=0
S=0 R=0 -> Q=0
S=0 R=1 -> Q=0
S=1 R=0 -> Q=1

In Schritt 4 wird gesetzt, obwohl QQ schon 1 ist: Es bleibt einfach bei 1. Genauso ändert das Rücksetzen in Schritt 7 nichts, weil QQ schon 0 ist. Bei Schritt 1, 3 und 6 wird gespeichert: QQ behält den Wert aus dem Schritt davor.

2.5.7Das Flipflop in CircuitVerse bauen

Jetzt baust du das SR-Flipflop im Simulator CircuitVerse und testest den Speicher-Effekt selbst.

Tipp

CircuitVerse zeigt die US-Symbole für Gatter. Das NOR-Gatter sieht dort aus wie das gebogene ODER-Symbol mit einem kleinen Kreis an der Spitze:

Das NOR-Gatter: links das IEC-Symbol (Skript), rechts das US-Symbol (CircuitVerse)

Falls du kein NOR-Gatter findest, kannst du ein ODER-Gatter mit einem nachgeschalteten NICHT-Gatter nehmen. Das ergibt dasselbe.

So gehst du vor:

  1. Lege zwei Eingänge (Schalter) SS und RR sowie zwei Ausgänge (LEDs) QQ und Q' an.
  2. Füge zwei NOR-Gatter hinzu.
  3. Verschalte sie über Kreuz:
    • Das erste NOR-Gatter bekommt RR und den Ausgang des zweiten NOR-Gatters.
    • Das zweite NOR-Gatter bekommt SS und den Ausgang des ersten NOR-Gatters.
  4. Der Ausgang des ersten Gatters ist QQ, der Ausgang des zweiten ist Q'.
  5. Teste die Speicherwirkung: Setze kurz S=1S = 1, R=0R = 0. Dann wird QQ zu 1. Schalte danach SS wieder auf 0, also S=0S = 0, R=0R = 0. Beobachte: QQ bleibt 1, obwohl kein Eingang mehr aktiv ist!
Stolperstein
Arbeitsauftrag 56: Zustände protokollieren

Führe die Testreihenfolge in deiner CircuitVerse-Schaltung durch. Trage jeweils den beobachteten Wert von QQ ein.

Schritt SS RR QQ (beobachtet) Erklärung
1 1 0 Setzen
2 0 0 Speichern (QQ bleibt wie zuvor)
3 0 1 Rücksetzen
4 0 0 Speichern (QQ bleibt wie zuvor)
Lösung vergleichen
Schritt SS RR QQ (beobachtet) Erklärung
1 1 0 1 Setzen
2 0 0 1 Speichern (QQ bleibt wie zuvor)
3 0 1 0 Rücksetzen
4 0 0 0 Speichern (QQ bleibt wie zuvor)

Vergleiche die Schritte 2 und 4: Beide Male liegt S=0S = 0, R=0R = 0 an, aber QQ ist einmal 1 und einmal 0. Der Ausgang hängt also von der Vorgeschichte ab. Bei einer kombinatorischen Schaltung wäre das unmöglich. Siehst du in Schritt 1 den Wert 0, sind SS und RR vertauscht (siehe Stolperstein).

2.5.8Wozu braucht man Flipflops?

Ein Speicher für ein Bit

Ein Flipflop speichert genau ein Bit. Setzt man acht Flipflops nebeneinander, kann man ein ganzes Byte speichern, zum Beispiel eine Zahl von 0 bis 255 oder einen Buchstaben. So sind die Register im Prozessor aufgebaut: kleine, sehr schnelle Speicher, in denen der Prozessor die Zahlen ablegt, mit denen er gerade rechnet. Auch die schnellen Zwischenspeicher im Prozessor (der Cache) bestehen aus Speicherzellen, die wie Flipflops funktionieren.

Der große Arbeitsspeicher (RAM) eines PCs arbeitet meist mit einer anderen Technik: Dort wird jedes Bit als winzige elektrische Ladung gespeichert. Das Prinzip ist aber dasselbe: Eine Speicherzelle merkt sich eine 0 oder eine 1, bis sie überschrieben wird.

Eine Alarmanlage mit Gedächtnis

Jetzt kannst du das Problem vom Anfang lösen. Der Ausgang der bisherigen Alarm-Schaltung wird an den Eingang SS eines Flipflops angeschlossen. An RR kommt eine Taste „Quittieren“, mit der man den Alarm ausschaltet. Die Sirene hängt an QQ.

Alarmanlage mit Gedächtnis: Die Alarm-Schaltung setzt das Flipflop, die Taste setzt es zurück
Arbeitsauftrag 57: Warum Rückkopplung?

Beantworte in 2–3 Sätzen: Warum kann eine rein kombinatorische Schaltung (ohne Rückkopplung) kein Bit speichern? Was genau ermöglicht die Rückkopplung, das eine gewöhnliche Gatterkette nicht kann?

Meine Erklärung:

Lösung vergleichen

Musterantwort: Bei einer kombinatorischen Schaltung hängt der Ausgang nur von den aktuellen Eingangswerten ab. Sobald sich die Eingänge ändern, ist der alte Wert verloren – es gibt keinen Ort, an dem er aufbewahrt wird. Durch die Rückkopplung wird der Ausgang wieder an einen Eingang geführt. Deshalb hängt der neue Ausgangswert auch vom bisherigen Ausgangswert ab, und die Schaltung kann einen Wert festhalten, wenn SS und RR wieder 0 sind.

Worauf es ankommt: Du nennst den Unterschied „nur aktuelle Eingänge“ gegenüber „auch Vorgeschichte“ und erklärst, dass der Ausgang über die Rückkopplung sich selbst festhält.

Arbeitsauftrag 58 (Zusatz): Andere Flipflops

Recherchiere (zum Beispiel im Internet) den Unterschied zwischen dem SR-Flipflop und einem D-Flipflop oder einem JK-Flipflop. Welchen Vorteil haben sie gegenüber dem einfachen SR-Flipflop?

Meine Ergebnisse:

Lösung vergleichen
  • D-Flipflop (D für Data, Daten): Es hat einen Dateneingang DD und einen Takteingang. Nur wenn das Taktsignal es erlaubt, übernimmt es den Wert von DD und speichert ihn, sonst behält es seinen Wert. Weil intern SS und RR aus DD und ¬D\lnot D gebildet werden, kann der verbotene Zustand nicht auftreten.
  • JK-Flipflop: Es funktioniert wie ein SR-Flipflop (JJ setzt, KK setzt zurück). Liegt aber J=K=1J = K = 1 an, ist das nicht verboten: Der gespeicherte Wert wechselt dann (aus 0 wird 1, aus 1 wird 0).

Vorteile: Beide vermeiden den verbotenen Zustand. Außerdem arbeiten sie mit einem Takt: Viele Flipflops übernehmen ihre neuen Werte im selben Moment. So sind zum Beispiel alle acht Bits eines Registers gleichzeitig gültig. Deshalb sind in Prozessoren fast nur getaktete Flipflops eingebaut.

2.5.9Weitere Übungen

Hier kannst du das Gelernte weiter üben. Die Punkte im Titel zeigen, wie schwer eine Aufgabe ist: ●○○ leicht, ●●○ mittel, ●●● knifflig. Fang mit den leichten an.

Arbeitsauftrag 59: Mit oder ohne Gedächtnis? ●○○

Entscheide bei jedem Beispiel, ob es sich wie eine kombinatorische Schaltung verhält (ohne Gedächtnis) oder ob es sich etwas merkt. Begründe kurz.

  1. der Halbaddierer
  2. die Alarmanlage Alarm=(Tür∧Scharf)∨Rauch\text{Alarm} = (\text{Tür} \land \text{Scharf}) \lor \text{Rauch}
  3. das SR-Flipflop
  4. die Haltewunsch-Lampe im Bus: Sie geht an, wenn jemand die Stopp-Taste drückt, und bleibt an, bis der Bus an der Haltestelle die Türen öffnet.
  5. eine Türklingel: Sie tönt nur, solange jemand auf den Knopf drückt.

Deine Antwort:

Lösung vergleichen
  1. ohne Gedächtnis: Summe und Übertrag hängen nur von den Bits ab, die gerade anliegen.
  2. ohne Gedächtnis: Sobald die Tür wieder zu ist und kein Rauch da ist, ist der Alarm aus.
  3. mit Gedächtnis: Bei S=0S = 0, R=0R = 0 behält es den zuletzt gespeicherten Wert.
  4. mit Gedächtnis: Die Taste ist längst losgelassen, trotzdem leuchtet die Lampe weiter. Sie verhält sich wie ein Flipflop: Die Taste setzt, das Öffnen der Türen setzt zurück.
  5. ohne Gedächtnis: Die Klingel hängt nur davon ab, ob der Knopf jetzt gedrückt ist.

Prüffrage: Kann bei denselben Eingangswerten einmal 0 und einmal 1 herauskommen? Dann hängt der Ausgang von der Vorgeschichte ab, und die Schaltung merkt sich etwas.

Arbeitsauftrag 60: Die vier Fälle ●○○

Das SR-Flipflop speichert gerade die 1. Ergänze für jede Zeile den Namen des Zustands und den Wert von QQ danach. Wo es keinen sinnvollen Wert gibt, schreibe einen Strich.

SS RR Name des Zustands QQ danach
1 0
0 1
0 0
1 1
Lösung vergleichen
SS RR Name des Zustands QQ danach
1 0 Setzen 1
0 1 Rücksetzen 0
0 0 Speichern 1 (wie vorher)
1 1 verboten –

Bei „Speichern“ hängt das Ergebnis davon ab, was vorher gespeichert war. Hier war es die 1, also bleibt Q=1Q = 1.

Arbeitsauftrag 61: Eine kurze Folge ●○○

Das Flipflop speichert am Anfang die 1. Dann liegen nacheinander diese Werte an. Trage ein, welchen Wert QQ nach jedem Schritt hat.

Schritt 1 2 3 4 5
SS 0 0 0 1 0
RR 0 1 0 0 0
QQ danach
Lösung vergleichen
Schritt 1 2 3 4 5
SS 0 0 0 1 0
RR 0 1 0 0 0
QQ danach 1 0 0 1 1

In Schritt 1 wird gespeichert, also bleibt die 1 vom Anfang. Schritt 2 setzt zurück, Schritt 4 setzt. In den Schritten 3 und 5 wird jeweils der Wert aus dem Schritt davor gespeichert.

Arbeitsauftrag 62: Passende Eingänge finden ●●○

Jetzt umgekehrt: Das Flipflop speichert am Anfang die 0. QQ soll nach den einzelnen Schritten die Werte in der unteren Zeile haben. Bestimme passende Werte für SS und RR. Der verbotene Zustand darf nicht vorkommen.

Schritt 1 2 3 4 5 6
SS
RR
QQ danach 0 1 1 0 0 1
Lösung vergleichen

Eine mögliche Lösung:

Schritt 1 2 3 4 5 6
SS 0 1 0 0 0 1
RR 0 0 0 1 0 0
QQ danach 0 1 1 0 0 1

Wo QQ gleich bleibt (Schritte 1, 3 und 5), passt Speichern: S=0S = 0, R=0R = 0. Wo QQ auf 1 wechselt, muss gesetzt werden, wo QQ auf 0 wechselt, muss zurückgesetzt werden. Es gibt auch andere richtige Lösungen: In Schritt 3 darf man zum Beispiel noch einmal setzen (S=1S = 1, R=0R = 0), in den Schritten 1 und 5 zurücksetzen (S=0S = 0, R=1R = 1). Das ändert nichts, weil QQ den Wert schon hat.

Arbeitsauftrag 63: Haltewunsch im Bus mit Python ●●○

Die Haltewunsch-Lampe im Bus verhält sich wie ein SR-Flipflop: Die Stopp-Taste ist SS, das Öffnen der Türen ist RR, die Lampe ist QQ. Am Anfang ist die Lampe aus.

Schritt 1 2 3 4 5 6
Taste 0 1 0 1 0 0
Tür 0 0 0 0 1 0
  1. Sage voraus, ob die Lampe nach jedem Schritt leuchtet.
  2. Prüfe deine Vorhersage mit Python. Verwende die Funktion sr_flipflop aus dem Abschnitt Das Flipflop in Python nachbilden und zwei Listen taste und tuer. Gib in jedem Schritt eine Zeile wie Schritt 2: Taste=1 Tür=0 -> Lampe=1 aus.

Deine Vorhersage:

Lösung vergleichen
def sr_flipflop(s, r, q):
    if s == 1 and r == 0:
        return 1
    elif s == 0 and r == 1:
        return 0
    elif s == 0 and r == 0:
        return q
    else:
        print("Achtung: S = 1 und R = 1 ist der verbotene Zustand!")
        return 0

taste = [0, 1, 0, 1, 0, 0]
tuer = [0, 0, 0, 0, 1, 0]
lampe = 0
for i in range(6):
    lampe = sr_flipflop(taste[i], tuer[i], lampe)
    print(f"Schritt {i + 1}: Taste={taste[i]} Tür={tuer[i]} ->",
          f"Lampe={lampe}")
Schritt 1: Taste=0 Tür=0 -> Lampe=0
Schritt 2: Taste=1 Tür=0 -> Lampe=1
Schritt 3: Taste=0 Tür=0 -> Lampe=1
Schritt 4: Taste=1 Tür=0 -> Lampe=1
Schritt 5: Taste=0 Tür=1 -> Lampe=0
Schritt 6: Taste=0 Tür=0 -> Lampe=0

In Schritt 3 ist die Taste losgelassen, die Lampe leuchtet trotzdem weiter: der Speicher-Effekt. In Schritt 4 drückt eine zweite Person. Das ändert nichts, die Lampe ist schon an. Erst das Öffnen der Türen in Schritt 5 schaltet sie aus. Die Variable lampe übernimmt im Programm die Rolle der Rückkopplung.

Arbeitsauftrag 64: Ein rätselhafter Baustein ●●●

Ein Baustein mit den Eingängen XX und YY und dem Ausgang ZZ wurde getestet. Das ist das Protokoll:

Schritt 1 2 3 4 5 6
XX 1 0 0 0 1 0
YY 0 0 1 0 0 0
ZZ 1 1 0 0 1 1
  1. Begründe mit dem Protokoll, dass der Baustein keine kombinatorische Schaltung sein kann.
  2. Prüfe, ob sich der Baustein wie ein SR-Flipflop verhält, wenn XX der Eingang SS und YY der Eingang RR ist.
  3. In Schritt 7 liegt X=0X = 0, Y=1Y = 1 an, in Schritt 8 X=0X = 0, Y=0Y = 0. Sage ZZ für beide Schritte voraus.

Deine Antwort:

Lösung vergleichen
  1. In Schritt 2 und in Schritt 4 liegen dieselben Eingangswerte an (X=0X = 0, Y=0Y = 0). Trotzdem ist ZZ einmal 1 und einmal 0. Bei einer kombinatorischen Schaltung gehört zu denselben Eingangswerten immer derselbe Ausgangswert. Der Baustein muss sich also etwas merken.
  2. Ja. Schritt 1 und 5: X=1X = 1 setzt ZZ auf 1. Schritt 3: Y=1Y = 1 setzt ZZ auf 0. Schritte 2, 4 und 6: Bei X=0X = 0, Y=0Y = 0 behält ZZ jeweils den Wert aus dem Schritt davor. Das ist genau das Verhalten eines SR-Flipflops.
  3. Schritt 7 setzt zurück: Z=0Z = 0. Schritt 8 speichert: ZZ bleibt 0.

Worauf es bei 1. ankommt: Ein einziges Paar von Schritten mit gleichen Eingängen und verschiedenen Ausgängen genügt als Begründung.

2.5.10Das Wichtigste in Kürze

Selbstcheck

2.6Aussagenlogik: Schaltungen als Terme beschreiben DS20

Diesen Abschnitt als PDF (S. 75–91)

Das Jupyter-Notebook aus dem Unterricht: DS20_Aussagenlogik_Syntax.ipynb. Herunterladen und in VS Code oder Jupyter öffnen.

Leitidee

Eine Schaltung zu zeichnen dauert lange, und bei großen Schaltungen verliert man schnell den Überblick. Viel kürzer ist eine Formel wie (Tür∧Scharf)∨Rauch(\text{Tür} \land \text{Scharf}) \lor \text{Rauch}. Solche Formeln gibt es schon viel länger als Computer: Die Aussagenlogik untersucht seit über 2000 Jahren, wie man Aussagen mit „und“, „oder“ und „nicht“ verknüpft. Der Ingenieur Claude Shannon hat erkannt, dass man mit genau diesen Formeln auch Schaltungen beschreiben kann. In diesem Abschnitt lernst du, wie solche Formeln – man nennt sie Terme – genau aufgebaut sind, wie man sie als Baum zeichnet und wie man zwischen Term und Schaltung hin- und herübersetzt.

Lernziele

Nach diesem Abschnitt kannst du

2.6.1Aussagen und Aussagenvariablen

Eine Aussage ist ein Satz, der entweder wahr oder falsch ist. „Die Tür ist offen.“ ist eine Aussage. „Mach die Tür zu!“ ist keine Aussage, denn ein Befehl ist weder wahr noch falsch.

In der Aussagenlogik interessiert uns nicht, was eine Aussage genau sagt, sondern nur, ob sie wahr oder falsch ist. Deshalb ersetzt man sie durch einen Buchstaben oder ein kurzes Wort, zum Beispiel Tür\text{Tür} für „Die Tür ist offen.“ Eine solche Aussagenvariable hat einen von zwei Werten: 1 für wahr, 0 für falsch.

Das passt genau zu den Schaltungen: Eine Leitung führt Strom (1) oder keinen Strom (0). Jeder Eingang einer Schaltung entspricht einer Aussagenvariablen. Wenn wir einer Variablen einen Wert geben, sagt man: Die Variable wird mit einem Wert belegt.

Definition: Aussagenvariable

Eine Aussagenvariable ist ein Platzhalter für eine Aussage. Sie kann mit einem der beiden Wahrheitswerte 1 (wahr) oder 0 (falsch) belegt werden. Man schreibt sie meist als Großbuchstaben: AA, BB, CC …

Merke

Die Aussagenlogik beschreibt dieselben Zusammenhänge wie logische Schaltungen – nur mit Symbolen statt mit Gattern und Leitungen.

2.6.2Die drei Verknüpfungen: Negation, Konjunktion, Disjunktion

Aus einfachen Aussagen baut man zusammengesetzte Aussagen. Dafür gibt es in der Aussagenlogik drei Zeichen. Du kennst sie schon von den Gattern:

AA BB ¬A\lnot A A∧BA \land B A∨BA \lor B
0 0 1 0 0
0 1 1 0 1
1 0 0 0 1
1 1 0 1 1
Definition: Negation, Konjunktion, Disjunktion
Tipp

Eine Merkhilfe für die Zeichen: ∨\lor sieht aus wie ein „v“ – das lateinische Wort vel heißt „oder“. Das andere Zeichen ∧\land ist dann das „und“. Für das Zeichen ¬\lnot stell dir einen Haken vor, der den Wert umdreht.

Die folgende Tabelle fasst zusammen, wie die drei Verknüpfungen in der Aussagenlogik, bei den Gattern und in Python heißen:

Name Zeichen gesprochen Gatter Python
Negation ¬A\lnot A nicht AA NICHT (NOT) not a
Konjunktion A∧BA \land B AA und BB UND (AND) a and b
Disjunktion A∨BA \lor B AA oder BB ODER (OR) a or b
Merke

Entsprechung zu Schaltungen: ∧\land (Konjunktion) entspricht dem UND-Gatter, ∨\lor (Disjunktion) dem ODER-Gatter, ¬\lnot (Negation) dem NICHT-Gatter.

Stolperstein

Das „oder“ der Aussagenlogik ist kein „entweder … oder“. A∨BA \lor B ist auch dann 1, wenn beide Variablen 1 sind. Im Alltag meinen wir mit „oder“ manchmal „nur eins von beiden“ („Willst du Tee oder Kaffee?“). Das wäre XOR. Das Zeichen ⊕\oplus für XOR gehört aber nicht zu den Zeichen der Aussagenlogik, die du gleich kennenlernst. Dass man XOR auch mit ∧\land, ∨\lor und ¬\lnot ausdrücken kann, hast du im Auftrag Belegungstabelle zu einer Schaltung gesehen. Ein Verfahren, das immer funktioniert, lernst du im nächsten Abschnitt.

2.6.3Was ist ein Term? Die induktive Definition

Nicht jede Zeichenfolge ist eine sinnvolle Formel. Mit A∧∨BA \land \lor B kann niemand etwas anfangen. Wir brauchen also eine genaue Regel, welche Zeichenfolgen erlaubt sind. Die erlaubten Formeln heißen aussagenlogische Terme.

Die Regel funktioniert wie ein Baukasten: Man fängt mit den kleinsten Bausteinen an, den Variablen. Dann gibt es Regeln, wie man aus fertigen Termen größere Terme baut. Jeder Term, den man so gebaut hat, darf wieder als Baustein verwendet werden. Eine solche Definition, die Schritt für Schritt vom Kleinen zum Großen aufbaut, nennt man induktiv.

Merke

Induktive Definition eines aussagenlogischen Terms:

  1. Jede Aussagenvariable (z. B. AA, BB, CC) ist ein Term.
  2. Ist tt ein Term, so ist auch ¬t\lnot t (Negation) ein Term.
  3. Sind t1t_1 und t2t_2 Terme, so sind auch (t1∧t2)(t_1 \land t_2) (Konjunktion, entspricht AND) und (t1∨t2)(t_1 \lor t_2) (Disjunktion, entspricht OR) Terme.
  4. Nichts anderes ist ein Term.

Die Buchstaben tt, t1t_1 und t2t_2 stehen hier nicht für Variablen, sondern für beliebige Terme – kleine wie AA oder große wie (A∧¬B)(A \land \lnot B). Regel 4 ist wichtig: Sie sagt, dass es keine anderen Terme gibt als die, die man mit den Regeln 1 bis 3 bauen kann.

Beispiel

Wir bauen den Term ((A∧B)∨¬C)((A \land B) \lor \lnot C) Schritt für Schritt auf:

Schritt gebauter Term Regel gebaut aus
1 AA, BB, CC 1 –
2 (A∧B)(A \land B) 3 t1=At_1 = A, t2=Bt_2 = B
3 ¬C\lnot C 2 t=Ct = C
4 ((A∧B)∨¬C)((A \land B) \lor \lnot C) 3 t1=(A∧B)t_1 = (A \land B), t2=¬Ct_2 = \lnot C

Weil jeder Schritt eine der Regeln benutzt, ist ((A∧B)∨¬C)((A \land B) \lor \lnot C) ein Term.

Umgekehrt kann man bei einer Zeichenfolge prüfen, ob sie ein Term ist. Diese Zeichenfolgen sind keine Terme:

Zeichenfolge Warum kein Term?
A∧A \land Für ∧\land braucht man zwei Terme, rechts fehlt einer.
∨AB\lor A B Das Zeichen ∨\lor muss zwischen zwei Termen stehen.
(A∨B(A \lor B Die schließende Klammer fehlt.
A¬BA \lnot B ¬\lnot steht vor einem Term, nicht zwischen zwei Termen.
A+BA + B Das Zeichen ++ kommt in den Regeln nicht vor.

Klammern sparen

Nach der strengen Definition stehen um jede Konjunktion und jede Disjunktion Klammern. Bei großen Termen wird das unübersichtlich. Deshalb gibt es Vereinbarungen, wann man Klammern weglassen darf:

  1. Die äußersten Klammern dürfen weg: (A∧B)∨¬C(A \land B) \lor \lnot C statt ((A∧B)∨¬C)((A \land B) \lor \lnot C).
  2. Das Zeichen ¬\lnot bezieht sich nur auf das, was direkt dahinter steht. ¬A∧B\lnot A \land B bedeutet (¬A)∧B(\lnot A) \land B. Soll ¬\lnot für mehr gelten, braucht man Klammern: ¬(A∧B)\lnot (A \land B).
  3. Bei lauter ∧\land (oder lauter ∨\lor) ist die Klammerung egal, das Ergebnis ist immer dasselbe. Man schreibt einfach A∧B∧CA \land B \land C statt ((A∧B)∧C)((A \land B) \land C).
  4. ∧\land bindet stärker als ∨\lor – so wie Punkt vor Strich. A∧B∨CA \land B \lor C bedeutet also (A∧B)∨C(A \land B) \lor C.

Python hält sich übrigens an dieselbe Reihenfolge: zuerst not, dann and, dann or.

Tipp

Die letzte Vereinbarung ist leicht zu vergessen. Setze deshalb Klammern, sobald ∧\land und ∨\lor zusammen vorkommen. Schreibe also lieber (A∧B)∨C(A \land B) \lor C als A∧B∨CA \land B \lor C. Zu viele Klammern schaden nie.

Stolperstein

¬(A∨B)\lnot (A \lor B) und ¬A∨B\lnot A \lor B sind zwei verschiedene Terme! Beim ersten wird das Ergebnis von A∨BA \lor B umgedreht. Beim zweiten wird nur AA umgedreht. Setze für A=0A = 0, B=1B = 1 ein: ¬(0∨1)=¬1=0\lnot (0 \lor 1) = \lnot 1 = 0, aber ¬0∨1=1∨1=1\lnot 0 \lor 1 = 1 \lor 1 = 1.

Arbeitsauftrag 65: Term oder kein Term?

Entscheide bei jeder Zeichenfolge, ob sie nach der strengen induktiven Definition ein Term ist. Begründe kurz. Gib bei den Termen an, in welcher Reihenfolge sie mit den Regeln aufgebaut werden.

  1. (A∨¬B)(A \lor \lnot B)
  2. ¬¬A\lnot\lnot A
  3. (A∧B∨)(A \land B \lor)
  4. (¬(A∨B)∧C)(\lnot (A \lor B) \land C)
  5. ∧(A,B)\land (A, B)

Meine Antworten:

Lösung vergleichen
  1. Term. BB ist ein Term (Regel 1), also auch ¬B\lnot B (Regel 2). Mit t1=At_1 = A und t2=¬Bt_2 = \lnot B ist (A∨¬B)(A \lor \lnot B) ein Term (Regel 3).

  2. Term. AA ist ein Term, also auch ¬A\lnot A (Regel 2). Regel 2 darf man noch einmal anwenden: ¬¬A\lnot\lnot A ist ein Term. (Er hat übrigens immer denselben Wert wie AA.)

  3. Kein Term. Hinter dem ∨\lor fehlt der zweite Term.

  4. Term. (A∨B)(A \lor B) ist ein Term (Regel 3), also auch ¬(A∨B)\lnot (A \lor B) (Regel 2). Mit t1=¬(A∨B)t_1 = \lnot (A \lor B) und t2=Ct_2 = C ist (¬(A∨B)∧C)(\lnot (A \lor B) \land C) ein Term (Regel 3).

  5. Kein Term. So schreibt man in manchen Programmiersprachen, aber nicht in der Aussagenlogik. Das Zeichen ∧\land muss zwischen zwei Termen stehen, und Kommas kommen in den Regeln nicht vor.

2.6.4Termbäume

Ein Term ist eine Zeichenkette. Seinen Aufbau sieht man aber besser in einem Bild. Dafür zeichnet man einen Termbaum. Er steht – anders als echte Bäume – auf dem Kopf:

Hier ist der Termbaum zum Term (A∧B)∨¬C(A \land B) \lor \lnot C:

Termbaum zu (A \land B) \lor \lnot C: Der Operator, der zuletzt ausgewertet wird, steht ganz oben (Wurzel)

Vergleiche den Baum mit dem schrittweisen Aufbau im Beispiel oben: Jede Anwendung einer Regel ist ein Knoten im Baum. Die Variablen aus Schritt 1 sind die Blätter. Der letzte Schritt (∨\lor) ist die Wurzel.

Definition: Termbaum

Ein Termbaum stellt einen Term als Baumstruktur dar. Die Blätter sind die Aussagenvariablen, die inneren Knoten die Operatoren (¬\lnot, ∧\land, ∨\lor). Der Operator, der zuletzt ausgewertet wird, steht an der Wurzel.

Merke

Ein Termbaum stellt einen Term als Baumstruktur dar: Die Blätter sind die Aussagenvariablen, die inneren Knoten die Operatoren (¬\lnot, ∧\land, ∨\lor).

So zeichnest du einen Termbaum

  1. Suche den Operator, der zuletzt ausgerechnet wird. Das ist der Operator, der außerhalb aller Klammern steht. Stehen dort mehrere, nimm den schwächsten (∨\lor vor ∧\land vor ¬\lnot). Er wird die Wurzel.
  2. Zeichne darunter seine Teilterme. Bei ∧\land und ∨\lor ist das der Teil links und der Teil rechts vom Zeichen. Bei ¬\lnot ist es das, was dahinter steht.
  3. Wiederhole Schritt 1 und 2 für jeden Teilterm, bis nur noch Variablen übrig sind.

Für (A∧B)∨¬C(A \land B) \lor \lnot C: Außerhalb der Klammer stehen ∨\lor und ¬\lnot. Das schwächere Zeichen ist ∨\lor, also ist ∨\lor die Wurzel. Links davon steht (A∧B)(A \land B), rechts ¬C\lnot C. Beide werden auf dieselbe Weise weiter zerlegt.

Einen Term am Baum ausrechnen

Am Termbaum kannst du auch gut ausrechnen, welchen Wert ein Term für eine bestimmte Belegung hat. Du rechnest von unten nach oben. Für A=1A = 1, B=0B = 0, C=1C = 1 sieht das so aus (die Werte stehen rot neben den Knoten):

Auswertung von (A \land B) \lor \lnot C für A = 1, B = 0, C = 1: Die Werte werden von den Blättern zur Wurzel weitergereicht
Arbeitsauftrag 66: Vom Term zum Termbaum

Zeichne den Termbaum zum Term

¬(A∨B)∧C.\lnot (A \lor B) \land C.

Mein Termbaum:

Lösung vergleichen
Termbaum zu \lnot (A \lor B) \land C

Außerhalb der Klammer stehen ¬\lnot und ∧\land. Das schwächere Zeichen ist ∧\land, also ist ∧\land die Wurzel. Links hängt der Teilterm ¬(A∨B)\lnot (A \lor B), rechts CC. Unter ¬\lnot hängt nur ein Teilterm, nämlich A∨BA \lor B.

Häufiger Fehler: ¬\lnot als Wurzel nehmen. Das ¬\lnot gilt aber nur für die Klammer (A∨B)(A \lor B), nicht für CC.

2.6.5Vom Term zur Schaltung und zurück

Ein Termbaum und eine Schaltung haben denselben Aufbau. Dreh den Termbaum in Gedanken um 90 Grad, sodass die Wurzel rechts steht:

So sieht die Schaltung zum Term (A∧B)∨¬C(A \land B) \lor \lnot C aus:

Schaltung zum Term (A \land B) \lor \lnot C: Jeder Knoten des Termbaums ist ein Gatter

Die Schaltung braucht so viele Gatter, wie der Termbaum innere Knoten hat – hier drei. Zum Bauen gehst du von innen nach außen vor: zuerst die Gatter für die innersten Teilterme (A∧BA \land B und ¬C\lnot C), zuletzt das Gatter der Wurzel.

Von der Schaltung zum Term

Der umgekehrte Weg geht genauso. Schreibe an jede Leitung, welchen Teilterm sie führt. Beginne an den Eingängen und arbeite dich nach rechts vor:

  1. An den Eingängen stehen die Variablen.
  2. Am Ausgang jedes Gatters steht der Teilterm, der aus seinen Eingängen entsteht. Ein UND-Gatter mit den Eingängen AA und BB liefert zum Beispiel A∧BA \land B.
  3. Am Ausgang der Schaltung steht dann der gesamte Term.

Setze dabei um jeden Teilterm, der in ein weiteres Gatter läuft, Klammern. Überflüssige Klammern kannst du am Ende wieder weglassen.

So kannst du es sagen

So sprichst du über Terme und Schaltungen – vom einfachen zum genauen Satz:

Arbeitsauftrag 67: Schaltung beschreiben

Gib den Term an, den die folgende Schaltung darstellt. Zeichne anschließend den Termbaum.

Eine Schaltung mit drei Eingängen

Term und Termbaum:

Lösung vergleichen

Das NICHT-Gatter liefert ¬A\lnot A. Das ODER-Gatter verknüpft ¬A\lnot A mit BB zu ¬A∨B\lnot A \lor B. Das UND-Gatter verknüpft dieses Ergebnis mit CC. Der Term lautet also

(¬A∨B)∧C.(\lnot A \lor B) \land C.

Die Klammer ist nötig, weil ∧\land sonst stärker binden würde als ∨\lor.

Termbaum zu (\lnot A \lor B) \land C
Arbeitsauftrag 68: Termbaum der Alarmanlage

Im Abschnitt über Schaltungsentwurf hast du die Alarmanlage gebaut:

Alarm=(Tür∧Scharf)∨Rauch\text{Alarm} = (\text{Tür} \land \text{Scharf}) \lor \text{Rauch}

Zeichne den Termbaum zu diesem Term.

Mein Termbaum:

Lösung vergleichen
Termbaum zu (\text{Tür} \land \text{Scharf}) \lor \text{Rauch}

Die Wurzel ist ∨\lor, denn es steht außerhalb der Klammer. Die Variablennamen dürfen ganze Wörter sein. Der Baum hat zwei innere Knoten, also besteht die Schaltung aus zwei Gattern: einem UND- und einem ODER-Gatter.

Mit Python kannst du die Belegungstabelle ausgeben. Wie solche Programme aufgebaut sind, wird weiter unten im Abschnitt Terme mit Python kontrollieren Zeile für Zeile erklärt.

def alarm(tuer, scharf, rauch):
    return int((tuer and scharf) or rauch)

for tuer in [0, 1]:
    for scharf in [0, 1]:
        for rauch in [0, 1]:
            belegung = f"Tuer={tuer} Scharf={scharf} Rauch={rauch}"
            print(belegung, "->", alarm(tuer, scharf, rauch))
Tuer=0 Scharf=0 Rauch=0 -> 0
Tuer=0 Scharf=0 Rauch=1 -> 1
Tuer=0 Scharf=1 Rauch=0 -> 0
Tuer=0 Scharf=1 Rauch=1 -> 1
Tuer=1 Scharf=0 Rauch=0 -> 0
Tuer=1 Scharf=0 Rauch=1 -> 1
Tuer=1 Scharf=1 Rauch=0 -> 1
Tuer=1 Scharf=1 Rauch=1 -> 1

2.6.6Terme mit Python kontrollieren

Terme lassen sich direkt als Python-Ausdrücke schreiben: and für ∧\land, or für ∨\lor, not für ¬\lnot. Damit kannst du prüfen, ob du einen Term richtig verstanden hast. Das folgende Programm gibt die Belegungstabelle zum Term ¬(A∨B)∧C\lnot (A \lor B) \land C aus:

def term1(a, b, c):
    return int(not (a or b) and c)

print("Term 1: not (A or B) and C")
for a in [0, 1]:
    for b in [0, 1]:
        for c in [0, 1]:
            print(f"A={a} B={b} C={c} -> {term1(a, b, c)}")
Term 1: not (A or B) and C
A=0 B=0 C=0 -> 0
A=0 B=0 C=1 -> 1
A=0 B=1 C=0 -> 0
A=0 B=1 C=1 -> 0
A=1 B=0 C=0 -> 0
A=1 B=0 C=1 -> 0
A=1 B=1 C=0 -> 0
A=1 B=1 C=1 -> 0

Der Term ist nur bei A=0A = 0, B=0B = 0, C=1C = 1 wahr. Das passt zur Bedeutung: „Weder AA noch BB, aber CC.“

Arbeitsauftrag 69: Vom Term zur Schaltung

Jetzt geht es in die umgekehrte Richtung. Nimm den Term ¬(A∨B)∧C\lnot (A \lor B) \land C aus dem Auftrag Vom Term zum Termbaum.

  1. Skizziere die zugehörige Schaltung mit IEC-Symbolen.
  2. Baue die Schaltung in CircuitVerse: ein ODER-Gatter für A∨BA \lor B, ein NICHT-Gatter dahinter und ein UND-Gatter, das das Ergebnis mit CC verknüpft.
  3. Teste alle 8 Belegungen. Vergleiche mit deinem Termbaum und mit der Ausgabe des Python-Programms oben.

Meine Skizze:

Lösung vergleichen
Schaltung zum Term \lnot (A \lor B) \land C

Die Schaltung hat drei Gatter, so viele, wie der Termbaum innere Knoten hat. Beim Testen in CircuitVerse leuchtet der Ausgang nur bei A=0A = 0, B=0B = 0, C=1C = 1 – genau wie in der Python-Ausgabe:

AA BB CC A∨BA \lor B ¬(A∨B)\lnot (A \lor B) ¬(A∨B)∧C\lnot (A \lor B) \land C
0 0 0 0 1 0
0 0 1 0 1 1
0 1 0 1 0 0
0 1 1 1 0 0
1 0 0 1 0 0
1 0 1 1 0 0
1 1 0 1 0 0
1 1 1 1 0 0
Arbeitsauftrag 70: Genau eine von drei

Formuliere einen aussagenlogischen Term für folgende Situation: „Der Ausgang ist 1, wenn genau eine der drei Variablen AA, BB, CC den Wert 1 hat.“ Notiere den Term symbolisch und als Python-Funktion term3(a, b, c). Prüfe deine Funktion mit drei geschachtelten Schleifen.

Tipp: Überlege, in welchen Fällen der Ausgang 1 sein soll. Beschreibe jeden Fall mit einer Konjunktion, die genau auf diesen Fall passt. Verbinde dann alle Fälle mit ∨\lor.

Mein Term:

Lösung vergleichen

Es gibt drei passende Fälle: Nur AA ist 1, nur BB ist 1 oder nur CC ist 1. „Nur AA“ heißt: AA ist 1, BB und CC sind 0, also A∧¬B∧¬CA \land \lnot B \land \lnot C. Die drei Fälle werden mit ∨\lor verbunden:

(A∧¬B∧¬C)∨(¬A∧B∧¬C)∨(¬A∧¬B∧C)(A \land \lnot B \land \lnot C) \lor (\lnot A \land B \land \lnot C) \lor (\lnot A \land \lnot B \land C)

def term3(a, b, c):
    nur_a = a and not b and not c
    nur_b = not a and b and not c
    nur_c = not a and not b and c
    return int(nur_a or nur_b or nur_c)

for a in [0, 1]:
    for b in [0, 1]:
        for c in [0, 1]:
            print(f"A={a} B={b} C={c} -> {term3(a, b, c)}")
A=0 B=0 C=0 -> 0
A=0 B=0 C=1 -> 1
A=0 B=1 C=0 -> 1
A=0 B=1 C=1 -> 0
A=1 B=0 C=0 -> 1
A=1 B=0 C=1 -> 0
A=1 B=1 C=0 -> 0
A=1 B=1 C=1 -> 0

Genau in den drei Zeilen mit einer einzigen 1 ist das Ergebnis 1. Die Hilfsvariablen nur_a, nur_b und nur_c machen die Funktion übersichtlicher. Du kannst auch alles in eine einzige return-Zeile schreiben. Andere richtige Terme sind möglich, solange die Tabelle stimmt. Ein häufiger Fehler ist A∨B∨CA \lor B \lor C: Dieser Term ist auch 1, wenn zwei oder drei Variablen 1 sind.

2.6.7Weitere Übungen

Hier kannst du das Gelernte weiter üben. Die Punkte im Titel zeigen, wie schwer eine Aufgabe ist: ●○○ leicht, ●●○ mittel, ●●● knifflig. Fang mit den leichten an.

Arbeitsauftrag 71: Drei Schreibweisen ●○○

Ergänze die Tabelle.

Name Zeichen Gatter Python
Negation
∧\land
ODER (OR)
Lösung vergleichen
Name Zeichen Gatter Python
Negation ¬\lnot NICHT (NOT) not
Konjunktion ∧\land UND (AND) and
Disjunktion ∨\lor ODER (OR) or

Merkhilfe: Das Zeichen ∨\lor sieht aus wie ein „v“ wie in vel, dem lateinischen Wort für „oder“.

Arbeitsauftrag 72: Termbäume zeichnen ●○○

Zeichne zu jedem Term den Termbaum.

  1. ¬A∨B\lnot A \lor B \qquad b) (A∨B)∧C(A \lor B) \land C \qquad c) ¬(A∨¬B)\lnot (A \lor \lnot B)

Deine Termbäume:

Lösung vergleichen
Termbäume zu a) \lnot A \lor B, b) (A \lor B) \land C und c) \lnot (A \lor \lnot B)
  1. Das ¬\lnot gilt nur für AA. Die Wurzel ist deshalb ∨\lor.
  2. Die Klammer wird zuerst ausgewertet, die Wurzel ist ∧\land.
  3. Das äußere ¬\lnot gilt für die ganze Klammer, es ist die Wurzel. Darunter hängt A∨¬BA \lor \lnot B, und das zweite ¬\lnot gilt nur für BB.
Arbeitsauftrag 73: Vom Termbaum zum Term ●○○

Gib zu jedem Termbaum den Term an. Setze Klammern, wo sie nötig sind.

Drei Termbäume a), b) und c)

Deine Terme:

Lösung vergleichen
  1. ¬A∨(B∧C)\lnot A \lor (B \land C)
  2. ¬(A∧B)\lnot (A \land B)
  3. (A∨B)∧(A∨C)(A \lor B) \land (A \lor C)

Jeder Operator, der in einem Teilbaum unter einem anderen Operator hängt, wird zuerst ausgewertet. Bei b) muss deshalb eine Klammer um A∧BA \land B, sonst würde das ¬\lnot nur für AA gelten. Bei a) zeigt die Klammer um B∧CB \land C, dass das UND zuerst ausgewertet wird. In c) darf dieselbe Variable in zwei Blättern vorkommen.

Arbeitsauftrag 74: Term oder kein Term? ●●○

Entscheide mit der induktiven Definition, ob die Zeichenfolge ein aussagenlogischer Term ist. Begründe mit den Regeln.

  1. AA
  2. (A∧¬C)(A \land \lnot C)
  3. (A∨B∨)(A \lor B \lor)
  4. ((A∨B)∧¬C)((A \lor B) \land \lnot C)
  5. (A⊕B)(A \oplus B)
  6. ¬∧A\lnot \land A

Deine Antworten:

Lösung vergleichen
  1. Term nach Regel 1: Jede Aussagenvariable ist ein Term.
  2. Term: CC ist ein Term (Regel 1), also auch ¬C\lnot C (Regel 2). Mit t1=At_1 = A und t2=¬Ct_2 = \lnot C ist (A∧¬C)(A \land \lnot C) ein Term (Regel 3).
  3. Kein Term: Hinter dem zweiten ∨\lor fehlt ein Term.
  4. Term: (A∨B)(A \lor B) ist ein Term (Regel 3), ¬C\lnot C ebenfalls (Regel 2). Beide werden mit Regel 3 zu ((A∨B)∧¬C)((A \lor B) \land \lnot C) verbunden.
  5. Kein Term: Das Zeichen ⊕\oplus kommt in den Regeln nicht vor. Nach Regel 4 ist nichts anderes ein Term. XOR muss man in der Aussagenlogik mit ∧\land, ∨\lor und ¬\lnot ausdrücken.
  6. Kein Term: ∧\land muss zwischen zwei Termen stehen, und ¬\lnot muss vor einem Term stehen. Hier steht ¬\lnot vor einem ∧\land.
Arbeitsauftrag 75: Schaltung, Term und Termbaum ●●○
  1. Gib den Term an, den die Schaltung darstellt.
  2. Zeichne den Termbaum.
  3. Berechne den Wert von ZZ für die Belegung A=0A = 0, B=1B = 1, C=0C = 0. Schreibe die Zwischenwerte an die Knoten deines Termbaums.
Eine Schaltung mit drei Gattern

Term, Termbaum und Wert:

Lösung vergleichen

Das NICHT-Gatter liefert ¬A\lnot A, das ODER-Gatter B∨CB \lor C. Das UND-Gatter verknüpft beide:

Z=¬A∧(B∨C)Z = \lnot A \land (B \lor C)

Termbaum zu \lnot A \land (B \lor C) mit den Werten für A = 0, B = 1, C = 0 (rot)

Von unten nach oben: ¬0=1\lnot 0 = 1 und 1∨0=11 \lor 0 = 1, an der Wurzel 1∧1=11 \land 1 = 1. Also ist Z=1Z = 1.

Die Klammer um B∨CB \lor C ist nötig. Sie zeigt, dass das ODER-Gatter zuerst rechnet und sein Ergebnis in das UND-Gatter geht.

Arbeitsauftrag 76: Genau zwei von drei ●●●

Formuliere einen aussagenlogischen Term für die Situation: „Der Ausgang ist 1, wenn genau zwei der drei Variablen AA, BB, CC den Wert 1 haben.“ Notiere den Term symbolisch und als Python-Funktion genau_zwei(a, b, c). Prüfe die Funktion mit drei geschachtelten Schleifen.

Tipp

Geh vor wie im Auftrag Genau eine von drei: Überlege, welche Fälle es gibt. Beschreibe jeden Fall mit einer Konjunktion, in der alle drei Variablen vorkommen. Verbinde die Fälle mit ∨\lor.

Dein Term:

Lösung vergleichen

Es gibt drei Fälle: Nur CC ist 0, nur BB ist 0 oder nur AA ist 0. „Nur CC ist 0“ heißt: AA und BB sind 1, CC ist 0, also A∧B∧¬CA \land B \land \lnot C. Die drei Fälle werden mit ∨\lor verbunden:

(A∧B∧¬C)∨(A∧¬B∧C)∨(¬A∧B∧C)(A \land B \land \lnot C) \lor (A \land \lnot B \land C) \lor (\lnot A \land B \land C)

def genau_zwei(a, b, c):
    ohne_c = a and b and not c
    ohne_b = a and not b and c
    ohne_a = not a and b and c
    return int(ohne_c or ohne_b or ohne_a)

for a in [0, 1]:
    for b in [0, 1]:
        for c in [0, 1]:
            print(f"A={a} B={b} C={c} -> {genau_zwei(a, b, c)}")
A=0 B=0 C=0 -> 0
A=0 B=0 C=1 -> 0
A=0 B=1 C=0 -> 0
A=0 B=1 C=1 -> 1
A=1 B=0 C=0 -> 0
A=1 B=0 C=1 -> 1
A=1 B=1 C=0 -> 1
A=1 B=1 C=1 -> 0

Genau in den drei Zeilen mit zwei Einsen ist das Ergebnis 1. Ein häufiger Fehler ist die Mehrheitsschaltung (A∧B)∨(B∧C)∨(A∧C)(A \land B) \lor (B \land C) \lor (A \land C): Sie liefert auch in der letzten Zeile eine 1, obwohl dort alle drei Variablen 1 sind.

2.6.8Das Wichtigste in Kürze

Selbstcheck

2.7Belegungstabellen, Äquivalenz und disjunktive Normalform DS21

Diesen Abschnitt als PDF (S. 92–105)

Das Jupyter-Notebook aus dem Unterricht: DS21_DNF_Aequivalenz.ipynb. Herunterladen und in VS Code oder Jupyter öffnen.

Leitidee

Ein Term beschreibt eine Schaltung. Aber welche Werte liefert sie eigentlich? Das zeigt die Belegungstabelle. Spannend wird es, wenn man zwei Terme vergleicht: Oft sehen zwei Terme ganz verschieden aus und liefern trotzdem in jeder Zeile dasselbe. Dann beschreiben sie Schaltungen, die genau dasselbe tun – und man kann die billigere bauen. Umgekehrt hat man beim Entwurf oft nur eine Tabelle: „In diesen Fällen soll der Ausgang 1 sein.“ Mit der disjunktiven Normalform lernst du ein Verfahren, das zu jeder solchen Tabelle zuverlässig einen passenden Term liefert.

Lernziele

Nach diesem Abschnitt kannst du

2.7.1Belegungstabellen zu Termen

Eine Belegungstabelle enthält für jede mögliche Belegung der Variablen eine Zeile. Bei nn Variablen gibt es 2n2^n Belegungen: bei zwei Variablen 4, bei drei Variablen 8, bei vier Variablen 16.

Damit keine Zeile fehlt, schreibst du die Belegungen immer in derselben Reihenfolge auf: Du zählst im Binärsystem von 000000 bis 111111. Dann wechselt die letzte Variable in jeder Zeile, die mittlere alle zwei Zeilen und die erste alle vier Zeilen. Die erste Spalte besteht also aus vier Nullen und vier Einsen, die zweite aus zwei Nullen, zwei Einsen, zwei Nullen, zwei Einsen.

Bei größeren Termen rechnet man nicht alles auf einmal aus. Man legt Hilfsspalten für die Teilterme an – und zwar in der Reihenfolge, in der man sie im Termbaum von unten nach oben findet. Für den Term (A∧¬B)∨C(A \land \lnot B) \lor C sind das zuerst ¬B\lnot B, dann A∧¬BA \land \lnot B und zuletzt der ganze Term:

AA BB CC ¬B\lnot B A∧¬BA \land \lnot B (A∧¬B)∨C(A \land \lnot B) \lor C
0 0 0 1 0 0
0 0 1 1 0 1
0 1 0 0 0 0
0 1 1 0 0 1
1 0 0 1 1 1
1 0 1 1 1 1
1 1 0 0 0 0
1 1 1 0 0 1

Jede Hilfsspalte entsteht aus Spalten weiter links. Die Spalte A∧¬BA \land \lnot B zum Beispiel ist nur dort 1, wo sowohl in der Spalte AA als auch in der Spalte ¬B\lnot B eine 1 steht. Die letzte Spalte ist 1, wo in der Spalte A∧¬BA \land \lnot B oder in der Spalte CC eine 1 steht.

Tipp

Lies eine Zeile der Belegungstabelle immer als ganzen Satz. Die fünfte Zeile besagt: „Ist AA mit 1, BB mit 0 und CC mit 0 belegt, dann hat der Term den Wert 1.“

Arbeitsauftrag 77: Vom Term zur Belegungstabelle

Erstelle von Hand die vollständige Belegungstabelle zum Term

(A∨B)∧¬C.(A \lor B) \land \lnot C.

Überprüfe dein Ergebnis anschließend mit einem Python-Programm.

AA BB CC A∨BA \lor B ¬C\lnot C (A∨B)∧¬C(A \lor B) \land \lnot C
0 0 0
0 0 1
0 1 0
0 1 1
1 0 0
1 0 1
1 1 0
1 1 1
Lösung vergleichen
AA BB CC A∨BA \lor B ¬C\lnot C (A∨B)∧¬C(A \lor B) \land \lnot C
0 0 0 0 1 0
0 0 1 0 0 0
0 1 0 1 1 1
0 1 1 1 0 0
1 0 0 1 1 1
1 0 1 1 0 0
1 1 0 1 1 1
1 1 1 1 0 0
def mein_term(a, b, c):
    return int((a or b) and (not c))

for a in [0, 1]:
    for b in [0, 1]:
        for c in [0, 1]:
            print(f"A={a} B={b} C={c} -> {mein_term(a, b, c)}")
A=0 B=0 C=0 -> 0
A=0 B=0 C=1 -> 0
A=0 B=1 C=0 -> 1
A=0 B=1 C=1 -> 0
A=1 B=0 C=0 -> 1
A=1 B=0 C=1 -> 0
A=1 B=1 C=0 -> 1
A=1 B=1 C=1 -> 0

Die Ausgabe stimmt mit der letzten Spalte der Tabelle überein. Der Term ist genau dann 1, wenn mindestens eine der Variablen AA, BB den Wert 1 hat und CC den Wert 0 hat.

2.7.2Äquivalenz: verschiedene Terme, gleiche Wirkung

Vergleiche die beiden Terme A∨(A∧B)A \lor (A \land B) und AA. Sie sehen ganz verschieden aus. Schau dir aber ihre Belegungstabellen an:

AA BB A∧BA \land B A∨(A∧B)A \lor (A \land B)
0 0 0 0
0 1 0 0
1 0 0 1
1 1 1 1

Die letzte Spalte stimmt Zeile für Zeile mit der Spalte AA überein! Egal, wie man AA und BB belegt: Beide Terme liefern immer denselben Wert. Man sagt: Die beiden Terme sind äquivalent (gleichwertig).

Für Schaltungen ist das sehr nützlich. Die Schaltung zu A∨(A∧B)A \lor (A \land B) braucht ein UND- und ein ODER-Gatter. Die Schaltung zu AA braucht gar kein Gatter – der Ausgang ist einfach mit dem Eingang AA verbunden. Beide Schaltungen verhalten sich genau gleich. Natürlich baut man dann die einfachere.

Definition: Äquivalenz

Zwei aussagenlogische Terme heißen äquivalent, wenn sie für jede mögliche Belegung der Variablen denselben Wert liefern, wenn also ihre Belegungstabellen übereinstimmen.

Beachte: „äquivalent“ ist ein Wort, mit dem wir über zwei Terme sprechen – so wie man über zwei Wörter sagen kann, dass sie gleich lang sind. Es ist kein neues Zeichen, das man in einen Term hineinschreibt wie ∧\land oder ∨\lor. Wir schreiben deshalb einfach: „Die Terme A∨(A∧B)A \lor (A \land B) und AA sind äquivalent.“

Merke

Zwei aussagenlogische Terme heißen äquivalent, wenn sie für jede mögliche Belegung denselben Wahrheitswert liefern – also dieselbe Belegungstabelle besitzen. Äquivalenz ist ein Begriff über Terme, kein eigener Operator!

Nicht äquivalent: Ein Gegenbeispiel genügt

Um zu zeigen, dass zwei Terme äquivalent sind, musst du alle Zeilen prüfen. Um zu zeigen, dass sie nicht äquivalent sind, reicht eine einzige Zeile, in der sie sich unterscheiden. Eine solche Zeile heißt Gegenbeispiel.

AA BB A∨BA \lor B A⊕BA \oplus B
0 0 0 0
0 1 1 1
1 0 1 1
1 1 1 0

ODER und XOR stimmen in drei Zeilen überein, aber in der letzten Zeile nicht. Für A=1A = 1, B=1B = 1 ist A∨B=1A \lor B = 1, aber A⊕B=0A \oplus B = 0. Also sind die beiden nicht äquivalent.

Äquivalenz mit Python prüfen

Bei drei oder vier Variablen ist der Vergleich von Hand mühsam. Python kann das schnell erledigen. Die Idee: Man geht alle Belegungen durch und vergleicht die Werte beider Terme. Am Anfang nimmt man an, dass die Terme äquivalent sind. Findet man eine Belegung, in der sie sich unterscheiden, merkt man sich das.

def term_links(a, b):
    return a or (a and b)

def term_rechts(a, b):
    return a

aequivalent = True
for a in [0, 1]:
    for b in [0, 1]:
        if term_links(a, b) != term_rechts(a, b):
            aequivalent = False
            print(f"Unterschied bei A={a} B={b}")

print("Äquivalent:", aequivalent)
Äquivalent: True

Hier wurde kein Unterschied gefunden, also gibt das Programm nur True aus.

Versuch: Probiere es aus

Ersetze in term_links das or durch and. Welche Gegenbeispiele findet das Programm jetzt? Prüfe auch: Ist a and (a or b) äquivalent zu a?

Arbeitsauftrag 78: Äquivalenz prüfen

Prüfe mit Python, ob die beiden folgenden Terme äquivalent sind. Vergleiche dazu für alle Belegungen, ob beide Funktionen stets denselben Wert liefern.

Term A: ¬(A∧B)Term B: ¬A∨¬B\text{Term A: } \lnot (A \land B) \qquad\qquad \text{Term B: } \lnot A \lor \lnot B

Ergänze das Programm:

def term_a(a, b):
    return not (a and b)

def term_b(a, b):
    return (not a) or (not b)

aequivalent = True
for a in [0, 1]:
    for b in [0, 1]:
        # Vergleich einbauen und ggf. aequivalent = False setzen
        ...

print("Äquivalent:", aequivalent)

Erstelle zusätzlich die Belegungstabelle beider Terme von Hand.

Meine Tabelle:

Lösung vergleichen
def term_a(a, b):
    return not (a and b)

def term_b(a, b):
    return (not a) or (not b)

aequivalent = True
for a in [0, 1]:
    for b in [0, 1]:
        if term_a(a, b) != term_b(a, b):
            aequivalent = False

print("Äquivalent:", aequivalent)
Äquivalent: True
AA BB A∧BA \land B ¬(A∧B)\lnot (A \land B) ¬A\lnot A ¬B\lnot B ¬A∨¬B\lnot A \lor \lnot B
0 0 0 1 1 1 1
0 1 0 1 1 0 1
1 0 0 1 0 1 1
1 1 1 0 0 0 0

Die Spalten von ¬(A∧B)\lnot (A \land B) und ¬A∨¬B\lnot A \lor \lnot B stimmen in allen vier Zeilen überein. Die Terme sind also äquivalent. Das ist eine der beiden Regeln von De Morgan: „Nicht beide“ bedeutet dasselbe wie „mindestens einer nicht“.

Die Regeln von De Morgan

Die Äquivalenz aus dem letzten Auftrag ist so wichtig, dass sie einen eigenen Namen hat. Der englische Mathematiker Augustus De Morgan hat im 19. Jahrhundert zwei Regeln aufgeschrieben, die zeigen, wie man eine verneinte Klammer auflöst:

Merke

Regeln von De Morgan: Für alle Belegungen von AA und BB gilt

Merkregel: Zieht man das ¬\lnot in die Klammer, wird jede Variable verneint, und aus ∧\land wird ∨\lor bzw. aus ∨\lor wird ∧\land.

Ein Beispiel aus dem Alltag: „Es ist nicht so, dass es regnet oder windet“ bedeutet dasselbe wie „Es regnet nicht und es windet nicht“. Das ist die zweite Regel.

Für Schaltungen heißt das: Ein NAND-Gatter (UND mit verneintem Ausgang) leistet dasselbe wie ein ODER-Gatter, dessen beide Eingänge vorher verneint werden. Ein NOR-Gatter leistet dasselbe wie ein UND-Gatter mit zwei verneinten Eingängen. Mit den Regeln von De Morgan kann man also Gatter gegeneinander austauschen, ohne dass sich das Verhalten der Schaltung ändert.

Arbeitsauftrag 79: Die zweite Regel von De Morgan

Zeige mit einer Belegungstabelle, dass ¬(A∨B)\lnot (A \lor B) und ¬A∧¬B\lnot A \land \lnot B äquivalent sind. Fülle dazu die Tabelle aus und begründe dein Ergebnis in einem Satz.

AA BB A∨BA \lor B ¬(A∨B)\lnot (A \lor B) ¬A\lnot A ¬B\lnot B ¬A∧¬B\lnot A \land \lnot B
0 0
0 1
1 0
1 1

Begründung:

Lösung vergleichen
AA BB A∨BA \lor B ¬(A∨B)\lnot (A \lor B) ¬A\lnot A ¬B\lnot B ¬A∧¬B\lnot A \land \lnot B
0 0 0 1 1 1 1
0 1 1 0 1 0 0
1 0 1 0 0 1 0
1 1 1 0 0 0 0

Die Spalten von ¬(A∨B)\lnot (A \lor B) und ¬A∧¬B\lnot A \land \lnot B stimmen in allen vier Zeilen überein. Also sind die beiden Terme äquivalent. Beide sind nur dann 1, wenn AA und BB beide 0 sind.

Stolperstein

Ein sehr häufiger Fehler ist, das ¬\lnot einfach in die Klammer „hineinzuziehen“: ¬(A∧B)\lnot (A \land B) ist nicht äquivalent zu ¬A∧¬B\lnot A \land \lnot B. Gegenbeispiel: Für A=1A = 1, B=0B = 0 ist ¬(1∧0)=¬0=1\lnot (1 \land 0) = \lnot 0 = 1, aber ¬1∧¬0=0∧1=0\lnot 1 \land \lnot 0 = 0 \land 1 = 0. Wer das ¬\lnot in die Klammer zieht, muss das ∧\land in ein ∨\lor umwandeln (und umgekehrt).

2.7.3Die disjunktive Normalform (DNF)

Beim Schaltungsentwurf steht am Anfang oft eine Belegungstabelle: In diesen Fällen soll der Ausgang 1 sein, in den anderen 0. Wie kommt man von der Tabelle zu einem Term? Dafür gibt es ein Verfahren, das immer funktioniert.

Die Idee: ein Steckbrief für jede 1-Zeile

Schau dir diese Tabelle an:

AA BB Ausgang
0 0 0
0 1 1
1 0 1
1 1 0

Der Ausgang ist in zwei Zeilen 1. Für jede dieser Zeilen schreiben wir einen „Steckbrief“: eine Konjunktion, die genau in dieser einen Zeile den Wert 1 hat und sonst überall 0.

Der Ausgang soll 1 sein, wenn wir in der einen oder in der anderen Zeile sind. Also verbinden wir die Steckbriefe mit ∨\lor:

(¬A∧B)∨(A∧¬B)(\lnot A \land B) \lor (A \land \lnot B)

Das ist die disjunktive Normalform der Tabelle. Übrigens ist die Tabelle genau die von XOR. Wir haben also nebenbei herausgefunden, wie man XOR mit ∧\land, ∨\lor und ¬\lnot schreibt.

Definition: Minterm und disjunktive Normalform

Ein Minterm ist eine Konjunktion, in der jede Variable genau einmal vorkommt, entweder ohne oder mit ¬\lnot. Er hat genau in einer Zeile der Belegungstabelle den Wert 1.

Die disjunktive Normalform (DNF) einer Belegungstabelle ist die Disjunktion (∨\lor) der Minterme aller Zeilen, in denen das Ergebnis 1 ist.

Der Name erklärt sich so: disjunktiv, weil die Minterme mit ∨\lor (Disjunktion) verbunden werden; Normalform, weil jeder Term auf diese feste, „normale“ Form gebracht werden kann.

Merke

Die disjunktive Normalform (DNF) ist eine standardisierte Darstellung eines Terms:

Beispiel: Ist der Ausgang bei A=1,B=0A = 1, B = 0 und bei A=0,B=1A = 0, B = 1 gleich 1 (sonst 0), lautet die DNF (A∧¬B)∨(¬A∧B)(A \land \lnot B) \lor (\lnot A \land B) – das ist genau XOR!

Ob man die Minterme in der Reihenfolge (¬A∧B)∨(A∧¬B)(\lnot A \land B) \lor (A \land \lnot B) oder (A∧¬B)∨(¬A∧B)(A \land \lnot B) \lor (\lnot A \land B) aufschreibt, ist egal. Bei ∨\lor kommt es auf die Reihenfolge nicht an.

Mit Python lässt sich prüfen, dass die DNF wirklich die Tabelle von oben liefert:

def dnf_beispiel(a, b):
    return int((not a and b) or (a and not b))

for a in [0, 1]:
    for b in [0, 1]:
        print(f"A={a} B={b} -> {dnf_beispiel(a, b)}")
A=0 B=0 -> 0
A=0 B=1 -> 1
A=1 B=0 -> 1
A=1 B=1 -> 0

Die Klammern um not a and b sind in Python eigentlich nicht nötig, weil and stärker bindet als or. Sie machen die Funktion aber leichter lesbar.

Warum funktioniert das?

Jeder Minterm ist in genau einer Zeile 1 – nämlich in der Zeile, aus der er gebaut wurde. In jeder anderen Zeile stimmt mindestens eine Variable nicht, und die Konjunktion wird 0. Die Disjunktion aller Minterme ist deshalb genau in den Zeilen 1, aus denen ein Minterm gebaut wurde – und das sind genau die 1-Zeilen der Tabelle. Die DNF hat also dieselbe Belegungstabelle wie der Ausgang. Wenn die Tabelle zu einem Term gehört, ist die DNF zu diesem Term äquivalent.

Das Verfahren Schritt für Schritt

  1. Suche in der Belegungstabelle alle Zeilen, in denen das Ergebnis 1 ist. Die Zeilen mit 0 brauchst du nicht.
  2. Schreibe für jede dieser Zeilen den Minterm auf: alle Variablen mit ∧\land verbunden; eine Variable, die in der Zeile 0 ist, bekommt ein ¬\lnot.
  3. Setze um jeden Minterm Klammern und verbinde alle Minterme mit ∨\lor.
Beispiel

DNF der Alarmanlage. Wir kürzen ab: TT für Tür, SS für Scharf, RR für Rauch. Der Term lautet (T∧S)∨R(T \land S) \lor R. Zuerst die Belegungstabelle, dann für jede 1-Zeile der Minterm:

TT SS RR (T∧S)∨R(T \land S) \lor R Minterm
0 0 0 0
0 0 1 1 ¬T∧¬S∧R\lnot T \land \lnot S \land R
0 1 0 0
0 1 1 1 ¬T∧S∧R\lnot T \land S \land R
1 0 0 0
1 0 1 1 T∧¬S∧RT \land \lnot S \land R
1 1 0 1 T∧S∧¬RT \land S \land \lnot R
1 1 1 1 T∧S∧RT \land S \land R

Die DNF lautet:

(¬T∧¬S∧R)∨(¬T∧S∧R)∨(T∧¬S∧R)∨(T∧S∧¬R)∨(T∧S∧R)(\lnot T \land \lnot S \land R) \lor (\lnot T \land S \land R) \lor (T \land \lnot S \land R) \lor (T \land S \land \lnot R) \lor (T \land S \land R)

Sie ist äquivalent zu (T∧S)∨R(T \land S) \lor R, aber viel länger. Im nächsten Abschnitt lernst du, wie man eine DNF wieder vereinfacht.

Stolperstein
So kannst du es sagen

So sprichst du über Belegungstabellen und Terme – vom einfachen zum genauen Satz:

Arbeitsauftrag 80: DNF ablesen

Gegeben ist folgende Belegungstabelle:

AA BB CC Ausgang
0 0 0 0
0 0 1 1
0 1 0 0
0 1 1 0
1 0 0 0
1 0 1 0
1 1 0 1
1 1 1 1
  1. Bestimme die DNF auf Papier.
  2. Schreibe die DNF als Python-Funktion meine_dnf(a, b, c) und überprüfe sie mit drei geschachtelten Schleifen gegen die Tabelle.

Meine DNF:

Lösung vergleichen

Die 1-Zeilen sind (0,0,1)(0, 0, 1), (1,1,0)(1, 1, 0) und (1,1,1)(1, 1, 1). Die DNF lautet:

(¬A∧¬B∧C)∨(A∧B∧¬C)∨(A∧B∧C)(\lnot A \land \lnot B \land C) \lor (A \land B \land \lnot C) \lor (A \land B \land C)

def meine_dnf(a, b, c):
    m1 = not a and not b and c
    m2 = a and b and not c
    m3 = a and b and c
    return int(m1 or m2 or m3)

for a in [0, 1]:
    for b in [0, 1]:
        for c in [0, 1]:
            print(f"A={a} B={b} C={c} -> {meine_dnf(a, b, c)}")
A=0 B=0 C=0 -> 0
A=0 B=0 C=1 -> 1
A=0 B=1 C=0 -> 0
A=0 B=1 C=1 -> 0
A=1 B=0 C=0 -> 0
A=1 B=0 C=1 -> 0
A=1 B=1 C=0 -> 1
A=1 B=1 C=1 -> 1

Die Ausgabe stimmt mit der Spalte „Ausgang“ überein. Die drei Hilfsvariablen m1, m2, m3 stehen für die drei Minterme.

Arbeitsauftrag 81: DNF zu einem Term

Bestimme die DNF zum Term (A∨B)∧¬C(A \lor B) \land \lnot C aus dem Auftrag Vom Term zur Belegungstabelle. Benutze deine Belegungstabelle von dort.

Meine DNF:

Lösung vergleichen

Die Belegungstabelle hat drei 1-Zeilen: (0,1,0)(0, 1, 0), (1,0,0)(1, 0, 0) und (1,1,0)(1, 1, 0). Die DNF lautet:

(¬A∧B∧¬C)∨(A∧¬B∧¬C)∨(A∧B∧¬C)(\lnot A \land B \land \lnot C) \lor (A \land \lnot B \land \lnot C) \lor (A \land B \land \lnot C)

Sie ist äquivalent zum Term (A∨B)∧¬C(A \lor B) \land \lnot C, aber länger. Das ist typisch: Die DNF ist ein sicheres Verfahren, aber selten die kürzeste Lösung.

2.7.4Weitere Übungen

Hier kannst du das Gelernte weiter üben. Die Punkte im Titel zeigen, wie schwer eine Aufgabe ist: ●○○ leicht, ●●○ mittel, ●●● knifflig. Fang mit den leichten an.

Arbeitsauftrag 82: Belegungstabelle mit zwei Variablen ●○○

Erstelle die Belegungstabelle zum Term ¬A∨B\lnot A \lor B. Benutze die Hilfsspalte.

AA BB ¬A\lnot A ¬A∨B\lnot A \lor B
0 0
0 1
1 0
1 1
Lösung vergleichen
AA BB ¬A\lnot A ¬A∨B\lnot A \lor B
0 0 1 1
0 1 1 1
1 0 0 0
1 1 0 1

Der Term ist nur in der Zeile A=1A = 1, B=0B = 0 gleich 0. Dort sind beide Teile der Disjunktion 0.

Arbeitsauftrag 83: Minterme aufschreiben ●○○
  1. Schreibe zu jeder Belegung den Minterm auf (drei Variablen AA, BB, CC).

    1. A=1A = 1, B=0B = 0, C=1C = 1 \qquad b) A=0A = 0, B=0B = 0, C=0C = 0 \qquad c) A=0A = 0, B=1B = 1, C=1C = 1
  2. Jetzt umgekehrt: Bei welcher Belegung hat der Minterm ¬A∧B∧¬C\lnot A \land B \land \lnot C den Wert 1?

Deine Antworten:

Lösung vergleichen
    1. A∧¬B∧CA \land \lnot B \land C \qquad b) ¬A∧¬B∧¬C\lnot A \land \lnot B \land \lnot C \qquad c) ¬A∧B∧C\lnot A \land B \land C
  1. Bei A=0A = 0, B=1B = 1, C=0C = 0. Jede Variable mit ¬\lnot muss 0 sein, jede ohne ¬\lnot muss 1 sein.

Merke: Eine Variable bekommt ein ¬\lnot, wenn sie in der Zeile den Wert 0 hat.

Arbeitsauftrag 84: DNF mit zwei Variablen ●○○

Bestimme die DNF zu dieser Belegungstabelle. Beschreibe in Worten, wann der Ausgang 1 ist.

AA BB Ausgang
0 0 1
0 1 0
1 0 0
1 1 1

DNF und Beschreibung:

Lösung vergleichen

Die 1-Zeilen sind (0,0)(0, 0) und (1,1)(1, 1). Die DNF lautet

(¬A∧¬B)∨(A∧B).(\lnot A \land \lnot B) \lor (A \land B).

Der Ausgang ist 1, wenn AA und BB gleich sind. Das ist das Gegenteil von XOR.

Arbeitsauftrag 85: DNF mit drei Variablen ●○○

Bestimme die DNF zu dieser Belegungstabelle.

AA BB CC Ausgang
0 0 0 0
0 0 1 0
0 1 0 1
0 1 1 0
1 0 0 0
1 0 1 0
1 1 0 0
1 1 1 1

DNF:

Lösung vergleichen

Die 1-Zeilen sind (0,1,0)(0, 1, 0) und (1,1,1)(1, 1, 1). Die DNF lautet

(¬A∧B∧¬C)∨(A∧B∧C).(\lnot A \land B \land \lnot C) \lor (A \land B \land C).

Innerhalb eines Minterms steht ∧\land, zwischen den Mintermen ∨\lor.

Arbeitsauftrag 86: Äquivalent oder nicht? ●●○

Prüfe mit Belegungstabellen, ob die beiden Terme äquivalent sind. Wenn nicht, gib eine Belegung an, in der sie sich unterscheiden.

  1. A∨(¬A∧B)A \lor (\lnot A \land B) und A∨BA \lor B
  2. ¬A∧¬B\lnot A \land \lnot B und ¬(A∧B)\lnot (A \land B)

Deine Tabellen und deine Antwort:

Lösung vergleichen
  1. äquivalent:
AA BB ¬A∧B\lnot A \land B A∨(¬A∧B)A \lor (\lnot A \land B) A∨BA \lor B
0 0 0 0 0
0 1 1 1 1
1 0 0 1 1
1 1 0 1 1

Die beiden letzten Spalten stimmen in allen vier Zeilen überein.

  1. nicht äquivalent:
AA BB ¬A∧¬B\lnot A \land \lnot B ¬(A∧B)\lnot (A \land B)
0 0 1 1
0 1 0 1
1 0 0 1
1 1 0 0

Zum Beispiel bei A=1A = 1, B=0B = 0 ist ¬A∧¬B=0\lnot A \land \lnot B = 0, aber ¬(A∧B)=1\lnot (A \land B) = 1. Eine einzige solche Zeile genügt. Das ist ein typischer Fehler: Man darf das ¬\lnot nicht einfach in die Klammer schreiben und das ∧\land stehen lassen. Äquivalent zu ¬(A∧B)\lnot (A \land B) ist ¬A∨¬B\lnot A \lor \lnot B.

Arbeitsauftrag 87: Vom Term zur DNF ●●○

Gegeben ist der Term (A∧¬B)∨(B∧C)(A \land \lnot B) \lor (B \land C).

  1. Erstelle die Belegungstabelle mit Hilfsspalten.
  2. Bestimme die DNF.
AA BB CC ¬B\lnot B A∧¬BA \land \lnot B B∧CB \land C Term
0 0 0
0 0 1
0 1 0
0 1 1
1 0 0
1 0 1
1 1 0
1 1 1

DNF:

Lösung vergleichen
AA BB CC ¬B\lnot B A∧¬BA \land \lnot B B∧CB \land C (A∧¬B)∨(B∧C)(A \land \lnot B) \lor (B \land C)
0 0 0 1 0 0 0
0 0 1 1 0 0 0
0 1 0 0 0 0 0
0 1 1 0 0 1 1
1 0 0 1 1 0 1
1 0 1 1 1 0 1
1 1 0 0 0 0 0
1 1 1 0 0 1 1

Die 1-Zeilen sind (0,1,1)(0, 1, 1), (1,0,0)(1, 0, 0), (1,0,1)(1, 0, 1) und (1,1,1)(1, 1, 1). Die DNF lautet

(¬A∧B∧C)∨(A∧¬B∧¬C)∨(A∧¬B∧C)∨(A∧B∧C).(\lnot A \land B \land C) \lor (A \land \lnot B \land \lnot C) \lor (A \land \lnot B \land C) \lor (A \land B \land C).

Sie ist äquivalent zum gegebenen Term, aber deutlich länger.

Arbeitsauftrag 88: Äquivalenz mit Python prüfen ●●○

Prüfe mit Python, ob die Terme äquivalent sind. Wenn nicht, soll das Programm alle Belegungen ausgeben, in denen sie sich unterscheiden.

  1. A∧(B∨C)A \land (B \lor C) und (A∧B)∨(A∧C)(A \land B) \lor (A \land C)
  2. A∨(B∧C)A \lor (B \land C) und (A∨B)∧C(A \lor B) \land C
Tipp

Schreibe jeden Term als eigene Funktion. Gehe dann vor wie im Abschnitt Äquivalenz mit Python prüfen, nur mit drei geschachtelten Schleifen.

Lösung vergleichen
def term1(a, b, c):
    return int(a and (b or c))

def term2(a, b, c):
    return int((a and b) or (a and c))

def term3(a, b, c):
    return int(a or (b and c))

def term4(a, b, c):
    return int((a or b) and c)

aequivalent = True
for a in [0, 1]:
    for b in [0, 1]:
        for c in [0, 1]:
            if term1(a, b, c) != term2(a, b, c):
                aequivalent = False
                print(f"a) Unterschied bei A={a} B={b} C={c}")
print("a) äquivalent:", aequivalent)

aequivalent = True
for a in [0, 1]:
    for b in [0, 1]:
        for c in [0, 1]:
            if term3(a, b, c) != term4(a, b, c):
                aequivalent = False
                print(f"b) Unterschied bei A={a} B={b} C={c}")
print("b) äquivalent:", aequivalent)
a) äquivalent: True
b) Unterschied bei A=1 B=0 C=0
b) Unterschied bei A=1 B=1 C=0
b) äquivalent: False
  1. Die Terme sind äquivalent. „AA und (BB oder CC)“ heißt dasselbe wie „(AA und BB) oder (AA und CC)“.
  2. Die Terme sind nicht äquivalent. Bei A=1A = 1, C=0C = 0 ist der linke Term 1 (weil A=1A = 1), der rechte aber 0 (weil C=0C = 0). Die Klammern stehen an verschiedenen Stellen. Das ändert die Bedeutung.

Wichtig: Vor dem zweiten Vergleich muss aequivalent wieder auf True gesetzt werden.

Arbeitsauftrag 89: Warnleuchte im Auto ●●●

Eine Warnleuchte im Auto (L=1L = 1) leuchtet, wenn der Motor läuft (M=1M = 1) und der Gurt nicht angelegt ist (G=0G = 0). Sie leuchtet außerdem, wenn der Motor läuft und eine Tür offen ist (T=1T = 1).

  1. Stelle die Belegungstabelle für MM, GG, TT auf.
  2. Bestimme die DNF.
  3. Mia hat den kürzeren Term M∧(¬G∨T)M \land (\lnot G \lor T) gefunden. Prüfe mit Python, ob er zu deiner DNF äquivalent ist.

Tabelle und DNF:

Lösung vergleichen
  1. Die Leuchte leuchtet nur bei laufendem Motor. Hilfsspalten für die beiden Fälle machen die Tabelle übersichtlich:
MM GG TT M∧¬GM \land \lnot G M∧TM \land T LL
0 0 0 0 0 0
0 0 1 0 0 0
0 1 0 0 0 0
0 1 1 0 0 0
1 0 0 1 0 1
1 0 1 1 1 1
1 1 0 0 0 0
1 1 1 0 1 1
  1. Die 1-Zeilen sind (1,0,0)(1, 0, 0), (1,0,1)(1, 0, 1) und (1,1,1)(1, 1, 1):

(M∧¬G∧¬T)∨(M∧¬G∧T)∨(M∧G∧T)(M \land \lnot G \land \lnot T) \lor (M \land \lnot G \land T) \lor (M \land G \land T)

  1. Kontrolle mit Python:
def dnf(m, g, t):
    m1 = m and not g and not t
    m2 = m and not g and t
    m3 = m and g and t
    return int(m1 or m2 or m3)

def mia(m, g, t):
    return int(m and (not g or t))

aequivalent = True
for m in [0, 1]:
    for g in [0, 1]:
        for t in [0, 1]:
            if dnf(m, g, t) != mia(m, g, t):
                aequivalent = False
print("Äquivalent:", aequivalent)
Äquivalent: True

Mias Term ist äquivalent zur DNF, braucht aber viel weniger Gatter. Man kann ihn so lesen: Der Motor muss laufen, und außerdem muss der Gurt fehlen oder eine Tür offen sein. Wie man solche kürzeren Terme systematisch findet, lernst du im nächsten Abschnitt.

2.7.5Das Wichtigste in Kürze

Selbstcheck

2.8KV-Diagramme: Terme vereinfachen, Schaltungen sparen DS22

Diesen Abschnitt als PDF (S. 106–129)

Das Jupyter-Notebook aus dem Unterricht: DS22_KV_Diagramme.ipynb. Herunterladen und in VS Code oder Jupyter öffnen.

Leitidee

Im letzten Abschnitt hast du die disjunktive Normalform kennengelernt. Sie liefert zu jeder Belegungstabelle einen Term – aber oft einen sehr langen. Für die Alarmanlage hatte die DNF fünf Minterme, obwohl der Term (T∧S)∨R(T \land S) \lor R dasselbe leistet. Jedes ∧\land, ∨\lor und ¬\lnot ist in der Schaltung ein Gatter, und jedes Gatter kostet Geld, Platz und Strom. Deshalb will man Terme so weit wie möglich vereinfachen. Ein praktisches Hilfsmittel dafür ist das Karnaugh-Veitch-Diagramm, kurz KV-Diagramm. Es wurde in den 1950er-Jahren von Edward Veitch und Maurice Karnaugh erfunden. Damit findest du einen kurzen Term, indem du in einer Tabelle Kästchen um Einsen zeichnest.

Lernziele

Nach diesem Abschnitt kannst du

2.8.1Warum vereinfachen? Die Kosten einer Schaltung

Als einfaches Maß für die Kosten einer Schaltung zählen wir ihre Gatter. Dabei gilt:

Vergleiche damit die beiden äquivalenten Terme der Alarmanlage (TT: Tür offen, SS: Scharf, RR: Rauch):

Term UND ODER NICHT Gatter gesamt
DNF mit 5 Mintermen 5⋅2=105 \cdot 2 = 10 4 3 17
(T∧S)∨R(T \land S) \lor R 1 1 0 2

Die DNF braucht 17 Gatter: Jeder der fünf Minterme hat drei Variablen und braucht zwei UND-Gatter. Vier ODER-Gatter verbinden die fünf Minterme. Und für ¬T\lnot T, ¬S\lnot S und ¬R\lnot R braucht man drei NICHT-Gatter. Die einfache Form kommt mit zwei Gattern aus. Beide Schaltungen tun genau dasselbe! Je weniger Gatter, desto billiger, kleiner und sparsamer ist die Schaltung, und desto schneller liegt das Ergebnis vor.

2.8.2Die Idee: Nachbarn zusammenfassen

Fangen wir klein an. Eine Belegungstabelle mit zwei Variablen hat genau in den Zeilen A=0,B=0A = 0, B = 0 und A=0,B=1A = 0, B = 1 eine 1. Die DNF lautet:

(¬A∧¬B)∨(¬A∧B)(\lnot A \land \lnot B) \lor (\lnot A \land B)

Schau dir die beiden Minterme genau an. Sie stimmen in ¬A\lnot A überein und unterscheiden sich nur bei BB. Der erste verlangt B=0B = 0, der zweite B=1B = 1. Zusammen heißt das: Wenn A=0A = 0 ist, ist das Ergebnis 1 – egal, welchen Wert BB hat. BB spielt also keine Rolle und fällt weg. Übrig bleibt:

¬A\lnot A

Diese Regel ist der Kern der ganzen Methode: Zwei Minterme, die sich nur in einer Variablen unterscheiden, kann man zusammenfassen. Die Variable, in der sie sich unterscheiden, fällt weg.

Das prüfen wir mit Python. Beide Terme müssen für alle Belegungen denselben Wert liefern:

def unminimiert(a, b):
    return (not a and not b) or (not a and b)

def minimiert(a, b):
    return not a

for a in [0, 1]:
    for b in [0, 1]:
        print(a, b, unminimiert(a, b) == minimiert(a, b))
0 0 True
0 1 True
1 0 True
1 1 True

In jeder Zeile steht True: Die beiden Terme sind äquivalent.

Das KV-Diagramm mit zwei Variablen

Um solche Paare schnell zu finden, ordnet man die Zeilen der Belegungstabelle in einem Raster an, dem KV-Diagramm. Bei zwei Variablen hat es zwei Zeilen und zwei Spalten. Die Zeile gibt den Wert von AA an, die Spalte den Wert von BB. In jedem Feld steht der Ausgangswert für diese Belegung. Die kleinen grauen Zahlen sind die Nummern der Zeilen in der Belegungstabelle, gezählt ab 0. Man erhält sie, wenn man die Belegung als Binärzahl liest: Das Feld A=1A = 1, B=0B = 0 hat die Nummer 102=210_2 = 2.

In unserem Beispiel stehen die beiden Einsen in der oberen Zeile (A=0A = 0) nebeneinander. Wir umranden sie als Block. Im ganzen Block hat AA den Wert 0, BB dagegen wechselt. Also bleibt nur ¬A\lnot A übrig:

KV-Diagramm zu (\lnot A \land \lnot B) \lor (\lnot A \land B): Die beiden Einsen bilden einen Block mit A = 0. Die kleinen grauen Zahlen sind die Zeilennummern der Belegungstabelle
Definition: Karnaugh-Veitch-Diagramm

Ein Karnaugh-Veitch-Diagramm (KV-Diagramm) ist eine Anordnung aller Belegungen einer Belegungstabelle in einem Raster. Die Felder sind so angeordnet, dass sich benachbarte Felder in genau einer Variablen unterscheiden.

2.8.3KV-Diagramme mit drei Variablen

Bei drei Variablen hat das KV-Diagramm zwei Zeilen und vier Spalten. Die Zeile gibt den Wert von AA an. Die Spalte gibt die Werte von BB und CC zusammen an. Achtung: Die Spalten stehen nicht in der Reihenfolge 00, 01, 10, 11, sondern

00,01,11,10.00, \quad 01, \quad 11, \quad 10.

KV-Diagramm für drei Variablen. Die kleine graue Zahl in jedem Feld ist die Nummer der passenden Zeile in der Belegungstabelle

Warum diese seltsame Reihenfolge?

Damit man Nachbarn zusammenfassen kann, müssen sich benachbarte Felder in genau einer Variablen unterscheiden. Bei der gewohnten Reihenfolge 00, 01, 10, 11 stünden 01 und 10 nebeneinander. Die beiden unterscheiden sich aber in beiden Stellen. In der Reihenfolge 00, 01, 11, 10 ändert sich von Spalte zu Spalte immer nur eine Stelle:

00 -> 01    (C ändert sich)
01 -> 11    (B ändert sich)
11 -> 10    (C ändert sich)
10 -> 00    (B ändert sich)

Diese Reihenfolge heißt Gray-Code (nach dem Ingenieur Frank Gray). Beachte die letzte Zeile: Auch die letzte und die erste Spalte unterscheiden sich nur in einer Stelle. Sie sind also ebenfalls Nachbarn, obwohl sie am Rand weit auseinander stehen. Stell dir vor, das Diagramm wäre zu einer Rolle gebogen, sodass der linke und der rechte Rand aneinanderstoßen.

Tipp

Um eine Belegungstabelle ins KV-Diagramm zu übertragen, liest du in jeder Zeile die Belegung als Binärzahl. Die Zeile A=1,B=0,C=1A = 1, B = 0, C = 1 hat die Nummer 1012=5101_2 = 5. Ihr Wert gehört in das Feld in der Zeile A=1A = 1 und der Spalte BC=01BC = 01. Die Feldnummern in der Vorlage oben helfen dir dabei.

Blöcke bilden

Jetzt fassen wir benachbarte Einsen zu Blöcken zusammen. Dafür gelten feste Regeln:

  1. Ein Block enthält nur Einsen.
  2. Ein Block ist ein Rechteck aus 1, 2, 4 oder 8 Feldern. Blöcke aus 3 oder 6 Feldern gibt es nicht.
  3. Blöcke dürfen über den Rand gehen: Gegenüberliegende Ränder sind Nachbarn.
  4. Blöcke dürfen sich überlappen.
  5. Jede 1 muss in mindestens einem Block liegen.
  6. Die Blöcke sollen so groß wie möglich sein, und es sollen so wenige wie möglich sein.

Zu jedem Block gehört ein Term. Du findest ihn so: Schau, welche Variablen in allen Feldern des Blocks denselben Wert haben. Nur diese bleiben übrig – mit ¬\lnot, wenn der Wert 0 ist. Alle anderen fallen weg. Die Terme aller Blöcke werden mit ∨\lor verbunden.

Je größer ein Block ist, desto mehr Variablen fallen weg. Bei drei Variablen bleiben in einem Einzelfeld drei Variablen übrig, in einem Zweierblock zwei, in einem Viererblock eine.

Merke
Beispiel

Mehrheitsentscheid. Drei Personen AA, BB, CC stimmen ab. Der Ausgang ist 1, wenn mindestens zwei dafür sind. Das ist in den Zeilen 3, 5, 6 und 7 der Belegungstabelle der Fall. Die DNF hat vier Minterme:

(¬A∧B∧C)∨(A∧¬B∧C)∨(A∧B∧¬C)∨(A∧B∧C)(\lnot A \land B \land C) \lor (A \land \lnot B \land C) \lor (A \land B \land \lnot C) \lor (A \land B \land C)

KV-Diagramm zum Mehrheitsentscheid: drei Zweierblöcke, die sich im Feld 7 überlappen

Feld 7 hat drei Nachbarn mit einer 1: Feld 3 direkt darüber, Feld 5 links daneben und Feld 6 rechts daneben. Einen Viererblock gibt es nicht, weil die Felder 1, 2 und 4 den Wert 0 haben. Also bildet Feld 7 mit jedem seiner Nachbarn einen Zweierblock:

Der vereinfachte Term lautet (B∧C)∨(A∧C)∨(A∧B)(B \land C) \lor (A \land C) \lor (A \land B). Feld 7 liegt in allen drei Blöcken. Das ist erlaubt und sogar nötig, denn sonst könnte man die anderen Einsen nicht in Zweierblöcke packen. Die DNF braucht 14 Gatter (8 UND, 3 ODER, 3 NICHT), die vereinfachte Form nur 5 (3 UND, 2 ODER).

Stolperstein
Arbeitsauftrag 90: KV-Diagramm zeichnen und minimieren

Gegeben ist folgende Belegungstabelle für drei Variablen:

AA BB CC Ausgang
0 0 0 1
0 0 1 1
0 1 0 0
0 1 1 0
1 0 0 1
1 0 1 1
1 1 0 0
1 1 1 0
  1. Zeichne ein KV-Diagramm und finde die größtmöglichen Blöcke.
  2. Notiere die minimierte Form.
  3. Überprüfe deine minimierte Form mit Python gegen die unminimierte DNF. Verwende dazu diese Funktion:
def unminimiert_a(a, b, c):
    return ((not a and not b and not c) or (not a and not b and c) or
            (a and not b and not c) or (a and not b and c))
Vorlage zum Ausfüllen: KV-Diagramm für drei Variablen mit Feldnummern

Minimierte Form:

Lösung vergleichen
Lösung: Alle Einsen liegen in einem Viererblock mit B = 0

Alle vier Einsen liegen in den beiden linken Spalten (BC=00BC = 00 und BC=01BC = 01), und zwar in beiden Zeilen. Sie bilden einen Viererblock. Im ganzen Block ist B=0B = 0, während AA und CC wechseln. Die minimierte Form lautet also

¬B.\lnot B.

def unminimiert_a(a, b, c):
    return ((not a and not b and not c) or (not a and not b and c) or
            (a and not b and not c) or (a and not b and c))

def minimiert_a(a, b, c):
    return not b

for a in [0, 1]:
    for b in [0, 1]:
        for c in [0, 1]:
            gleich = unminimiert_a(a, b, c) == minimiert_a(a, b, c)
            print(a, b, c, "->", gleich)
0 0 0 -> True
0 0 1 -> True
0 1 0 -> True
0 1 1 -> True
1 0 0 -> True
1 0 1 -> True
1 1 0 -> True
1 1 1 -> True

Wer nur die Zweierblöcke ¬A∧¬B\lnot A \land \lnot B (obere Zeile) und A∧¬BA \land \lnot B (untere Zeile) gefunden hat, erhält (¬A∧¬B)∨(A∧¬B)(\lnot A \land \lnot B) \lor (A \land \lnot B). Das ist richtig, aber nicht minimal: Der Viererblock fasst beide zusammen. Statt 14 Gattern für die DNF genügt ein einziges NICHT-Gatter.

2.8.4Über den Rand hinaus

Weil der linke und der rechte Rand Nachbarn sind, dürfen Blöcke über den Rand gehen. In diesem Beispiel ist der Ausgang in den Zeilen 0, 2, 4 und 6 gleich 1:

Randüberlappung: Die linke und die rechte Spalte sind Nachbarn. Die vier Einsen bilden einen Block mit C = 0

Die Einsen stehen in der ersten Spalte (BC=00BC = 00) und in der letzten Spalte (BC=10BC = 10). Diese beiden Spalten unterscheiden sich nur in BB. Zusammen bilden die vier Felder einen Viererblock. In der Abbildung ist er als zwei getrennte Rechtecke in derselben Farbe gezeichnet – denk dir die Rolle zusammengebogen, dann stoßen die beiden Teile aneinander. Im Block ist überall C=0C = 0, AA und BB wechseln. Der Term lautet ¬C\lnot C.

2.8.5KV-Diagramme mit vier Variablen

Bei vier Variablen hat das KV-Diagramm vier Zeilen und vier Spalten. Die Zeilen geben die Werte von AA und BB an, die Spalten die Werte von CC und DD. Beide folgen dem Gray-Code 00, 01, 11, 10. Die Feldnummern erhältst du wieder, indem du ABCDABCD als Binärzahl liest. Im ersten Beispiel unten sind sie in jedem Feld eingetragen.

Jetzt sind sowohl der linke und der rechte Rand Nachbarn als auch der obere und der untere Rand. Blöcke dürfen also nach rechts und nach unten über den Rand gehen. Bei vier Variablen bleiben in einem Zweierblock drei Variablen übrig, in einem Viererblock zwei und in einem Achterblock nur noch eine.

Beispiel: zwei überlappende Viererblöcke

Der Ausgang ist in den Zeilen 4, 5, 7, 12, 13 und 15 gleich 1:

Zwei Viererblöcke, die sich überlappen: B \land \lnot C (rot) und B \land D (blau)

Der vereinfachte Term lautet (B∧¬C)∨(B∧D)(B \land \lnot C) \lor (B \land D). Die DNF hätte sechs Minterme mit je vier Variablen.

Beispiel: die vier Ecken

Die vier Eckfelder sind alle miteinander benachbart: Links und rechts sind Nachbarn, oben und unten auch. Sind genau die Ecken 1, bilden sie einen Viererblock:

Die vier Ecken sind Nachbarn und bilden einen Viererblock mit B = 0 und D = 0

In allen vier Ecken ist B=0B = 0 (Zeilen 00 und 10) und D=0D = 0 (Spalten 00 und 10). Der Term lautet ¬B∧¬D\lnot B \land \lnot D.

Beispiel: ein Achterblock

Hier ist der Ausgang in den Zeilen 0 bis 7 und in Zeile 15 gleich 1:

Ein Achterblock (A = 0) und ein Zweierblock (B \land C \land D)

Der vereinfachte Term lautet ¬A∨(B∧C∧D)\lnot A \lor (B \land C \land D). Die DNF hätte neun Minterme.

Arbeitsauftrag 91: KV-Training

Vereinfache mithilfe eines KV-Diagramms. Benutze die Vorlagen unten.

  1. die DNF (¬A∧¬B∧C)∨(¬A∧B∧C)∨(A∧¬B∧C)∨(A∧B∧C)(\lnot A \land \lnot B \land C) \lor (\lnot A \land B \land C) \lor (A \land \lnot B \land C) \lor (A \land B \land C)
  2. Drei Variablen AA, BB, CC: Der Ausgang ist genau in den Zeilen 0, 2 und 5 der Belegungstabelle 1.
  3. Vier Variablen AA, BB, CC, DD: Der Ausgang ist genau in den Zeilen 0, 1, 2, 3, 8, 9, 10 und 11 der Belegungstabelle 1.
Vorlage für a)
Vorlage für b)
Vorlage für c)

Meine vereinfachten Terme:

Lösung vergleichen
  1. Die Minterme gehören zu den Zeilen 1, 3, 5 und 7. Das sind die beiden mittleren Spalten (BC=01BC = 01 und BC=11BC = 11). Dort ist überall C=1C = 1:
Lösung zu a)

Ergebnis: CC.

  1. Die Felder 0 und 2 liegen in der oberen Zeile ganz links und ganz rechts. Über den Rand sind sie Nachbarn: A=0A = 0, C=0C = 0. Feld 5 hat keinen Nachbarn mit einer 1 und bleibt ein Einerblock:
Lösung zu b): ein Zweierblock über den Rand und ein Einerblock

Ergebnis: (¬A∧¬C)∨(A∧¬B∧C)(\lnot A \land \lnot C) \lor (A \land \lnot B \land C). Der Einerblock bleibt ein vollständiger Minterm.

  1. Die Einsen füllen die oberste Zeile (AB=00AB = 00) und die unterste Zeile (AB=10AB = 10). Die beiden Zeilen sind über den Rand benachbart. Zusammen bilden sie einen Achterblock, in dem nur B=0B = 0 konstant ist:
Lösung zu c): ein Achterblock über den oberen und unteren Rand

Ergebnis: ¬B\lnot B.

Merke

Das KV-Diagramm liefert eine minimierte DNF, die zur ursprünglichen DNF äquivalent, aber kürzer ist. Das ist wichtig für kostengünstigere Schaltungen (weniger Gatter).

2.8.6Zurück zur Alarmanlage

Arbeitsauftrag 92: Ist die Alarmanlage minimal?

Erinnere dich an die Alarmanlage: Alarm=(Tür∧Scharf)∨Rauch\text{Alarm} = (\text{Tür} \land \text{Scharf}) \lor \text{Rauch}. Ist dieser Term bereits minimal, oder lässt er sich mit einem KV-Diagramm weiter vereinfachen? Begründe deine Antwort in Worten. Ein Programm brauchst du nicht.

Vorlage: KV-Diagramm mit den Variablen T, S, R

Meine Begründung:

Lösung vergleichen

Die Belegungstabelle (siehe Abschnitt über die DNF) hat Einsen in den Zeilen 1, 3, 5, 6 und 7:

KV-Diagramm der Alarmanlage (T: Tür, S: Scharf, R: Rauch)

Die vier Felder mit R=1R = 1 (die beiden mittleren Spalten) bilden einen Viererblock: Term RR. Die Felder 6 und 7 bilden einen Zweierblock mit T=1T = 1 und S=1S = 1: Term T∧ST \land S. Größere Blöcke gibt es nicht, weil die Felder 0, 2 und 4 den Wert 0 haben.

Das KV-Diagramm liefert also R∨(T∧S)R \lor (T \land S). Das ist genau der Term, von dem wir ausgegangen sind (nur die Reihenfolge ist anders). Er ist also bereits minimal. Das sieht man auch so: Der Ausgang hängt von allen drei Eingängen ab, und um drei Eingänge zu verknüpfen, braucht man mindestens zwei Gatter mit zwei Eingängen. Weniger als zwei Gatter geht also nicht.

So kannst du es sagen

So sprichst du über KV-Diagramme – vom einfachen zum genauen Satz:

Arbeitsauftrag 93 (Zusatz): Vier Variablen, ein Block

Erstelle selbst eine Belegungstabelle mit vier Variablen AA, BB, CC, DD und mindestens vier 1-Zeilen, die sich zu einem einzigen Block zusammenfassen lassen. Gib die DNF und die minimierte Form an. Prüfe deine Minimierung mit Python. Tipp: Verwende vier geschachtelte Schleifen und eine Variable aequivalent wie im Abschnitt über Äquivalenz.

Meine Tabelle (als Liste der 1-Zeilen), DNF und minimierte Form:

Lösung vergleichen

Eine mögliche Lösung: Der Ausgang ist genau in den Zeilen 5, 7, 13 und 15 gleich 1.

Beispiellösung: vier Einsen in einem Block B \land D

Die vier Felder bilden einen Viererblock in der Mitte. B=1B = 1 und D=1D = 1 sind konstant, AA und CC wechseln. Die minimierte Form lautet B∧DB \land D. Die DNF lautet

(¬A∧B∧¬C∧D)∨(¬A∧B∧C∧D)∨(A∧B∧¬C∧D)∨(A∧B∧C∧D).(\lnot A \land B \land \lnot C \land D) \lor (\lnot A \land B \land C \land D) \lor (A \land B \land \lnot C \land D) \lor (A \land B \land C \land D).

def dnf(a, b, c, d):
    m5 = not a and b and not c and d
    m7 = not a and b and c and d
    m13 = a and b and not c and d
    m15 = a and b and c and d
    return bool(m5 or m7 or m13 or m15)

def minimiert(a, b, c, d):
    return bool(b and d)

aequivalent = True
for a in [0, 1]:
    for b in [0, 1]:
        for c in [0, 1]:
            for d in [0, 1]:
                if dnf(a, b, c, d) != minimiert(a, b, c, d):
                    aequivalent = False

print("Äquivalent:", aequivalent)
Äquivalent: True

bool(...) sorgt dafür, dass beide Funktionen True oder False liefern. Weitere richtige Lösungen: zum Beispiel die vier Ecken (Zeilen 0, 2, 8, 10, Term ¬B∧¬D\lnot B \land \lnot D) oder eine ganze Zeile des Diagramms (Zeilen 4, 5, 6, 7, Term ¬A∧B\lnot A \land B). Auch ein Achterblock ist erlaubt.

2.8.7Weitere Übungen

Hier kannst du das Gelernte weiter üben. Die Punkte im Titel zeigen, wie schwer eine Aufgabe ist: ●○○ leicht, ●●○ mittel, ●●● knifflig. Fang mit den leichten an.

Arbeitsauftrag 94: Unterscheiden sich die Felder in genau einer Variablen? ●○○

Im KV-Diagramm werden nur Felder zu einem Zweierblock zusammengefasst, die sich in genau einer Variablen unterscheiden. Gib für jedes Paar von Belegungen (AA, BB, CC) an, in wie vielen Variablen sie sich unterscheiden und ob man sie zu einem Zweierblock zusammenfassen darf.

Belegung 1 Belegung 2 Anzahl verschiedener Variablen Zweierblock erlaubt?
0 0 0 0 0 1
0 1 1 1 1 1
0 0 1 0 1 0
1 1 0 1 1 1
1 0 1 1 1 0
0 1 0 1 1 0
Lösung vergleichen
Belegung 1 Belegung 2 Anzahl verschiedener Variablen Zweierblock erlaubt?
0 0 0 0 0 1 1 (CC) ja
0 1 1 1 1 1 1 (AA) ja
0 0 1 0 1 0 2 (BB und CC) nein
1 1 0 1 1 1 1 (CC) ja
1 0 1 1 1 0 2 (BB und CC) nein
0 1 0 1 1 0 1 (AA) ja

In einem Zweierblock fällt genau die Variable weg, in der sich die beiden Felder unterscheiden. Bei zwei verschiedenen Variablen geht das nicht.

Arbeitsauftrag 95: Eine Tabelle ins KV-Diagramm übertragen ●○○

Übertrage die Belegungstabelle in das KV-Diagramm. Achte auf die Reihenfolge der Spalten: 00, 01, 11, 10.

AA BB CC Ausgang
0 0 0 1
0 0 1 1
0 1 0 0
0 1 1 0
1 0 0 0
1 0 1 1
1 1 0 0
1 1 1 1
Vorlage zum Ausfüllen: KV-Diagramm für drei Variablen
Lösung vergleichen
Lösung: das ausgefüllte KV-Diagramm

Die Zeile gibt AA an, die Spalte BB und CC zusammen. Die Belegung A=1A = 1, B=1B = 1, C=0C = 0 steht also in der unteren Zeile in der letzten Spalte (BC=10BC = 10), nicht in der dritten. Wer die Spalten in der Reihenfolge 00, 01, 10, 11 füllt, vertauscht die beiden rechten Spalten.

Arbeitsauftrag 96: Blöcke ablesen ●○○

Gib zu jedem eingezeichneten Block den Term an.

Drei KV-Diagramme mit eingezeichneten Blöcken

Deine Terme:

Lösung vergleichen
  1. Im Block ist B=1B = 1, AA wechselt. Term: BB.
  2. Im Block ist A=1A = 1 und C=1C = 1, BB wechselt (Spalten 01 und 11). Term: A∧CA \land C.
  3. Der Block ist die ganze obere Zeile. Dort ist nur A=0A = 0 konstant, BB und CC wechseln. Term: ¬A\lnot A.

Prüfe bei jeder Variablen: Hat sie im ganzen Block denselben Wert? Nur dann bleibt sie im Term, mit ¬\lnot, wenn der Wert 0 ist.

Arbeitsauftrag 97: Minimieren mit zwei Variablen ●○○

Vereinfache die DNF mithilfe eines KV-Diagramms.

  1. (A∧¬B)∨(A∧B)(A \land \lnot B) \lor (A \land B)
  2. (¬A∧¬B)∨(¬A∧B)∨(A∧B)(\lnot A \land \lnot B) \lor (\lnot A \land B) \lor (A \land B)
Vorlagen für a) und b)

Deine vereinfachten Terme:

Lösung vergleichen
Lösung zu a): ein Zweierblock mit A = 1
  1. Die beiden Einsen stehen in der unteren Zeile. Dort ist A=1A = 1, BB wechselt. Ergebnis: AA.
Lösung zu b): zwei Zweierblöcke, die sich im Feld A = 0, B = 1 überlappen
  1. Die obere Zeile ist ein Block mit A=0A = 0, die rechte Spalte ein Block mit B=1B = 1. Das Feld A=0A = 0, B=1B = 1 liegt in beiden Blöcken. Das ist erlaubt. Ergebnis: ¬A∨B\lnot A \lor B.
Arbeitsauftrag 98: Minimieren mit drei Variablen ●●○

Die Tabelle enthält zwei Ausgänge QaQ_a und QbQ_b. Vereinfache beide mit je einem KV-Diagramm. Prüfe dein Ergebnis zu QbQ_b mit Python: Vergleiche für alle Belegungen deine vereinfachte Form mit der DNF.

AA BB CC QaQ_a QbQ_b
0 0 0 0 0
0 0 1 0 1
0 1 0 1 0
0 1 1 1 1
1 0 0 0 0
1 0 1 0 0
1 1 0 1 1
1 1 1 1 1
Vorlagen für Q_a und Q_b

Deine vereinfachten Terme:

Lösung vergleichen
Lösung zu a): ein Viererblock mit B = 1
  1. Die vier Einsen stehen in den beiden rechten Spalten (BC=11BC = 11 und BC=10BC = 10). Dort ist B=1B = 1, AA und CC wechseln. Ergebnis: Qa=BQ_a = B.
Lösung zu b): zwei Zweierblöcke
  1. Die Felder A=0A = 0, BC=01BC = 01 und A=0A = 0, BC=11BC = 11 bilden einen Block mit A=0A = 0, C=1C = 1. Die Felder A=1A = 1, BC=11BC = 11 und A=1A = 1, BC=10BC = 10 bilden einen Block mit A=1A = 1, B=1B = 1. Ergebnis: Qb=(¬A∧C)∨(A∧B)Q_b = (\lnot A \land C) \lor (A \land B).
def dnf_b(a, b, c):
    m1 = not a and not b and c
    m2 = not a and b and c
    m3 = a and b and not c
    m4 = a and b and c
    return int(m1 or m2 or m3 or m4)

def minimiert_b(a, b, c):
    return int((not a and c) or (a and b))

for a in [0, 1]:
    for b in [0, 1]:
        for c in [0, 1]:
            gleich = dnf_b(a, b, c) == minimiert_b(a, b, c)
            print(a, b, c, "->", gleich)
0 0 0 -> True
0 0 1 -> True
0 1 0 -> True
0 1 1 -> True
1 0 0 -> True
1 0 1 -> True
1 1 0 -> True
1 1 1 -> True

Bei b) gibt es auch einen Zweierblock aus den beiden Feldern mit BC=11BC = 11. Er wird aber nicht gebraucht, denn diese beiden Einsen liegen schon in den anderen Blöcken. So wenige Blöcke wie möglich!

Arbeitsauftrag 99: Fehler im KV-Diagramm ●●○

Tom hat ein KV-Diagramm ausgefüllt und die drei Einsen mit einem Block umrandet. Daraus liest er den Term ¬A\lnot A ab.

Toms KV-Diagramm
  1. Erkläre, welche Regel Tom verletzt hat.
  2. Zeige mit einer Belegung, dass sein Term ¬A\lnot A falsch ist.
  3. Gib den richtigen vereinfachten Term an.

Deine Antwort:

Lösung vergleichen
  1. Ein Block muss aus 1, 2, 4 oder 8 Feldern bestehen. Einen Block aus drei Feldern gibt es nicht.
  2. ¬A\lnot A ist auch bei A=0A = 0, B=0B = 0, C=0C = 0 gleich 1. In diesem Feld steht aber eine 0.
  3. Drei Einsen nebeneinander deckt man mit zwei Zweierblöcken ab, die sich überlappen:
Richtig: zwei Zweierblöcke, die sich überlappen

Rot (A=0A = 0, C=1C = 1): ¬A∧C\lnot A \land C. Blau (A=0A = 0, B=1B = 1): ¬A∧B\lnot A \land B. Ergebnis: (¬A∧C)∨(¬A∧B)(\lnot A \land C) \lor (\lnot A \land B).

Arbeitsauftrag 100: Eine sparsame Schaltung ●●○

Der Ausgang QQ einer Schaltung soll genau bei diesen Belegungen 1 sein: (0,1,1)(0, 1, 1), (1,0,0)(1, 0, 0), (1,0,1)(1, 0, 1), (1,1,0)(1, 1, 0) und (1,1,1)(1, 1, 1). Die Werte stehen in der Reihenfolge AA, BB, CC.

  1. Wie viele Minterme hätte die DNF?
  2. Vereinfache mit einem KV-Diagramm.
  3. Skizziere die Schaltung zum vereinfachten Term und gib an, wie viele Gatter sie braucht.
Vorlage zum Ausfüllen: KV-Diagramm für drei Variablen

Dein Term und deine Skizze:

Lösung vergleichen
  1. Fünf Minterme, für jede 1-Zeile einen.
  2. Vereinfachung:
Lösung: ein Viererblock und ein Zweierblock

Die ganze untere Zeile ist ein Viererblock mit A=1A = 1. Das Feld (0,1,1)(0, 1, 1) bildet mit dem Feld darunter einen Zweierblock mit B=1B = 1, C=1C = 1. Ergebnis: Q=A∨(B∧C)Q = A \lor (B \land C).

  1. Die Schaltung braucht nur zwei Gatter:
Schaltung zu Q = A \lor (B \land C)

Die DNF mit fünf Mintermen aus je drei Variablen bräuchte viel mehr Gatter. Beide Schaltungen tun genau dasselbe.

Arbeitsauftrag 101: Vier Variablen ●●●

Vereinfache die DNF mit einem KV-Diagramm für vier Variablen. Prüfe dein Ergebnis mit Python.

(¬A∧B∧¬C∧¬D)∨(¬A∧B∧¬C∧D)∨(A∧B∧¬C∧¬D)(\lnot A \land B \land \lnot C \land \lnot D) \lor (\lnot A \land B \land \lnot C \land D) \lor (A \land B \land \lnot C \land \lnot D) ∨(A∧B∧¬C∧D)∨(A∧B∧C∧D)\lor\; (A \land B \land \lnot C \land D) \lor (A \land B \land C \land D)

Vorlage: KV-Diagramm für vier Variablen
Tipp

Die Zeilen des Diagramms geben AA und BB an, die Spalten CC und DD. Beide folgen der Reihenfolge 00, 01, 11, 10. Trage für jeden Minterm eine 1 ein: Für ¬A∧B∧¬C∧D\lnot A \land B \land \lnot C \land D zum Beispiel in die Zeile AB=01AB = 01 und die Spalte CD=01CD = 01.

Dein vereinfachter Term:

Lösung vergleichen
Lösung: ein Viererblock (rot) und ein Zweierblock (blau)
  • Rot: Die vier Einsen in den Zeilen AB=01AB = 01 und AB=11AB = 11 und den Spalten CD=00CD = 00 und CD=01CD = 01 bilden einen Viererblock. Konstant sind B=1B = 1 und C=0C = 0. Term: B∧¬CB \land \lnot C.
  • Blau: Die Eins bei A=1A = 1, B=1B = 1, C=1C = 1, D=1D = 1 hat keinen Viererblock. Sie bildet mit dem Feld links daneben (CD=01CD = 01) einen Zweierblock. Konstant sind A=1A = 1, B=1B = 1, D=1D = 1. Term: A∧B∧DA \land B \land D.

Ergebnis: (B∧¬C)∨(A∧B∧D)(B \land \lnot C) \lor (A \land B \land D).

def dnf(a, b, c, d):
    m1 = not a and b and not c and not d
    m2 = not a and b and not c and d
    m3 = a and b and not c and not d
    m4 = a and b and not c and d
    m5 = a and b and c and d
    return int(m1 or m2 or m3 or m4 or m5)

def minimiert(a, b, c, d):
    return int((b and not c) or (a and b and d))

aequivalent = True
for a in [0, 1]:
    for b in [0, 1]:
        for c in [0, 1]:
            for d in [0, 1]:
                if dnf(a, b, c, d) != minimiert(a, b, c, d):
                    aequivalent = False
print("Äquivalent:", aequivalent)
Äquivalent: True

Die Zeilen AB=01AB = 01 und AB=11AB = 11 stehen im Diagramm direkt untereinander und unterscheiden sich nur in AA. Deshalb dürfen sie in einen Block. Typischer Fehler: die Eins bei A=B=C=D=1A = B = C = D = 1 vergessen oder als eigenen Einerblock mit vier Variablen stehen lassen. Das ist richtig, aber nicht minimal.

2.8.8Das Wichtigste in Kürze

Selbstcheck

2.9Kapitel 2 kompakt: der Lernzettel

Diesen Abschnitt als PDF (S. 130–132)

Leitidee

Dieser Lernzettel fasst das Kapitel auf wenigen Seiten zusammen. Nutze ihn zum Wiederholen vor einem Test. Ausführliche Erklärungen, Beispiele und Übungen findest du in den einzelnen Abschnitten.

2.9.1Grundgatter, Belegungstabellen, Schaltungsentwurf (Abschnitte 2.1 und 2.2)

Die vier Grundgatter als IEC-Symbole. CircuitVerse zeigt sie als US-Symbole
Gatter Zeichen Term Ausgang 1, wenn …
UND (AND) & A∧BA \land B alle Eingänge 1 sind
ODER (OR) ≥1 A∨BA \lor B mindestens ein Eingang 1 ist
XOR =1 A⊕BA \oplus B die Eingänge unterschiedlich sind
NICHT (NOT) 1 mit Kreis ¬A\lnot A der Eingang 0 ist (Gegenteil)
AA BB A∧BA \land B A∨BA \lor B A⊕BA \oplus B ¬A\lnot A
0 0 0 0 0 1
0 1 0 1 1 1
1 0 0 1 1 0
1 1 1 1 0 0

Typische Fehler: ODER und XOR verwechseln (Unterschied nur bei 1 1); eine Zeile der Tabelle vergessen; die Bedeutung von 0 und 1 nicht festlegen; Klammern vergessen ((T∧S)∨R(T \land S) \lor R ist nicht T∧(S∨R)T \land (S \lor R)).

2.9.2Binäre Addition, Halb- und Volladdierer (Abschnitte 2.3 und 2.4)

      0 1 0 1     (= 5)
    + 0 0 1 1     (= 3)
  Ü   1 1 1
    ---------
      1 0 0 0     (= 8)

Typische Fehler: „1 + 1 = 2“ schreiben; Übertrag vergessen oder unter die falsche Stelle schreiben; den letzten Übertrag ganz links weglassen; beim Volladdierer ein UND statt des ODER-Gatters am Ende.

2.9.3Rückkopplung und Flipflop (Abschnitt 2.5)

Typische Fehler: bei S=R=0S = R = 0 einfach 0 eintragen statt den alten Wert; SS und RR vertauschen.

2.9.4Aussagenlogik und Termbäume (Abschnitt 2.6)

Name Zeichen Gatter Python
Negation ¬A\lnot A NICHT not a
Konjunktion A∧BA \land B UND a and b
Disjunktion A∨BA \lor B ODER a or b

Typische Fehler: ¬(A∨B)\lnot (A \lor B) und ¬A∨B\lnot A \lor B verwechseln (das ¬\lnot gilt nur für das, was direkt dahinter steht); die falsche Wurzel wählen; ⊕\oplus in einen Term schreiben (gehört nicht zu den Regeln).

2.9.5Äquivalenz und DNF (Abschnitt 2.7)

Typische Fehler: ¬\lnot an die Variablen mit Wert 1 setzen; eine Variable im Minterm vergessen; Zeilen mit Ausgang 0 verwenden; ∧\land und ∨\lor vertauschen.

2.9.6KV-Diagramme (Abschnitt 2.8)

Links: ein Viererblock mit B = 0, Ergebnis \lnot B. Rechts: Mehrheit, drei Zweierblöcke, Ergebnis (B \land C) \lor (A \land C) \lor (A \land B)

Typische Fehler: Spalten in der Reihenfolge 00, 01, 10, 11 anlegen; diagonale Felder zusammenfassen; Dreierblöcke bilden; zu kleine Blöcke wählen (richtig, aber nicht minimal); eine 1 in keinem Block vergessen.

2.10Rückblick auf Kapitel 2

Diesen Abschnitt als PDF (S. 133–134)

Leitidee

Am Ende des Kapitels lohnt sich ein Blick zurück: Welche Fachbegriffe kennst du jetzt? Was kannst du schon sicher, was solltest du noch einmal üben? Die Tabellen helfen dir dabei, zum Beispiel bei der Vorbereitung auf eine Klassenarbeit.

2.10.1Die Basisbegriffe

Begriff Bedeutung
logische Schaltung verarbeitet Eingangswerte 0 und 1 zu Ausgangswerten 0 und 1
Grundgatter einfachste Bausteine: UND (AND), ODER (OR), XOR, NICHT (NOT)
Belegungstabelle listet für jede Kombination der Eingangswerte die Ausgangswerte auf
Halbaddierer addiert zwei Bits; liefert Summe SS und Übertrag CC
Volladdierer addiert drei Bits (zwei Summanden und einen Übertrag); liefert Summe und Übertrag
Carry-Ripple-Addierer hintereinandergeschaltete Volladdierer, die mehrstellige Binärzahlen addieren; der Übertrag wandert von Stelle zu Stelle
Rückkopplung ein Ausgang wird wieder an einen Eingang zurückgeführt
Flipflop Schaltung mit Rückkopplung, die ein Bit speichert
Konjunktion UND-Verknüpfung A∧BA \land B: nur wahr, wenn beide wahr sind
Disjunktion ODER-Verknüpfung A∨BA \lor B: wahr, wenn mindestens einer wahr ist
Negation NICHT ¬A\lnot A: kehrt den Wahrheitswert um
Termbaum stellt den Aufbau eines Terms als Baum dar; die Wurzel ist der zuletzt ausgewertete Operator
Äquivalenz Zwei Terme sind äquivalent, wenn sie für jede Belegung denselben Wert haben (gleiche Belegungstabelle).
Regeln von De Morgan ¬(A∧B)\lnot (A \land B) ist äquivalent zu ¬A∨¬B\lnot A \lor \lnot B; ¬(A∨B)\lnot (A \lor B) ist äquivalent zu ¬A∧¬B\lnot A \land \lnot B
Disjunktive Normalform (DNF) ODER-Verknüpfung der Minterme; jede 1-Zeile der Belegungstabelle ergibt einen Minterm (UND-Verknüpfung aller Variablen)
Karnaugh-Veitch-Diagramm Anordnung der Belegungstabelle, in der benachbarte Felder sich in genau einer Variablen unterscheiden; dient zum Vereinfachen der DNF

2.10.2Kompetenz-Check

Ich kann … sicher teilweise noch nicht
die Grundgatter nennen und skizzieren und ihre Belegungstabellen angeben.
zu einer gegebenen Schaltung die Belegungstabelle erstellen.
in einem Sachzusammenhang eine Schaltung entwerfen, auch mit einem Simulator.
zwei natürliche Zahlen im Binärsystem addieren.
Aufbau und Funktionsweise von Halb- und Volladdierer erläutern.
einen Carry-Ripple-Addierer skizzieren und seine Funktionsweise erläutern.
ein Flipflop skizzieren und erklären, wie es durch Rückkopplung ein Bit speichert.
Schaltungen durch Terme beschreiben und Terme in Schaltungen übertragen.
aussagenlogische Terme induktiv definieren und als Termbaum darstellen.
die Begriffe Konjunktion, Disjunktion und Negation sachgemäß verwenden.
zu einem Term die Belegungstabelle erstellen.
erläutern, wann zwei Terme äquivalent sind.
die Regeln von De Morgan nennen und anwenden.
die DNF zu einem Term oder einer Belegungstabelle aufstellen.
eine DNF mit bis zu vier Variablen mit einem KV-Diagramm vereinfachen.
Informatik 10 | Logische SchaltungenDruckfassung (PDF)