Transcript
ETH Zürich Institut für Theoretische Informatik Prof. Dr. Angelika Steger, Prof. Dr. Thomas Holenstein Ralph Keusch
HS 2015 Abgabe 01.12.2015
Algorithmen und Komplexität Übungsblatt 11 Aufgabe 1 Eine boolsche Funktion auf n Variablen ist eine Funktion {0, 1}n → {0, 1}. a) Zeigen Sie, dass jede boolsche Funktion durch eine KNF-Formel (d.h. boolsche Formel in konjunktiver Normalform) dargestellt werden kann. b) Beschreiben Sie, wie man eine beliebige Formel als Schaltkreis darstellen kann, und schliessen Sie daraus, dass auch jede boolsche Funktion als Schaltkreis dargestellt werden kann. c) Sei die Funktion f : {0, 1}n → {0, 1} wie folgt definiert: ( 1 wenn ∑in=1 xi = 1, f ( x1 , . . . , x n ) = 0 sonst. Finden Sie eine KNF F mit insgesamt nur n2 Literalen, so dass F ( x1 , . . . , xn ) = f ( x1 , . . . , xn ) für alle Belegungen von x1 , . . . , xn gilt. d) Zeigen Sie, dass es für jedes k ≥ 1 eine boolsche Funktion gibt, die nicht durch eine k-KNFFormel (d.h. boolsche Formel in konjunktiver Normalform mit höchstens k Literalen pro Klausel) dargestellt werden kann.
Aufgabe 2 Eine boolsche Formel F in disjunktiver Normalform (DNF) ist von der Bauart F = D1 ∨ D2 ∨ · · · ∨ Dm , wobei jede der m Klauseln eine Konjunktion Di = yi1 ∧ yi2 ∧ · · · ∧ yik von höchstens k Literalen ist. Wir nehmen an dass es total n Variablen gibt. Zeigen Sie, dass man in linearer Zeit in der Eingabegrösse entscheiden kann, ob eine gegebene boolsche Formel F in disjunktiver Normalform erfüllbar ist.
1
Aufgabe 3 n
a) Zeigen Sie, dass es genau 22 viele unterschiedliche Boolsche Funktionen auf n Variabeln gibt. b) Beweisen Sie, dass es höchstens n2n viele gerichtete Graphen auf n Knoten gibt, die kreisfrei sind und bei denen jeder Knoten höchstens 2 eingehende Kanten aufweist. Hinweis: Aus Serie 3 wissen wir, dass auf einem solchen Graphen eine topologische Ordnung existiert. Nummerieren Sie darum die Knotenmenge V mit v1 , . . . , vn , und nehmen Sie an, dass i < j für jede gerichtete Kante (vi , v j ) gilt. c) Sei x ≥ 4. Zeigen Sie, dass es höchstens x4x viele Schaltkreise gibt, die exakt einen Ausgabeknoten besitzen und deren Grösse höchstens x ist. Hinweis: Verwenden Sie Teilaufgabe b), um abzuzählen, wieviele Graphen es geben kann, auf denen ein solcher Schaltkreis basiert. Zählen Sie dann die Anzahl Möglichkeiten, die Knoten des Graphen als Variable, Konstante oder Gatter zu beschriften, und ziehen Sie auch noch die Möglichkeiten in Betracht, einen Ausgabeknoten auszuwählen. d) Sei n hinreichend gross. Beweisen Sie, dass mehr boolsche Funktionen auf n Variabeln exi2n . Folgern Sie daraus, dass eine boolsche Funktion f : stieren als Schaltkreise der Grösse 5n 2n n {0, 1} → {0, 1} existiert, so dass jeder Schaltkreis, der f berechnet, mindestens Grösse 5n hat.
A BGABE DER H AUSAUFGABEN IN DER V ORLESUNG AM 01.12.2015.
2
