Es geht natürlich auch komplizierter: Eine Operation a ∧ b entspricht einer binären Operation.

2.4 Rechenregeln für Boolesche Algebra

Die Boolsche Algebra ist mathematisch eine Menge. Daraus folgt, dass es einige Theoreme gibt:

Null-Gesetze:

a ∧ 0 =0 

Dahinter steckt nichts anderes, als die Aussage, dass egal welchen Wert a annimmt, die AND-Verknüpfung mit einer unwahren Aussage „0“ immer ein unwahres Ergebnis erzeugt.

a ∨ 0 =a

Die OR-Verknüpfung von einem Wert a mit einer unwahren Aussage „0“ nimmt immer das Ergebnis a an.

Eins-Gesetze:

a ∧ 1 = a

Sie sehen, dass die AND-Verknüpfung zwischen a und einem wahren Ergebnis „1“ immer den Wert a annimmt, egal welchen Wert a hat.

 a ∨ 1 = 1

Die OR-Verknüpfung von einem Wert a mit dem wahren Ergebnis „1“ nimmt immer den Wert „1“ (wahr) an.

Doppelte Negierung

¬ ( ¬ a) = a

Wenn ich in der Ungangsprache die doppelte Verneinung benutze, lande ich ebenfalls bei der Aussage „ja“. Die zweifache Anwendung eines NOT-Operators auf einen Operanden hebt sich auf.

Beispiel: „Das ist nicht unwahr“ ist eine Aussage mit doppelter Verneinung. Die äquivalente Aussage ist: „Das ist wahr“.

Idempotenzgesetze oder auch Identitätsgesetze:

a ∧ a = a

a ∨ a = a

Wenn ich zwei gleiche Werte miteinander Verknüpfe (durch AND oder OR) erhalte ich den Wert als Ergebnis.

Beispiel aus der Aussagelogik:

„Gestern schien die Sonne und gestern schien die Sonne“ ist gleichbedeutend mit der Aussage „Gestern schien die Sonne“

„Gestern schien die Sonne oder gestern schien die Sonne“ ist gleichbedeutend mit der Aussage „Gestern schien die Sonne“

Komplementgesetze:

a ∧  ( ¬ a) = 0

Hier sehen Sie schnell, dass das Gesetzt sinnvoll ist.

a ∨ ( ¬ a) = 1

Schauen Sie wieder in die Wahrheitstabellen oben und Sie werden feststellen, dass auch dieses Gesetzt korrekt ist.

Kommutativgesetze:

a ∨ b = b ∨ a

a ∧ b = b ∧ a

Bei der Verknüpfung mit AND, wie auch bei der Verknüpfung mit OR spielt die Reihenfolge der Operanden keine Rolle.

Assoziativgesetze:

(a ∨ b) ∨ c = a ∨ (b ∨ c)

(a ∧ b) ∧ c = a ∧ (b ∧ c)

Bei Verknüpfungen einer “Art” (AND oder OR) spielt die Reihenfolge der Anwendung der Operanden keine Rolle. Eine Klammerung ist also überflüssig.

Distributivgesetze:

a ∧ (b ∨ c ) = (a ∧ b) ∨ (a ∧ c)

Der Ausdruck a ∧ (b ∨ c) ist genau dann wahr, wenn a wahr ist und einer der beiden Operanden b oder c wahr sind. Der Ausdruck (a ∧ b) ∨ (a ∧ c) ist genau dann wahr, wenn einer der Klammerausdrücke wahr ist. Entweder muss (a ∧ b) wahr sein, oder (a ∧ c). Einer der Klammerausdrücke kann aber nur dann wahr werden, wenn a wahr ist und entweder b oder c auch wahr sind.

a ∨ (b ∧ c) = (a ∨ b) ∧ (a ∨ c)

Aufgabe:Stellen Sie einen ähnlichen „Beweis“ für das zweite Distributivgesetz auf. Hinweis: Überlegen Sie erst, wann der Ausdruck vor dem Gleichheitszeichen unwahr wird.

Kürzungsregeln:

Nun wollen wir uns noch mit Kürzungsregeln beschäftigen. Bei der Umstellung nach diesen Regeln werden Sie möglicherweise immer die Möglichkeit haben, die Formeln durch einfaches kürzen zu vereinfachen.

1) a ∨ (a ∧ b) = a

2) a ∧ (a ∨ b) = a

3) a ∨ ( ¬ a ∧ b) = a ∨ b

Beweis: a ∨ ( ¬ a ∧ b) lässt sich nach dem Distributivgesetz schreiben als :

