Boolesche Algebra

aus ZUM-Wiki, dem Wiki für Lehr- und Lerninhalte auf ZUM.de
Wechseln zu: Navigation, Suche

Hier findest Du eine Selbstlerneinheit mit vielen Übungen, bei der Du Dir Wissen über die Boolesche Algebra, ihre Operatoren und deren Anwendung im Internet, aneignen kannst. Viel Spaß dabei!

Inhaltsverzeichnis

Einleitung

Während frühe Computer intern noch durch das Dezimalsystem gesteuert wurden, wird heute praktisch in jedem Rechner das Binärsystem verwendet. Es kommt mit nur zwei Werten, der 0 und der 1, aus, mit Hilfe derer Informationen im Rechner mittels Schaltungen weitergeleitet, entschlüsselt, verarbeitet und in Registern gehalten werden können. Dies erlaubt den Bau von günstigen und leistungsstarken Schaltungen, die im Gegensatz zum Dezimalsystem mit nur zwei möglichen Zuständen auskommen anstatt der sonst nötigen 10.

Im Folgenden lernst Du etwas über das Logiksystem des Mathematiker George Boole, sowie dessen Repräsentation und die Umformungsgesetze. Des Weiteren werden Logikgatter und Schaltungen thematisiert, als auch die praktische Anwendung der Verknüpfungsoperatoren bei der Suche nach Begriffen im Internet.

In den Übungsaufgaben kannst Du testen, ob du alles verstanden hast.

Boolesche Algebra

Die sogenannte Boolesche Algebra geht auf den englischen Mathematiker George Boole (1815-1864) zurück. Boole hat als erster eine Art „Algebra der Logik“ entwickelt, die nur die Zustände 0 und 1 kennt. Der Zustand 1 entspricht dabei „wahr“ beziehungsweise, dass Strom fließt, der Zustand 0 „falsch“ und keinem Stromfluss in einem Schaltkreis. Logische Aussagen müssen entweder wahr oder falsch sein, es handelt sich also um eine zweiwertige Logik.

In vielen Programmiersprachen, wie zum Beispiel Java, prägte er den Datentyp für Wahrheitswerte (true/false).

Basis-Operationen

Die Boolesche Algebra beruht auf der Menge {0,1}. Ausgehend von dieser sind die Verknüpfungen AND (Konjunktion), NOT (Negation) und OR (Disjunktion) definiert. Die Eingabe kann aus einer oder zwei Variablen bestehen, abhängig von der Verknüpfung. Als Ausgabe erhältst Du eine Variable, die „wahr“ oder „falsch“, beziehungsweise 0 oder 1 ist. Die Operationen führen also Berechnungen mit Deinen Eingaben aus.
Dargestellt werden die Operationen entweder mit Hilfe einer Wahrheitstabelle oder als Boolesche Funktion.

Eine Wahrheitstabelle kannst Du Dir wie eine Tabelle vorstellen, in der einerseits die möglichen Eingaben dargestellt werden und andererseits die dazu gehörenden Ausgaben.


Gehen wir einmal von zwei Eingaben x und y aus. Beide können jeweils 0 oder 1 sein.
Weißt Du wie viele Kombinationsmöglichkeiten es also gibt?

Es gibt 4 Möglichkeiten, denn x und y könnten beide 0 oder 1 sein, aber auch verschiedene Werte haben (also x=0 und y=1 oder x=1 und y=0).
Für 3 Eingaben, zum Beispiel x, y und z, gibt es sogar 8 Möglichkeiten.
Allgemein gilt: Es gibt 2^n Möglichkeiten, wobei n die Anzahl der Eingabevariablen darstellt. In unseren Fällen war n zuerst 2 und dann 3.
Wir beschränken uns zunächst auf den Fall von nur zwei Eingabevariablen.

Das Grundgerüst einer Wahrheitstabelle für die Konjunktion und Disjunktion sieht immer so aus:

Konjunktion Disjunktion

x y x ∧ y
0 0
0 1
1 0
1 1
x y x ∨ y
0 0
0 1
1 0
1 1

