Exercise  Show that the following formulae are valid using tableau proofs.
(a) φ ∧ ψ → ψ ∧ φ
(b) ψ → ((φ ∧ ψ) ∨ ψ)
(c) (¬ψ → ¬φ) → (φ → ψ)
(d) φ → ¬¬φ
(e) ((φ ∧ ψ) ∨ ψ) → ψ
(f) (φ → ψ) ∧ (φ → ϑ) → (φ → ψ ∧ ϑ)
(g) (φ → ψ ∧ ϑ) → (φ → ψ) ∧ (φ → ϑ)
(h) ¬¬φ → φ
(i) φ ∨ ¬φ
(j) ¬(¬φ ∧ ¬ψ) → (φ ∨ ψ)
(k) φ → ∃xφ
(l) ∀xφ → φ
(m) ∀xR(x, x) → ∀x∃yR(f (x), y)
(n) ∃x(φ ∨ ψ) → (∃xφ ∨ ∃xψ)
(o) (∃xφ ∨ ∃xψ) → ∃x(φ ∨ ψ)
(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  Derive the following additional rules from the basic ones of the Natural Deduction cal-
culus.
Γ ⊢ ¬¬φ
Γ ⊢ φ
Γ ⊢ φ
Γ, ∆ ⊢ φ
Γ, ¬φ ⊢ ¬ψ
Γ ⊢ ψ → φ
Γ, ¬φ ⊢ ψ
Γ ⊢ φ ∨ ψ
Exercise  Find a rule for proofs by induction.
⋯ ⋯
∀xφ(x)
where φ(x) is a formula talking about natural numbers.
