Ein berühmter Mathematiker DeMorgan erfand die beiden wichtigsten Sätze der Booleschen Algebra. Die Sätze von DeMorgan werden zur mathematischen Überprüfung der Äquivalenz der NOR- und negativen UND-Gatter sowie der negativen ODER- und NAND-Gatter verwendet. Diese Theoreme spielen eine wichtige Rolle bei der Lösung verschiedener Ausdrücke der Booleschen Algebra. In der folgenden Tabelle ist die logische Operation für jede Kombination der Eingabevariablen definiert.
| Eingabevariablen | Ausgabebedingung | ||||
|---|---|---|---|---|---|
| A | B | UND | NAND | ODER | NOCH |
| 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 Regeln des De-Morgan-Theorems werden aus den booleschen Ausdrücken für OR, AND und NOT unter Verwendung zweier Eingabevariablen x und y erstellt. Der erste Satz von Demorgan besagt, dass, wenn wir die UND-Verknüpfung zweier Eingangsvariablen und dann die NICHT-Verknüpfung des Ergebnisses durchführen, das Ergebnis dasselbe sein wird wie die ODER-Verknüpfung des Komplements dieser Variablen. Der zweite Satz von DeMorgan besagt, dass, wenn wir die ODER-Verknüpfung zweier Eingabevariablen durchführen und dann die NICHT Wenn Sie das Ergebnis verknüpfen, ist das Ergebnis dasselbe wie bei der UND-Verknüpfung des Komplements dieser Variablen.
De-Morgans erster Satz
Nach dem ersten Satz ist das Komplementergebnis der UND-Verknüpfung gleich der ODER-Verknüpfung des Komplements dieser Variablen. Somit entspricht sie der NAND-Funktion und ist eine negative ODER-Funktion, die beweist, dass (A.B)' = A'+B' ist, und wir können dies anhand der folgenden Tabelle zeigen.
| Eingaben | Ausgabe für jeden Begriff | |||||
|---|---|---|---|---|---|---|
| A | B | A.B | (A.B)' | A' | B' | A'A+B' |
| 0 | 0 | 0 | 1 | 1 | 1 | 1 |
| 0 | 1 | 0 | 1 | 1 | 0 | 1 |
| 1 | 0 | 0 | 1 | 0 | 1 | 1 |
| 1 | 1 | 1 | 0 | 0 | 0 | 0 |
De-Morgans zweiter Satz
Nach dem zweiten Satz ist das Komplementergebnis der ODER-Verknüpfung gleich der UND-Verknüpfung des Komplements dieser Variablen. Somit ist sie das Äquivalent der NOR-Funktion und eine negative UND-Funktion, die beweist, dass (A+B)' = A'.B', und wir können dies anhand der folgenden Wahrheitstabelle zeigen.
| Eingaben | Ausgabe für jeden Begriff | |||||
|---|---|---|---|---|---|---|
| A | B | A+B | (A+B)' | A' | B' | A'.B' |
| 0 | 0 | 0 | 1 | 1 | 1 | 1 |
| 0 | 1 | 1 | 0 | 1 | 0 | 0 |
| 1 | 0 | 1 | 0 | 0 | 1 | 0 |
| 1 | 1 | 1 | 0 | 0 | 0 | 0 |
Nehmen wir einige Beispiele, in denen wir einige Ausdrücke nehmen und die Theoreme von DeMorgan anwenden.
Beispiel 1: (A.B.C)'
(A.B.C)'=A'+B'+C'
Beispiel 2: (A+B+C)'
(A+B+C)'=A'.B'.C
Beispiel 3: ((A+BC')'+D(E+F')')'
Um den Satz von DeMorgan auf diesen Ausdruck anzuwenden, müssen wir den folgenden Ausdrücken folgen:
1) Im vollständigen Ausdruck finden wir zunächst die Terme, auf die wir den Satz von DeMorgan anwenden und jeden Term als einzelne Variable behandeln können.
Also,
2) Als nächstes wenden wir den ersten Satz von DeMorgan an. Also,
3) Als nächstes verwenden wir Regel Nummer 9, d. h. (A=(A')'), um die Doppelbalken zu eliminieren.
4) Als nächstes wenden wir den zweiten Satz von DeMorgan an. Also,
5) Wenden Sie erneut Regel Nr. 9 an, um den Doppelbalken aufzuheben
Nun hat dieser Ausdruck keinen Begriff, auf den wir eine Regel oder einen Satz anwenden können. Das ist also der letzte Ausdruck.
Beispiel 3: (AB'.(A + C))'+ A'B.(A + B + C')'
Prolog-Sprache
