Question

Use rules of inference to show that if \(\forall x(P(x) \vee Q(x))\) and \(\forall x((\neg P(x) \wedge Q(x)) \to R(x))\) are true, then \(\forall x(\neg R(x) \to P(x))\) is also true, where the domains of all quantifiers are the same.

Short answer

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

Step-by-step solution

Rules of Inference and Laws

(a)Universal instantiation:It is a rule of inference which used to conclude that\(P(a)\)is true, whereais 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 thatP(a)is true for all elementsain the domain.

(c)De Morgan’s Law:\(\neg (p \wedge q) = \neg p \vee \neg q\)

(d)Logical Equivalence:\(p \vee q \equiv \neg p \to q\)

(e)Idempotent Law:\(p \vee p \to p\)

Proof

Given: Premises\(\forall x(P(x) \vee Q(x))\)and\(\forall x((\neg P(x) \wedge Q(x)) \to R(x))\).

To prove:\(\forall x(\neg R(x) \to P(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.\(\neg Q(a) \to P(a)\) Logical Equivalence of (3)

5.\(\forall x((\neg P(x) \wedge Q(x)) \to R(x))\) Premise

6.\(((\neg P(a) \wedge Q(a)) \to R(a)\) Universal Instantiation from (5)

7.\(\neg (\neg P(a) \wedge Q(a)) \vee R(a)\) Logical Equivalence of (6)

8.\((P(a) \vee \neg Q(a)) \vee R(a)\) De Morgan’s Law on (7)

9.\(P(a) \vee P(a) \vee R(a)\) Conclusion of (4)

10.\(P(a) \vee R(a)\) Idempotent Law on (9)

11.\(R(a) \vee P(a)\) Commutative Law on (10)

12.\(\neg R(a) \to P(a)\) Logical Equivalence of (11)

13.\(\forall x(\neg R(x) \to P(x))\) Universal Generalization of (12)

Hence\(\forall x(\neg R(x) \to P(x))\)is true.