MAT 3361, INTRODUCTION TO MATHEMATICAL LOGIC, Fall 2004

Answers to the Midterm

Problem 1. Prove the following in natural deduction, using your choice of Fitch or Prawitz style:

(a) (A → B) → C ⊢ A ∨ C.

Answer:

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

(b) A ∨ B ⊢ (¬ B) → (C → A).

Answer:

1  A ∨ B
2  ¬ B
3  C
4  A
5 A R, 4
6  B
7  ⊥  ¬E, 2, 6
8  A  ⊥E, 7
9  A  ∨E, 1, 4–5, 6–8
10  C → A  ⇒I, 3–9
11 ¬ B → (C → A)  ⇒I, 2–10

Problem 2. Prove the following proposition using analytic tableaux:

(a) (A ∨ B) → C ⊢ (A → C) ∧ (B → C).

Answer:

\begin{matrix}T (A ∨ B → C) \\ F ((A → C) ∧ (B → C)) \end{matrix}

[figure]
[figure: \begin{matrix}F (A ∨ B) \\ F A \\ F B \end{matrix}; \begin{matrix}F (A → C) \\ T A \\ × \end{matrix} \begin{matrix}F (B → C) \\ T B \\ × \end{matrix}; T C; \begin{matrix}F (A → C) \\ F C \\ × \end{matrix} \begin{matrix}F (B → C) \\ F C \\ × \end{matrix}]

(b) B ∧ C → A, (¬ A) → C ⊢ (C → B) → A. Answer:

T (B ∧ C → A)
T (¬ A → C)
F ((C → B) → A)
T (C → B)
F A
[figure]
[figure: F (B ∧ C); F B; F C; \begin{matrix}F (¬ A) \\ T A \\ × \end{matrix} \begin{matrix}T C \\ × \end{matrix}; \begin{matrix}T B \\ × \end{matrix}; F C; \begin{matrix}F (¬ A) \\ T A \\ × \end{matrix} \begin{matrix}T C \\ × \end{matrix}]  \begin{matrix}T A \\ × \end{matrix}

Problem 3. Let us write v(φ) for the number of occurrences of propositional variables in a proposition φ. Let us write c(φ) for the number of occurrences of connectives in φ.

Examples:

v(((p_{2} ∧ p_{5}) → (⊥ ∧ p_{2}))) = 3, because there are 3 variable occurrences p_{2}, p_{5}, p_{2}.

c(((p_{2} ∧ p_{5}) → (⊥ ∧ p_{2}))) = 4, because there are 4 occurrences of connectives ∧, →, ⊥, ∧.

(a) Give recursive definitions of v(φ) and c(φ).

Answer:

\begin{aligned}v(p_{i}) & = & 1 \\ v(⊥) & = & 0 \\ v((φ □ ψ)) & = & v(φ) + v(ψ) \\ v((¬ φ)) & = & v(φ) \\ c(p_{i}) & = & 0 \\ c(⊥) & = & 1 \\ c((φ □ ψ)) & = & c(φ) + c(ψ) + 1 \\ c((¬ φ)) & = & c(φ) + 1 \end{aligned}

(b) Prove: for all φ, v(φ) ⩽ c(φ) + 1. Answer: Base case: v(p_{i}) = 1 ⩽ 0 + 1 = c(p_{i}) + 1, and v(⊥) = 0 ⩽ 1 + 1 = c(⊥) + 1. Induction step: let φ = (ψ □ θ). By induction hypothesis, v(ψ) ⩽ c(ψ) + 1 and v(θ) ⩽ c(θ) + 1. We want to show v(φ) ⩽ c(φ) + 1. But:

v(φ) = v(ψ □ θ)
= v(ψ) + v(θ)
⩽ c(ψ) + 1 + c(θ) + 1 by ind.hyp.
= c(ψ □ θ) + 1
= c(φ) + 1

Second induction step: let φ = (¬ ψ). By induction hypothesis, v(ψ) ⩽ c(ψ) + 1. We want to show v(φ) ⩽ c(φ) + 1. But:

v(φ) = v(¬ ψ)
= v(ψ)
⩽ c(ψ) + 1 by ind.hyp.
= c(¬ ψ)
= c(φ)
⩽ c(φ) + 1

