Interaktive Mathe- und Wissenschafts-Lektionen

Boolescher-Ausdruck-Löser

Wahrheitstabelle mit schrittweisen Teilausdrucksspalten

Interaktive Simulation wird geladen...

Wähle die Variable, die am meisten erklärt 🖖

Nützlicher Hardware-Trick: Wähle die Eingabevariable, die TRUE/FALSE-Verhalten am besten trennt, implementiere dann jeden Zweig separat und multiplexe über diese Eingabe. Genau das berechnet die Informationsgewinn-Aufteilung unten: Sie findet die Variable, deren Wert die Unsicherheit über den Ausgang am stärksten reduziert — dieselbe Idee, mit der Entscheidungsbäume ihre erste Aufteilung wählen.

eine Zeile für jede Möglichkeit 🖖

Eine Wahrheitstabelle ist einfach eine vollständige Auflistung: Sie schreibt jede mögliche Kombination von WAHR/FALSCH-Eingaben auf und zeigt, was der Ausdruck jeweils tut. Bei n Variablen gibt es 2ⁿ Zeilen, jede neue Eingabe verdoppelt also die Tabelle — 3 Variablen ergeben 8 Zeilen, 5 ergeben 32. Auch die Zwischenspalten zählen: Sie bauen jeden Teilausdruck Schritt für Schritt auf, sodass du der Logik Operator für Operator folgen kannst, statt dem Endergebnis blind zu vertrauen.

32 Zeilen, vier Milliarden Funktionen 🖖

Hier kommt die Überraschung: Die Tabelle für 5 Variablen hat nur 32 Zeilen, doch die Zahl der verschiedenen Ausdrücke, die man über ihnen definieren kann, beträgt 2³² = 4,294,967,296. Jede unterschiedliche Art, die Ergebnisspalte mit 0 und 1 zu füllen, ist eine eigene Boolesche Funktion, und insgesamt gibt es 2^(2ⁿ) davon. Dieses schlichte Werkzeug durchstreift also lautlos einen Raum von über vier Milliarden möglichen Logikschaltungen — eine für jedes Muster, das die letzte Spalte annehmen kann.

BOOLESCHE AUSDRÜCKE — WELCHES GESETZ VEREINFACHT DIESEN?

In welchem Vereinfachungsfall bist du?

Zwei Ausdrücke sind genau dann derselbe Ausdruck, wenn ihre Wahrheitstabellen übereinstimmen — und nur dieser Test entscheidet. Die Gesetze der booleschen Algebra sind bloß die Übereinstimmungen, die man auf einen Blick kennen sollte: ein NOT nach innen ziehen, eine Klammer ausmultiplizieren, einen Term streichen, der nichts ändert, und den Term erkennen, den die anderen längst abdecken. Stelle die Tabelle auf, und die Antwort steht fest.

Ein NOT auf einer Klammer — De Morgan tauscht den Junktor ¬(A ∧ B) = ¬A ∨ ¬B
Eine Klammer zum Ausmultiplizieren — Distributivgesetz A ∧ (B ∨ C) = (A∧B) ∨ (A∧C)
Ein Term, der nichts beiträgt — Absorption A ∨ (A ∧ B) = A
Ein Term, den die anderen schon abdecken — der Konsensussatz (A∧B) ∨ (¬A∧C) ∨ (B∧C) = (A∧B) ∨ (¬A∧C)
Der Ausdruck hängt gar nicht mehr von seinen Eingängen ab A ∨ ¬A = 1

01

Ein NOT auf einer Klammer — De Morgan tauscht den Junktor

Was du weißt: Eine Negation über einem ganzen Ausdruck. Zieht man sie hinein, wird aus AND ein OR oder aus OR ein AND, und jeder Teil wird dabei negiert.

Gesetz: ¬(A ∧ B) = ¬A ∨ ¬B

Rechenbeispiel: !(A & B) ist derselbe Ausdruck wie !A | !B — beide Ausgangsspalten stimmen in allen vier Zeilen überein

