1.4 Monotone Funktionen und monotone Schaltkreise

Für zwei Tupel $\mathbf{x}, \mathbf{y} \in \{0,1\}^n$ schreiben wir $ \mathbf{x} \leq \mathbf{y}$, falls $x_1 \leq y_1, \dots, x_n \leq y_n$, also $\mathbf{x}$ in jeder Koordinate kleiner gleich $\mathbf{y}$ ist. Beispielsweise gilt $ (0,0,1) \leq (1,0,1)$. Allerdings gilt weder $ (0,1,0) \leq (1,0,1)$ noch umgekehrt; die beiden Tupel sind unvergleichbar; es handelt sich bei $\leq$ also um eine Partialordnung. Am Besten stellen Sie sich eine solche Partialordnung als gerichteten Graphen vor:

Diese Darstellung einer Partialordnung als gerichteter Graph bezeichnet man auch als Hasse-Diagramm (ich verzichte hier auf eine formale Definition). Es gilt nun $\mathbf{x} \leq \mathbf{y}$, wenn Sie im Hasse-Diagramm einen Pfad von $\mathbf{x}$ nach $\mathbf{y}$ finden.

Vorsicht. Im obigen Bild steht zwar $001$ unterhalb von $110$, allerdings werden Sie keinen Pfad von $001$ nach $110$ finden; es gilt also $001 \not \leq 110$; die beiden Elemente sind unvergleichbar.

Definition Eine Boolesche Funktion $f: \{0,1\}^n \rightarrow \{0,1\}$ heißt monoton, wenn $$ \forall \mathbf{x} \leq \mathbf{y} \in \{0,1\}^n \ : \ f(\mathbf{x}) \leq f(\mathbf{y}) \ . $$ In anderen Worten: wenn wir ein Input-Bit von 0 auf 1 ändern, kann das Output-Bit nicht von 1 auf 0 umkippen.

Übungsaufgabe Welche der Booleschen Funktionen $\wedge, \vee, \neg, \oplus, \maj$ sind monoton?

Funktionen auf wenigen Variablen können wir graphisch darstellen und somit erkennen, ob sie monoton sind oder nicht. Für eine Funktion $ f: \{0,1\}^2 \rightarrow \{0,1\}$ markieren wir im Hasse-Diagramm von $\{0,1\}^2$ diejenigen Elemente blau, auf denen $f(x,y) = 1$ ist, und die anderen rot.

Wir sehen nun, dass es im Bild von $\wedge$ keinen roten Punkt gibt, der oberhalb eines blauen Punktes liegt, im Bild von $\oplus$ allerdings schon. Der Grund: $\wedge$ ist monoton, $\xor$ ist es nicht. Formaler argumentiert: in der Partialordnung gilt $01 \leq 11$ aber $\xor (0,1) \gt \xor (1,0)$, was der Definition einer monotonen Funktion widerspricht. (Ich habe hier absichtlich die Präfixschreibweise $\xor(0,1)$ verwendet, um hervorzuheben, dass es sich hierbei um eine Funktion in zwei Variablen handelt.) Beachten Sie, dass ich die Worte "oberhalb" im Sinne der Partialordnung meine, nicht wirklich im geometrischen Sinne in der Abbildung.

Von den Basis-Gates $\wedge, \vee, \neg$ sind $\wedge$ und $\vee$ monoton, $\neg$ ist es nicht. Es sollte also klar sein, dass ein Schaltkreis ohne Negation immer eine monotone Funktion berechnet. Allerdings stimmt der Umkehrschluss nicht. Der Schaltkreis

ist nicht monoton (beachten Sie hinter der $\bar{y}$-Schreibweise versteckte NOT-Gate), ist aber äquivalent zu der offensichtlich monotonen Funktion $x$. Allerdings können wir folgendes beweisen:

Theorem Zu jeder monotonen Funktion $f: \{0,1\}^n \rightarrow \{0,1\}$ gibt es einen monotonen Schaltkreis (also ohne NOT-Gates), der $f$ berechnet.

Übungsaufgabe Beweisen Sie das Theorem. Tip. Gehen Sie meine oben skizzierten drei Konstruktionen durch (Rekursiv, DNF, CNF) und versuchen Sie, sie so zu modifizieren, dass Sie alle NOT-Gates loswerden.

Übungsaufgabe Finden Sie alle monotonen Funktionen in zwei Variablen. Wie sieht es mit allen monotonen Funktionen in drei Variablen aus?

Am Besten betrachten Sie das Hasse-Diagramm der Partialordnungen auf Mengen $ \{0,1\}^2$ bzw. $ \{0,1\}^3$:

