Wertemenge und Variablen
Boolesche Ausdrücke beinhalten Konstanten, die man "wahr" und falsch", "true" und "false" oder einfacher "1" und "0" nennt. Mit diesen Zahlen kann man rechnen, indem man sie miteinander verknüpft. Variablen sind im Folgenden immer entweder 0 oder 1.
Verknüpfungen
Man unterscheidet Verknüpfungen nach der Anzahl der Variablen, die miteinander verknüpft werden und nach der Funktion, die sie berechnen. Die Funktion, die sie berechnen, stellt man in einer Tabelle zusammen. Dabei bezeichnen die ersten Spalten immer die Belegung der Variablen, die letzte Spalte zeigt, was die Funktion bei der Belegung ergibt:
NOT / Nicht /Negation
Eine typische einstellige Verknüpfung ist NOT:
NOT erzeugt immer das Gegenteil. Die folgende Tabelle stellt das dar:
|
|
---|---|
0 | 1 |
1 | 0 |
AND / Und
Für zwei Variablen ist AND genau dann "1", wenn die erste und die zweite Variable beide "1" sind. Die Funktion ist über die folgende Wertetabelle definiert;
|
| |
---|---|---|
0 | 0 | 0 |
0 | 1 | 0 |
1 | 0 | 0 |
1 | 1 | 1 |
OR / Oder
Für zwei Variablen ist OR genau dann "1", wenn mindestens eine der Variablen "1" ist. Die Funktion ist über die folgende Wertetabelle definiert:
|
| |
---|---|---|
0 | 0 | 0 |
0 | 1 | 1 |
1 | 0 | 1 |
1 | 1 | 1 |
(Das Zeichen für OR erinnert an ein "v" für "vel", lateinisch für "oder")
NAND / Und nicht
NAND ist eine Verknüpfung, die AND und NOT miteinander verknüpft. Sie ist folgendermaßen definiert:
|
| |
---|---|---|
0 | 0 | 1 |
0 | 1 | 1 |
1 | 0 | 1 |
1 | 1 | 0 |
Manchmal schreibt man NAND auch mit einem senkrechten Strich, also oder einfach mit dem Wort "NAND".
NOR / Weder noch
NOR ist eine Verknüpfung, die OR und NOT miteinander verknüpft. Sie ist folgendermaßen definiert:
|
| |
---|---|---|
0 | 0 | 1 |
0 | 1 | 0 |
1 | 0 | 0 |
1 | 1 | 0 |
XOR / Exklusives Oder / Entweder oder
XOR ist eine Verknüpfung, die genau dann "1" ist, wenn genau eine der Variablen "1" ist. Sie ist folgendermaßen definiert:
|
| |
---|---|---|
0 | 0 | 0 |
0 | 1 | 1 |
1 | 0 | 1 |
1 | 1 | 0 |
Oft schreibt man auch einfach
Anzahl der n-stelligen Funktionen
Wenn eine Variable ist, dann kann man folgende Funktionen mit nur einer Variablen finden:
|
|
|
|
|
---|---|---|---|---|
0 | 0 | 0 | 1 | 1 |
1 | 0 | 1 | 0 | 1 |
Es gibt also 4 Funktionen mit nur einem Argument. Davon sind zwei Funktionen praktisch unabhängig vom Argument.
ist die Nullfunktion, f3 die Einsfunktion, diese beiden Funktionen werten das Argument nicht aus, sondern sind konstant,
ist die Identitätsfunktion,
Die Funktion ist dabei die schon bekannte Funktion NOT.
Für Null Argumente gibt es die beiden konstanten Funktionen 0 und 1.
Es gibt die folgenden 2-stelligen Funktionen:
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
0 | 0 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 |
0 | 1 | 0 | 0 | 1 | 1 | 0 | 0 | 1 | 1 | 0 | 0 | 1 | 1 | 0 | 0 | 1 | 1 |
1 | 0 | 0 | 0 | 0 | 0 | 1 | 1 | 1 | 1 | 0 | 0 | 0 | 0 | 1 | 1 | 1 | 1 |
1 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
Allgemeine boolesche Ausdrücke
Zu Booleschen Ausdrücken gehört eine Variablenmenge X = {, , …, } und Operatoren aus der in diesem Kapitel dargestellten Menge. Ein einfacher Boolescher Ausdruck kann aus einer Variablen oder der Negation dieser Variablen bestehen. Allgemein gilt: Ist e ein Boolescher Ausdruck, dann sind
ebenfalls Boolesche Ausdrücke.
Um die Klammern sparen zu können, legt man folgendes fest: Die Negation bindet am stärksten. Dann folgt AND und zum Schluss OR. Um Schreibarbeit zu ersparen, kann der AND-Operator auch weggelassen werden.
Der Ausdruck wird also als geschrieben.