Zum Inhalt springen
Zurück zur Themenübersicht

Technische Informatik

Logische Grundbausteine: AND, OR, NOT, XOR, NAND, NOR

Sechs Bausteine, aus denen sich jede Schaltung bauen lässt, und die Tabelle, die jede Frage über sie beantwortet.

Benötigte Grundlagen

Dieses Vorwissen brauchst du für das Kapitel. Schau kurz nach, wenn dir etwas davon nicht mehr präsent ist, sonst leg direkt los.

Einführung

Ein Auto piept, wenn die Zündung an ist und der Gurt nicht angelegt ist. Ein Treppenhauslicht schaltet um, egal welchen der beiden Schalter man drückt. Eine Alarmanlage schlägt an, wenn Fenster oder Tür geöffnet werden.

Jede dieser Regeln lässt sich mit einer Handvoll Bausteinen bauen, und es sind immer dieselben. In diesem Kapitel lernst du sie kennen, und du wirst sehen, dass zwei davon eine überraschende Eigenschaft haben: Mit einem einzigen von ihnen lässt sich alles andere nachbauen.

Das kannst du nach diesem Kapitel

  • die Gatter AND, OR, NOT, XOR, NAND und NOR benennen und ihre Wirkung erklären.

  • für jedes Gatter die Schaltbelegungstabelle aufstellen.

  • eine Schaltung aus mehreren Gattern analysieren und ihre Tabelle bestimmen.

  • eine Alltagsregel in eine Schaltung übersetzen.

  • begründen, warum NAND allein genügt, um alle anderen Gatter nachzubauen.

Woher die Bausteine kommen

Im Kapitel zur hast du gesehen, dass ein Rechner nur zwei kennt: 0 und 1. Was er damit tut, sind Verknüpfungen: Aus einem oder zwei Eingangswerten wird ein Ausgangswert berechnet.

Ein Bauteil, das genau eine solche Verknüpfung ausführt, heißt Gatter (englisch gate). Sein Verhalten schreibt man vollständig in einer Schaltbelegungstabelle auf, die jede mögliche Eingabekombination und den zugehörigen Ausgang enthält.

Bei zwei Eingängen gibt es 22=42^2 = 4 Kombinationen, also vier Zeilen. Diese Zahl kennst du: Es ist dieselbe Zweierpotenz wie bei den Bitmustern.

Die drei Grundgatter

NOT (Negation, „nicht“) hat einen Eingang und dreht ihn um.

ANOT A
01
10

AND (Konjunktion, „und“) liefert genau dann 1, wenn beide Eingänge 1 sind.

ABA AND B
000
010
100
111

OR (Disjunktion, „oder“) liefert 1, wenn mindestens ein Eingang 1 ist.

ABA OR B
000
011
101
111

🔴 Beachte die letzte Zeile des OR: Auch wenn beide 1 sind, ist das Ergebnis 1. Das umgangssprachliche „oder“ meint oft „entweder das eine oder das andere, aber nicht beides“; das logische OR meint „mindestens eines“. Für das ausschließende Oder gibt es ein eigenes Gatter.

Die drei Grundgatter

ab&ybeideab≥1yeins reichta1ydreht um

Drei Bausteine, und mit ihnen lässt sich jede logische Verknüpfung bauen. Das Zeichen im Kasten ist die eigentliche Definition: & verlangt beide Eingänge, ≥1 mindestens einen, die 1 mit dem Kringel am Ausgang dreht um. Der kleine Kreis ist dabei nicht Verzierung, sondern bedeutet immer „und dann verneint“, du wirst ihn gleich bei NAND und NOR wiedersehen.

XOR: das ausschließende Oder

XOR liefert 1, wenn die Eingänge verschieden sind.

ABA XOR B
000
011
101
110

Man kann es sich als „Ungleichheitsprüfer“ merken: Ausgang 1 bedeutet „die beiden sind verschieden“.

Das Treppenhauslicht ist genau ein XOR: Betätigt man einen der beiden Schalter, ändert sich der ; betätigt man beide, ist man wieder am Anfang.

OR und XOR nebeneinander

aba OR ba XOR b0000011110111110

