Homework Sheet 2
Exercise � (� points)
(a) (� points) Intuition: We are looking for a binary operation f and a unary operation u that
together form a complete system, but such that f together with all other unary operations does not.
Exact question: For i ∈ {, , , }, let ui be the unary operation mapping  ↦ i mod  and  ↦
⌊i/⌋. Find a binary operation f and an index i ∈ {, , , } such that the system L(f , ui) is complete
but the system L(f , u(i+) mod , u(i+) mod , u(i+) mod ) is not. Prove your claim.
(b) (� points) Intuition: Is there a strongest unary operation?
Exact question: Is there an index i ∈ {, , , } such that, for every n ∈ N and every n-ary operation
f , if there is some j ∈ {, , , } such that L(f , uj) is complete, then L(f , ui) is also complete?
Prove your answer. You can use the statement from the lecture that the system L(¬, →) is complete,
but you cannot assume the completeness of other systems.
Exercise � (� points) We consider the logical system L(↑, ↓, →) where ↑ and ↓ are unary and → is
binary. We use the following proof system consisting of three axiom schemata and one rule.
(A) ↑↑↓↓φ
(A) ↑↓φ → ↑ψ
(A) (φ → ψ) → (↑ψ → ↑φ)
(MP) from φ and φ → ψ derive ψ
Determine (with proof) which of the following formulae are derivable in this system.
(a) ↑↑↓A
(b) ↑↓A
(c) ↓A
(d) ↓A → ↓A