Einführung in die Logik

Institut für
Theoretische Informatik
ITI
Dr. Jürgen Koslowski
Einführung in die Logik
Aufgabenblatt 4, 2016-05-09
Übungsaufgabe 21
Tick, Trick und Track sind durch den Konsum gewaltorientierte Computerspiele endgültig
auf die schiefe Bahn eraten und haben Onkel Dagoberts Geldspeicher ausgeraubt. Beim Polizeiverhör möchte 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 für einen guten Zweck spenden.
Trick: Genau, und wenn wir etwas spenden, dann vergraben wir nichts im Wald.
Kommissar Hunter ist empört: Mindestens einer von Euch belügt 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 Erfüllbarkeit.
Aufgabe 23 [15 PUNKTE]
Schneewittchen möchte 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 müssen. Die möglichen Begleiter, die Zwerge Alberich, Gimli, Rübezahl und Zwergnase,
diskutieren, wer mit in die Stadt geht.
Alberich: “Wenn Gimli nicht geht und Rübezahl nicht geht, dann geh’ ich auch nicht.”
Gimli: “Ich gehe nur, wenn Rübezahl oder Zwergnase mitgehen.”
Rübezahl: “Wenn Gimli nicht geht, dann gehe ich auch nicht.”
Zwergnase: “Ich gehe nur, wenn Gimli nicht mitkommt. Wenn Rübezahl 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 Erfüllbarkeit 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

Download Report