Transcript
¨ ¨r Informatiker Ubungen zur Vorlesung Logik fu Gabriele Kern-Isberner Martin Schuster Nils Vortmeier
WS 2015/16
¨ Ubungsblatt 3
9.11.2015
Abgabe bis zum 16.11.2015 um 10:10 Uhr • (vor der Vorlesung) im HG II, HS 3, oder • in den Briefkästen mit den Nummern 26-31 im Durchgangsflur, der die 1. Etage der OH 12 mit dem Erdgeschoss der OH 14 verbindet. Es gelten die Bedingungen von Blatt 1 und 2.
Quizfragen: Welche der folgenden Aussagen sind richtig, welche sind falsch? Und warum?
keine Punkte
1. Sei G = {(A ∨ B ∨ ¬C), (A ∨ ¬B ∨ C)}. Dann gilt G |= A. 2. Sei G eine Menge von aussagenlogischen Formeln und ϕ eine aussagenlogische Formel. Wenn ϕ allgemeingültig ist, dann gilt 2 ∈ Res∞ (G ∪ {¬ϕ}). 3. Sei G eine Menge von aussagenlogischen Formeln und ϕ eine aussagenlogische Formel. Wenn ϕ unerfüllbar ist, dann gilt 2 6∈ Res∞ (G ∪ {¬ϕ}).
Aufgabe 3.1 [Erfüllbarkeitstest] 3 Punkte Viele Behauptungen können dadurch überprüft werden, dass eine Menge K von Klauseln auf Erfüllbarkeit getestet wird. So gilt zum Beispiel die Behauptung „Es gilt {A} |= B.“ genau dann, wenn die Klauselmenge K = {{A}, {¬B}} unerfüllbar ist. Bestimmen Sie für die Behauptungen a) und b) jeweils eine Menge K von Klauseln, so dass mit einem Erfüllbarkeitstest auf K die Gültigkeit der Behauptung überprüft werden kann. Beschreiben Sie genau, wie der Zusammenhang zwischen der Erfüllbarkeit von K und der Gültigkeit der jeweiligen Behauptung ist. Die Erfüllbarkeit von K soll nicht getestet werden. a) Es gilt (C ∨ D) ∈ Cn({A ∨ B, B → (C ∨ D)}). b) Die Formeln A und (B ∨ C) sind semantisch äquivalent (d.h. A ≡ (B ∨ C)).
(1 Punkt) (2 Punkte)
Übungsblatt 3
Übungen zur Logik
Seite 2
Aufgabe 3.2 [Filmabend] 7 Punkte Der kleine Tim möchte mit seinen Freunden einen Filmabend veranstalten. Essen und Getränke stehen schon bereit, nun müssen sie sich „nur“ noch darauf einigen, welche Filme sie schauen wollen. Zur Auswahl stehen die vier Filme: Der Pate, The Dark Knight, Star Wars: Episode IV und Forrest Gump. Wie erwartet gibt es einige Vorbehalte und Einschränkungen bezüglich der Filmauswahl: 1. Die Gruppe schaut auf jeden Fall einen der vier Filme. 2. Tim hat Forrest Gump schon recht häufig gesehen, deshalb wird er nur zustimmen, diesen Film zu schauen, wenn sie auch einen weiteren Film schauen. 3. Auf Grund der ungeschriebenen Regel, dass schwarz gekleidete Personen mit übermenschlichen Fähigkeiten nur im Doppel auftreten dürfen, schauen sie The Dark Knight genau dann, wenn sie auch Star Wars schauen. 4. Da der kleine Tim auch irgendwann schlafen muss, können sie nicht Star Wars schauen, wenn sie Der Pate und The Dark Knight schauen. 5. Weiterhin einigen sie sich darauf, dass sie nur dann Der Pate nicht schauen, wenn sie nicht The Dark Knight oder nicht Star Wars schauen. 6. Als letzte Bedingung stellen sie auf, dass sie Forrest Gump oder Star Wars schauen, wenn sie Der Pate sehen. a) Modellieren Sie die beschriebene Situation mit den Mitteln der Aussagenlogik. Geben Sie dazu zunächst die verwendeten aussagenlogischen Variablen und deren intendierte Bedeutung an. Stellen Sie anschließend eine aussagenlogische Formel auf, welche die für die Filmauswahl relevante Situation modelliert. (3 Punkte) b) Zeigen Sie, dass die Gruppe Der Pate und Forrest Gump schaut und keinen der anderen beiden Filme. Benutzen Sie die Resolutionsmethode! (4 Punkte)
Zusatzaufgabe [Nicht-Äquivalenz] 2 Punkte Zeigen Sie: Nicht zu jeder aussagenlogischen Formel ϕ gibt es eine äquivalente aussagenlogische Formel ϕ′ , die nur die Operatoren ∧, ∨ und → enthält, aber nicht den Operator ¬ und nicht das Symbol ⊥.
