# Rules of Inference - Stuck on discrete problem

• Sep 22nd 2009, 08:28 PM
Dfowj
Rules of Inference - Stuck on discrete problem
Use rules of inference to show that if

$

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

$

then

$

\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!
• Sep 23rd 2009, 04:28 AM
PiperAlpha167
Quote:

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

$

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

$

then

$

\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]
• Sep 23rd 2009, 04:57 AM
paweld
Another solution:

$
\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.
$


\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}


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

$
\forall x (R(x) \vee P(x)) \Longleftrightarrow \forall x (\neg R(x) \rightarrow P(x))
$

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