und überlegen sich, wie Sie die vier bzw. acht Knoten auf monotone Weise in einen 1-Bereich und einen 0-Bereich aufteilen können.

Übungsaufgabe (Challenge). Bauen Sie einen Schaltkreis mit drei Input-Variablen $x,y,z$, der drei Output-Gates hat, die $\bar{x}, \bar{y}, \bar{z}$ berechnen. Ihr Schaltkreis darf höchstens zwei NOT-Gates einhalten, aber beliebig viele AND- und OR-Gates.

Lösungen zu den Übungsaufgaben

Ich lege Ihnen sehr ans Herz, die obigen Übungsaufgaben selbständig zu bearbeiten. Falls Sie dennoch die Geduld verlieren, so habe ich hier Lösungen ausgearbeitet. Auch mit dem Zweck, an dieser Stelle auf Beweismethoden wie Induktion und verschiedene Beweisstrategien einzugehen.

Theorem Zu jeder monotonen Funktion $f: \{0,1\}^n \rightarrow \{0,1\}$ gibt es einen monotonen Schaltkreis (also ohne NOT-Gates), der $f$ berechnet.

Ich werde zweieinhalb Beweise für dieses Theorem vorstellen. Dies dient auch dazu, gängige Beweistechniken und Beweismethoden zu illustrieren. Unter Beweismethoden verstehe ich hier formale Methoden wie

Beweis durch Induktion,
Beweis durch Widerspruch,
Beweis durch vollständige Fallunterscheidung,
...

wie sie zum Beispiel auf Wikipedia aufgeführt sind. Diesen zur Seite stehen die nicht wirklich formalisierbaren Beweistechniken oder Beweisstrategien, die sich oft aus persönlicher Erfahrung speisen, wie zum Beispiel

kleine Beispiele untersuchen und dann verallgemeinern,
bereits Bekanntes abwandeln und hoffen, dass es funktioniert,
local change: ein Objekt schrittweise in die gewünschte Richtung verändern;

da bei den Beweistechniken Erfahrung, Intuition und Kreativität mit ins Spiel kommen, ist es unmöglich, eine vollständige Liste anzugeben; ich habe die drei obigen Punkte gewählt, weil sie in der Tat das repräsentieren, was wir in den Beweisen jetzt verwenden werden.

Erster Beweis. Top-Down mit if-then-else.

In diesem Beweis verwende ich die zweite oben erwähnte Technik: bereits bekanntes abwandeln. Was kennen wir denn bereits? Wir kennen die Top-Down-Methode, wie wir aus einer Wahrheitstabelle einen Schaltkreis bauen:

Theorem Zu jeder Booleschen Funktion $f: \{0,1\}^n \rightarrow \{0,1\}$ gibt es einen Schaltkreis $C$, der $f$ berechnet.

Wir haben diese Konstruktion in der Vorlesung an einem Beispiel durchexerziert und auch Größe und Tiefe des resultierenden Schaltkreises analysiert, allerdings haben wir den Beweis nicht formal aufgeschrieben. Nutzen wir hier die Gelegennheit und üben an diesem Beispiel das Finden und Führen mathematischer Beweise. Beachten Sie, dass wir nun vorerst über allgemeine, nicht notwendigerweise monotone Boolesche Funktionen reden. Falls Sie sich noch gut an unseren Beweis von Theorem 2 in der Vorlesung erinnern können und eher an Theorem 1 als an allgemeinen Beweismethoden interessiert sind, dürfen Sie gerne runterspringen.

Beweis. Als Beweismethode verwenden wir Induktion über $n$, die Anzahl der Variablen.

Zur Erinnerung: bei einem Beweis per Induktion wollen wir eine Aussage der Form Für alle natürlichen Zahlen $n \in \N$ gilt $P(n)$ beweisen, wobei $P(n)$ wiederum eine Aussage ist, in der die Zahl $n$ irgendwo vorkommt. Bei einem Beweis durch Induktion zeigen wir nun,

dass $P(0)$ gilt (Induktionsbasis),
dass, wenn $P(n)$ für eine Zahl $n \in \N $ gilt, dann sicherlich auch $P(n+1)$ gilt (Induktionsschritt).

Wenn wir beide Teile gezeigt haben, können wir uns nun "hochhangeln": $P(0)$ gilt, weil wir in Punkt 1 gezeigt haben; mit Hilfe von Punkt 2 können wir nun argumentieren, dass aus $P(0)$ die Aussage $P(1)$ folgt; dass aus $P(1)$ die Aussage $P(2)$ folgt; und so weiter. Da wir auf diese Weise jede natürliche Zahl irgendwann erreichen, können wir schlussfolgern, dass $P(n)$ für jede Zahl $n \in \Z$ gilt.

