MATHEMATISCHES INSTITUT Bonn, den 16.05.2002 DER UNIVERSITÄT BONN Prof. Dr. Peter Koepke

Einführung in die Mathematische Logik SS 2002

Übungsaufgaben, Folge 5, Abgabe: Bis 31.05.2002, 12 Uhr in das Fach von Stefan Bold (Beringstr. 1)

Aufgabe 1 Formulieren Sie eine aussagenlogische Theorie, die

(a) genau ein Modell besitzt.

(b) genau zwei Modelle besitzt.

(c) genau drei Modelle besitzt.

(d) abzählbar unendlich, nicht aber überabzählbar unendlich, viele Modelle besitzt.

(e) überabzählbar unendlich viele Modelle besitzt.

Aufgabe 2 Es sei 𝔸 ein Alphabet mit +, · ∈ 𝔸. Ein Wort w ∈ 𝔸^{∗} heißt Term (der Arithmetik) in polnischer Notation, falls w in folgendem Kalkül abgeleitet werden kann:

\overline{a} für jedes a ∈ A \ \{+, · \}  \frac{w, w′}{+ww′}  \frac{w, w′}{· ww′}

(a) Begründen Sie, ob die folgenden Wörter über 𝔸 = {+, · , a, b, …} Terme in polnischer Notation sind: (α) · a · b (β) + · ab (γ) + · ab · ac

(b) Schreiben Sie folgende Terme der Arithmetik in polnischer Notation; geben Sie jeweils die Herleitung mit an! (α) a + (b + c) (β) (a + b) + c (γ) (a(((b + c)d) + e))(be)

Aufgabe 3 𝔸 sei ein endliches Alphabet, ⌢ die Konkatenation zweier Wörter. Betrachten Sie die Struktur (𝔸^{∗},⌢):

(a) Ist die Verknüpfung dieser Struktur assoziativ?

(b) Ist die Verknüpfung dieser Struktur kommutativ?

(c) Was ist das neutrale Element dieser Struktur?

(d) U, V, W seien Wörter aus 𝔸^{∗}. Beweisen Sie: Aus UW = V W folgt U = V.

Aufgabe 4 Es sei 𝔸 = {a, b}. Ein Wort w über 𝔸 heißt reduziert, wenn auf w keine der folgenden zwei Kürzungsregeln

\frac{w′aaw′′}{w′w′′}  und  \frac{w′bbw′′}{w′w′′}

angewendet werden kann. Ein Wort r ∈ 𝔸^{∗} heißt ein Redukt von w ∈ 𝔸^{∗}, falls r reduziert ist und r aus w durch (evtl. mehrmaliges) Anwenden der Kürzungsregeln gewonnen werden kann.

(a) Charakterisieren Sie die Menge der reduzierten Wörter über 𝔸.

(b) Zeigen Sie, daß jedes w ∈ 𝔸^{∗} genau ein Redukt r(w) hat.

(c) Charakterisieren Sie die Paare (w, w′) ∈ 𝔸^{∗} × 𝔸^{∗}, für die r(w^{⌢}w′) = r(w)^{⌢}r(w′) gilt.

(d) Zeigen Sie, daß durch w ∼ w′ :≡ r(w) = r(w′) eine Äquivalenzrelation auf 𝔸^{∗} definiert ist.

(e) Es sei \overline{w} die ∼ -Äquivalenzklasse von w ∈ 𝔸^{∗} und G sei die Menge der ∼ -Äquivalenzklassen. Zeigen Sie, daß G durch \overline{w} ∘ \overline{w′} :≡ \overline{ww′} zu einer Gruppe wird. Ist (G, ∘) kommutativ?

Homepage der Vorlesung:

http://www.math.uni-bonn.de/people/logic/Lectures/SoSe2002/Vorlesung.html
Newsgroup: uni-bonn.math.logik