Boolesche Funktion

Wenn dein Handy entscheidet, ob eine Sperre aufgeht, oder ein Spiel prüft, ob zwei Bedingungen gleichzeitig gelten, steckt oft dieselbe Idee dahinter: Es gibt nur zwei Möglichkeiten, ja oder nein. Boolesche Funktionen beschreiben solche Entscheidungen sauber mit 0 und 1.

Nach dieser Erklärung kannst du Wahrheitstabellen lesen, einfache Schaltfunktionen als Formel schreiben und erkennen, warum schon wenige Eingänge sehr viele mögliche Funktionen ergeben.

Deine Lernziele

• Ich kann erklären, was eine Boolesche Funktion ist.
• Ich kann die Werte 0 und 1 als falsch und wahr deuten.
• Ich kann eine Wahrheitstabelle zu einer einfachen Booleschen Funktion ausfüllen.
• Ich kann UND, ODER, NICHT und XOR unterscheiden.
• Ich kann aus einer Wahrheitstabelle eine passende Boolesche Formel bauen.
• Ich kann berechnen, wie viele Boolesche Funktionen es bei $n$ Eingangsvariablen gibt.

Die Grundidee

Eine Boolesche Funktion ist eine Funktion für Entscheidungen. Die Eingaben dürfen nur zwei Werte haben: \(0\) oder \(1\). Auch das Ergebnis ist wieder \(0\) oder \(1\).

Definition

Boolesche Funktion

Eine Boolesche Funktion ordnet jeder Kombination aus Booleschen Eingaben genau einen Booleschen Ausgabewert zu. Für \(n\) Eingaben schreibt man oft \(f:\{0,1\}^n \to \{0,1\}\). Dabei steht \(0\) meist für falsch oder aus, \(1\) für wahr oder an.

Das klingt abstrakt, ist aber nah an Technik: Ein Lichtschalter kann offen oder geschlossen sein. Eine Lampe ist aus oder an. Genau solche Zustände passen zu \(0\) und \(1\).

Beispiel

Ein einzelner Schalter \(s\) steuert eine Lampe \(l\).

• Schalter offen: \(s=0\), die Lampe bleibt aus, also \(l=0\).
• Schalter geschlossen: \(s=1\), die Lampe leuchtet, also \(l=1\).

Die Funktion lautet hier einfach \(l=s\). Die Ausgabe übernimmt also den Eingabewert.

Merke

Eine Boolesche Funktion beantwortet für jede erlaubte Eingabekombination eine Ja-Nein-Frage.

Wahrheitstabellen lesen

Damit du eine Boolesche Funktion vollständig kennst, musst du wissen, was bei jeder möglichen Eingabe passiert. Dafür nutzt man eine Wahrheitstabelle.

Definition

Wahrheitstabelle

Eine Wahrheitstabelle listet alle möglichen Eingabekombinationen einer Booleschen Funktion auf. In der letzten Spalte steht jeweils der Ausgabewert.

Bei zwei Eingaben \(a\) und \(b\) gibt es vier Kombinationen: \(00\), \(01\), \(10\) und \(11\). Jede Zeile ist ein anderer Fall, den die Funktion entscheiden muss.

Beispiel

Die Funktion \(y=a \land b\) bedeutet: \(y\) ist genau dann \(1\), wenn \(a\) und \(b\) beide \(1\) sind.

\(a\)	\(b\)	\(y=a \land b\)
0	0	0
0	1	0
1	0	0
1	1	1

Schritt für Schritt:

1. Prüfe jede Zeile einzeln.
2. Bei UND reicht eine einzige \(0\), damit das Ergebnis \(0\) wird.
3. Nur in der letzten Zeile stehen beide Eingaben auf \(1\).

Gut zu wissen

Das Zeichen \(\land\) liest du als "und". In Programmiersprachen begegnet dir dieselbe Idee oft als and, && oder in Bedingungen wie "Passwort stimmt UND Konto ist aktiv".

Die wichtigsten Grundfunktionen

Viele Boolesche Funktionen werden aus wenigen Grundbausteinen zusammengesetzt. Die drei wichtigsten sind UND, ODER und NICHT.

Definition

Grundfunktionen

