Wie wir bereits gesehen haben, verwendet die Boolesche Algebra eine Reihe von Gesetzen und Regeln, um den Betrieb einer digitalen Logikschaltung zu definieren, wobei „0’s“ und „1’s“ verwendet werden, um einen digitalen Eingangs- oder Ausgangszustand darzustellen. Die Boolesche Algebra verwendet diese Nullen und Einsen, um Wahrheitstabellen und mathematische Ausdrücke zu erstellen, um die digitale Operation einer logischen UND-, ODER- und NICHT- (oder Inversions-) Operation zu definieren, sowie Möglichkeiten, andere logische Operationen wie die XOR- (Exklusiv-ODER-) Funktion auszudrücken.
Während George Boole’s Satz von Gesetzen und Regeln uns erlaubt, eine digitale Schaltung zu analysieren und zu vereinfachen, gibt es zwei Gesetze innerhalb seines Satzes, die Augustus DeMorgan (einem englischen Mathematiker des neunzehnten Jahrhunderts) zugeschrieben werden, der die logischen NAND- und NOR-Operationen als separate NICHT UND- bzw. NICHT ODER-Funktionen betrachtet.
Aber bevor wir uns DeMorgans Theorie genauer ansehen, wollen wir uns an die grundlegenden logischen Operationen erinnern, bei denen A und B logische (oder boolesche) binäre Eingangsvariablen sind, deren Werte nur entweder „0“ oder „1“ sein können, wodurch sich vier mögliche Eingangskombinationen ergeben: 00, 01, 10 und 11.
Wahrheitstabelle für jede logische Operation
| Eingangsvariable | Ausgangsbedingungen | ||||||
| A | B | AND | NAND | OR | NOR | ||
| 0 | 0 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 1 | 0 |
| 1 | 0 | 0 | 1 | 1 | 0 | ||
| 1 | 1 | 1 | 0 | 1 | 0 | ||
Die folgende Tabelle enthält eine Liste der gängigen Logikfunktionen und ihrer äquivalenten booleschen Schreibweise, wobei ein „.“ (ein Punkt) eine UND-Verknüpfung (Produkt) bedeutet, ein „+“ (Pluszeichen) eine ODER-Verknüpfung (Summe) bedeutet und das Komplement oder die Umkehrung einer Variablen durch einen Balken über der Variablen angezeigt wird.
| Logische Funktion | Boolesche Schreibweise |
| AND | A.B |
| OR | A+B |
| NOT | A | NAND | A .B |
| NOR | A+B |
DeMorgan’s Theorie
DeMorgan’s Theoreme sind im Grunde zwei Sätze von Regeln oder Gesetzen, die aus den booleschen Ausdrücken für AND, OR und NOT unter Verwendung von zwei Eingangsvariablen, A und B. Diese beiden Regeln oder Theoreme erlauben es, die Eingangsvariablen zu negieren und von einer Form einer booleschen Funktion in eine entgegengesetzte Form umzuwandeln.
DeMorgans erstes Theorem besagt, dass zwei (oder mehr) Variablen NOR’ed zusammen dasselbe sind wie die beiden Variablen invertiert (Komplement) und AND’ed, während das zweite Theorem besagt, dass zwei (oder mehr) Variablen NAND’ed zusammen dasselbe sind wie die beiden Terme invertiert (Komplement) und OR’ed. Das heißt, man ersetzt alle ODER-Operatoren durch UND-Operatoren oder alle UND-Operatoren durch einen ODER-Operator.
DeMorgan’s First Theorem
DeMorgan’s First Theorem beweist, dass, wenn zwei (oder mehr) Eingangsvariablen UND-verknüpft und negiert werden, sie äquivalent zum ODER der Komplemente der einzelnen Variablen sind. Somit ist das Äquivalent der NAND-Funktion eine negative ODER-Funktion, was beweist, dass A.B = A+B. Wir können diese Operation anhand der folgenden Tabelle zeigen.
Überprüfung des Ersten Satzes von DeMorgan mit Hilfe der Wahrheitstabelle
| Eingänge | Ausgaben der Wahrheitstabelle für jeden Begriff | ||||||
| B | A | A.B | A.B | A | B | A + B | |
| 0 | 0 | 0 | 1 | 1 | 1 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 1 |
| 1 | 0 | 0 | 1 | 1 | 0 | 1 | 1 | 1 | 0 | 0 | 0 | 0 |
Wir können auch zeigen, dass A.B = A+B mit Hilfe von Logikgattern wie gezeigt.
DeMorgans erstes Gesetz Implementierung mit Logikgattern
Die obere Logikgatteranordnung von: A.B kann mit einem Standard-NAND-Gatter mit den Eingängen A und B realisiert werden. Die untere Logikgatter-Anordnung invertiert zunächst die beiden Eingänge, die A und B ergeben. Diese werden dann zu den Eingängen des ODER-Gatters. Der Ausgang des ODER-Gatters ist somit: A+B
Wir sehen hier, dass eine Standard-ODER-Gatterfunktion mit Invertern (NOT-Gattern) an jedem seiner Eingänge einer NAND-Gatterfunktion entspricht. Ein einzelnes NAND-Gatter kann also so dargestellt werden, dass die Äquivalenz eines NAND-Gatters ein negatives ODER ist.
DeMorgans zweiter Satz
DeMorgans zweiter Satz beweist, dass, wenn zwei (oder mehr) Eingangsvariablen ODER-verknüpft und negiert werden, sie äquivalent zum UND der Komplemente der einzelnen Variablen sind. Somit ist das Äquivalent der NOR-Funktion eine Negativ-AND-Funktion, die beweist, dass A+B = A.B ist, und wiederum können wir die Operation mit der folgenden Wahrheitstabelle zeigen.
Überprüfung von DeMorgans zweitem Satz mit Hilfe der Wahrheitstabelle
| Eingaben | Wahrheitstabellenausgaben für jeden Term | ||||||
| B | A | A+B | A+B | A | B | A . B | |
| 0 | 0 | 0 | 1 | 1 | 1 | 1 | |
| 0 | 1 | 1 | 0 | 0 | 1 | 0 | |
| 1 | 0 | 1 | 0 | 1 | 0 | 0 | |
| 1 | 1 | 1 | 0 | 0 | 0 | 0 | |
Wir können auch zeigen, dass A+B = A.B mit Hilfe des folgenden Logikgatter-Beispiels.
DeMorgan’s Second Law Implementation using Logic Gates
Die obere Logikgatter-Anordnung von: A+B kann mit einer Standard-NOR-Gatterfunktion mit den Eingängen A und B realisiert werden. Die untere Logikgatter-Anordnung invertiert zunächst die beiden Eingänge und erzeugt so A und B. Diese werden dann zu den Eingängen des UND-Gatters. Der Ausgang des UND-Gatters ist somit: A.B
Damit sehen wir, dass eine Standard-UND-Gatterfunktion mit Invertern (NICHT-Gattern) an jedem ihrer Eingänge eine äquivalente Ausgangsbedingung zu einer Standard-NOR-Gatterfunktion erzeugt, und ein einzelnes NOR-Gatter kann auf diese Weise dargestellt werden, da die Äquivalenz eines NOR-Gatters ein negatives-AND ist.
Obwohl wir DeMorgan’s Theoreme mit nur zwei Eingangsvariablen A und B verwendet haben, sind sie genauso gültig für die Verwendung mit drei, vier oder mehr Eingangsvariablenausdrücken, zum Beispiel:
Für eine 3-Variablen-Eingabe
A.B.C = A+B+C
und auch
A+B+C = A.B.C
Für eine 4-variable Eingabe
A.B.C.D = A+B+C+D
und auch
A+B+C+D = A.B.C.D
und so weiter.
DeMorgan’s Equivalent Gates
Wir haben hier gesehen, dass wir mit Hilfe von DeMorgan’s Theoremen alle UND (.) Operatoren durch ein ODER (+) ersetzen können und umgekehrt, und dann jeden der Terme oder Variablen im Ausdruck durch Invertierung ergänzen, d.h. 0’s zu 1’s und 1’s zu 0’s, bevor die gesamte Funktion invertiert wird.
Um also das DeMorgan-Äquivalent für ein UND-, NAND-, ODER- oder NOR-Gatter zu erhalten, fügen wir einfach Inverter (NICHT-Gatter) zu allen Ein- und Ausgängen hinzu und ändern ein UND-Symbol in ein ODER-Symbol oder ändern ein ODER-Symbol in ein UND-Symbol, wie in der folgenden Tabelle gezeigt.
DeMorgan’s Equivalent Gates
| Standard Logic Gate | DeMorgan’s Equivalent Gate |
 |
 |
 |
 |
 |
 |
 |
 |
Dann haben wir in diesem Tutorial über DeMorgan’s Thereom gesehen, dass das Komplement von zwei (oder mehr) UND-verknüpften Eingangsvariablen äquivalent zum ODER der Komplemente dieser Variablen ist, und dass das Komplement von zwei (oder mehr) ODER-verknüpften Variablen dem UND der Komplemente der Variablen nach der Definition von DeMorgan äquivalent ist.
