Übungen zur Vorlesung Logik (Grundkurs)

Abgabe am Mittwoch, dem 6. 5. 98, fünf Minuten vor der Vorlesung

2.1 Eine Bewertung b : F m(Ak) → {0.1} ist eine Abbildung mit folgenden Eigenschaften:

b(A ∧ B) = b(A) ∩ b(B)
b(A ∨ B) = b(A) ∪ b(B)
b(¬A) = \b(A)

Zeigen Sie durch Induktion über den Formelaufbau:

Sind b_{1}, b_{2} Bewertungen, so daß für alle Variablen p ∈ V gilt: b_{1}(p) = b_{2}(p), dann folgt b_{1} = b_{2}. (Eine Belegung bestimmt eine Bewertung eindeutig.)

2.2 Man zeige, daß

⊧ ⋁_{i≤n} A_{i} → ⋀_{i≤m} B_{j}

genau dann, wenn für alle i ≤ n, j ≤ m gilt: A_{i} → B_{j}.

2.3 Eine Substitution σ ist eine Abbildung, die jeder Variablen p ∈ V eine Formel σ(p) ∈ F m(Ak) zuordnet, wobei σ fast überall (d. h. bis auf endlich viele Ausnahmen) identisch ist.

Man zeige, daß die Menge Ag der logisch gültigen Formeln abgeschlossen ist gegenüber Substitutionen. Das heißt, es gilt:

F ∈ Ag ⇒ σ(F) ∈ Ag

2.4 Man beweise, daß zu jeder Formel A eine äquivalente Formel B exisitert, die nur die Funktoren → und ¬ enthält.