MATH 2090  Problem Set #4 (On Ch.12 and 14)

York University

Faculties of Pure and Applied Science, Arts, Atkinson MATH 2090. Problem Set #4. Posted November 8 , 2003

Due in the Course Box. November 25, 2003

Section A

In your proofs (all informal please) it is imperative to clearly state what tools you use (e.g., WLUS, sWLUS, MP, Leibniz, Monotonicity, Deduction Theorem, Generalization, Auxiliary Variable metatheorem, which axiom(s), etc.)

1. (5 Marks) Prove that Boolean (propositional calculus) formulas are uniquely readable. That is, prove that if a string S is a formula, then it is impossible for it to be equal (as a string!) to \underline{more than} one of

(a) false

(b) true

(c) p (some variable)

(d) (¬A)

(e) (¬A′)—where the formulas A and A′ are different strings

(f) (A ∨ B)

(g) (A′∨B′)—where the formulas A and A′ and B and B′ are different strings

Hint. The results that say (1) “Any non-empty proper prefix of a formula has an excess of left brackets” and (2) “Every formula has an equal number of left and right brackets” are what you will use. This exercise involves no induction.

2. (5 Marks) Define substitution into a Boolean variable by induction, where “=” in the definition below is informal equality of strings. A, B, D denote Boolean formulas.

MATH 2090  Problem Set #4 (On Ch.12 and 14)

(a) false[p := D] = false

(b) true[p := D] = true

(c) p[p := D] = D

(d) q[p := D] = q—where q is variable other than p.

(e) (¬A)[p := D] = (¬(A[p := D]))

(f) (A ∨ B)[p := D] = ((A[p := D]) ∨ (B[p := D])) We have always taken it for granted (!) that if A is a formula then so is A[p := D]. You are asked here to prove this fact, at long last, by GCVI with respect to the ≺ relation that means “subformula of”.

3. (5 Marks) Prove

ST ⊢ (∃x)(⟨x, y⟩ = z) ∧ (∃x)(⟨x, w⟩ = z) ⇒ y = w

Note. You do not need to refer to any “implementation” of ordered pair. You only need its “fundamental property”, ⟨a, b⟩ = ⟨a′, b′⟩ ⇒ a = a′ ∧ b = b′.

4. (5 Marks each) Text, p. 300, #14.8, # 14.11, #14.14, #14.22, #14.26.