Als erstes müssen wir nun unsere Aussage, die wir beweisen wollen (also die im Theorem) so formulieren, dass sie die Form $P(n)$ für alle $n \in \N$ annimmt. Dies ist einfach, da die Zahl $n$ bereits im Theorem vorkommt. Wir formulieren sie also nun so um:

Theorem 1.4.4, alternative Formulierung Für jede natürliche Zahl $n$ gilt: zu jeder Booleschen Funktion $f: \{0,1\}^n \rightarrow \{0,1\}$ gibt es einen Schaltkreis $C$, der $f$ berechnet.

Wir haben also im Prinzip Theorem 1.4.4 umständlicher formuliert, um die Abhängigkeit von $n$ zu verdeutlichen. Wir müssen nun Induktionsbasis und Induktionsschritt durchführen.

Induktionsbasis. Wenn $n=0$ ist, dann gibt es nur zwei mögliche Boolesche Funktionen, nämlich die konstanten Funktionen $0$ und $1$. Für beide Funktionen gibt es einen Schaltkreis, nämlich bestehend aus einem Input-Gate (mit der Konstant 0 bzw. 1 beschriftet), das gleichzeitig auch Output-Gate ist.

Vielleicht fühlen Sie sich unwohl bei der Idee, es mit Funktionen mit null Variablen tun zu haben. Allerdings: warum? In Java hätten Sie bestimmt kein Problem mit

        public boolean constantFalse() {
            return false;
        }
        public boolean constantTrue() {
            return true;
        }

und dies sind ja offensichtlich Boolesche Funktionen mit null Input-Variablen. Ich nehme Ihre Ängste aber ernst, und in der Tat gibt es Fälle, wo es sich nicht richtig anfühlt, den Induktionsbeweis bei $0$ anzufangen. In diesem Fall dürfen Sie die Induktionsbasis gerne bei $n=1$ ansetzen oder wo auch immer Sie sich "wohlfühlen"; sie müssen dann aber im Hinterkopf behalten, dass Sie Ihre Aussage für $n=0$ nicht bewiesen haben; machnmal ist das unvermeidbar, weil manche Aussagen einfach z.B. erst ab $n \geq 2$ gelten.

Wenn wir die Induktionsbasis bei $n=1$ ansetzen wollen, dann sehen wir, dass es vier Funktionen gibt: $0, 1, x, \neg x$; all diese haben natürlich einen (sehr einfachen) Schaltkreis. Nur bei $\neg x$ braucht unser Schaltkreis überhaupt ein Gate.

An diesem Punkt protestieren Sie vielleicht und sagen, dass $0$ keine Funktion in einer Variable ist, sondern in zwei Variablen. Und auch hier appelliere ich an Ihre Programmiererfahrung: weder Sie noch der Java-Compiler werden Probleme mit der Funktion

        public boolean constantFalse(boolean x) {
            return false;
        }

haben. Ja in der Tat, Java toleriert es, dass Sie constantFalse zweimal deklariert haben, einmal als Funktion mit 0 Input-Variablen, einmal als Funktion mit einer Input-Variablen. Um hundertprozentig korrekt zu sein, müssten wir Funktionen $\textnormal{zero}_n$ definieren als

\begin{align*} \textnormal{zero}_n & : \{0,1\}^n \rightarrow \{0,1\} \\ (x_1,\dots,x_n) & \mapsto 0 \ . \end{align*}

In der Praxis gehen wir in der Mathematik deutlich laxer mit Notation um und hoffen, dass der Leser aus dem Kontext die richtige Interpretation herausliest: ob $0$ nun eine Konstante ist, eine Funktion mit einer Input-Variablen, mit zwei Input-Variablen etc. In mathematischen Papern lesen Sie in diesem Kontext manchmal with abuse of notation, womit die Autoren andeuten, dass sie ihre Notation nicht ganz korrekt anwenden, aber davon ausgehen, dass Leser oder Leserin (die ja Menschen sind und keine Compiler), verstehen, was gemeint ist.

