Reference no: EM132381070
Syntax and Semantics Problems -
Problem 1 - Prove Proposition - Any formula in Frm(L0) is balanced, in that it has as many left parentheses as right ones.
Problem 2 - Prove Proposition - No proper initial segment of a formula is a formula.
Problem 3 - Give a mathematically rigorous definition of φ[ψ/p] by induction.
Problem 4 - Prove Proposition - v |= φiff v-( φ) = T. Proof. By induction on φ.
Problem 5 - Prove Proposition -
1. φ is a tautology if and only if ∅ |= φ;
2. If Γ |= φ and Γ |= φ → ψ then Γ |= ψ;
3. If Γ is satisfiable then every finite subset of Γ is also satisfiable;
4. Monotony: if Γ ⊆ Δ and Γ |= φ then also Δ |= φ;
5. Transitivity: if Γ |= φ and Δ U {φ} |= ψ then Γ U Δ |= ψ;
Problem 6 - Prove Proposition - Γ |= φ if and only if Γ U {¬φ} is unsatisfiable;
Problem 7 - Prove Theorem - (Semantic Deduction Theorem). Γ |= φ → ψ if and only if Γ U {φ} |= ψ.