Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit

Assignment 11

1. Let L = {f, R, S, c} where f is a unary function symbol, R is a binary relation symbol, S is a ternary relation symbol, and c is a constant symbol. Let x, y, and z denote distinct variables. Put the following L-formulas into prenex normal form. You may use any claims made in the Week 11 Slides.

(a) ∀x(Rxy → Sczz)

(b) (∀xRxy → Sczz)

(c) (∀xRxy → Sczx)

(d) (Sxxy ∨ ¬(∃xfx ≈ y → Ryc))

(e) (∃x(Sycc ∧ ∀yfy ≈ c) → ¬(∀xSxcy ∨ z ≈ fx))

2. Show that if ϕ and ψ are L-formulas and x is a variable such that x 6∈ free(ψ), then (∃xϕ → ψ)  ∀x(ϕ → ψ). (This is a part of a proof on page 10 of the Week 11 Slides that was left as an exercise.)

3. Let ϕ be an L-formula. Suppose x and y are variables such that y 6∈ free(ϕ), and y is substitutable for x in ϕ. Show that ∃xϕ  ∃yϕx y . (That is, fill in the details to the proof sketched on the last line of page 11 of the Week 11 Slides.)

4. Complete the proof of the “Implies case” of the proof on Prenex normal form, by giving the argument for the case when 1 ≤ qn(ϕ1) ≤ n + 1. (This was left as an exercise on page 22 of the Week 11 Slides.)

5. Show that if ϕ and ψ are formulas, x is a variable such that x 6∈ free(ψ), and Q is a quantifier, that (ψ ∨ Qxϕ)  Qx(ψ ∨ ϕ). (This is one of the rules who’s proof was left as an exercise on page 25 of the Week 11 Slides.)