Wir haben nun also die Induktionsbasis erfolgreich gezeigt. Als nächstes kommt nun der Schritt. In diesem nehmen wir an, dass die Aussage $P(n)$ bereits gilt, und wollen davon ausgehend zeigen, dass auch $P(n+1)$ gilt. Alternativ können wir annehmen, dass $P(n-1)$ gilt und wollen $P(n)$ zeigen (wobei wir nun $n \geq 1$ annehmen müssen). Ob Sie $P(n) \Rightarrow P(n+1)$ oder $P(n-1) \Rightarrow P(n)$ zeigen, kommt aufs Gleiche raus und unterscheidet sich nur in der Notation; in diesem Falle ist es mir angenehmer, $P(n-1) \Rightarrow P(n)$ zu zeigen. Wir dürfen also die Induktionshypothese $P(n-1)$ als gegeben annehmen:

Induktionshypothese. Zu jeder Booleschen Funktion in $n-1$ Variablen gibt es einen äquivalenten Schaltkreis.

und wollen den Induktionsschritt vollziehen, also $P(n)$ zeigen:

Ziel des Induktionsschritts. Zu jeder Booleschen Funktion in $n$ Variablen gibt es einen äquivalenten Schaltkreis.

Beweistechnik/-strategie. Um den Induktionsschritt vollziehen zu können, müssen wir irgendwie die $n$-stellige Funktion $f$ auf sinnvolle Weise in $n-1$-stellige Funktionen "zerlegen". Hier ist im Allgemeinen Kreativität gefragt. Im vorliegenden Falle ist es aber recht klar, welche Zerlegung in Frage kommt. Wir definieren zwei neue, "kleinere" Funktionen $f_0, f_1: \{0,1\}^{n-1} \rightarrow \{0,1\}$ per \begin{align*} f_0 (x_2, \dots, x_n) & := f(0, x_2, \dots, x_n) \\ f_1 (x_2, \dots, x_n) & := f(1, x_2, \dots, x_n) \ . \end{align*} In anderen Worten, wir fixieren das erste Input-Bit auf einen konstanten Wert und erhalten so eine Funktion in $n-1$ Variablen. Die Funktion $f_0$ ist im Prinzip die obere Hälfte der Wahrheitstabelle, und $f_1$ ist die untere Hälfte. Da $f_0$ und $f_1$ jeweils nur $n-1$ Input-Variablen haben, können wir die Induktionshypothese anwenden und folgern, dass es Boolesche Schaltkreise für sie gibt. Nach Zerlegen in $f_0, f_1$ und Anwenden der Induktionshypothese müssen wir nun die Teilergebnisse wieder sinnvoll zusammenfügen. Dies tun wir in diesem Falle mit einem if-then-else-Gate:

Ich behaupte, dass obiger Schaltkreis tatsächlich $f$ berechnet. Falls dies noch nicht klar sein sollte, können wir auch dies formal beweisen, und zwar durch die Methode vollständige Fallunterscheidung. Sei nun also ein konkreter Input $x_1,\dots,x_n$ gegeben.

