Results 1 to 5 of 5

Math Help - Proving the Validity of an Argument in Predicate Logic

  1. #1
    Newbie
    Joined
    Mar 2009
    From
    Plymouth
    Posts
    12

    Proving the Validity of an Argument in Predicate Logic - Another pointer please!

    Hi all,

    I am having an issue with the following question, I wonder if anyone could point me in the right direction:

    Using only the standard rules of inference and logical equivalence, prove the validity of the following argument, where the propositional functions P, Q, R and S share the same domain.



    Any suggestions would be much appreciated!
    Last edited by ft_fan; March 12th 2009 at 01:16 PM.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Senior Member
    Joined
    Nov 2008
    Posts
    394
    Quote Originally Posted by ft_fan View Post
    Hi all,

    I am having an issue with the following question, I wonder if anyone could point me in the right direction:

    Using only the standard rules of inference and logical equivalence, prove the validity of the following argument, where the propositional functions P, Q, R and S share the same domain.



    Any suggestions would be much appreciated!
    You might need to consider the following steps.

    1. Change an existential quantifier in Premise 2 into a universal quantifier.

    \neg \forall x (\neg R(x) .......

    2. Drop all universal quantifers for premise 1 and 2.

    3. Eliminate implications using  \neg, \vee...
    4. Using resolutions (if needed), reduce Premise1 \wedge Premise 2.
    5. Restore a universal quantifer and implication if possible. Then check it with a conclusion whether or not it is valid.
    Last edited by aliceinwonderland; March 11th 2009 at 03:35 AM. Reason: Error correction
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Mar 2009
    From
    Plymouth
    Posts
    12
    Thanks a lot for your hints, I'm on track now!

    Cheers!
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Newbie
    Joined
    Mar 2009
    From
    Plymouth
    Posts
    12
    Okay, so I'm getting there, but I'm stuck again, although I think I'm close! What I have so far is as follows:

    1.  \forall x (R(x) \rightarrow \forall y (S(y) \rightarrow (\neg Q (x,y)))) - Premise

    2.  \exists x (R(x) \wedge \forall y (P(y) \rightarrow Q(x,y))) - Premise

    3.  R(x) \wedge \forall y(P(y) \rightarrow Q(x,y)) -  \exists _E from 2.

    4.  R(x) \rightarrow \forall y (S(y) \rightarrow (\neg Q(x,y))) -  \forall _E from 1.

    5.  \neg R(x) \vee \forall y (S(y) \rightarrow (\neg Q(x,y))) - Implication, from 4.

    6.  \neg R(x) \vee (S(y) \rightarrow (\neg Q(x,y)) -  \forall _E on 5.

    7.  \neg R(x) \vee ((\neg S(y)) \vee (\neg Q(x,y)) - Implication from 6.

    8.  \forall y(P(y) \rightarrow Q(x,y)) \wedge R(x) - Commutative, from 3.

    9.  \forall y (P(y) \rightarrow Q(x,y)) - 8, simplification.

    10.  P(y) \rightarrow Q(x,y) -  \forall _E from 9.

    11.  \neg P(y) \vee Q(x,y) - 10, implication.

    I just can't see how to proceed - any advice, much appreciated!
    Last edited by ft_fan; March 12th 2009 at 01:15 PM.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,605
    Thanks
    1574
    Awards
    1
    1.  \forall x (R(x) \rightarrow \forall y (S(y) \rightarrow (\neg Q (x,y)))) - Premise

    2.  \exists x (R(x) \wedge \forall y (P(y) \rightarrow Q(x,y))) - Premise

    3.  R(a) \wedge \forall y(P(y) \rightarrow Q(a,y)) -  \exists _E from 2. [changed to a]

    4.  R(a) \rightarrow \forall y (S(y) \rightarrow (\neg Q(a,y))) -  \forall _E from 1.

    5. \forall y(P(y) \rightarrow Q(a,y)) _Simp from 3

    6. (P(y) \rightarrow Q(a,y)) -  \forall_from 5

    7.  R(a) _simp from 3

    8. \forall y (S(y) \rightarrow (\neg Q(a,y))) _M.P. From 4 & 7.

    9. S(y) \rightarrow \neg Q(a,y) -  \forall_from 8

    10.  Q(a,y) \rightarrow \neg S(y) –Trans from 9

    11.  P(y) \rightarrow \neg S(y) –H.S. from 6 &10.

    Now can you preceed?
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Proving a Theorem (Predicate Logic)
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: October 13th 2011, 03:57 AM
  2. Argument #4, determine validity.
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: May 14th 2011, 04:25 PM
  3. Prove validity of an argument by Indirect derivation
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: November 13th 2010, 07:23 PM
  4. Predicate Logic
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: November 5th 2010, 07:53 AM
  5. Predicate Logic
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: February 21st 2010, 08:39 PM

Search Tags


/mathhelpforum @mathhelpforum