In den Spalten x und y sind unsere Kombinationsmöglichkeiten eingetragen. Hätten wir noch eine dritte Eingabe, würde noch eine Spalte, z, hinzukommen. Damit würde sich die Anzahl der Zeilen erhöhen, denn dann haben wir 8 Kombinationsmöglichkeiten. In die noch leere Spalte werden die Ausgaben notiert, die sich durch die Operationen auf den Eingaben ergeben. Welche dies genau sind, erfährst Du gleich.


Die Wahrheitstabelle für die Negation ist sogar noch einfacher. Bei der Negation gibt es nur eine Eingabe- und auch nur eine Ausgabevariable. Deshalb reicht eine Spalte mit x und zwei Zeilen, da die Eingabe nur 0 oder 1 sein kann.

Negation

x ¬
0
1

Eine andere Möglichkeit der Darstellung ist die sogenannte Boolesche Funktion. Ihr werden eine bzw. zwei (natürlich sind auch mehr möglich, diesen Fall werden wir aber später betrachten) Eingabevariable übergeben. In diesem Fall hier sind x und y die Eingabevariablen, also sieht die Funktion zunächst so aus:

Für die Konjunktion und die Disjunktion: f(x,y)=
Für die Negation: f(x)=

Hinter dem = folgt eine Art Funktionsgleichung, wie du sie schon aus der Mathematik kennst. Mit Hilfe der Funktion kannst du die Ausgabe berechnen.

Konjunktion

Bei der Konjunktion, auch "Und-Verknüpfung" genannt, handelt es sich um eine binäre Verknüpfung. Binär kommt aus dem Lateinischen und bedeutet hier, dass „je zwei“ Eingabevariablen miteinander verknüpft werden.
Sie wird durch das Zeichen ∧ dargestellt und man ließt „x ∧ y“ als „x und y“. Dabei werden zwei Eingabevariablen x und y verknüpft zu einer Ausgabevariablen. x und y können dabei nur die Werte 0 und 1 annehmen, genau wie die Ausgabevariable.

Die Ausgabe ist genau dann 1, wenn beide Eingabevariablen 1 sind, ansonsten ist sie 0.


Übungsaufgabe: Fülle die Wahrheitstabelle ausgehend vom Grundgerüst aus.

Suche dazu das Grundgerüst der Wahrheitstabelle für die Konjunktion aus dem vorherigen Abschnitt. Die Belegungen mit 0 und 1 kannst Du so belassen, da wir hier zunächst nur zwei Eingaben betrachten möchten.
Brauchst Du Hilfe bei der ersten Zeile der Tabelle? Dann klicke auf "Tipp anzeigen". Möchtest Du Deine Lösung überprüfen, klicke auf "Lösung anzeigen".


Möchtest Du die Konjunktion lieber als Boolesche Funktion darstellen, so gelten die folgenden äquivalenten Funktion:
f(x,y) = x ∧ y und f(x,y) = x • y.
Äquivalent bedeutet, dass die beiden Funktionen das gleiche Ergebnis liefern, obwohl sie verschieden sind.

Negation

Die Negation, auch "Nicht-Operator" genannt, stellt die einfachste der drei Grundoperationen dar. Sie besitzt nur eine Eingabe- und eine Ausgabevariable. Wie der Name bereits andeutet, wird hier die Eingabe negiert.
Die Eingabe 0 wird als 1 ausgegeben und die 1 als 0. Die Werte der Variablen werden also umgekehrt. Die Negation wird mit dem Zeichen ¬ dargestellt und „¬x“ als „nicht x“ gelesen.


Übungsaufgabe: Wie sieht die Wahrheitstabelle hier aus?
Fülle auch hier das oben vorgestellte Grundgerüst aus.

Die Darstellung der Negation als Boolesche Funktion lautet: f(x) = ¬x oder f(x) = \bar{x}

Disjunktion

Genau wie bei der Konjunktion handelt es sich bei der Disjunktion, auch "Oder-Verknüpfung" genannt, um eine binäre Verknüpfung. Auch hier werden zwei Variablen miteinander verknüpft zu einer Ausgabevariablen. Das Verknüpfungszeichen lautet ∨ und „x ∨ y“ wird gelesen als „x oder y“.
Die Ausgabe ist genau dann 1, wenn eine oder beide der Eingabevariablen 1 sind.


