Results 1 to 5 of 5

Thread: 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; Mar 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.

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

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

    3. Eliminate implications using $\displaystyle \neg, \vee..$.
    4. Using resolutions (if needed), reduce Premise1 $\displaystyle \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; Mar 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. $\displaystyle \forall x (R(x) \rightarrow \forall y (S(y) \rightarrow (\neg Q (x,y)))) $ - Premise

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

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

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

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

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

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

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

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

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

    11. $\displaystyle \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; Mar 12th 2009 at 01:15 PM.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor

    Joined
    Aug 2006
    Posts
    21,735
    Thanks
    2811
    Awards
    1
    1. $\displaystyle \forall x (R(x) \rightarrow \forall y (S(y) \rightarrow (\neg Q (x,y)))) $ - Premise

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

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

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

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

    6. $\displaystyle (P(y) \rightarrow Q(a,y)) $ - $\displaystyle \forall$_from 5

    7. $\displaystyle R(a) $_simp from 3

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

    9. $\displaystyle S(y) \rightarrow \neg Q(a,y) $ - $\displaystyle \forall$_from 8

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

    11. $\displaystyle 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: Oct 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: Nov 13th 2010, 07:23 PM
  4. Predicate Logic
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: Nov 5th 2010, 07:53 AM
  5. Predicate Logic
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: Feb 21st 2010, 08:39 PM

Search Tags


/mathhelpforum @mathhelpforum