2.4 Monotone Schaltkreise

Für zwei Tupel $x, y \in {0, 1}^{n}$ schreiben wir $x \leq y$ , falls $x_{1} \leq y_{1}, \dots, x_{n} \leq y_{n}$ , also $x$ in jeder Koordinate kleiner gleich $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 $x \leq y$ , wenn Sie im Hasse-Diagramm einen Pfad von $x$ nach $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 ≰ 110$ ; die beiden Elemente sind unvergleichbar.

Definition 2.4.1 Eine Boolesche Funktion

f : {0, 1}^{n} \to {0, 1}

heißt monoton, wenn

\forall x \leq y \in {0, 1}^{n} : f (x) \leq f (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 2.4.1 Welche der Booleschen Funktionen

\land, \lor, \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} \to {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 $\land$ keinen roten Punkt gibt, der oberhalb eines blauen Punktes liegt, im Bild von $\oplus$ allerdings schon. Der Grund: $\land$ ist monoton, $\oplus$ ist es nicht. Formaler argumentiert: in der Partialordnung gilt $01 \leq 11$ aber $\oplus (0, 1) > \oplus (1, 0)$ , was der Definition einer monotonen Funktion widerspricht. (Ich habe hier absichtlich die Präfixschreibweise $\oplus (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 $\land, \lor, \neg$ sind $\land$ und $\lor$ 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 2.4.2 Zu jeder monotonen Funktion

f : {0, 1}^{n} \to {0, 1}

gibt es einen monotonen Schaltkreis (also ohne NOT-Gates), der

f

berechnet.

Übungsaufgabe 2.4.2 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 2.4.3 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 2.4.4 (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 2.4.3 Zu jeder monotonen Funktion

f : {0, 1}^{n} \to {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 2.4.4 Zu jeder Booleschen Funktion

gibt es einen Schaltkreis

, der

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 , die Anzahl der Variablen.

Zur Erinnerung: bei einem Beweis per Induktion wollen wir eine Aussage der Form Für alle natürlichen Zahlen gilt beweisen, wobei

wiederum eine Aussage ist, in der die Zahl

irgendwo vorkommt. Bei einem Beweis durch Induktion zeigen wir nun,

dass gilt (Induktionsbasis),
dass, wenn für eine Zahl gilt, dann sicherlich auch gilt (Induktionsschritt).

Wenn wir beide Teile gezeigt haben, können wir uns nun "hochhangeln":

gilt, weil wir in Punkt 1 gezeigt haben; mit Hilfe von Punkt 2 können wir nun argumentieren, dass aus

die Aussage

folgt; dass aus

die Aussage

folgt; und so weiter. Da wir auf diese Weise jede natürliche Zahl irgendwann erreichen, können wir schlussfolgern, dass

für jede Zahl

gilt.

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

Theorem 1.4.4, alternative Formulierung 2.4.5 Für jede natürliche Zahl

gilt: zu jeder Booleschen Funktion

gibt es einen Schaltkreis

, der

berechnet.

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

Induktionsbasis. Wenn ist, dann gibt es nur zwei mögliche Boolesche Funktionen, nämlich die konstanten Funktionen und . 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

anzufangen. In diesem Fall dürfen Sie die Induktionsbasis gerne bei

ansetzen oder wo auch immer Sie sich "wohlfühlen"; sie müssen dann aber im Hinterkopf behalten, dass Sie Ihre Aussage für

nicht bewiesen haben; machnmal ist das unvermeidbar, weil manche Aussagen einfach z.B. erst ab

gelten.

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

An diesem Punkt protestieren Sie vielleicht und sagen, dass 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 definieren als

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 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 bereits gilt, und wollen davon ausgehend zeigen, dass auch gilt. Alternativ können wir annehmen, dass gilt und wollen zeigen (wobei wir nun annehmen müssen). Ob Sie oder zeigen, kommt aufs Gleiche raus und unterscheidet sich nur in der Notation; in diesem Falle ist es mir angenehmer, zu zeigen. Wir dürfen also die Induktionshypothese als gegeben annehmen:

Induktionshypothese. Zu jeder Booleschen Funktion in

Variablen gibt es einen äquivalenten Schaltkreis.

und wollen den Induktionsschritt vollziehen, also zeigen:

Ziel des Induktionsschritts. Zu jeder Booleschen Funktion in

Variablen gibt es einen äquivalenten Schaltkreis.

Beweistechnik/-strategie. Um den Induktionsschritt vollziehen zu können, müssen wir irgendwie die -stellige Funktion auf sinnvolle Weise in -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 per In anderen Worten, wir fixieren das erste Input-Bit auf einen konstanten Wert und erhalten so eine Funktion in Variablen. Die Funktion ist im Prinzip die obere Hälfte der Wahrheitstabelle, und ist die untere Hälfte. Da und jeweils nur Input-Variablen haben, können wir die Induktionshypothese anwenden und folgern, dass es Boolesche Schaltkreise für sie gibt. Nach Zerlegen in 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 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 gegeben.

Der Fall . Dann gibt der obige Schaltkreis den Wert aus, was per Definition von gleich ist. Er gibt also den korrekten Wert aus.
Der Fall . Dann gibt der obige Schaltkreis den Wert aus, was per Definition von gleich ist. Er gibt also auch hier den korrekten Wert aus.

Wir haben also erfolgreich einen Schaltkreis für konstruiert. Unser Induktionsbeweis von Theorem 2 ist nun abgeschlossen.

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

gibt es einen monotonen Schaltkreis (also ohne NOT-Gates), der

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 in zwei neue, "kleinere" Funktionen per 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 und . Wir kombinieren diese mit einem if-then-else-Gate und erhalten:

Die "durchgetrichenen" Kabel bedeuten, dass hier mehrere Kabel parallel laufen (also hier

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,

Ich erlaube mir hier, aus Bequemlichkeit einfach

statt

zu schreiben. Auch ein abuse of notation. In der obigen Formel habe ich rechts das

ausgeklammert; die Formel beginnt nun mit

; falls

ist, gibt sie also auf jeden Fall

aus; das kann im Allgemeinen nicht korrekt (also äquivalent zu

sein; warum sollte

automatisch

sein, nur weil

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 -Gate hat nur einen Input, kann also weggelassen werden (d.h. durch ein Kabel ersetzt werden); wir erhalten den monotonen Schaltkreis

bzw. als Formel:

Wir müssen nun zeigen, dass dies wirklich

berechnet, also

Behauptung. 2.4.6 Für alle

gilt

Beweis. Wir machen eine Fallunterscheidung nach dem Wert von

Der Fall . Dann gilt und die behauptete Gleichung gilt.
Der Fall . Dann gilt Was ist aber mit der rechten Seite der behaupteten Gleichung? Die linke Seite ist also , die rechte ist . Schaut leider nicht gleich aus. Jetzt sollten bei Ihnen die Glocken klingeln: wir haben bisher an keiner Stelle im Beweis verwendet, dass eine monotone Funktion ist! Und wenn wir das nicht verwendet haben, kann der Beweis ja gar nicht funktionieren. Also: verwenden wir Monotonität: Wir überprüfen nun also: wenn ist, dann gilt . Wenn ist, dann ist wegen Monotonität (größer als 1 geht ja nicht), und daher . In jedem Fall gilt also: Und somit sind linke und rechte Seite gleich, wie behauptet.

Wir haben nun also gezeigt, dass für jeden Input gilt: (wobei wir aus Gründen der Lesbarkeit statt einfach schreiben); per Induktion können wir für monotone Schaltkreise finden, und somit ist

ein monotoner Schaltkreis für

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 -Tupel , für welches den Wert 1 ausgibt, konstruieren wir einen DNF-Term , der auf eine 1 ausgibt und sonst überall eine 0. Um den Term genau zu beschreiben, definieren wir

Als Beispiel: wenn

und

, dann ist

und

. Wir definieren

Für

gibt das also

. Noch kompakter kann man es hinschreiben, wenn man für eine Variable

und einen Wert

folgendes definiert:

Dann können wir

einfach als

definieren, für

also

. Das gibt den gleichen Term wie zuvor, nur mit den Literalen in anderer Reihenfolge aufgelistet (was keine Rolle spielt, da

kommutativ ist).

Gegen eine Boolesche Funktion , definieren wir Die Abkürzung steht für satisfying assignments, also diejenigen Belegungen der Variablen, die "erfüllen", also 1 werden lassen. Wir bauen uns einen Schaltkreis :

Dies ist eine DNF-Formel, also insbesondere ein Schaltkreis der Tiefe 2; wir sehen, dass

ist, dieser Schaltkreis (diese Formel) also die Funktion

berechnet. Dies ist genau die Konstruktion einer DNF, die wir in der Vorlesung bereits besprochen haben.

Das Bekannte abwandeln. Der Ausdruck ist ja bereits ein Schaltkreis (der Tiefe 2), allerdings im Allgemeinen kein monotoner, da die Terme 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 den Term zu machen. Wir definieren also: Der Term ist "kürzer" als , stellt also weniger "Bedingungen". Formal gesprochen:

Behauptung. 2.4.7 Für alle

gilt

Beweis. Definieren wir zusätzlich noch

, dann können wir

schreiben. Und jetzt ist

offensichtlich, weil

ganz allgemein gilt (überzeugen Sie sich davon).

Wir definieren nun analog zu eine DNF-Formel Sie können sich vorstellen, dass wir nehmen und alle negativen Literale ersatzlos streichen. Wir behaupten nun, dass und dieselbe Funktion darstellen:

Behauptung 2.4.8

, d.h. sie berechnen beide dieselbe Funktion, nämlich

Beweis. Um zu zeigen, dass beide dieselbe Funktion berechnen, müssen wir zeigen, dass

Eine Möglichkeit, eine Gleichheit

zu zeigen, ist, beide Ungleichungen

und

zu zeigen, also:

Punkt 1 ist einfach: wir haben bereits gesehen, dass

gilt, und somit auch

Hier haben wir angewendet, dass

eine monotone Funktion ist und wir somit vom

ihrer Inputs auf das

ihres Outputs schließen können.

Punkt 2 ist schwieriger. Um zu zeigen, machen wir eine Fallunterscheidung. Falls ist, so gilt die Ungleichung offensichtlich, denn kleiner als kann der Output ja nicht werden. Falls nun ist, dann müssen wir zeigen, dass auch gilt. Und das muss mindestens ein bisschen nicht-triviale Arbeit erfordern, weil wir ja irgendwo verwenden müssen, dass nicht monoton ist. Nehmen wir also an, dass ist.

Strategie: was haben wir? Es ist immer gut, Dinge konkret "in der Hand zu haben". In diesem Falle? Wir wissen ja, dass ist. Wenn nun also die linke Seite, , den Wert 1 annimmt, dann muss es auf der rechten Seite (mindestens) einen Term geben, der auch 1 annimmt: für ein festes, bestimmtes , also Wir wollen zeigen, dass gilt. Da gilt, liegt der Verdacht nahe, dass der entsprechende Term auch 1 ausgibt. Das Problem ist leider, dass Wir wissen also, dass für alle gilt; über die wissen wir leider nichts. Was hätten wir denn gerne? Wir hätten gerne, dass für die alle gilt, weil dann wäre; wir können das aber nicht garantieren.

Wie schaut denn ein Input aus, auf dem 1 ausgibt? So ein müsste für alle und für alle haben; also 1 sein, wo auch 1 ist, und 0 sein, wo auch 0 ist. Aha! Es müsste selbst sein! Na klar, wir erinnern uns: wir haben den Term so definiert, dass er auf und nur dort 1 wird. Wir wissen also: Wenn wir Glück haben, gilt . Ansonsten gilt immerhin, dass für alle , also wenn . In anderen Worten, es gilt ! Wunderbar! Jetzt können wir Monotonie anwenden! Denn selbst wenn nicht monoton ist, so wissen wir, dass eine monotone Funktion berechnet, und somit Wir können zwar nicht genau mit dem Finger auf einen Term von zeigen, der 1 wird, wissen aber per Monotonie, dass es so einen geben muss.

Wir haben nun gezeigt, dass die DNF-Formeln

und

dieselbe Boolesche Funktion berechnen, nämlich

. Die Formel

enthält keine negativen Literale und ist somit ein monotoner Schaltkreis von Tiefe 2.

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