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.
We use the notation f = ○, f = ¬, f = id, f = .
(a) We take for f the conjunction and for u the negation. The system L(∧, ¬) is complete since it
can express all connectives of the system L(→, ¬) (which we already know to be complete):
φ → ψ ≈ ¬(φ ∧ ¬ψ) .
It remains to prove that L(∧, ○, id, ) is not complete. To do so, we show that negation cannot be
expressed in it. Let v be a variable assignment with v(X) =  for all variables X. We show that every
formula φ of the system L(∧, ○, id, ) satisfies the following property.
P(φ) v(φ) =  or φ is a contradiction.
Since P(¬A) does not hold, it follows that no formula in L(∧, ○, id, ) is equivalent to ¬A.
We proceed by induction on φ.
If φ = X is a propositional variable, we have v(φ) = v(X) = .
If φ = id(ψ) and P(ψ) holds, then φ ≈ ψ. Hence, P(ψ) implies P(φ).
If φ = ψ, then φ is a tautology. Hence, v(φ) = .
If φ = ○ψ, then φ is a contradiction. Hence, P(φ).
Suppose that φ = ψ ∧ ξ and that P(ψ) and P(ξ) hold. If one of the formulae ψ and ξ is a contradiction,
so is φ. Otherwise, we have v(ψ) =  and v(ξ) = , which implies that v(φ) = .
Finally, let us remark that the only other solution to this exercise is to take f = ∨ and u = ¬.
(b) We already know that L(∧, ¬) is complete and L(∧, ○, id, ) is not. This implies that L(∧, ○),
L(∧, id), and L(∧, ) are neither. Consequently, the only candidate for a strongest connective is
negation ¬. Let us show that ¬ also does not work. We consider the ternary operation f for the
function F {, }
→ {, } given by the following truth table.
x y z F(x, y, z)
   
   
   
   
   
   
   
   
This operation has the two following properties.
(1) F( − x,  − y,  − z) =  − F(x, y, z)
(2) F(, x, y) = −xy,that is, f (○x, x, y) ≈ x y,where the operation is defined by x y = ¬(x∧y).
We start by showing that L(f , ○) is complete. We have already shown above that we can express
using f and ○. Furthermore, we have
¬φ ≈ φ φ and φ ∧ ψ ≈ ¬(φ ψ) .
Since L(∧, ¬) is complete, the claim follows.
It remains to show that L(f , ¬) is not complete. We prove that we cannot express disjunction.
Given a variable assignment v, let ¯v be the assignment where every variable is negated, i.e., ¯v(X) =
−v(X). We will show by induction on φ ∈ L(f , ¬) that v(φ) = ¯v(φ),for every variable assignment v.
Since v(A∨ B) = ¬ = ¯v(A∨ B), for the assignment with v(A) =  and v(B) = , it then follows that
no formula in L(f , ¬) is equivalent to A ∨ B.
If φ = X is a variable, then v(X) =  − ¯v(X) by definition of ¯v. If φ = ¬ψ with v(ψ) =  − ¯v(ψ), we
have
v(φ) =  − v(ψ) = ¯v(ψ) =  − ¯v(φ) .
Suppose that φ = f (ψ, ψ, ψ) with v(ψi) =  − ¯v(ψi). Then
v(φ) = v(f (ψ, ψ, ψ))
= f (v(ψ), v(ψ), v(ψ))
= f ( − ¯v(ψ),  − ¯v(ψ),  − ¯v(ψ))
=  − f (¯v(ψ), ¯v(ψ), ¯v(ψ)) [by (1)]
=  − ¯v(f (ψ, ψ, ψ))
=  − ¯v(φ) .
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
(a) This formula is derivable. For instance, as
. (↑↓A → ↑↓↓A) → (↑↑↓↓A → ↑↑↓A) (A) with φ =↑↓ A and ψ =↑↓↓ A
. ↑↓A → ↑↓↓A (A) with φ = A and ψ =↓↓ A
. ↑↑↓↓A → ↑↑↓A (MP) from 1. and 2.
. ↑↑↓↓ A (A) with φ = A
. ↑↑↓ A (MP) from 4. and 3.
(b) This formula is not derivable. We will show this using a semantic argument, that is, we will
define a semantics for the operations ↑ and ↓ such that the above axioms are true, but the formula
↑↓ A is not.
The connective → will be interpreted as usual as implication. Looking at (A) we see that ↑ behaves
like negation.
(φ → ψ) → (↑ψ → ↑φ) ≈ (φ → ψ) → (¬ψ → ¬φ) .
Thus interpreting ↑ by ¬, every instance of (A) becomes true.
The axiom (A) now becomes
↑↑↓↓φ ≈ ¬¬↓↓φ ,
which is a tautology if, and only if, ↓ is the connective mapping every value to .
With this interpretation (A) takes the form
↑↓φ → ↑ψ ≈ ¬ φ → ψ ,
which is a tautology, since ¬ φ is always false.
The fact that the rule MP preserves tautologies can be shown in the same way as in the lecture. As
in the lecture (using induction),it therefore follows that the above system is sound for this semantics.
But the formula ↑↓A ≈ ¬ A is not a tautology. Hence, it cannot be derived.
(c),(d) None of these formulae is derivable. We give a syntactic proof by showing that in our system
only formulae of the form
↑ξ , ψ → ↑ ξ , or φ → (ψ → ↑ ξ)
are derivable. We call such formulae nice. In particular, no formula of the form ↓φ or φ → ↓ψ is
derivable.
The proof of our claim proceeds by induction on the number of steps in the derivation. If φ is an
instance of one of the axioms (A), (A), or (A) it has the desired form.
Hence, suppose that we obtain φ by the rule (MP) applied to two nice formulae ψ and ψ → φ.
Since ψ → φ is nice, it must be of the form ψ → ↑ ξ or ψ → (ϑ → ↑ξ). Hence, φ = ↑ξ or φ = ϑ → ↑ξ.
Comment. The last proof would also work for a slightly looser definition of niceness where we define
a formula to be nice if it has the form
φ → (φ → (⋯ → (φn → ↑ξ)⋯)) , for some n ∈ N .
A precise definition of niceness would be by induction on the structure of a formula.
• If φ is of the form X or ↓ψ, it is not nice.
• If φ is of the form ↑ψ, it is nice.
• If φ is of the form ψ → ϑ it is nice if, and only if, ϑ is nice.
In the solution above we solved (b) semantically and (c), (d) syntactically. It also works the other
way round, but those solutions are more complex. For (c), we could interpret ↑ as the constant  and
↓ as any other unary connective. For (d), we also would have to reinterpret →, for instance, by setting
x → y = y. Finally, for (b) we could use a syntactic property. The simplest one seems to be that every
derivable formula is of the form
↑↑φ , ↑↓ψ → φ , (φ → ψ) → (↑φ → ↑ψ) , ↑φ → ↑↑ψ , or ↑(φ → ψ) → ↑ξ .