DeMorgans Theoreme

Ein Mathematiker namens DeMorgan hat zwei wichtige Regeln zur Gruppenkomplementierung in der Booleschen Algebra entwickelt.

Nach Gruppe Komplementation, ich beziehe mich auf das Komplement einer Gruppe von Begriffen, dargestellt durch einen langen Balken über mehr als einer Variablen.

Sie sollten sich an das Kapitel über Logikgatter erinnern, dass das Invertieren aller Eingänge zu einem Gatter die wesentliche Funktion dieses Gatters von UND zu ODER oder umgekehrt umkehrt und auch den Ausgang invertiert.

Ein ODER-Gatter mit allen invertierten Eingängen (ein negatives ODER-Gatter) verhält sich also genauso wie ein NAND-Gatter, und ein UND-Gatter mit allen invertierten Eingängen (ein negatives UND-Gatter) verhält sich wie ein NOR-Gatter.

Die Theoreme von DeMorgan besagen die gleiche Äquivalenz in „rückwärts“ Form:dass das Invertieren des Ausgangs eines beliebigen Gatters zur gleichen Funktion führt wie der entgegengesetzte Gattertyp (UND vs. ODER) mit invertierten Eingängen:

Ein langer Balken, der sich über den Begriff AB erstreckt, fungiert als Gruppierungssymbol und ist als solches völlig verschieden vom Produkt von A und B unabhängig invertiert.

Mit anderen Worten, (AB)’ ist nicht gleich A’B’. Da das „Prime“-Symbol (’) nicht wie ein Balken über zwei Variablen gestreckt werden kann, sind wir gezwungen, Klammern zu verwenden, damit es auf den gesamten Begriff AB im vorherigen Satz angewendet wird.

Ein Balken fungiert jedoch als eigenes Gruppierungssymbol, wenn er über mehr als eine Variable gedehnt wird.

Dies hat tiefgreifende Auswirkungen darauf, wie boolesche Ausdrücke ausgewertet und reduziert werden, wie wir sehen werden.

Theorem von DeMorgan

Der Satz von DeMorgan kann als Brechen betrachtet werden ein langes Balkensymbol.

Wenn ein langer Balken gebrochen wird, ändert sich die Operation direkt unter dem Bruch von Addition zu Multiplikation oder umgekehrt, und die gebrochenen Balkenstücke bleiben über den einzelnen Variablen. Zur Veranschaulichung:

Wenn in einem Ausdruck mehrere „Schichten“ von Takten vorhanden sind, können Sie nur einen Takt gleichzeitig unterbrechen , und es ist im Allgemeinen einfacher, mit der Vereinfachung zu beginnen, indem man zuerst den längsten (obersten) Balken bricht.

Nehmen wir zur Veranschaulichung den Ausdruck (A + (BC)’)’ und reduzieren ihn mit den DeMorgan’s Theorems:

Dem Rat folgend, den längsten (obersten) Takt zuerst zu brechen, beginne ich damit, den Takt zu brechen, der den gesamten Ausdruck als ersten Schritt abdeckt:

Als Ergebnis wird die ursprüngliche Schaltung auf ein UND-Gatter mit drei Eingängen reduziert, wobei der A-Eingang invertiert ist:

Du solltest nie brechen Sie mehr als einen Balken in einem einzigen Schritt, wie hier dargestellt:

So verlockend es auch sein mag, Schritte zu sparen und mehr als einen Takt gleichzeitig zu brechen, führt oft zu einem falschen Ergebnis, also tu es nicht!

Es ist möglich, diesen Ausdruck richtig zu reduzieren, indem zuerst der kurze Balken und nicht der lange Balken zuerst unterbrochen wird:

Das Endergebnis ist das gleiche, aber es sind mehr Schritte erforderlich als bei der ersten Methode, bei der der längste Balken zuerst gebrochen wurde.

Beachten Sie, wie wir im dritten Schritt die lange Stange an zwei Stellen gebrochen haben.

Dies ist eine legitime mathematische Operation und nicht dasselbe wie das Brechen von zwei Balken in einem Schritt!

Das Verbot, mehr als einen Balken in einem Schritt zu brechen, ist nicht ein Verbot, eine Stange an mehr als einer Stelle zu zerbrechen.

