Schaltalgebra (Boolsche Algebra)
Wir nehmen an, es soll auf Grund einer verbalen Vorgabe eine Schaltung zu entwerfen sein, die ein vorgegebenes Verhalten zeigen soll.
Der erste Schritt wird es nun sein, eine Wahrheitstabelle aufzustellen und daraus die Formel für jeden der Ausgänge abzuleiten. In vielen Fällen wird der Versuch, die Schaltung zu diesem Zeitpunkt zu zeichnen ein ziemlich kompliziertes Vorgehen sein. Bei komplexen Schaltungen wird dies auch durch probieren in vertretbarer Zeit nicht zu lösen sein.
Hier setzt nun die Schaltalgebra an, mit deren Hilfe man die Fomeln rechnerisch auf die kleinstmögliche Schaltung minimieren kann.
Benannt nach dem englischen Mathematiker Boole wird die boolsche Algebra in der Digital- und Rechnertechnik verwendet.
Ein praktisches Beispiel sehen Sie am Programmbeispiel: Codewandler O´Brian-Code in BCD-Code
Die Schaltalgebra kennt VARIABLE und KONSTANTEN.
Die KONSTANTEN sind 0 und 1 entsprechend der logischen Zustände 0 und 1.
Die Eingänge eines Gatters sind z.B. Variablen, da Sie den Wert 0 und 1 annehmen können. Eine Konstante ist z.B. eine Steckbrücke, die immer den fixen Wert 0 oder 1 liefert.
Die Rechenregeln für die Verknüpfung einer Variablen mit einer Konstanten oder einer Variablen mit sich selbst oder ihrer Negation nennt man Theoreme.
Rechenregeln und Theoreme
Kommutativgesetz und Assoziativgesetz
Kommutativ bedeutet Vertauschung. Somit zeigt uns das Kommutativgesetz die Vertauschbarkeit der Variablen bei der UND- und der ODER-Verknüpfung.
Kommutativgesetz
Die Reihenfolge der Variablen einer UND- bzw. einer ODER-Verknüpfung ist beliebig und hat keinen Einfluss auf das Ergebnis.
Assoziativgesetz
Die Reihenfolge der Zuordnung der Variablen bei der UND- bzw. ODER-Verknüpfung hat keinen Einfluss auf das Ergebnis.
Distributivgesetz
Das Distributivgesetz entspricht dem Ausklammern bzw. Herausheben eines Faktors in der normalen Algebra.
Man unterscheidet das konjunktive und das disjunktive Distributivgesetz.
konjunktives Distributivgesetz
Z = A * (B + C) = (A * B) + (A * C)
Wir verwenden, obwohl veraltet, die einfachere Schreibweise:
-
* entspricht dem UND
-
+ entspricht dem ODER
disjunktives Distributivgesetz
Z = A + (B * C) = (A + B) * (A + C)
Das ganze mit Schaltern dargestellt sieht dann so aus:
Augustus DeMorgan
Der englische Mathematiker Augustus DeMorgan hat diese nach ihm benannten Gesetze gefunden.
Die Gesetze werden verwendet, um Ausdrücke zu vereinfachen bzw. zur Umrechnung von NAND auf NOR oder NOR auf NAND.
Erstes DeMorgansches Gesetz
Das 1. DeMorgansche Gesetz beschreibt die Umwandlung von NAND auf NOR.
Eine UND-Verknüpfung kann durch Auftrennen des Negationsstriches in eine ODER-Verknüpfung umgewandelt werden
Zweites DeMorgansches Gesetz
Das 2. DeMorgansche Gesetz beschreibt die Umwandlung von NOR auf NAND.
Eine ODER-Verknüpfung kann durch Auftrennen des Negationsstriches in eine UND-Verknüpfung umgewandelt werden
Beide Gesetze gelten nicht nur für zwei, sondern für beliebig viele Variablen.
Eine Verknüpfung mehrerer Variablen kann leicht zu Mehrdeutigkeiten führen.
Die Gleichung
Die Gleichung
kann auf zwei Arten interpretiert werden:
a.)
b.)
Die Ergebnisse Z1 und Z2 sind vollkommen verschieden. Um solche Mehrdeutigkeiten zu vermeiden, wurde eine Bindungsregel eingeführt.
Wie die "Punkt vor Strich-Rechnung" der Algebra gilt hier:
UND vor ODER
Eine UND-Verknüpfung bindet stärker als eine ODER-Verknüpfung.
Befindet sich also eine UND- und eine ODER-Verknüpfung ohne Klammern in einer Gleichung, so gilt die UND-Verknüpfung als geklammert. Sollten zwei oder mehr Variablen mit einem Negationsstrich verbunden sein, gilt dies auch als Klammerung.
Um solche Mehrdeutigkeiten zu vermeiden, schreibt man auch:
Die UND-Verknüpfung zwischen A und B wurde weggelassen. Wenn zwischen zwei Variablen keine Verknüpfung steht, ist es immer eine UND-Verknüpfung.
Laut DeMorgan kann jede UND-Verknüpfung mittels ODER- und NICHT-Gattern gebildet werden.
Beispiel:
1. DeMorgansches Gesetz
beides negieren
da sich eine doppelte Negation aufhebt ergibt sich ein NOR mit negierten Eingängen
Daraus folgt, dass ein UND-Gatter nicht erforderlich ist.
Jede Verknüpfungsschaltung kann somit aus ODER- und NICHT-Gattern aufgebaut werden.
Da sogar NICHT-Gatter aus NOR-Gattern bestehen können, nennt man das NOR-Gatter auch Universalgatter mit dem jede gewünschte Verknüpfungsschaltung aufgebaut werden kann.
Aus dem 2. DeMorganschen Gesetz lässt sich ein ODER auch mittels UND und NICHT bilden.
Beispiel:
2. DeMorgansches Gesetz
beides negieren
da sich eine doppelte Negation aufhebt ergibt sich ein NAND mit negierten Eingängen
Daraus folgt, dass ein ODER-Gatter nicht erforderlich ist.
Jede Verknüpfungsschaltung kann somit aus NAND-Gattern aufgebaut werden.
Daher bezeichnet man das NAND-Gatter wie auch das NOR-Gatter als Universalgatter mit dem jede gewünschte Verknüpfungsschaltung aufgebaut werden kann.
Aufgabe:
Die folgende Schaltung soll nur aus NAND-Gattern realisiert werden.
Die Schaltungsgleichung lautet:
der 1. Schritt ist nun, die ganze rechte Seite der Gleichung doppelt zu negieren.
2. der innere Negationsstrich wird aufgetrennt und aus der ODER-Verknüpfung wird eine UND-Verknüpfung.
Voilá, wir haben unsere Gleichung aus lauter NAND-Gatter realisiert.
Ein weiteres Beispiel:
Die folgende Gleichung soll vereinfacht werden.
Hier fällt auf, dass wir am Anfang und am Ende der Gleichung eine ODER-Verknüpfung mit B und B-Nicht haben.
Das ergibt immer 1. (Vergleichbar mit einer Parallelschaltung von zwei Schaltern B. Ein Schalter ist immer geschlossen und einer offen.)
Das ergibt auch 1. Egal wie A, B oder C steht, durch die ODER-Verknüpfung mit der Konstanten 1 ist das Ergebnis immer 1.
Funktionsgleichung zur Schaltung
Anhand der gegebenen Schaltung soll die Funktionsgleichung erstellt werden.
Dies ist am einfachsten, wenn man die jeweiligen Ausgangsgleichungen mit dem nächsten Eingang verbindet. So kommt man schrittweise auf das Endergebnis.
Die UND-Verknüpfung wurde hier bereits weggelassen. Also AB = A und B usw.
Diese Gleichung kann man aber noch weiter vereinfachen. Wir wenden das 2. DeMorgansche Gesetz an.
Die doppelte Negierung hebt sich auf und wir trennen den Negationsstrich auf.
Aus unserem UND wird ein ODER. Die beiden doppelten Negationen heben sich auf und wir erhalten
Wir trennen weiter auf und heben die gemeinsamen Faktoren heraus. Es entsteht
somit bleibt
die 0 noch weg und es bleibt
Das ist ein XOR
