Übungen zur Vorlesung Logik für Informatiker WS 2008/09, Blatt 12

Dies ist das letzte Übungsblatt!

Abgabe: Mittwoch, 4. Februar 2009, vor der Vorlesung Schreiben Sie bitte den Namen Ihres Tutors auf Ihr Lösungsblatt!

Aufgabe 1. (Die Bearbeitung dieser Aufgabe ist verbindlich.) Die Formel

φ = ∀v_{2}((∀v_{0}∀v_{1}(B(v_{0}, v_{1}) → B(v_{0}, g(v_{1})))) → (∀v_{1}(B(v_{2}, v_{1}) → B(v_{2}, g(g(v_{1}))))))

ist allgemeingültig (vergleiche Aufgabe 1 auf Blatt 9). Zeigen Sie dies, indem Sie wie folgt vorgehen:

1. Geben Sie eine Herbrand-Normalform ∃x_{1} … ∃x_{n}ψ(x_{1}, …, x_{n}) zu φ an.

2. Finden Sie Terme t_{1}^{1}, t_{2}^{1}, …, t_{n}^{1}, …, t_{1}^{N}, t_{2}^{N}, … t_{n}^{N}, für die ⋁_{i=1}^{N} ψ(t^{i}) allgemeingültig

ist.

3. Zeigen Sie die Allgemeingültigkeit von ⋁_{i=1}^{N} ψ(t^{i}) mittels Resolution.

Aufgabe 2. Formalisieren Sie die folgenden Aussagen:

1) Jeder Barbier rasiert alle Personen, die sich nicht selbst rasieren.

2) Kein Barbier rasiert jemanden, der sich selbst rasiert.

Verwenden Sie dabei B(x) für “x ist ein Barbier” und R(x, y) für “x rasiert y”. Folgern Sie wie in Aufgabe 1, daß es keine Barbiere gibt.

Aufgabe 3. Gegeben sei eine quantorenfreie Formel ψ(x_{1}, …, x_{n}) ohne Gleichheitszeichen. Kann man effektiv entscheiden, ob es eine natürliche Zahl N und konstante Terme

t_{1}^{1}, t_{2}^{1}, …, t_{n}^{1}, …, t_{1}^{N}, t_{2}^{N}, … t_{n}^{N}

gibt, für die

⋁_{i=1}^{N} ψ(t^{i})

allgemeingültig ist? Begründen Sie Ihre Antwort und vergleichen Sie sie mit Folgerung 2.5.7. der Vorlesung.

Aufgabe 4. Gegeben sei die Formel φ = ∀x∃yR(x, y) in der Sprache L = {R}. Geben Sie ein Verfahren an, welches angesetzt auf eine endliche L-Struktur A mit Grundmenge {1, …, n} (für ein n ∈ ℕ) in polynomialer Zeit entscheidet, ob A ⊧ φ. Zeigen Sie, daß Ihr Verfahren polynomielle Laufzeit in der Eingabe A (siehe Kodierung) hat. Zur Kodierung: Verwenden Sie das Alphabet A = {|, (,),; }. Für die Struktur A = (\{1, …, n\}, R^{A}) stehe im Register R_{1} das Wort \underbrace{| … |}_{n mal}. Im Register R_{2} stehe das Wort

w = w_{1}w_{2} … w_{k} mit w_{i} = (\underbrace{| … |}_{n_{i} mal}; \underbrace{| … |}_{m_{i} mal}), falls R^{A} = \{(n_{1}, m_{1}), (n_{2}, m_{2}), …, (n_{k}, m_{k})\}.

Zum Beispiel steht für A = ({1, 2, 3}, {(1, 1), (1, 3)}) in R_{2} das Wort (|; |)(|; |||).