Boolesche Algebra Rechner: Wahrheitstabelle, DNF, KNF und Minimierung

Das Verfahren sortiert zuerst alle Minterme, also die Zeilen mit Ergebnis 1, nach der Zahl ihrer Einsen in Gruppen.

Danach verschmilzt es Minterme, die sich in genau einem Bit unterscheiden, zu einem Muster mit Strich, zum Beispiel 001 und 011 zu 0-1. Das wiederholt sich, bis keine Verschmelzung mehr möglich ist. Was übrig bleibt, sind die Primimplikanten.

Beim Beispiel (A AND B) OR (NOT A AND C) mit den Mintermen 1, 3, 6 und 7 entstehen drei: 0-1 (¬A ∧ C), -11 (B ∧ C) und 11- (A ∧ B). Im zweiten Schritt wählt der Rechner die kleinste Auswahl, die jeden Minterm abdeckt.

Primimplikanten, die als einzige einen Minterm abdecken, heißen wesentlich und sind immer dabei; hier sind das ¬A ∧ C und A ∧ B. B ∧ C wird nicht gebraucht.

McCluskey beschrieb das tabellarische Verfahren 1956, den Begriff Primimplikant prägte Quine 1952. Wähle die Ausgabeform Minimierung, dann zeigt der Rechenweg alle Runden.

Die DNF ist eine Summe von Produkten und liest sich wie eine Aufzählung der Fälle, in denen die Funktion wahr ist. Sie passt, wenn es wenige Zeilen mit Ergebnis 1 gibt.

Die KNF ist ein Produkt von Summen und zählt auf, was verboten ist; sie passt, wenn es wenige Zeilen mit Ergebnis 0 gibt. Beim Beispiel gilt Σ m(1, 3, 6, 7) für die DNF und Π M(0, 2, 4, 5) für die KNF, beide mit 12 Literalen.

Bei A -> B gibt es nur eine Null: Die KNF ist ¬A ∨ B und hat 2 Literale, die kanonische DNF braucht 3 Minterme mit 6 Literalen. In Programmcode ist eine Bedingung wie ¬A ∨ B meist die lesbarere Form.

Für Schaltungen hängt die Wahl von den verfügbaren Gattern ab: UND-ODER-Strukturen nutzen die DNF, ODER-UND-Strukturen die KNF. Der Rechner zeigt beide kanonischen Formen im Modus Normalformen und die minimierten Formen im Modus Minimierung.

Ohne Klammern bindet NOT am stärksten, danach folgen AND und NAND, dann XOR und XNOR, dann OR und NOR, danach die Implikation -> und zuletzt die Äquivalenz <->.

Das entspricht der Reihenfolge & vor ^ vor | in C und JavaScript, ist aber keine Norm, sondern eine Festlegung dieses Rechners.

Der Unterschied ist groß: A OR B AND C wird als A ∨ (B ∧ C) gelesen und ist in 5 von 8 Belegungen wahr, (A OR B) AND C nur in 3 von 8. Die Implikation -> bindet von rechts, A -> B -> C bedeutet also A -> (B -> C).

NAND, NOR und -> sind nicht assoziativ; bei ihnen führen fehlende Klammern zu anderen Funktionen. Das Feld Gelesen als zeigt den Ausdruck mit voller Klammerung, so erkennst du sofort, wie der Rechner deine Eingabe verstanden hat.

Setze im Zweifel Klammern, sie kosten nichts. Nutzt dein Skript eine andere Rangfolge, klammere vollständig.

Wähle den Vergleich zweier Ausdrücke und gib als Boolescher Ausdruck NOT (A AND B) und als Vergleichsausdruck NOT A OR NOT B ein. Der Rechner wertet beide für alle 4 Belegungen aus und meldet 0 abweichende Zeilen: Die Ausdrücke sind äquivalent.

Genauso funktioniert das zweite Gesetz, NOT (A OR B) gegen NOT A AND NOT B, ebenfalls mit 4 von 4 gleichen Zeilen.

Die Spalte Gleich der Tabelle zeigt für jede Zeile ja oder nein, und bei einem Unterschied nennt der Rechner die abweichenden Zeilennummern.

Eine Wahrheitstabelle ist ein vollständiger Beweis, weil sie jede mögliche Belegung enthält; bei höchstens vier Variablen sind das höchstens 16 Zeilen.

Dieselbe Methode taugt für Absorption, Distributivgesetz oder die Kontraposition A -> B gegen NOT B -> NOT A. Schreibe in der Klausur die Tabelle mit allen Zeilen auf, nicht nur die Spalte des Ergebnisses, damit die Rechnung nachvollziehbar bleibt.