Beide Spalten stehen absichtlich nebeneinander, denn sie unterscheiden sich in genau einer Zeile, der hervorgehobenen letzten. Sind beide Eingänge 11, sagt OR weiterhin 11 („mindestens eines“), XOR dagegen 00 („genau eines“). In den ersten drei Zeilen sind sie nicht zu unterscheiden, und daher rührt die Verwechslung: Wer nur bis Zeile 3 prüft, hält die beiden für dasselbe Gatter.

NAND und NOR: die Verneinungen

NAND ist „nicht und“, also ein AND mit nachgeschaltetem NOT.

ABA NAND B
001
011
101
110

NOR ist „nicht oder“.

ABA NOR B
001
010
100
110

Beide Tabellen entstehen, indem man die Ausgangsspalte von AND beziehungsweise OR umdreht. Man muss sie also nicht auswendig lernen.

NAND und NOR

ab&ynicht beideab≥1yweder noch

Dieselben Zeichen wie bei AND und OR, nur mit dem Kringel am Ausgang, mehr ist der Unterschied nicht. NAND ist also wörtlich „AND, danach verneint“, NOR ist „OR, danach verneint“. Deshalb muss man ihre Wahrheitstabellen auch nicht auswendig lernen: Man schreibt die von AND beziehungsweise OR hin und dreht jede Zeile des Ergebnisses um.

Warum NAND besonders ist

Jetzt kommt der bemerkenswerte Teil. Aus NAND allein lassen sich alle anderen Gatter bauen.

NOT aus NAND: Man legt denselben Wert an beide Eingänge.

NOT A=A NAND A\text{NOT } A = A \text{ NAND } A

Probe: Bei A=0A = 0 liefert NAND(0,0) den Wert 1. Bei A=1A = 1 liefert NAND(1,1) den Wert 0. Genau die NOT-Tabelle.

AND aus NAND: NAND ist ein verneintes AND, also verneint man es noch einmal.

A AND B=NOT(A NAND B)=(A NAND B) NAND (A NAND B)A \text{ AND } B = \text{NOT}(A \text{ NAND } B) = (A \text{ NAND } B) \text{ NAND } (A \text{ NAND } B)

OR aus NAND: Man verneint beide Eingänge und verknüpft sie mit NAND.

A OR B=(A NAND A) NAND (B NAND B)A \text{ OR } B = (A \text{ NAND } A) \text{ NAND } (B \text{ NAND } B)

Probe für A=0,B=1A = 0, B = 1: Links steht NAND(0,0) = 1, rechts NAND(1,1) = 0, zusammen NAND(1,0) = 1. Und OR(0,1) ist ebenfalls 1.

Warum ist das nützlich? Weil eine Fabrik dann einen einzigen Bautyp herstellen muss statt sechs. Das senkt Kosten, vereinfacht die Fertigung und macht Schaltungen gleichmäßiger. Gatter mit dieser Eigenschaft nennt man vollständig; NOR ist ebenfalls vollständig, AND allein dagegen nicht, weil man aus lauter AND-Bausteinen nie eine Verneinung erzeugen kann.

Schaltungen analysieren

Werden mehrere Gatter hintereinandergeschaltet, bestimmt man das Verhalten, indem man eine Tabelle mit Zwischenspalten anlegt und von links nach rechts rechnet.

Beispiel: Y=(A AND B) OR (NOT C)Y = (A \text{ AND } B) \text{ OR } (\text{NOT } C)

ABCA AND BNOT CY
000011
001000
010011
011000
100011
101000
110111
111101

Bei drei Eingängen sind es 23=82^3 = 8 Zeilen. Die Eingangsspalten füllt man systematisch: Die rechte Spalte wechselt in jeder Zeile, die mittlere alle zwei, die linke alle vier. So kann keine Kombination fehlen und keine doppelt vorkommen.

XOR aus drei Grundgattern

aba ∧ b&a ∨ b≥1&y

Diese Schaltung ist genau das XOR von vorhin, nachgebaut aus den drei Grundgattern. Als Formel: y=(alorb)landlnot(alandb)y = (a lor b) land lnot(a land b), das obere AND liefert alandba land b, das OR darunter alorba lor b, und der Kringel am Eingang des rechten Gatters negiert den ersten Teil. Rechne sie zeilenweise durch: Bei a=1a = 1, b=1b = 1 liefert das obere AND eine 11, der Kringel am unteren Eingang macht daraus eine 00, und 1∧0=01 \land 0 = 0. Bei a=1a = 1, b=0b = 0 dagegen liefert OR eine 11, AND eine 00, der Kringel daraus eine 11 und 1∧1=11 \land 1 = 1. Vergleiche die vier Fälle mit der Tabelle: Es ist dieselbe Spalte.