Problem 4. Suppose ⊢ A → B and ⊬ B. Prove: the set {¬ A, ¬ B} is consistent.

Answer: There are many possible proofs. Here are two examples. Note that proof 1 uses soundness and completeness, whereas proof 2 does not.

Proof 1: Using soundness, we have ⊧ A → B and |̸= B. Because |̸= B, it follows that there exists some valuation [[−]]_{0} such that [[B]]_{0} = 0. But by ⊧ A → B, it follows that for all valuations, [[−]], [[B]] = 0 implies [[A]] = 0. So in particular, [[A]]_{0} = 0. So then, [[¬ B]]_{0} = 1 and [[¬ A]]_{0} = 1, so we have found a valuation which satisfies {¬ A, ¬ B}. It follows, by completeness, that {¬ A, ¬ B} is consistent. □

Proof 2: Suppose ⊢ A → B and ⊬ B. Also, suppose, for the sake of contradication, that {¬ A, ¬ B} is not consistent. By definition, this means that ¬ A, ¬ B ⊢ ⊥. We then have the following natural deduction proofs:

⋮ ; A → B  \begin{aligned}¬ A ; ⋮ & & ¬ B ; ⋮ \\ & ⊥ \end{aligned}

We can therefore construct the following natural deduction proof:

[¬ B]_{2}  \begin{aligned}⋮ ; A → B & & \begin{aligned}[¬ A]_{1} ; ⋮ & & [¬ B]_{2} ; ⋮ \\ & ⊥ \end{aligned} ; (RAA_{1}) ; A \\ & & (→E) \\ & B \end{aligned} (¬E) ⊥ (RAA_{2}) B

We therefore have ⊢ B, contradicting our assumption. □

Problem 5. Let Γ be a set of propositions such that for all propositional variables p_{n}, either Γ ⊧ p_{n} or Γ ⊧ ¬ p_{n}. Prove by induction: for all propositions φ, either Γ ⊧ φ or Γ ⊧ ¬ φ.

Note: To keep the problem short, do \underline{only} the cases \{atoms, ¬, ∧\}. Make sure you state the induction hypothesis clearly in each case.

Answer: Base case: if φ = p_{n}, then the claim is true by assumption.

