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

Abgabe: Mittwoch, 10. Dezember 2008, vor der Vorlesung

Schreiben Sie bitte den Namen Ihres Tutors auf Ihr Lösungsblatt! Allgemeiner Hinweis: Es besteht Anwesenheitspflicht bei den Übungen!

Aufgabe 1. Sei L = {P, R, f, g, c, d} eine Sprache. Dabei sollen P ein zweistelliges und R ein einstelliges Relationszeichen, f ein zweistelliges und g ein einstelliges Funktionszeichen und c und d Konstantenzeichen sein.

a) Welche der folgenden Zeichenfolgen sind L-Terme? Begründen Sie jeweils Ihre Antwort.

f(v_{2}, g(f(c, v_{2}))) f(g(f(c, d))) g(f(g(c), d))

b) Welche der folgenden Zeichenfolgen sind L-Formeln? Begründen Sie jeweils Ihre Antwort.

∀v_{1}∀v_{1}Rv_{1} ∀dP dd ∃v_{2}(P v_{2}v_{3} ∨ Rv_{3}) (∃v_{2}P v_{2}v_{3} ∨ Rv_{3})

Aufgabe 2. Sei L = {E} für ein zweistelliges Relationssymbol E und A die Menge aller Menschen. Weiterhin sei 𝔄 = (A, E^{𝔄}), wobei E^{𝔄}(a, b) für a, b ∈ A gelte, wenn a und b befreundet sind. Formalisieren Sie:

1. Jeder hat einen Freund.

2. Niemand ist mit jedem befreundet.

3. Je zwei Menschen haben verschiedene Freunde.

4. Je zwei Freunde haben einen gemeinsamen dritten Freund.

Aufgabe 3. Wie viele Automorphismen hat der folgende Graph?

\begin{aligned}a & & & b \\ & • & • \\ & • & • \\ c & & & d \end{aligned}

Aufgabe 4. Eine lineare Ordnung auf einer Menge M ist eine zweistellige Relation < mit folgenden Eigenschaften:

1. Für kein x ∈ M gilt x < x.

2. Sind x, y ∈ M, so gilt x < y oder x = y oder y < x.

3. Sind x, y, z ∈ M mit x < y und y < z, so gilt x < z. Zeigen Sie mit Hilfe des Kompaktheitssatzes der Aussagenlogik, daß sich jede Menge linear ordnen lässt: Zu jeder Menge M existiert eine lineare Ordnung auf M.