Blatt 4 - Professur für Theoretische Informatik

Diskrete Modellierung
Wintersemester 2015/2016
Dipl.-Inf. Bert Besser
Mario Holldack
Institut für Informatik
AG Theoretische Informatik
Prof. Dr. Georg Schnitger
Hannes Seiwert, M.Sc.
Ausgabe: 05.11.15
Abgabe: 12.11.15
Übung 4
Aufgabe 4.1.
Ivan, und nu? Navi!
(12+12 = 24 Punkte)
Ivan hat groÿe Probleme, sich in seiner Stadt zu orientieren. Das Straÿennetz besteht aus einer Menge
von Kreuzungen K := {1, 2}×{1, 2, . . . , n+1}. Zwischen je zwei Kreuzungen (1, b), (2, b) ∈ K verläuft
eine (vertikale) Straÿe, zwischen je zwei Kreuzungen (a, b), (a, b+1) ∈ K verläuft eine (horizontale) Straÿe. Alle Straÿe sind Einbahnstraÿen: Sie können nur von oben nach unten bzw. von links
nach rechts befahren werden. Ivan wohnt an Kreuzung (1, 1), der Eingang zum Einkaufszentrum
bendet sich an Kreuzung (2, n+1). Dort hat er sich ein neues Navi gekauft. Um weiteres Zubehör
zu erwerben, möchte er mit dem Auto zum Einkaufszentrum fahren.
Das Verkehrsamt muss allerdings einige der horizontal verlaufenden Straÿenabschnitte erneuern lassen und richtet dazu Baustellen ein. Ein Straÿenabschnitt mit Baustelle wird voll gesperrt, die Straÿe
ist also nicht mehr befahrbar. Glücklicherweise kann das Navi über das Internet auf den neuesten
Aussagenlogik-Cloud-Service (ALCS) zugreifen und so herausnden, ob ein Ziel erreichbar ist.
ALCS verwendet die aussagenlogischen Variablen X1 , . . . , Xn , Y1 , . . . , Yn , wobei Variable Xi ausdrückt, dass der Straÿenabschnitt zwischen den Kreuzungen (1, i) und (1, i+1) gesperrt ist, und Yi
ausdrückt, dass der Straÿenabschnitt zwischen (2, i) und (2, i+1) gesperrt ist.
a) Bestimmen Sie für allgemeines1 n ≥ 3 eine Formel ϕn in DNF, die ausdrückt, dass Ivan das
Einkaufszentrum trotz der Baustellen erreichen kann, dass es also einen baustellenfreien Weg
von Ivans Wohnung zum Einkaufszentrum gibt.
Beschreiben Sie zuerst Ihre Idee bzw. skizzieren Sie Ihren Lösungsweg.
Hinweis : Wie sehen die Primimplikanten von ϕn aus?
b) Bestimmen Sie für allgemeines1 n ≥ 3 eine Formel ψn in KNF, die dasselbe wie ϕn ausdrückt.
Sie können dabei z.B. folgendermaÿen vorgehen:
• Bestimmen Sie eine DNF χn für ¬ϕn , wobei ϕn die Formel aus Teil a) ist.
• Formen Sie ¬χn durch Anwendung der De Morganschen Regeln in eine KNF um.
Beschreiben Sie zuerst Ihre Idee bzw. skizzieren Sie Ihren Lösungsweg.
1
Sie dürfen
n
also nicht auf eine Zahl festsetzen.
1
Aufgabe 4.2.
Schie versenken
(3+10+5+2+7 = 27 Punkte)
Analog zum Sudoku-Beispiel aus der Vorlesung behandeln wir in dieser Aufgabe eine Variante des
Spiels Schie versenken auf einem (n×n)-Spielfeld. Die Zeilen und Spalten sind jeweils von 1 bis n
durchnummeriert. Den Spielern stehen beliebig viele Schie des Typs 1 und des Typs 2 (siehe Abbildung 1) zur Verfügung, die jeweils eine bzw. zwei benachbarte Zellen einer Zeile oder Spalte belegen.
In jede Zelle des Spielfeldes muss entweder ein Schi (bzw. ein Teil eines Schis) oder Wasser platziert
werden. Gegeben ist auÿerdem eine Teilmenge W ⊆ {1, 2, . . . , n}2 der Spielfeldzellen.
s
s
(a)
Typ 1
(b)
Abbildung 1:
s
s
oder
s
Typ 2
Schistypen
Schie dürfen nach den folgenden Regeln auf das Spielfeld gesetzt werden:
1. Randzellen dürfen nicht von Schien belegt sein, d. h. Zeile 1 und Spalte 1 sowie Zeile n und
Spalte n beinhalten nur Wasser.
2. Für jedes Paar (i, j) ∈ W muss die Zelle in Zeile i und Spalte j mit Wasser belegt sein.
3. Zwischen je zwei Schien muss mindestens eine Wasser-Zelle vorhanden sein, d. h. jedes Schi
muss in allen Richtungen (auch diagonal) von Wasser-Zellen umgeben sein.
4. Für alle i ∈ {2, . . . , n − 1} gilt: In Zeile i ist mindestens eine Zelle mit einem Schi belegt.
1
2
3
4
5
6
(a)
Abbildung 2:
1
◦
◦
◦
◦
◦
◦
2
◦
3
◦
s
s
◦ ≈
s ◦
s ◦
◦ ◦
4
◦
◦
≈
◦
≈
◦
5
◦
◦
6
◦
◦
s ◦
◦ ◦
≈ ◦
◦ ◦
legale Konguration
1
2
3
4
5
6
1
◦
◦
◦
◦
◦
◦
2
◦
3
◦
s
s
(b)
illegale Konguration
◦ ≈
s ◦
◦ s
◦ ◦
4
◦
5
◦
s ◦
≈ ◦
◦ s
≈ ≈
◦ ◦
6
◦
◦
◦
s
◦
◦
Kongurationen des Spielfelds für n = 6 und W = {(3, 3), (3, 4), (5, 4), (5, 5)}.
a) Sei n = 5 und W = {(3, 2), (3, 3)}. Skizzieren Sie (analog zu Abbildung 2) eine legale Konguration des Spielfelds mit mindestens zwei Schien des Typs 1 und einem Schi des Typs 2.
Erläutern Sie in b) bis e) jeweils die Idee hinter Ihren Formeln. Fertigen Sie ggf. eine Skizze an. Was
möchten Sie ausdrücken? Weitere Begründungen sind nicht erforderlich.
b) Stellen Sie jede der Spielregeln 1 bis 4 als aussagenlogische Formel ϕ1 , . . . , ϕ4 dar.
Benutzen Sie die Variablenmenge {Xi,j : i, j ∈ {1, . . . , n}}, wobei Xi,j ausdrückt, dass die Zelle
in Zeile i und Spalte j mit einem Schi (oder mit einem Teil eines Schis) belegt ist.
Sie dürfen in den Teilaufgaben b), c) und d) der Einfachheit halber annehmen, dass nur Schie
des Typs 1 verwendet werden.
Hinweis : Welche Bedingung für Zelle (i, j + 1) folgt, wenn Zelle (i, j) mit einem Schi besetzt ist? Wie
lässt sich diese Bedingung als Disjunktionsterm formulieren? Welche weiteren Bedingungen müssen
formuliert werden, wenn Zelle (i, j) von einem Schi besetzt ist?
c) Geben Sie zu jeder Formel ϕi aus b), die
nicht in KNF vorliegt, eine äquivalente KNF ψi an.
d) Geben Sie eine Formel ψ in KNF an, die besagt, dass alle Spielregeln eingehalten werden.
e) Nun sind Schie beider Typen erlaubt. Modizieren Sie Ihre Formel ϕ3 aus b) (oder ψ3 aus c))
in geeigneter Weise, um Regel 3 für beide Schistypen zu beschreiben.
2
Aufgabe 4.3.
DNFs, KNFs, Implikanten und Primimplikanten
(4+20 = 24 Punkte)
a) Bestimmen Sie für jede der folgenden Formeln ϕi , ob sie in DNF und/oder in KNF vorliegt.
Eine Begründung ist nicht notwendig.
• ϕ1 = (V4 ∧ V3 ) ∧ ¬V2
• ϕ3 = (¬¬V0 ∧ V0 )
• ϕ2 = (¬(V2 ∧ V2 ) ∨ V5 )
• ϕ4 = (¬V5 ∧ V6 ) ∨ (¬V6 ∧ V5 )
b) Sei ψ eine Formel mit Var(ψ) = {X1 , X2 , X3 }, für die gelte:
JψKB = 1 ⇐⇒ B(X1 ), B(X2 ), B(X3 ) enthält mindestens zwei 1en.
i) Bestimmen Sie die kanonische DNF sowie die kanonische KNF für ψ .
ii) Weisen Sie nach, dass X1 ∧ X2 ∧ X3 ein Implikant von ψ ist.
iii) Weisen Sie nach, dass X2
kein Implikant von ψ ist.
iv) Weisen Sie nach, dass X1 ∧ X2 ein Primimplikant von ψ ist.
v) Bestimmen Sie alle Primimplikanten von ψ und nden Sie eine möglichst kleine DNF für
ψ , d. h. eine DNF, die möglichst wenige Konjunktionsterme enthält.
Aufgabe 4.4.
Keine Wahrheitstafeln
(5+5+5+5+5 = 25 Punkte)
Im Allgemeinen ist es nicht praktikabel, (Eigenschaften von) Formeln mit Hilfe von Wahrheitstafeln
zu erkunden: Die Wahrheitstafel einer gegebenen Formel ist mitunter so groÿ, dass sie per Hand oder sogar maschinell nicht schnell genug verarbeitet werden kann.
Beantworten Sie die Fragen ohne Verwendung von Wahrheitstafeln. Begründen Sie jeweils Ihre Antwort, indem Sie z.B. eine (äquivalente) Umformung vornehmen oder logische Schlüsse ziehen.
a) Sind die folgenden Formeln erfüllbar? Wenn ja, warum? Wenn nein, warum nicht?
i)
(A → B) → (C → D) → C ∧ C ∧ D ∧ E ∧ F
ii)
(A → B) → (C → D) → C ∧ ¬C ∧ D ∧ E ∧ F
b) Sei n ∈ N mit n ≥ 3 beliebig (Sie dürfen n also nicht auf eine Zahl festsetzen). Wir suchen
nach erfüllenden Belegungen B : {V1 , . . . , Vn } → {0, 1} für die folgenden Formeln auf den
Variablen V1 , . . . , Vn .
Vn−1
i) Geben Sie alle erfüllenden Belegungen der Formel i=1
(Vi ⊕ Vi+1 ) an. Warum gibt es
keine weiteren erfüllenden Belegungen?
V
ii) Geben Sie alle erfüllenden Belegungen der Formel i,j∈{1,...,n} (Vi ⊕ Vj ) an.
c) Gilt die folgende Äquivalenz? Begründen Sie Ihre Antwort.
(Vn → V1 ) ∧
n−1
^
¬Vi ∨ Vi+1
i=1
!
?
≡
^
(Vj ↔ Vk )
j,k∈{1,...,n}
3

Download Report