Springe zum Inhalt oder Footer
SerloDie freie Lernplattform

Boolesche Ausdrücke

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:

xx

¬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;

x1x_1

x2x_2

x1x2x_{1}\wedge 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:

x1x_1

x2x_2

x1x2x_{1}\vee 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:

x1x_1

x2x_2

(x1x2)\overline{(x_1\wedge x_2)}

0

0

1

0

1

1

1

0

1

1

1

0

Manchmal schreibt man NAND auch mit einem senkrechten Strich, also x1x2x_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:

x1x_1

x2x_2

(x1x2)\overline{(x_1\vee 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:

x1x_1

x2x_2

(x1x2)(x_1 \oplus x_2)

0

0

0

0

1

1

1

0

1

1

1

0

Oft schreibt man auch einfach (x1XORx2)(x_1 XOR x_2)

Anzahl der n-stelligen Funktionen

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

xx

f0(x)f_0(x)

f1(x)f_1(x)

f2(x)f_2(x)

f3(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.

  • f0f_0 ist die Nullfunktion, f3 die Einsfunktion, diese beiden Funktionen werten das Argument nicht aus, sondern sind konstant,

  • f1f_1 ist die Identitätsfunktion,

  • Die Funktion f2f_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:

x1x_1

x2x_2

f0f_0

f1f_1

f2f_2

f3f_3

f4f_4

f5f_5

f6f_6

f7f_7

f8f_8

f9f_9

f10f_{10}

f11f_{11}

f12f_{12}

f13f_{13}

f14f_{14}

f15f_{15}

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 = {x1x_1, x2x_2, …, xnx_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

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 ((e1e2)((e3)e2)( (e_1\wedge e_2)\vee ((\overline e3) \wedge e_2) wird also als e1e2e3  e2e_1e_2\vee\overline{e_3} \;e_2 geschrieben.


Dieses Werk steht unter der freien Lizenz
CC BY-SA 4.0Was bedeutet das?