Boolesche Algebra

Logische Grundfunktionen der Digitaltechnik

Eine der wichtigsten Funktionen der Digitaltechnik ist es, Entscheidungen treffen zu können. Anhand von Regeln wird ausgewertet welche Instruktion als nächste im Computer ausgeführt wird.

Zur Definition dieser Regeln verwenden wir Boolesche Algebra.

Boolesche Algebra

Ist benannt nach dem Mathematiker George Boole (England, 1815-1864).

Bei der booleschen Algebra werden Werte in binärer Form dargestellt. Die boolesche Algebra kennt also genau zwei mögliche Werte: wahr und falsch, bzw. auf englisch true und false.

Verknüpfung von Werten

Damit Entscheidungen anhand von booleschen Werten getroffen werden können, werden diese verknüpft.

Grundlegende Funktionen zum Verknüpfen sind UND, ODER, NICHT.

Ein erstes Beispiel

Angenommen ein Benutzer meldet sich auf einer Website an. Er navigiert zu einer Seite für den Verein in dem er Mitglied ist. Die Seite hat auch einen Admin-Bereich in den nur Personen zutritt haben, die sowohl Vereinsmitglied, als auch im Vorstand des Vereins tätig sind.

Die Regel ob der Benutzer zum Admin-Bereich darf ist also:
IstVereinsmitglied UND IstVorstand

Ein erstes Beispiel (2)

In diesem Beispiel arbeiten wir mit zwei booleschen Werten: IstVereinsmitglied, IstVorstand

Beide dieser Werte können entweder wahr/true oder falsch/false sein.

Nur wenn beide Werte wahr/true sind, hat der Benutzer Zugriff auf den Admin-Bereich. Das drücken wir mit der Verknüpfung UND aus.

Wahrheitstabellen

Für die booleschen Verknüpfungsfunktionen existieren sogenannte Wahrheitstabellen. Sie geben an, was das Resultat ist, wenn man die Funktionen auf Wahrheitswerte anwendet.

Anstatt der Werte true und false verwenden wir auch oft die Kurzschreibweise:
1 (für true) und 0 (für false).

Wahrheitstabelle für UND

(auch AND, Konjunktion genannt)

A	B	A UND B
0	0	0
0	1	0
1	0	0
1	1	1

Bei einer UND Verknüpfung ist die einzige Möglichkeit als Ergebnis true zu bekommen, wenn beide zu verknüpfenden Werte auch true sind.

Wahrheitstabelle für ODER

(auch OR, Disjunktion genannt)

Bei der ODER Verknüpfung reicht es, wenn einer der beiden Werte true ist. Es ist egal welcher davon. Auch wenn beide Werte true sind, ist das Ergebnis true.

A	B	A ODER B
0	0	0
0	1	1
1	0	1
1	1	1

Wahrheitstabelle für XODER

(auch exklusives Oder, XOR, Kontravalenz genannt)

Die XODER Verknüpfung ist ähnlich der ODER Verknüpfung, allerdings darf nur einer der beiden Eingangswerte true sein.

A	B	A XODER B
0	0	0
0	1	1
1	0	1
1	1	0

Wahrheitstabelle für NICHT

Die Funktion NICHT bietet einen Spezialfall, da sie nicht mit zwei Eingangswerten arbeitet, sondern nur mit einem. Die Funktion NICHT invertiert diesen.

A	NICHT A
0	1
1	0

Schreibweisen

Folgende Schreibweisen existieren für die einzelnen Funktionen.

	UND	ODER	XODER	NICHT
Boolesche Algebra	$\land$	$\lor$	$\oplus$	$\neg$
Mathematisch	$\cdot$	$+$	$\not\equiv$	$-$

Beispiel

Für das Beispiel für den Zugriff auf den Admin-Bereich könnte man folgenden booleschen Ausdruck verwenden:
IstVereinsmitglied $\land$ IstVorstand

Die Wahrheitstabelle für die Funktion UND verrät uns ob der Benutzer zugriff auf den Admin-Bereich hat:

IstVereinsmitglied	IstVorstand	HatZugriff
0	0	0
1	0	0
0	1	0
1	1	1

Verknüpfung mehrerer Werte

Will man mehr als zwei Werte miteinander Verknüpfen, so muss die Auswertung schrittweise erfolgen.