An mehr als einem Ort einbrechen in einem einzigen Schritt ist in Ordnung; mehr als einen Balken brechen in einem Schritt ist das nicht.

Sie fragen sich vielleicht, warum Klammern um den Unterausdruck B’ + C’ gesetzt wurden, wenn man bedenkt, dass ich sie im nächsten Schritt einfach entfernt habe.

Ich tat dies, um einen wichtigen, aber leicht zu vernachlässigenden Aspekt von DeMorgans Theorem hervorzuheben.

Da ein langer Balken als Gruppierungssymbol fungiert, müssen die Variablen, die zuvor durch einen unterbrochenen Balken gruppiert wurden, gruppiert bleiben, damit die richtige Priorität (Operationsreihenfolge) verloren geht.

In diesem Beispiel wäre es wirklich egal, wenn ich vergesse, Klammern einzufügen, nachdem ich den Short-Balken gebrochen habe, aber in anderen Fällen könnte es sein.

Betrachten Sie dieses Beispiel, beginnend mit einem anderen Ausdruck:

Wie Sie sehen, ist es entscheidend, die durch die Komplementierungsbalken für diesen Ausdruck implizierte Gruppierung beizubehalten, um die richtige Antwort zu erhalten.

Wenden wir die Prinzipien der DeMorgan-Theoreme auf die Vereinfachung einer Gate-Schaltung an:

Wie immer muss unser erster Schritt zur Vereinfachung dieser Schaltung darin bestehen, einen äquivalenten booleschen Ausdruck zu generieren.

Wir können dies tun, indem wir am Ausgang jedes Gatters ein Unterausdruckslabel platzieren, wenn die Eingänge bekannt werden. Hier ist der erste Schritt in diesem Prozess:

Als nächstes können wir die Ausgänge des ersten NOR-Gatters und des NAND-Gatters beschriften.

Bei Gattern mit invertiertem Ausgang fällt es mir leichter, einen Ausdruck für den Ausgang des Gatters ohne . zu schreiben die letzte Inversion, wobei ein Pfeil auf kurz vor der Inversionsblase zeigt.

Dann schreibe ich am Draht, der aus dem Tor herausführt (nach der Blase), den vollständigen, ergänzten Ausdruck.

Dies hilft sicherzustellen, dass ich keinen ergänzenden Balken im Unterausdruck vergesse, indem ich mich dazu zwinge, die Aufgabe des Ausdrucksschreibens in zwei Schritte aufzuteilen:

Schließlich schreiben wir einen Ausdruck (oder ein Ausdruckspaar) für das letzte NOR-Gatter:

Nun reduzieren wir diesen Ausdruck unter Verwendung der Identitäten, Eigenschaften, Regeln und Theoreme (DeMorgans) der Booleschen Algebra:

Die äquivalente Gatterschaltung für diesen stark vereinfachten Ausdruck lautet wie folgt:

RÜCKBLICK:

• Die Theoreme von DeMorgan beschreiben die Äquivalenz zwischen Gattern mit invertierten Eingängen und Gattern mit invertierten Ausgängen. Einfach ausgedrückt entspricht ein NAND-Gatter einem Negativ-ODER-Gatter und ein NOR-Gatter entspricht einem Negativ-UND-Gatter.
• Beim „Unterbrechen“ eines Komplementationsbalkens in einem booleschen Ausdruck wird die Operation direkt unter dem Bruch (Addition oder Multiplikation) umgekehrt und die unterbrochenen Balkenstücke bleiben über den jeweiligen Termen.
• Es ist oft einfacher, ein Problem anzugehen, indem man den längsten (obersten) Balken durchbricht, bevor irgendwelche Balken darunter gebrochen werden. Du darfst nie Versuche, zwei Balken in einem Schritt zu brechen!
• Ergänzungsbalken dienen als Gruppierungssymbole. Wenn ein Balken unterbrochen wird, müssen die darunter liegenden Begriffe daher gruppiert bleiben. Diese gruppierten Begriffe können in Klammern gesetzt werden, um eine Änderung der Rangfolge zu vermeiden.

VERWANDTE ARBEITSBLÄTTER:

• Arbeitsblatt zur Booleschen Algebra