Exercise � Show that the following formulae are valid using tableau proofs.
(a) ψ → ((φ∧ ψ) ∨ ψ)
(b) ((φ∧ ψ) ∨ ψ) → ψ
(c) φ → ∃xφ
(d) ∀xφ → φ
(e) ∀x(φ∧ ψ) → ∀xφ∧ ∀xψ
(f) ∃x(φ∨ ψ) → (∃xφ∨ ∃xψ)
(g) φ∧ ψ → ψ ∧ φ
(h) (¬ψ → ¬φ) → (φ → ψ)
(i) φ → ¬¬φ
(j) (φ → ψ) ∧ (φ → ϑ) → (φ → ψ ∧ ϑ)
(k) (φ → ψ ∧ ϑ) → (φ → ψ) ∧ (φ → ϑ)
(l) ¬¬φ → φ
(m) φ∨ ¬φ
(n) ¬(¬φ∧ ¬ψ) → (φ∨ ψ)
(o) ∀xR(x,x) → ∀x∃yR(f(x),y)
(p) (∃xφ∨ ∃xψ) → ∃x(φ∨ ψ)
(q) ∀xφ∧ ∀xψ → ∀x(φ∧ ψ)
(r) ∀x∀y[φ(x) ↔ φ(y)] ∧ ∃xφ(x) → ∀xφ(x)
Exercise � Prove that the formulae from Exercise � are valid using Natural Deduction.
Exercise � Find all consistent sets for the following sets of rules.
(a)
α
α β
δ
α γ
δ
(b)
α
α βγ
β
(c)
α
α β
γ
α γ
β
�
Exercise � For each of the following subsets Φ ⊆ ℘({α,β}), find a set of rules R such that Φ is the
set of all consistent sets for R.
(a) {∅, {α}, {α,β}}
(b) {{α}, {β}, {α,β}}
(c) {∅, {α,β}}
(d) {{α}, {α,β}}
Exercise � (optional) Derive the following additional rules from the basic ones of the Natural Deduction
calculus (that is, combine the basic rules to obtain the ones below).
Γ ⊢ ¬¬φ
Γ ⊢ φ
Γ ⊢ φ
Γ,Δ ⊢ φ
Γ,¬φ ⊢ ¬ψ
Γ ⊢ ψ → φ