Eine Tautologie ist für jede Belegung wahr, eine Kontradiktion nie. Im Modus Wahrheitstabelle steht das in der Klassifikation: Bei einer Tautologie ist die Zahl der Belegungen mit Ergebnis 1 gleich 2^n, bei einer Kontradiktion gleich 0.

A OR NOT A ist in 2 von 2 Belegungen wahr, A AND NOT A in 0 von 2. Auch (A -> B) OR (B -> A) ist mit 4 von 4 Belegungen eine Tautologie, obwohl man ihr das nicht ansieht. Alles dazwischen heißt erfüllbar, aber keine Tautologie.

Die Minimierung zeigt dasselbe als Minimalform 1 oder 0. Der Rechner weist außerdem darauf hin, wenn eine Variable zwar vorkommt, das Ergebnis aber in keiner Belegung ändert; bei A OR NOT A ist das die Variable A.

Eine Kontradiktion ist in der Praxis oft ein Hinweis auf einen Fehler, etwa eine Bedingung, die nie erfüllt wird und deshalb toten Code erzeugt. Prüfe in diesem Fall die Verknüpfung der Teilbedingungen.

Vier Variablen ergeben 16 Zeilen, fünf schon 32 und sechs 64: Die Tabelle verdoppelt sich mit jeder Variablen.

Bei vier Variablen bleiben Tabelle und Minimierung auf einem Bildschirm lesbar, und die Primimplikanten lassen sich im Karnaugh-Diagramm von Hand nachvollziehen; das ist die übliche Grenze für Übungsaufgaben.

Außerdem erlaubt sie die vollständige Suche nach der kleinsten Überdeckung: Bei höchstens 16 Mintermen gibt es nur wenige Primimplikanten, und alle Teilmengen lassen sich prüfen.

Bei mehr Variablen wird dieses Überdeckungsproblem schwer, größere Werkzeuge setzen auf Heuristiken, die nicht immer die kleinste Form liefern. Eine fünfte Variable meldet der Rechner mit den Namen A bis E und lehnt ab.

Hast du mehr Variablen, zerlege die Aufgabe in Teilausdrücke mit bis zu vier Variablen und ersetze jeden Teil durch eine eigene Variable. Zum Test: A XOR B XOR C XOR D hat 4 Variablen, 8 Minterme und lässt sich nicht verkürzen.

Ja, die Minimalform ist nicht immer eindeutig. Ein Beispiel sind die Minterme 0, 1, 2, 5, 6 und 7 mit drei Variablen. Hier gibt es sechs Primimplikanten, und keiner davon ist wesentlich: ¬A ∧ ¬B, ¬A ∧ ¬C, ¬B ∧ C, B ∧ ¬C, A ∧ C und A ∧ B.

Jede Auswahl von drei Termen, die alle sechs Minterme abdeckt, hat 6 Literale, und der Rechner meldet 2 gleichwertige Minimalformen. Er zeigt eine davon, nämlich (¬A ∧ ¬B) ∨ (B ∧ ¬C) ∨ (A ∧ C); die andere lautet (¬A ∧ ¬C) ∨ (¬B ∧ C) ∨ (A ∧ B).

Beide sind richtig und gleich lang. Wähle die, die sich mit deinen Bauteilen oder deiner Schreibweise besser verträgt. In der Prüfung genügt meist eine Minimalform, solange du begründest, dass es keine kürzere gibt.

Einen Hinweis auf die Anzahl gleichwertiger Formen gibt das Feld Aufwand vorher und nachher.

Stelle die Schreibweise der Ausgabe auf Programmcode. Der Rechner schreibt dann ! für NOT, && für AND und || für OR, bei XOR den Vergleich !== und bei Äquivalenz ===.

NAND, NOR, XNOR und die Implikation löst er in diese Bausteine auf: A NAND B wird !(A && B), A -> B wird !A || B. Beim Multiplexer lautet die Minimalform (!A && C) || (A && B), die minimale KNF (A || C) && (!A || B).

Beide gelten in Java, JavaScript, C und C# unverändert, in Python ersetzt du die Operatoren durch and, or und not. Prüfe vor dem Einbau mit dem Vergleich, dass die neue Bedingung dieselbe Wahrheitstabelle hat wie die alte.

Beachte, dass && und || in vielen Sprachen kurzschließen: Steht in B ein Funktionsaufruf mit Nebenwirkung, ändert sich das Verhalten, obwohl die Logik gleich bleibt. Die Variablen heißen im Rechner A bis Z; benenne sie im Code nach ihrer Bedeutung.