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.

Im folgenden betrachten wir eine CNF-Formel als Menge von Klauseln und eine Klausel als Menge von Literalen. Somit sind beispielsweise $(x \vee \bar{y}) \wedge (z \vee \bar{x})$ und $(z \vee \bar{x}) \wedge (\bar{y} \vee x)$ die selbe Formel, da sie beide die Menge $\{ \{x, \bar{y}\},\{z, \bar{x}\}\}$ sind.

Übungsaufgabe Sei $F$ eine CNF-Formel und $C, C' \in F$ zwei Klauseln mit $C \subsetneq C'$. Zeigen Sie, dass $F \equiv F \setminus \{C'\}$ gilt. In Worten: wenn wir die größere Klausel $C'$ löschen, dann erhalten wir eine äquivalente Formel.

Eine CNF-Formel $F$ heißt reduziert, wenn es keine $C, C' \in F$ mit $C \subsetneq C'$ gibt.

Übungsaufgabe Sei $f : \{0,1\}^n \rightarrow \{0,1\}$ eine monotone Boolesche Funktion und seien $F$ und $G$ zwei reduzierte monotone CNF-Formeln, die beide $f$ berechnen. Zeigen Sie, dass $F = G$ gilt, dass es sich also um die selbe Klauselmenge handelt!

Ü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.

Übungsaufgabe Zeigen Sie, dass es mindestens $2^{n \choose \floor{n/2}}$ monotone Boolesche Funktionen über $n$ Variablen gibt.

Zeigen Sie, dass es höchstens $(n+2)^{n \choose \floor{n/2}}$ monotone Boolesche Funktionen in $n$ Variablen gibt.

Tip

Verwenden Sie, dass man den Booleschen Hyperwürfel partitieren kann in ${n \choose \floor{n/2}}$ Ketten, jede von der Form $A = \{a_1, a_2, \dots, a_t\}$ mit $a_1 \leq a_2 \leq \dots \leq a_t$. Für $n=3$ zum Beispiel \begin{align*} A_1 & = \{000, 001, 011, 111\} \\ A_2 & = \{010, 110\} \\ A_3 & = \{100, 101\} \end{align*}

Übungsaufgabe Jetzt, wo Sie die vorherige Aufgabe gelöst haben, können Sie bessere obere Schranken herleiten?