Von der Regel zur Schaltung

Der umgekehrte Weg ist der praktisch wichtigere. Man übersetzt den Satz Wort für Wort:

  • „und“ wird zu AND
  • „oder“ (im Sinne von mindestens eines) wird zu OR
  • „nicht“ wird zu NOT
  • „entweder oder, aber nicht beides“ wird zu XOR

Beispiel Gurtwarnung: „Es piept, wenn die Zündung an ist und der Gurt nicht angelegt ist.“

Piep=Zuendung AND (NOT Gurt)\text{Piep} = \text{Zuendung} \text{ AND } (\text{NOT } \text{Gurt})

Die Probe macht man mit der Tabelle: Bei Zündung 1 und Gurt 0 ergibt sich 1 AND 1=11 \text{ AND } 1 = 1, es piept. Bei Zündung 1 und Gurt 1 ergibt sich 1 AND 0=01 \text{ AND } 0 = 0, es ist still. Bei ausgeschalteter Zündung ist es in beiden Fällen still. Genau so soll es sein.

Eine Alltagsregel übersetzen

Ein Rasenmähroboter soll nur fahren, wenn er genug Akku hat und es nicht regnet und kein Hindernis erkannt wird. Stelle die Schaltung und die Tabelle auf.

  1. 1

    Eingänge benennen: A = Akku voll, R = Regen, H = Hindernis. Jeder ist 1, wenn die Aussage zutrifft.

  2. 2

    Wort für Wort übersetzen: „genug Akku“ ist A. „nicht regnet“ ist NOT R. „kein Hindernis“ ist NOT H. Die drei sind mit „und“ verbunden.

  3. 3
    Fahren=A AND (NOT R) AND (NOT H)\text{Fahren} = A \text{ AND } (\text{NOT } R) \text{ AND } (\text{NOT } H)
  4. 4

    Tabelle mit 23=82^3 = 8 Zeilen:

    ARHNOT RNOT HFahren
    000110
    001100
    010010
    011000
    100111
    101100
    110010
    111000
  5. 5

    Probe: Genau eine Zeile liefert 1, nämlich Akku voll, kein Regen, kein Hindernis. Das ist ein gutes Zeichen: Eine Regel mit lauter „und“ trifft immer nur auf genau eine Kombination zu.

Fahren=A AND (NOT R) AND (NOT H)\text{Fahren} = A \text{ AND } (\text{NOT } R) \text{ AND } (\text{NOT } H), mit genau einer 1 in der Tabelle.

NOT und AND aus NAND bauen

Zeige durch vollständige Tabellen, dass A NAND AA \text{ NAND } A dasselbe liefert wie NOT A\text{NOT } A, und dass (A NAND B) NAND (A NAND B)(A \text{ NAND } B) \text{ NAND } (A \text{ NAND } B) dasselbe liefert wie A AND BA \text{ AND } B.

  1. 1

    NOT aus NAND: Man legt beide Eingänge auf denselben Wert.

    AA NAND ANOT A
    011
    100

    Die beiden rechten Spalten sind gleich, also stimmen die Gatter überein.

  2. 2

    Warum funktioniert das? NAND liefert nur bei zwei Einsen eine 0. Legt man denselben Wert an, gibt es nur die Fälle (0,0) und (1,1), und deren Ausgänge sind 1 und 0. Genau die NOT-Tabelle.

  3. 3

    AND aus NAND: NAND ist ein verneintes AND, also verneint man noch einmal, und die Verneinung baut man wieder aus NAND.

    ABA NAND BErgebnisA AND B
    00100
    01100
    10100
    11011
  4. 4

    Die Spalte „Ergebnis“ entsteht, indem man die Spalte davor mit sich selbst durch NAND verknüpft, also verneint. Sie stimmt mit AND überein.

  5. 5

    Damit ist gezeigt: Wer NAND hat, hat NOT und AND. Und weil sich OR aus AND und NOT bauen lässt, hat er auch OR. Ein einziger Bautyp genügt.

