Die beiden Gesetze
Die Gesetze von De Morgan beschreiben, wie sich Negation über AND und OR verteilt:
- ¬(A·B) = ¬A + ¬B — die Negation eines AND ist das OR der Negationen.
- ¬(A+B) = ¬A · ¬B — die Negation eines OR ist das AND der Negationen.
Warum das in der Hardware wichtig ist
NAND- und NOR-Gatter sind in CMOS-Technologie günstiger herzustellen als AND/OR-Gatter, und jede Boolesche Funktion lässt sich allein aus NAND-Gattern (oder allein aus NOR-Gattern) aufbauen. Die Gesetze von De Morgan sind das Werkzeug, mit dem ein AND/OR/NOT-Ausdruck in ein äquivalentes reines NAND- oder NOR-Netzwerk umgeschrieben werden kann.
Zum Beispiel ist A·B dasselbe wie ¬(¬A+¬B) — eine nützliche Identität, wenn nur NOR-Gatter verfügbar sind oder ein Fertigungsprozess NOR-Gatter deutlich schneller macht als AND-Gatter.
Ein Beispiel
Nehmen wir den Ausdruck ¬(A·B + C). Zunächst wenden wir das Gesetz von De Morgan auf die äußere Negation an:
- ¬(A·B + C) = ¬(A·B) · ¬C
- Das Gesetz noch einmal auf ¬(A·B) anwenden: = (¬A + ¬B) · ¬C
Selbst ausprobieren
Bauen Sie beide Versionen eines Ausdrucks — die ursprüngliche und die nach De Morgan transformierte — im Schaltungseditor, prüfen Sie dann mit dem Werkzeug „Prüfung“, dass keine offenen Ausgänge oder unverbundenen Eingänge vorhanden sind, und mit der Wahrheitstabelle, dass beide Versionen identische Ergebnisse liefern.