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

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

Aufgabe 1. (Die Bearbeitung dieser Aufgabe ist verbindlich.) Sei L = {P, G, I} mit einstelligen Relationszeichen P, G und zweistelligem Relationszeichen I. Wir lesen P (x) als “x ist ein Punkt”, G(x) als “x ist eine Gerade” und I(x, y) als “x ist ein Punkt, y eine Gerade und x liegt auf y”.

a) Symbolisieren Sie:

• Zu je zwei Punkten gibt es genau eine Gerade, auf der beide liegen.

• Auf jeder Geraden liegen mindestens zwei Punkte.

• Je zwei Geraden schneiden sich in genau einem Punkt.

b) Welche der folgenden Zeichenfolgen sind L-Formeln? Begründen Sie Ihre Antwort. Formulieren Sie gegebenenfalls umgangssprachlich, was die jeweilige Formel ausdrückt.

• ∀x∀y∀z((I(x, y) ∧ G(z)) → (I(x, z) ∨ ¬y ≐ z))

• ∃x∀yI(x, y) → ¬∃z(f(z) ≐ x ∧ I(z, y))

Aufgabe 2. Sei L = {E} mit zweistelligem Relationszeichen E. G sei der folgende Graph:

\begin{aligned}a & & & & & & & b \\ & • & & & & & • \\ & & & c & d \\ & & • & & & • \\ & & & e & f \\ & & • & & & • \\ & • & & & & & • \\ g & & & & & & & h \end{aligned}

a) Gilt G ⊧ ∃x∃y∃z(Exy ∧ Eyz ∧ Ezx) ?

b) Gilt G ⊧ ∀x∀y(¬Exy → ∃z(Exz ∧ Ezy)) ?

c) Gilt G ⊧ ∀x∃y_{1}∃y_{2}∃y_{3}∃y_{4}(Exy_{1} ∧ Exy_{2} ∧ Exy_{3} ∧ Exy_{4}) ? Begründen Sie jeweils Ihre Antwort.

Aufgabe 3. Sei L = {P, f} für ein dreistelliges Relationszeichen P und ein zweistelliges Funktionszeichen f. Betrachten Sie die folgenden L-Formeln:

φ_{1} = ∃v_{3}(P (v_{1}, v_{2}, v_{3}) ∧ (∀v_{1}P (v_{1}, v_{2}, v_{3}) ∨ ∀v_{2}P (v_{4}, v_{2}, v_{3})))

φ_{2} = ∃v_{3}(P (v_{1}, v_{2}, v_{3}) ∧ (∀v_{2}P (v_{1}, v_{2}, v_{3}) ∨ ∀v_{1}P (v_{4}, v_{2}, v_{3})))

a) Welche der Variablen treten frei auf? Welche gebunden?

b) Ist v_{1} frei für f(v_{0}, v_{2}) in φ_{1}? In φ_{2}?

c) Bestimmen Sie φ_{1} \frac{f(v_{0},v_{2})}{v_{1}} und φ_{2} \frac{f(v_{0},v_{2})}{v_{1}} .

d) Welche Variablen treten nach der Substitution frei auf? Welche gebunden?

Aufgabe 4. L sei eine endliche Sprache. Zeigen Sie, daß es für jede endliche L-Struktur A eine L-Aussage φ gibt mit der Eigenschaft, daß für alle L-Strukturen B gilt:

B ⊧ φ gdw. A ≅ B.

Sie können der Einfachheit halber annehmen, daß L = {E} für ein zweistelliges Relationszeichen E.

Wir wünschen Ihnen Frohe Weihnachten und einen guten Start ins Neue Jahr!