Beide Nachbauten stimmen zeilenweise überein. NAND ist deshalb vollständig.

Typischer Fehler

„Bei 1 OR 11 \text{ OR } 1 kommt 0 heraus, weil man ja nur eines von beiden nehmen kann.“

Hier wird das umgangssprachliche „oder“ auf das logische übertragen, und die beiden bedeuten Verschiedenes.

Im Alltag ist „Kuchen oder Eis“ meist ausschließend gemeint: eines von beiden, nicht beides. Das logische OR bedeutet dagegen mindestens eines, und damit ist beides ausdrücklich eingeschlossen. Deshalb gilt 1 OR 1=11 \text{ OR } 1 = 1.

Für die ausschließende Bedeutung gibt es ein eigenes Gatter, XOR, und genau dort ist 1 XOR 1=01 \text{ XOR } 1 = 0.

Die Verwechslung fällt in Aufgaben sofort auf, weil sie nur die letzte Zeile der Tabelle betrifft; die ersten drei Zeilen sind bei OR und XOR gleich. Wer sich unsicher ist, prüft deshalb immer den Fall, in dem beide Eingänge 1 sind. Er ist der einzige, der die beiden Gatter unterscheidet.

Ein Merksatz hilft: OR fragt „mindestens einer?“, XOR fragt „genau einer?“

Übung 1

leicht

Bestimme die Ausgänge:

a) 1 AND 01 \text{ AND } 0 b) 1 OR 11 \text{ OR } 1 c) NOT 0\text{NOT } 0 d) 1 XOR 11 \text{ XOR } 1 e) 0 NAND 00 \text{ NAND } 0 f) 1 NOR 01 \text{ NOR } 0

Tipp anzeigen

NAND und NOR sind AND und OR mit umgedrehtem Ausgang.

Lösung anzeigen

a) 0 (AND braucht beide 1) b) 1 (OR heißt mindestens eines) c) 1 d) 0 (XOR ist 1 nur bei verschiedenen Eingängen) e) 1 (AND wäre 0, NAND dreht das um) f) 0 (OR wäre 1, NOR dreht das um)

Detaillierte Schritterklärung anzeigen

Hier wird jeder Schritt einzeln erklärt, vor allem, warum er gemacht wird.

Erklärungstiefe

✦ Empfohlen: Standard – Die normale Erklärungstiefe passt zum Einstieg.

  1. 1

    Jedes Gatter als einen Satz merken

    Statt sechs Tabellen auswendig zu lernen, genügt je Gatter ein Satz: AND, nur wenn beide 1 sind. OR, wenn mindestens eines 1 ist. NOT, dreht um. XOR, nur wenn die Eingänge verschieden sind.

  2. 2

    a) bis d): die vier Grundgatter anwenden

    1 AND 01 \text{ AND } 0 ist 0, denn AND braucht beide. 1 OR 11 \text{ OR } 1 ist 1, mindestens eines genügt. NOT 0\text{NOT } 0 ist 1. 1 XOR 11 \text{ XOR } 1 ist 0, denn die Eingänge sind gleich.

  3. 3

    e) und f): NAND und NOR sind AND und OR mit umgedrehtem Ausgang

    Man rechnet in zwei Schritten. 0 AND 00 \text{ AND } 0 ist 0, NAND dreht das um: 1. 1 OR 01 \text{ OR } 0 ist 1, NOR dreht das um: 0. Das kleine N vorn bedeutet immer „und dann NOT“.

Übung 2

mittel

Eine Alarmanlage soll auslösen, wenn die Anlage scharf geschaltet ist und entweder das Fenster oder die Tür geöffnet wird.

a) Benenne die Eingänge und stelle die logische Verknüpfung auf. b) Erstelle die vollständige Schaltbelegungstabelle. c) In wie vielen Zeilen löst der Alarm aus? d) Wie ändert sich die Tabelle, wenn nur bei genau einer geöffneten Öffnung Alarm gegeben werden soll?

Tipp anzeigen

Zu a): „entweder Fenster oder Tür“ ist hier im Sinne von „mindestens eines“ gemeint.

Lösung anzeigen

a) Eingänge: S = scharf geschaltet, F = Fenster offen, T = Tür offen.

Alarm=S AND (F OR T)\text{Alarm} = S \text{ AND } (F \text{ OR } T)

