MATH 0050: Logic
Sample Exercises 3
1) Write down a direct proof of the following syntactic implication (a proof that does not assume the
validity of any theorems and does not use the Deduction Theorem):
{(α⇒ β)⇒ ((¬¬γ)⇒ (¬β)) , β} ⊢ ¬γ
The following is a direct proof of ¬γ from {(α⇒ β)⇒ ((¬¬γ)⇒ (¬β)) , β}:
1. (α⇒ β)⇒ ((¬¬γ)⇒ (¬β)) Hypothesis
2. β Hypothesis
3. β ⇒ (α⇒ β) Axiom 1
4. α⇒ β Modus ponens on lines 2, 3
5. (¬¬γ)⇒ (¬β) Modus ponens on lines 1, 4
6. ((¬¬γ)⇒ (¬β))⇒ (((¬¬γ)⇒ β)⇒ (¬γ)) Axiom 3
7. ((¬¬γ)⇒ β)⇒ (¬γ) Modus ponens on lines 5, 6
8. β ⇒ ((¬¬γ)⇒ β) Axiom 1
9. (¬¬γ)⇒ β Modus ponens on lines 2, 8
10. ¬γ Modus ponens on lines 7, 9
1
2) Write down a direct proof of the following syntactic implication; you may assume the validity of
the theorem ϵ⇒ ϵ, for every proposition ϵ:
{(α⇒ β)⇒ ((α⇒ β)⇒ γ) , ((α⇒ β)⇒ γ)⇒ δ} ⊢ δ
The following is a direct proof of δ from {(α⇒ β)⇒ ((α⇒ β)⇒ γ) , ((α⇒ β)⇒ γ)⇒ δ}, in
which we assume the validity of ϵ⇒ ϵ:
1. (α⇒ β)⇒ ((α⇒ β)⇒ γ) Hypothesis
2. ((α⇒ β)⇒ γ)⇒ δ Hypothesis
3. ((α⇒ β)⇒ ((α⇒ β)⇒ γ))⇒ (((α⇒ β)⇒ (α⇒ β))⇒ ((α⇒ β)⇒ γ)) Axiom 2
4. ((α⇒ β)⇒ (α⇒ β))⇒ ((α⇒ β)⇒ γ) Modus ponens on lines 1, 3
5. (α⇒ β)⇒ (α⇒ β) ‘theorem’ / ‘assumed’
6. (α⇒ β)⇒ γ Modus ponens on lines 4, 5
7. δ Modus ponens on lines 2, 6
On line 5 of the above proof, we used ϵ⇒ ϵ, substituting α⇒ β for ϵ.
2
3) Write down proofs of the following theorems. Apart from the three axioms (or axiom schemes)
given in lectures, and modus ponens, you may use the Deduction Theorem for parts (b) to (h), and,
when trying to solve one part of the exercise, may assume the validity of theorems from earlier
parts.
a) α⇒ α
b) α⇒ ((¬β)⇒ α) i.e. α⇒ (β ∨ α)
c) α⇒ ((¬α)⇒ β) i.e. α⇒ (α ∨ β)
d) (¬¬α)⇒ α
e) α⇒ (¬¬α)
f) ((¬α)⇒ (¬β))⇒ (β ⇒ α)
g) (α⇒ β)⇒ ((¬β)⇒ (¬α))
h) (α⇒ β)⇒ (((¬α)⇒ β)⇒ β)
(We have already given proofs for most of these results in lectures. This sample exercise is partly
intended to give you an opportunity to revise those proofs, and also to indicate how the gradual
‘build up’ of theorems can enable one to arrive at a theorem such as the one given in part (h) above.)
a) The following is a proof of α⇒ α, which uses no hypotheses:
1. (α⇒ ((α⇒ α)⇒ α))⇒ ((α⇒ (α⇒ α))⇒ (α⇒ α)) Axiom 2
2. α⇒ ((α⇒ α)⇒ α) Axiom 1
3. (α⇒ (α⇒ α))⇒ (α⇒ α) Modus ponens on lines 1, 2
4. α⇒ (α⇒ α) Axiom 1
5. α⇒ α Modus ponens on lines 3, 4
b) The following is a proof of α⇒ ((¬β)⇒ α), which uses no hypotheses:
1. α⇒ ((¬β)⇒ α) Axiom 1
3
c) We wish to show that ⊢ (α⇒ ((¬α)⇒ β)).
By an application of the Deduction Theorem, it suffices to give a proof of {α} ⊢ ((¬α)⇒ β).
A further application of the Deduction Theorem indicates that it suffices to give a proof of
{α , ¬α} ⊢ β; we do so below:
1. α Hypothesis
2. ¬α Hypothesis
3. ((¬β)⇒ (¬α))⇒ (((¬β)⇒ α)⇒ β) Axiom 3
4. (¬α)⇒ ((¬β)⇒ (¬α)) Axiom 1
5. (¬β)⇒ (¬α) Modus ponens on lines 2, 4
6. ((¬β)⇒ α)⇒ β Modus ponens on lines 3, 5
7. α⇒ ((¬β)⇒ α) Axiom 1
8. (¬β)⇒ α Modus ponens on lines 1, 7
9. β Modus ponens on lines 6, 8
d) By the Deduction Theorem, it suffices to give a proof of {¬¬α} ⊢ α; we do so below:
1. ¬¬α Hypothesis
2. ((¬α)⇒ (¬¬α))⇒ (((¬α)⇒ (¬α))⇒ α) Axiom 3
3. (¬¬α)⇒ ((¬α)⇒ (¬¬α)) Axiom 1
4. (¬α)⇒ (¬¬α) Modus ponens on lines 1, 3
5. ((¬α)⇒ (¬α))⇒ α Modus ponens on lines 2, 4
6. (¬α)⇒ (¬α) ‘theorem’ / ‘assumed’
7. α Modus ponens on lines 5, 6
On line 6 of the above proof, we assumed the theorem given in part (a) of this exercise.
e) By the Deduction Theorem, it suffices to give a proof of {α} ⊢ (¬¬α); we do so below:
1. α Hypothesis
2. ((¬¬¬α)⇒ (¬α))⇒ (((¬¬¬α)⇒ α)⇒ (¬¬α)) Axiom 3
3. (¬¬¬α)⇒ (¬α) ‘theorem’ / ‘assumed’
4. ((¬¬¬α)⇒ α)⇒ (¬¬α) Modus ponens on lines 2, 3
5. α⇒ ((¬¬¬α)⇒ α) Axiom 1
6. (¬¬¬α)⇒ α Modus ponens on lines 1, 5
7. ¬¬α Modus ponens on lines 4, 6
On line 3 of the above proof, we assumed the theorem given in part (d) of this exercise.
4
f) By an application of the Deduction Theorem, it suffices to prove the syntactic implication
{(¬α)⇒ (¬β)} ⊢ (β ⇒ α).
A further application of the Deduction Theorem indicates that it suffices to give a proof of
{(¬α)⇒ (¬β) , β} ⊢ α; we do so below:
1. β Hypothesis
2. (¬α)⇒ (¬β) Hypothesis
3. ((¬α)⇒ (¬β))⇒ (((¬α)⇒ β)⇒ α) Axiom 3
4. ((¬α)⇒ β)⇒ α Modus ponens on lines 2, 3
5. β ⇒ ((¬α)⇒ β) Axiom 1
6. (¬α)⇒ β Modus ponens on lines 1, 5
7. α Modus ponens on lines 4, 6
g) By an application of the Deduction Theorem, it suffices to prove the syntactic implication
{α⇒ β} ⊢ ((¬β)⇒ (¬α)).
A further application of the Deduction Theorem indicates that it suffices to give a proof of
{α⇒ β , ¬β} ⊢ (¬α); we do so below:
1. ¬β Hypothesis
2. α⇒ β Hypothesis
3. ((¬¬α)⇒ (¬β))⇒ (((¬¬α)⇒ β)⇒ (¬α)) Axiom 3
4. (¬β)⇒ ((¬¬α)⇒ (¬β)) Axiom 1
5. (¬¬α)⇒ (¬β) Modus ponens on lines 1, 4
6. ((¬¬α)⇒ β)⇒ (¬α) Modus ponens on lines 3, 5
7. ((¬¬α)⇒ (α⇒ β))⇒ (((¬¬α)⇒ α)⇒ ((¬¬α)⇒ β)) Axiom 2
8. (α⇒ β)⇒ ((¬¬α)⇒ (α⇒ β)) Axiom 1
9. (¬¬α)⇒ (α⇒ β) Modus ponens on lines 2, 8
10. ((¬¬α)⇒ α)⇒ ((¬¬α)⇒ β) Modus ponens on lines 7, 9
11. (¬¬α)⇒ α ‘theorem’ / ‘assumed’
12. (¬¬α)⇒ β Modus ponens on lines 10, 11
13. ¬α Modus ponens on lines 6, 12
On line 11 of the above proof, we assumed the theorem given in part (d) of this exercise.
(Please note that lines 7 to 10 of the above proof are essentially “copied” from the argument
included in the proof of the general syntactic implication of α ⇒ γ from {α ⇒ β, β ⇒ γ},
which was mentioned in our lectures. Had we allowed ourselves to use this result from our
lecture notes, we would have been able to “arrive” at line 12 of the proof given here directly
from lines 2 and 11.)
5
h) By an application of the Deduction Theorem, it suffices to prove the syntactic implication
{α⇒ β} ⊢ (((¬α)⇒ β)⇒ β).
A further application of the Deduction Theorem indicates that it suffices to give a proof of
{α⇒ β , (¬α)⇒ β} ⊢ β; we do so below:
1. α⇒ β Hypothesis
2. (¬α)⇒ β Hypothesis
3. ((¬β)⇒ (¬¬α))⇒ (((¬β)⇒ (¬α))⇒ β) Axiom 3
4. ((¬α)⇒ β)⇒ ((¬β)⇒ (¬¬α)) ‘theorem’ / ‘assumed’
5. (¬β)⇒ (¬¬α) Modus ponens on lines 2, 4
6. ((¬β)⇒ (¬α))⇒ β Modus ponens on lines 3, 5
7. (α⇒ β)⇒ ((¬β)⇒ (¬α)) ‘theorem’ / ‘assumed’
8. (¬β)⇒ (¬α) Modus ponens on lines 1, 7
9. β Modus ponens on lines 6, 8
On lines 4 and 7 of the above proof, we assumed the theorem given in part (g) of this exercise.
6
4) Give two proofs of the following, one using the Deduction Theorem and one a direct proof not using
the Deduction Theorem (in either case, you may not assume the validity of any theorems):
{(α⇒ β)⇒ γ} ⊢ (α⇒ β)⇒ (β ⇒ γ)
We wish to show that {(α⇒ β)⇒ γ} ⊢ (α⇒ β)⇒ (β ⇒ γ).
Using the Deduction Theorem, it suffices to give a proof of
{(α⇒ β)⇒ γ , α⇒ β} ⊢ β ⇒ γ
and we do so below:
1. (α⇒ β)⇒ γ Hypothesis
2. α⇒ β Hypothesis
3. γ Modus ponens on lines 1, 2
4. γ ⇒ (β ⇒ γ) Axiom 1
5. β ⇒ γ Modus ponens on lines 3, 4
Alternatively, by an application of the Deduction Theorem, it suffices to give a proof of
{(α⇒ β)⇒ γ , α⇒ β} ⊢ β ⇒ γ
A further application of the Deduction Theorem indicates that it suffices to give a proof of
{(α⇒ β)⇒ γ , α⇒ β , β} ⊢ γ
and we do so below:
1. (α⇒ β)⇒ γ Hypothesis
2. α⇒ β Hypothesis
3. β Hypothesis
4. γ Modus ponens on lines 1, 2
7
The following is a direct proof of {(α⇒ β) ⇒ γ} ⊢ (α⇒ β) ⇒ (β ⇒ γ), which does not use
the Deduction Theorem:
1. (α⇒ β)⇒ γ Hypothesis
2. ((α⇒ β)⇒ (γ ⇒ (β ⇒ γ)))⇒ (((α⇒ β)⇒ γ)⇒ ((α⇒ β)⇒ (β ⇒ γ))) Axiom 2
3. γ ⇒ (β ⇒ γ) Axiom 1
4. (γ ⇒ (β ⇒ γ))⇒ ((α⇒ β)⇒ (γ ⇒ (β ⇒ γ))) Axiom 1
5. (α⇒ β)⇒ (γ ⇒ (β ⇒ γ)) Modus ponens on lines 3, 4
6. ((α⇒ β)⇒ γ)⇒ ((α⇒ β)⇒ (β ⇒ γ)) Modus ponens on lines 2, 5
7. (α⇒ β)⇒ (β ⇒ γ) Modus ponens on lines 1, 6
Alternatively, the following is a direct proof of {(α⇒ β) ⇒ γ} ⊢ (α⇒ β) ⇒ (β ⇒ γ), which
does not use the Deduction Theorem:
1. (α⇒ β)⇒ γ Hypothesis
2. (β ⇒ ((α⇒ β)⇒ γ))⇒ ((β ⇒ (α⇒ β))⇒ (β ⇒ γ)) Axiom 2
3. ((α⇒ β)⇒ γ)⇒ (β ⇒ ((α⇒ β)⇒ γ)) Axiom 1
4. β ⇒ ((α⇒ β)⇒ γ) Modus ponens on lines 1, 3
5. (β ⇒ (α⇒ β))⇒ (β ⇒ γ) Modus ponens on lines 2, 4
6. β ⇒ (α⇒ β) Axiom 1
7. β ⇒ γ Modus ponens on lines 5, 6
8. (β ⇒ γ)⇒ ((α⇒ β)⇒ (β ⇒ γ)) Axiom 1
9. (α⇒ β)⇒ (β ⇒ γ) Modus ponens on lines 7, 8
8
5) Use the Deduction Theorem to show that the following syntactic implication holds:
{α⇒ ((β ⇒ γ)⇒ (γ ⇒ δ))} ⊢ γ ⇒ (α⇒ δ)
We wish to show that {α⇒ ((β ⇒ γ)⇒ (γ ⇒ δ))} ⊢ γ ⇒ (α⇒ δ).
By an application of the Deduction Theorem, it suffices to give a proof of
{α⇒ ((β ⇒ γ)⇒ (γ ⇒ δ)) , γ} ⊢ α⇒ δ
A further application of the Deduction Theorem indicates that it suffices to give a proof of
{α⇒ ((β ⇒ γ)⇒ (γ ⇒ δ)) , γ , α} ⊢ δ
and we do so below:
1. α⇒ ((β ⇒ γ)⇒ (γ ⇒ δ)) Hypothesis
2. γ Hypothesis
3. α Hypothesis
4. (β ⇒ γ)⇒ (γ ⇒ δ) Modus ponens on lines 1, 3
5. γ ⇒ (β ⇒ γ) Axiom 1
6. β ⇒ γ Modus ponens on lines 2, 5
7. γ ⇒ δ Modus ponens on lines 4, 6
8. δ Modus ponens on lines 2, 7
9
6) Give two proofs of the following; one using the Deduction Theorem and one a direct proof not using
the Deduction Theorem (in either case, you may not assume the validity of any theorems):
{α⇒ (β ⇒ γ), β} ⊢ (α⇒ γ)
We wish to show that {α⇒ (β ⇒ γ), β} ⊢ (α⇒ γ).
Using the Deduction Theorem, it suffices to give a proof of {α ⇒ (β ⇒ γ) , β , α} ⊢ γ; we do so
below:
1. α Hypothesis
2. β Hypothesis
3. α⇒ (β ⇒ γ) Hypothesis
4. β ⇒ γ Modus ponens on lines 1, 3
5. γ Modus ponens on lines 2, 4
The following is a direct proof of {α⇒ (β ⇒ γ), β} ⊢ (α⇒ γ), which does not use the Deduction
Theorem:
1. β Hypothesis
2. α⇒ (β ⇒ γ) Hypothesis
3. (α⇒ (β ⇒ γ))⇒ ((α⇒ β)⇒ (α⇒ γ)) Axiom 2
4. (α⇒ β)⇒ (α⇒ γ) Modus ponens on lines 2, 3
5. β ⇒ (α⇒ β) Axiom 1
6. α⇒ β Modus ponens on lines 1, 5
7. α⇒ γ Modus ponens on lines 4, 6
10