Dies ist eine alte Version des Dokuments!
Boolsche Algebra
Seit Konrad Zuse erkannt hatte, dass das Binärsystem für den Bau von modernen Rechenmaschinen geeigneter ist als unser Dezimalsystem, basieren quasi alle Computer auf dieser Grundlage. Nachdem Relais oder Elektronenröhren durch moderne, winzige Transistoren ersetzt wurden, besteht die Hardware eines Computers aus Millionen von winzigen Schaltelementen, welche zu immer komplexeren Schaltungen zusammengefügt werden.
Das mathematische Teilgebiet, welches sich mit der Manipulation von logischen Aussagen beschäftigt, ist die Boolsche Algebra. Sie ist nach dem englischen Mathematiker George Boole (1815-1864) benannt. In der Booleschen Algebra gibt es für Variablen oder Ausdrücke nur zwei mögliche Werte: „wahr“ und „falsch“ (1 und 0). Mit diesen beiden Werten und logischen Operatoren wie und, oder und nicht können komplexe logische Aussagen aufgebaut werden.
Die Boolesche Algebra findet Anwendung in der Schaltungstechnik, in der digitalen Signalverarbeitung, in der Informatik und der Logik, und ist eine Grundlage für die Entwicklung digitaler Schaltungen, Rechner und Algorithmen.
Für die Verknüpfungen der Boolschen Algebra gibt es einige Schreibweisen, diese werden in der untenstehenden Tabelle zusammengefasst:
| Operation | Schreibweise 1 | Schreibweise 2 | Bezeichnung | Bedeutung |
|---|---|---|---|---|
| UND | $A \land B$ | $A \cdot B$ | Konjunktion | Wahr, wenn A und B wahr sind |
| ODER | $A \lor B $ | $A + B$ | Disjunktion | Wahr, wenn A oder B (oder beide) wahr ist |
| NICHT | $ \overline{A} $ | $\lnot A $ | Negation | Wahr, wenn A falsch ist |
Aufgabe 1
Wir betrachten die folgende Boolsche Funktion: Es werden drei Bits als Eingabe verarbeitet und die Ausgabe ist ein Bit, welches angibt, ob die durch die drei Bits dargestellte Zahl durch 3 teilbar ist.
- Gib die Wahrheitstabelle der Funktion an
- Gib die Funktion als logischen Ausdruck an
- Realisiere die Schaltung der Funktion im Programm von Sebasian Lague
Aufgabe 2
Stelle die NOR-Funktion mit allen Repräsentationsformen dar (Wahrheitstabelle, Logischer Ausdruck, Schaltung).
Aufgabe 3
Stelle die De Morganschen Gesetze mit einem Ven-Diagramm dar.
- Welche Standardgatter gibt es, was bedeuten sie und wie stellt man sie dar (NOT, AND, OR, XOR, NAND, XNOR)?
- Stelle die NOR-Funktion mit allen Repräsentationsformen dar.
- Was sagen die De Morganschen Gesetze aus?
- Was ist die Disjunktive Normalform und wie findet man diese aus der Wahrheitstabelle?
- Was ist die Konjunktive Normalform und wie findet man sie aus der Wahrheitstabelle?
- Was sind logische Nachbarn und inwiefern kann man mit ihrer Hilfe eine Disjunktive Normalform vereinfachen?
- Wie kann eine logische Gleichung mithilfe des KV-Diagramms vereinfacht werden? (Achtung: dies läuft über die Disjunktive Normalform, die Konjunktive Normalform lässt sich nicht so ohne Weiteres minimieren)
- Gegeben ist Funktion, welche testet, ob eine Zahl mit vier Bit durch drei teilbar ist. Gib diese Funktion als Wahrheitstabelle und als logischen Term in der Disjunktiven bzw. Konjunktiven Normalform an. Minimiere die Normalform mit dem KV Diagramm und realisiere die Funktion als Schaltung im Programm von Sebastian Lague.
Links zum Stoff
Erklärung der Grundlagen: Electrical Engeneering for ETH Students
Die Playlist mit den 6 Kurzen Videos erklärt alles: Schrack for Students Gattergrundlagen
Weitere Beispiele/Erklärung zur Disjunktiven/Konjunktiven Normalform Disjunktive Normalform (NLogSpace) und Konjunktive Normalform (NLogSpace)
Lernziele
- Darstellungsarten von Logischen Funktionen verstehen und umschreiben können: Logischer Ausdruck (Formel), Wahrheitstabelle, Schaltung (nicht relevant: Zeitdiagramm).
- Standardgatter verstehen (Darstellung nach IEC 60617-12 kennen, siehe diesen Link) NOT, AND, OR, XOR, NAND, XNOR?
- Wissen, was die De Morganschen Gesetze aussagen und einen Term damit umschreiben können.
- Disjunktive Normalform verstehen und sie aus der Wahrheitstabelle aufstellen können.
- Konjunktive Normalform verstehen und sie aufstellen können.
- Logische Nachbarn verstehen und Terme mit logischen Nachbarn vereinfachen können.
- Die Disjunktive Normalform mithilfe des KV-Diagramms vereinfachen können (Diagramm wird gegeben).
- Schaltung zu einer gegebenen einfachen logischen Funktion aufschrieben können.