Diesen Fall öffnen: De Morgan !(A & B)
Ein NOT auf einer Klammer — De Morgan tauscht den Junktor. Zieht man das NOT hinein, wird aus dem AND ein OR; beide Ausgangsspalten sind gleich. Eine Negation über einem ganzen Ausdruck. Zieht man sie hinein, wird aus AND ein OR oder aus OR ein AND, und jeder Teil wird dabei negiert.
Zieht man das NOT hinein, wird aus dem AND ein OR; beide Ausgangsspalten sind gleich.

02

Eine Klammer zum Ausmultiplizieren — Distributivgesetz

Was du weißt: AND verteilt sich über OR genau so, wie die Multiplikation sich über die Addition verteilt. Das Ausmultiplizieren liefert eine Summe von Produkten, die Standardform, um aus einem Ausdruck eine Schaltung zu machen.

Gesetz: A ∧ (B ∨ C) = (A∧B) ∨ (A∧C)

Rechenbeispiel: A & (B | C) ist dasselbe wie (A & B) | (A & C), über alle acht Zeilen dreier Variablen

Diesen Fall öffnen: A & (B | C)
Eine Klammer zum Ausmultiplizieren — Distributivgesetz. Das Ausmultiplizieren liefert zwei Produktterme, deren OR dem Original entspricht. AND verteilt sich über OR genau so, wie die Multiplikation sich über die Addition verteilt. Das Ausmultiplizieren liefert eine Summe von Produkten, die Standardform, um aus einem Ausdruck eine Schaltung zu machen.
Das Ausmultiplizieren liefert zwei Produktterme, deren OR dem Original entspricht.

03

Ein Term, der nichts beiträgt — Absorption

Was du weißt: Wenn ein Term einen anderen bereits impliziert, kann der schwächere entfallen. A | (A & B) ist schlicht A, was immer B sein mag.

Gesetz: A ∨ (A ∧ B) = A

Rechenbeispiel: A | (A & B) = A: Wo A gleich 1 ist, ist der Ausgang ohnehin 1, und wo A gleich 0 ist, ist auch der zweite Term 0

Diesen Fall öffnen: Absorptionsgesetz
Ein Term, der nichts beiträgt — Absorption. Der zweite Term greift nur dort, wo der erste ohnehin schon griff, und ändert also nie den Ausgang. Wenn ein Term einen anderen bereits impliziert, kann der schwächere entfallen. A | (A & B) ist schlicht A, was immer B sein mag.
Der zweite Term greift nur dort, wo der erste ohnehin schon griff, und ändert also nie den Ausgang.

04

Ein Term, den die anderen schon abdecken — der Konsensussatz

Was du weißt: Drei Terme, deren dritter der Konsensus der ersten beiden ist: Er deckt nur Fälle ab, die jene gemeinsam ohnehin abdecken. Sein Wegfall ändert keine Zeile der Tabelle.

Gesetz: (A∧B) ∨ (¬A∧C) ∨ (B∧C) = (A∧B) ∨ (¬A∧C)

Rechenbeispiel: (A & B) | (!A & C) | (B & C) ist gleich (A & B) | (!A & C) — der dritte Term ist in allen acht Zeilen überflüssig

Diesen Fall öffnen: Konsenstheorem
Ein Term, den die anderen schon abdecken — der Konsensussatz. Lässt man den dritten Term weg, bleibt die Ausgangsspalte in jeder Zeile unverändert. Drei Terme, deren dritter der Konsensus der ersten beiden ist: Er deckt nur Fälle ab, die jene gemeinsam ohnehin abdecken. Sein Wegfall ändert keine Zeile der Tabelle.
Lässt man den dritten Term weg, bleibt die Ausgangsspalte in jeder Zeile unverändert.

05

Der Ausdruck hängt gar nicht mehr von seinen Eingängen ab

