DISCRETE MATH: Use rules of inference to show that

[VinnyCee]

Homework Statement

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

Homework Equations

Universal instantiation, Disjunctive syllogism, Conjunction.

The Attempt at a Solution

1) \forall\,x\,(P(x)\,\vee\,Q(x)) Premise

2) P(a)\,\vee\,Q(a) Universal instantiation of (1)

3) \neg\,P(a) Disjunctive syllogism of (2)

4) \forall\,x\,((\neg\,P(x)\,\wedge\,Q(x))\,\longrightarrow\,R(x)) Premise

5) (\neg\,P(a)\,\wedge\,Q(a))\,\longrightarrow\,R(a) Universal instantiation of (4)

6) R(a) Modus Ponens of (5)

Here I am stuck, any suggestions?

 

[TeethWhitener]

The exact derivation will depend on which inference rules are allowed, but there are several errors in the attempt above.

3) ¬P(a) Disjunctive syllogism of (2)

This is an incorrect use of disjunctive syllogism, which is properly:
$$A\vee B,\neg A\vdash B$$
The above step invalidly concluded $\neg A$ from $A\vee B$.

6) R(a) Modus Ponens of (5)

This is incorrect use of modus ponens, which is:
$$A\to B,A\vdash B$$
The above step incorrectly concluded $B$ from $A\to B$.

If youre working in predicate calculus and there’s nothing actually involving the quantifiers, it’s probably easiest to do instantiation on everything at the beginning and generalization on everything at the end. Then you can do the rest of the derivation in propositional calculus.

With this in mind, the premises become
$$P\vee Q$$
$$(\neg P\wedge Q)\to R$$
And the conclusion is
$$\neg R \to P$$
If I were to try to solve this, I would probably proceed as follows:

Taking the contrapositive of premise 2 gives:
$$\neg R \to \neg(\neg P\wedge Q)$$. Distributing the negation over the conjunction using DeMorgan’s law gives:
$$\neg R \to (P\vee \neg Q)$$
Up to this point, we’ve been mechanically manipulating premise 2 to get it as close to the conclusion as we can. There are a few ways to proceed from here, but the key is to see that we have two cases. if $P$ is true, then we’re done. If $P$ is false (equivalently, $\neg P$ is true), then $\neg Q$ has to be true. But $\neg P$ and $\neg Q$ together give $\neg (P\vee Q)$, which contradicts premise 1. So $P$ must be true.

Probably the most straightforward way to show this using rules of inference is to rewrite premise 1 as a conditional:
$$\neg Q \to P$$
And note that this means that if you substitute $P$ for $\neg Q$ in any valid expression, the expression remains valid. So
$$\neg R \to (P\vee \neg Q)$$
becomes
$$\neg R \to (P\vee P)$$
And $P\vee P$ can be replaced by $P$.