phi 210

Symbolic Logic Final

Provide derivations to show that the following arguments are valid (10 points each).

1. ⊢ (∀x)[ Fx → (∃y)[Fy]]

2. ⊢ (∀x)[((∃y)[x=y]→ Fx) → Fx]

3. ⊢ (∀x)[ Fx → (∀y)[y=x →Fx] ]

4. ⊢ (∀x)(∀y)[R(x,y) → ¬(x=y ∧ ¬R(y,x))]

5. (∀x)[ Fx → Gx ] ⊢ (∃x)[¬Gx]→(∃x)[¬Fx]

6. (∃x)[Fx ∨ Gx], (∀x)[ x=a → ¬Hx ], (∀x)[Hx ↔ Gx] ⊢ (∃x)[ Fx ∨ ¬x=a]

7. (∀x)¬[x<x] ⊢ ¬(∃x)(∀y)[y<x]

8. (∀x)(∀y)[ x<y → ¬y<x ] ⊢ (∀x)[¬x<x]

PICK TWO of the following arguments and provide derivations to show that they are valid (10

points each).

9. (∀x)(∀y)(∀z)[(x<y ∧ y<z) → x<z ], (∀x)[¬x<x] ⊢ (∀x)(∀y)[ x<y → ¬y<x ]

10. (∀x)[Nx → (∃y)[Ny ∧ x<y]], (∀x)(∀y)[x<y→¬y<x] ⊢ ¬(∃x)[Nx ∧ (∀y)[¬y=x → y<x]]

11. (∀x)(∀y)[(Fx ↔ Fy) → x=y] ⊢ (∃x)[Fx → ¬(∃y)[Fy ∧ ¬y=x]]

12. (∃x)(∃y)(∀z)¬[R(z,x) ↔ R(z,y)] ⊢ (∃x)(∃y)[¬x=y]

13. (∃x)(∃y)(∀z)¬[R(z,x) ↔ R(z,y)] ⊢ (∃x)(∀z)[¬R(z,x) → (∃y)[¬x=y ∧ R(z,y)]]

BONUS: Provide trees to evaluate the following arguments for soundness (5 points each).

1. (∀x)[¬Fx → Hx], (∃x)[ Hx ] ⊢ (∃x)[ Fx ]

2. (∀x)[Fx → R(x,a)], (∃x)[ Fx ∧ R(x,x)] ⊢ R(a,a)

3. (∀x)(∀y)(∀z)[(x<y ∧ y<z) → x<z ] ⊢ (∀x)(∀y)[ (x<y ∧ y<x) → y=x ]

4. (∀x)(∀y)[ (x<y ∧ y<x) → y=x ] ⊢(∀x)(∀y)[¬x=y → (x<y→¬y<x) ]

BONUS: Provide trees to determine whether the following formulae are tautologies (5 points each).

5. (∀x)[ (Fx → (∃y)[y=x]) ↔ Fx ]

6. (∀x)(∀y)[R(x,y)↔R(y,x)] → R(a,a)