Informatik
Wahrheitstabelle eines booleschen Ausdrucks
Schreibe den Ausdruck in der Notation, die dir liegt — AND/OR/NOT, die Zeichen · + ', oder && || ! — und erhalte die vollständige Wahrheitstabelle.
Wie man eine Wahrheitstabelle liest
Eine Wahrheitstabelle listet alle möglichen Kombinationen der Eingänge und den Wert, den der Ausdruck in jeder annimmt. Bei n Variablen sind es 2ⁿ Zeilen: zwei Variablen ergeben vier, drei ergeben acht, vier sechzehn. Die übliche Reihenfolge ist die eines Binärzählers, bei dem sich die erste Variable am langsamsten ändert, und sie stellt sicher, dass keine Kombination übersprungen wird.
Die drei Grundoperatoren lassen sich auf drei Sätze bringen. AND ist nur wahr, wenn beide Eingänge wahr sind, OR ist nur falsch, wenn beide falsch sind, NOT kehrt um. XOR, in den ersten Aufgaben seltener und in Rechenschaltungen zentral, ist wahr, wenn die Eingänge verschieden sind: es ist die binäre Addition ohne Übertrag.
Die Tabelle ist auch das Werkzeug, um eine Identität zu beweisen. Zwei Ausdrücke sind gleichwertig, wenn ihre Ausgangsspalten Zeile für Zeile übereinstimmen, und genau so prüft man die Gesetze von De Morgan: die Negation eines AND ist das OR der Negationen und umgekehrt. Es ist die Umformung, die es erlaubt, jede Schaltung mit nur einem Gattertyp zu bauen.
Häufige Fehler
- Die Rangfolge der Operatoren verwechseln: NOT bindet stärker als AND, und AND stärker als OR. Ohne Klammern bedeutet A OR B AND C also A OR (B AND C), nicht (A OR B) AND C.
- De Morgan falsch anwenden und die Negation nur auf einen Term setzen: die Negation von (A AND B) ist (NOT A) OR (NOT B), wobei sich auch der mittlere Operator ändert.
- Kombinationen in der Tabelle auslassen: bei drei Variablen sind es acht Zeilen, und alle müssen aufgeführt werden, auch die scheinbar offensichtlichen. Die binäre Reihenfolge sorgt dafür, dass keine verloren geht.
Häufige Fragen
Wie viele Zeilen hat eine Wahrheitstabelle?
Zwei hoch der Anzahl der Variablen: 2ⁿ. Zwei Variablen ergeben vier Zeilen, drei acht, vier sechzehn. Jede Zeile ist eine andere Kombination aus Nullen und Einsen.
Wie ist die Rangfolge der booleschen Operatoren?
Zuerst NOT, dann AND, dann XOR, zuletzt OR. Es ist dieselbe Hierarchie wie in der gewöhnlichen Algebra, wenn man AND als Produkt und OR als Summe auffasst — darum schreibt man sie · und +.
Was besagen die Gesetze von De Morgan?
Dass die Negation einer Konjunktion die Disjunktion der Negationen ist und umgekehrt: NOT(A AND B) = NOT A OR NOT B und NOT(A OR B) = NOT A AND NOT B. Man prüft sie durch Vergleich der Ausgangsspalten.
Was unterscheidet OR von XOR?
OR ist auch dann wahr, wenn beide Eingänge wahr sind; XOR nicht. XOR ist nur wahr, wenn die Eingänge sich voneinander unterscheiden. Deshalb heißt es auch „exklusives ODER".
Wie diese Berechnung funktioniert
Operatoren: NOT A ist 1, wenn A 0 ist. A AND B ist 1 nur bei A = B = 1. A OR B ist 0 nur bei A = B = 0. A XOR B ist 1, wenn A ≠ B. Rangfolge, von stark nach schwach: NOT, AND, XOR, OR; Klammern überschreiben sie. Zeilenzahl bei n Variablen: 2ⁿ. Gesetze von De Morgan: ¬(A·B) = ¬A + ¬B und ¬(A + B) = ¬A · ¬B. Nützliche Identitäten: A + A·B = A (Absorption), A·(A + B) = A, A + ¬A = 1 (Satz vom ausgeschlossenen Dritten), A·¬A = 0 (Satz vom Widerspruch). Der Parser akzeptiert die Wortnotation, die symbolische (· + ') und die der Programmiersprachen (&& || !).