Die Grundfunktionen der Schaltlogik sind UND (\(\land\)), ODER (\(\lor\)) und NICHT (\(\lnot\)). UND ist genau dann wahr, wenn alle betrachteten Bedingungen wahr sind. ODER verlangt mindestens eine wahre Bedingung. NICHT kehrt einen Wahrheitswert um.

UND ist streng: Beide Eingaben müssen \(1\) sein. ODER ist lockerer: Mindestens eine Eingabe muss \(1\) sein. NICHT dreht den Wert um.

Beispiel

Vergleiche dieselben Eingaben für UND und ODER.

\(a\)	\(b\)	\(a \land b\)	\(a \lor b\)
0	0	0	0
0	1	0	1
1	0	0	1
1	1	1	1

Für NICHT gilt:

\(a\)	\(\lnot a\)
0	1
1	0

Du kannst dir merken: UND fragt "alles erfüllt?", ODER fragt "mindestens eins erfüllt?", NICHT fragt "gerade nicht?".

Eine weitere wichtige Funktion ist XOR, gesprochen "exklusives Oder". In deutschen Tabellen heißt sie auch Antivalenz. Sie ist wahr, wenn genau eine der beiden Eingaben wahr ist.

Beispiel

Bei \(y=a \oplus b\) gilt:

\(a\)	\(b\)	\(y=a \oplus b\)
0	0	0
0	1	1
1	0	1
1	1	0

Warum ist die letzte Zeile \(0\)? Weil XOR nicht "mindestens eine", sondern "genau eine" wahre Eingabe meint.

Von der Tabelle zur Formel

Eine Boolesche Funktion kann als Wahrheitstabelle oder als Formel dargestellt werden. Die Formel nennt man oft Booleschen Ausdruck.

Definition

Boolescher Ausdruck

Ein Boolescher Ausdruck ist eine Formel aus Booleschen Variablen, Konstanten und Operatoren wie \(\land\), \(\lor\) und \(\lnot\). Er beschreibt dieselbe Funktion wie eine Wahrheitstabelle, aber kompakter.

Der sichere Weg von einer Tabelle zur Formel ist: Suche die Zeilen, in denen \(y=1\) ist. Für jede dieser Zeilen baust du einen UND-Term. Diese Terme verbindest du mit ODER.

Beispiel

Gesucht ist eine Formel für diese Funktion:

\(a\)	\(b\)	\(y\)
0	0	0
0	1	1
1	0	1
1	1	0

1. Markiere die Zeilen mit \(y=1\): Das sind \(a=0,b=1\) und \(a=1,b=0\).
2. Schreibe für \(a=0,b=1\) den Term \(\lnot a \land b\).
3. Schreibe für \(a=1,b=0\) den Term \(a \land \lnot b\).
4. Verbinde beide Fälle mit ODER:

$$ y=(\lnot a \land b)\lor(a \land \lnot b) $$

Das ist wieder die XOR-Funktion.

Merke

Eine Zeile mit Ergebnis 1 wird zu einem UND-Term. Mehrere passende Zeilen werden mit ODER verbunden.

Gut zu wissen

Diese Bauweise heißt genauer kanonische disjunktive Normalform, kurz KDNF. "Disjunktiv" meint hier: Die Treffer-Zeilen werden mit ODER zusammengefügt. In manchen Schulmaterialien steht dafür nur DNF, obwohl eine allgemeine DNF auch kürzere Terme enthalten kann.

Boolesche Algebra liefert außerdem Rechengesetze, mit denen du Formeln vereinfachen oder umformen kannst. Besonders wichtig sind die De-Morgan-Regeln.

Beispiel

De Morgan hilft, eine Negation über eine Klammer zu verteilen:

$$ \lnot(a \land b)=\lnot a \lor \lnot b $$

Probe für \(a=1,b=0\):

• Links: \(a \land b=0\), also \(\lnot(a \land b)=1\).
• Rechts: \(\lnot a=0\) und \(\lnot b=1\), also \(0 \lor 1=1\).

Beide Seiten liefern denselben Wert.

Wie viele Funktionen gibt es?

Die Anzahl der möglichen Eingabekombinationen wächst schnell. Bei \(n\) Eingaben hat jede Eingabe zwei mögliche Werte. Deshalb gibt es \(2^n\) Tabellenzeilen.

Definition

Stelligkeit

Die Stelligkeit einer Booleschen Funktion ist die Anzahl ihrer Eingangsvariablen. Eine Funktion mit zwei Eingaben heißt zweistellig, eine Funktion mit drei Eingaben dreistellig.