Induction step (¬): suppose φ = ¬ ψ, and suppose that Γ ⊧ ψ or Γ ⊧ ¬ ψ (induction hypothesis). We want to show Γ ⊧ φ or Γ ⊧ ¬ φ. Case 1: if Γ ⊧ ψ, then Γ ⊧ ¬ ¬ ψ (because for any valuation, [[¬ ¬ ψ]] = [[ψ]]. Therefore Γ ⊧ ¬ φ. Case 2: if Γ ⊧ ¬ ψ, then Γ ⊧ φ, because φ = ¬ ψ.

Induction step (∧): suppose φ = ψ ∧ ρ, and suppose that (Γ ⊧ ψ or Γ ⊧ ¬ ψ) and (Γ ⊧ ρ or Γ ⊧ ¬ ρ) (induction hypothesis). We want to show Γ ⊧ φ or Γ ⊧ ¬ φ. Case 1: if Γ ⊧ ψ and Γ ⊧ ρ, then Γ ⊧ ψ ∧ ρ, hence Γ ⊧ φ. Case 2: if Γ ⊧ ¬ ψ, then Γ ⊧ ¬(ψ ∧ ρ), because ¬ ψ logically implies ¬(ψ ∧ ρ). Therefore, Γ ⊧ ¬ φ. Case 3: if Γ ⊧ ¬ ρ, then Γ ⊧ ¬(ψ ∧ ρ), because ¬ ρ logically implies ¬(ψ ∧ ρ). Therefore, Γ ⊧ ¬ φ. Since at least one of the three cases must hold, we are done. □

Problem 6. In this problem, we consider a version of Hintikka sets for unsigned propositions. For simplicity, we consider a propositional logic using only the connectives {¬, ∧}. Thus, we do not consider the connectives {∨, →, ↔, ⊥}

Let S be a set of unsigned propositions. S is called a Hintikka set if it satisfies:

1. for no propositional symbol p, both p ∈ S and (¬ p) ∈ S,

2. if (φ ∧ ψ) ∈ S, then φ ∈ S and ψ ∈ S,

3. if (¬(φ ∧ ψ)) ∈ S, then (¬ φ) ∈ S or (¬ ψ) ∈ S, 4. if (¬(¬ φ)) ∈ S, then φ ∈ S.

(a) Prove: Every Hintikka set is satisfiable.

Hint: first, define a suitable valuation [[−]]. Then, prove the following statement by induction: for all propositions φ, (φ ∈ S ⇒ [[φ]] = 1) and ((¬ φ) ∈ S ⇒ [[φ]] = 0).

Answer: Let S be a Hintikka set. Define a valuation [[−]] by:

[[p_{i}]] = \{ \begin{matrix}1 & if p_{i} ∈ S, \\ 0 & if p_{i} ∉ S, \end{matrix}

and extend [[−]] to composite formulas in the unique way:

\begin{aligned}[[¬ ψ]] & = & 1 − [[ψ]], \\ [[ψ ∧ ρ]] & = & min\{[[ψ]]_{,}[[ρ]]_{\}}. \end{aligned}

We claim that for all propositions φ, φ ∈ S ⇒ [[φ]] = 1 and (¬ φ) ∈ S ⇒ [[φ]] = 0. We prove this by induction on φ.

Base case: if φ = p_{i} is atomic, then p_{i} ∈ S ⇒ [[p_{i}]] = 1 by definition. Also, assume ¬ p_{i} ∈ S, then p_{i} ∉ S by clause (1) in the definition of a Hintikka set, so [[p_{i}]] = 0 by definition.

Induction step (∧): Assume φ = ψ∧ρ, and assume the induction hypothesis holds for ψ and ρ. If φ ∈ S, then by clause (2) in the definition of a Hintikka set, ψ ∈ S and ρ ∈ S. By I.H., [[ψ]] = 1 and [[ρ]] = 1, hence [[φ]] = [[ψ ∧ ρ]]_{=}1. If ¬ φ ∈ S, then by clause (3) in the definition of a Hintikka set, ¬ ψ ∈ S or ¬ ρ ∈ S. Without loss of generality, assume ¬ ψ ∈ S. Then by I.H., [[ψ]] = 0, hence [[φ]] = [[ψ ∧ ρ]] = 0.

Induction step (¬): Assume φ = ¬ ψ, and assume the induction hypothesis holds for ψ. If φ ∈ S, then ¬ ψ ∈ S, hence [[ψ]]_{=}0 by I.H., hence [[φ]]_{=}1. If ¬ φ ∈ S, then ¬ ¬ ψ ∈ S, and by clause (4) in the definition of a Hintikka set, ψ ∈ S, hence by I.H., [[ψ]] = 1, hence [[¬ φ]] = 1.

It follows that [[−]] satisfies all φ ∈ S, so S is satisfiable. □

(b) [Extra credit] Prove: Every maximally consistent set is a Hintikka set.

Answer: Let S be a maximally consistent set of formulas. From a theorem in class, we know that every maximally consistent set satisfies φ ∈ S ⟺ ¬ φ ∉ S, for all φ. We prove that S is a Hintikka set:

(1) Since S is consistent, we cannot have p ∈ S and ¬ p ∈ S, or else S ⊢ ⊥.

(2) Assume φ ∧ ψ ∈ S. Suppose φ ∉ S. Then ¬ φ ∈ S by maximality. But φ ∧ ψ, ¬ φ ⊢ ⊥, so S is inconsistent, a contradiction. Therefore φ ∈ S.

(3) Assume ¬(φ ∧ ψ) ∈ S. Suppose ¬ φ ∉ S and ¬ ψ ∉ S. By maximal consistency, φ ∈ S and ψ ∈ S. But ¬(φ ∧ ψ), φ, ψ ⊢ ⊥, so S is inconsistent, a contradiction. Therefore ¬ φ ∈ S or ¬ ψ ∈ S.

(4) Assume ¬ ¬ φ ∈ S. By maximal consistency, ¬ φ ∉ S, and therefore φ ∈ S. We have shown that S satisfies all 4 conditions of a Hintikka set.