Results 1 to 3 of 3

Math Help - Rules of Inference - Stuck on discrete problem

  1. #1
    Newbie
    Joined
    Aug 2009
    Posts
    15

    Rules of Inference - Stuck on discrete problem

    Use rules of inference to show that if

    <br /> <br />
\forall x (P(x) \vee Q(x)) and \forall x ((\neg P(x) \wedge Q(x)) \rightarrow R(x))<br /> <br />

    then

    <br /> <br />
\forall x (\neg R(x) \rightarrow P(x))<br /> <br />

    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!
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Junior Member
    Joined
    Oct 2006
    Posts
    71
    Quote Originally Posted by Dfowj View Post
    Use rules of inference to show that if

    <br /> <br />
\forall x (P(x) \vee Q(x)) and \forall x ((\neg P(x) \wedge Q(x)) \rightarrow R(x))<br /> <br />

    then

    <br /> <br />
\forall x (\neg R(x) \rightarrow P(x))<br /> <br />

    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]
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Sep 2009
    Posts
    12
    Another solution:

    <br />
 \forall x \left\{<br />
\begin{array}{l}<br />
(P(x) \vee Q(x)) \\<br />
((\neg P(x) \wedge Q(x)) \rightarrow R(x)) <br />
\end{array}<br />
\right.<br />
\Longleftrightarrow<br />
\forall x \left\{<br />
\begin{array}{l}<br />
(P(x) \vee Q(x)) \\<br />
(P(x) \vee \neg Q(x) \vee R(x))<br />
\end{array}<br />
\right.<br />

    <br />
\begin{aligned}<br />
& \Longleftrightarrow \forall x (P(x) \vee Q(x)) \wedge (P(x) \vee \neg Q(x) \vee R(x)) \\<br />
& \Longleftrightarrow \forall x (P(x) \wedge (P(x) \vee \neg Q(x) \vee R(x) ))<br />
\vee (Q(x) \wedge (P(x) \vee \neg Q(x) \vee R(x)))<br />
\end{aligned}<br />
    <br />
\begin{aligned}<br />
& \Longleftrightarrow \forall x P(x) <br />
\vee (Q(x) \wedge (P(x) \vee R(x))) \Rightarrow (P(x) \vee R(x))<br />
\end{aligned}<br />
    <br />
 \forall x (R(x) \vee P(x)) \Longleftrightarrow \forall x (\neg R(x) \rightarrow P(x))<br />

    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)
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Rules of Inference
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: October 11th 2009, 11:36 PM
  2. Rules of Inference... I think
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: September 17th 2009, 04:53 PM
  3. HELP: Rules of Inference
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: September 8th 2009, 10:08 AM
  4. Rules of Inference Help
    Posted in the Discrete Math Forum
    Replies: 5
    Last Post: March 8th 2009, 08:25 AM
  5. Rules Of Inference
    Posted in the Discrete Math Forum
    Replies: 7
    Last Post: November 5th 2008, 06:00 PM

Search Tags


/mathhelpforum @mathhelpforum