Für jede Tabellenzeile darf die Ausgabe entweder \(0\) oder \(1\) sein. Wenn es \(2^n\) Zeilen gibt und jede Zeile zwei Ausgabemöglichkeiten hat, gibt es insgesamt \(2^{2^n}\) verschiedene Boolesche Funktionen.

Beispiel

Bei zwei Eingaben gilt:

• Anzahl der Tabellenzeilen: \(2^2=4\)
• Für jede Zeile gibt es zwei mögliche Ausgabewerte.
• Anzahl der Funktionen: \(2^4=16\)

Bei drei Eingaben gilt:

• Anzahl der Tabellenzeilen: \(2^3=8\)
• Anzahl der Funktionen: \(2^8=256\)

Bei vier Eingaben sind es schon \(2^{16}=65536\) Funktionen.

Merke

Erst wachsen die Tabellenzeilen mit \(2^n\). Danach wachsen die möglichen Funktionen noch einmal als \(2^{2^n}\).

Schaltungen und Prüfungsmodus

In der Informatik heißen Boolesche Funktionen oft auch Schaltfunktionen. Das passt, weil digitale Schaltungen ebenfalls mit zwei Zuständen arbeiten: Strom liegt an oder nicht, Signal ist hoch oder niedrig, Lampe ist an oder aus.

Definition

Schaltfunktion

Eine Schaltfunktion ist eine Boolesche Funktion, die das Verhalten einer digitalen Schaltung beschreibt. Eingänge sind Signale oder Schalter, die Ausgabe ist das berechnete Signal.

In Prüfungen sollst du häufig nicht nur Werte einsetzen. Du sollst entscheiden, ob eine Beschreibung, eine Tabelle, eine Formel und manchmal eine Schaltung zusammenpassen.

Beispiel

Eine Alarmanlage soll auslösen, wenn die Tür offen ist und die Anlage scharf geschaltet ist. Sei \(t=1\) für "Tür offen" und \(s=1\) für "scharf". Dann lautet die Funktion:

$$ a=t \land s $$

Probe an zwei Fällen:

• Tür offen und Anlage scharf: \(t=1,s=1\), also \(a=1\).
• Tür offen und Anlage nicht scharf: \(t=1,s=0\), also \(a=0\).

Die Formel passt, weil beide Bedingungen gleichzeitig erfüllt sein müssen.

Beispiel

Fehlersuche: Jemand behauptet, die Formel \(y=a \lor b\) beschreibe XOR.

Prüfe die Zeile \(a=1,b=1\):

• Bei ODER ist \(1 \lor 1=1\).
• Bei XOR müsste das Ergebnis \(0\) sein, weil die Eingaben nicht verschieden sind.

Ein einziger Gegenfall reicht, um zu zeigen: Die Behauptung ist falsch.

Gut zu wissen

Bei solchen Aufgaben ist eine kleine Probe oft schneller als langes Umformen. Suche gezielt eine Zeile, in der sich zwei Kandidaten unterscheiden.

Alles auf einen Blick

Abschluss-Check

Jetzt prüfst du, ob du das Gelernte auf neue Situationen übertragen kannst. Lies die Aufgaben genau: Oft steckt der entscheidende Unterschied in einem einzigen Wort wie "und", "oder" oder "genau".

Zusammenfassung

Eine Boolesche Funktion beschreibt eine Entscheidung mit den Werten \(0\) und \(1\). Sie kann als Wahrheitstabelle, als Boolescher Ausdruck oder als Schaltfunktion dargestellt werden. Eine Wahrheitstabelle ist vollständig, wenn sie jede Eingabekombination enthält.

Die wichtigsten Bausteine sind UND, ODER, NICHT und XOR. Aus Tabellenzeilen mit Ausgabe \(1\) kannst du systematisch eine Formel bauen, indem du pro Trefferzeile einen UND-Term bildest und diese Terme mit ODER verknüpfst.

Bei \(n\) Eingaben gibt es \(2^n\) Tabellenzeilen. Weil jede Zeile als Ausgabe \(0\) oder \(1\) bekommen kann, gibt es insgesamt \(2^{2^n}\) Boolesche Funktionen. Genau deshalb werden Wahrheitstabellen schnell groß und kompakte Formeln so wichtig.