(a ∨ ¬ a) ∧ (a ∨ b). Nach dem Komplementgesetz ist (a ∨ ¬ a) = 1

1 ∧ (a ∨ b) = (a ∨ b) nach dem Einsgesetz. q e d!

4) a ∧ ( ¬ a ∨ b) = a ∧ b

Hier gehen wir im Prinzip genauso vor: a ∧ ( ¬ a ∨ b) = (a ∧ ¬ a) ∨ (a ∧ b) = 0 ∨ (a ∧ b) = (a ∧ b)

Beweis : (a ∧ b) ∨ (a ∧ ¬ b) lässt sich nach dem Distributivgesetz schreiben als:

a ∧ (b ∨ ¬ b ) Nach dem Komplementgesetz ist   (b ∨ ¬ b) =1 also

a ∧ 1 nach dem Eins-Gesetz ist a ∧ 1 =a. Was zu beweisen war.

Beweis: (a ∨ b) ∧ (a ∨ ¬ b) lässt sich auch schreiben als a ∨ (b ∧ ¬ b). (Distributivgesetz)

a ∨ (b ∧ ¬ b) ist nach Anwendung des Komplementgesetzes a ∨ 0. Diese ist aber nach dem Null-Gesetz a ∨ 0 =a

Hausaufgabe: Zeigen Sie unter Anwendung der Gesetze, dass die Kürzungsregeln 1+2 richtig sind. Kleiner Trick: Manchmal muss man erst etwas erweitern, damit alles gut wird.

de Morgan Gesetze:

Augustus de Morgan lebte 1806-1871 als englischer Mathematiker und ein Freund von Charles Babbage. Er zeigte, dass jede Konjunktion durch eine Disjunktion (und umgekehrt) ersetzt werden kann. Er erweiterte damit die von Boole aufgestellte Logik um eine entscheidende Erkenntnis .

¬ (a ∧ b) = ( ¬ a ∨ ¬ b)

¬ (a ∨ b) = ( ¬ a ∧ ¬ b)

Shannonsches Gesetz:

Claude Shannon (1916-2001) verallgemeinerte diese Regel von de Morgan und zeigte, dass die Inversion eines jeden Ausdrucks, sofern er nur mittels der Operatoren ∧ , ∨ und ¬ (d.h. Konjunktion, Disjunktion und Negation) gebildet wurde, erreicht werden, indem man ∧ und ∨ vertauscht und jedes Literal negiert.

Das klingt ziemlich kompliziert, die Aussage kann aber auch ausgedrückt werden als:

Der invertierte Wert einer Booleschen Funktion ist gleich dem Wert, den diese Funktion liefert, wenn alle Operanden und Operatoren invertiert werden.

Beispiel: ¬ (a ∧ b ∨ c ∧ ¬ d)  =  ( ¬ a ∨ ¬ b ∧ ¬ c ∨ d)

Aufgabe zum Mitdenken: Bitte rechnen Sie das mal ein einem einfachen Beispiel nach: > (¬a ∧ ¬b) = ¬(a ∨ b) , indem Sie die Wahrheitstabellen für diese Aussagen aufstellen.

Nun haben wir die einzelnen Gesetze kennen gelernt und können damit umgehen. Zur besseren Übersicht hier noch einmal die Gesetze zusammengefasst in einer Tabelle.

• Sie kennen Venn- Diagramme
• Sie kennen die Verknüpfungen AND, OR, NOT sowie die Funktionen Implikation, Äquivalenz und Antivalenz.
• Sie können Wahrheittabellen zu den Verknüpfungen aufstellen
• Sie wissen, dass es die obigen Rechenregeln gibt und können diese anwenden.

2.5 Schaltalgebra

Nun haben wir begriffen, dass es in der Booleschen Algebra die Verknüpfungen UND,OR,NOT gibt. Wir kennen auch die Wahrheitswertetabelle dieser Verknüpfungen.

Wenn wir eine Wahrheitswertetabelle aufstellen, die alle verschiedenen Wahrheitswertekombinationen enthält, werden wir feststellen, dass es 16 Möglichkeiten gibt.

Wenn wir nun sagen, die Verknüpfungen seien jeweils eine Funktion, dann haben wir 16 verschiedene Funktionen. Die Funktionen haben natürlich alle einen Namen, den ich Ihnen hier mit auf den Weg geben möchte.

Um einige der Funktionen werden wir uns nun ganz speziell kümmern, da sie für Schaltungen immer wieder benötigt werden und Ihnen daher sicherlich mal wieder über den Weg laufen werden.

Schaltsymbole

