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
© Copyright 2024 ExpyDoc
