Wahrheitstabelle für jeden logischen Ausdruck

Zuerst die Klammern, dann die Negation, dann die Konjunktion (UND), dann die Disjunktion (ODER) zusammen mit dem exklusiven ODER, dann die Implikation und zuletzt die Äquivalenz. ¬A ∧ B ∨ C ∧ D bedeutet also ((¬A) ∧ B) ∨ (C ∧ D). Für einen Fall gibt es keine einheitliche Regel: eine Kette von Implikationen ohne Klammern. Die mathematische Logik liest A → B → C als A → (B → C), manche Kurse werten dagegen von links nach rechts aus. Die Implikation ist nicht assoziativ, deshalb ergeben die beiden Lesarten verschiedene Tabellen – das Tool zeigt, welche es verwendet hat, und lässt Sie umschalten.

A → B ist ein Versprechen: „Wenn A, dann B“. Gebrochen wird es nur, wenn A gilt und B nicht – das ist die einzige Zeile 1 → 0 = 0. Ist A falsch, wurde das Versprechen gar nicht auf die Probe gestellt, also gilt es als gehalten, und die Implikation ist 1. Deshalb hat A → B dieselbe Tabelle wie ¬A ∨ B, und deshalb ersetzt das Tool die Implikation beim Vereinfachen durch genau diese Formel.

Die kanonische DNF nimmt für jede Zeile mit F = 1 eine Konjunktion aller Variablen – einen Minterm; eine Funktion, die in sechs Zeilen 1 ist, bekommt also sechs lange Terme. Die Minimierung fasst Terme zusammen, die sich in einer Variable unterscheiden: A∧B∧C ∨ A∧B∧¬C = A∧B. Im KV-Diagramm sind solche Terme benachbarte Felder, und ein Block aus 2, 4 oder 8 Feldern wird zu einem kurzen Term. Das Quine-McCluskey-Verfahren fasst genauso zusammen, nur systematisch, und wählt dann die günstigste Auswahl von Termen, die noch jede 1 überdeckt.

Notieren Sie die Zeilen der vollständigen Tabelle, in denen F den Wert aus dem Ausschnitt annimmt – meist sind es wenige. Suchen Sie, was ihnen gemeinsam ist: Gilt y = 1 immer dann, wenn F = 0 ist, kann eine Spalte mit einer 0 in einer Zeile mit F = 0 nicht y sein. Nehmen Sie dann die aufschlussreichste Zeile des Ausschnitts und prüfen Sie, welche vollständigen Zeilen sie sein kann; die Zeilen des Ausschnitts sind alle verschieden, das schließt weitere Fälle aus. Der Modus „Spaltenrätsel“ macht genau das und schreibt jeden Schritt auf.

Das Schegalkin-Polynom (algebraische Normalform) schreibt jede boolesche Funktion nur mit UND, XOR und der Konstante 1 und ist für jede Funktion eindeutig – praktisch, um Funktionen zu vergleichen und auf Linearität zu prüfen. Die fünf Postschen Klassen beantworten eine andere Frage: Lässt sich aus einer gegebenen Menge von Gattern jede Funktion aufbauen? Nach dem Satz von Post ist eine Menge genau dann vollständig, wenn sie zu jeder der fünf Klassen eine Funktion enthält, die außerhalb dieser Klasse liegt. NAND und NOR liegen in keiner davon – deshalb genügt jedes der beiden allein, um jede Schaltung aufzubauen.