Nun haben wir begriffen, dass es in der Booleschen Algebra verschiedene Operationen gibt. Diese lassen sich natürlich auch durch Schalter darstellen. Hier seien nun die wichtigsten Funktionen dargestellt abgebildet.

AND – Funktion

Wenn Sie beispielsweise eine AND – Funktion in einer Schaltung darstellen wollen, können Sie dieses sich am Besten durch einen Stromfluss klarmachen:

Die Lampe soll genau dann leuchten (das Ergebnis true (1) sein), wenn beide Schalter den Wert true annehmen (also beide Schalter geschlossen sind. Dazu werden die beiden Schalter hintereinander (in Reihe) geschaltet.

Wenn einer der Schalter geöffnet („false) ist, leuchtet die Lampe nicht. Das Ergebnis wird „false“.

OR-Funktion

Bei einer OR-Funktion werden die Schalter nicht in Reihe, sondern parallel geschaltet. Dadurch wird erreicht, dass die Wahrheitswertetabelle der OR-Funktion bei den verschiedenen Schalterstellungen stimmt.

Bei beiden geschlossenen Schaltern leuchtet die Lampe, das Ergebnis wird „true“.

Aber auch bei einem geöffneten Schalter bleibt der Stromkreis geschlossen. Das Ergebnis ist ebenfalls wieder „true“.

NOT-Funktion

Die Negation einer Aussage wird in der Schaltalgebra durch die Änderung der Schalterstellung umgesetzt, ein geschlossener Schalter wird ein geöffneter, ein offener Schalter wird geschlossen.

Da sich jeder komplexe logische Ausdruck auf die elementaren Verknüpfungen elementarer Ausdrücke zurückführen lässt, kann dementsprechend auch jeder noch so komplexe logische Ausdruck durch eine entsprechende Schaltung realisiert werden. Da komplexere Schaltungen in dieser Darstellungsart sehr unübersichtlich werden würden, hat man für die verschiedenen Booleschen Funktionen Schaltsymbole eingeführt.

Übersicht über die Schaltsymbole

Leider unterscheiden sich die Schaltsymbole in der europäischen und amerikanische Darstellung etwas.  In der Übersicht sehen Sie die Darstellung nach DIN (nach 1976, davor sahen auch hierzulande die Symbole etwas anders aus) und der Darstellung nach IEEE.

Diese Symbole nennt man logische Gatter.

Nun wollen wir ein Beispiel für eine Schaltung mit den neuen Schaltsymbolen darstellen.

Danach werden wir versuchen, die Darstellung zu vereinfachen. Dazu werden wir wieder die Gesetze, die wir bereits kennen gelernt haben, heranziehen.

Erste Schaltungen

Nehmen wir uns ein erstes Beispiel einer Realisierung einer Booleschen Verknüpfung vor:

Gegeben sei die Verknüpfung

a ∧ (b ∨ c) = y

Dies können wir mit den logischen Gattern in einem Schaltnetz darstellen.

Beispiel:

Wir haben den Ausdruck (a ∧ b) ∨ (a ∧ c) der sich als Schaltung darstellen würde als

Nach Anwendung des Distributivgesetzes: (a ∧ b) ∨ (a ∧ c) = a ∧ (b ∨ c) kann die Schaltung auch dargestellt werden als

Der Vorteil ist klar ersichtlich: Es werden nicht mehr drei, sondern nur noch zwei Gatter benötigt.

Wie kommt man nun auf die Zeichnung? In der Praxis geht man folgendermaßen vor:

• Zuerst wird die gewünschte Wahrheitswertetabelle aufgestellt.
• Dann sehen wir in der Tabelle der möglichen Booleschen Funktionen nach, welche Funktion dem gewünschten Ergebnis entspricht. Bei der Verknüpfung von mehreren Variablen (a,b,c,d …) nutzen wir das Wissen, dass wir die Schaltfunktion aus der Wahrheitswertetabelle konstruieren können (Boolesche Normalform)
• Danach formen wir die Schaltfunktionen so um, dass sie möglichst einfach darstellbar und realisierbar ist.

Wenn Sie jetzt aufgepasst haben, werden Sie merken, dass uns die Boolesche Normalform noch gar nicht bekannt ist. Deshalb folgt nun ein kleiner Einschub.

Boolesche Normalformen

Mit Hilfe des Theorems der Booleschen Normalform kann man aus einer Wahrheitswertetabelle einer Booleschen Funktion einen Booleschen Ausdruck konstruieren. Die Schaltfunktion wird dabei ausschließlich durch die drei Verknüpfungen AND, OR, NOT ausgedrückt.  

Disjunktive Normalform (DNF)

Das Entstehen einer disjunktiven Normalform erläutert man ideal an einem Beispiel.

Wir nehmen eine Wahrheitswertetabelle mit einer Verknüpfung von drei Operanden:

Gesucht wird nun ein Boolescher Ausdruck, der genau dieser Wahrheitswertetabelle entspricht.

Dazu bedient man sich der Gesetzmäßigkeit der Bildung von disjunktiven Normalformen. Die Bildung der disjunktiven Normalform funktioniert wie folgt.

Ich nehme jede Zeile mit dem Eintrag 1 in der Ergebnistabelle und bilde eine Konjunktion, die alle Variablen der Funktion verknüpft. Variablen, die in der Zeile mit 1 belegt sind, werden dabei nicht negiert und Variablen, die mit 0 belegt sind, werden negiert.

Das hört sich sehr kompliziert ist, ist es aber gar nicht:

Die Zeilen 2, 5 und 8 enthalten bei Ergebnis eine 1.

Jetzt verknüpfe ich die Variablen a,b,c durch eine Konjunktion. Dabei negiere ich die Variablen, bei denen in der entsprechenden Zeile eine 0 steht.

Beispiel für Zeile 2 : ( ¬ a ∧ ¬ b ∧ c). Die so gebildeten Terme werden Minterme genannt.

Das mache ich für jede Zeile mit einer 1 in der Ergebnisspalte. Die einzelnen Zeilenergebnisse verknüpfe ich danach durch eine Disjunktion

( ¬ a ∧ ¬ b ∧ c) ∨ (a ∧ ¬ b ∧ ¬ c)  ∨ (a ∧ b ∧ c) = f(a,b,c).

Damit die die erforderlich Schaltung für das obige Problem bereits aufgestellt.

Konjunktive Normalform (KNF)

Auch die Bildung der konjunktiven Normalform führt zum Ziel.

Die KNF wird sehr ähnlich gebildet. Hier werden die Zeilen mit dem Eintrag 1 in der Ergebnisspalte ignoriert. Es werden dafür die Zeilen mit dem Eintrag 0 in der Resultatspalte herangezogen. Die Variablen mit einem Eintrag 0 werden nicht negiert, die Variablen mit einem Eintrag 1 werden negiert. Die nach dieser Methode gebildeten Terme heißen Maxterme.

Die Maxterme werden nun über Konjunktionen verbunden:
( a ∨ b ∨ c) ∧ ( a ∨ ¬ b ∨ c) ∧   ( a ∨ ¬ b ∨ ¬ c) ∧   (¬ a ∨ b ∨ ¬ c) ∧   (¬ a ∨ ¬ b ∨ c)

Für die Bildung solcher Normalformen gibt es auch systematisierte Verfahren (z.B. Karnaugh Veitch Diagramme). Auf diese wollen gleich kurz eingehen eingehen.

Um nun zu einer Schaltung zu kommen, sollten Sie den erhaltenen Booleschen Ausdruck aber noch etwas vereinfachen.

Das können Sie gerne zu Hause einmal machen, um Übung in der Umformung solcher Terme zu bekommen.

Karnaugh-Veitch-Diagramme

Wenn wir einen Ausdruck vorliegen haben, ist manchmal sehr schwer zu sehen, ob dieser noch vereinfacht werden kann.

Das K-V-Diagramm bietet hier eine übersichtliche und schnelle Hilfe.

Die Vorgehensweise nach Karnaugh und Veitch ist grafisch orientiert und bietet einem eigentlich nur mehr Übersicht, als es die vielen Terme nach der Ermittlung von Normalformen es tun.

Allerdings muss man sagen, dass die K-V-Diagramme bei mehr als 4 Variabeln auch nicht mehr übersichtlich sind und daher dort kaum verwendet werden. Da gibt es dann wieder andere Verfahren, auf die wir hier nicht eingehen werden.

Man könnte nun eine Menge Mathematik betreiben zu zeigen, warum die K-V-Diagramme so gut funktionieren. Wir wollen und das ersparen und eher die Verwendung der K-V-Diagramme erlernen.

Nur soviel sei gesagt:"Dadurch, dass benachbarte Felder sich immer nur in einer Stelle unterscheiden, funktioniert es überhaupt".

Noch einen weiteren Satz: "Für die Verwendung benötigt man die disjunktive Normalform".

Gut klarmachen kann man sich die Anwendung eines Vorgangs immer genau dann, wenn man den Vorgang anwendet..... Es folgt also ein Beispiel:

Wir nehmen eine Lampe an, die bei folgender Schaltung leuchtet:

Die disjunktive Normalform ist dazu schnell aufgestellt:

( ¬ a ∧ ¬ b ∧ ¬ c) ∨ ( ¬ a ∧ b ∧ ¬ c) ∨ (a ∧ b ∧ ¬ c) ∨ ( ¬ a ∧ ¬ b ∧ c) ∨ ( ¬ a ∧ b ∧ c) ∨ (a ∧ b ∧ c) = f(a,b,c).

Diese Funktion ist noch etwas unbequem gross. Wir wollen sie nun vereinfachen. Entweder rechnen Sie nun mit Hilfe der Rechengesetze der Booleschen Algebra, oder sie benutzen ein K-V-Diagramm.

Wir entscheiden uns für das K-V-Diagramm.

Wir nehmen nun einfach die Minterme her und setzen in eine vorbereitete Matrix an den richtigen Stellen eine 1.

	a	a	¬a	¬a
b	1	1	1	1
¬b	0	0	1	1
	c	¬c	¬c	c

Wie man nun sehr deutlich sieht, stehen einige Einsen in Reihe nebeneinander oder untereinander.

Blöcke von 2, 4, 8 oder allgemein kⁿ Einsen lassen sich zusammenfassen. n ist die Anzahl der Variablen.

Hier lassen sich also zwei Blöcke bilden. Die Einsen in der Zeile mit dem b

Der Block von 4 Einsen bei ¬a.

Die obige Funktion kann also mit ¬a ∨ b recht schnell ausgedückt werden.

Die haben sich das komplizierte Umstellen und Rechnen erspart.

Sie sollten aber bitte zu Hause einmal nachrechnen, ob ich auch alles richtig gemacht habe.

Um gleich zu sehen, ob Sie es verstanden haben, folgt ein weiteres Beispiel. Diesmal werden wir vier Variabeln einfliessen lassen.

Nehmen wir an, wir haben folgendes K-V-Diagramm ausgefüllt vorliegen:

Hier haben wir einen Block von Einsen in der Reihe ¬b und d. Damit ist ein Term bestimmt.

Einen anderen Block haben wir bei a und c und d vorliegen. Damit läßt sich unsere gesuchte Funktion ausdrücken als:

( ¬ b ∧ d) ∨ (a ∧ c ∧ d) = f (a,b,c,d)

Sie sehen, das Vorgehen ist recht schnell und einfach. Sie müssen lediglich beachten, dass Sie die richtigen Diagramme zur Hand haben.

Es fehlt Ihnen nun noch das Diagramm für zwei Variabeln. Hier ist es:

	a	¬a
b
¬b

2.6 Anwendungen (Addierer)

Halbaddierer

Wir haben bereits gesehen, dass die Grundrechenarten in Dualen Zahlensystem sich alle auf das Addieren zurückführen lassen. Nun wollen wir uns ansehen, wie ein Rechner eigentlich intern rechnet. Wir bauen dazu ein Schaltbild für einen Addierer auf.

Zunächst stellen wir die Wahrheitswertetabelle für das Addieren auf. Bei Addieren müssen wir aber berücksichtigen, dass wir Überträge (das so genannte Carry-Bit) haben. Wir haben also zwei Wahrheitswertetabellen zu berücksichtigen.

Aus der Tabelle der möglichen Funktionen unter Kapitel 2.5  erkennen wir sehr schnell, dass wir die Funktion F7 (XOR) für das Resultat benötigen. Den Übertrag decken wir über die Funktion AND ab.

Damit ist die Schaltfunktion eines Halbaddierer bereits fertig:

Volladdierer

Wenn ich aber richtig addieren möchte, muss ich den Übertrag des vorangegangenen Schrittes mitnehmen und als weiteren Eingangswert spezifizieren.

Die Schaltfunktion wird dadurch aber nur unwesentlich komplizierter.

Wir erinnern uns, dass wir die Subtraktion auf eine Addition mit dem Zweierkomplement zurückführen können. Damit ist dieses Problem also auch schon gelöst.

Die Multiplikation und Division lassen sich zwar auch auf die Addition zurückführen, aber dazu braucht es noch eine weitere Einheit, nämlich so genannte Schieberegister, auf die wir hier aber nicht weiter eingehen wollen

• Sie kennen die Booleschen Funktionen. Dabei wissen Sie genau, wie die Funktionen AND, NOT, OR, NAND, XOR gebildet werden.
• Sie kennen die Schaltsymbole nach DIN 40900;
• Sie können einfache Schaltungen lesen und in eine Boolesche Funktion übertragen
• Sie können aus einer Wahrheitswertetabelle anhand der Normalformen eine Boolesche Funktion ableiten
• Sie kennen die Karnaugh-Veitch-Diagramme und können diese anwenden