Results 1 to 6 of 6

Math Help - Predicate Logic

  1. #1
    Newbie
    Joined
    Jan 2011
    Posts
    13

    Post Predicate Logic

    The domain of the following predicates is all integers greater than 1.
    P(x) = “x is prime”
    Q(x,y) = “x divides y”
    Consider the following statement.
    “For every x that is not prime, there is some prime y that divides it”

    i. Write the statement in predicate logic.
    ii. Formally negate the statement so that no quantifier lies in the scope of the
    negation.
    iii. Write the English translation of your negated statement

    I tried this and I got

    i. ∀x¬P(x)∃xQ(x,y)

    ii. ∃xP(x)∀x¬Q(x,y)

    iii. There exists a x that is prime, there is y for every prime that does not divide it.

    Thanks
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,614
    Thanks
    1581
    Awards
    1
    Quote Originally Posted by Newskin01 View Post
    The domain of the following predicates is all integers greater than 1.
    P(x) = “x is prime”
    Q(x,y) = “x divides y”
    Consider the following statement.
    “For every x that is not prime, there is some prime y that divides it”
    i. Write the statement in predicate logic.
    ii. Formally negate the statement so that no quantifier lies in the scope of the negation.
    iii. Write the English translation of your negated statement
    I would say that first one is:
    i. \left( {\forall x} \right)\left( {\exists y} \right)\left[ {P(x) \vee \left( {P(y) \wedge Q(y,x)} \right)} \right]
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,530
    Thanks
    774
    Or, equivalently, \forall x\,(\neg P(x)\to\exists y\,(P(y)\land Q(y,x)), which is perhaps closer to the English sentence.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,614
    Thanks
    1581
    Awards
    1
    Quote Originally Posted by emakarov View Post
    Or, equivalently, \forall x\,(\neg P(x)\to\exists y\,(P(y)\land Q(y,x)), which is perhaps closer to the English sentence.
    There can be no doubt that is "closer to the English sentence".
    The reason I did not use that was these instructions: i. Formally negate the statement so that no quantifier lies in the scope of the negation..
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,530
    Thanks
    774
    The reason I did not use that was these instructions: i. Formally negate the statement so that no quantifier lies in the scope of the negation.
    What difference does it make? This instruction says, after negating the formula, to move the negation inside so that it is inside the quantifiers' scopes. It has nothing to do with the original formula, which in any case has no quantifiers in the scope of the negation.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,614
    Thanks
    1581
    Awards
    1
    Quote Originally Posted by emakarov View Post
    What difference does it make? This instruction says, after negating the formula, to move the negation inside so that it is inside the quantifiers' scopes. It has nothing to do with the original formula, which in any case has no quantifiers in the scope of the negation.
    I thought is was less confusing. That is all.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Predicate Logic
    Posted in the Discrete Math Forum
    Replies: 5
    Last Post: April 29th 2010, 03:51 PM
  2. Predicate Logic #2
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: February 21st 2010, 08:34 PM
  3. Predicate Logic HELP.
    Posted in the Discrete Math Forum
    Replies: 7
    Last Post: February 16th 2010, 08:54 AM
  4. predicate logic
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: March 6th 2009, 01:06 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