Boolesche Ausdrücke - lernen mit Serlo!

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:

\neg x

NOT erzeugt immer das Gegenteil. Die folgende Tabelle stellt das dar:

$x$	$\neg x$
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;

$x_{1}$	$x_{2}$	$x_{1} \land x_{2}$
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:

$x_{1}$	$x_{2}$	$x_{1} \lor x_{2}$
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:

$x_{1}$	$x_{2}$	$(x_{1} \land x_{2})$
0	0	1
0	1	1
1	0	1
1	1	0

Manchmal schreibt man NAND auch mit einem senkrechten Strich, also $x_{1} | x_{2}$ 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:

$x_{1}$	$x_{2}$	$(x_{1} \lor x_{2})$
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:

$x_{1}$	$x_{2}$	$(x_{1} \oplus︎ x_{2})$
0	0	0
0	1	1
1	0	1
1	1	0

Oft schreibt man auch einfach $(x_{1} X O R x_{2})$

Anzahl der n-stelligen Funktionen

Wenn $x$ eine Variable ist, dann kann man folgende Funktionen mit nur einer Variablen finden:

$x$	$f_{0} (x)$	$f_{1} (x)$	$f_{2} (x)$	$f_{3} (x)$
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.

$f_{0}$ ist die Nullfunktion, f3 die Einsfunktion, diese beiden Funktionen werten das Argument nicht aus, sondern sind konstant,
$f_{1}$ ist die Identitätsfunktion,
Die Funktion $f_{2}$ 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:

$x_{1}$	$x_{2}$	$f_{1}$	$f_{2}$	$f_{3}$	$f_{4}$	$f_{5}$	$f_{6}$	$f_{7}$	$f_{8}$	$f_{9}$	$f_{10}$	$f_{11}$	$f_{12}$	$f_{13}$	$f_{14}$	$f_{15}$
0	0	1	0	1	0	1	0	1	0	1	0	1	0	1	0	1
0	1	0	1	1	0	0	1	1	0	0	1	1	0	0	1	1
1	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	1	1	1	1	1	1	1	1

Allgemeine boolesche Ausdrücke

Zu Booleschen Ausdrücken gehört eine Variablenmenge X = { $x_{1}$ , $x_{2}$ , …, $x_{n}$ } 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

\begin{array}{l} e \\ (e) \\ (e_{1} \lor e_{2}) \\ (e_{1} \land e_{2}) \\ f (e_{1}, e_{2}, \dots, e_{n}) \end{array}

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 $((e_{1} \land e_{2}) \lor ((e 3) \land e_{2})$ wird also als $e_{1} e_{2} \lor e_{3} e_{2}$ geschrieben.

$x_{1}$	$x_{2}$	$f_{1}$	$f_{2}$	$f_{3}$	$f_{4}$	$f_{5}$	$f_{6}$	$f_{7}$	$f_{8}$	$f_{9}$	$f_{10}$	$f_{11}$	$f_{12}$	$f_{13}$	$f_{14}$	$f_{15}$
0	0	1	0	1	0	1	0	1	0	1	0	1	0	1	0	1
0	1	0	1	1	0	0	1	1	0	0	1	1	0	0	1	1
1	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	1	1	1	1	1	1	1	1

$x_{1}$	$x_{2}$	$f_{1}$	$f_{2}$	$f_{3}$	$f_{4}$	$f_{5}$	$f_{6}$	$f_{7}$	$f_{8}$	$f_{9}$	$f_{10}$	$f_{11}$	$f_{12}$	$f_{13}$	$f_{14}$	$f_{15}$
0	0	1	0	1	0	1	0	1	0	1	0	1	0	1	0	1
0	1	0	1	1	0	0	1	1	0	0	1	1	0	0	1	1
1	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	1	1	1	1	1	1	1	1

$x_{1}$	$x_{2}$	$f_{1}$	$f_{2}$	$f_{3}$	$f_{4}$	$f_{5}$	$f_{6}$	$f_{7}$	$f_{8}$	$f_{9}$	$f_{10}$	$f_{11}$	$f_{12}$	$f_{13}$	$f_{14}$	$f_{15}$
0	0	1	0	1	0	1	0	1	0	1	0	1	0	1	0	1
0	1	0	1	1	0	0	1	1	0	0	1	1	0	0	1	1
1	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	1	1	1	1	1	1	1	1