Question

Use rules of inference to show that if ∀x(p (x) ∨ q(x)), ∀x(¬q(x) ∨ s(x)), ∀x(r(x) → ¬s(x)), and ∃x¬p (x) are true, then ∃x¬r(x) is true.

Answer 1

01 ∀x[P(x)→Q(x)] premise

02 ∀x[Q(x)→R(x)] premise

03 ∃x[¬R(x)] premise

04 ¬R(a) assumption

05 P(a) assumption

06 P(a)→Q(a) ∀elim 01 a/x

07 Q(a) MP 06 05

08 Q(a)→R(a) ∀elim 02 a/x

09 R(a) MP 08 07

10 ⊥ contradiction 09 04

11 ¬P(a) ¬intro 05-10

12 ∃x[¬P(x)] ∃intro 11 a/x

13 ∃x[¬P(x)] ∃elim 03 04-12