Question

Use rules of inference to show that if \(\forall x(P(x) \vee Q(x))\), \(\forall x(\neg Q(x) \vee S(x))\), \(\forall x(R(x) \to \neg S(x))\)and \(\exists x\neg P(x)\)are true, then \(\exists x\neg R(x)\)is true.

Short answer

If \(\forall x(P(x) \vee Q(x))\), \(\forall x(\neg Q(x) \vee S(x))\), \(\forall x(R(x) \to \neg S(x))\)and \(\exists x\neg P(x)\)are true, \(\exists x\neg R(x)\)holds.

Step-by-step solution

Rules of Inference

(a) Universal instantiation:It is a rule of inference which used to conclude that \(P(a)\) is true, where ais a particular member of the domain, with the given premise\(\forall xP(x)\).

(b) Universal generalization: It is a rule of inference that states that ∀xP(x) is true, given the premise that P(a) is true for all elements a in the domain.

(c) Disjunctive Syllogism: \(((P(a) \vee Q(a)) \wedge \neg P(a)) \to Q(a)\)

(d) Resolution: \(((P(a) \vee Q(a)) \wedge (\neg P(a) \vee R(a))) \to (Q(a) \vee R(a))\)

(e) Modus Ponens: \((P(a) \wedge (P(a) \to Q(a))) \to Q(a)\)

Proof

Given: Premises\(\forall x(P(x) \vee Q(x))\), \(\forall x(\neg Q(x) \vee S(x))\), \(\forall x(R(x) \to \neg S(x))\)and\(\exists x\neg P(x)\)

To prove:\(\exists x\neg R(x)\)

Proof:Following arguments are required for the proof-

Step Reason

1. \(\forall x(P(x) \vee Q(x))\) Premise
2. \((P(a) \vee Q(a))\) Universal Instantiation from(1)
3. \((Q(a) \vee P(a))\) Commutative Law on (2)
4. \(\forall x(\neg Q(x) \vee S(x))\) Premise
5. \((\neg Q(a) \vee S(a))\) Universal Instantiation from(4)
6. \(((Q(a) \vee P(a) \wedge (\neg Q(a) \vee S(a))) \to (P(a)vS(a))\) Resolution on (3) and (5)
7. \(\exists x\neg P(x)\) Premise
8. \(\neg P(a)\) Existential Instantiation from(7)
9. \(((P(a) \vee S(a)) \wedge \neg P(a)) \to S(a)\) Disjunctive Syllogism (6) & (8)
10. \(\forall x(R(x) \to \neg S(x))\) Premise
11. \(R(a) \to \neg S(a)\) Universal Instantiation from(10)
12. \(S(a) \to \neg R(a)\) Contrapositive of (11)
13. \((S(a) \wedge (S(a) \to R(a))) \to \neg R(a)\) Modus Ponens on (3) and (9)
14. \(\exists x\neg R(x)\) Existential Generalization of(13)

Therefore, there exists\(x\neg R(x)\).