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 berechen. 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}\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:

$$x_1$$

$$x_2$$

$$x_{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:

$$x_1$$

$$x_2$$

$$\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 %%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$$

$$\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:

$$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 XOR 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.

  • f0 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.

Wie viele 2-stellige Funktionen gibt es?

Es gibt 16 2-stellige Funktionen.

Es gibt die folgenden 2-stelligen Funktionen:

$$x_1$$

$$x_2$$

$$f_0$$

$$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

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

Welche der obigen Funktion ist die AND-Funktion?

$$f_8$$

Welche der obigen Funktion ist die OR-Funktion?

$$f_{14}$$

Welche der obigen Funktionen ist die Identitätsfunktion vom ersten bzw. zweiten Argument?

$$f_{12}$$ und $$f_{10}$$

Wie lautet die allgemeine Formel für die Anzahl der n-stelligen Funktionen?

Allgemein gibt es $$2^{2^n}$$ n-stellige Funktionen.

Allgemeine boolesche Ausdrücke

Zu Booleschen Ausdrücken gehört eine Variablenmenge X = {x1, x2, …, xn} 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\\(\overline e)\\(e_1 \vee e_2)\\(e_1 \wedge e_2)\\f(e_1, e_2, …, 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\wedge e_2)\vee ((\overline e3) \wedge e_2)%% wird also als %%e_1e_2\vee\overline{e_3} \;e_2%% geschrieben.

Kommentieren Kommentare

Zu article Boolesche Ausdrücke: Inhalt Überschneidung
Knorrke 2015-11-13 15:32:56
Zu Booleschen Ausdrücken hat @horotab bereits in einem Kurs ein paar Inhalte erstellt, vielleicht kann man daraus etwas hier gebrauchen? - https://de.serlo.org/47876

Außerdem existiert noch die Seite in der Mathematik ( https://de.serlo.org/2083 ). Fände ich super, wenn man das irgendwie vernetzen kann!

Viele Grüße,
Benjamin
eike 2015-11-14 16:01:41
Hallo zusammen,

die Darstellung von "Logik" in der Mathematik ist oft anders als die Darstellung von Bool'schen Ausdrücken in der technischen Informatik. Auch wenn beides "irgendwie gleich" ist, geht es in der technischen Informatik letztlich um "wie bastel ich einen Computer". Das führt zu unterschiedlichen Darstellungen. Auch sind manche Ausdrücke der Mathematik in der TI nicht zu gebrauchen, wie zum Beispiel die Implikation. Ich würde daher gerne beide Bereiche vorerst getrennt behandeln - auch wenn sie sie wesensgleich sind.
VG
Eike
Antwort abschicken