Zum Beispiel könnte man sagen, dass für das Beispiel von vorhin es eine Ausnahme gibt. Wenn jemand ein Passwort für den Admin-Bereich bekommt, muss er weder Vereinsmitglied, noch Vorstand sein.

Die Regel ob die Person zutritt hat würde lauten:
(IstVereinsmitglied $\land$ IstVorstand) $\lor$ BesitztPasswort

Wir verwenden Klammern um zu zeigen, welcher Teil zuerst ausgewertet werden soll.

Verknüpfung mehrerer Werte (2)

Für die Auflösung des Beispiels
(IstVereinsmitglied $\land$ IstVorstand) $\lor$ BesitztPasswort
wird zuerst die UND Verknüpfung
IstVereinsmitglied $\land$ IstVorstand
aufgelöst und anschließend das Ergebnis davon für die ODER Verknüpfung mit BesitztPasswort verwendet

Beispiel mehrere Werte

(IstVereinsmitglied $\land$ IstVorstand) $\lor$ BesitztPasswort

Angenommen wir arbeiten mit folgenden Werten:


IstVereinsmitglied	1
IstVorstand	0
BesitztPasswort	1

Wir lösen zuerst den Teil in der Klammer. Die Wahrheitstabelle für UND sagt uns dass wir bei den Eingangswerten 1 und 0 als Ergebnis 0 bekommen.

Es bleibt also: 0 $\lor$ BesitztPasswort

BesitztPasswort hat den Wert 1. Die Wahrheitstabelle für ODER sagt uns, dass bei 0 und 1 als Eingangswerte als Ergebnis 1 herauskommt.

Der Benutzer hat also Zugriff.

Weitere Verknüpfungsfunktionen

Implikation

Schreibweise: $A \implies B$

(eine Aussage impliziert eine andere Aussage)

A impliziert B
aus A folgt B
A ist hinreichend für B
B ist notwendig für A
wenn A, dann B
A nur dann, wenn B

Reihenfolge von A und B ist wichtig!

Wahrheitstabelle für Implikation

A	B	$A \implies B$
0	0	1
0	1	1
1	0	0
1	1	1

Achtung: die Implikation gilt auch dann als wahr, wenn die Prämisse (das ist die Teilaussage links vom $\implies$ ) falsch ist.

Das ist ungewohnt, weil auch Sätze wie “Wenn Krems am Mittelmeer liegt, ist 4 eine Primzahl” “wahr” sind.

Äquivalenz

Schreibweise: $A \Longleftrightarrow B$

(zwei Aussagen sind äquivalent, also gleichwertig)

A und B sind äquivalent
A ist notwendig und hinreichend für B
A dann und nur dann, wenn B
A genau dann, wenn B

Reihenfolge von A und B ist egal.

Wahrheitstabelle für Äquivalenz

A	B	$A \Longleftrightarrow B$
0	0	1
0	1	0
1	0	0
1	1	1

Zusammenfassung Wahrheitstabellen

A	B	$\neg A$	$A \land B$	$A \lor B$	$A \oplus B$	$A \implies B$	$A \Longleftrightarrow B$
0	0	1	0	0	0	1	1
0	1	1	0	1	1	1	0
1	0	0	0	1	1	0	0
1	1	0	1	1	0	1	1

Atomare Aussagen

Wir haben bis jetzt eine Form von atomaren Aussagen kennen gelernt. Eine Aussage (zB IstVereinsmitglied) kann entweder wahr oder falsch sein.

Das ist die einfachste Form einer atomaren Aussage.

Atomare Aussagen mittels Vergleichsoperatoren

Eine atomare Aussage kann auch mittels Vergleichsoperatoren ausgedrückt werden. Dabei vergleichen wir (wie der Name schon sagt) zwei Werte miteinander. Das Ergebnis des Vergleichs ist ein Wahrheitswert.

Zum Beispiel: $5 > 2$
Das Ergebnis dieser Aussage ist wahr.

Vergleichsoperatoren

Operator	Bedeutung
$>$	größer als
$\lt$	kleiner als
$\ge$	größer oder gleich
$\le$	kleiner oder gleich
$=$	gleich
$\ne$	ungleich

Beachte: Die ersten vier Operatoren sind nur für numerische Vergleiche. Gleich und Ungleich können beliebige Werte miteinander vergleichen.