
Kapitel 2
Logische Schaltungen und Aussagenlogik
Skript Informatik · Klasse 10 · MINT
Notebooks in diesem Kapitel DS15–DS22
- DS15 Grundgatter und Belegungstabellen
- DS16 Schaltungen entwerfen: vom Text zur Schaltung
- DS17 Addition im Binärsystem und Halbaddierer
- DS18 Volladdierer und Carry-Ripple-Addierer
- DS19 Rückkopplung: Das Flipflop speichert ein Bit
- DS20 Aussagenlogik: Schaltungen als Terme beschreiben
- DS21 Belegungstabellen, Äquivalenz und disjunktive Normalform
- DS22 KV-Diagramme: Terme vereinfachen, Schaltungen sparen
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:
- Grundgatter und Belegungstabellen – die Bausteine UND, ODER, XOR und NICHT und wie man ihr Verhalten in Tabellen festhält.
- Schaltungen entwerfen – aus einer Beschreibung in Worten wird Schritt für Schritt eine Schaltung.
- Addition im Binärsystem und Halbaddierer – schriftlich rechnen mit 0 und 1 und die erste rechnende Schaltung.
- Volladdierer und Carry-Ripple-Addierer – wie ein Computer ganze Binärzahlen addiert.
- Das Flipflop – eine Schaltung, die sich durch Rückkopplung ein Bit merkt.
- Aussagenlogik – Schaltungen als Terme schreiben und als Termbaum darstellen.
- Äquivalenz und disjunktive Normalform – wann zwei Terme dasselbe leisten und wie man zu jeder Tabelle einen Term findet.
- KV-Diagramme – Terme vereinfachen, damit Schaltungen mit weniger Gattern auskommen.
Mit diesen Satzanfängen beschreibst und begründest du deine Ergebnisse in diesem Kapitel:
- „Der Term/die Tabelle repräsentiert die Schaltung, weil …“
- „Die Rückkopplung bzw. Gruppierung bewirkt …“
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.
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.
Nach diesem Abschnitt kannst du
- die vier Grundgatter UND (AND), ODER (OR), XOR und NICHT (NOT) nennen und mit ihren Symbolen skizzieren,
- zu jedem Grundgatter die Belegungstabelle angeben,
- begründen, warum es bei Eingängen Belegungen gibt,
- zu einer Schaltung aus mehreren Gattern die Belegungstabelle mit Hilfsspalten erstellen,
- Gatter im Simulator CircuitVerse aufbauen und testen,
- Belegungstabellen mit Python nachprüfen.
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 , , , den Ausgang oft mit .
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.
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.
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):
| 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 eine 1 und an 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 (gelesen: „A und B“). Das Zeichen 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.
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 mit jeder der 2 Möglichkeiten von kombinieren: Zeilen. Jeder weitere Eingang verdoppelt die Anzahl:
| Anzahl der Eingänge | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|
| Anzahl der Belegungen | 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.
- Eine Belegungstabelle (Wahrheitstabelle) listet für jede mögliche Kombination von Eingangswerten den zugehörigen Ausgangswert auf.
- Bei Eingängen gibt es mögliche Belegungen.
- Wie viele Zeilen hat die Belegungstabelle einer Schaltung mit 3 Eingängen, wie viele bei 6 Eingängen?
- Schreibe die Eingangsspalten , , einer Belegungstabelle mit 3 Eingängen in der richtigen Reihenfolge auf.
Deine Antwort:
Lösung vergleichen
- Bei 3 Eingängen sind es Zeilen, bei 6 Eingängen Zeilen.
- In der Spalte wechseln 0 und 1 in jeder Zeile, in der Spalte alle zwei Zeilen, in der Spalte alle vier Zeilen:
| 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.
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 1 |
Das Zeichen steht für ODER; liest man „A oder B“. Die ODER-Verknüpfung heißt in der Logik auch Disjunktion.
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.
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 0 |
Das Zeichen 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.
| 0 | 1 |
| 1 | 0 |
Das Zeichen steht für NICHT; 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.
| 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 beschreibst du ein Gatter in Fachsprache – vom einfachen zum genauen Satz:
- „Da kommt 1 raus, wenn beide 1 sind.“ → „Das UND-Gatter liefert genau dann eine 1, wenn an beiden Eingängen eine 1 anliegt.“
- „Bei 1 und 0 gibt es eine 1.“ → „Zu der Belegung , gehört beim ODER-Gatter der Ausgangswert 1.“
- „Die Zeile 1, 1, 0 heißt …“ → „Die letzte Zeile der Belegungstabelle besagt: Liegen an beiden Eingängen des XOR-Gatters Einsen an, ist der Ausgangswert 0.“
Skizziere die vier Grundgatter UND, ODER, XOR und NICHT mit ihren IEC-Symbolen. Beschrifte jeweils die Eingänge mit und (beim NICHT-Gatter nur ) und den Ausgang mit . Schreibe unter jedes Gatter seinen Namen und in einem kurzen Satz, wann sein Ausgang 1 ist.
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
- UND (
&): ist 1, wenn und beide 1 sind. - ODER (
≥1): ist 1, wenn mindestens einer der Eingänge 1 ist. - XOR (
=1): ist 1, wenn und unterschiedlich sind. - NICHT (
1mit Kreis am Ausgang): ist das Gegenteil von .
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:
- Öffne die Seite
circuitverse.org/simulator. - Im linken Bereich findest du unter Input den Baustein Input. Das ist ein Schalter, der 0 oder 1 liefert. Ziehe zwei davon ins Arbeitsfeld.
- 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.
- Unter Gates findest du AND, OR, XOR und NOT. Ziehe ein Gatter zwischen die Schalter und die Anzeige.
- Verbinde die Bausteine mit Leitungen: Klicke auf einen Anschluss, halte die Maustaste gedrückt und ziehe zum anderen Anschluss.
- Klicke auf einen Input-Schalter. Er wechselt zwischen 0 und 1. Beobachte, was die Anzeige am Ausgang zeigt.
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.
| Ausgang AND | Ausgang OR | Ausgang XOR | ||
|---|---|---|---|---|
| 0 | 0 | |||
| 0 | 1 | |||
| 1 | 0 | |||
| 1 | 1 |
| Ausgang NOT | |
|---|---|
| 0 | |
| 1 |
Lösung vergleichen
| AND | OR | XOR | ||
|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 |
| 0 | 1 | 0 | 1 | 1 |
| 1 | 0 | 0 | 1 | 1 |
| 1 | 1 | 1 | 1 | 0 |
| 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.
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
- Zeilen 1–8: Drei Funktionen, eine für jedes Gatter. Jede bekommt die beiden Eingangswerte als Parameter und gibt den Ausgangswert 0 oder 1 zurück.
- Zeile 10: Die Kopfzeile der Tabelle.
- Zeilen 11–12: Die äußere Schleife setzt
anacheinander auf 0 und 1. Für jeden dieser Werte läuft die innere Schleife einmal ganz durch und setztbauf 0 und 1. So entstehen die vier Belegungen in der üblichen Reihenfolge: 0 0, 0 1, 1 0, 1 1. - Zeile 13: Ein f-String gibt die Belegung und die drei Ausgangswerte in einer Zeile aus.
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
- Zeilen 1–2: Die Funktion
nichtbekommt nur einen Eingangswert.not adreht ihn um,int(...)macht daraus wieder 0 oder 1. - Zeilen 4–5: Die Schleife setzt
anacheinander auf 0 und 1 und gibt jeweils Eingang und Ausgang aus.
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 , , und einen Ausgang .
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.
- Das NICHT-Gatter dreht um. Die erste Hilfsspalte ist .
- Das UND-Gatter verknüpft mit dem Ausgang des NICHT-Gatters. Die zweite Hilfsspalte ist . Sie ist nur dort 1, wo und beide 1 sind.
- Das ODER-Gatter verknüpft diese Leitung mit . Das ergibt den Ausgang . Er ist 1, wo die zweite Hilfsspalte oder eine 1 enthält.
| 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 , , der Ausgangswert gehört. Das stimmt: ist 1, also ist auch gleich 1, und damit ist das ODER-Gatter erfüllt.
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.
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.
Erstelle die Belegungstabelle zur folgenden Schaltung. Fülle dazu die Hilfsspalten von links nach rechts aus. Mit welchem Grundgatter stimmt die letzte Spalte überein?
| 0 | 0 | ||||
| 0 | 1 | ||||
| 1 | 0 | ||||
| 1 | 1 |
Die letzte Spalte stimmt überein mit:
Lösung vergleichen
Die Schaltung berechnet :
| 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 (), aber nicht beide ()“ heißt „genau eine 1“. Ein XOR-Gatter lässt sich also aus UND, ODER und NICHT zusammensetzen.
Baue in CircuitVerse eine Schaltung mit drei Eingängen , , , 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.
- Fülle die Belegungstabelle aus.
- Skizziere die Schaltung mit IEC-Symbolen.
- Teste deine Schaltung in CircuitVerse mit allen acht Belegungen.
Tipp: Die Schaltung lässt sich als beschreiben: Entweder sind und beide 1, oder und , oder und . In CircuitVerse kannst du beim OR-Gatter die Anzahl der Eingänge auf 3 stellen oder zwei OR-Gatter hintereinanderschalten.
| 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
| 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 |
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
Zu vier unbekannten Gattern mit den Eingängen und wurden die Ausgangswerte bis gemessen. Gib jeweils an, um welches Gatter es sich handelt. Eine der vier Spalten passt zu keinem Grundgatter. Begründe, woran du das erkennst.
| 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
- ist nur bei 0 0 eine 0, sonst 1: ODER.
- ist nur bei 1 1 eine 1: UND.
- ist 1, wenn die Eingänge unterschiedlich sind: XOR.
- ist genau das Gegenteil von , also das Gegenteil von UND. Das ist kein Grundgatter, sondern ein UND-Gatter mit einem NICHT-Gatter dahinter: .
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.
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.
Deine Antwort:
Lösung vergleichen
- XOR (Kennzeichen
=1): Der Ausgang ist 1, wenn die beiden Eingänge unterschiedlich sind. - UND (Kennzeichen
&): Der Ausgang ist 1, wenn alle Eingänge 1 sind. - NICHT (Kennzeichen
1mit Kreis am Ausgang): Der Ausgang ist das Gegenteil des Eingangs. - 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“.
Bestimme für jede Zeile den Ausgangswert des Gatters. Beim NICHT-Gatter gibt es nur den Eingang .
| Gatter | 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 | 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 , : Die Eingänge sind gleich, deshalb liefert XOR eine 0. Das ODER-Gatter liefert dagegen eine 1.
Gib zu jeder Situation das passende Grundgatter an. Begründe kurz.
- Ein Handy lässt sich entsperren, wenn der Fingerabdruck erkannt wird oder die richtige PIN eingegeben wird.
- Ein Online-Spiel startet nur, wenn du eingeloggt bist und das Internet verbunden ist.
- 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.
- Die Warnleuchte am Wasserkocher leuchtet, wenn kein Wasser im Kocher ist. (Eingang: 1 = Wasser ist im Kocher.)
Deine Antwort:
Lösung vergleichen
- ODER: Eines von beiden genügt. Wenn Fingerabdruck und PIN beide stimmen, wird das Handy natürlich auch entsperrt.
- UND: Beide Bedingungen müssen erfüllt sein.
- 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.
- NICHT: Die Leuchte zeigt das Gegenteil des Eingangs. Ist Wasser im Kocher (1), ist sie aus (0).
Bei dieser Belegungstabelle für drei Eingänge fehlt eine Zeile.
- Gib an, wie viele Zeilen die Tabelle haben muss.
- Bestimme die fehlende Belegung und gib an, an welcher Stelle sie eingefügt werden muss.
| 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
- Bei 3 Eingängen gibt es Belegungen, also 8 Zeilen. Hier sind es nur 7.
- Es fehlt die Belegung , , . Sie gehört zwischen die Zeilen 1 0 0 und 1 1 0.
So findest du die Lücke schnell: In der Spalte müssen sich 0 und 1 in jeder Zeile abwechseln. Nach 1 0 0 steht aber wieder eine 0 in der Spalte .
Erstelle zu beiden Schaltungen die Belegungstabelle. Fülle die Hilfsspalten aus. Beschreibe danach in Worten, wann ist.
| 0 | 0 | ||||
| 0 | 1 | ||||
| 1 | 0 | ||||
| 1 | 1 |
Deine Beschreibung:
Lösung vergleichen
Schaltung a) berechnet , Schaltung b) berechnet :
| 0 | 0 | 1 | 0 | 0 | 1 |
| 0 | 1 | 1 | 1 | 1 | 0 |
| 1 | 0 | 0 | 0 | 1 | 0 |
| 1 | 1 | 0 | 0 | 0 | 1 |
ist nur bei , gleich 1. ist das Gegenteil von XOR: ist 1, wenn die beiden Eingänge gleich sind. Die Schaltung b) prüft also, ob und übereinstimmen.
Typischer Fehler bei a): das NICHT-Gatter übersehen und einfach ausrechnen. Rechne immer zuerst die Hilfsspalte aus.
Erstelle die Belegungstabelle zur folgenden Schaltung. Gib danach alle Belegungen an, für die ist.
| 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 :
| 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 |
gilt bei den Belegungen 0 1 1, 1 0 1 und 1 1 1. In Worten: muss 1 sein, und außerdem muss mindestens einer der Eingänge , eine 1 haben.
Ü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.
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.
In der folgenden Schaltung ist der Ausgang eines XOR-Gatters mit einem zweiten XOR-Gatter verbunden.
- Erstelle die Belegungstabelle mit der Hilfsspalte .
- 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 ist.
| 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
| 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 |
ist 1, wenn eine ungerade Anzahl der Eingänge 1 ist, also genau eine oder alle drei. Bei null oder zwei Einsen ist .
Achtung, die letzte Zeile: ist 0, weil und gleich sind. Das zweite XOR-Gatter bekommt also 0 und 1 und liefert . 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
- In logischen Schaltungen hat jede Leitung den Wert 0 oder 1 (ein Bit).
- Die vier Grundgatter: UND (
&, , alle Eingänge 1), ODER (≥1, , mindestens ein Eingang 1), XOR (=1, , Eingänge unterschiedlich), NICHT (1mit Kreis am Ausgang, , Gegenteil des Eingangs). - Eine Belegungstabelle listet zu jeder Kombination der Eingangswerte den Ausgangswert auf. Bei Eingängen hat sie Zeilen.
- Bei Schaltungen aus mehreren Gattern rechnet man von links nach rechts und legt für jede Zwischenleitung eine Hilfsspalte an.
- In Zeichnungen verwendet man die IEC-Symbole. CircuitVerse zeigt die US-Symbole; sie bedeuten dasselbe.
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.
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.
Nach diesem Abschnitt kannst du
- zu einer Beschreibung in Worten die Eingänge und Ausgänge einer Schaltung festlegen,
- die Belegungstabelle aufstellen, die die Beschreibung erfüllt,
- die Beschreibung in einen logischen Term übersetzen und daraus die Schaltung skizzieren,
- die Schaltung in CircuitVerse aufbauen und mit allen Belegungen testen,
- dein Ergebnis mit einem kurzen Python-Programm nachprüfen.
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.
Beim Schaltungsentwurf übersetzt man eine Anforderung in Textform zunächst in eine Belegungstabelle, danach in eine passende Gatterkombination. Vorgehen:
- Eingangs- und Ausgangsgrößen benennen (und festlegen, was 0 und 1 jeweils bedeuten).
- Belegungstabelle aufstellen: alle Fälle durchgehen und markieren, in welchen der Ausgang 1 sein soll.
- Passende Gatter auswählen und verschalten. Dabei hilft ein logischer Term.
- 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 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 | 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:
- Zeile 2 (0, 0, 1): Die Tür ist zu, die Anlage ist aus, aber es brennt. Es muss Alarm geben.
- Zeile 5 (1, 0, 0): Die Tür ist offen, aber die Anlage ist nicht scharf. Das ist der normale Fall, wenn jemand zu Hause ist und das Haus betritt. Kein Alarm.
- Zeile 7 (1, 1, 0): Die Tür wird geöffnet, während die Anlage scharf ist. Das könnte ein Einbruch sein. Alarm.
Schritt 3: Term und Schaltung
Jetzt übersetzt du die Beschreibung in einen logischen Term. Der Satz hat zwei Teile, die durch „oder“ verbunden sind:
- „die Tür ist geöffnet und die Anlage ist scharfgeschaltet“ wird zu ,
- „der Rauchmelder schlägt an“ ist einfach .
Beide Teile werden mit ODER verknüpft. Weil das UND zuerst ausgewertet werden soll, kommt es in Klammern:
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.
Vergleiche die Schaltung mit der Tabelle: Die Leitung zwischen den beiden Gattern führt genau die Werte der Hilfsspalte .
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.
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.
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
- Zeilen 1–2: Die Funktion
alarmenthält den Term der Schaltung. Die Klammern stehen genau wie im Term.int(...)sorgt dafür, dass das Ergebnis 0 oder 1 ist. - Zeile 4: Die Kopfzeile der Tabelle.
- Zeilen 5–7: Drei Schleifen erzeugen alle acht
Belegungen in der üblichen Reihenfolge. Die innerste Schleife
(
rauch) wechselt am schnellsten. - Zeilen 8–9: Für jede Belegung wird der Ausgang berechnet und zusammen mit den Eingängen ausgegeben. Die Leerzeichen im f-String sorgen dafür, dass die Werte unter den Überschriften stehen.
Die Ausgabe stimmt Zeile für Zeile mit der Belegungstabelle überein. Die Schaltung erfüllt also die Anforderung.
Achte auf die Klammern. Der Term 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):
| 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 beschreibst du eine Schaltung in Fachsprache – vom einfachen zum genauen Satz:
- „Links gehen drei Leitungen rein, rechts eine raus.“ → „Die Schaltung hat drei Eingänge und einen Ausgang.“
- „Bei 0, 0, 1 kommt 1 raus.“ → „Zu der Kombination der Eingangswerte Tür = 0, Scharf = 0, Rauch = 1 gehört der Ausgangswert Alarm = 1.“
- „Die Formel ist die Schaltung.“ → „Der logische Term repräsentiert die Schaltung der Alarmanlage.“
2.2.3Typische Fehler beim Entwurf
- Bedeutung von 0 und 1 nicht festgelegt. Schreibe in Schritt 1 immer auf, was 1 bedeutet. Bei der Fahrstuhltür in den Übungen unten bedeutet 1 bei den Lichtschranken „frei“, nicht „blockiert“.
- Alltags-Oder mit XOR verwechseln. Prüfe beim Wort „oder“, ob „beides gleichzeitig“ erlaubt ist. Dann ist es ODER, sonst XOR.
- Klammern vergessen. Was in der Beschreibung zusammengehört, gehört im Term in eine Klammer und in der Schaltung zu einem eigenen Gatter.
- Nicht alle Fälle getestet. Eine Schaltung, die in drei Fällen funktioniert, kann im vierten falsch sein. Teste immer alle Belegungen.
2.2.4Übungen
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“.
- Stelle die Belegungstabelle auf.
- Gib einen logischen Term an und skizziere die Schaltung.
- Baue die Schaltung in CircuitVerse und teste sie.
- Kontrolliere dein Ergebnis mit Python. Ergänze dazu die Funktion
schliessenim 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:
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.
Drei Personen A, B und C stimmen ab (0 = dagegen, 1 = dafür). Ein Antrag ist angenommen (Ausgang ), wenn die Mehrheit dafür ist. Aber: Stimmt Person A dagegen, ist der Antrag in jedem Fall abgelehnt (Vetorecht).
- Überlege dir zunächst in Worten, wann der Ausgang 1 sein muss.
- Stelle die Belegungstabelle auf. Die Hilfsspalte „Mehrheit“ gibt an, ob mindestens zwei Personen dafür sind.
- Gib einen Term an, skizziere die Schaltung und baue sie in CircuitVerse.
- Vergleiche mit einer Python-Kontrolle. Schreibe dazu eine Funktion
antrag_angenommen(a, b, c).
| Mehrheit | ||||
|---|---|---|---|---|
| 0 | 0 | 0 | ||
| 0 | 0 | 1 | ||
| 0 | 1 | 0 | ||
| 0 | 1 | 1 | ||
| 1 | 0 | 0 | ||
| 1 | 0 | 1 | ||
| 1 | 1 | 0 | ||
| 1 | 1 | 1 |
Die Mehrheitsschaltung kennst du schon aus dem letzten Abschnitt: . Ü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.
| Mehrheit | |||||
|---|---|---|---|---|---|
| 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 : die Mehrheitsschaltung mit einem zusätzlichen UND-Gatter für A. Die letzte Spalte zeigt, dass der kürzere Term zu genau derselben Tabelle führt. Er braucht nur zwei Gatter:
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
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.
- Benenne die Eingänge und den Ausgang und lege fest, was 0 und 1 bedeuten.
- Stelle die Belegungstabelle auf (mit Hilfsspalten).
- Gib einen Term an und skizziere die Schaltung.
Deine Lösung:
Lösung vergleichen
- Eingänge: Trocken (1 = Boden ist trocken), Regen (1 = es regnet), Hand (1 = Handschalter ein). Ausgang: Pumpe (1 = Pumpe läuft).
- Belegungstabelle (abgekürzt: T = Trocken, R = Regen, H = Hand):
| 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 |
- „Nicht regnet“ wird zu , also brauchst du ein NICHT-Gatter. Der Term lautet .
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.
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.
Setze den Auftrag Eingänge und Ausgang benennen fort.
- Stelle die Belegungstabelle auf.
- 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: .
Übersetze jeden Satz in einen logischen Term. Nenne die Gatter, die du für die Schaltung brauchst.
- Das Tablet lädt (), wenn das Kabel steckt () und die Steckdose Strom hat ().
- Die Klingel tönt (), wenn an der Haustür () oder an der Gartentür () jemand drückt.
- Der Bildschirm des Laptops ist an (), wenn der Deckel nicht zugeklappt ist. ( bedeutet: Der Deckel ist zugeklappt.)
- Die Handykamera blitzt (), wenn es dunkel ist () und der Blitz nicht ausgeschaltet ist. ( bedeutet: Der Blitz ist ausgeschaltet.)
Deine Terme:
Lösung vergleichen
- , ein UND-Gatter.
- , ein ODER-Gatter. Drücken an beiden Türen gleichzeitig Personen, tönt die Klingel auch.
- , ein NICHT-Gatter.
- , ein NICHT-Gatter für und ein UND-Gatter.
Bei c) und d) steckt das „nicht“ in der Festlegung von 0 und 1. Lies diese Festlegung immer genau.
Das Licht auf dem Pausenhof geht an (), wenn es dunkel ist () und der Bewegungsmelder etwas meldet (), oder wenn der Hausmeister den Schalter einschaltet ().
Welcher der drei Terme beschreibt die Anlage richtig? Begründe deine Wahl.
① ② ③
Deine Antwort:
Lösung vergleichen
Richtig ist ① . „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 () schaltet der Hausmeister ein (). Laut ② bleibt es dunkel, denn das UND mit ergibt 0.
- ③ Nachts meldet der Bewegungsmelder etwas (, , ). Laut ③ bleibt das Licht aus, denn das UND mit ergibt 0.
Ein einziger Fall, in dem ein Term das Falsche liefert, genügt, um ihn auszuschließen.
Am Eingang eines Kinosaals öffnet sich eine Schranke (), wenn ein gültiges Ticket gescannt wurde () und außerdem die Person mindestens 16 Jahre alt ist () oder von einer erwachsenen Person begleitet wird ().
- Stelle die Belegungstabelle auf. Die Hilfsspalte gibt an, ob die Altersregel erfüllt ist.
- Gib einen logischen Term an.
- Skizziere die Schaltung mit IEC-Symbolen.
| 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
| 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 . Die Klammer ist nötig, weil „16 oder begleitet“ zusammengehört.
Typischer Fehler: . Dann würde die Schranke auch ohne Ticket öffnen, sobald eine erwachsene Begleitung dabei ist (Zeile 0 0 1).
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.
Ein Wasserspiel im Freizeitpark spritzt (), wenn Musik läuft () oder ein Kind auf die Bodenplatte tritt (). Bei Sturm () bleibt es aber in jedem Fall aus.
- Stelle die Belegungstabelle auf (mit Hilfsspalten).
- Gib einen Term an und skizziere die Schaltung.
- Jonas schlägt den Term 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
| 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 . Das ist dasselbe Muster wie beim Vetorecht: Ein Eingang kann alles verhindern.
Jonas’ Term liefert zum Beispiel bei , , eine 1: Das Wasserspiel würde bei Sturm spritzen. Auch bei , , 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
- Beim Schaltungsentwurf geht man in festen Schritten vor: Eingänge und Ausgänge benennen, Belegungstabelle aufstellen, Term und Schaltung entwickeln, Schaltung testen.
- Für jeden Eingang und Ausgang legt man fest, was 0 und 1 bedeuten.
- Die Wörter „und“, „oder“, „nicht“ einer Beschreibung führen oft zu den Gattern UND, ODER, NICHT. Klammern im Term zeigen, was zuerst berechnet wird.
- Das Beispiel Alarmanlage: .
- Verschiedene Schaltungen können dieselbe Belegungstabelle haben. Dann erfüllen beide die Anforderung; die mit weniger Gattern ist billiger.
- Getestet wird mit allen Belegungen, zum Beispiel in CircuitVerse oder mit einem Python-Programm mit geschachtelten Schleifen.
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.
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.
Nach diesem Abschnitt kannst du
- natürliche Zahlen vom Dezimalsystem ins Binärsystem umrechnen und umgekehrt,
- zwei natürliche Zahlen im Binärsystem schriftlich addieren und dabei die Überträge richtig berücksichtigen,
- den Aufbau des Halbaddierers aus einem XOR- und einem UND-Gatter skizzieren,
- die Funktionsweise des Halbaddierers mit seiner Belegungstabelle erläutern,
- einen Halbaddierer in CircuitVerse bauen und als Python-Funktion nachbilden.
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: . 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.
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 . Damit man die Zahlensysteme nicht verwechselt, schreibt man manchmal das System klein dahinter: .
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.
- 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 .
- Passt 8 in 6? Nein. Schreibe unter 8 eine 0.
- Passt 4 in 6? Ja. Schreibe unter 4 eine 1. Es bleiben .
- Passt 2 in 2? Ja. Schreibe unter 2 eine 1. Es bleibt 0.
- 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 . Zur Probe rechnest du zurück: .
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.
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.
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 , 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 .
Python kann Zahlen zwischen Dezimal- und Binärsystem umrechnen. Diese beiden Befehle brauchst du nur zum Nachprüfen:
int("1101", 2)wandelt die Zeichenkette"1101"in eine Zahl um. Die2sagt Python, dass die Ziffern im Binärsystem gemeint sind. Ergebnis:13.bin(13)liefert die Binärschreibweise von 13 als Zeichenkette:'0b1101'. Die Vorsilbe0bzeigt nur an, dass eine Binärzahl folgt.
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: . Du schreibst 5 und überträgst 1. Links: . 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 | 0 | 0 | |
| 1 | 1 | 0 | |
| 1 | 1 | 0 | |
| 10 | 0 | 1 |
Kommt ein Übertrag aus der Stelle davor dazu, können auch drei Einsen zusammenkommen: , binär 11. Dann schreibst du 1 und überträgst 1.
- Die binäre Addition funktioniert wie die schriftliche Addition im Dezimalsystem, nur mit den Ziffern 0 und 1: , , , (also 0 schreiben, 1 Übertrag).
- Mit einem Übertrag aus der Stelle davor gilt außerdem (also 1 schreiben, 1 Übertrag).
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) | 0 | 1 | |
| 2 | 0 | 1 | |
| 3 | 0 | 1 | |
| 4 | 1 | 0 |
Ergebnis: 1000. Probe: und . ✓
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.
Typische Fehler bei der Binäraddition:
- „1 + 1 = 2“ hinschreiben. Die Ziffer 2 gibt es im Binärsystem nicht. Richtig: 0 schreiben, 1 übertragen.
- Übertrag vergessen. Schreibe jeden Übertrag sofort in die Ü-Zeile, und zwar unter die nächste Stelle links.
- Stellen verrutscht. Ergänze kürzere Zahlen vorn mit Nullen, damit die Stellen genau untereinanderstehen.
- Letzten Übertrag vergessen. Entsteht ganz links noch ein Übertrag, wird das Ergebnis eine Stelle länger: .
Mache immer die Probe im Dezimalsystem.
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).
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)
- Nur in der dritten Stelle von rechts entsteht ein Übertrag (). Ergebnis: 1011.
- In jeder Stelle entsteht ein Übertrag. In der zweiten Stelle von rechts addierst du drei Einsen: , also 1 schreiben und 1 übertragen. Ergebnis: 10010.
- 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 und . Das Ergebnis besteht aus zwei Bits: der Ziffer, die man hinschreibt, und dem Übertrag. Man nennt sie Summe und Übertrag (vom englischen carry, „tragen“).
| (dezimal) | Übertrag | Summe | ||
|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 |
| 0 | 1 | 1 | 0 | 1 |
| 1 | 0 | 1 | 0 | 1 |
| 1 | 1 | 2 | 1 | 0 |
Liest man und 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?
- Die Spalte ist 1, wenn und unterschiedlich sind. Das ist die Belegungstabelle des XOR-Gatters.
- Die Spalte ist nur 1, wenn und beide 1 sind. Das ist die Belegungstabelle des UND-Gatters.
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
So ist der Halbaddierer aufgebaut:
- Die beiden Eingänge und werden beiden Gattern zugeführt. Deshalb verzweigen sich die Leitungen. Die Punkte markieren die Verzweigungen. Wo sich die Leitung von und die Leitung von nur kreuzen, ist kein Punkt.
- Das XOR-Gatter berechnet die Summe: .
- Das UND-Gatter berechnet den Übertrag: .
Die Belegungstabelle des Halbaddierers fasst das zusammen:
| 0 | 0 | 0 | 0 |
| 0 | 1 | 1 | 0 |
| 1 | 0 | 1 | 0 |
| 1 | 1 | 0 | 1 |
Funktionsweise an einem Beispiel: Liegt an und an je eine 1 an, dann sind die Eingänge gleich. Das XOR-Gatter liefert also . Das UND-Gatter liefert , weil beide Eingänge 1 sind. Zusammen ergibt das die Binärzahl 10, also 2. Das ist richtig, denn .
Ein Halbaddierer ist eine Schaltung mit zwei Eingängen , und zwei Ausgängen. Er addiert die beiden Bits und liefert die Summe (XOR-Gatter) und den Übertrag (UND-Gatter).
Warum heißt er „halb“? Schau noch einmal auf das Beispiel . 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.
- Ein Halbaddierer addiert zwei einzelne
Bits
(,
)
und liefert zwei Ausgänge:
- Summe (XOR),
- Übertrag (UND; englisch carry).
- „Halb“-Addierer heißt er, weil er keinen eingehenden Übertrag aus einer vorherigen Stelle berücksichtigen kann. Das kann erst der Volladdierer.
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.
So beschreibst du den Halbaddierer in Fachsprache – vom einfachen zum genauen Satz:
- „Da gehen zwei Leitungen rein und zwei raus.“ → „Ein Halbaddierer hat zwei Eingänge und zwei Ausgänge.“
- „Der rechnet A plus B.“ → „Ein Halbaddierer addiert zwei Bits und liefert die Summe und den Übertrag.“
- „Bei 1 und 1 kommt 0 und 1 raus.“ → „Ein Halbaddierer addiert die an den beiden Eingängen anliegenden Bits und liefert deren Summe und den entstehenden Übertrag. Liegen zwei Einsen an, ist die Summe 0 und der Übertrag 1.“
- Lege zwei Input-Schalter und an.
- Füge ein XOR-Gatter hinzu (Eingänge: , ). Sein Ausgang ist die Summe .
- Füge ein AND-Gatter hinzu (Eingänge: , ). Sein Ausgang ist der Übertrag .
- Verbinde beide Gatterausgänge mit je einem Output.
- Teste alle vier Belegungen, trage die Werte ein und vergleiche mit der Belegungstabelle oben.
| 0 | 0 | ||
| 0 | 1 | ||
| 1 | 0 | ||
| 1 | 1 |
Lösung vergleichen
| 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 eine Leitung zum XOR-Gatter und eine zweite zum AND-Gatter, ebenso von . Speichere die Schaltung: Du brauchst sie im nächsten Abschnitt für den Volladdierer.
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.
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
ergibt binär 10.
2.3.5Übungen
- Erläutere den Aufbau und die Funktionsweise eines Halbaddierers. Gehe dabei auf die Belegung , ein.
- Begründe am Beispiel , warum ein Halbaddierer für die zweite Stelle von rechts nicht ausreicht.
Deine Antwort:
Lösung vergleichen
- Ein Halbaddierer hat zwei Eingänge und und zwei Ausgänge, die Summe und den Übertrag . Beide Eingänge sind mit einem XOR-Gatter und mit einem UND-Gatter verbunden. Das XOR-Gatter liefert die Summe , das UND-Gatter den Übertrag . Bei , sind die Eingänge unterschiedlich, also liefert das XOR-Gatter . Das UND-Gatter liefert , weil nicht beide Eingänge 1 sind. Zusammen ergibt das 01, also .
- In der Stelle ganz rechts entsteht der Übertrag 1 (). In der zweiten Stelle müssen deshalb drei Bits addiert werden: . Der Halbaddierer hat aber nur zwei Eingänge und kann den eingehenden Übertrag nicht berücksichtigen.
An einem Halbaddierer liegt und an. Gib ohne Tabelle an, welche Werte und haben, und begründe mit den beiden Gattern. Welche Belegung führt zu ?
Deine Antwort:
Lösung vergleichen
, denn die Eingänge sind unterschiedlich, und das XOR-Gatter liefert dann eine 1. , denn das UND-Gatter liefert nur eine 1, wenn beide Eingänge 1 sind. Nur die Belegung , führt zu .
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.
Bestimme für jede Rechnung, welche Ziffer man hinschreibt und welcher Übertrag entsteht.
| Rechnung | Ergebnis (binär) | schreibe | Übertrag |
|---|---|---|---|
Lösung vergleichen
| Rechnung | Ergebnis (binär) | schreibe | Übertrag |
|---|---|---|---|
| 1 | 1 | 0 | |
| 10 | 0 | 1 | |
| 1 | 1 | 0 | |
| 10 | 0 | 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.
Berechne von Hand. Die Dezimalwerte stehen zur Kontrolle in Klammern.
- (4 + 3)
- (10 + 5)
- (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 . In keiner Spalte stehen zwei Einsen untereinander, also gibt es keinen Übertrag. Man kann die Ziffern einfach Spalte für Spalte hinschreiben.
Berechne von Hand. Schreibe den Übertrag in die Ü-Zeile.
- (2 + 2)
- (5 + 1)
- (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.
Ergänze die Lücken (1) bis (7).
Ein Halbaddierer hat (1) Eingänge und (2) Ausgänge. Die Summe liefert ein (3)-Gatter, den Übertrag ein (4)-Gatter. Liegt an beiden Eingängen eine 1 an, ist (5) und (6). „Halb“ heißt er, weil er keinen (7) aus der Stelle davor verarbeiten kann.
Deine Lösungen:
Lösung vergleichen
- zwei, (2) zwei, (3) XOR, (4) UND, (5) 0, (6) 1, (7) Übertrag (eingehenden Übertrag).
Zu (5) und (6): im Binärsystem. Die 0 ist die Summe, die 1 ist der Übertrag.
Berechne von Hand Schritt für Schritt. Schreibe alle Überträge in die Ü-Zeile. Prüfe dein Ergebnis anschließend mit Python.
- (7 + 3)
- (6 + 6)
- (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)
- In der zweiten Stelle von rechts kommen drei Einsen zusammen: , also 1 schreiben, 1 übertragen.
- Der letzte Übertrag macht das Ergebnis fünfstellig. Vergiss ihn nicht.
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
- Beschreibe jeweils den Fehler.
- Rechne beide Aufgaben richtig.
- Tim hat in jeder Spalte dasselbe Gatter „nachgespielt“. Welches Gatter ist das?
Deine Antwort und die richtigen Rechnungen:
Lösung vergleichen
- Lena hat geschrieben. Die Ziffer 2 gibt es im Binärsystem nicht. Tim hat alle Überträge vergessen. Er hat bei nur die 0 hingeschrieben.
- 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)
- 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 des Halbaddierers. Was ihm fehlt, ist der Übertrag und dessen Weitergabe an die nächste Stelle.
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
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.
In jeder Rechnung ist eine Ziffer durch x ersetzt. Bestimme x und begründe, Spalte für Spalte von rechts.
Deine Begründung:
Lösung vergleichen
- x = 1. Rechts: ✓, dann ✓. In der dritten Stelle von rechts steht im Ergebnis eine 0. Aus wird nur dann 0, wenn ist: , also 0 schreiben, 1 übertragen. Links: , 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)
- x = 1. Rechts: , also 0 schreiben ✓ und 1 übertragen. Zweite Stelle: muss eine 0 ergeben. Das geht nur mit : , also 0 schreiben ✓, 1 übertragen. Dritte Stelle: , also 1 schreiben ✓, 1 übertragen. Links: ✓.
0 1 1 1 (= 7)
+ 0 1 0 1 (= 5)
Ü 1 1 1
---------
1 1 0 0 (= 12)
Mit ginge es jeweils nicht: In a) erhielte man 1111, in b) 1010.
2.3.7Das Wichtigste in Kürze
- Im Binärsystem gibt es nur die Ziffern 0 und 1. Die Stellenwerte sind 1, 2, 4, 8, 16, … Beispiel: .
- Binärzahlen werden schriftlich addiert wie Dezimalzahlen: Stelle für Stelle von rechts nach links. Es gilt (0 schreiben, 1 übertragen) und .
- Die Überträge schreibt man in eine eigene Zeile. Die Probe im Dezimalsystem deckt Fehler auf.
- Ein Halbaddierer addiert zwei Bits: Summe (XOR-Gatter), Übertrag (UND-Gatter).
- Er heißt „halb“, weil er keinen Übertrag aus der Stelle davor verarbeiten kann.
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.
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.
Nach diesem Abschnitt kannst du
- erklären, warum beim Addieren mehrstelliger Binärzahlen in jeder Stelle drei Bits addiert werden,
- den Aufbau eines Volladdierers aus zwei Halbaddierern und einem ODER-Gatter skizzieren und seine Funktionsweise erläutern,
- die Belegungstabelle des Volladdierers angeben,
- einen Carry-Ripple-Addierer skizzieren und erläutern, wie der Übertrag von Stelle zu Stelle wandert,
- eine Addition Stufe für Stufe durch einen Carry-Ripple-Addierer verfolgen.
2.4.1Drei Bits addieren
Erinnere dich an die Rechnung 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 : 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:
- und : die beiden Bits, die an dieser Stelle addiert werden,
- : den eingehenden Übertrag aus der Stelle rechts davon.
Die Summe von drei Bits ist höchstens , binär 11. Das Ergebnis passt also wieder in zwei Bits: die Summe , die an dieser Stelle hingeschrieben wird, und den ausgehenden Übertrag , der an die nächste Stelle links weitergegeben wird. Im Englischen heißen die Überträge carry in und carry out, kurz und .
| Einsen | |||||
|---|---|---|---|---|---|
| 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 und zusammen als Binärzahl, steht dort genau diese Anzahl: 00, 01, 10 oder 11. Zwei Beobachtungen helfen beim Merken:
- ist 1, wenn die Anzahl der Einsen ungerade ist (1 oder 3).
- ist 1, wenn mindestens zwei Eingänge 1 sind. Das ist genau die Mehrheitsschaltung, die du schon kennst.
Ein Volladdierer ist eine Schaltung mit drei Eingängen und zwei Ausgängen. Er addiert die beiden Bits und und den eingehenden Übertrag und liefert die Summe und den ausgehenden Übertrag .
So beschreibst du den Volladdierer in Fachsprache – vom einfachen zum genauen Satz:
- „Es gehen links drei Leitungen hinein und rechts zwei hinaus.“ → „Ein Volladdierer hat drei Eingänge und zwei Ausgänge.“
- „Der rechnet drei Bits zusammen.“ → „Ein Volladdierer addiert drei Bits und liefert die Summe und den Übertrag.“
- „Da kommt die Summe und der Übertrag raus.“ → „Ein Volladdierer addiert die an den drei Eingängen anliegenden Bits und liefert deren Summe und den entstehenden Übertrag.“
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:
- Halbaddierer 1 addiert und . Er liefert eine Zwischensumme und einen Übertrag .
- Halbaddierer 2 addiert die Zwischensumme und den eingehenden Übertrag . Er liefert die endgültige Summe und einen zweiten Übertrag .
- Ist bei einem der beiden Schritte ein Übertrag entstanden, gibt es einen ausgehenden Übertrag. Ein ODER-Gatter verknüpft deshalb und : .
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:
Die Belegungstabelle mit den Zwischenergebnissen als Hilfsspalten zeigt, dass der Aufbau stimmt. Die beiden letzten Spalten sind genau die Spalten und aus der Tabelle oben.
| 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 , , , und .
Funktionsweise an einem Beispiel (letzte Zeile): An allen drei Eingängen liegt eine 1 an. Halbaddierer 1 rechnet , also und . Halbaddierer 2 rechnet , also und . Das ODER-Gatter liefert . Zusammen ergibt das 11, also 3. Das stimmt: .
Warum genügt am Ende ein ODER-Gatter? Könnten nicht beide Halbaddierer gleichzeitig einen Übertrag liefern? Nein: heißt, dass und beide 1 sind. Dann ist aber , und der zweite Halbaddierer addiert höchstens . Er liefert also keinen Übertrag. In der Tabelle sind und nie gleichzeitig 1.
- Ein Volladdierer addiert drei Bits: die beiden zu addierenden Bits und sowie einen eingehenden Übertrag aus der vorherigen Stelle. Er liefert die Summe und einen ausgehenden Übertrag .
- Ein Volladdierer lässt sich aus zwei Halbaddierern und einem
ODER-Gatter aufbauen:
- Halbaddierer 1: und ergeben die Zwischensumme und den Übertrag .
- Halbaddierer 2: und ergeben die Summe und den Übertrag .
- .
- Baue zwei Halbaddierer wie im letzten Abschnitt (je ein XOR- und ein AND-Gatter).
- Verbinde den Summenausgang des ersten Halbaddierers mit einem Eingang des zweiten Halbaddierers. Der zweite Eingang ist .
- Verknüpfe die beiden Übertragsausgänge und mit einem OR-Gatter. Dessen Ausgang ist .
- Teste alle acht möglichen Belegungen von , und , trage die Werte ein und vergleiche mit der Belegungstabelle oben.
| 0 | 0 | 0 | ||
| 0 | 0 | 1 | ||
| 0 | 1 | 0 | ||
| 0 | 1 | 1 | ||
| 1 | 0 | 0 | ||
| 1 | 0 | 1 | ||
| 1 | 1 | 0 | ||
| 1 | 1 | 1 |
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
| 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 : Sie muss zu beiden Gattern des zweiten Halbaddierers führen, und 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]
- Zeilen 2–3: der erste Halbaddierer (XOR für die Summe, UND für den Übertrag).
- Zeilen 4–5: der zweite Halbaddierer. Er bekommt die
Zwischensumme
s1und den eingehenden Übertragc_ein. - Zeile 6: das ODER-Gatter für den ausgehenden Übertrag.
- Zeilen 9–13: Drei geschachtelte Schleifen gehen
alle acht Belegungen durch. Ausgegeben wird die Liste
[S, Caus]: vorn die Summe, hinten der ausgehende Übertrag.
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: ist das Bit ganz rechts von , das Bit ganz links. Der Volladdierer VA ist für die Stelle 0 zuständig, VA 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 . Der Übertrag , der ganz links herauskommt, ist die fünfte Stelle des Ergebnisses.
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 rechnen. Es ist und . Die Stufen arbeiten von rechts nach links. (Achtung: bezeichnet hier das Summenbit der Stelle 1, nicht die Zwischensumme im Inneren eines Volladdierers.)
| Stufe | Übertrag ein | Summe | Übertrag aus | ||
|---|---|---|---|---|---|
| VA | 1 | 1 | |||
| VA | 0 | 1 | |||
| VA | 1 | 0 | |||
| VA | 0 | 0 |
Das Ergebnis liest man von links nach rechts ab: , also 8. Die Rechnung stimmt: .
Achte auf die Spalte „Übertrag ein“: Jede Stufe braucht den Übertrag der Stufe rechts davon. VA kann sein endgültiges Ergebnis erst liefern, wenn VA fertig ist; VA muss auf VA 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.
Ein Carry-Ripple-Addierer verkettet mehrere Volladdierer: Der ausgehende Übertrag einer Stelle wird zum eingehenden Übertrag der nächsthöheren Stelle. So werden mehrstellige Binärzahlen addiert. Der Übertrag „rieselt“ (englisch ripple) von Stelle zu Stelle durch.
So erläuterst du den Carry-Ripple-Addierer:
- „Da sind vier Volladdierer nebeneinander.“ → „Ein 4-Bit-Carry-Ripple-Addierer besteht aus vier hintereinandergeschalteten Volladdierern, einer für jede Stelle.“
- „Der Übertrag geht weiter.“ → „Der ausgehende Übertrag jedes Volladdierers liegt am Übertragseingang des Volladdierers der nächsthöheren Stelle an.“
Skizziere das Blockschaltbild eines 4-Bit-Carry-Ripple-Addierers: vier Volladdierer-Blöcke nebeneinander mit den Eingängen bis und bis , den Summenausgängen bis 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
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 () ist die fünfte Stelle des Ergebnisses. Statt VA darf man auch einen Halbaddierer verwenden, weil dort kein Übertrag ankommt.
Verfolge die Addition 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 | Übertrag ein | Summe | Übertrag aus | ||
|---|---|---|---|---|---|
| VA | |||||
| VA | |||||
| VA | |||||
| VA |
Ergebnis und Probe:
Lösung vergleichen
Es ist und .
| Stufe | Übertrag ein | Summe | Übertrag aus | ||
|---|---|---|---|---|---|
| VA | 1 | 0 | |||
| VA | 1 | 1 | |||
| VA | 0 | 1 | |||
| VA | 1 | 0 |
Ergebnis: , also 17. Probe: , , . ✓
Häufiger Fehler: mit der Stufe VA beim linken Bit anfangen. Die Stufe 0 gehört immer zum Bit ganz rechts.
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
.
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
cist der Übertrag, der von Stufe zu Stufe weitergegeben wird. Am Anfang ist er 0. - Zeile 12:
iläuft rückwärts: 3, 2, 1, 0. So wird die Stelle ganz rechts zuerst bearbeitet.len(a_bits) - 1statt 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
iund den Übertragc. - 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
bis
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
VA.
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
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 ():
| Ergebnis | dezimal | ||
|---|---|---|---|
| 01 | 01 | 010 | |
| 10 | 01 | 011 | |
| 11 | 01 | 100 | |
| 11 | 11 | 110 |
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.
Bestimme für jede Belegung die Summe und den ausgehenden Übertrag . Addiere dazu die drei Bits wie bei der schriftlichen Addition.
| 1 | 0 | 0 | ||
| 0 | 1 | 1 | ||
| 1 | 1 | 0 | ||
| 0 | 0 | 1 | ||
| 1 | 1 | 1 |
Lösung vergleichen
| Rechnung | |||||
|---|---|---|---|---|---|
| 1 | 0 | 0 | 1 | 0 | |
| 0 | 1 | 1 | 0 | 1 | |
| 1 | 1 | 0 | 0 | 1 | |
| 0 | 0 | 1 | 1 | 0 | |
| 1 | 1 | 1 | 1 | 1 |
Das Ergebnis der Rechnung ist eine zweistellige Binärzahl : Die rechte Ziffer ist die Summe, die linke der Übertrag. Der eingehende Übertrag zählt genauso mit wie und .
Entscheide, ob die Aussage richtig oder falsch ist. Verbessere die falschen Aussagen.
- Ein Volladdierer hat drei Eingänge und zwei Ausgänge.
- Ein Volladdierer besteht aus zwei Halbaddierern und einem UND-Gatter.
- Beim Carry-Ripple-Addierer wird der ausgehende Übertrag einer Stelle zum eingehenden Übertrag der nächsthöheren Stelle.
- In der Stelle ganz rechts ist der eingehende Übertrag immer 1.
- Die Summe zweier vierstelliger Binärzahlen kann fünf Stellen haben.
Deine Antwort:
Lösung vergleichen
- Richtig: die Eingänge , , und die Ausgänge , .
- Falsch: Die beiden Überträge werden mit einem ODER-Gatter verknüpft: .
- Richtig: So entsteht die Kette, durch die der Übertrag „rieselt“.
- Falsch: Ganz rechts kommt kein Übertrag an. Der eingehende Übertrag ist dort immer 0.
- Richtig: zum Beispiel . Die fünfte Stelle ist der letzte Übertrag.
An einem Volladdierer liegt , und an. Bestimme alle Zwischenwerte. Die Abbildung des Volladdierers aus zwei Halbaddierern weiter vorn in diesem Abschnitt hilft dir.
| Wert | so wird er berechnet | Ergebnis |
|---|---|---|
| (Halbaddierer 1) | ||
| (Halbaddierer 1) | ||
| (Halbaddierer 2) | ||
| (Halbaddierer 2) | ||
| (ODER-Gatter) |
Lösung vergleichen
| Wert | so wird er berechnet | Ergebnis |
|---|---|---|
| 1 | ||
| 0 | ||
| 0 | ||
| 1 | ||
| 1 |
Probe: , also und . ✓ Hier entsteht der Übertrag im zweiten Halbaddierer.
Ein Carry-Ripple-Addierer soll zwei achtstellige Binärzahlen addieren. Alle Stellen werden mit Volladdierern gebaut.
- Wie viele Volladdierer braucht man?
- Wie viele Stellen kann das Ergebnis höchstens haben?
- 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
- Für jede Stelle einen, also 8 Volladdierer.
- 9 Stellen: acht Summenbits und der Übertrag ganz links.
- Jeder Halbaddierer hat ein XOR- und ein UND-Gatter. Ein Volladdierer hat also Gatter. Der ganze Addierer hat Gatter.
Verfolge die Addition durch alle Stufen eines 4-Bit-Carry-Ripple-Addierers. Fülle die Tabelle aus und lies das Ergebnis ab. Zur Probe: .
| Stufe | Übertrag ein | Summe | Übertrag aus | ||
|---|---|---|---|---|---|
| VA | |||||
| VA | |||||
| VA | |||||
| VA |
Ergebnis:
Lösung vergleichen
Es ist und .
| Stufe | Übertrag ein | Summe | Übertrag aus | ||
|---|---|---|---|---|---|
| VA | 0 | 1 | |||
| VA | 1 | 1 | |||
| VA | 1 | 1 | |||
| VA | 0 | 0 |
Ergebnis: , also 1101. Das ist 13. ✓ In der Stufe VA werden drei Einsen addiert: .
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
Das Ergebnis lautet , 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.
Nimm die Funktionen volladdierer und
carry_ripple_addierer aus der Lösung zum Auftrag
4-Bit-Carry-Ripple-Addierer in Python.
- Teste sie mit zwei achtstelligen Binärzahlen: (also ) und (also ).
- 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]
- 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 ✓.
- Die Schleife läuft von
len(a_bits) - 1bis 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.
- Bestimme für jede Addition die Überträge bis zwischen den Stufen und das Ergebnis.
| Rechnung | Ergebnis | ||||
|---|---|---|---|---|---|
- Gib eine Addition zweier vierstelliger Binärzahlen an, bei der alle vier Überträge bis gleich 1 sind.
- 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
- Die Überträge, von rechts nach links:
| Rechnung | Ergebnis | ||||
|---|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0111 | |
| 1 | 1 | 1 | 0 | 1000 | |
| 0 | 1 | 1 | 1 | 10000 |
- Zum Beispiel : Ganz rechts ist , und in jeder weiteren Stelle ist . Jede Stufe erzeugt also einen Übertrag. Auch ist eine richtige Antwort.
- Jede Stufe kann ihr Ergebnis erst liefern, wenn der Übertrag der Stufe rechts davon da ist. Bei hängt jede Stufe von der vorigen ab: Der Übertrag muss von VA bis ganz nach links durch alle vier Stufen „rieseln“. Bei entsteht dagegen nirgends ein Übertrag, der von Stufe zu Stufe weitergereicht werden muss.
2.4.5Das Wichtigste in Kürze
- Beim Addieren mehrstelliger Binärzahlen werden ab der zweiten Stelle drei Bits addiert: , und der eingehende Übertrag.
- Ein Volladdierer hat drei Eingänge (, , ) und zwei Ausgänge (Summe , Übertrag ).
- Aufbau: zwei Halbaddierer und ein ODER-Gatter. Halbaddierer 1 addiert und , Halbaddierer 2 addiert die Zwischensumme und , das ODER-Gatter verknüpft die beiden Überträge.
- Die Belegungstabelle des Volladdierers hat 8 Zeilen. ist 1 bei einer ungeraden Anzahl von Einsen, ist 1, wenn mindestens zwei Eingänge 1 sind.
- Ein Carry-Ripple-Addierer verkettet Volladdierer: Der ausgehende Übertrag jeder Stelle ist der eingehende Übertrag der nächsthöheren Stelle. Ganz rechts ist .
- Der Übertrag wandert Stufe für Stufe von rechts nach links. Bei vielen Stellen dauert die Addition deshalb länger.
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.
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.
Nach diesem Abschnitt kannst du
- erklären, worin sich eine Schaltung ohne Gedächtnis von einer speichernden Schaltung unterscheidet,
- das Prinzip der Rückkopplung erläutern,
- ein SR-Flipflop aus zwei NOR-Gattern skizzieren,
- die Zustände Setzen, Rücksetzen, Speichern und den verbotenen Zustand beschreiben,
- Schritt für Schritt nachvollziehen, wie die Rückkopplung einen Wert festhält,
- ein SR-Flipflop in CircuitVerse bauen und testen.
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
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.
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.
- Bisherige Schaltungen (Addierer usw.) sind kombinatorisch: Der Ausgang hängt nur vom aktuellen Eingang ab.
- Ein Flipflop kann sich dagegen ein Bit merken: Der Ausgang hängt auch von der Vorgeschichte ab. Flipflops sind die Grundlage für Speicher im Computer, zum Beispiel für die Register im Prozessor.
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 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.
| NOR: | |||
|---|---|---|---|
| 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:
- Liegt an einem Eingang eine 1, ist der Ausgang sicher 0 – egal, was am anderen Eingang anliegt.
- Nur wenn beide Eingänge 0 sind, ist der Ausgang 1. Dann gibt das Gatter sozusagen die Umkehrung des anderen Eingangs weiter.
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 auf den zweiten Eingang zurückgeführt wird:
Wir nehmen an, dass am Anfang und ist. Dann passiert Folgendes:
- Solange ist, rechnet das Gatter . Der Ausgang bleibt 0.
- Jetzt wird kurz auf 1 gestellt. Das Gatter rechnet , also wird .
- Diese 1 läuft über die Rückkopplung zurück an den unteren Eingang.
- Nun wird wieder auf 0 gestellt. Das Gatter rechnet . Der Ausgang bleibt 1!
Die Schaltung hat sich gemerkt, dass 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.
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.
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.
Schau dir die Abbildung in Ruhe an und verfolge jede Leitung mit dem Finger:
- Das obere Gatter bekommt den Eingang und den Ausgang des unteren Gatters. Sein eigener Ausgang heißt .
- Das untere Gatter bekommt den Eingang und den Ausgang des oberen Gatters. Sein eigener Ausgang heißt .
- Wo eine Leitung sich verzweigt, sitzt ein Punkt. Wo sich zwei Leitungen nur kreuzen, gibt es keinen Punkt.
Die Namen kommen aus dem Englischen:
| Name | englisch | Bedeutung |
|---|---|---|
| Set (setzen) | setzt den gespeicherten Wert auf 1 | |
| Reset (zurücksetzen) | setzt den gespeicherten Wert auf 0 | |
| – | der gespeicherte Wert, also das Bit, das sich das Flipflop merkt | |
| – | gesprochen „Q quer“; im Normalfall das Gegenteil von |
In CircuitVerse und vielen Büchern schreibt man statt
auch Q'.
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 und anliegen, macht das Flipflop etwas anderes:
| 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 und . 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.
Das einfachste Beispiel ist das SR-Flipflop (Set-Reset), gebaut aus zwei über Kreuz rückgekoppelten NOR-Gattern:
- (Set) setzt den gespeicherten Wert auf 1.
- (Reset) setzt den gespeicherten Wert auf 0.
- und : Der zuletzt gespeicherte Wert bleibt erhalten. Das ist der Speicher-Effekt!
- und gleichzeitig ist ein verbotener Zustand und sollte vermieden werden.
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 und und die beiden Ausgänge mit und . Vergleiche zum Schluss mit der Abbildung.
Meine Skizze:
Lösung vergleichen
Prüfe deine Skizze an diesen Punkten:
- Es sind zwei NOR-Gatter (Symbol mit dem kleinen Kreis am Ausgang).
- geht in das Gatter, dessen Ausgang ist. geht in das Gatter, dessen Ausgang ist.
- ist auf den zweiten Eingang des Gatters mit zurückgeführt, auf den zweiten Eingang des Gatters mit .
- An den Stellen, wo sich die Ausgangsleitungen verzweigen, sitzt ein Punkt.
Ob 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: , , und . Prüfe, dass das zusammenpasst: Das obere Gatter bekommt und . Eine 1 am Eingang macht den Ausgang zu 0, also . ✓ Das untere Gatter bekommt und . Beide Eingänge sind 0, also . ✓ Die Schaltung ist stabil – nichts ändert sich. Sie speichert die 0.
Jetzt wird kurz auf 1 gestellt und danach wieder auf 0:
| Schritt | Was passiert? | ||||
|---|---|---|---|---|---|
| 0 | 0 | 0 | Ausgangslage: Das Flipflop speichert 0. | 0 | 1 |
| 1 | 1 | 0 | wird 1. Das untere Gatter hat eine 1 am Eingang, also wird . | 0 | 0 |
| 2 | 1 | 0 | Das obere Gatter bekommt jetzt und . Beide sind 0, also wird . | 1 | 0 |
| 3 | 1 | 0 | Das untere Gatter bekommt und : bleibt 0. Nichts ändert sich mehr. | 1 | 0 |
| 4 | 0 | 0 | wird wieder 0. Das untere Gatter bekommt aber noch über die Rückkopplung: bleibt 0. Also bleibt auch . | 1 | 0 |
Schritt 4 ist der entscheidende: Der Eingang ist wieder 0, trotzdem bleibt . Die 1 an 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 beschreibst du das Flipflop in Fachsprache – vom einfachen zum genauen Satz:
- „Man kann sich damit eine 0 oder 1 merken.“ → „Die Schaltung speichert eine 0 oder eine 1.“
- „Die Schaltung kann ein Bit speichern.“ → „Die Schaltung ist in der Lage, ein Bit zu speichern.“
- „Das Ding merkt sich den Wert, weil der Ausgang zurückgeht.“ → „Das Flipflop nutzt die Technik der Rückkopplung und ist so in der Lage, ein Bit zu speichern. Die Rückkopplung bewirkt, dass der Wert erhalten bleibt.“
Das Flipflop speichert jetzt die 1: , , , . Nun wird 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 | Was passiert? | ||||
|---|---|---|---|---|---|
| 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 | Was passiert? | ||||
|---|---|---|---|---|---|
| 0 | 0 | 0 | Ausgangslage: Das Flipflop speichert 1. | 1 | 0 |
| 1 | 0 | 1 | wird 1. Das obere Gatter hat eine 1 am Eingang, also wird . | 0 | 0 |
| 2 | 0 | 1 | Das untere Gatter bekommt und . Beide sind 0, also wird . | 0 | 1 |
| 3 | 0 | 1 | Das obere Gatter bekommt und : bleibt 0. Nichts ändert sich mehr. | 0 | 1 |
| 4 | 0 | 0 | wird wieder 0. Das obere Gatter bekommt aber noch : 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 () geändert hat. Am Ende speichert das Flipflop die 0, und sie bleibt erhalten, obwohl wieder 0 ist.
Der verbotene Zustand
Was passiert, wenn und gleichzeitig anliegen? Beide Gatter haben dann eine 1 am Eingang, also sind beide Ausgänge 0: und . Das widerspricht der Idee, dass das Gegenteil von ist. Findest du also in einer Tabelle und , dann liegt (oder lag gerade) an.
Schlimmer ist, was danach kommt: Werden und 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 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 und schreiben. Man kann den Speicher-Effekt aber nachbilden, wenn man den alten Wert von 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
- Zeilen 1–10: Die Funktion
sr_flipflopbekommt die Eingängesundrund den bisher gespeicherten Wertq. Sie gibt den neuen Wert von zurück. - Zeilen 2–5: Setzen liefert 1, Rücksetzen liefert 0.
- Zeilen 6–7: Speichern: Der alte Wert
qwird unverändert zurückgegeben. Das ist der Speicher-Effekt. - Zeilen 8–10: Bleibt nur noch übrig. Die Funktion gibt eine Warnung aus und liefert 0, denn im verbotenen Zustand ist .
- Zeilen 12–13: Die beiden Listen enthalten die
Testreihenfolge: Setzen, Speichern, Rücksetzen, Speichern. An derselben
Stelle
istehen jeweils die Werte von und , die zusammengehören. - Zeile 14: Am Anfang speichert das Flipflop 0.
- Zeilen 15–17: Für jeden Schritt wird der neue Wert
berechnet und in derselben Variablen
qgespeichert. Im nächsten Schritt wird er der Funktion wieder mitgegeben. Die Variableqübernimmt also die Rolle der Rückkopplung.
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.
Ändere die beiden Listen so, dass einmal und gleichzeitig vorkommt. Was gibt das Programm aus? Setze danach zweimal hintereinander , . Ändert sich beim zweiten Mal etwas?
Das Flipflop speichert am Anfang die 0. Dann liegen nacheinander diese Werte an:
| Schritt | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
|---|---|---|---|---|---|---|---|---|
| 0 | 1 | 0 | 1 | 0 | 0 | 0 | 1 | |
| 0 | 0 | 0 | 0 | 1 | 0 | 1 | 0 | |
| danach |
- Trage ein, welchen Wert nach jedem Schritt hat.
- Ü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 |
|---|---|---|---|---|---|---|---|---|
| 0 | 1 | 0 | 1 | 0 | 0 | 0 | 1 | |
| 0 | 0 | 0 | 0 | 1 | 0 | 1 | 0 | |
| 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 schon 1 ist: Es bleibt einfach bei 1. Genauso ändert das Rücksetzen in Schritt 7 nichts, weil schon 0 ist. Bei Schritt 1, 3 und 6 wird gespeichert: 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.
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:
Falls du kein NOR-Gatter findest, kannst du ein ODER-Gatter mit einem nachgeschalteten NICHT-Gatter nehmen. Das ergibt dasselbe.
So gehst du vor:
- Lege zwei Eingänge (Schalter)
und
sowie zwei Ausgänge (LEDs)
und
Q'an. - Füge zwei NOR-Gatter hinzu.
- Verschalte sie über Kreuz:
- Das erste NOR-Gatter bekommt und den Ausgang des zweiten NOR-Gatters.
- Das zweite NOR-Gatter bekommt und den Ausgang des ersten NOR-Gatters.
- Der Ausgang des ersten Gatters ist
,
der Ausgang des zweiten ist
Q'. - Teste die Speicherwirkung: Setze kurz , . Dann wird zu 1. Schalte danach wieder auf 0, also , . Beobachte: bleibt 1, obwohl kein Eingang mehr aktiv ist!
- und vertauscht: Wenn bei dir den Ausgang auf 0 setzt, hast du die Eingänge vertauscht. gehört an das Gatter, dessen Ausgang ist. (Merkhilfe: Das Gatter mit liefert . macht dieses Gatter zu 0, also setzt das auf 0 zurück.)
- Unklarer Anfang: Direkt nach dem Aufbau ist manchmal nicht klar, was gespeichert ist. Vielleicht sind sogar beide Ausgänge gleich. Setze dann einmal auf 1 und wieder auf 0. Danach ist alles eindeutig.
Führe die Testreihenfolge in deiner CircuitVerse-Schaltung durch. Trage jeweils den beobachteten Wert von ein.
| Schritt | (beobachtet) | Erklärung | ||
|---|---|---|---|---|
| 1 | 1 | 0 | Setzen | |
| 2 | 0 | 0 | Speichern ( bleibt wie zuvor) | |
| 3 | 0 | 1 | Rücksetzen | |
| 4 | 0 | 0 | Speichern ( bleibt wie zuvor) |
Lösung vergleichen
| Schritt | (beobachtet) | Erklärung | ||
|---|---|---|---|---|
| 1 | 1 | 0 | 1 | Setzen |
| 2 | 0 | 0 | 1 | Speichern ( bleibt wie zuvor) |
| 3 | 0 | 1 | 0 | Rücksetzen |
| 4 | 0 | 0 | 0 | Speichern ( bleibt wie zuvor) |
Vergleiche die Schritte 2 und 4: Beide Male liegt , an, aber 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 und 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 eines Flipflops angeschlossen. An kommt eine Taste „Quittieren“, mit der man den Alarm ausschaltet. Die Sirene hängt an .
- Öffnet der Einbrecher die Tür, liefert die Alarm-Schaltung eine 1. Das Flipflop wird gesetzt, die Sirene heult.
- Schließt er die Tür, liegt an wieder 0 an. Mit wird gespeichert: Die Sirene heult weiter.
- Erst wenn jemand die Taste drückt (), wird das Flipflop zurückgesetzt und die Sirene verstummt.
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 und 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.
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 und einen Takteingang. Nur wenn das Taktsignal es erlaubt, übernimmt es den Wert von und speichert ihn, sonst behält es seinen Wert. Weil intern und aus und gebildet werden, kann der verbotene Zustand nicht auftreten.
- JK-Flipflop: Es funktioniert wie ein SR-Flipflop ( setzt, setzt zurück). Liegt aber 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.
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.
- der Halbaddierer
- die Alarmanlage
- das SR-Flipflop
- 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.
- eine Türklingel: Sie tönt nur, solange jemand auf den Knopf drückt.
Deine Antwort:
Lösung vergleichen
- ohne Gedächtnis: Summe und Übertrag hängen nur von den Bits ab, die gerade anliegen.
- ohne Gedächtnis: Sobald die Tür wieder zu ist und kein Rauch da ist, ist der Alarm aus.
- mit Gedächtnis: Bei , behält es den zuletzt gespeicherten Wert.
- 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.
- 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.
Das SR-Flipflop speichert gerade die 1. Ergänze für jede Zeile den Namen des Zustands und den Wert von danach. Wo es keinen sinnvollen Wert gibt, schreibe einen Strich.
| Name des Zustands | danach | ||
|---|---|---|---|
| 1 | 0 | ||
| 0 | 1 | ||
| 0 | 0 | ||
| 1 | 1 |
Lösung vergleichen
| Name des Zustands | 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 .
Das Flipflop speichert am Anfang die 1. Dann liegen nacheinander diese Werte an. Trage ein, welchen Wert nach jedem Schritt hat.
| Schritt | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|
| 0 | 0 | 0 | 1 | 0 | |
| 0 | 1 | 0 | 0 | 0 | |
| danach |
Lösung vergleichen
| Schritt | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|
| 0 | 0 | 0 | 1 | 0 | |
| 0 | 1 | 0 | 0 | 0 | |
| 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.
Jetzt umgekehrt: Das Flipflop speichert am Anfang die 0. soll nach den einzelnen Schritten die Werte in der unteren Zeile haben. Bestimme passende Werte für und . Der verbotene Zustand darf nicht vorkommen.
| Schritt | 1 | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|---|
| danach | 0 | 1 | 1 | 0 | 0 | 1 |
Lösung vergleichen
Eine mögliche Lösung:
| Schritt | 1 | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|---|
| 0 | 1 | 0 | 0 | 0 | 1 | |
| 0 | 0 | 0 | 1 | 0 | 0 | |
| danach | 0 | 1 | 1 | 0 | 0 | 1 |
Wo gleich bleibt (Schritte 1, 3 und 5), passt Speichern: , . Wo auf 1 wechselt, muss gesetzt werden, wo auf 0 wechselt, muss zurückgesetzt werden. Es gibt auch andere richtige Lösungen: In Schritt 3 darf man zum Beispiel noch einmal setzen (, ), in den Schritten 1 und 5 zurücksetzen (, ). Das ändert nichts, weil den Wert schon hat.
Die Haltewunsch-Lampe im Bus verhält sich wie ein SR-Flipflop: Die Stopp-Taste ist , das Öffnen der Türen ist , die Lampe ist . 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 |
- Sage voraus, ob die Lampe nach jedem Schritt leuchtet.
- Prüfe deine Vorhersage mit Python. Verwende die Funktion
sr_flipflopaus dem Abschnitt Das Flipflop in Python nachbilden und zwei Listentasteundtuer. Gib in jedem Schritt eine Zeile wieSchritt 2: Taste=1 Tür=0 -> Lampe=1aus.
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.
Ein Baustein mit den Eingängen und und dem Ausgang wurde getestet. Das ist das Protokoll:
| Schritt | 1 | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|---|
| 1 | 0 | 0 | 0 | 1 | 0 | |
| 0 | 0 | 1 | 0 | 0 | 0 | |
| 1 | 1 | 0 | 0 | 1 | 1 |
- Begründe mit dem Protokoll, dass der Baustein keine kombinatorische Schaltung sein kann.
- Prüfe, ob sich der Baustein wie ein SR-Flipflop verhält, wenn der Eingang und der Eingang ist.
- In Schritt 7 liegt , an, in Schritt 8 , . Sage für beide Schritte voraus.
Deine Antwort:
Lösung vergleichen
- In Schritt 2 und in Schritt 4 liegen dieselben Eingangswerte an (, ). Trotzdem ist einmal 1 und einmal 0. Bei einer kombinatorischen Schaltung gehört zu denselben Eingangswerten immer derselbe Ausgangswert. Der Baustein muss sich also etwas merken.
- Ja. Schritt 1 und 5: setzt auf 1. Schritt 3: setzt auf 0. Schritte 2, 4 und 6: Bei , behält jeweils den Wert aus dem Schritt davor. Das ist genau das Verhalten eines SR-Flipflops.
- Schritt 7 setzt zurück: . Schritt 8 speichert: 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
- Kombinatorische Schaltungen (z. B. Addierer, Alarmanlage) haben kein Gedächtnis: Der Ausgang hängt nur von den aktuellen Eingängen ab.
- Bei der Rückkopplung wird ein Ausgang auf einen Eingang derselben Schaltung zurückgeführt. Dadurch kann eine Schaltung einen Wert festhalten.
- Ein Flipflop speichert ein Bit; sein Ausgang hängt auch von der Vorgeschichte ab. Das SR-Flipflop besteht aus zwei über Kreuz rückgekoppelten NOR-Gattern.
- setzt auf 1, setzt auf 0, bei wird gespeichert. ist verboten.
- Flipflops sind die Grundlage von Speichern wie den Registern im Prozessor.
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.
Eine Schaltung zu zeichnen dauert lange, und bei großen Schaltungen verliert man schnell den Überblick. Viel kürzer ist eine Formel wie . 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.
Nach diesem Abschnitt kannst du
- die Begriffe Konjunktion, Disjunktion und Negation sachgemäß verwenden und ihre Belegungstabellen angeben,
- den Begriff des aussagenlogischen Terms induktiv definieren,
- entscheiden, ob eine Zeichenfolge ein Term ist, und die Klammerregeln anwenden,
- aussagenlogische Terme als Termbäume darstellen,
- logische Schaltungen durch Terme beschreiben und Terme in Schaltungen übertragen.
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 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.
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: , , …
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:
- Die Negation (gesprochen „nicht “) dreht den Wert um. Sie entspricht dem NICHT-Gatter.
- Die Konjunktion (gesprochen „ und “) ist nur dann 1, wenn beide Teile 1 sind. Sie entspricht dem UND-Gatter.
- Die Disjunktion (gesprochen „ oder “) ist 1, wenn mindestens einer der Teile 1 ist. Sie entspricht dem ODER-Gatter.
| 0 | 0 | 1 | 0 | 0 |
| 0 | 1 | 1 | 0 | 1 |
| 1 | 0 | 0 | 0 | 1 |
| 1 | 1 | 0 | 1 | 1 |
- Die Negation ist genau dann 1, wenn den Wert 0 hat.
- Die Konjunktion ist genau dann 1, wenn und beide den Wert 1 haben.
- Die Disjunktion ist genau dann 1, wenn mindestens eine der beiden Variablen den Wert 1 hat.
Eine Merkhilfe für die Zeichen: sieht aus wie ein „v“ – das lateinische Wort vel heißt „oder“. Das andere Zeichen ist dann das „und“. Für das Zeichen 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 | nicht | NICHT (NOT) | not a |
|
| Konjunktion | und | UND (AND) | a and b |
|
| Disjunktion | oder | ODER (OR) | a or b |
Entsprechung zu Schaltungen: (Konjunktion) entspricht dem UND-Gatter, (Disjunktion) dem ODER-Gatter, (Negation) dem NICHT-Gatter.
Das „oder“ der Aussagenlogik ist kein „entweder … oder“. 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 für XOR gehört aber nicht zu den Zeichen der Aussagenlogik, die du gleich kennenlernst. Dass man XOR auch mit , und 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 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.
Induktive Definition eines aussagenlogischen Terms:
- Jede Aussagenvariable (z. B. , , ) ist ein Term.
- Ist ein Term, so ist auch (Negation) ein Term.
- Sind und Terme, so sind auch (Konjunktion, entspricht AND) und (Disjunktion, entspricht OR) Terme.
- Nichts anderes ist ein Term.
Die Buchstaben , und stehen hier nicht für Variablen, sondern für beliebige Terme – kleine wie oder große wie . Regel 4 ist wichtig: Sie sagt, dass es keine anderen Terme gibt als die, die man mit den Regeln 1 bis 3 bauen kann.
Wir bauen den Term Schritt für Schritt auf:
| Schritt | gebauter Term | Regel | gebaut aus |
|---|---|---|---|
| 1 | , , | 1 | – |
| 2 | 3 | , | |
| 3 | 2 | ||
| 4 | 3 | , |
Weil jeder Schritt eine der Regeln benutzt, ist ein Term.
Umgekehrt kann man bei einer Zeichenfolge prüfen, ob sie ein Term ist. Diese Zeichenfolgen sind keine Terme:
| Zeichenfolge | Warum kein Term? |
|---|---|
| Für braucht man zwei Terme, rechts fehlt einer. | |
| Das Zeichen muss zwischen zwei Termen stehen. | |
| Die schließende Klammer fehlt. | |
| steht vor einem Term, nicht zwischen zwei Termen. | |
| 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:
- Die äußersten Klammern dürfen weg: statt .
- Das Zeichen bezieht sich nur auf das, was direkt dahinter steht. bedeutet . Soll für mehr gelten, braucht man Klammern: .
- Bei lauter (oder lauter ) ist die Klammerung egal, das Ergebnis ist immer dasselbe. Man schreibt einfach statt .
- bindet stärker als – so wie Punkt vor Strich. bedeutet also .
Python hält sich übrigens an dieselbe Reihenfolge: zuerst
not, dann and, dann or.
Die letzte Vereinbarung ist leicht zu vergessen. Setze deshalb Klammern, sobald und zusammen vorkommen. Schreibe also lieber als . Zu viele Klammern schaden nie.
und sind zwei verschiedene Terme! Beim ersten wird das Ergebnis von umgedreht. Beim zweiten wird nur umgedreht. Setze für , ein: , aber .
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.
Meine Antworten:
Lösung vergleichen
Term. ist ein Term (Regel 1), also auch (Regel 2). Mit und ist ein Term (Regel 3).
Term. ist ein Term, also auch (Regel 2). Regel 2 darf man noch einmal anwenden: ist ein Term. (Er hat übrigens immer denselben Wert wie .)
Kein Term. Hinter dem fehlt der zweite Term.
Term. ist ein Term (Regel 3), also auch (Regel 2). Mit und ist ein Term (Regel 3).
Kein Term. So schreibt man in manchen Programmiersprachen, aber nicht in der Aussagenlogik. Das Zeichen 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:
- Ganz oben steht die Wurzel. Das ist der Operator, der zuletzt ausgerechnet wird.
- Unter jedem Operator hängen die Teilterme, mit denen er arbeitet: unter und zwei, unter einer.
- Ganz unten stehen die Blätter. Das sind die Variablen.
Hier ist der Termbaum zum Term :
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 () ist die Wurzel.
Ein Termbaum stellt einen Term als Baumstruktur dar. Die Blätter sind die Aussagenvariablen, die inneren Knoten die Operatoren (, , ). Der Operator, der zuletzt ausgewertet wird, steht an der Wurzel.
Ein Termbaum stellt einen Term als Baumstruktur dar: Die Blätter sind die Aussagenvariablen, die inneren Knoten die Operatoren (, , ).
So zeichnest du einen Termbaum
- Suche den Operator, der zuletzt ausgerechnet wird. Das ist der Operator, der außerhalb aller Klammern steht. Stehen dort mehrere, nimm den schwächsten ( vor vor ). Er wird die Wurzel.
- Zeichne darunter seine Teilterme. Bei und ist das der Teil links und der Teil rechts vom Zeichen. Bei ist es das, was dahinter steht.
- Wiederhole Schritt 1 und 2 für jeden Teilterm, bis nur noch Variablen übrig sind.
Für : Außerhalb der Klammer stehen und . Das schwächere Zeichen ist , also ist die Wurzel. Links davon steht , rechts . 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 , , sieht das so aus (die Werte stehen rot neben den Knoten):
- : .
- : .
- An der Wurzel: . Der Term hat also für diese Belegung den Wert 0.
Zeichne den Termbaum zum Term
Mein Termbaum:
Lösung vergleichen
Außerhalb der Klammer stehen und . Das schwächere Zeichen ist , also ist die Wurzel. Links hängt der Teilterm , rechts . Unter hängt nur ein Teilterm, nämlich .
Häufiger Fehler: als Wurzel nehmen. Das gilt aber nur für die Klammer , nicht für .
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:
- Die Blätter (Variablen) werden zu den Eingängen links.
- Jeder innere Knoten wird zu einem Gatter: zum UND-Gatter, zum ODER-Gatter, zum NICHT-Gatter.
- Die Wurzel wird zum letzten Gatter. Sein Ausgang ist der Ausgang der Schaltung.
So sieht die Schaltung zum Term aus:
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 ( und ), 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:
- An den Eingängen stehen die Variablen.
- Am Ausgang jedes Gatters steht der Teilterm, der aus seinen Eingängen entsteht. Ein UND-Gatter mit den Eingängen und liefert zum Beispiel .
- 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 sprichst du über Terme und Schaltungen – vom einfachen zum genauen Satz:
- „Der Baum zeigt, wie der Term aufgebaut ist.“ → „Der Termbaum stellt den logischen Term dar und strukturiert ihn.“
- „Die Formel ist die Schaltung.“ → „Der logische Term repräsentiert die Schaltung.“
- „A ist 1 und B ist 0.“ → „Die logischen Variablen werden mit Werten belegt: mit 1, mit 0.“
Gib den Term an, den die folgende Schaltung darstellt. Zeichne anschließend den Termbaum.
Term und Termbaum:
Lösung vergleichen
Das NICHT-Gatter liefert . Das ODER-Gatter verknüpft mit zu . Das UND-Gatter verknüpft dieses Ergebnis mit . Der Term lautet also
Die Klammer ist nötig, weil sonst stärker binden würde als .
Im Abschnitt über Schaltungsentwurf hast du die Alarmanlage gebaut:
Zeichne den Termbaum zu diesem Term.
Mein Termbaum:
Lösung vergleichen
Die Wurzel ist , 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
,
or für
,
not für
.
Damit kannst du prüfen, ob du einen Term richtig verstanden hast. Das
folgende Programm gibt die Belegungstabelle zum Term
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
- Zeilen 1–2: Die Funktion
term1rechnet den Term für eine Belegung aus. Python wertetnotvorandaus – genau wie in der Aussagenlogik.int(...)sorgt dafür, dass das Ergebnis als 0 oder 1 erscheint und nicht alsTrueoderFalse. - Zeilen 5–7: Drei ineinander geschachtelte Schleifen
gehen alle Belegungen durch. Jede Variable läuft über die Liste
[0, 1]. Die innerste Schleife (fürc) läuft am schnellsten. So entstehen die Belegungen in der üblichen Reihenfolge von 000 bis 111. - Zeile 8: Für jede Belegung wird eine Zeile der Tabelle ausgegeben.
Der Term ist nur bei , , wahr. Das passt zur Bedeutung: „Weder noch , aber .“
Jetzt geht es in die umgekehrte Richtung. Nimm den Term aus dem Auftrag Vom Term zum Termbaum.
- Skizziere die zugehörige Schaltung mit IEC-Symbolen.
- Baue die Schaltung in CircuitVerse: ein ODER-Gatter für , ein NICHT-Gatter dahinter und ein UND-Gatter, das das Ergebnis mit verknüpft.
- Teste alle 8 Belegungen. Vergleiche mit deinem Termbaum und mit der Ausgabe des Python-Programms oben.
Meine Skizze:
Lösung vergleichen
Die Schaltung hat drei Gatter, so viele, wie der Termbaum innere Knoten hat. Beim Testen in CircuitVerse leuchtet der Ausgang nur bei , , – genau wie in der Python-Ausgabe:
| 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 |
Formuliere einen aussagenlogischen Term für folgende Situation: „Der
Ausgang ist 1, wenn genau eine der drei Variablen
,
,
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 .
Mein Term:
Lösung vergleichen
Es gibt drei passende Fälle: Nur ist 1, nur ist 1 oder nur ist 1. „Nur “ heißt: ist 1, und sind 0, also . Die drei Fälle werden mit verbunden:
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
:
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.
Ergänze die Tabelle.
| Name | Zeichen | Gatter | Python |
|---|---|---|---|
| Negation | |||
| ODER (OR) |
Lösung vergleichen
| Name | Zeichen | Gatter | Python |
|---|---|---|---|
| Negation | NICHT (NOT) | not |
|
| Konjunktion | UND (AND) | and |
|
| Disjunktion | ODER (OR) | or |
Merkhilfe: Das Zeichen sieht aus wie ein „v“ wie in vel, dem lateinischen Wort für „oder“.
Zeichne zu jedem Term den Termbaum.
- b) c)
Deine Termbäume:
Lösung vergleichen
- Das gilt nur für . Die Wurzel ist deshalb .
- Die Klammer wird zuerst ausgewertet, die Wurzel ist .
- Das äußere gilt für die ganze Klammer, es ist die Wurzel. Darunter hängt , und das zweite gilt nur für .
Gib zu jedem Termbaum den Term an. Setze Klammern, wo sie nötig sind.
Deine Terme:
Lösung vergleichen
Jeder Operator, der in einem Teilbaum unter einem anderen Operator hängt, wird zuerst ausgewertet. Bei b) muss deshalb eine Klammer um , sonst würde das nur für gelten. Bei a) zeigt die Klammer um , dass das UND zuerst ausgewertet wird. In c) darf dieselbe Variable in zwei Blättern vorkommen.
Entscheide mit der induktiven Definition, ob die Zeichenfolge ein aussagenlogischer Term ist. Begründe mit den Regeln.
Deine Antworten:
Lösung vergleichen
- Term nach Regel 1: Jede Aussagenvariable ist ein Term.
- Term: ist ein Term (Regel 1), also auch (Regel 2). Mit und ist ein Term (Regel 3).
- Kein Term: Hinter dem zweiten fehlt ein Term.
- Term: ist ein Term (Regel 3), ebenfalls (Regel 2). Beide werden mit Regel 3 zu verbunden.
- Kein Term: Das Zeichen kommt in den Regeln nicht vor. Nach Regel 4 ist nichts anderes ein Term. XOR muss man in der Aussagenlogik mit , und ausdrücken.
- Kein Term: muss zwischen zwei Termen stehen, und muss vor einem Term stehen. Hier steht vor einem .
- Gib den Term an, den die Schaltung darstellt.
- Zeichne den Termbaum.
- Berechne den Wert von für die Belegung , , . Schreibe die Zwischenwerte an die Knoten deines Termbaums.
Term, Termbaum und Wert:
Lösung vergleichen
Das NICHT-Gatter liefert , das ODER-Gatter . Das UND-Gatter verknüpft beide:
Von unten nach oben: und , an der Wurzel . Also ist .
Die Klammer um ist nötig. Sie zeigt, dass das ODER-Gatter zuerst rechnet und sein Ergebnis in das UND-Gatter geht.
Formuliere einen aussagenlogischen Term für die Situation: „Der
Ausgang ist 1, wenn genau zwei der drei Variablen
,
,
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.
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 .
Dein Term:
Lösung vergleichen
Es gibt drei Fälle: Nur ist 0, nur ist 0 oder nur ist 0. „Nur ist 0“ heißt: und sind 1, ist 0, also . Die drei Fälle werden mit verbunden:
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 : Sie liefert auch in der letzten Zeile eine 1, obwohl dort alle drei Variablen 1 sind.
2.6.8Das Wichtigste in Kürze
- Eine Aussagenvariable steht für eine Aussage und hat den Wert 1 (wahr) oder 0 (falsch). Sie entspricht einem Eingang einer Schaltung.
- Negation , Konjunktion und Disjunktion entsprechen dem NICHT-, UND- und ODER-Gatter.
- Aussagenlogische Terme sind induktiv definiert: Variablen sind Terme; aus Termen entstehen mit , , und Klammern neue Terme; sonst gibt es keine Terme.
- Klammern darf man sparen: äußerste Klammern weglassen, bindet am stärksten, dann , dann .
- Ein Termbaum zeigt den Aufbau eines Terms: Blätter sind Variablen, innere Knoten Operatoren. Termbaum und Schaltung haben denselben Aufbau: Jeder innere Knoten ist ein Gatter.
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.
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.
Nach diesem Abschnitt kannst du
- zu einem Term systematisch die Belegungstabelle erstellen,
- den Begriff der Äquivalenz zweier Terme erläutern,
- prüfen, ob zwei Terme äquivalent sind – von Hand und mit Python,
- aus einer Belegungstabelle die disjunktive Normalform (DNF) ablesen,
- die DNF zu einem gegebenen Term erstellen.
2.7.1Belegungstabellen zu Termen
Eine Belegungstabelle enthält für jede mögliche Belegung der Variablen eine Zeile. Bei Variablen gibt es 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 bis . 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 sind das zuerst , dann und zuletzt der ganze Term:
| 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 zum Beispiel ist nur dort 1, wo sowohl in der Spalte als auch in der Spalte eine 1 steht. Die letzte Spalte ist 1, wo in der Spalte oder in der Spalte eine 1 steht.
Lies eine Zeile der Belegungstabelle immer als ganzen Satz. Die fünfte Zeile besagt: „Ist mit 1, mit 0 und mit 0 belegt, dann hat der Term den Wert 1.“
Erstelle von Hand die vollständige Belegungstabelle zum Term
Überprüfe dein Ergebnis anschließend mit einem Python-Programm.
| 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
| 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 , den Wert 1 hat und den Wert 0 hat.
2.7.2Äquivalenz: verschiedene Terme, gleiche Wirkung
Vergleiche die beiden Terme und . Sie sehen ganz verschieden aus. Schau dir aber ihre Belegungstabellen an:
| 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 überein! Egal, wie man und 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 braucht ein UND- und ein ODER-Gatter. Die Schaltung zu braucht gar kein Gatter – der Ausgang ist einfach mit dem Eingang verbunden. Beide Schaltungen verhalten sich genau gleich. Natürlich baut man dann die einfachere.
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 oder . Wir schreiben deshalb einfach: „Die Terme und sind äquivalent.“
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.
| 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 , ist , aber . 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
- Zeilen 1–5: Jeder Term wird als eigene Funktion geschrieben.
- Zeile 7: Die Variable
aequivalentstartet mitTrue: Solange kein Unterschied gefunden ist, gehen wir von Äquivalenz aus. - Zeilen 8–9: Zwei geschachtelte Schleifen erzeugen alle vier Belegungen.
- Zeilen 10–12: Liefern die beiden Funktionen
verschiedene Werte, wird
aequivalentaufFalsegesetzt und das Gegenbeispiel ausgegeben. - Zeile 14: Am Ende steht fest, ob es irgendeine Belegung mit einem Unterschied gab.
Hier wurde kein Unterschied gefunden, also gibt das Programm nur
True 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?
Prüfe mit Python, ob die beiden folgenden Terme äquivalent sind. Vergleiche dazu für alle Belegungen, ob beide Funktionen stets denselben Wert liefern.
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
| 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 und 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:
Regeln von De Morgan: Für alle Belegungen von und gilt
- ist äquivalent zu („nicht beide“ = „mindestens einer nicht“),
- ist äquivalent zu („keiner von beiden“ = „der eine nicht und der andere auch nicht“).
Merkregel: Zieht man das in die Klammer, wird jede Variable verneint, und aus wird bzw. aus wird .
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.
Zeige mit einer Belegungstabelle, dass und äquivalent sind. Fülle dazu die Tabelle aus und begründe dein Ergebnis in einem Satz.
| 0 | 0 | |||||
| 0 | 1 | |||||
| 1 | 0 | |||||
| 1 | 1 |
Begründung:
Lösung vergleichen
| 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 und stimmen in allen vier Zeilen überein. Also sind die beiden Terme äquivalent. Beide sind nur dann 1, wenn und beide 0 sind.
Ein sehr häufiger Fehler ist, das einfach in die Klammer „hineinzuziehen“: ist nicht äquivalent zu . Gegenbeispiel: Für , ist , aber . Wer das in die Klammer zieht, muss das in ein 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:
| 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.
- Zeile , : Wir brauchen „ ist 0 und ist 1“. „ ist 0“ heißt dasselbe wie „ ist 1“. Der Steckbrief lautet also .
- Zeile , : Der Steckbrief lautet .
Der Ausgang soll 1 sein, wenn wir in der einen oder in der anderen Zeile sind. Also verbinden wir die Steckbriefe mit :
Das ist die disjunktive Normalform der Tabelle. Übrigens ist die Tabelle genau die von XOR. Wir haben also nebenbei herausgefunden, wie man XOR mit , und schreibt.
Ein Minterm ist eine Konjunktion, in der jede Variable genau einmal vorkommt, entweder ohne oder mit . Er hat genau in einer Zeile der Belegungstabelle den Wert 1.
Die disjunktive Normalform (DNF) einer Belegungstabelle ist die Disjunktion () der Minterme aller Zeilen, in denen das Ergebnis 1 ist.
Der Name erklärt sich so: disjunktiv, weil die Minterme mit (Disjunktion) verbunden werden; Normalform, weil jeder Term auf diese feste, „normale“ Form gebracht werden kann.
Die disjunktive Normalform (DNF) ist eine standardisierte Darstellung eines Terms:
- Für jede Zeile der Belegungstabelle, in der der Ausgang 1 ist, bildet man einen Minterm: die Konjunktion aller Variablen, wobei Variablen mit Wert 0 negiert werden.
- Alle Minterme werden anschließend disjunktiv (mit ) verknüpft.
Beispiel: Ist der Ausgang bei und bei gleich 1 (sonst 0), lautet die DNF – das ist genau XOR!
Ob man die Minterme in der Reihenfolge oder aufschreibt, ist egal. Bei 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
- Suche in der Belegungstabelle alle Zeilen, in denen das Ergebnis 1 ist. Die Zeilen mit 0 brauchst du nicht.
- Schreibe für jede dieser Zeilen den Minterm auf: alle Variablen mit verbunden; eine Variable, die in der Zeile 0 ist, bekommt ein .
- Setze um jeden Minterm Klammern und verbinde alle Minterme mit .
DNF der Alarmanlage. Wir kürzen ab: für Tür, für Scharf, für Rauch. Der Term lautet . Zuerst die Belegungstabelle, dann für jede 1-Zeile der Minterm:
| Minterm | ||||
|---|---|---|---|---|
| 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 DNF lautet:
Sie ist äquivalent zu , aber viel länger. Im nächsten Abschnitt lernst du, wie man eine DNF wieder vereinfacht.
- Negation vertauscht: Eine Variable bekommt ein , wenn sie in der Zeile 0 ist – nicht, wenn sie 1 ist.
- Variable vergessen: In jedem Minterm müssen alle Variablen vorkommen. ist kein Minterm, wenn es drei Variablen gibt.
- Falsche Zeilen: Nur die Zeilen mit Ergebnis 1 werden verwendet.
- Falsche Zeichen: Innerhalb eines Minterms steht , zwischen den Mintermen – nicht umgekehrt.
So sprichst du über Belegungstabellen und Terme – vom einfachen zum genauen Satz:
- „Die Tabelle passt zum Term.“ → „Die Belegungstabelle gehört zum Term.“
- „In Zeile 5 kommt 1 raus.“ → „Die fünfte Zeile der Belegungstabelle besagt: Ist mit 1 und sind und mit 0 belegt, hat der Term den Wert 1.“
- „Die beiden Terme sind gleich.“ → „Die beiden Terme sind äquivalent, denn ihre Belegungstabellen stimmen überein.“
Gegeben ist folgende Belegungstabelle:
| 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 |
- Bestimme die DNF auf Papier.
- 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 , und . Die DNF lautet:
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.
Bestimme die DNF zum Term aus dem Auftrag Vom Term zur Belegungstabelle. Benutze deine Belegungstabelle von dort.
Meine DNF:
Lösung vergleichen
Die Belegungstabelle hat drei 1-Zeilen: , und . Die DNF lautet:
Sie ist äquivalent zum Term , 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.
Erstelle die Belegungstabelle zum Term . Benutze die Hilfsspalte.
| 0 | 0 | ||
| 0 | 1 | ||
| 1 | 0 | ||
| 1 | 1 |
Lösung vergleichen
| 0 | 0 | 1 | 1 |
| 0 | 1 | 1 | 1 |
| 1 | 0 | 0 | 0 |
| 1 | 1 | 0 | 1 |
Der Term ist nur in der Zeile , gleich 0. Dort sind beide Teile der Disjunktion 0.
Schreibe zu jeder Belegung den Minterm auf (drei Variablen , , ).
- , , b) , , c) , ,
Jetzt umgekehrt: Bei welcher Belegung hat der Minterm den Wert 1?
Deine Antworten:
Lösung vergleichen
- b) c)
- Bei , , . Jede Variable mit muss 0 sein, jede ohne muss 1 sein.
Merke: Eine Variable bekommt ein , wenn sie in der Zeile den Wert 0 hat.
Bestimme die DNF zu dieser Belegungstabelle. Beschreibe in Worten, wann der Ausgang 1 ist.
| Ausgang | ||
|---|---|---|
| 0 | 0 | 1 |
| 0 | 1 | 0 |
| 1 | 0 | 0 |
| 1 | 1 | 1 |
DNF und Beschreibung:
Lösung vergleichen
Die 1-Zeilen sind und . Die DNF lautet
Der Ausgang ist 1, wenn und gleich sind. Das ist das Gegenteil von XOR.
Bestimme die DNF zu dieser Belegungstabelle.
| 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 und . Die DNF lautet
Innerhalb eines Minterms steht , zwischen den Mintermen .
Prüfe mit Belegungstabellen, ob die beiden Terme äquivalent sind. Wenn nicht, gib eine Belegung an, in der sie sich unterscheiden.
- und
- und
Deine Tabellen und deine Antwort:
Lösung vergleichen
- äquivalent:
| 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.
- nicht äquivalent:
| 0 | 0 | 1 | 1 |
| 0 | 1 | 0 | 1 |
| 1 | 0 | 0 | 1 |
| 1 | 1 | 0 | 0 |
Zum Beispiel bei , ist , aber . Eine einzige solche Zeile genügt. Das ist ein typischer Fehler: Man darf das nicht einfach in die Klammer schreiben und das stehen lassen. Äquivalent zu ist .
Gegeben ist der Term .
- Erstelle die Belegungstabelle mit Hilfsspalten.
- Bestimme die DNF.
| 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
| 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 , , und . Die DNF lautet
Sie ist äquivalent zum gegebenen Term, aber deutlich länger.
Prüfe mit Python, ob die Terme äquivalent sind. Wenn nicht, soll das Programm alle Belegungen ausgeben, in denen sie sich unterscheiden.
- und
- und
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
- Die Terme sind äquivalent. „ und ( oder )“ heißt dasselbe wie „( und ) oder ( und )“.
- Die Terme sind nicht äquivalent. Bei , ist der linke Term 1 (weil ), der rechte aber 0 (weil ). Die Klammern stehen an verschiedenen Stellen. Das ändert die Bedeutung.
Wichtig: Vor dem zweiten Vergleich muss aequivalent
wieder auf True gesetzt werden.
Eine Warnleuchte im Auto () leuchtet, wenn der Motor läuft () und der Gurt nicht angelegt ist (). Sie leuchtet außerdem, wenn der Motor läuft und eine Tür offen ist ().
- Stelle die Belegungstabelle für , , auf.
- Bestimme die DNF.
- Mia hat den kürzeren Term gefunden. Prüfe mit Python, ob er zu deiner DNF äquivalent ist.
Tabelle und DNF:
Lösung vergleichen
- Die Leuchte leuchtet nur bei laufendem Motor. Hilfsspalten für die beiden Fälle machen die Tabelle übersichtlich:
| 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 |
- Die 1-Zeilen sind , und :
- 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
- Eine Belegungstabelle hat bei Variablen Zeilen. Die Belegungen werden wie Binärzahlen von bis aufgeschrieben. Hilfsspalten für Teilterme erleichtern das Ausrechnen.
- Zwei Terme sind äquivalent, wenn ihre Belegungstabellen übereinstimmen. Äquivalenz ist ein Begriff über Terme, kein Operator.
- Für den Nachweis der Äquivalenz prüft man alle Zeilen. Für den Nachweis, dass Terme nicht äquivalent sind, genügt ein Gegenbeispiel.
- Regeln von De Morgan: ist äquivalent zu , und ist äquivalent zu .
- Ein Minterm ist eine Konjunktion aller Variablen (Variablen mit Wert 0 negiert). Er ist genau in einer Zeile 1.
- Die DNF ist die Disjunktion der Minterme aller 1-Zeilen. Sie ist zum ursprünglichen Term äquivalent, aber oft lang.
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.
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 dasselbe leistet. Jedes , und 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.
Nach diesem Abschnitt kannst du
- die Kosten einer Schaltung über die Anzahl ihrer Gatter vergleichen,
- ein KV-Diagramm für zwei, drei und vier Variablen aufstellen und erklären, warum die Spalten in der Reihenfolge 00, 01, 11, 10 stehen,
- Einsen zu Blöcken der Größe 1, 2, 4 und 8 zusammenfassen, auch über den Rand hinweg,
- aus den Blöcken den vereinfachten Term ablesen,
- die vereinfachte Form mit der DNF vergleichen und ihre Äquivalenz mit Python prüfen.
2.8.1Warum vereinfachen? Die Kosten einer Schaltung
Als einfaches Maß für die Kosten einer Schaltung zählen wir ihre Gatter. Dabei gilt:
- Wir nehmen an, dass jedes UND- und jedes ODER-Gatter zwei Eingänge hat. Für braucht man deshalb zwei UND-Gatter: eins für , ein zweites, das das Ergebnis mit verknüpft. (Ein UND-Gatter mit drei Eingängen, wie bei der Fahrstuhltür, zählt also wie zwei Gatter.)
- Jedes NICHT-Gatter zählt mit. Kommt dieselbe negierte Variable mehrmals vor, genügt ein NICHT-Gatter: Seine Ausgangsleitung wird einfach verzweigt.
Vergleiche damit die beiden äquivalenten Terme der Alarmanlage (: Tür offen, : Scharf, : Rauch):
| Term | UND | ODER | NICHT | Gatter gesamt |
|---|---|---|---|---|
| DNF mit 5 Mintermen | 4 | 3 | 17 | |
| 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 , und 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 und eine 1. Die DNF lautet:
Schau dir die beiden Minterme genau an. Sie stimmen in überein und unterscheiden sich nur bei . Der erste verlangt , der zweite . Zusammen heißt das: Wenn ist, ist das Ergebnis 1 – egal, welchen Wert hat. spielt also keine Rolle und fällt weg. Übrig bleibt:
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 an, die Spalte den Wert von . 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 , hat die Nummer .
In unserem Beispiel stehen die beiden Einsen in der oberen Zeile () nebeneinander. Wir umranden sie als Block. Im ganzen Block hat den Wert 0, dagegen wechselt. Also bleibt nur übrig:
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 an. Die Spalte gibt die Werte von und zusammen an. Achtung: Die Spalten stehen nicht in der Reihenfolge 00, 01, 10, 11, sondern
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.
Um eine Belegungstabelle ins KV-Diagramm zu übertragen, liest du in jeder Zeile die Belegung als Binärzahl. Die Zeile hat die Nummer . Ihr Wert gehört in das Feld in der Zeile und der Spalte . 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:
- Ein Block enthält nur Einsen.
- Ein Block ist ein Rechteck aus 1, 2, 4 oder 8 Feldern. Blöcke aus 3 oder 6 Feldern gibt es nicht.
- Blöcke dürfen über den Rand gehen: Gegenüberliegende Ränder sind Nachbarn.
- Blöcke dürfen sich überlappen.
- Jede 1 muss in mindestens einem Block liegen.
- 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 , wenn der Wert 0 ist. Alle anderen fallen weg. Die Terme aller Blöcke werden mit 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.
- Ein Karnaugh-Veitch-Diagramm (KV-Diagramm) ordnet alle Belegungen so in einem Raster an, dass sich benachbarte Felder nur in genau einer Variablen unterscheiden.
- Benachbarte Einsen werden zu Blöcken der Größe 1, 2, 4, 8 … zusammengefasst. Je größer der Block, desto weniger Variablen braucht der zugehörige Term.
- Innerhalb eines Blocks fällt jede Variable weg, die sowohl negiert als auch nicht negiert vorkommt. Übrig bleiben nur die Variablen, die im gesamten Block konstant sind.
Mehrheitsentscheid. Drei Personen , , 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:
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:
- Rot (Felder 3 und 7): und sind konstant, wechselt. Term: .
- Blau (Felder 5 und 7): und sind konstant, wechselt. Term: .
- Grün (Felder 6 und 7): und sind konstant, wechselt. Term: .
Der vereinfachte Term lautet . 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).
- Diagonal ist nicht benachbart. Zwei Felder, die sich nur an einer Ecke berühren, unterscheiden sich in zwei Variablen. Sie dürfen nicht in einen Zweierblock.
- Keine Dreierblöcke. Drei Einsen in einer Reihe deckt man mit zwei überlappenden Zweierblöcken ab.
- Nicht zu klein. Wer zwei Zweierblöcke zeichnet, wo ein Viererblock möglich ist, bekommt einen richtigen, aber längeren Term.
- Rand vergessen. Viele übersehen Blöcke über den Rand. Prüfe immer: Stehen in der ersten und der letzten Spalte (bei vier Variablen auch in der ersten und der letzten Zeile) Einsen, die man zusammenfassen kann? Wie das aussieht, zeigt der Abschnitt Über den Rand hinaus weiter unten.
Gegeben ist folgende Belegungstabelle für drei Variablen:
| 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 |
- Zeichne ein KV-Diagramm und finde die größtmöglichen Blöcke.
- Notiere die minimierte Form.
- Ü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))Minimierte Form:
Lösung vergleichen
Alle vier Einsen liegen in den beiden linken Spalten ( und ), und zwar in beiden Zeilen. Sie bilden einen Viererblock. Im ganzen Block ist , während und wechseln. Die minimierte Form lautet also
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 (obere Zeile) und (untere Zeile) gefunden hat, erhält . 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:
Die Einsen stehen in der ersten Spalte () und in der letzten Spalte (). Diese beiden Spalten unterscheiden sich nur in . 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 , und wechseln. Der Term lautet .
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 und an, die Spalten die Werte von und . Beide folgen dem Gray-Code 00, 01, 11, 10. Die Feldnummern erhältst du wieder, indem du 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:
- Rot (Felder 4, 5, 12, 13): In beiden Zeilen ist , in beiden Spalten ist . und wechseln. Term: .
- Blau (Felder 5, 7, 13, 15): und sind konstant. Term: .
Der vereinfachte Term lautet . 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:
In allen vier Ecken ist (Zeilen 00 und 10) und (Spalten 00 und 10). Der Term lautet .
Beispiel: ein Achterblock
Hier ist der Ausgang in den Zeilen 0 bis 7 und in Zeile 15 gleich 1:
- Rot (die beiden oberen Zeilen, acht Felder): Nur ist konstant. Term: .
- Blau (Felder 7 und 15): Feld 15 hat keinen Viererblock. Sein bester Partner ist Feld 7 direkt darüber, denn die Zeilen 01 und 11 sind benachbart. , und sind konstant. Term: .
Der vereinfachte Term lautet . Die DNF hätte neun Minterme.
Vereinfache mithilfe eines KV-Diagramms. Benutze die Vorlagen unten.
- die DNF
- Drei Variablen , , : Der Ausgang ist genau in den Zeilen 0, 2 und 5 der Belegungstabelle 1.
- Vier Variablen , , , : Der Ausgang ist genau in den Zeilen 0, 1, 2, 3, 8, 9, 10 und 11 der Belegungstabelle 1.
Meine vereinfachten Terme:
Lösung vergleichen
- Die Minterme gehören zu den Zeilen 1, 3, 5 und 7. Das sind die beiden mittleren Spalten ( und ). Dort ist überall :
Ergebnis: .
- Die Felder 0 und 2 liegen in der oberen Zeile ganz links und ganz rechts. Über den Rand sind sie Nachbarn: , . Feld 5 hat keinen Nachbarn mit einer 1 und bleibt ein Einerblock:
Ergebnis: . Der Einerblock bleibt ein vollständiger Minterm.
- Die Einsen füllen die oberste Zeile () und die unterste Zeile (). Die beiden Zeilen sind über den Rand benachbart. Zusammen bilden sie einen Achterblock, in dem nur konstant ist:
Ergebnis: .
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
Erinnere dich an die Alarmanlage: . 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.
Meine Begründung:
Lösung vergleichen
Die Belegungstabelle (siehe Abschnitt über die DNF) hat Einsen in den Zeilen 1, 3, 5, 6 und 7:
Die vier Felder mit (die beiden mittleren Spalten) bilden einen Viererblock: Term . Die Felder 6 und 7 bilden einen Zweierblock mit und : Term . Größere Blöcke gibt es nicht, weil die Felder 0, 2 und 4 den Wert 0 haben.
Das KV-Diagramm liefert also . 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 sprichst du über KV-Diagramme – vom einfachen zum genauen Satz:
- „Damit wird der Term kürzer.“ → „Das KV-Diagramm vereinfacht (minimiert) die DNF.“
- „Die vier Einsen kreise ich ein.“ → „Die vier Felder werden zu einem Block zusammengefasst.“
- „B ist hier egal.“ → „Im Block kommt negiert und nicht negiert vor, deshalb fällt weg.“
Erstelle selbst eine Belegungstabelle mit vier
Variablen
,
,
,
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.
Die vier Felder bilden einen Viererblock in der Mitte. und sind konstant, und wechseln. Die minimierte Form lautet . Die DNF lautet
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
)
oder eine ganze Zeile des Diagramms (Zeilen 4, 5, 6, 7, Term
).
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.
Im KV-Diagramm werden nur Felder zu einem Zweierblock zusammengefasst, die sich in genau einer Variablen unterscheiden. Gib für jedes Paar von Belegungen (, , ) 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 () | ja |
| 0 1 1 | 1 1 1 | 1 () | ja |
| 0 0 1 | 0 1 0 | 2 ( und ) | nein |
| 1 1 0 | 1 1 1 | 1 () | ja |
| 1 0 1 | 1 1 0 | 2 ( und ) | nein |
| 0 1 0 | 1 1 0 | 1 () | ja |
In einem Zweierblock fällt genau die Variable weg, in der sich die beiden Felder unterscheiden. Bei zwei verschiedenen Variablen geht das nicht.
Übertrage die Belegungstabelle in das KV-Diagramm. Achte auf die Reihenfolge der Spalten: 00, 01, 11, 10.
| 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 |
Lösung vergleichen
Die Zeile gibt an, die Spalte und zusammen. Die Belegung , , steht also in der unteren Zeile in der letzten Spalte (), nicht in der dritten. Wer die Spalten in der Reihenfolge 00, 01, 10, 11 füllt, vertauscht die beiden rechten Spalten.
Gib zu jedem eingezeichneten Block den Term an.
Deine Terme:
Lösung vergleichen
- Im Block ist , wechselt. Term: .
- Im Block ist und , wechselt (Spalten 01 und 11). Term: .
- Der Block ist die ganze obere Zeile. Dort ist nur konstant, und wechseln. Term: .
Prüfe bei jeder Variablen: Hat sie im ganzen Block denselben Wert? Nur dann bleibt sie im Term, mit , wenn der Wert 0 ist.
Vereinfache die DNF mithilfe eines KV-Diagramms.
Deine vereinfachten Terme:
Lösung vergleichen
- Die beiden Einsen stehen in der unteren Zeile. Dort ist , wechselt. Ergebnis: .
- Die obere Zeile ist ein Block mit , die rechte Spalte ein Block mit . Das Feld , liegt in beiden Blöcken. Das ist erlaubt. Ergebnis: .
Die Tabelle enthält zwei Ausgänge und . Vereinfache beide mit je einem KV-Diagramm. Prüfe dein Ergebnis zu mit Python: Vergleiche für alle Belegungen deine vereinfachte Form mit der DNF.
| 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 |
Deine vereinfachten Terme:
Lösung vergleichen
- Die vier Einsen stehen in den beiden rechten Spalten ( und ). Dort ist , und wechseln. Ergebnis: .
- Die Felder , und , bilden einen Block mit , . Die Felder , und , bilden einen Block mit , . Ergebnis: .
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 . Er wird aber nicht gebraucht, denn diese beiden Einsen liegen schon in den anderen Blöcken. So wenige Blöcke wie möglich!
Tom hat ein KV-Diagramm ausgefüllt und die drei Einsen mit einem Block umrandet. Daraus liest er den Term ab.
- Erkläre, welche Regel Tom verletzt hat.
- Zeige mit einer Belegung, dass sein Term falsch ist.
- Gib den richtigen vereinfachten Term an.
Deine Antwort:
Lösung vergleichen
- Ein Block muss aus 1, 2, 4 oder 8 Feldern bestehen. Einen Block aus drei Feldern gibt es nicht.
- ist auch bei , , gleich 1. In diesem Feld steht aber eine 0.
- Drei Einsen nebeneinander deckt man mit zwei Zweierblöcken ab, die sich überlappen:
Rot (, ): . Blau (, ): . Ergebnis: .
Der Ausgang einer Schaltung soll genau bei diesen Belegungen 1 sein: , , , und . Die Werte stehen in der Reihenfolge , , .
- Wie viele Minterme hätte die DNF?
- Vereinfache mit einem KV-Diagramm.
- Skizziere die Schaltung zum vereinfachten Term und gib an, wie viele Gatter sie braucht.
Dein Term und deine Skizze:
Lösung vergleichen
- Fünf Minterme, für jede 1-Zeile einen.
- Vereinfachung:
Die ganze untere Zeile ist ein Viererblock mit . Das Feld bildet mit dem Feld darunter einen Zweierblock mit , . Ergebnis: .
- Die Schaltung braucht nur zwei Gatter:
Die DNF mit fünf Mintermen aus je drei Variablen bräuchte viel mehr Gatter. Beide Schaltungen tun genau dasselbe.
Vereinfache die DNF mit einem KV-Diagramm für vier Variablen. Prüfe dein Ergebnis mit Python.
Die Zeilen des Diagramms geben und an, die Spalten und . Beide folgen der Reihenfolge 00, 01, 11, 10. Trage für jeden Minterm eine 1 ein: Für zum Beispiel in die Zeile und die Spalte .
Dein vereinfachter Term:
Lösung vergleichen
- Rot: Die vier Einsen in den Zeilen und und den Spalten und bilden einen Viererblock. Konstant sind und . Term: .
- Blau: Die Eins bei , , , hat keinen Viererblock. Sie bildet mit dem Feld links daneben () einen Zweierblock. Konstant sind , , . Term: .
Ergebnis: .
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 und stehen im Diagramm direkt untereinander und unterscheiden sich nur in . Deshalb dürfen sie in einen Block. Typischer Fehler: die Eins bei vergessen oder als eigenen Einerblock mit vier Variablen stehen lassen. Das ist richtig, aber nicht minimal.
2.8.8Das Wichtigste in Kürze
- Die Kosten einer Schaltung messen wir an der Anzahl der Gatter. Eine DNF ist oft viel teurer als nötig.
- Im KV-Diagramm sind die Belegungen im Gray-Code 00, 01, 11, 10 angeordnet. Benachbarte Felder unterscheiden sich in genau einer Variablen. Auch gegenüberliegende Ränder sind benachbart.
- Benachbarte Einsen werden zu rechteckigen Blöcken aus 1, 2, 4 oder 8 Feldern zusammengefasst – so groß und so wenige wie möglich. Blöcke dürfen sich überlappen und über den Rand gehen.
- Zu jedem Block gehört die Konjunktion der Variablen, die im Block konstant sind. Die Blockterme werden mit verbunden.
- Das Ergebnis ist eine minimierte DNF: äquivalent zur DNF, aber mit weniger Gattern.
2.9Kapitel 2 kompakt: der Lernzettel
Diesen Abschnitt als PDF (S. 130–132)
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)
| Gatter | Zeichen | Term | Ausgang 1, wenn … |
|---|---|---|---|
| UND (AND) | & |
alle Eingänge 1 sind | |
| ODER (OR) | ≥1 |
mindestens ein Eingang 1 ist | |
| XOR | =1 |
die Eingänge unterschiedlich sind | |
| NICHT (NOT) | 1 mit Kreis |
der Eingang 0 ist (Gegenteil) |
| 0 | 0 | 0 | 0 | 0 | 1 |
| 0 | 1 | 0 | 1 | 1 | 1 |
| 1 | 0 | 0 | 1 | 1 | 0 |
| 1 | 1 | 1 | 1 | 0 | 0 |
- Belegungstabelle: für jede Kombination der Eingangswerte der Ausgangswert. Bei Eingängen Zeilen (3 Eingänge: 8 Zeilen). Reihenfolge: Die letzte Spalte wechselt in jeder Zeile, die davor alle 2 Zeilen, die davor alle 4 Zeilen.
- Schaltung → Tabelle: von links nach rechts, für jeden Gatterausgang eine Hilfsspalte.
- Entwurf in vier Schritten: Eingänge und Ausgang benennen (was bedeuten 1 und 0?), Belegungstabelle aufstellen, Gatter auswählen und verschalten (Term hilft), mit allen Belegungen testen.
- Beispiel Alarmanlage: . Was in der Klammer steht, rechnet ein eigenes Gatter zuerst.
- Kontrolle mit Python:
and,or,not, XOR alsa != b; alle Belegungen mit geschachtelten Schleifenfor a in [0, 1]:usw. Ergebnis mitint(...)als 0 oder 1 ausgeben.
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 ( ist nicht ).
2.9.2Binäre Addition, Halb- und Volladdierer (Abschnitte 2.3 und 2.4)
- Binäre Addition wie schriftlich im Dezimalsystem, von rechts nach links: , (0 schreiben, 1 übertragen), (1 schreiben, 1 übertragen). Überträge in eine eigene Ü-Zeile.
0 1 0 1 (= 5)
+ 0 0 1 1 (= 3)
Ü 1 1 1
---------
1 0 0 0 (= 8)
- Halbaddierer: addiert zwei Bits. Summe (XOR-Gatter), Übertrag (UND-Gatter). „Halb“, weil er keinen eingehenden Übertrag verarbeiten kann.
- Volladdierer: addiert drei Bits , , und liefert und . Aufbau: zwei Halbaddierer und ein ODER-Gatter: HA 1 rechnet (ergibt , ), HA 2 rechnet (ergibt , ), dann . Kurz: ist die Summe der drei Bits als Binärzahl.
- Carry-Ripple-Addierer: ein Volladdierer pro Stelle; der ausgehende Übertrag einer Stelle ist der eingehende Übertrag der nächsthöheren Stelle. Ganz rechts ist der Übertrag 0. Der Übertrag „rieselt“ von rechts nach links; jede Stufe wartet auf die vorige. Vier Stellen ergeben bis zu fünf Ergebnisbits.
- Kontrolle mit Python:
int("0101", 2)ergibt 5,bin(8)ergibt'0b1000'.
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)
Kombinatorische Schaltung: Ausgang hängt nur von den aktuellen Eingängen ab (Gatter, Addierer, Alarmanlage).
Flipflop: merkt sich ein Bit; der Ausgang hängt auch von der Vorgeschichte ab. Grundlage schneller Speicher, z. B. Register.
Rückkopplung: Ein Ausgang wird auf einen Eingang der eigenen Schaltung zurückgeführt.
SR-Flipflop: zwei NOR-Gatter (ODER mit Kreis am Ausgang), über Kreuz zurückgekoppelt. Ausgänge und (auch
Q')., : Setzen (). , : Rücksetzen (). , : Speichern ( bleibt wie vorher). : verboten.
In Python ahmt eine Variable die Rückkopplung nach:
q = sr_flipflop(s, r, q).
Typische Fehler: bei einfach 0 eintragen statt den alten Wert; und vertauschen.
2.9.4Aussagenlogik und Termbäume (Abschnitt 2.6)
| Name | Zeichen | Gatter | Python |
|---|---|---|---|
| Negation | NICHT | not a |
|
| Konjunktion | UND | a and b |
|
| Disjunktion | ODER | a or b |
- Induktive Definition: (1) Jede Aussagenvariable ist ein Term. (2) Ist ein Term, dann auch . (3) Sind , Terme, dann auch und . (4) Nichts anderes ist ein Term.
- Termbaum: Blätter = Variablen, innere Knoten = Operatoren, Wurzel = Operator, der zuletzt ausgewertet wird. Beispiel : Wurzel , darunter (mit , ) und (mit ).
- Term ↔︎ Schaltung: Jeder innere Knoten ist ein Gatter ( UND, ODER, NICHT), die Blätter sind die Eingänge, die Wurzel ist das letzte Gatter. Was in einer Klammer steht, rechnet ein eigenes Gatter zuerst.
Typische Fehler: und verwechseln (das gilt nur für das, was direkt dahinter steht); die falsche Wurzel wählen; in einen Term schreiben (gehört nicht zu den Regeln).
2.9.5Äquivalenz und DNF (Abschnitt 2.7)
- Äquivalent: Zwei Terme liefern für jede Belegung denselben Wert, haben also dieselbe Belegungstabelle. Äquivalenz ist ein Begriff über Terme, kein Operator. Für „nicht äquivalent“ genügt eine Belegung, in der sie sich unterscheiden.
- Beispiel (De Morgan): ist äquivalent zu , aber nicht zu .
- Minterm: Konjunktion aller Variablen; eine Variable mit dem Wert 0 bekommt ein . Zur Zeile , , gehört .
- DNF: Minterme aller Zeilen mit Ausgang 1, verbunden mit . Beispiel XOR: Einsen bei und , DNF .
- Äquivalenz mit Python prüfen: beide Terme als Funktionen schreiben,
aequivalent = Truesetzen, in geschachtelten Schleifen alle Belegungen vergleichen und bei!=aufFalsesetzen.
Typische Fehler: an die Variablen mit Wert 1 setzen; eine Variable im Minterm vergessen; Zeilen mit Ausgang 0 verwenden; und vertauschen.
2.9.6KV-Diagramme (Abschnitt 2.8)
- KV-Diagramm: alle Belegungen in einem Raster, Spalten (und bei vier Variablen auch Zeilen) in der Reihenfolge 00, 01, 11, 10. Benachbarte Felder unterscheiden sich in genau einer Variablen.
- Benachbarte Einsen zu Blöcken zusammenfassen: Rechtecke aus 1, 2, 4 oder 8 Feldern, nur Einsen, so groß und so wenige wie möglich; Überlappen ist erlaubt; jede 1 liegt in einem Block.
- Term eines Blocks: nur die Variablen, die im ganzen Block konstant sind (mit bei 0). Alle Blockterme mit verbinden. Ergebnis: minimierte DNF, äquivalent zur DNF, aber mit weniger Gattern.
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)
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 und Übertrag |
| 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 : nur wahr, wenn beide wahr sind |
| Disjunktion | ODER-Verknüpfung : wahr, wenn mindestens einer wahr ist |
| Negation | NICHT : 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 | ist äquivalent zu ; ist äquivalent zu |
| 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. |