Exercise � We consider (undirected) graphs as structures of the form G = ⟨V, E⟩ where E is the
binary edge relation. Express the following statements in first-order logic.
(a) All vertices are neighbours.
(b) The graph contains a triangle.
(c) Every vertex has exactly three neighbours.
(d) Every pair of vertices is connected by a path of length at most .
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 calculus
(that is, combine the basic rules to obtain the ones below).
Γ ⊢ ¬¬φ
Γ ⊢ φ
Γ ⊢ φ
Γ, ∆ ⊢ φ
Γ, ¬φ ⊢ ¬ψ
Γ ⊢ ψ → φ
