# Thread: Rules of Inference - Stuck on discrete problem

1. ## Rules of Inference - Stuck on discrete problem

Use rules of inference to show that if

$\displaystyle \forall x (P(x) \vee Q(x))$ and $\displaystyle \forall x ((\neg P(x) \wedge Q(x)) \rightarrow R(x))$

then

$\displaystyle \forall x (\neg R(x) \rightarrow P(x))$

Im doing test review stuff, and im just plain stuck here... I can get about halfway, then after that i can't make any connections. Any help would be great!

2. Originally Posted by Dfowj
Use rules of inference to show that if

$\displaystyle \forall x (P(x) \vee Q(x))$ and $\displaystyle \forall x ((\neg P(x) \wedge Q(x)) \rightarrow R(x))$

then

$\displaystyle \forall x (\neg R(x) \rightarrow P(x))$

Im doing test review stuff, and im just plain stuck here... I can get about halfway, then after that i can't make any connections. Any help would be great!
Here's an outline.

Assume you're in an NDS, with the standard prime rules.

1. You have a universally quantified conclusion. So think final step will be application of universal quantifier introduction.
2. Let u denote some arbitrary member of universe; call it a temporary constant if you like.
3. Drop universal quantifiers on the premisses (by universal quantifier elimination), and express them as Pu V Qu and (~Pu & Qu)->Ru
4. Assume ~Ru. Then assume ~Pu. (So essentially the derivation will be by CP (->I), with a subderivation by RAA (~I).)
5. Now hunt for a blatant contradiction, i.e., a self-contradiction. The one you might be looking for is: Ru & ~Ru.
6. Once you find it, you're almost home. The contradiction allows you to state, ~~Pu, by RAA. From this get Pu.
7. Now from your original assumption, ~Ru, you have, ~Ru->Pu, by CP.
8. Finally get the universally quantifed conclusion by an application of universal quantifier introduction mentioned above: (x)[~Rx->Px].

So then we have: (x)[Px V Qx], (x)[(~Px & Qx)->Rx] |- (x)[~Rx->Px]

3. Another solution:

$\displaystyle \forall x \left\{ \begin{array}{l} (P(x) \vee Q(x)) \\ ((\neg P(x) \wedge Q(x)) \rightarrow R(x)) \end{array} \right. \Longleftrightarrow \forall x \left\{ \begin{array}{l} (P(x) \vee Q(x)) \\ (P(x) \vee \neg Q(x) \vee R(x)) \end{array} \right.$

\displaystyle \begin{aligned} & \Longleftrightarrow \forall x (P(x) \vee Q(x)) \wedge (P(x) \vee \neg Q(x) \vee R(x)) \\ & \Longleftrightarrow \forall x (P(x) \wedge (P(x) \vee \neg Q(x) \vee R(x) )) \vee (Q(x) \wedge (P(x) \vee \neg Q(x) \vee R(x))) \end{aligned}
\displaystyle \begin{aligned} & \Longleftrightarrow \forall x P(x) \vee (Q(x) \wedge (P(x) \vee R(x))) \Rightarrow (P(x) \vee R(x)) \end{aligned}
$\displaystyle \forall x (R(x) \vee P(x)) \Longleftrightarrow \forall x (\neg R(x) \rightarrow P(x))$

I used the following laws:
$\displaystyle (p \Rightarrow q) \Longleftrightarrow (\neg p \vee q)$
and
$\displaystyle (p \vee q) \wedge r \Longleftrightarrow (p \vee r) \wedge (q \vee r)$