Exercise 1 Prove that the following formulae are valid using Natural Deduction.
(a) φ ∧ ψ → ψ ∧ φ
(b) ψ → ((φ ∧ ψ) ∨ ψ)
(c) (¬ψ → ¬φ) → (φ → ψ)
(d) φ → ¬¬φ
(e) ((φ ∧ ψ) ∨ ψ) → ψ
(f) ¬¬φ → φ
(g) φ ∨ ¬φ
(h) ¬(¬φ ∧ ¬ψ) → (φ ∨ ψ) (This one is tricky.)
(i) φ → ∃xφ
(j) ∀xφ → φ
(k) ∀xR(x, x) → ∀x∃yR(f (x), y)
(l) ∃x(φ ∨ ψ) → (∃xφ ∨ ∃xψ)
(m) (∃xφ ∨ ∃xψ) → ∃x(φ ∨ ψ)
(n) ∀xφ ∧ ∀xψ → ∀x(φ ∧ ψ)
(o) ∀x(φ ∧ ψ) → ∀xφ ∧ ∀xψ
(p) ∀x∀y[φ(x) ↔ φ(y)] ∧ ∃xφ(x) → ∀xφ(x)
Exercise 2 Prove that the formulae from Exercise  are valid using tableau proofs.
Exercise 3 Find all consistent sets for the following sets of rules.
(a)
α
α ∶ β
δ
α ∶ γ
δ
(b)
α
α ∶ β γ
β
(c)
α
α β
γ
α ∶ γ
β
Exercise 4 For each subset Φ ⊆ ℘({α, β}), try to find a set of rules R such that Φ is the set of all
consistent sets for R.

Exercise 5 Derive the following additional rules from the basic ones of the Natural Deduction
calculus.
Γ Ȃ ¬¬φ
Γ Ȃ φ
Γ Ȃ φ
Γ, ∆ Ȃ φ
Γ, ¬φ Ȃ ¬ψ
Γ Ȃ ψ → φ
Γ, ¬φ Ȃ ψ
Γ Ȃ φ ∨ ψ
Exercise 6 Find a rule for proofs by induction.
Ȃ Ȃ
∀xφ(x)
where φ(x) is a formula talking about natural numbers.
