Transcript
Institut für Theoretische Informatik
ITI
Prof. Dr. J. Adámek · Dipl.-Math. Dipl.-Inf. H. Urbat
Einführung in die Logik Aufgabenblatt 5
Übungsaufgabe 1 Testen Sie die KNF (B ∨¬C)∧(¬A∨¬C)∧(¬A∨C)∧(A∨B ∨¬C) mit der Resolutionsmethode auf Erfüllbarkeit. Hausaufgabe 1 [10 PUNKTE] Tick, Trick und Track sind durch den Konsum gewaltorientierter Computerspiele auf die schiefe Bahn geraten und haben Onkel Dagoberts Geldspeicher ausgeraubt. Beim Polizeiverhör mö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 für einen guten Zweck spenden. Trick: Genau, und wenn wir etwas spenden, dann vergraben wir nichts im Wald. Kommissar Hunter ist empört: ”Mindestens einer von euch belügt mich doch!” (a) [4 PUNKTE] Formalisieren Sie die Aussagen von Tick, Trick und Track in Aussagenlogik. (b) [6 PUNKTE] Zeigen Sie mit der Resolutionsmethode, dass Kommissar Hunter recht hat. Hausaufgabe 2 [8 PUNKTE] Sei F eine KNF in den Atomen A1 , . . . , An mit höchstens zwei Literalen pro Klausel. Zeigen Sie, dass die Resolutionsmethode für F maximal O(n2 ) Resolventen erzeugt. (Die Resolutionsmethode liefert in diesem Fall also einen effizienten Erfüllbarkeitstest für F .) Hausaufgabe 3 [10 PUNKTE] Sei F eine Formel mit vollständiger Klammerung gemäß Definition 2.3 im Vorlesungsskript. Beweisen Sie mittels Strukturinduktion: Wenn F kein Atom ist, sind mindestens 60 Prozent der Symbole von F keine Atome. (Beispiel: Die Formel F = ((¬A) ∨ A) hat die Länge 8 und enthält zwei Atome; also sind 75 Prozent der Symbole keine Atome.) Hausaufgabe 4 [10 PUNKTE] Für Atome A und B seien die Formeln Fn (n ≥ 1) induktiv wie folgt definiert: ( (Fn ⇒ A), n gerade; F1 := A und Fn+1 := (Fn ⇒ B), n ungerade. Zeigen Sie, dass Fn für kein n ≥ 1 eine Tautologie ist. Der Beweis soll per Induktion erfolgen; dabei kann es hilfreich sein, eine stärkere Aussage zu beweisen.
Abgabe bis Freitag, 22.5., 14:00 Uhr, in den Briefkästen vor Raum IZ 343