Übungsaufgabe: Fülle die entsprechende Wahrheitstabelle aus.

Als Boolesche Funktion dargestellt, sieht die Disjunktion folgendermaßen aus:
f(x,y) = x + y oder f(x,y) = x ∨ y.

Rechenregeln der Booleschen Algebra

Aus den Basis-Operationen, die Du eben gelernt hast, kannst Du nun beliebige Funktionen zusammensetzen. Du kannst auch mehr als nur zwei Eingabevariablen verwenden.

Sieh Dir dieses Beispiel mit den drei Eingabevariablen x, y und z an.

f(x,y,z) = ((¬x) ∧ y) ∨ (x ∧ (¬z))

Kannst Du dafür eine Wahrheitstabelle erstellen? Sieh Dir die Klammerung genau an und beginne von innen nach außen zu lösen.

Wenn Du möchtest, kannst Du Dir dazu auch das Video anschauen. Darin erkläre ich Dir, wie Du dabei vorgehen musst. Du findest das Video direkt hier unter der Lösung.




Stell Dir vor, die boolesche Funktion hätte keine Klammern: Wüsstest Du welche Operatoren am stärksten binden und welche Verknüpfungen daher zuerst betrachtet werden müssen?
Lies Dir den nächsten Abschnitt durch und dann kannst Du die Frage beantworten.

Prioritäten

Schau Dir noch einmal die boolesche Funktion f(x,y,z)= ((¬x) ∧ y) ∨ (x ∧ (¬z)) aus dem vorigen Abschnitt an. Mit den vielen Klammern sieht das ganz schön kompliziert aus. Daher hat man Präzedenzregeln eingeführt, um die Schreibweise zu vereinfachen. Solche Präzedenzregeln kennst Du schon aus der Mathematik, dort gilt „Punktrechnung vor Strichrechnung“.

Schau Dir die Klammern nun noch einmal ganz genau an. Welche Operatoren werden zuerst ausgewertet und binden damit am stärksten?
Ziehe die Kästchen ins richtige Feld. Wenn Du fertig bist, kannst Du auf prüfen klicken und schauen, ob Du alles richtig gemacht hast.

1. Priorität: Klammerung (...)
2. Priorität: Negation ¬
3. Priorität: Konjunktion ∧
4. Priorität: Disjunktion ∨

Da Du nun weißt, welche Operatoren am stärksten binden, kannst du die Klammern weglassen. Die boolesche Funktion sieht jetzt so aus:

f(x,y,z) = ¬x ∧ y ∨ x ∧ ¬z

Ohne Klammern sieht es doch viel einfacher aus, oder?
Wenn Du möchtest, dass die Verknüpfungen in anderer Reihenfolge ausgewertet werden sollen, dann musst Du Klammern setzen.

Umformungssätze

Wenn Du eine boolesche Funktion mit vielen Verknüpfungen hast, dann kann das Erstellen einer Wahrheitstabelle sehr aufwendig sein. Deshalb solltest Du, bevor Du anfängst, eine Wahrheitstabelle aufzustellen, erst einmal schauen, ob Du die Funktion nicht noch vereinfachen kannst. Damit kannst Du Dir eine Menge Arbeit sparen. Und auch später, wenn die boolesche Funktion als Schaltung umgesetzt werden soll, sind diese Umformungen hilfreich.

Es gibt eine Reihe von Rechengesetzen, die Du Dir nun anschauen solltest:

Kommutativgesetz: a ∧ b = b ∧ a a ∨ b = b ∨ a
Assoziativgesetz: (a ∧ b) ∧ c = a ∧ (b ∧ c) (a ∨ b) ∨ c = a ∨ (b ∨ c)
Distributivgesetz: a ∧ (b ∨ c) = (a ∧ b) ∨ (a ∧ c) a ∨ (b ∧ c) = (a ∨ b) ∧ (a ∨ c)
Idempotenzgesetz: a ∧ a = a a ∨ a = a
Neutralitätsgesetz: a ∧ 1 = a a ∨ 0 = a
Extremalgesetz: a ∧ 0 = 0 a ∨ 1 = 1
De Morgansche Gesetz: ¬(a ∧ b) = ¬a ∨ ¬b ¬(a ∨ b) = ¬a ∧ ¬b
Doppelnegationsgesetz: ¬(¬a) = a
Absorptionsgesetz: a ∨ (a ∧ b) = a a ∧ (a ∨ b) = a
Komplementärgesetz: a ∧ ¬a = 0 a ∨ ¬a = 1


Übungsaufgabe: Beweise beide Varianten des Distributivgesetzes mit Hilfe einer Wahrheitstabelle. Du kannst alles in einer Wahrheitstabelle notieren.


Übungsaufgabe: Vereinfache die folgende boolesche Funktion mit Hilfe der Rechengesetze:
¬(¬x ∨ (x ∧ ¬x) ∨ ¬(y ∧ (x ∨ y)))

weitere boolesche Funktionen

Aus den Operatoren ∧, ∨ und ¬, die Du bereits kennst, lassen sich weitere Operatoren ableiten. Diese lassen sich alle mit nur diesen drei Grundoperatoren bilden, Du brauchst nichts weiter dazu.
In der Tabelle bekommst Du eine Übersicht, welche Operatoren es noch gibt, wie ihre Wahrheitstabellen für zwei Eingaben aussehen und wie die boolesche Funktion lautet.

x y Xor: (x ∧ ¬y) ∨ (¬x ∧ y) Nor: ¬(x ∨ y) Equivalence: (x ∧ y) ∨ (¬x ∧ ¬y) Implication: x ∨ ¬y Nand: ¬(x ∧ y)
0 0 0 1 1 1 1
0 1 1 0 0 0 1
1 0 1 0 0 1 1
1 1 0 0 1 1 0

Normalformen

In manchen Fällen hat man eine Wahrheitstabelle und möchte dazu eine boolesche Funktion angeben. Manchmal ist das ganz einfach und man sieht sofort wie der boolesche Ausdruck auszusehen hat. Manchmal aber ist die Wahrheitstabelle so kompliziert, dass man dazu systematisch vorgehen muss.

disjunktive Normalform

Bei der disjunktiven Normalform (DNF) werden die Variablen, durch deren Belegung sich die Ausgabe 1 ergibt, durch eine Konjunktion verknüpft. Anschließend werden alle konjunktiven Ausdrücke durch Disjunktionen verbunden.
Die Vorgehensweise siehst Du an diesem Beispiel: Wir haben eine Wahrheitstabelle mit drei Eingabevariablen und einer Ausgabevariablen gegeben, die durch die boolesche Funktion erzeugt wird. Die Aufgabe ist es nun, die dafür angewendete boolesche Funktion zu finden.

x y z f(x,y,z)
0 0 0 0
0 0 1 0
0 1 0 0
0 1 1 1
1 0 0 0
1 0 1 1
1 1 0 1
1 1 1 1

Suche zunächst alle Zeilen, deren Ausgabevariable eine 1 ist.

Jetzt können wir für Zeile 4 einen konjunktiven Ausdruck bilden. Er hat die Form ¬x ∧ y ∧ z. Ist Dir aufgefallen, dass wir alle Eingabevariablen, deren Wert 0 ist, negiert haben?
Bilde jetzt noch für die restlichen Zeilen einen konjunktiven Ausdruck!

Nun fehlt noch der letzte Schritt zur disjunktiven Normalform: Die Verbindung der konjunktiven Ausdrücke durch Disjunktionen.

Damit haben wir unser Ziel erreicht!

Wenn Du möchtest, kannst Du das Ergebnis nun noch mit den eben gelernten Rechengesetzen umformen.

konjunktive Normalform

Bei der konjunktiven Normalform (KNF) werden die Variablen, durch deren Belegung sich die Ausgabe 0 ergibt, zunächst durch eine Disjunktion verknüpft. Anschließend werden alle disjunktiven Ausdrücke durch Konjunktionen verbunden.

