0
$\begingroup$

I have the following argument:

-∀x(P(x) ∨ Q(x))

∀x(¬P(x) ∧ Q(x)) → R(x)

___________________.

∴ ∀x(¬R(x) → P(x))

I don't want the answer. I just need some general tips to get there. I know I can use Universal Instantiation on the two arguments to remove $\forall$$x$, but that's about it. I can't see any other rules I could use.

$\endgroup$
1
$\begingroup$

You can rewrite the second sentence as: $$\forall x (\neg R(x) \to \neg(\neg P(x) \wedge Q(x)))$$ by taking the contrapositive of the inner formula. That in turn is equivalent to: $$\forall x (\neg R(x) \to P(x) \vee \neg Q(x))$$ (Here, we get rid of one pair of parentheses by using the convention that $\vee, \wedge$ bind more tightly than $\to$). So temporarily instantiate the universally quantified x: $$ (\neg R(a) \to P(a) \vee \neg Q(a))$$. Suppose $$\neg R(a) \tag{not-R(a)}$$ Then: $$ P(a) \vee \neg Q(a) \tag{PnotQ}$$ Instantiating the first sentence $\forall x (P(x) \vee Q(x))$ with $a$ gives: $$P(a) \vee Q(a) \tag{PQ}$$ From (PnotQ) and (PQ) you can conclude: $$P(a)$$ Here's why: (PnotQ) is equivalent to $Q(a) \to P(a)$, and (PQ) is equivalent to $\neg Q(a) \to P(a)$. From these, we can conclude $Q(a) \vee \neg Q(a) \to P(a)$. But of course $Q(a) \vee \neg Q(a)$ is provable, so by modus ponens, $P(a)$.

Discharging the assumption (not-R(a)) gives: $$\neg R(a) \to P(a)$$ Finally, $a$ was just temporary, so we can eliminate it and universally quantify: $$ \forall x(\neg R(x) \to P(x))$$

$\endgroup$
  • $\begingroup$ I added a bit to explain what you asked about in your comment, which has now disappeared... so perhaps I didn't have to. $\endgroup$ – BrianO Oct 13 '15 at 2:36
  • $\begingroup$ How did you conclude with P(a)? $\endgroup$ – Andrew Kor Oct 13 '15 at 2:38
  • $\begingroup$ See the "Here's why:" paragraph -- still not clear? $\endgroup$ – BrianO Oct 13 '15 at 2:39
  • $\begingroup$ sorry i added that comment just as you edited the post. im confused about the $Q(a) \rightarrow P(a)$ part. the rest makes sense $\endgroup$ – Andrew Kor Oct 13 '15 at 2:40
  • $\begingroup$ But that's just instantiating the first of your two hypotheses. $\endgroup$ – BrianO Oct 13 '15 at 2:41
0
$\begingroup$

In the second assumption you write that P(x) and Q(x) can't occur so by contraopistion of the second assumption combining with the first you the required result.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.