Blatt 5 - Professur für Theoretische Informatik

Diskrete Modellierung
Wintersemester 2015/2016
Dipl.-Inf. Bert Besser
Mario Holldack
Prof. Dr. Georg Schnitger
Hannes Seiwert, M.Sc.
Institut für Informatik
AG Theoretische Informatik
Ausgabe: 12.11.15
Abgabe: 19.11.15
Übung 5
Das Schubfachprinzip: Wenn n Bälle in n−1 Schubfächer verteilt werden, dann gibt es mindestens
ein Schubfach mit mindestens zwei Bällen.
Aufgabe 5.1. Existenz- und Allaussagen, Implikationen
(5+10+15 = 30 Punkte)
a) Sei n ∈ N>0 . Auf dem Tisch liegen nebeneinander beliebige Karten k1 , k2 , . . . , kn , welche jeweils
auf einer Seite mit einem Buchstaben aus der Menge {A, B, C, . . . , Z} und auf der anderen
Seite mit einer natürlichen Zahl beschriftet sind. Wir können auf dem Tisch jeweils nur eine
der beiden Beschriftungen sehen und wollen nun testen, ob folgende Aussage wahr ist:
Steht auf einer Seite der Karte eine gerade Zahl, dann steht auf der anderen Seite ein Vokal.
C
8
3
U
Z
Abbildung 1: Zu Aufgabe 5.1 a) i)
Natürlich können wir jede Karte k1 , k2 , . . . , kn umdrehen, um den Wahrheitsgehalt der Aussage
zu überprüfen, aber es geht oft auch einfacher.
i) Ein konkretes Beispiel: Die Karten liegen wie in Abbildung 1 auf dem Tisch. Welche
Karten müssen wir umdrehen? Begründen Sie Ihre Antwort.
ii) Verallgemeinern Sie Ihre Antwort für beliebige Kartenfolgen k1 , k2 , . . . , kn .
b) Betrachten Sie eine Färbung f : N → {rot, blau} der natürlichen Zahlen. Folgende Aussage
über f sei wahr: Für jede blau gefärbte Zahl gibt es eine größere rot gefärbte Zahl.
Welche der folgenden Aussagen kann man folgern? Begründungen sind nicht erforderlich.
i)
ii)
iii)
iv)
v)
Es gibt eine blau gefärbte natürliche Zahl.
Für jede rot gefärbte natürliche Zahl gibt es eine größere rot gefärbte.
f −1 (rot) = {x ∈ N : f (x) = rot} ist unendlich.
f −1 (blau) = {x ∈ N : f (x) = blau} ist endlich.
Wenn f (1) = blau gilt, dann gibt es ein n ∈ N, sodass f (n) = blau und f (n+1) = rot gilt.
c) Sei n ∈ N mit n ≥ 2. Zu Freds Geburtstagsfeier im Vereinsheim des Dackelzüchterclubs Wily
Werewolf sind n Personen (inklusive Fred) erschienen. Manche dieser Personen kennen einander, andere wiederum nicht. Die Bekanntschaften sind symmetrisch, d. h. Person i kennt
Person j genau dann, wenn Person j Person i kennt. Bekanntschaften außerhalb des Vereinsheims werden nicht berücksichtigt.
Beweisen Sie, dass es stets zwei Personen gibt, die dieselbe Anzahl von Bekannten haben.
Hinweis: Eine Fallunterscheidung ist hilfreich. Nehmen Sie zunächst an, dass einer der Anwesenden alle anderen Personen auf Freds Geburtstagsfeier kennt. Wie kann das Schubfachprinzip
in diesem Fall angewendet werden?
1
Aufgabe 5.2. Resolution
(5+10 = 15 Punkte)
a) Zeigen Sie mit Resolution, dass die KNF-Formel
ω := (A ∨ B ∨ ¬C) ∧ (¬A) ∧ (A ∨ ¬B) ∧ (A ∨ B ∨ C)
unerfüllbar ist, indem Sie den leeren Disjunktionsterm herleiten. Zu zeigen ist also:
n
o
{A, B, ¬C}, {¬A}, {A, ¬B}, {A, B, C} `R b) Gegeben sei die Menge
n
Φ := {A, B, C}, {A, B, ¬C}, {A, ¬B, C}, {A, ¬B, ¬C},
{¬A, B, C}, {¬A, B, ¬C}, {¬A, ¬B, C}, {¬A, ¬B, ¬C}
o
von Disjunktionstermen. Leiten Sie mit Resolution den leeren Disjuktionsterm aus Φ her, d.h.
zeigen Sie:
Φ `R Hinweis: Es ist nicht zielführend, Terme zu erzeugen, die selbst in keiner weiteren Anwendung
der Resolutionsregel verwendet werden. Versuchen Sie, mit möglichst wenigen Ableitungsschritten
auszukommen.
Aufgabe 5.3. Boolesche Funktionen
(14+5+12+4 = 35 Punkte)
Für eine aussagenlogische Formel ϕ ∈ AL mit Var(ϕ) = {V1 , . . . , Vn } heißt die boolesche Funktion
fϕ : {0, 1}n → {0, 1} passend zu ϕ, wenn für alle Belegungen B mit Def(B) ⊇ {V1 , . . . , Vn } gilt:
fϕ B(V1 ), . . . , B(Vn ) = JϕKB
Die Funktion fϕ weist also der zu B gehörenden Zeile der Wahrheitstafel von ϕ den Wert JϕKB zu.
a) Sei n ∈ N>0 . Seien ϕ, ψ ∈ AL mit Var(ϕ) = Var(ψ) = {V1 , . . . , Vn } und fϕ , fψ : {0, 1}n → {0, 1}
dazu passende boolesche Funktionen. Zeigen Sie:
i) ϕ |= ψ ⇐⇒ fϕ (x) ≤ fψ (x) f.a. x ∈ {0, 1}n
ii) ϕ ≡ ψ ⇐⇒ fϕ (x) = fψ (x) f.a. x ∈ {0, 1}n
b) Sei n ∈ N>0 . Wie viele verschiedene boolesche Funktionen f : {0, 1}n → {0, 1} gibt es, d.h. wie
groß ist die Menge Abb(A, B) für A = {0, 1}n und B = {0, 1}? Beweisen Sie Ihre Antwort.
c) Zeigen Sie: Es gibt überabzählbar viele Funktionenf : {0, 1}∗ → {0, 1}, d.h. es existiert keine
surjektive Funktion von N nach Abb {0, 1}∗ , {0, 1} .
Hinweis: Passen Sie das Diagonalargument aus dem Beweis für die Nichtabzählbarkeit
von P(N)
(Satz 4.5 im Skript) an. Für eine beliebige Funktion F : N → Abb {0, 1}∗ , {0, 1} konstruiere
eine Funktion g : {0, 1}∗ → {0, 1} sodass g 6= F (n) f.a. n ∈ N.
d) Vergleichen Sie die Größen der beiden Mengen
[
Abb {0, 1}n , {0, 1} und Abb {0, 1}∗ , {0, 1} .
n∈N
Welche ist „größer“ 1 ? Oder sind beide gleichmächtig? Ein Beweis ist nicht erforderlich.
Bitte wenden!
1
Eine Menge A ist „größer“ als eine Menge B, wenn es keine surjektive Funktion s : B → A gibt.
2
Aufgabe 5.4. Beweistechniken
(5+10+5 = 20 Punkte)
a) Seien a, b ∈ N. Beweisen Sie: a · b ist gerade ⇐⇒ a ist gerade oder b ist gerade.
b) Beweisen oder widerlegen Sie:
i) Für jedes gerade k ∈ N>0 und jedes a ∈ Z gilt:
a + (a + 1) + (a + 2) + · · · + (a + k − 1) ist durch k teilbar2 .
ii) Für jedes ungerade k ∈ N>0 und jedes a ∈ Z gilt:
a + (a + 1) + (a + 2) + · · · + (a + k − 1) ist durch k teilbar.
P
Hinweis: Die Identität ni=1 i = n(n+1)
kann hilfreich sein.
2
c) Seien n ∈ N>0 und x1 , x2 , . . . , xn ∈ R. Beweisen Sie:
n
P
xi = b, dann gibt es ein i ∈ {1, 2, . . . , n} mit xi ≥ nb .
Gilt
i=1
2
Eine Zahl z ∈ Z ist durch k ∈ Z teilbar, wenn es ein l ∈ Z mit z = k · l gibt.
3

Download Report