Diesmal kannst Du es gleich selbst versuchen.
Wir betrachten wieder das gleiche Beispiel. Diesmal musst Du allerdings darauf achten, dass Du für jede Zeile, die den Funktionswert 0 hat, einen disjunktiven Ausdruck bildest. Schaffst Du das?

Gatter und logische Schaltungen

Vielleicht fragst Du Dich jetzt wo diese Boolesche Algebra Anwendung findet. Genau das erfährst Du in diesem Abschnitt.


Jeder Computer, auch der, an dem Du gerade sitzt, arbeitet nach dem Logiksystem, das von George Boole entwickelt wurde. Für Addition, Multiplikation, und vieles andere, benötigt dein Computer dieses Logiksystem und die logischen Schaltungen, die darauf aufbauen.
Eine solche logische Schaltung kannst Du Dir als Realisierung einer ganzen Wahrheitstabelle in Form eines Bauteils vorstellen. In der Wahrheitstabelle haben wir dafür viele Zeilen benötigt, jetzt reicht eine einzige Schaltung aus, um alle Möglichkeiten zu realisieren.
Aus der Theorie wird also Realität.

Basis-Gatter

Ein Gatter ist ein Hardware-Baustein, der eine boolesche Funktion umsetzt. In der Regel besitzt er einen oder zwei Eingangs-Pins und einen Ausgangs-Pin. Diese Pins können mit den Werten 0 und 1 belegt werden, wie wir vorhin schon gesehen haben, oder mit true und false. Die drei Basis-Operationen, die Du eben kennen gelernt hast, lassen sich wie rechts zu sehen, als Gatter darstellen.

Zeichnung von AND, NOT, OR Gattern

Die Und- und Oder-Gatter sind hier nur mit zwei Eingängen versehen, aber können natürlich auch mehr als zwei Eingänge haben. Sie haben dann aber trotzdem nur einen Ausgang.

Wenn du dir in der Tabelle in Abschnitt 2.3 weitere boolesche Funktionen noch einmal NAND und NOR anschaust, fällt Dir auf, dass es sich dabei einfach um eine negierte AND bzw. OR-Operation handelt?
Daher werden in der Darstellung dafür die AND bzw OR-Operation verwendet und am Ausgang ein kleiner Kreis angefügt, der die Negierung andeutet.

Zeichnung von NAND und NOR Gattern


logische Verbindungen

Mit den Basis-Gattern, die Du nun kennst, lassen sich für beliebige boolesche Funktionen logische Schaltungen zusammenbauen. Diese verschiedenen Kombinationen von Gattern veranlassen den Computer, seine Aufgaben zu erfüllen. Damit können beispielsweise Daten bewegt werden.

Um eine logische Schaltung zu erhalten, bedarf es mehrerer Schritte und einer effizienten Kombination von Gattern. Zunächst wird die Wahrheitstabelle der Funktion, die als Schaltung umgesetzt werden soll, aufgestellt. Anschließend muss eine disjunktive Normalform erstellt werden. Hier bietet sich manchmal eine Vereinfachung des Ausdrucks an, um möglichst wenig Gatter verwenden zu müssen. Jetzt kann der Ausdruck mit Gattern realisiert werden.

Wir wollen nun anschauen, wie wir aus der Wahrheitstabelle der Operation XOR eine logische Schaltung bauen können, die aus unseren Basis-Gattern besteht.

x y XOR
0 0 0
0 1 1
1 0 1
1 1 0

Eine Umformung ist hier nicht nötig, sodass wir die disjunktive Normalform sofort in eine Schaltung überführen können. Dazu benötigen wir drei Gatter: zwei AND-Gatter und ein OR-Gatter. Dies erkennst du an der Funktion, nachdem Du die disjunktive Normalform gebildet hast.
Zunächst werden die beiden Ausdrücke, die in Klammern stehen, mit AND-Gattern realisiert.
Die beiden Ausgangs-Pins bilden nun die Eingangs-Pins für das OR-Gatter.

Damit haben wir bereits unsere fertige XOR-Schaltung, die jetzt so aussieht:

XOR-Schaltung



