Transcript
Universit¨ at Augsburg Institut f¨ ur Informatik
Prof. Dr. W. Vogler Dipl.-Inform. F. Bujtor
Logik fu ¨ r Informatiker WS 15/16
¨ Ubungsblatt 5 – Lo ¨sungsvorschlag (Abgabe bis Donnerstag 26.11.2015, 12:00 Uhr) Aufgabe 1: (Hilbert-Kalk¨ ul)
3 + 4 = 7 Punkte
1. Leiten Sie folgende Aussage im Hilbert-Kalk¨ ul her. Verwenden Sie nur die Axiome 1-3, Modus Ponens und die Eigenschaft ` A → A. {A → (A → B)} ` A → B L¨ osung: (1) (2) (3) (4) (5)
Die Herleitung:
A → (A → B) (A → (A → B)) → ((A → A) → (A → B)) (A → A) → (A → B) A→A A→B
trivial (∈ M) Ax2 MP (1),(2) A → A, 2.6 b MP (4),(3)
2. Leiten Sie die folgende Aussage im Hilbert-Kalk¨ ul her. Verwenden Sie nur die Axiome 1-3 und den Modus Ponens. {A → B, B → C} ` A → C Lo ¨sung: (1) (2) (3) (4) (5) (6) (7)
Die Herleitung:
B→C (B → C) → (A → (B → C)) A → (B → C) (A → (B → C)) → ((A → B) → (A → C)) (A → B) → (A → C) A→B A→C
trivial (∈ M) Ax1 MP (1), (2) Ax2 MP (3), (4) trivial (∈ M) MP (6), (5)
Gehen Sie bei den Konstruktionen der Herleitungen vor wie in Beispiel 2.6 beschrieben; versuchen Sie insbesondere, herzuleitende Aussagen (wie A → B in 2.6) als rechte Seiten von Axiomen zu erkennen. Aufgabe 2: (Deduktions-Theorem) Betrachten Sie die folgende Herleitung: (1) (2) (3) (4)
{B, B → C} ` B {B, B → C} ` B → C {B, B → C} ` C {B} ` (B → C) → C
5 Punkte
∈M ∈M MP (1) (2) Ded. (3)
In Zeile 4 wird das Deduktionstheorem verwendet. Konstruieren Sie aus dieser Herleitung eine Herleitung f¨ ur die letzte Zeile, die das Deduktionstheorem nicht verwendet. Gehen Sie dabei so vor, wie im Beweis von Satz 2.8 (Deduktionstheorem) aus der Vorlesung beschrieben!
¨ Ubungsblatt 5 (Logik f¨ ur Informatiker WS 15/16)
L¨ osung:
(1) (2) (3) (4) (5) (6) (7)
B B → ((B → C) → B) (B → C) → B (B → C) → (B → C) ((B → C) → (B → C)) → (((B → C) → B) → ((B → C) → C)) ((B → C) → B) → ((B → C) → C) (B → C) → C
2 ∈M Ax 1 MP (1) (2) B→B Ax 2 MP (4) (5) MP (3) (6)
Aufgabe 3: (Formalisierung) 5 Punkte Wir betrachten erneut die Interpretation von Blatt 3 Aufgabe 3: D sei eine Teilmenge nat¨ urlicher Zahlen. Gegeben seien die Pr¨adikatssymbole P und LE mit Interpretation ist prim“ und kleiner-gleich“ sowie die Funktionssymbole add und mult mit ” ” Interpretation + und ·. 1. M¨ogliche L¨ osungen zur 3. Teilaufgabe ( D enth¨alt 0“) waren: ” (a) ∃x add(x, x) = x L¨ osung: Gute Formalisierung. Diese Gleichung kann recht offensichtlich nur von x = 0 erf¨ ullt werden. (b) ∃x∀y add(x, y) = y L¨ osung: Gute Formalisierung: 0 ist das neutrale Element in den nat¨ urlichen Zahlen bzgl. Addition. (unn¨ otig kompliziert im gegensatz zu (a)) Im allgemeinen kann bei einer Struktur mit neutralem Element in einer Teilmenge ein anderes Element neutral sein. (z.B. Maximumsbildung auf {0, 1} mit Teilmenge {1}) (c) ∃x mult(x, x) = x Lo ullt, ¨sung: Schlichtweg falsch. Falls D = N \ 0 so ist die Formel (wegen 1) erf¨ obwohl die 0 nicht in der Grundmenge ist. (d) ∃x∀y mult(x, y) = x L¨ osung: Dies ist keine gute Formalisierung, da nicht offensichtlich ist, dass sie ¨ korrekt ist. F¨ ur D = {1} w¨are die Formel auch erf¨ ullt. Erst durch weitere Uberlegungen kann man einsehen, dass solch problematische D wegen dem Abschluss unter Addition nicht zugelassen sind. Bewerten Sie die Angemessenheit dieser Formalisierungen. (Selbstverst¨andlich mit Begr¨ undung) 2. Geben Sie eine Formel an, die besagt, dass x das Doppelte von y ist. (x, y ungebunden) L¨ osung:
x = add(y, y)
3. Geben Sie eine Formel an, die besagt, dass x das Dreifache von y ist. (x, y ungebunden) L¨ osung:
x = add(add(y, y), y)
¨ Ubungsblatt 5 (Logik f¨ ur Informatiker WS 15/16)
3
Aufgabe 4: (Beweis) 5 Punkte Seien F und G aussagenlogische Formeln, die keine gemeinsamen Atome haben. Zeigen Sie: Ist F → G eine Tautologie, so ist F nicht erf¨ ullbar oder G ist eine Tautologie. Tipp: Zeigen Sie die Kontraposition der Aussage. L¨ osung: F habe die Atome p1 , p2 , . . . , pi und G die Atome pi+1 , . . . , pn . Angenommen F ist erf¨ ullbar und G ist keine Tautologie. Dann gibt es Interpretationen I1 mit I1 |= F und I2 mit I2 6|= G. Aus I1 und I2 konstruieren wir eine neue Interpration I, die sich bei p1 , . . . , pi wie I1 , bei pi+1 , . . . , pn wie I2 verh¨alt. Offensichtlich gelten analog I |= F und I 6|= G. Mit (vgl. A4) folgt I 6|= F → G. Also ist F → G keine Tautologie. Aufgabe 5: (Alice II) 3 Punkte Der L¨owe und das Einhorn waren nicht die einzigen Besucher im Wald der Vergesslichkeit. Die Zwillinge Tweedledee und Tweedledum gingen dort auch ein und aus. Einer von ihnen verhielt sich wie der L¨ owe. Er log montags, dienstags und mittwochs. Der andere verhielt sich wie das Einhorn, er log Donnerstags, Freitags und Samstags. Leider wusste Alice nicht, welcher von beiden sich wie verhielt. Noch dazu konnte sie die beiden vom Sehen her nicht auseinanderhalten, weil sie sich so a ¨hnlich sahen. Wichtig: Begr¨ unden Sie, wie immer, Ihre Antworten knapp. 1. Eines Tages trifft Alice die Zwillinge, die folgendes behaupten: • Der eine: Ich bin Tweedledum.“ ” • Der andere: Ich bin Tweedledee.“ ” Welcher ist welcher Zwilling und an welchem Wochentag geschah das? L¨ osung: Nachdem nur einer Tweedledee und einer Tweedledum sein kann, m¨ ussen beide l¨ ugen oder beide die Wahrheit sagen. Das kann nur an einem Sonntag passieren, da sonst immer einer von ihnen l¨ ugt. Also ist Jeder wer er behauptet zu sein. 2. An einem anderen Tag derselben Woche behaupteten die beiden folgendes: • Der eine: Ich bin Tweedledum.“ ” • Der andere: Wenn das stimmt, dann bin ich Tweedledee.“ ” Welcher von den beiden ist welcher? L¨ osung: Die zweite Aussage ist sicherlich wahr. Nachdem es aber nicht derselbe Tag ist wie in 1., k¨ onnen nicht beide die Wahrheit sagen. Also ist der erste Tweedledee und der zweite Tweedledum. 3. Es gab zwei Tage, an denen Alice nur jeweils einen der Zwillinge getroffen hat. An dem einen Tag sagte der Zwilling: Ich l¨ uge heute und ich bin Tweedledee“. Am anderen Tag ” sagte der Zwilling (Alice wusste nicht, ob es derselbe war): Ich l¨ uge heute oder ich bin ” Tweedledee“. Kann man herausfinden, welchem der Zwillinge sie an dem einen, bzw. dem anderen Tag begegnet ist? Wenn ja, dann geben Sie dies auch an. L¨ osung: Die erste Aussage muss gelogen gewesen sein. Wenn sie wahr w¨are h¨atte das zur Folge, dass der Sprecher l¨ ugen w¨ urde, was ein offensichtlicher Widerspruch ist. Wenn die Aussage aber gelogen ist, ist ihr erster Teil wahr, also muss der zweite falsch sein. Damit ist der Sprecher Tweedledum. Auch im zweiten Fall kann der Sprecher identifiziert werden: Wenn er l¨ ugen w¨ urde, dann w¨are der der erste Teil und damit die ganze Aussage wahr. Also muss er die Wahrheit sagen. Nachdem deswegen der erste Teil falsch ist, muss der zweite wahr sein. Damit ist der Sprecher Tweedledee.
¨ Ubungsblatt 5 (Logik f¨ ur Informatiker WS 15/16)
4
4. An einem ganz besonderen Tag konnte Alice ihre Neugier in dreierlei Hinsicht befriedigen. Sie traf die beiden Zwillinge und konnte anhand ihrer Aussagen feststellen: 1. Welcher Tag es war, 2. Welcher von den beiden Tweedledee und welcher Tweedledum war und 3. welcher von den beiden sich wie der L¨owe verhielt. Die Aussagen waren die folgenden: • Der eine: Heute ist nicht Sonntag.“ ” • Der andere: Genauer gesagt ist sogar Montag.“ ” • Der eine: Morgen wird Tweedledee l¨ ugen.“ ” • Der andere: Der L¨ owe hat gestern gelogen.“ ” Finden Sie die Antworten zu den drei Fragen. L¨ osung: Aus der ersten Aussage wissen wir, dass nicht Sonntag ist und dass der erste die Wahrheit sagt. Wenn Sonntag w¨are, w¨ urde er l¨ ugen, was aber Sonntags keiner von beiden macht. Nachdem nicht Sonntag ist und der erste die Wahrheit spricht, l¨ ugt der zweite. Damit ist heute auch nicht Montag. Die vierte Aussage ist auch gelogen, womit wir Dienstag, Mittwoch und Donnerstag ebenfalls ausschließen k¨ onnen. Es bleiben Freitag und Samstag. Nachdem die dritte Aussage wahr ist, kann nicht Samstag sein, sonst w¨ urde Tweedledee am Sonntag l¨ ugen. Also ist es Freitag und Tweedledee l¨ ugt Samstags. Er ist also wie das Einhorn und damit ist Tweedledum wie der L¨owe. Aus diesen Tatsachen schließen wir, dass der ” eine“ Tweedledum und der andere“ Tweedledee ist. ”
