Es ist wirklich nicht schwierig. Du musst lediglich sauber mit den Definitionen arbeiten.
Fixiere L eine passende Sprache für FOL für die gebrauchte Formeln.
Zu 13.2:
Sei φ ∈ FO(L). Sei M eine L-Struktur. Sei s eine Belegung der freien Variablen. Zu zeigen: eval(∀x φ; s) = eval(¬∃x ¬φ; s).
Fall 1. eval(∀x φ; s) = TRUE. Dann per Definition für alle a ∈ M gilt eval(φ; s[a/x]) = TRUE od. wie auch immer du Substitutionen schreibst. Darum eval(¬φ; s[a/x]) = FALSE für alle a ∈ M, sodass per Definition eval(∃x ¬φ; s) = FALSE. Daraus folgt eval(¬∃x ¬φ; s) = TRUE.
Fall 2. eval(∀x φ; s) = FALSE. Dann per Definition existiert ein a ∈ M mit eval(φ; s[a/x]) = FALSE. Also eval(¬φ; s[a/x]) = TRUE, sodass per Definition eval(∃x ¬φ; s) = TRUE. Daraus folgt eval(¬∃x ¬φ; s) = FALSE.
In allen Fällen gilt also eval(∀x φ; s) = eval(¬∃x ¬φ; s). Da dies für alle s und alle M gilt, gilt per Definition ∀x φ ≡ ¬∃x ¬φ.
Zu 13.3
Seien ψ, φ₁, φ₂ ∈ FO(L).
(⟹) Angenommen, ψ ⊨ {φ₁, φ₂} … ACHTUNG diese Schreibweise ist allgemein in der Logik gefährlich. Vom Kontext ist es klar, dass dies (ψ ⊨ φ₁ und ψ ⊨ φ₂) bedeutet. Seien M, s eine L-Struktur bzw. eine Interpretation. Zu zeigen: eval(ψ⟶(φ₁⋀φ₂); s) = TRUE.
Fall 1. eval(ψ; s) = TRUE. Dann, da ψ ⊨ φ₁ und ψ ⊨ φ₂, folgt aus der Annahme dieses Falls eval(φ₁; s) = TRUE und eval(φ₂; s) = TRUE. Also eval(φ₁⋀φ₂; s) = TRUE. Es folgt, dass eval(ψ⟶(φ₁⋀φ₂); s) = TRUE.
Fall 2. eval(ψ; s) = FALSE. Dann gilt eval(ψ⟶(φ₁⋀φ₂); s) = TRUE trivialerweise.
Also gilt in allen Fällen eval(ψ⟶(φ₁⋀φ₂); s) = TRUE. Da dies für alle M, s gilt, folgt ψ⟶(φ₁⋀φ₂) ∈ TAUT.
(⟸). Angenommen, ψ⟶(φ₁⋀φ₂) ∈ TAUT. Seien M, s eine L-Struktur bzw. eine Interpretation mit eval(ψ; s) = TRUE. Zu zeigen: eval(ψ; φ₁) = TRUE und eval(ψ; φ₂) = TRUE.
- Da ψ⟶(φ₁⋀φ₂) ∈ TAUT, gilt eval(ψ⟶(φ₁⋀φ₂); s) = TRUE.
- Da eval(ψ; s) = TRUE, folgt hieraus eval(φ₁⋀φ₂; s) = TRUE.
- Daraus folgt eval(φ₁; s) = TRUE und eval(φ₂; s) = TRUE.
Da eval(ψ; φ₁) = TRUE und eval(ψ; φ₂) = TRUE für alle M, s mit eval(ψ; s) = TRUE, erschließt sicht, dass ψ ⊨ {φ₁, φ₂}.