Rules of Inference - Stuck on discrete problem

Printable View

September 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!
September 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]
September 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)$