Was du weißt: Eine Spalte aus lauter Einsen ist eine Tautologie, eine aus lauter Nullen ein Widerspruch. In beiden Fällen spielen die Variablen keine Rolle mehr.

Gesetz: A ∨ ¬A = 1

Rechenbeispiel: A | !A ist in beiden Zeilen 1, und sein Spiegelbild A & !A ist in beiden 0

Diesen Fall öffnen: Tautologie A | !A
Der Ausdruck hängt gar nicht mehr von seinen Eingängen ab. Beide Zeilen liefern denselben Ausgang, der Eingang hat also überhaupt keinen Einfluss. Eine Spalte aus lauter Einsen ist eine Tautologie, eine aus lauter Nullen ein Widerspruch. In beiden Fällen spielen die Variablen keine Rolle mehr.
Beide Zeilen liefern denselben Ausgang, der Eingang hat also überhaupt keinen Einfluss.
Quellen (2)

Aufgaben vollständig gelöst

  1. Summe der Minterme für den Ausdruck !(A & B) 5 Schritte

    Der Ausdruck lautet !(A & B) mit den zwei Variablen A und B. Zähle die Zeilen, in denen das Ergebnis 1 ist, schreibe die Funktion als Summe von Mintermen auf und ermittle dann, was sich aus diesem einen Gatter ohne weitere Hilfsmittel bauen lässt.

    1. Zwei Variablen, die jeweils 0 oder 1 sein können, sodass die Tabelle eine Zeile pro Paar erhält. Der Parser meldet diese Anzahl, bevor er irgendetwas auswertet, da die Größe der Aufgabe durch die Variablen festgelegt ist und nicht durch den darüber geschriebenen Ausdruck.

    2. Fülle zuerst die innere Spalte aus. A & B ist nur dann 1, wenn beide Eingänge 1 sind, sodass drei Zeilen eine 0 und die letzte eine 1 tragen. Die Tabelle gibt diesen Teilausdruck als eigene Spalte neben dem Ergebnis aus, sodass sich die Syntaxanalyse überprüfen lässt und nicht nur die Antwort.

    3. NOT kehrt jeden Eintrag um und tut sonst nichts. Die drei Nullen werden zu Einsen und die einzelne Eins wird zur Null, sodass die Ergebnisspalte das genaue Gegenteil der Spalte darüber ist.

    4. Damit stehen 3 der 4 Zeilen auf 1. Als Bruch ausgedrückt ist das 0,75, was das Bedienfeld als Prozentsatz der Eingangskombinationen angibt.

    5. Benenne jede wahre Zeile nach der Konjunktion, die genau auf dieser Zeile 1 ist und auf keiner anderen — ihrem Minterm — und verknüpfe die drei mit OR. Dies ist die kanonische disjunktive Normalform, und es ist genau die Liste, die das Werkzeug unter der Tabelle ausgibt.

    Antwort

    NAND ist in 3 der 4 Zeilen 1, also 75,0 %, und seine Normalform besteht aus diesen 3 Mintermen. Nun der Gewinn. Führt man A beiden Eingängen zu, ergibt A NAND A den Ausdruck !(A & A), was !A entspricht — man erhält NOT. Führt man den Ausgang eines NAND zurück in beide Eingänge eines weiteren NAND, heben sich die beiden Negationen auf, sodass (A NAND B) NAND (A NAND B) gleich AND ist. Für OR negiert man zuerst beide Eingänge: (A NAND A) NAND (B NAND B) ist !(!A & !B), und !A & !B ist nur in der einzelnen Zeile 0,0 gleich 1, sodass seine Negation in den anderen 3 Zeilen 1 ist — was A OR B entspricht. NOT, AND und OR sind genau das, was Schritt 5 verwendete, um eine Funktion als Normalform zu schreiben; somit kann diese eine 4-Zeilen-Spalte jede boolesche Funktion einer beliebigen Anzahl von Variablen ausdrücken.

  2. Die Spalte für !A | !B von Grund auf aufbauen 6 Schritte

    Betrachte nun !A | !B, was keinen Operator mit !(A & B) teilt — keine negierte Klammer, nirgends ein AND. Baue seine Spalte von Grund auf auf und sieh nach, wo sie landet.

    1. Zwei NOT-Spalten, beide neben dem Ergebnis ausgegeben. !A ist 1 in den 2 Zeilen, in denen A 0 ist; !B ist 1 in den 2 Zeilen, in denen B 0 ist. Sie stimmen in einer Zeile überein und schlagen beide in einer Zeile fehl.

    2. OR ist nur dort 0, wo beide Eingänge 0 sind, und das geschieht in genau einer Zeile: A=1, B=1, der Zeile, in der keine der Negationen bestehen bleibt. Jede andere Zeile hat mindestens eine 1 beizutragen.

    3. Somit sind 3 der 4 Zeilen 1 — dieselben 0,75, angegeben als derselbe Prozentsatz.

    4. Auch die Minterme stimmen überein, Term für Term und in derselben Reihenfolge wie in der ersten Aufgabe.

    5. Vergleiche nun die beiden Ausdrücke ganz ohne Tabelle. A & B ist in genau einer Zeile 1, somit ist !(A & B) in genau dieser Zeile 0, und es ist dieselbe Zeile, die gerade !A | !B zu Fall gebracht hat. Zwei Spalten, die an derselben Stelle 0 und überall sonst 1 sind, sind dieselbe Spalte.

    6. Wie beeindruckt sollte man sein? Eine 4-Zeilen-Tabelle hat 4 Ergebniszellen mit jeweils 0 oder 1, sodass zwei Variablen insgesamt nur 16 verschiedene Funktionen zulassen. Eine Übereinstimmung in einer so kleinen Menge ist nicht überraschend — weshalb Schritt 5 der entscheidende Teil ist: Er hat eine Zeile festgelegt und den Rest gar nicht erst gezählt.

    Antwort

    Beide Ausdrücke ergeben 75,0 % mit denselben 3 Mintermen, weil sie eine Funktion unter zwei Namen sind. Die kanonische Form ist ein Fingerabdruck: Zwei Ausdrücke sind genau dann äquivalent, wenn ihre Mintermmengen übereinstimmen, sodass sich die Frage, ob sich zwei Schaltungen gleich verhalten, darauf reduziert, ob zwei Listen übereinstimmen. Was sich nicht reduziert, sind die Kosten für das Erstellen der Listen. 2 Variablen benötigen 4 Zeilen, und die hat man im Kopf berechnet; 20 Variablen benötigen 1.048.576; 100 Variablen benötigen ungefähr 1,27×10³⁰ Zeilen, und der Fingerabdruck ist immer noch die richtige Idee, während die Tabelle als Methode ausgedient hat. Das Argument Zeile für Zeile in Schritt 5 ist dasjenige, das den Sprung übersteht, weil darin nie erwähnt wurde, wie viele Zeilen es gab.

