Transcript
Institut für Theoretische Informatik
ITI
Dr. J¨ urgen Koslowski
Einfu ¨ hrung in die Logik Aufgabenblatt 7, 2016-06-14
Aufgabe 36 [optional 14 PUNKTE] Der ber¨ uhmte Vierfarbensatz besagt, dass man auf jedem Globus mit endlich vielen zusammenh¨ angenden(!) L¨ andern diese so mit vier Farben einf¨arben kann, dass benachbarte L¨ander stets unterschiedliche Farben haben. Zeigen Sie mit Hilfe des Kompaktheitssatzes, dass der Vierfarbensatz auch f¨ ur Globen mit unendlich vielen L¨andern gilt. ¨ Hinweis: Ubersetzen Sie das Problem in ein Problem u uhren Sie ¨ber ungerichtete Graphen; f¨ atomare Formeln ein, die die m¨ oglichen Farben eines jeden Knoten ausdr¨ ucken; konstruieren Sie eine Formel, die die korrekte 4-F¨ arbbarkeit des Graphen ausdr¨ uckt. Um Spitzfindigkeiten vorzubeugen: L¨ander heißen benachbart, wenn sie ein gemeinsames St¨ uck Grenze haben, das keine Ecke ist, wobei man unter Ecken Punkte auf dem Globus versteht, die zu drei oder mehr L¨ andern geh¨oren (etwa der Mittelpunkt eines Tortendiagrams). F¨ ur Neugierige: Wieviele Farben braucht man, wenn man die Kugel (Globus) durch einen Torus ersetzt? Aufgabe 37 [10 PUNKTE] Gegeben sei die DNF F := ¬D ∨ (A ∧ B ∧ ¬C) ∨ ¬A ∨ (D ∧ ¬B) ∨ (B ∧ C). (a) [6 punkte] Zeigen Sie mit Hilfe des Markierungsalgorithmus, dass F eine Tautologie ist. (b) [4 punkte] Welche Eigenschaft muss eine DNF haben, damit man mit der Methode aus Teil (a) entscheiden kann, ob sie eine Tautologie ist?
Aufgabe 38 [optional 14 PUNKTE] Weisen Sie die Sequenz ¬G ∧ ¬H ` ¬(G ∨ H) aus Beispiel 7.6.4 nach, indem Sie f¨ ur die Disjunktion und die Negation die modifizierten Schlußregeln aus dem Programm von Herrn Grunwald auf Seite 61 oben verwenden. [Hinweis: eine Herleitung in weniger als 20 Zeilen ist m¨ oglich.] Aufgabe 39 basiert auf dem Stoff der n¨achsten Vorlesung. Aufgabe 39 [12 PUNKTE] Die Signatur Σ enthalte ein 2-stelliges Pr¨adikatensymbol P , Funktionssymbole c (0-stellig, Konstante), f (1-stellig) und g (2-stellig). Welche der folgenden Ausdr¨ ucke in den Variablen x, y und z sind korrekt gebildete Formeln u ¨ber Σ? (a) [2 punkte] ∀x : (∃x : ((x = z) ∧ (P (f (c), g(c, x)) ∨ (f (x) = x)) ⇒ z)) (b) [2 punkte] (x = c) ∨ (∀x : (P (x) ∧ (f (g(z, y)) = c)) (c) [2 punkte] ∃y : (∀x : ((g(x, y) = c) ∧ ¬(c = x)))
(d) [2 punkte] (f (x) = c) ∧ (∃c : (c = x)) (e) [2 punkte] ∃x : (y = f (g(x, x), x)) ( f ) [2 punkte] ∀x : (P (f (g(f (f (f (x))), f (g(x, x)))))) Identifizieren Sie die Fehler bei den unzul¨assigen Formeln und geben Sie bei den zul¨assigen Formeln jeweils die freien und die gebundenen Variablen an.
Abgabe bis Montag, 2016-06-21, im Kasten neben IZ 343
