Quantified statements and rules of inference

Question

I'm having problems proving the following. I have two hypothesis: $\forall x(P(x) \vee Q(x))$ and $\forall x((\neg P(x) \wedge Q(x)) \rightarrow R(x))$ and the conclusion is $\forall x(\neg R(x) \rightarrow P(x))$ where the domain is all the same. how would I do this using the rules of inference for quantified statements. What I did first was used was universal instantiation for both hypothesis but after that I am not sure what to do. After applying the universal instantiation I have $P(c) \vee Q(c)$ for the first hypothesis and $(\neg P(c) \wedge Q(c) \rightarrow R(c))$ for the second hypothesis. After this I don't know what else to do please help.

Answer 1

OK: you've got as far as

$P(c) \vee Q(c)\\ ((\neg P(c) \wedge Q(c)) \rightarrow R(c))$

and your first target is to show $(\neg R(c) \rightarrow P(c))$. Once you can derive that, then you can generalize to get $\forall x(\neg R(x) \rightarrow P(x))$.

This leaves you with some straightforwardly propositional reasoning to do. Now, you want to prove a conditional. So assume the antecedent $\neg R(c)$ and aim for the consequent $P(c)$.

Cutting down on notation, then, what you need to do is fill in a proof of this shape:

$(P \lor Q)\\ ((\neg P \land Q) \to R)\\ \quad\quad|\quad \neg R\\ \quad\quad|\quad \vdots\\ \quad\quad|\quad P\\ (\neg R \to P)\quad\quad\quad\quad\text{By conditional proof}$

How exactly you do this will depend on your available rules of inference. A helpful rule of thumb is: if in doubt, try reductio! In other words, try

$(P \lor Q)\\ ((\neg P \land Q) \to R)\\ \quad\quad|\quad \neg R\\ \quad\quad|\quad \quad | \quad \neg P\\ \quad\quad|\quad \quad | \quad \vdots\\ \quad\quad|\quad \quad | \quad \bot\\ \quad\quad|\quad \neg\neg P\quad\quad\quad\text{By reductio}\\ \quad\quad|\quad P\\ (\neg R \to P)$

How are we going to fill this out now? Well the obvious thing to do is make use of the first premiss, and go for disjunction elimination so you get something of this shape

$(P \lor Q)\\ ((\neg P \land Q) \to R)\\ \quad\quad|\quad \neg R\\ \quad\quad|\quad \quad | \quad \neg P\\ \quad\quad|\quad \quad | \quad \quad | \quad P\\ \quad\quad|\quad \quad | \quad \quad | \quad \vdots\\ \quad\quad|\quad \quad | \quad \quad | \quad \bot \\ \quad\quad|\quad \quad | \quad \quad / \\ \quad\quad|\quad \quad | \quad \quad | \quad Q \\ \quad\quad|\quad \quad | \quad \quad | \quad \vdots \\ \quad\quad|\quad \quad | \quad \quad | \quad \bot \\ \quad\quad|\quad \quad | \quad \bot\quad\quad\quad\text{From first premiss and the two [not yet completed] subproofs}\\ \quad\quad|\quad \neg\neg P\\ \quad\quad|\quad P\\ (\neg R \to P)$

The first subproof is trivial! For the second subproof we can use the second premiss in a modus ponens inference to end up with ...

$(P \lor Q)\\ ((\neg P \land Q) \to R)\\ \quad\quad|\quad \neg R\\ \quad\quad|\quad \quad | \quad \neg P\\ \quad\quad|\quad \quad | \quad \quad | \quad P\\ \quad\quad|\quad \quad | \quad \quad | \quad \bot \\ \quad\quad|\quad \quad | \quad \quad / \\ \quad\quad|\quad \quad | \quad \quad | \quad Q \\ \quad\quad|\quad \quad | \quad \quad | \quad (\neg P \land Q) \quad\quad\quad\text{Conjunction introduction}\\ \quad\quad|\quad \quad | \quad \quad | \quad R \quad\quad\quad\quad\quad\text{Modus ponens}\\ \quad\quad|\quad \quad | \quad \quad | \quad \bot \quad\quad\quad\quad\quad\text{Since you have $R$ and $\neg R$ in play}\\ \quad\quad|\quad \quad | \quad \bot\\ \quad\quad|\quad \neg\neg P\\ \quad\quad|\quad P\\ (\neg R \to P)$

Not the most obvious proof in the history of natural deduction proofs for propositional logic, but it falls out easily enough with a bit of strategic thinking. (Fine details will depend of course on the version of natural deduction for the propositional connectives which you are working with.)