· Aktualisiert

Anhand veröffentlichter Quellen geprüft. Korrekturen willkommen. Redaktionsrichtlinie · Korrekturen

Alle Lektionen: Informatik →

Beispielaufgaben

  • einfaches AND - UND: Ausgang ist nur dann 1, wenn A und B beide 1 sind
  • (A OR B) AND NOT C - 3 Variablen, 8 Zeilen – zeigt, wie NOT einen ganzen Zweig umkehrt
  • 3-Eingang-Mehrheit - Mehrheitsentscheid: 1, wenn mindestens 2 von A, B, C gleich 1 sind
  • 2:1 Multiplexer - Multiplexer: S=0 gibt A aus, S=1 gibt B aus
  • Tautologie A | !A - A | !A ist in jeder Zeile wahr. Die Ergebnisspalte besteht folglich nur aus Einsen, und die Eingabe spielt überhaupt keine Rolle. Kombiniert mit dem Gegenteil A & !A sind dies die beiden Funktionen, welche die Wahrheitstabelle ausdrücken kann, ohne die Variable auch nur einmal auslesen zu müssen.
  • Widerspruch A & !A - A & !A ist in jeder einzelnen Zeile falsch. Jeder andere Ausdruck auf dieser Seite bewegt sich zwischen diesem und seinem Gegenteil. Genau deshalb markieren diese beiden die Endpunkte der Skala und sind keine bloßen Kuriositäten.
  • De Morgan !(A & B) - Lade diesen Ausdruck und danach seinen Partner !A | !B. Die beiden Ergebnisspalten sind identisch, was genau das ist, was das De-Morgansche Gesetz besagt: Die Negation eines UND wird zu einem ODER der Negationen. Zwei Ausdrücke, aber nur eine Funktion.
  • De Morgan !A | !B - Die andere Hälfte des De-Morgan-Paares. Stelle den Ausdruck neben !(A & B), und du wirst sehen, dass die Ergebnisspalten Zeile für Zeile übereinstimmen. Die beiden Ausdrücke sind also nicht nur in bestimmten Fällen gleichwertig, sondern exakt dieselbe Funktion in zweifacher Ausführung.
  • A & (B | C) - A & (B | C), die linke Seite des Distributivgesetzes. Sein Partner multipliziert den Ausdruck zu (A & B) | (A & C) aus. Die Tabellen stimmen überall überein, was diese Umformung mathematisch gültig und nicht bloß plausibel macht.
  • (A & B) | (A & C) - Die ausmultiplizierte Form. Sie erfordert zwei UND und ein ODER, während die kompakte Variante von jedem nur eines benötigt. Eine Umformung, die die Wahrheitstabelle unverändert lässt, ist in der Hardware also keineswegs kostenlos. Das ist derselbe Grund, weshalb sich die Algebra lohnt, bevor man überhaupt Schaltungen baut.
  • XOR erweiterte Form - Hier ist XOR anhand der zwei Fälle ausgeschrieben, in denen sich die Eingaben unterscheiden. Es gibt hier bewusst keinen eigenen XOR-Operator. Wenn du es als Summe von Mintermen betrachtest, verstehst du das Grundprinzip: Genau so wird jede Funktion aus den drei Bausteinen konstruiert, die du bereits kennst.
  • A AND A AND A AND A - Verknüpfst du eine Variable viermal über ein UND mit sich selbst, erhältst du die Variable zurück. Bedenke, was das kostet: drei Gatter, die rein gar nichts verändern. Genau solche Bausteine soll ein Optimierer beseitigen.
  • Absorptionsgesetz - A | (A & B) reduziert sich auf A. Die Spalte B beweist ihre Daseinsberechtigung dadurch, dass sie ganz offensichtlich ignoriert wird: Wo immer A wahr ist, ist der gesamte Ausdruck ohnehin wahr, und wo A falsch ist, wird auch der zweite Term falsch.
  • Konsenstheorem - Der mittlere Term ist überflüssig, und die Tabelle beweist es. Streiche B & C, und die Ergebnisspalte bleibt unverändert. Das durch reines Hinsehen zu erkennen, ist schwer, weshalb dieser Satz auch einen eigenen Namen trägt.
  • Implikation A -> B - „A impliziert B“ ist kein logischer Grundbaustein. Es entspricht !A | B, und die Tabelle ist der Beweis dafür. Die Zeile, die die meisten Menschen überrascht, ist jene mit A falsch und B wahr. Auch hier bleibt die Implikation vollkommen gültig.
  • 3-Eingang-Parität - Dieser Ausdruck ist wahr, sobald eine ungerade Anzahl der Eingaben 1 ist. Das entspricht einem XOR, das über drei Variablen verkettet wurde. Dies ist das Prüfbit auf einem Speicherwort. Es fängt jeden Einzelbitfehler ab, da das Kippen einer einzigen Eingabe unweigerlich die Ausgabe umkehrt.