Logik-Grundlagen
Was ist ein NAND-Gatter?
Ein NAND-Gatter stellt genau eine Frage: Sind alle meine Eingänge an? Und dann antwortet es das Gegenteil. Dieser kleine Widerspruchsgeist reicht aus, um jeden Computer zu bauen, den es je gab.
NAND steht für NOT AND, also „nicht UND“. Ein UND-Gatter (AND) gibt nur dann 1 aus, wenn jeder Eingang 1 ist. Ein NAND-Gatter macht dieselbe Prüfung und dreht das Ergebnis um: Sein Ausgang ist nur dann 0, wenn alle Eingänge 1 sind – in jedem anderen Fall ist er 1.
Die Wahrheitstabelle des NAND-Gatters
Eine Wahrheitstabelle listet jede Kombination der Eingänge auf und daneben den jeweiligen Ausgang. Bei zwei Eingängen sind das vier Zeilen:
| A | B | A NAND B |
|---|---|---|
| 0 | 0 | 1 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 0 |
Vergleich das mit UND: Dort steht nur in der untersten Zeile eine 1. Beim NAND ist dieselbe Spalte umgedreht – drei Einsen und eine einzige 0. Ein NAND mit drei oder vier Eingängen folgt derselben Regel: Es gibt nur dann 0 aus, wenn alle Eingänge 1 sind.
Schaltzeichen und Schreibweise
Das NAND-Symbol ist das UND-Symbol mit einem kleinen Kreis am Ausgang, dem Negationskreis. In den rechteckigen Schaltzeichen nach IEC bzw. DIN EN 60617, wie sie in den meisten deutschen Schulbüchern stehen, ist es ein Kästchen mit & und demselben Kreis am Ausgang.
In der Booleschen Algebra gibt es mehrere Schreibweisen für NAND:
Q = ¬(A ∧ B)oderQ = (A · B)′, oft auch mit Überstrich über A · B: „nicht (A und B)“.Q = A ↑ B: der Sheffer-Strich, benannt nach dem Logiker, der ihn bekannt gemacht hat (mehr zu ihm unten).- Im Code
!(a && b)für Wahrheitswerte oder~(a & b)für alle Bits eines Worts auf einmal.
Eine Eigenschaft stolpert man leicht: NAND ist kommutativ (A ↑ B ist gleich B ↑ A), aber nicht assoziativ. Mit A = 1, B = 1, C = 0 ergibt (A ↑ B) ↑ C eine 1, A ↑ (B ↑ C) aber eine 0. Zwei NAND-Gatter mit je zwei Eingängen hintereinander ergeben also kein NAND mit drei Eingängen. Breitere Gatter brauchen etwas mehr Nachdenken.
Warum ein einziges Gatter genügt
NAND ist ein universelles Gatter. Jede Logikfunktion – ob ein einzelnes Logikgatter, ein Addierer oder die Steuerlogik eines Prozessors – lässt sich allein aus NAND-Gattern bauen, ganz ohne andere Bauteile. Logiker nennen das funktionale Vollständigkeit. Warum NAND jedes andere Gatter bauen kann erklärt, warum das klappt – und warum UND, ODER oder XOR allein es nicht schaffen.
Sein Geschwister NOR ist ebenfalls universell. Die Logik des Apollo Guidance Computer, der zum Mond flog, bestand fast vollständig aus einem einzigen Chiptyp: einem kleinen Baustein mit zwei NOR-Gattern mit je drei Eingängen. Ein einziges Standardteil machte die Maschine viel leichter zu fertigen und zu prüfen.
Warum Chipdesigner NAND mögen
In CMOS, der Technik in fast jedem modernen Chip, sind die invertierenden Gatter die billigsten. Ein NAND mit zwei Eingängen braucht vier Transistoren: Zwei p-Kanal-Transistoren parallel ziehen den Ausgang auf 1, sobald irgendein Eingang 0 ist, und zwei n-Kanal-Transistoren in Reihe ziehen ihn nur dann auf 0, wenn beide Eingänge 1 sind. Ein normales UND ist ein NAND mit nachgeschaltetem Inverter – sechs Transistoren und langsamer. Deshalb sind NAND, NOR und Inverter das tägliche Brot jeder Standardzellen-Bibliothek, und deshalb war der klassische 7400 – vier NAND-Gatter in einem Gehäuse – einer der ersten Bausteine der berühmten 7400er-Logikfamilie von Texas Instruments in den 1960ern.
Ein bisschen Geschichte
1913 veröffentlichte der amerikanische Logiker Henry M. Sheffer einen Aufsatz, der zeigte, dass sich alle Operationen der Booleschen Algebra aus einer einzigen ableiten lassen: dem „Strich“, der heute seinen Namen trägt. Charles Sanders Peirce war um 1880 schon auf dasselbe gekommen, für NAND und NOR, aber seine Notizen erschienen erst Jahrzehnte später. Ein halbes Jahrhundert lang war das eine Kuriosität der Logik. Dann machten Transistoren daraus handfeste Technik: Wenn eine Sorte Gatter alles kann, baust du einen ganzen Computer aus Tausenden Kopien eines einzigen Bauteils.
Was du mit einem NAND anfangen kannst
Allein ist ein NAND eine winzige Entscheidung. Ein paar davon ergeben die anderen Gatter. Ein paar Dutzend ergeben einen Addierer. Führst du den Ausgang eines Gatters auf seine eigenen Eingänge zurück, fängt es an, sich zu erinnern (siehe Flipflops und Speicher). Stapel diese Ideen, und du bekommst eine CPU. Auf dem Weg nach oben kommt nichts Neues dazu. Es ist immer dasselbe Gatter, nur immer geschickter angeordnet.