So wie wir aus einzelnen Bits komplexe Daten kodieren können, lässt sich ein kompletter Computer bauen, indem die logischen Operationen UND, ODER und NICHT kombiniert werden. Zunächst lernen wir, mithilfe der Booleschen Algebra logische Berechnungen durchzuführen, und konstruieren anschließend Schaltkreise aus Gattern. Schließlich erfahren wir, wie komplexere Funktionalitäten wie Addition oder Multiplikation realisiert werden können.
Dieses Kapitel baut auf der @lialink(Einführung in die Aussagenlogik) auf.
Für einen Gesamtüberblick über den Kurs geht es @lialink(hier zurück zur Kursübersicht).
Den Begriff der Algebra kennen Sie sicherlich aus der Mathematik. Er beschreibt einen Satz von Regeln, mit dem man Berechnungen durchführen kann. So erklärt die elementare Algebra, wie wir Zahlen addieren, multiplizieren, substrahieren und dividieren können. Sie verwendet Variablen und erlaubt uns Gleichungen und Ungleichungen aufzustellen. Dabei legt sie fest, welche Regeln man dabei beachten muss.
Die boolesche Algebra hat ihren Namen von George Boole, der sie 1847 in seinem Buch „The Mathematical Analysis of Logic” erfand.
Sie ist eine besondere Form der Algebra, die Regeln beschreibt, wie man mit Wahrheitswerten rechnen kann.
So wie in der elementaren Algebra verwendet man in der booleschen Algebra Variablen, nennt diese aber boolesche Variablen. Sie können nur die Wahrheitswerte wahr und falsch annehmen.
Diese zwei Werte wahr und falsch schreibt man auf englisch true und false oder verwendet die Ziffern
Hier wird deutlich, warum die boolesche Algebra so interessant für die Informatik ist: Da man 1 und 0 verwendet, um digitale Daten zu repräsentieren, erlaubt uns diese Algebra Berechnungen auf diesen Daten zu definieren.
Für diese Berechnungen verwendet man die Operationen oder Verknüpfungen der booleschen Algebra: UND, ODER, und NICHT.
Diese kennen Sie bereits von den Grundlagen der Aussagenlogik im @lialink(ersten Kurskapitel)
Eine boolesche Funktion ist eine mathematische Funktion, die boolesche Variablen als Eingabe verwendet und Boolesche Werte (1 oder 0) als Ausgabe liefert.
Jedem möglichen Satz von Eingangsvariablen wird dabei ein eindeutiger Ausgangswert zugewiesen.
Notiert man für jede mögliche Kombination von Eingangsvariablen den Ausgangswert, erhält man eine Wahrheitstabelle, die die Funktion charakterisiert.
Für eine Funktion mit einer Eingabevariablen (unär), z.B.
Die Wahrheitstabelle sieht dann so aus:
| 0 | 0 |
| 1 | 1 |
Diese Funktion nennt man auch Identität von
Etwas interessanter ist da die schon die Funktion
| 0 | 1 |
| 1 | 0 |
Bei zwei Eingabewerten gibt es 4 mögliche Kombinationen an Eingabewerten.
Hier die binäre Funktion
| 0 | 0 | 0 |
| 0 | 1 | 0 |
| 1 | 0 | 0 |
| 1 | 1 | 1 |
Bei drei Eingabewerten gibt es bereits 8 verschiedene Eingaben.
Hier die Funktion
| 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 |
Analysieren Sie die Wahrheitstabelle der Funktion
- [( )]
$F_4$ ist genau dann wahr, wenn mindestens eine Eingangsvariable wahr ist. - [( )]
$F_4$ ist die sogenannte Parity-Funktion, die Ausgabe ist 1 genau dann, wenn die Summe der Eingabebits gerade ist. - [(X)]
$F_4$ ist die sogenannte Mehrheitsfunktion, die Ausgabe ist 1 genau dann, wenn die Mehrheit der Eingabebits 1 ist.
Es gibt nur 16 verschiedene binäre boolesche Funktionen. Jede davon ist eindeutig durch die Abfolge der Ausgabewerte in der Wahrheitstabelle charakterisiert.
Für 0001, für 0111.
Welche neuen Funktionen können Sie in der interaktiven Wahrheitstabelle entdecken?
Klicken Sie auf die Zahlen in der Ergebnisspalte um die Funktion zu verändern, links können Sie dann das Verhalten der Funktion testen Einige Funktionen haben spezielle Namen oder sogar besondere Symbole. Versuchen Sie herauszufinden was die Namen oder Symbole bedeuten könnten.
@embed(style="height: 455px; width:800px; border: none")
Wie Sie gesehen haben, können wir eine boolesche Funktion eindeutig durch ihre Wahrheitstabelle darstellen. Oft ist es jedoch einfacher, einen booleschen Ausdruck zu notieren.
So können wir für die UND-Funktion
Das nennt man einen booleschen Ausdruck.
-
$0$ und$1$ sind boolesche Ausdrücke - Jede boolesche Variable (z.B.
$x$ oder$a$ ) ist ein boolescher Ausdruck - Sind
$t_0$ und$t_1$ boolesche Ausdrücke, so auch:
a)$t_0∧t_1$
b)$t_0∨t_1$
c)$¬t_0$
Wenn der Ausdruck eindeutig ist, können die Klammern weggelassen werden.
Eine solche Definition nennt man rekursiv: durch wiederholte Anwendung der Regeln kann man komplexe boolesche Ausdrücke aufbauen.
-
$x$ ist ein boolescher Ausdruck (BA) -
$¬x$ ist ein BA (Wende Regel 3c auf 1 an) -
$y$ ist ein BA -
$¬x∨y$ ist ein BA (Wende Regel 3b auf 2 und 1 an)
Um mit booleschen Ausdrücken rechnen zu können, müssen wir die Rechengesetze für unsere booleschen Verknüpfungen und Ausdrücke festlegen.
Die mathematische Struktur, auf der diese Rechenregeln basieren, nennt man boolesche Algebra:
Eine boolesche Algebra ist eine Menge
- Kommutativgesetze
- Assoziativgesetze
- Distributivgesetze
- Komplementärgesetze
- Neutralitätsgesetze
Die Kommutativ- und Assoziativgesetze kennen Sie bereits aus der elementaren Algebra. Auch die Neutralitätsgesetze gelten ähnlich für Addition und Multiplikation. Die boolesche Algebra kennt aber zwei Distributivgesetze anstatt nur einem und außerdem noch die Komplementärgesetze.
Die folgenden Gleichungen sind alle korrekt. Wählen Sie aus, welches Gesetz der Booleschen Algebra zur Anwendung kam.
$$ \neg(x\vee y) \wedge (x\vee y) = 0 $$ [[ Kommutativ | Distributiv | Assoziativ | (Komplementär) | Neutralität ]] $$ (x\vee z)\wedge \neg (z\vee y)=\neg (z\vee y)\wedge (x\vee z) $$ [[ (Kommutativ) | Distributiv | Assoziativ | Komplementär | Neutralität ]] $$ (x\vee y)\vee (z\vee x) = x\vee(y\vee(z\vee x)) $$ [[ Kommutativ | Distributiv | (Assoziativ) | Komplementär | Neutralität ]] $$ \neg x\wedge(x\vee y) = (\neg x\wedge x)\vee(\neg x\wedge y) $$ [[ Kommutativ | (Distributiv) | Assoziativ | Komplementär | Neutralität ]] $$ (x\wedge y)\vee(x\wedge z)\vee 0 = (x\wedge y)\vee(x\wedge z) $$ [[ Kommutativ | Distributiv | Assoziativ | Komplementär | (Neutralität) ]]
Aus der Definition der Booleschen Algebra lassen sich noch weitere Gesetze ableiten, die es einfacher machen, boolesche Ausdrücke umzuformen.
Die Idempotenzgesetze besagen zum Beispiel, dass ein Wert, der mit sich selbst verknüpft wird, seinen Wert nicht ändert:
Dieses Gesetz ist nicht notwendigerweise Bestandteil der Definition, da es sich aus den bereits bekannten Gesetzen herleiten lässt:
Das erste Neutralitätsgesetz ist
$$
x = x\vee 0
$$
Wenden wir das Komplementärgesetz rückwärts an, können wir
$$
x = x\vee (x \wedge \neg x)
$$
Nach dem zweiten Distributivgesetz ist das gleich
$$
x = (x\vee x) \wedge (x \vee \neg x)
$$
das entspricht nach dem ersten Komplementärgesetz
$$
x = (x\vee x) \wedge 1
$$
und nach dem zweiten Neutralitätsgesetz wissen wir, dass eine Konjunktion mit 1 weggelassen werden kann.
So erhalten wir
$$
x = x\vee x \quad \square
$$
In diesem Beweis wird gezeigt, wie die Gesetze der booleschen Algebra verwendet werden, um boolesche Ausdrücke zu vereinfachen.
Beachten Sie, dass die Variablen
So erhalten wir im letzten Schritt des Beweises im Ausdruck
Welcher der folgenden Ausdrücke vereinfacht sich mit dem Idempotenzgesetz zu $ x \lor y $?
- [( )] $ (x \land x) \lor y $
- [( )] $ x \land (y \lor y) $
- [(X)] $ (x \lor x) \lor y $
- [( )] $ (x \lor y) \land (x \lor x) $
Die Disjunktion mit
$$
\quad x\vee 1 = 1
$$
$$
\quad x\wedge 0 = 0
$$
Die Extremalgesetze können sehr hilfreich in der praktischen Anwendung sein:
- Wenn mehrere Bedingungen gleichzeitig wahr sein müssen, kann man schon bei der ersten falschen Bedingung die Auswertung abbrechen.
- Reicht es, wenn nur eine von vielen Bedingungen erfüllt ist, so ist nach der ersten wahren Bedingung bereits bekannt, dass der Gesamtausdruck wahr sein muss.
$$ (y \wedge \neg z) \vee (\neg x\vee x) $$ vereinfacht sich nach dem Komplementärgesetz zu
und ist damit nach dem Extremalgesetz immer
Betrachten Sie den booleschen Ausdruck $$ (a \land \lnot (b \lor \lnot b)) $$
zu welchem Ausdruck lässt dieser sich vereinfachen?
- [( )] $ 1 $
- [(X)] $ 0 $
- [( )] $ a $
- [( )] $ b $
Die doppelte Negation eines Ausdrucks ist also gleich dem ursprünglichen Ausdruck.
Das Doppelnegationsgesetz kennen wir auch aus dem Alltag:
Ich gehe nicht ohne Regenschirm aus dem Haus,
ist eine doppelte Negation und damit logisch äquivalent zu
Ich gehe mit Regenschirm aus dem Haus
Die De-morganschen Gesetze erlauben es, mit Hilfe der Negation NICHT eine Disjunktion als Konjunktion oder eine Konjunktion als Disjunktion zu schreiben. Das führt zu der Erkenntnis, dass jeder boolesche Ausdruck mit nur zwei booleschen Verknüpfungen dargestellt werden kann (eine davon muss die Negation sein).
Dieses Gesetz lässt sich auch mit einem Alltagsbeispiel veranschaulichen:
Jemand, der keine tierischen Produkte isst, sagt den Satz:
Wenn Fleisch oder Eier im Essen sind, esse ich es nicht.
Anders könnte man auch formulieren:
Wenn ich das Essen esse, sind keine Eier und kein Fleisch enthalten.
Das entspricht dem zweiten De-morganschen Gesetz.
Wir wollen den Ausdruck
$$ a \vee b $$
mit Hilfe der De-morganschen Gesetze ohne die Disjunktion ODER schreiben.
Welcher der folgenden Ausdrücke ist äquivalent?
- [(X)] $ \neg(\neg a \wedge \neg b) $
- [( )]
$(\neg a \wedge \neg b) $ - [( )]
$(a \wedge b) $ - [( )]
$\neg (a \wedge b) $
Das zweite De-Morgan'sche Gesetz lautet:
Wir negieren beide Seiten: $$ \neg \left( \neg (a \lor b) \right) = \neg (\neg a \land \neg b) $$
Die doppelte Negation auf der linken Seite vereinfacht sich zu: $$ a \lor b = \neg (\neg a \land \neg b) $$
Und so sehen wir direkt, dass $ \neg(\neg a \wedge \neg b) $ die richtige Antwort ist.