Transcript
Institut für Theoretische Informatik
ITI
Dr. J¨ urgen Koslowski
Einfu ¨ hrung in die Logik Aufgabenblatt 4, 2016-05-09
¨ Ubungsaufgabe 21 Tick, Trick und Track sind durch den Konsum gewaltorientierte Computerspiele endg¨ ultig auf die schiefe Bahn eraten und haben Onkel Dagoberts Geldspeicher ausgeraubt. Beim Polizeiverh¨ or m¨ ochte Kommissar Hunter wissen, was mit der Beute geschehen ist und nimmt folgende Aussagen auf: Tick: Wir haben Geld im Wald vergraben und im See versenkt. Trick: Normalerweise verstecken wir nichts zu Hause und bringen auch nichts zur Bank, wenn wir Geld im Wald vergraben. Track: Trick wollte etwas Geld zur Bank bringen oder f¨ ur einen guten Zweck spenden. Trick: Genau, und wenn wir etwas spenden, dann vergraben wir nichts im Wald. Kommissar Hunter ist emp¨ ort: Mindestens einer von Euch bel¨ ugt mich doch!“ ” (a) Formalisieren Sie die Aussagen in der Aussagenlogik. (b) Zeigen Sie mit Hilfe der Resolutionsmethode, dass Kommissar Hunter recht hat.
Aufgabe 22 [13 PUNKTE] (a) Formen Sie F = ((A ⇒ B) ⇒ C) ⇒ (C ⇒ (A ⇒ B)) um in – [3 punkte] NNF – [1 punkt] DNF – [3 punkte] KNF (b) [6 punkte] Testen Sie die Formel G = (C ⇒ B) ∧ (C ⇒ ¬A) ∧ (¬A ∨ C) ∧ (¬A ∧ C ⇒ B) mit der Resolutionsmethode auf Erf¨ ullbarkeit.
Aufgabe 23 [15 PUNKTE] Schneewittchen m¨ ochte in die Stadt einkaufen gehen und die Zwerge beschließen, dass mindestens einer von ihnen sie begleitet. Drei der Zwerge scheiden als Begleitung aus, da sie Holz hacken m¨ ussen. Die m¨ oglichen Begleiter, die Zwerge Alberich, Gimli, R¨ ubezahl und Zwergnase, diskutieren, wer mit in die Stadt geht. Alberich: “Wenn Gimli nicht geht und R¨ ubezahl nicht geht, dann geh’ ich auch nicht.” Gimli: “Ich gehe nur, wenn R¨ ubezahl oder Zwergnase mitgehen.” R¨ ubezahl: “Wenn Gimli nicht geht, dann gehe ich auch nicht.” Zwergnase: “Ich gehe nur, wenn Gimli nicht mitkommt. Wenn R¨ ubezahl geht, dann will ich auf jeden Fall mit.”
Zeigen Sie mit Hilfe der Resolutionsmethode, dass die vier Zwerge nur zufrieden sind, wenn Zwergnase als einziger mit Schneewittchen in die Stadt geht. Aufgabe 24 [8 PUNKTE] Verwenden Sie die Resolutionsmethode, um (a) [4 punkte] die Erf¨ ullbarkeit von F = ((M ⇒ A) ∨ (¬T ∧ H)) ∧ (M ∨ A) ∧ (¬(T ⇒ H) ∨ A)) zu analysieren, (b) [4 punkte] G = (A ⇒ B) ∨ (A ∧ ¬(B ∨ C)) ∨ (A ∧ C) als Tautologie zu identifizieren.
Abgabe bis Montag, 2016-05-23, im Kasten neben IZ 343