Der Fall $x_1 = 1$. Dann gibt der obige Schaltkreis den Wert $f_1(x_2,\dots,x_n$ aus, was per Definition von $f_1$ gleich $f(1, x_2,\dots,x_n) = f(x_1,\dots,x_n)$ ist. Er gibt also den korrekten Wert aus.
Der Fall $x_1 = 0$. Dann gibt der obige Schaltkreis den Wert $f_0(x_2,\dots,x_n$ aus, was per Definition von $f_0$ gleich $f(0, x_2,\dots,x_n) = f(x_1,\dots,x_n)$ ist. Er gibt also auch hier den korrekten Wert aus.

Wir haben also erfolgreich einen Schaltkreis für $f: \{0,1\}^n \rightarrow \{0,1\}$ konstruiert. Unser Induktionsbeweis von Theorem 2 ist nun abgeschlossen. $\square$

Diesen "hellblauen" Beweis haben wir ja bereits in der Vorlesung geführt. Ich habe ihn hier wiederholt und in größerem Detail besprochen, um auf verschiedene formale Aspekte der Beweisführung einzugehen. Wenden wir uns jetzt dem Beweis von Theorem 1.4.3 zu.

Theorem 1.4.3, nochmals. Zu jeder monotonen Funktion $f: \{0,1\}^n \rightarrow \{0,1\}$ gibt es einen monotonen Schaltkreis (also ohne NOT-Gates), der $f$ berechnet.

Erster Beweis. Top-Down mit if-then-else.

Wir verfolgen die Beweistechnik "Bekanntes abwandeln und hoffen". Das Bekannte ist die Konstruktion im Beweis von Theorem 1, also die top-down-Konstruktion. Wir gehen wieder induktiv vor (allerdings bin ich jetzt weniger formal und weise Sie nicht mehr ständig auf die Bestandteile eines Induktionsbeweises hin) und zerlegen $f: \{0,1\}^n \rightarrow \{0,1\}$ in zwei neue, "kleinere" Funktionen $f_0, f_1: \{0,1\}^{n-1} \rightarrow \{0,1\}$ per \begin{align*} f_0 (x_2, \dots, x_n) & := f(0, x_2, \dots, x_n) \\ f_1 (x_2, \dots, x_n) & := f(1, x_2, \dots, x_n) \ . \end{align*} Diese Funktionen sind selbst wiederum monoton (versuchen Sie, dies formal zu zeigen, wenn Sie Lust haben; oder versuchen Sie, es sich intuitiv klar zu machen). Per Induktionshypothese gibt es also monotone Schaltkreise für $f_0$ und $f_1$. Wir kombinieren diese mit einem if-then-else-Gate und erhalten:

Die "durchgetrichenen" Kabel bedeuten, dass hier mehrere Kabel parallel laufen (also hier $n-1$ viele). Erkennen Sie das Problem mit der Konstruktion? Klar: das if-then-else-Gate ist nicht monoton. Unser Schaltkreis schaut also in Wirklichkeit so aus:

und enthält ein NOT-Gate. Aber klar: wir können natürlich nicht die Konstruktion aus dem vorherigen Beweis wiederholen und hoffen, dass alles klappt. Die Beweistechnik heißt ja auch Bekanntes abwandeln, nicht Bekanntes kritiklos wiederholen. Wie können wir den obigen Schaltkreis abwandeln, dass er monoton wird, also das eine NOT-Gate entfernen? Spontan fallen mir zwei Wege ein: wir können das NOT-Gate einfach durch ein gate-loses Kabel ersetzen oder das Kabel einfach ganz weglassen, also:

Der linke Schaltkreis gibt uns, als Formel geschrieben, $$ (x \wedge f_1) \vee (x \wedge f_0) \equiv x \wedge (f_1 \vee f_0) \ . $$ Ich erlaube mir hier, aus Bequemlichkeit einfach $f_1$ statt $f_1(x_2,\dots,x_n)$ zu schreiben. Auch ein abuse of notation. In der obigen Formel habe ich rechts das $x$ ausgeklammert; die Formel beginnt nun mit $x \wedge ...$; falls $x=0$ ist, gibt sie also auf jeden Fall $0$ aus; das kann im Allgemeinen nicht korrekt (also äquivalent zu $f$ sein; warum sollte $f$ automatisch $0$ sein, nur weil $x_1=0$ ist? Wir schließen also: das NOT-Gate durch ein gate-loses Kabel zu ersetzen ist im Allgemeinen nicht korrekt.

Schauen wir uns also den Schaltkreis im zweiten Bild an. Das rechte $\wedge$-Gate hat nur einen Input, kann also weggelassen werden (d.h. durch ein Kabel ersetzt werden); wir erhalten den monotonen Schaltkreis

bzw. als Formel: $$ (x_1 \wedge f_1) \vee f_0 \ . $$ Wir müssen nun zeigen, dass dies wirklich $f$ berechnet, also

Behauptung. Für alle $x_1,\dots,x_n$ gilt $$ f(x_1,\dots,x_n) = (x_1 \wedge f_1(x_2,\dots,x_n)) \vee f_0(x_2,\dots,x_n) \ . $$

Beweis. Wir machen eine Fallunterscheidung nach dem Wert von $x_1$.

Der Fall $x_1 = 0$. Dann gilt \begin{align*} f(x_1,x_2,\dots,x_n) & = f(0,x_2,\dots,x_n) \tag{da $x_1=0$} \\ & = f_0 (x_2, \dots,x_n) \tag{Definition von $f_2$} \\ & = (0 \wedge f_1) \vee f_0 \tag{die 0 tötet den ersten Term eh}\\ & = (x_1 \wedge f_1) \vee f_0 \tag{weil $x_1 = 0$} \ , \end{align*} und die behauptete Gleichung gilt.
Der Fall $x_1 = 1$. Dann gilt \begin{align*} f(x_1,\dots,x_n) & = f_1(x_2,\dots,x_n) \ . \end{align*} Was ist aber mit der rechten Seite der behaupteten Gleichung? \begin{align*} (x_1 \wedge f_1) \vee f_0 & = f_1 \vee f_0 \tag{da $x_1=1$ ist und somit im $\wedge$ wegfällt} \end{align*} Die linke Seite ist also $f_1$, die rechte ist $f_1 \vee f_0$. Schaut leider nicht gleich aus. Jetzt sollten bei Ihnen die Glocken klingeln: wir haben bisher an keiner Stelle im Beweis verwendet, dass $f$ eine monotone Funktion ist! Und wenn wir das nicht verwendet haben, kann der Beweis ja gar nicht funktionieren. Also: verwenden wir Monotonität: \begin{align*} (0, x_2, \dots,x_n) & \leq (1, x_2, \dots,x_n) \tag{Definition unser Partialordnung, } \\ f(0, x_2, \dots,x_n) & \leq f(1, x_2, \dots,x_n) \tag{weil $f$ monoton ist.} \\ f_0 & \leq f_1 \ . \end{align*} Wir überprüfen nun also: wenn $f_0(x_2, \dots, x_n) = 0$ ist, dann gilt $f_0 \vee f_1 = 0 \vee f_1 = f_1$. Wenn $f_0 = 1$ ist, dann ist $f_1 = 1$ wegen Monotonität (größer als 1 geht ja nicht), und daher $f_0 \vee f_1 = 1 \vee 1 = 1 = f_1$. In jedem Fall gilt also: $$ (f_0 \vee f_1) = f_1 \ . $$ Und somit sind linke und rechte Seite gleich, wie behauptet.

$\square$

Wir haben nun also gezeigt, dass für jeden Input $x_1,\dots,x_n$ gilt: \begin{align*} f = (x_1 \wedge f_1) \vee f_0 \ , \end{align*} (wobei wir aus Gründen der Lesbarkeit statt $f(x_1,\dots,x_n)$ einfach $f$ schreiben); per Induktion können wir für $f_1, f_0$ monotone Schaltkreise finden, und somit ist

ein monotoner Schaltkreis für $f$.

$\square$

Zweiter Beweis. Bottom-Up, Konstruktion einer DNF-Formel. Als Beweisstrategie verwende ich wieder Bekanntes abwandeln.

Das Bekannte. Erinnern Sie sich an die Konstruktion einer DNF-Formel auf Basis der gegebenen Wahrheitstabelle. Für jedes $n$-Tupel $\mathbf{a} := a_1,\dots,a_n) \in \{0,1\}^n$, für welches $f$ den Wert 1 ausgibt, konstruieren wir einen DNF-Term $T_{\mathbf{a}}$, der auf $\mathbf{a}$ eine 1 ausgibt und sonst überall eine 0. Um den Term genau zu beschreiben, definieren wir

\begin{align*} I_{\mathbf{a}} & := \{ i \in \{1,\dots, n\} \ | \ a_i = 1 \} \\ O_{\mathbf{a}} & := \{ i \in \{1,\dots, n\} \ | \ a_i = 0 \} \ . \end{align*} Als Beispiel: wenn $n=5$ und $\mathbf{a} = (10010)$, dann ist $I_{\mathbf{a}} = \{1,4\}$ und $I_{\mathbf{a}} = \{2,3,5\}$. Wir definieren \begin{align*} T_{\mathbf{a}} & := \bigwedge_{i \in I_{\mathbf{a}}} x_i \wedge \bigwedge_{i \in O_{\mathbf{a}}} \bar{x}_i \ . \end{align*} Für $\mathbf{a} = (10010)$ gibt das also $x_1 \wedge x_4 \wedge \bar{x}_2 \wedge \bar{x}_3 \wedge \bar{x}_5$. Noch kompakter kann man es hinschreiben, wenn man für eine Variable $x$ und einen Wert $b \in \{0,1\}$ folgendes definiert: \begin{align*} x^{b} & := \begin{cases} x & \textnormal{ if $b=1$,}\\ \bar{x} & \textnormal{ if $b=0$.} \end{cases} \end{align*} Dann können wir $T_{\mathbf{a}}$ einfach als \begin{align*} T_{\mathbf{a}} = \bigwedge_{i=1}^n x_i^{a_i} \end{align*} definieren, für $\mathbf{a} = (10010)$ also $x_1^1 \wedge x_2^0 \wedge x_3^0 \wedge x_4^1 \wedge x_5^0 = x_1 \wedge \bar{x}_2 \wedge \bar{x}_3 \wedge x_4 \wedge \bar{x}_5$. Das gibt den gleichen Term wie zuvor, nur mit den Literalen in anderer Reihenfolge aufgelistet (was keine Rolle spielt, da $\wedge$ kommutativ ist).

Gegen eine Boolesche Funktion $f: \{0,1\}^n \rightarrow \{0,1\}$, definieren wir $$ \sat(f) := \{\mathbf{a} \in \{0,1\}^n \ | \ f(\mathbf{a}) = 1 \} \ . $$ Die Abkürzung $\sat$ steht für satisfying assignments, also diejenigen Belegungen der Variablen, die $f$ "erfüllen", also 1 werden lassen. Wir bauen uns einen Schaltkreis $F$:

\begin{align*} F := \bigvee_{\mathbf{a} \in \sat(f)} T_{\mathbf{a}} \end{align*} Dies ist eine DNF-Formel, also insbesondere ein Schaltkreis der Tiefe 2; wir sehen, dass $F \equiv f$ ist, dieser Schaltkreis (diese Formel) also die Funktion $f$ berechnet. Dies ist genau die Konstruktion einer DNF, die wir in der Vorlesung bereits besprochen haben.

Das Bekannte abwandeln. Der Ausdruck $\bigvee_{\mathbf{a} \in \sat(f)} T_{\mathbf{a}}$ ist ja bereits ein Schaltkreis (der Tiefe 2), allerdings im Allgemeinen kein monotoner, da die Terme $T_{\mathbf{a}}$ negative Literale (und somit NOT-Gates) enthalten können. Wie werden wir diese los? Sie erinnern sich, was wir im letzten Beweis getan haben: die NOT-Gates einfach weglassen und die ausgehenden Kabel ersatzlos streichen. Hier hieße das nun, aus dem Term $x_1 \wedge \bar{x}_2 \wedge \bar{x}_3 \wedge x_4 \wedge \bar{x}_5$ den Term $x_1 \wedge x_4 $ zu machen. Wir definieren also: $$ T'_{\mathbf{a}} := \bigwedge_{i \in I_{\mathbf{a}}} x_i \ . $$ Der Term $T'_{\mathbf{a}}$ ist "kürzer" als $T_{\mathbf{a}}$, stellt also weniger "Bedingungen". Formal gesprochen:

Behauptung. Für alle $x_1,\dots,x_n$ gilt $T_{\mathbf{a}} \leq T'_{\mathbf{a}}$.

Beweis. Definieren wir zusätzlich noch $T''_{\mathbf{a}} := \bigwedge_{i \in O_{\mathbf{a}}} \bar{x}_i$, dann können wir $T_{\mathbf{a}} = T'_{\mathbf{a}} \wedge T''_{\mathbf{a}}$ schreiben. Und jetzt ist $T'_{\mathbf{a}} \wedge T''_{\mathbf{a}} \leq T'_{\mathbf{a}}$ offensichtlich, weil $g \wedge h \leq g$ ganz allgemein gilt (überzeugen Sie sich davon). $\square$

Wir definieren nun analog zu $F$ eine DNF-Formel $$ F' := \bigvee_{\mathbf{a} \in \sat(f)} T'_{\mathbf{a}} \ . $$ Sie können sich vorstellen, dass wir $F$ nehmen und alle negativen Literale ersatzlos streichen. Wir behaupten nun, dass $F'$ und $F$ dieselbe Funktion darstellen:

Behauptung $F \equiv F'$, d.h. sie berechnen beide dieselbe Funktion, nämlich $f$.

Beweis. Um zu zeigen, dass beide dieselbe Funktion berechnen, müssen wir zeigen, dass $$ F(\mathbf{x}) = F'(\mathbf{x}) \textnormal{ für alle $\mathbf{x} \in \{0,1\}^n$. } $$ Eine Möglichkeit, eine Gleichheit $=$ zu zeigen, ist, beide Ungleichungen $\leq$ und $\geq$ zu zeigen, also:

$F(\mathbf{x}) \leq F'(\mathbf{x})$ und
$F(\mathbf{x}) \geq F'(\mathbf{x})$.

Punkt 1 ist einfach: wir haben bereits gesehen, dass $T_{\mathbf{a}} \leq T'_{\mathbf{a}}$ gilt, und somit auch $$ \bigvee_{\mathbf{a} \in \sat(f)} T_{\mathbf{a}} \leq \bigvee_{\mathbf{a} \in \sat(f)} T'_{\mathbf{a}} $$ Hier haben wir angewendet, dass $\bigvee$ eine monotone Funktion ist und wir somit vom $\leq$ ihrer Inputs auf das $\leq$ ihres Outputs schließen können.

Punkt 2 ist schwieriger. Um $F'(\mathbf{x}) \leq F(\mathbf{x})$ zu zeigen, machen wir eine Fallunterscheidung. Falls $F'(\mathbf{x}) = 0$ ist, so gilt die Ungleichung offensichtlich, denn kleiner als $0$ kann der Output ja nicht werden. Falls nun $F'(\mathbf{x}) = 1$ ist, dann müssen wir zeigen, dass auch $F(\mathbf{x}) = 1$ gilt. Und das muss mindestens ein bisschen nicht-triviale Arbeit erfordern, weil wir ja irgendwo verwenden müssen, dass $f$ nicht monoton ist. Nehmen wir also an, dass $F'(\mathbf{x}) = 1$ ist.

Strategie: was haben wir? Es ist immer gut, Dinge konkret "in der Hand zu haben". In diesem Falle? Wir wissen ja, dass $F' = \bigvee_{\mathbf{a} \in \sat(f)} T'_{\mathbf{a}} $ ist. Wenn nun also die linke Seite, $F'$, den Wert 1 annimmt, dann muss es auf der rechten Seite (mindestens) einen Term geben, der auch 1 annimmt: $$ T'_{\mathbf{a}^*}(x_1,\dots,x_n) = 1 \ , $$ für ein festes, bestimmtes $\mathbf{a}^*$, also $$ \bigwedge_{i \in I_{\mathbf{a}^*}} x_i = 1 \ . $$ Wir wollen zeigen, dass $F(x_1,\dots,x_n) = 1$ gilt. Da $F = \bigvee_{\mathbf{a} \in \sat(f)} T_{\mathbf{a}} $ gilt, liegt der Verdacht nahe, dass der entsprechende Term $ T_{\mathbf{a}^*}$ auch 1 ausgibt. Das Problem ist leider, dass \begin{align*} T_{\mathbf{a}^*}(\mathbf{x}) & = T'_{\mathbf{a}^*}(\mathbf{x}) \wedge T''_{\mathbf{a}^*}(\mathbf{x}) \\ & = 1 \wedge \bigwedge_{i \in O(\mathbf{a}^*)} \bar{x}_i \ . \end{align*} Wir wissen also, dass $x_i=1$ für alle $i \in I(\mathbf{a}^*)$ gilt; über die $i \in O(\mathbf{a}^*)$ wissen wir leider nichts. Was hätten wir denn gerne? Wir hätten gerne, dass für die alle $x_i = 0$ gilt, weil dann $\bigwedge_{i \in O(\mathbf{a}^*)} \bar{x}_i = 1$ wäre; wir können das aber nicht garantieren.

Wie schaut denn ein Input $\mathbf{y}$ aus, auf dem $ T_{\mathbf{a}^*}$ 1 ausgibt? So ein $\mathbf{y}$ müsste $y_i=1$ für alle $i \in I(\mathbf{a}^*)$ und $y_i=0$ für alle $i \in O(\mathbf{a}^*)$ haben; also 1 sein, wo $\mathbf{a}^*$ auch 1 ist, und 0 sein, wo $\mathbf{a}^*$ auch 0 ist. Aha! Es müsste $\mathbf{a}^*$ selbst sein! Na klar, wir erinnern uns: wir haben den Term $T_{\mathbf{a}}$ so definiert, dass er auf $\mathbf{a}$ und nur dort 1 wird. Wir wissen also: $$ T_{\mathbf{a}^*} (\mathbf{a}^*) = 1 \ . $$ Wenn wir Glück haben, gilt $\mathbf{a}^* = \mathbf{x}$. Ansonsten gilt immerhin, dass $x_i=1$ für alle $i \in I(\mathbf{a}^*)$, also $x_1 = 1$ wenn $a^*_i = 1$. In anderen Worten, es gilt $\mathbf{x} \geq \mathbf{a}^*$! Wunderbar! Jetzt können wir Monotonie anwenden! Denn selbst wenn $T_{\mathbf{a}^*}$ nicht monoton ist, so wissen wir, dass $F$ eine monotone Funktion berechnet, und somit $$ F(\mathbf{x}) \geq F(\mathbf{a}^*) = 1 \ . $$ Wir können zwar nicht genau mit dem Finger auf einen Term von $F$ zeigen, der 1 wird, wissen aber per Monotonie, dass es so einen geben muss. $\square$

Wir haben nun gezeigt, dass die DNF-Formeln $F$ und $F'$ dieselbe Boolesche Funktion berechnen, nämlich $f$. Die Formel $F'$ enthält keine negativen Literale und ist somit ein monotoner Schaltkreis von Tiefe 2. $\square$

Ich habe Ihnen zweieinhalb Beweise versprochen. Der zweieinhalbte Beweis geht nun genau so wie der zweite, nur dass er eine CNF-Formel $G$ statt einer DNF-Formel $F$ konstruiert und aus dieser dann alle negativen Literale entfernt, womit wir eine monotone CNF-Formel $G'$ erhalten. Der Beweis, dass $G'$ und $G$ dieselbe Funktion berechnen, geht analog zu dem obigen Beweis.