Was „funktional vollständig" bedeutet
Eine Menge von Gattertypen heißt funktional vollständig, wenn sich mit Gattern ausschließlich aus dieser Menge jede beliebige Boolesche Funktion aufbauen lässt. AND, OR und NOT zusammen sind vollständig, aber keines der drei ist es allein — es braucht immer mindestens zwei der drei. NAND ist die überraschende Ausnahme: ein einziger Gattertyp, mehrfach eingesetzt, genügt, um NOT, AND, OR und jede andere Boolesche Funktion zu bauen. Dasselbe gilt für NOR allein.
NOT, AND und OR allein aus NAND aufbauen
Drei Konstruktionen decken alles ab:
- NOT: dasselbe Signal an beide Eingänge eines NAND-Gatters legen. NAND(A,A) = ¬A.
- AND: ein NAND mit einem zweiten, als NOT verschalteten NAND negieren. AND(A,B) = ¬(NAND(A,B)).
- OR: die Gesetze von De Morgan anwenden — zuerst beide Eingänge negieren (mit dem NOT-Trick), dann das Ergebnis per NAND verknüpfen. OR(A,B) = NAND(¬A,¬B).
Warum die Fertigung einen Gattertyp bevorzugt
In CMOS wird ein NAND-Gatter direkt aus vier Transistoren aufgebaut; ein AND-Gatter sind dieselben vier Transistoren plus zwei weitere, um den Ausgang erneut zu invertieren. NAND und NOR sind daher die physisch einfachsten Gatter zu fertigen, und Standardzellenbibliotheken sind genau darum herum aufgebaut — ein OR-Gatter in einem echten Chip ist intern meist ein NOR gefolgt von einem Inverter, kein eigenes Primitiv. Einen beliebigen Entwurf auf einen einzigen Gattertyp zu reduzieren, vereinfacht zudem die Testmuster in der Fertigung, da sich jede Zelle auf dem Die identisch verhält.
Probieren Sie es selbst
Bauen Sie den Halbaddierer im Schaltungseditor ausschließlich aus NAND-Gattern neu auf — ohne AND, OR oder XOR — und vergleichen Sie dann seine Wahrheitstabelle mit der ursprünglichen Zwei-Gatter-Version, um zu bestätigen, dass beide logisch identisch sind.