Mit Google fortfahren
Boolesche Funktionen: Wahrheitstabellen verstehen
Eine Boolesche Funktion verarbeitet eine oder mehrere binäre Eingaben und liefert genau eine binäre Ausgabe. Alle Werte sind also entweder 0 oder 1, zum Beispiel falsch oder wahr. Auf dieser Seite lernst du, solche Funktionen mit Wahrheitstabellen und Termen zu beschreiben, auszuwerten und aus einer Tabelle zu gewinnen.
Hake ab, was du schon kannst — und komm am Ende hierher zurück!
Von Eingaben zu einer eindeutigen Ausgabe
Stell dir Schalter vor, die nur offen oder geschlossen sein können. Diese beiden Zustände lassen sich als 0 und 1 codieren. Eine Boolesche Funktion legt fest, welcher Ausgangswert zu jeder möglichen Kombination der Eingangswerte gehört.
Boolesche Funktion
Für $B=\{0,1\}$ ist eine $n$-stellige Boolesche Funktion eine Abbildung
$$f:B^n\to B.$$
Sie ordnet jeder Kombination aus $n$ Eingabewerten genau einen Ausgabewert aus $B$ zu. Bei $n=1$ heißt sie einstellig, bei $n=2$ zweistellig und bei $n=3$ dreistellig.
Für jede der $n$ Eingaben gibt es zwei Möglichkeiten. Deshalb besitzt eine vollständige Wahrheitstafel $2^n$ Zeilen. Bei drei Eingaben sind das $2^3=8$ Zeilen.
Auch die Zahl der möglichen Funktionen wächst schnell: Eine Wahrheitstafel mit $2^n$ Zeilen kann in jeder Ergebniszeile unabhängig 0 oder 1 enthalten. Daher gibt es $2^{2^n}$ verschiedene $n$-stellige Boolesche Funktionen. Bei zwei Eingaben sind es $2^4=16$.
Die Stelligkeit zählt die Eingaben, nicht die möglichen Werte. Eine einstellige Funktion hat eine Eingabe, obwohl diese Eingabe zwei Werte annehmen kann.
NICHT, UND und ODER sicher unterscheiden
Mit drei Grundoperationen kannst du Boolesche Funktionen beschreiben. Wir verwenden durchgehend $\neg$ für NICHT, $\land$ für UND und $\lor$ für ODER.
- NICHT kehrt einen Wert um: Aus
0wird1, aus1wird0. - UND liefert nur dann
1, wenn beide Eingaben1sind. - ODER liefert
1, wenn mindestens eine Eingabe1ist.
| $A$ | $B$ | $\neg A$ | $A\land B$ | $A\lor B$ |
|---|---|---|---|---|
| 0 | 0 | 1 | 0 | 0 |
| 0 | 1 | 1 | 0 | 1 |
| 1 | 0 | 0 | 0 | 1 |
| 1 | 1 | 0 | 1 | 1 |
Oder bedeutet hier das einschließende ODER: Sind beide Eingaben 1, ist auch die Ausgabe 1. Das exklusive ODER, kurz XOR, funktioniert anders und wird im nächsten Kapitel betrachtet.
Es gibt mehrere Schreibweisen. Für UND findest du etwa $AB$, $A\cdot B$ oder $A\land B$; für ODER auch $A+B$. Da Bindungsregeln je nach Schreibweise unterschiedlich angegeben werden können, setzen wir bei gemischten Operationen eindeutige Klammern.
Einen Booleschen Term auswerten
Bei einem Term arbeitest du Zeile für Zeile. Trage zuerst die Eingaben ein, berechne dann Negationen und Teilterme und zuletzt die gesamte Ausgabe.
Gesucht ist die Funktion
$$Y=(\neg A\land B)\lor(A\land\neg B).$$
Der erste Teilterm ist nur bei A=0, B=1 wahr. Der zweite ist nur bei A=1, B=0 wahr. Durch das abschließende ODER wird $Y$ genau dann 1, wenn sich die Eingaben unterscheiden.
| $A$ | $B$ | $\neg A\land B$ | $A\land\neg B$ | $Y$ |
|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 |
| 0 | 1 | 1 | 0 | 1 |
| 1 | 0 | 0 | 1 | 1 |
| 1 | 1 | 0 | 0 | 0 |
Die Ausgangsfolge 0,1,1,0 gehört zu XOR, dem exklusiven ODER.
Eine Wahrheitstafel beschreibt die Funktion eindeutig. Verschiedene Terme können dagegen dieselbe Funktion beschreiben. Für XOR ist zum Beispiel auch
$$Y=(A\lor B)\land\neg(A\land B)$$
geeignet: Mindestens eine Eingabe muss 1 sein, aber beide dürfen nicht zugleich 1 sein.
Aus der Wahrheitstafel KDNF und KKNF bilden
Manchmal kennst du nur die Wahrheitstafel. Dann kannst du daraus systematisch einen passenden Term erzeugen. Die kanonische disjunktive Normalform (KDNF) nutzt die Einszeilen; die kanonische konjunktive Normalform (KKNF) nutzt die Nullzeilen.
Betrachte die Äquivalenzfunktion: Sie ist genau dann 1, wenn beide Eingaben gleich sind.
| $A$ | $B$ | $f$ |
|---|---|---|
| 0 | 0 | 1 |
| 0 | 1 | 0 |
| 1 | 0 | 0 |
| 1 | 1 | 1 |
KDNF aus den Einszeilen
Ein Minterm ist eine UND-Verknüpfung, in der jede Variable genau einmal vorkommt. Bei einer Einszeile schreibst du eine Variable unnegiert für den Tabellenwert 1 und negiert für 0.
- Aus
A=0, B=0entsteht $\neg A\land\neg B$. - Aus
A=1, B=1entsteht $A\land B$.
Dann verbindest du die Minterme mit ODER:
$$f=(\neg A\land\neg B)\lor(A\land B).$$
Jeder Minterm trifft genau eine Einszeile. Das ODER sammelt alle Einszeilen ein.
KKNF aus den Nullzeilen
Ein Maxterm ist eine ODER-Verknüpfung, in der jede Variable genau einmal vorkommt. Er soll in seiner ausgewählten Nullzeile falsch sein. Deshalb gilt hier die umgekehrte Vorzeichenregel: Für den Tabellenwert 0 schreibst du die Variable unnegiert, für 1 negiert.
- Aus
A=0, B=1entsteht $A\lor\neg B$. - Aus
A=1, B=0entsteht $\neg A\lor B$.
Dann verbindest du die Maxterme mit UND:
$$f=(A\lor\neg B)\land(\neg A\lor B).$$
Jeder Maxterm erzeugt genau eine ausgewählte Nullzeile. Das UND hält alle diese Nullen fest.
KDNF: Einszeilen auswählen, Minterme bilden, mit ODER verbinden. KKNF: Nullzeilen auswählen, Maxterme bilden, mit UND verbinden.
Wähle in jeder Lücke die passende Form und prüfe anschließend deine Antworten.
Für die KDNF liest du die ab und verbindest die Minterme mit . Für die KKNF liest du die ab und verbindest die Maxterme mit .
Terme vereinfachen und als Schaltung lesen
Boolesche Rechengesetze verändern nicht die Funktion, sondern nur ihre Darstellung. Ein kürzerer Term kann mit weniger logischen Gattern umgesetzt werden.
| Gesetz | UND-Seite | ODER-Seite |
|---|---|---|
| Neutralität | $A\land1=A$ | $A\lor0=A$ |
| Extremwert | $A\land0=0$ | $A\lor1=1$ |
| Idempotenz | $A\land A=A$ | $A\lor A=A$ |
| Komplement | $A\land\neg A=0$ | $A\lor\neg A=1$ |
| Doppelnegation | $\neg\neg A=A$ | — |
| De Morgan | $\neg(A\land B)=\neg A\lor\neg B$ | $\neg(A\lor B)=\neg A\land\neg B$ |
Vereinfache
$$Y=(A\land B)\lor(A\land\neg B).$$
- Klammere $A$ aus: $Y=A\land(B\lor\neg B)$.
- Nutze das Komplementgesetz: $B\lor\neg B=1$.
- Nutze die Neutralität: $A\land1=A$.
Also gilt $Y=A$. Der ursprüngliche Term prüft beide möglichen Werte von $B$; deshalb hängt das Ergebnis tatsächlich nur von $A$ ab.
In einer Gatterschaltung entspricht jede Operation einem Baustein: NICHT einem Inverter, UND einem UND-Gatter und ODER einem ODER-Gatter. Für den XOR-Term werden die Eingänge zunächst passend negiert, in zwei UND-Gattern kombiniert und danach durch ein ODER-Gatter zusammengeführt. Die physische Realisierung solcher Gatter ist eine andere Ebene als die logische Funktion.
Karteikasten
Überlege zuerst selbst und drehe die Karte anschließend zum Prüfen um.
Alles auf einen Blick
- Boolesche Funktion
- Darstellung
- Wahrheitstafel: eindeutige Ausgangsspalte
- Term: kompakte Beschreibung
- Grundoperationen
- NICHT: Wert umkehren
- UND: beide Eingaben müssen `1` sein
- ODER: mindestens eine Eingabe ist `1`
- Von der Tabelle zum Term
- KDNF aus Einszeilen und Mintermen
- KKNF aus Nullzeilen und Maxtermen
- Weiterverarbeitung
- Gesetze vereinfachen äquivalente Terme
- Gatter setzen logische Operationen um
- Darstellung
Abschluss-Check
Du kannst eine Boolesche Funktion jetzt auf drei zusammengehörige Arten untersuchen: durch ihre Wahrheitstafel, durch einen Term und durch eine Schaltung aus Gattern. Gleiche Ausgangsspalten bedeuten dieselbe Funktion, auch wenn die Darstellungen verschieden aussehen.