Einführung in die Logik

Institut für
Theoretische Informatik
ITI
Dr. Jürgen Koslowski
Einführung in die Logik
Aufgabenblatt 7, 2016-06-14
Aufgabe 36 [optional 14 PUNKTE]
Der berühmte Vierfarbensatz besagt, dass man auf jedem Globus mit endlich vielen zusammenhängenden(!) Ländern diese so mit vier Farben einfärben kann, dass benachbarte Länder
stets unterschiedliche Farben haben. Zeigen Sie mit Hilfe des Kompaktheitssatzes, dass der
Vierfarbensatz auch für Globen mit unendlich vielen Ländern gilt.
Hinweis: Übersetzen Sie das Problem in ein Problem über ungerichtete Graphen; führen Sie
atomare Formeln ein, die die möglichen Farben eines jeden Knoten ausdrücken; konstruieren
Sie eine Formel, die die korrekte 4-Färbbarkeit des Graphen ausdrückt.
Um Spitzfindigkeiten vorzubeugen: Länder heißen benachbart, wenn sie ein gemeinsames
Stück Grenze haben, das keine Ecke ist, wobei man unter Ecken Punkte auf dem Globus
versteht, die zu drei oder mehr Ländern gehören (etwa der Mittelpunkt eines Tortendiagrams).
Für 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 für 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
möglich.]
Aufgabe 39 basiert auf dem Stoff der nächsten Vorlesung.
Aufgabe 39 [12 PUNKTE]
Die Signatur Σ enthalte ein 2-stelliges Prädikatensymbol P , Funktionssymbole c (0-stellig, Konstante), f (1-stellig) und g (2-stellig). Welche der folgenden Ausdrücke 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 unzulässigen Formeln und geben Sie bei den zulässigen
Formeln jeweils die freien und die gebundenen Variablen an.
Abgabe bis Montag, 2016-06-21, im Kasten neben IZ 343

Download Report