Results 1 to 6 of 6

Math Help - Predicate logic - Tautology?

  1. #1
    Junior Member
    Joined
    Oct 2008
    Posts
    74
    Awards
    1

    Predicate logic - Tautology?

    I'm struggling a bit with these formulas, whether they are tautologies or not;

    1) \forall x P(x) \wedge \exists x (P(x) \to Q(x)) \to \forall x Q(x)

    2) \exists y \forall x R(x,y) \to \forall x \exists yR(x,y)


    Any help/tips on where to start/solve these would be greatly appreciated!
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Junior Member
    Joined
    Oct 2008
    Posts
    74
    Awards
    1
    Hmmm....
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,712
    Thanks
    1642
    Awards
    1
    Quote Originally Posted by jokke22 View Post
    2) \exists y \forall x R(x,y) \to \forall x \exists yR(x,y)
    A. \exists y \forall x R(x,y)\;\;\;\;. B. \forall x \exists yR(x,y)
    Suppose that R(x,y) reads “x is causes y”.
    Then the A statements reads: Something is caused by everything.
    The B statement reads: Everything causes something.
    Now does A imply B?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Senior Member
    Joined
    Nov 2008
    Posts
    394
    Quote Originally Posted by jokke22 View Post
    2) \exists y \forall x R(x,y) \to \forall x \exists yR(x,y)
    1. \vdash \exists y \forall x R(x,y) \to \forall x \exists yR(x,y)
    2.  \exists y \forall x R(x,y) \vdash \forall x \exists yR(x,y) (by deduction theorem)
    3. \forall x R(x, c) \vdash \forall x \exists yR(x,y) (by rule EI, existential instantiation)
    4. \forall x R(x, c) \vdash \exists yR(x,y) (by generalization theorem)
    5. R(x, c) \vdash \exists yR(x,y) (by generalization theorem)
    6.  \forall y \neg R(x,y) \vdash \neg R(x,c) (contraposition)
    7.  \neg R(x,c) \vdash \neg R(x,c) (quantifier axiom)

    Thus, (2) is tautology.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Junior Member
    Joined
    Oct 2008
    Posts
    74
    Awards
    1
    Quote Originally Posted by aliceinwonderland View Post
    1. \vdash \exists y \forall x R(x,y) \to \forall x \exists yR(x,y)
    2.  \exists y \forall x R(x,y) \vdash \forall x \exists yR(x,y) (by deduction theorem)
    3. \forall x R(x, c) \vdash \forall x \exists yR(x,y) (by rule EI, existential instantiation)
    4. \forall x R(x, c) \vdash \exists yR(x,y) (by generalization theorem)
    5. R(x, c) \vdash \exists yR(x,y) (by generalization theorem)
    6.  \forall y \neg R(x,y) \vdash \neg R(x,c) (contraposition)
    7.  \neg R(x,c) \vdash \neg R(x,c) (quantifier axiom)

    Thus, (2) is tautology.
    That is thorough! Thank you!

    Those rules any site which shows "all" used in predicate logic? My school book is missing out on some of them.

    As for A), struggling hard myself, any help/suggestion on this as well?
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Senior Member
    Joined
    Nov 2008
    Posts
    394
    Quote Originally Posted by jokke22 View Post
    1) \forall x P(x) \wedge \exists x (P(x) \to Q(x)) \to \forall x Q(x)
    1. \{\forall x P(x), \exists x (P(x) \to Q(x)) \} \vdash \forall x Q(x).
    2. \{\forall x P(x), \exists x( \neg P(x) \vee Q(x) \} \vdash \forall x Q(x) .
    3. \{\forall x P(x), \exists x \neg P(x) \vee \exists x Q(x) \} \vdash \forall x Q(x) .
    4. \{\forall x P(x), \neg \forall x P(x) \vee \exists x Q(x) \} \vdash \forall x Q(x) .
    5. \{\forall x P(x), \exists x Q(x) \} \vdash \forall x Q(x) .

    Note.
    Since \{\exists x Q(x) \} \vdash \forall x Q(x) is not valid, 5 is not valid.
    3 uses the rule of union for existential quantifier (link).
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. tautology/logic help
    Posted in the Discrete Math Forum
    Replies: 5
    Last Post: September 12th 2010, 02:24 PM
  2. Predicate Logic
    Posted in the Discrete Math Forum
    Replies: 5
    Last Post: April 29th 2010, 03:51 PM
  3. Predicate Logic HELP.
    Posted in the Discrete Math Forum
    Replies: 7
    Last Post: February 16th 2010, 08:54 AM
  4. Replies: 1
    Last Post: March 27th 2009, 06:43 AM
  5. More predicate logic
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: March 4th 2009, 06:45 PM

Search Tags


/mathhelpforum @mathhelpforum