2.2 Wahrheitstabellen, CNF, DNF

Wir haben gesehen, dass jeder Schaltkreis eine Boolesche Funktion berechnet. In diesem Abschnitt wollen wir zeigen, dass es umgekehrt auch gilt: zu jeder Booleschen Funktion gibt es einen Schaltkreis (ja: viele Schaltkreise), die sie berechnen. Wir werden insgesamt drei Konstruktionen sehen. Als erstes lassen Sie uns überlegen, wie man eine Boolesche Funktion im Allgemeinen aufschreibt/codiert. Beschränken wir uns erst einmal auf Boolesche Funktionen mit einem Ausgabewert, also .

Dies ist ein endliches Objekt, wir können es also codieren, indem wir für jeden Eingabewert den Ausgabewert angeben. Dies nennt man eine Wahrheitstabelle (englisch truth table). Hier sehen Sie ein Beispiel: Wie können wir von so einer Tabelle ausgehend einen Schaltkreis bauen, der diese Funktion berechnet? Ich stelle Ihnen drei Herangehensweisen vor.

Rekursiv, top-down

Wir teilen die Tabelle in die obere Hälfte (wo gilt) und die untere Hälfte:

Die obere, roten Hälfte kommt Ihnen vielleicht bekannt vor: es ist genau die Wahrheitstabelle von . Der Wert von ist im roten Teil ja immer , also ist die obere Hälfte im Prinzip eine Funktion mit zwei Variablen: und ; wir sagen also mal, die obere Hälfte "ist" . Die untere Hälfte besteht auch aus drei Einsen und einer Null, allerdings ist die Null mittendrin. Überprüfen Sie es, wenn ich Ihnen sage, dass die untere Hälfte ist (ich schreibe im Fließtext übrigens gerne statt , weil das mir lesbarer erscheint). Insgesamt also:
f = if then else .

Jetzt können wir das mit unserem if-then-else-Schaltkreis kombinieren.

Übungsaufgabe 2.2.1 Führen Sie die Konstruktion zu Ende, indem Sie und mit dem if-then-else-Schaltkreis kombinieren.

Können wir das mit beliebigen Funktionen machen? Ja klar! Wir gehen wie folgt vor:

  1. Teile die Tabelle in die oberen Zeilen (für die gilt) und die unteren Zeilen (für die gilt) auf.
  2. Jede Hälfte kann als Boolesche Funktion mit Variablen betrachtet werden. Bauen Sie rekursiv Schaltkreise für die obere und für die untere Hälfte, beide mit Input-Variablen .
  3. Kombinieren Sie diese via if then else zu einem Schaltkreis für mit insgesamt Input-Variablen.

An dieser Stelle zahlt es sich aus, eine formale Notation einzuführen:

Definition 2.2.1 Sei eine Boolesche Funktion, ein Index und ein Wert. Dann ist eine neue Funktion, und zwar

In Worten: wir fixieren den -ten Input auf den Wert und erhalten eine Funktion in den restlichen Variablen.

Das Ergebnis ist im Allgemeinen sehr groß, aber was erwarten Sie bei einer Tabelle mit Zeilen?

Übungsaufgabe 2.2.2 Führen Sie das rekursive Verfahren durch, um für die folgende Funktion auf 4 Variablen einen Schaltkreis zu bauen:

Bottom-Up, als DNF

Wenn Sie Rekursionshasser sind und generell lieber in for-Schleifen denken, dann wird die nächste Konstruktion mehr nach Ihrem Geschmack sein. Im Prinzip werden wir alle Kombinationen der Variablen auflisten, für die die Funktion 1 ausgibt. Stellen Sie sich vor, wir haben drei Variable und einen AND-Ausdruck, der jede Variable oder deren Negation enthält, also zum Beispiel Von den 8 möglichen Input-Tupeln gibt es nur eins, für das dieser Ausdruck eine 1 ausgibt, in diesem Falle . Wir werden nun also für jede 1-Zeile unserer Wahrheitstabelle einen solchen Ausdruck hinschreiben und diese dann in einem großen OR zusammenführen. Einen Ausdruck, der aus einem AND von Variablen oder deren Negation besteht, nennt man auch einen Term.

Mit einem großen OR zusammengeführt ergibt das dann