Bevor Du nun zum letzten Kapitel gehst, kannst Du hier das bisher Gelernte testen:

Boolesche Suchoperatoren

Bisher war alles sehr theoretisch, doch jetzt kommt eine wirklich praktische Anwendung.

Dir ging es bestimmt auch schon mal so, dass Du im Internet nach etwas bestimmtem gesucht hast, aber unzählige Treffer kamen, die Du gar nicht wolltest. Du musstest dich durch viele vorgeschlagene Seiten lesen, bis Du endlich das gefunden hast, was Du gesucht hast. Mit den richtigen Suchoperatoren kannst Du sowas in Zukunft umgehen und Deine Suchanfrage genau nach deinen Wünschen gestalten.


Google

Übungsaufgabe: Du möchtest gerne nach dem deutschen Schulsystem suchen. Wie würdest du dabei in Google vorgehen?

Du könntest dabei zum Beispiel nach „Deutschland Schulsystem“ suchen. Probiere dies aus.


Versuche nun nach „Deutschland OR Schulsystem“ zu suchen. Achte dabei auf die Großschreibung von OR, sonst wird das Ergebnis verfälscht. Fällt Dir etwas auf?
Was passiert, wenn Du nach „Deutschland –Schulsystem“ suchst?


Hast Du bemerkt, dass wir genau unsere Basis-Operatoren der Booleschen Algebra verwendet haben?
Damit haben wir verschiedene Resultate erhalten. Hier kannst Du dir noch einmal bildlich anschauen, welche Operatoren welche Resultate liefern.

Boolesche Operatoren als Menge


Google sucht also automatisch bei mindestens zwei Suchbegriffen mit einer AND-Operation. Sollen Artikel gefunden werden, die einen bzw. mehrere der Suchbegriffe enthalten, muss zwischen die Begriffe ein OR eingefügt werden. Ein – vor einem Begriff schließt diesen aus.


Übungsaufgabe: Überlege Dir einige Suchbegriffe und probiere selber aus was passiert, wenn Du verschiedene Operatoren verwendest.


andere Suchmaschinen

Neben Google gibt es aber noch eine Vielzahl anderer Suchmaschinen, die Du nutzen kannst. Jede hat dabei aber andere Einschränkungen betreffend der Akzeptierung von NOT und -. Auf der folgenden Seite findest Du eine Übersicht, welche Suchmaschine welche booleschen Operatoren akzeptiert. Sieh dazu in der Spalte „BOOLEAN“ nach:
http://www.searchengineshowdown.com/features/
Wenn Du auf die jeweiligen Operatoren klickst, bekommst Du noch mehr Informationen. Ein Klick auf den Namen der Suchmaschine leitet Ddich auf die Seite weiter und unter „Review“ erhältst Du noch mehr Informationen über die Suchmaschine selbst.


Wie Du in der Tabelle sehen kannst, akzeptiert die Yahoo Suchmaschine nicht nur -, sondern auch das NOT selbst. Auch Klammern kannst Du nun setzen. Allerdings sucht Yahoo nicht automatisch mit einer AND-Operation. Diese musst Du selbst eingeben.

Übungsaufgabe: Wie würdest Du jetzt vorgehen, wenn Du in Yahoo herausfinden möchtest, was Fleischküchle bzw. Fleischplanzerl sind.
Verwende dazu die Operatoren AND und OR, als auch Klammern.

Warum wäre eine Suche mit Fleisch AND Küchle OR Pflanzerl falsch?

Super, nun kannst Du das nächste Mal, wenn Du etwas Bestimmtes suchst, viel effizienter vorgehen!

Quellen

http://www.uni-giessen.de/~gc1099/dm/DM%20II%20-%20Kapitel%203%20-%20Boolesche%20Algebra.pdf

http://www12.informatik.uni-erlangen.de/edu/gdi2/folien/4_GdI2_Entwicklungssatz.pdf

http://www.rs.tu-darmstadt.de/fileadmin/PDFs/LogicDesign/Slides/LE-02online.pdf

http://www.searchengineshowdown.com/features/

https://www.vetion.de/internet/detail.cfm?main_tipinfo_id=422

http://www.demorgan.de/