b) Tabelle mit 23=82^3 = 8 Zeilen:

SFTF OR TAlarm
00000
00110
01010
01110
10000
10111
11011
11111

c) In drei Zeilen. Alle drei haben S = 1 und mindestens eine geöffnete Stelle.

d) Dann wird aus dem OR ein XOR: Alarm=S AND (F XOR T)\text{Alarm} = S \text{ AND } (F \text{ XOR } T). In der Tabelle ändert sich genau eine Zeile, die letzte: Bei S = 1, F = 1, T = 1 ist der Alarm dann 0. Praktisch wäre diese Variante allerdings unsinnig, denn bei zwei offenen Zugängen sollte erst recht Alarm geschlagen werden. Das zeigt, dass die Wahl zwischen OR und XOR eine inhaltliche Entscheidung ist und keine sprachliche Feinheit.

Detaillierte Schritterklärung anzeigen

Hier wird jeder Schritt einzeln erklärt, vor allem, warum er gemacht wird.

Erklärungstiefe

✦ Empfohlen: Standard – Die normale Erklärungstiefe passt zum Einstieg.

  1. 1

    Teil a): Eingänge festlegen und benennen

    Zuerst wird jede Bedingung zu einem eigenen Eingang mit klarer Bedeutung: 1 heißt „trifft zu“. Diese Festlegung muss man aufschreiben, sonst rechnet man später mit vertauschten Bedeutungen.

    Zwischenergebnis

    S = scharf, F = Fenster offen, T = Tür offen. Jeweils 1 = ja.

    Achte auf Verneinungen im Aufgabentext. „Fenster geschlossen“ als Eingang zu nehmen würde die ganze Tabelle umdrehen.

  2. 2

    Teil a): den Satz Wort für Wort übersetzen

    „scharf geschaltet und (Fenster oder Tür)“ wird direkt zu AND und OR. Die Klammer ist wichtig: Ohne sie würde die Rangfolge der Operatoren die Bedeutung verändern.

    \text{Alarm} = S \text{ AND } (F \text{ OR } T)

    Zwischenergebnis

    Die Verknüpfung steht.

  3. 3

    Teil b): die Tabelle systematisch füllen

    Bei drei Eingängen sind es acht Zeilen. Die Eingangsspalten werden nach festem Muster gefüllt, dann kommt eine Zwischenspalte für die Klammer, erst danach die Ergebnisspalte.

    2^3 = 8\ \text{Zeilen}

    Zwischenergebnis

    Zwischenspalte F OR T, danach Alarm = S AND (F OR T).

  4. 4

    Teil d): OR gegen XOR abwägen

    Der Unterschied betrifft nur die Zeile, in der beide Öffnungen offen sind. Bei OR bleibt der Alarm dort an, bei XOR fällt er aus.

    Zwischenergebnis

    Genau eine Zeile ändert sich, die letzte.

    Hier lohnt der Blick über die Technik hinaus: Die XOR-Variante wäre formal korrekt und praktisch gefährlich. Eine richtige Tabelle ist noch keine sinnvolle Regel.

Übung 3

schwer

a) Bestimme die vollständige Tabelle von Y=(A XOR B) AND (NOT C)Y = (A \text{ XOR } B) \text{ AND } (\text{NOT } C). b) Zeige durch eine Tabelle, dass A OR BA \text{ OR } B und (A NAND A) NAND (B NAND B)(A \text{ NAND } A) \text{ NAND } (B \text{ NAND } B) dasselbe liefern. c) Begründe, warum man aus lauter AND-Gattern allein niemals ein NOT bauen kann. d) Ein Treppenhaus hat drei Schalter; jeder soll das Licht umschalten können. Welche Verknüpfung leistet das, und warum?

Tipp anzeigen

Zu c): Was passiert bei AND, wenn alle Eingänge 0 sind?

Lösung anzeigen

a) Tabelle:

ABCA XOR BNOT CY
000010
001000
010111
011100
100111
101100
110010
111000

b) Tabelle:

ABA NAND AB NAND BErgebnisA OR B
001100
011011
100111
110011

Die letzten beiden Spalten stimmen zeilenweise überein.

