MAT 3361, INTRODUCTION TO MATHEMATICAL LOGIC, Fall 2004

Answers to Problem Set 1: Handout 1, Problems 1-4, 10, 20, 30, 50 Peter Selinger

Problem 1 (a) ¬(A ∧ B) ⊢ ¬ A ∨ ¬ B

1  ¬(A ∧ B)
2  ¬(¬ A ∨ ¬ B)
3  A
4  B
5  A ∧ B  ∧I, 3, 4
6  ⊥  ¬E, 1, 5
7  ¬ B  ¬I, 4–6
8  ¬ A ∨ ¬ B  ∨I, 7
9  ⊥  ¬E, 2, 8
10  ¬ A  ¬I, 3–9
11  ¬ A ∨ ¬ B  ∨I, 10
12  ⊥  ¬E, 2, 11
13 ¬ ¬(¬ A ∨ ¬ B)  ¬I, 2–12
14 ¬ A ∨ ¬ B  ¬¬E, 13

(b) ¬ A ∧ ¬ B ⊢ ¬(A ∨ B)

1 ¬ A ∧ ¬ B
2  A ∨ B
3  A
4  ¬ A  ∧E, 1

5  ⊥  ¬E, 3, 4
6  B
7  ¬ B  ∧E, 1
8  ⊥  ¬E, 6, 7
9  ⊥  ∨E, 2, 3–5, 6–8
10 ¬(A ∨ B)  ¬I, 2–9

(c) ¬ A ∨ ¬ B ⊢ ¬(A ∧ B)

1  ¬ A ∨ ¬ B
2  A ∧ B
3  ¬ A
4  A  ∧E, 2
5  ⊥  ¬E, 3, 4
6  ¬ B
7  B  ∧E, 2
8  ⊥  ¬E, 6, 7
9  ⊥  ∨E, 1, 3–5, 6–8
10 ¬(A ∧ B)  ¬I, 2–9

Problem 2 (a) The definition of rank is:

r(p_{i}) = 0
r(⊥) = 0

r((φ □ ψ)) = 1 + max{r(φ), r(ψ)} r(( ¬ φ)) = 1 + r(φ).

The number of connectives of a formula can be defined as:

c(p_{i}) = 0
c(⊥) = 1
c((φ □ ψ)) = 1 + c(φ) + c(ψ)
c(( ¬ φ)) = 1 + c(φ).

(b) We prove that r(φ) ⩽ c(φ), for all φ. Base case: r(p_{i}) = 0 ⩽ 0 = c(p_{i}) and r(⊥) = 0 ⩽ 1 = c(⊥). Induction step: If r(φ) ⩽ c(φ) and r(ψ) ⩽ c(ψ), then

r((φ □ ψ)) = 1 + max{r(φ), r(ψ)}
⩽ 1 + r(φ) + r(ψ)
⩽ 1 + c(φ) + c(ψ)
= c((φ □ ψ)).

Here, we used the fact that the maximum of two non-negative numbers is ⩽ their sum. For the remaining induction step, assume r(φ) ⩽ c(φ). Then

r(( ¬ φ)) = 1 + r(φ)
⩽ 1 + c(φ)
= c(( ¬ φ)).

Problem 3 Let l(φ) denote the length of a proposition in symbols. Note that this is always a positive integer. We prove the following statement by induction: “for all propositions φ, l(φ) ∉ {2, 3, 6}”.

Base case: if φ is atomic, then l(φ) = 1 ∉ {2, 3, 6}.

Induction step 1: if φ = (φ′ □ φ′′), then l(φ) = 3 + l(φ′) + l(φ′′). Evidently this quantity is not 2 or 3. Also, if it were 6, then l(φ′) + l(φ′′) = 3, but this is not possible since then either l(φ′) = 2 or l(φ′′) = 2, contradicting the induction hypothesis.

Induction step 2: if φ = ( ¬ φ′), then l(φ) = 3 + l(φ′). Evidently this quantity is not 2 or 3; also it cannot be 6 since by induction hypothesis, l(φ′) ≠ 3.

Problem 4 (a) Base case: if φ = p_{i} is atomic, then φ = dm(φ), hence r(φ) = r(dm(φ)). Induction step: assume φ = (φ′ ∧ φ′′). By induction hypothesis, r(φ′) = r(dm(φ′)) and r(φ′′) = r(dm(φ′′)). But then