In diesem Schaltkreis habe ich die Input-Knoten mehrfach aufgeführt und die NOT-Gates nicht explizit aufgeführt, damit kein "Kabelsalat" entsteht. Beachten Sie auch, das jedes Gate (außer den Input-Gates) genau eine ausgehende Kante hat. Konkret bedeutet dies, dass man diesen Schaltkreis als logische Formel hinschreiben kann:
Definition 2.2.2 Ein Literal ist eine Variable oder deren Negation . Ein Term ist ein AND (auch: Konjunktion) von Literalen (beispielsweise . Eine Formel in disjunktiver Normalform (DNF) ist ein OR von Termen.

Alternativ: eine DNF ist ein Schaltkreis der Tiefe 2 (wobei NOT-Gates nicht mitzählen), dessen Output-Gate ein OR-Gate ist.

Übungsaufgabe 2.2.3 Was, wenn einige der "mittleren" Gates (auf Tiefe 1) keine AND-Gates sind, sondern auch OR-Gates? Dann wäre dies nach der ersten Definition keine DNF-Formel, nach der zweiten aber schon. Zeigen Sie, wie man OR-Gates auf Ebene 1 entfernen kann! Als konkretes Beispiel:

Bottom-Up, als CNF

Zu der eben demonstrierten Konstruktion gibt es noch eine weitere, dazu duale Konstruktion. Bildlich gesprochen listet DNF-Konstruktion alle Möglichkeiten auf, wie man eine 1 erhalten kann. Dual dazu können wir alle Möglichkeiten auflisten, wie man eine 0 erhalten kann; tritt keine davon ein, muss wohl eine 1 herauskommen. Wir gehen also in der Wahrheitstabelle alle Zeilen mit Wert 0 durch und schreiben einen Ausdruck, der genau diese Zeile verbietet. So kann man den Ausdruck verstehen als " darf nicht sein." An dem obigen Beispiel ergibt dies:

Einen Ausdruck der Form , also ein OR von Literaten, nennt man auch eine Klausel. Eine Klausel mit (hier: ) Literaten verbietet genau ein Tupel von Wahrheitswerten. Wenn wir also alle Verbote mit AND verknüpfen, erhalten wir
Definition 2.2.3 Eine Formel in konjunktiver Normalform (CNF) ist ein AND von Klauseln.

Alternativ: eine CNF-Formel ist ein Schaltkreis der Tiefe 2 (wobei NOT-Gates nicht mitzählen), dessen Output-Gate ein AND-Gate ist.

In diesem konkreten Beispiel ist die CNF viel kürzer als die DNF (das ist Zufall; ich habe meine Tabelle mit Zufallswerten erzeugt). Allerdings können wir, ausgehend von der "rohen" DNF (oder CNF), diese noch nachträglich bearbeiten und kleiner machen. Zum Beispiel können wir "nebeneinanderstehende" Terme zu einem einzigen zusammenziehen, z.B. :

Übungsaufgabe 2.2.4 Minimieren Sie die obige DNF (die mit den 6 Termen), indem Sie gewisse Paare von Termen zu einem kürzeren zusammenfassen.
Übungsaufgabe 2.2.5 Zeigen Sie, dass es zu jeder Booleschen Funktion eine äquivalente DNF-Formel mit höchstens Termen gibt.
Übungsaufgabe 2.2.6 Zeigen Sie, dass jede DNF-Formel für die Boolesche Funktion genau Terme besitzen muss.

Sie haben eventuell von Methoden zur Minimierung von DNFs bzw. CNFs oder Schaltkreisen im Allgemeinen gehört, z.B. Karnaugh-Diagramme. Dies sind Heuristiken, die hilfreich sind, aber nicht garantieren können, eine optimale Lösung zu finden (es sind also keine Algorithmen in dem Sinne). Die genaue Komplexität dieser Optimierungsprobleme ist in der Tat Gegenstand aktiver Forschung,

  1. Wenn die Funktion (1) bereits als Boolesche Formel vorliegt (also Schaltkreise, in denen außer den Eingabe-Gates alle Gates nur eine ausgehende Kante haben), so ist das Minimierungsproblem -vollständig, siehe Buchfuhrer, David; Umans, Christopher (January 2011), The complexity of Boolean formula minimization (JCSS 2011).
  2. Wenn die Funktion (2) als Tabelle gegeben ist, dann ist die genaue Komplexität nicht genau bekannt. Es hat in den letzten Jahren Fortschritte gegeben (die nahelegen, dass das Problem tatsächlich schwierig ist), z.B. Ilango, Loff, and Oliveira. NP-Hardness of Circuit Minimization for Multi-Output Functions, (CCC 2020).
Beachten Sie, dass (2) algorithmisch einfacher ist: durch die "verschwenderische" Darstellung der Funktion als Tabelle ist bereits der Input sehr groß ( Bits), sodass ein Algorithmus, der hier versucht, zu minimieren, bereits ein großes "Zeitbudget" hat. Dennoch ist das Problem höchstwahrscheinlich schwierig.