c) Ein AND-Gatter liefert bei lauter Nullen am Eingang immer eine 0. Setzt man nur AND-Gatter zusammen, bleibt diese Eigenschaft erhalten: Legt man an alle Eingänge der Schaltung 0 an, ist jeder Zwischenwert 0 und damit auch der Ausgang. Ein NOT müsste aus 0 aber eine 1 machen. Also kann keine reine AND-Schaltung ein NOT sein. AND ist deshalb nicht vollständig, NAND dagegen schon.

d) Ein XOR über drei Eingänge, also S1 XOR S2 XOR S3S_1 \text{ XOR } S_2 \text{ XOR } S_3. Der Grund: XOR liefert genau dann 1, wenn eine ungerade Anzahl der Eingänge 1 ist. Betätigt man einen beliebigen Schalter, ändert sich dessen Wert, damit ändert sich die Anzahl der Einsen um genau eins und die Antwort auf die Frage „ungerade?“ kippt. Also schaltet jeder Schalter das Licht um, unabhängig von der Stellung der anderen. Genau das ist die Anforderung.

Detaillierte Schritterklärung anzeigen

Hier wird jeder Schritt einzeln erklärt, vor allem, warum er gemacht wird.

Erklärungstiefe

✦ Empfohlen: Standard – Die normale Erklärungstiefe passt zum Einstieg.

  1. 1

    a) Die Tabelle in Zwischenspalten zerlegen statt im Kopf zu rechnen

    Bei drei gibt es 23=82^3 = 8 Zeilen. Man legt Zwischenspalten an: erst A XOR BA \text{ XOR } B, dann NOT C\text{NOT } C, dann das AND aus beiden. Damit wird jede Zeile eine einfache Ablesung statt einer Kopfrechnung.

    23=82^3 = 8 Zeilen; Y=1Y = 1 nur bei (0,1,0)(0,1,0) und (1,0,0)(1,0,0)

  2. 2

    b) Zwei Ausdrücke durch spaltenweisen Vergleich als gleich nachweisen

    Man baut eine Tabelle mit beiden Ausdrücken und vergleicht die Ergebnisspalten zeilenweise. A NAND AA \text{ NAND } A ist NOT A\text{NOT } A, ebenso für B; das äußere NAND verknüpft die beiden Negationen. In allen vier Zeilen stimmt das Ergebnis mit A OR BA \text{ OR } B überein.

  3. 3

    c) Warum aus lauter AND kein NOT wird

    Ein AND-Gatter liefert bei lauter Nullen am Eingang immer eine 0. Setzt man nur AND-Gatter zusammen, bleibt diese Eigenschaft erhalten: Legt man an alle Eingänge 0 an, ist jeder Zwischenwert 0 und damit auch der Ausgang. Ein NOT müsste aus 0 aber eine 1 machen. Also kann keine reine AND-Schaltung ein NOT sein.

  4. 4

    d) Das Treppenhaus: XOR zählt die Ungeradheit

    Ein XOR über drei Eingänge, also S1 XOR S2 XOR S3S_1 \text{ XOR } S_2 \text{ XOR } S_3. Der Grund: XOR liefert genau dann 1, wenn eine ungerade Anzahl der Eingänge 1 ist. Betätigt man einen beliebigen Schalter, ändert sich dessen Wert, damit die Anzahl der Einsen um genau eins und die Antwort auf „ungerade?“ kippt.

Zusammenfassung

Ein Gatter berechnet aus einem oder zwei nach fester Regel ein Ausgangsbit; sein Verhalten steht vollständig in der Schaltbelegungstabelle mit 2n2^n Zeilen. AND liefert 1 nur bei zwei Einsen, OR bei mindestens einer, NOT dreht um, XOR liefert 1 bei verschiedenen Eingängen, und NAND sowie NOR sind AND und OR mit umgedrehter Ausgangsspalte. Der häufigste Fehler liegt in der letzten Zeile: Das logische OR ist auch bei zwei Einsen 1, das ausschließende Oder heißt XOR. Zusammengesetzte Schaltungen analysiert man mit Zwischenspalten von links nach rechts, Alltagsregeln übersetzt man Wort für Wort. NAND ist vollständig, mit ihm allein lassen sich alle übrigen Gatter nachbauen, was in der Fertigung einen einzigen Bautyp genügen lässt; AND allein ist es nicht, weil aus lauter Nullen niemals eine Eins entstehen kann.