Übungen zur Vorlesung Mathematische Logik

SS 2009, Blatt 8

Aufgabe 1.

(a). Ist die Regel \begin{matrix}Γ & (φ ∧ ψ) \\ Γ & φ \end{matrix} ableitbar?

(b). Ist die Sequenz ¬(¬φ ∧ ψ) ψ φ ableitbar?

(c). Ist die Regel \begin{matrix}Γ & φ \\ Γ & ¬φ \end{matrix} ableitbar?

Aufgabe 2. Für Φ ⊆ L^{S} sei ℑ^{Φ} die Henkin-Interpretation zu Φ. Ein Literal λ ist ein Ausdruck der Gestalt

(1) λ = φ oder (2) λ = ¬φ

für atomares φ. Ausdrücke der Gestalt (1) sind positive Literale, solche der Gestalt (2) negative. Ausdrücke der Gestalt ∀x_{1} … ∀x_{n}(λ_{1} ∨ … ∨ λ_{r}), wobei λ_{1}, …, λ_{r} Literale sind und höchstens eines davon positiv ist, sind universelle Hornausdrücke.

(a). Zeigen Sie, daß für jede widerspruchsfreie Menge Φ universeller Hornausdrücke ℑ^{Φ} ⊧ Φ gilt.

(b). Folgern Sie: Die Struktur 𝔗^{Φ_{Grp}} ist eine Gruppe.

Aufgabe 3. Sei S endlich oder S = S_{∞}. Zeigen Sie:

(a). Die Menge {Γ φ | Γ φ Sequenz und ⊢ Γ φ} ist aufzählbar.

(b). Falls Φ aufzählbar ist, so auch die Menge {ψ | Φ ⊢ ψ}.

Aufgabe 4. Für Φ ⊆ L^{S} sei wieder ℑ^{Φ} die Henkin-Interpretation zu Φ. Zeigen Sie: Gilt ℑ^{Φ} ⊧ Φ, so hat ℑ^{Φ} die folgende universelle Eigenschaft: Für jedes Modell ℑ = (𝔄, β) von Φ wird durch h : t̄ ↦ ℑ(t) für t ∈ T^{S} ein Homomorphismus h : 𝔗^{Φ} → 𝔄 definiert. (Insbesondere ist zu zeigen, daß h wohldefiniert ist.)

Aufgabe 5.

(a). R sei ein dreistelliges Relationssymbol und φ = ∀x∀y∃zRxyz. Weiter sei f ein zweistelliges Funktionssymbol. Zeigen Sie, daß es für alle {R}- Strukturen 𝔄 ∈ Mod(φ) eine Funktion g : A × A → A gibt, so daß für die {R, f}-Expansion 𝔄′ von 𝔄 mit f^{𝔄′} = g und für den {R, f}-Satz

φ′ = ∀x∀yRxyf(x, y)

gilt, daß 𝔄′ ⊧ φ′. Folgern Sie, daß φ und φ′ erfüllbarkeitsäquivalent sind (d.h. Erf φ genau dann, wenn Erf φ′). Sind φ und φ′ logisch äquivalent?

(b). Wir wollen mit dieser Idee alle Existenzquantoren eliminieren. Sei S eine Symbolmenge. Definieren Sie für eine geeignete Symbolmenge S′ mit S ⊆ S′ eine Abbildung ·^{+} : L^{S} → L^{S′}, φ ↦ φ^{+}, so daß für alle φ = φ(x_{1}, …, x_{n}) gilt:

(i) φ^{+} ist universell,

(ii) für alle S-Strukturen 𝔄 und alle (a_{1}, …, a_{n}) ∈ A^{n} mit 𝔄 ⊧ φ[a_{1}, …, a_{n}] gibt es eine S′-Expansion 𝔄^{+} von 𝔄, so daß 𝔄^{+} ⊧ φ^{+}[a_{1}, …, a_{n}],

(iii) φ^{+} ⊧ φ.

Folgern Sie: φ und φ^{+} sind erfüllbarkeitsäquivalent. Hinweis: Um ·^{+} zu definieren, gehe man bei gegebenem φ zunächst zu einem logisch äquivalenten Ausdruck in pränexer Normalform über.

Abgabe: Mittwoch, 24. Juni, vor der Vorlesung.

Die Übungsblätter und die Einteilung der Übungen findet man auch unter

http://home.mathematik.uni-freiburg.de/bjoern/lehre/logik09/logik09.html