r(φ) = = 1 + max{r(φ′), r(φ′′)}
= 1 + max{r(dm(φ′)), r(dm(φ′′))}
= r((dm(φ′) ∨ dm(φ′′)))
= r(dm(φ)).

The case for φ = (φ′ ∨ φ′′) is similar. Finally, assume φ = ( ¬ φ′). By induction hypothesis, r(φ′) = r(dm(φ′)). But then

r(φ) = = 1 + r(φ′)
= 1 + r(dm(φ′))
= r(( ¬ dm(φ′)))
= r(dm(φ)).

(b) We have:

[[φ ∧ ψ]]′ = 1 − [[dm(φ ∧ ψ)]]
= 1 − [[dm(φ) ∨ dm(ψ)]]
= 1 − max{[[dm(φ)]], [[dm(ψ)]]}
= min{1 − [[dm(φ)]], 1 − [[dm(ψ)]]}
= min{[[φ]]′, [[ψ]]′}
[[φ ∨ ψ]]′ = 1 − [[dm(φ ∨ ψ)]]
= 1 − [[dm(φ) ∧ dm(ψ)]]
= 1 − min{[[dm(φ)]], [[dm(ψ)]]}
= max{1 − [[dm(φ)]], 1 − [[dm(ψ)]]}
= max{[[φ]]′, [[ψ]]′}
[[¬ φ]]′  = 1 − [[dm(¬ φ)]]
= 1 − [[¬ dm(φ)]]
= 1 − (1 − [[dm(φ)]])
= 1 − [[φ]]′

Thus, [[−]]′ is a valuation.

(c) In this proof, we use the fact that dm(dm(φ)) = φ, which is easily shown by induction.

Suppose φ is satisfiable. Then there is some valuation [[−]] such that [[φ]] = 1. Then [[−]]′ is a valuation, and we have [[dm(φ)]]′ = 1−[[dm(dm(φ))]] = 1−[[φ]] = 0, thus dm(φ) is not valid.

Conversely, suppose that dm(φ) is not valid, then there exists some valuation [[−]] such that [[dm(φ)]] = 0. Then [[−]]′ is a valuation, and we have [[φ]]′ = 1 − [[dm(φ)]] = 1, hence φ is satisfiable.

Problem 20 A ⇒ B ⊢ ¬(A ∧ ¬ B).

1 A ⇒ B
2  A ∧ ¬ B
3  A  ∧E, 2
4  A ⇒ B  R, 1
5  B  ⇒E, 3, 4
6  ¬ B  ∧E, 2
7  ⊥  ¬E, 5, 6
8 ¬(A ∧ ¬ B)  ¬I, 2–7

Problem 10 (a) A ∨ (B ∧ C) ⊢ (A ∨ B) ∧ (A ∨ C)

1  A ∨ (B ∧ C)
2  A
3  A ∨ B  ∨I, 2
4  A ∨ C  ∨I, 2
5  (A ∨ B) ∧ (A ∨ C)  ∧I, 3, 4
6  B ∧ C
7  B  ∧E, 6
8  C  ∧E, 6
9  A ∨ B  ∨I, 7
10  A ∨ C  ∨I, 8
11  (A ∨ B) ∧ (A ∨ C)  ∧I, 9, 10
12 (A ∨ B) ∧ (A ∨ C)  ∨E, 2, 3–5, 6–11

(b) (A ∨ B) ∧ (A ∨ C) ⊢ A ∨ (B ∧ C)

1  (A ∨ B) ∧ (A ∨ C)
2  A ∨ B  ∧E, 1
3  A ∨ C  ∧E, 1
4  A
5 A ∨ (B ∧ C) ∨I, 4
6  B
7  A
8 A ∨ (B ∧ C) ∨I, 4
9  C
10  B ∧ C  ∧I, 6, 9
11  A ∨ (B ∧ C)  ∨I, 10
12  A ∨ (B ∧ C)  ∨E, 3, 7–8, 9–11
13 A ∨ (B ∧ C)  ∨E, 2, 4–5, 6–12

Problem 30 See Problem 1. Problem 50 See Problem 1.