Results 1 to 5 of 5

Math Help - Negation of quantifiers and predicates

  1. #1
    Super Member
    Joined
    Oct 2007
    From
    Santiago
    Posts
    517

    Negation of quantifiers and predicates

    Hey guys, I have a question I answered, just want to make sure I got the correct answer or if I made any silly mistakes!

    So, negate the sentence:  \exists x ( \forall y ( Q(x,y) \wedge ( ( \neg P(x,q) \vee Q(x,y)) \rightarrow Qy)))

    \Longrightarrow \neg \exists x ( \forall y ( Q(x,y) \wedge ( ( \neg P(x,q) \vee Q(x,y))  \rightarrow Qy)))

    \Longrightarrow  \forall x \neg ( \forall y ( Q(x,y) \wedge ( ( \neg P(x,q) \vee Q(x,y))  \rightarrow Qy)))

    \Longrightarrow  \forall x  ( \exists y \neg( Q(x,y) \wedge ( ( \neg P(x,q) \vee Q(x,y))  \rightarrow Qy)))

    \Longrightarrow  \forall x  ( \exists y ( \neg Q(x,y) \vee \neg ( ( \neg P(x,q) \vee Q(x,y))  \rightarrow Qy)))

    \Longrightarrow  \forall x  ( \exists y ( \neg Q(x,y) \vee ( (  \neg P(x,q) \vee Q(x,y))  \wedge \neg Qy)))

    now since my final answer can only involve the negation being on the   \neg P(x,q) and the  \neg Q(x,y) to get rid of the final negation on the \neg Qy what do i need to do?

    Thanks
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,561
    Thanks
    785
    I rewrote the formula a bit to better show the scopes.

    \exists x\,\forall y \Big( Q(x,y) \wedge \big( [ \neg P(x,q) \vee Q(x,y)] \rightarrow Qy\big)\Big)

    I think your answer is correct. What is strange is that in the original formula two different predicates Q(x,y) and Q(y) are denoted by the same letter. My guess is that the person who assigned this wanted to say that only atomic formulas can be negated, and, seeing only P and Q, he/she said that negations can only be in front of P(x,y) and Q(x,y)
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Super Member
    Joined
    Oct 2007
    From
    Santiago
    Posts
    517
    Quote Originally Posted by emakarov View Post
    I rewrote the formula a bit to better show the scopes.

    \exists x\,\forall y \Big( Q(x,y) \wedge \big( [ \neg P(x,q) \vee Q(x,y)] \rightarrow Qy\big)\Big)

    I think your answer is correct. What is strange is that in the original formula two different predicates Q(x,y) and Q(y) are denoted by the same letter. My guess is that the person who assigned this wanted to say that only atomic formulas can be negated, and, seeing only P and Q, he/she said that negations can only be in front of P(x,y) and Q(x,y)
    Although my final answer cant have a negation on the last \neg  Qy which i still don't know how to remove it bit confused! would you then just have to negate the \neg  Qy which would be  Qy ?

    btw thanks for re writing the formula, i couldnt figure out how to make the big brackets
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,561
    Thanks
    785
    There is no way to remove negation in front of Qy. This is a general fact. Every atom in a formula occurs either in a positive or in a negative position. A position is called positive if it is under even number of negations; otherwise it is called negative. Also, since A\to B is equivalent to \neg A\lor B, a premise of an implication is also considered as being under negation. So, for example, the only occurrence of P(x,q) in the original formula is positive because it is in a premise and under one negation.

    Now, whether an occurrence is positive or negative is invariant in equivalent formulas. Since Qy occurs positively in the original formula, it occurs negatively in the negation, and it will continue to occur in a negative position in any equivalent formula.

    What I am saying is that the original formula does not make sense as written because two different things are denoted by the same letter. I think that it is a typo.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Super Member
    Joined
    Oct 2007
    From
    Santiago
    Posts
    517
    Quote Originally Posted by emakarov View Post
    There is no way to remove negation in front of Qy. This is a general fact. Every atom in a formula occurs either in a positive or in a negative position. A position is called positive if it is under even number of negations; otherwise it is called negative. Also, since A\to B is equivalent to \neg A\lor B, a premise of an implication is also considered as being under negation. So, for example, the only occurrence of P(x,q) in the original formula is positive because it is in a premise and under one negation.

    Now, whether an occurrence is positive or negative is invariant in equivalent formulas. Since Qy occurs positively in the original formula, it occurs negatively in the negation, and it will continue to occur in a negative position in any equivalent formula.

    What I am saying is that the original formula does not make sense as written because two different things are denoted by the same letter. I think that it is a typo.
    Yep ok I understand. thanks for the help!!
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Predicates And Quantifiers Hell
    Posted in the Discrete Math Forum
    Replies: 11
    Last Post: March 22nd 2010, 07:40 AM
  2. Replies: 1
    Last Post: August 26th 2009, 09:04 AM
  3. Predicates Help
    Posted in the Discrete Math Forum
    Replies: 7
    Last Post: March 4th 2009, 03:18 PM
  4. Replies: 2
    Last Post: January 27th 2009, 09:05 AM
  5. Predicates help
    Posted in the Math Topics Forum
    Replies: 1
    Last Post: September 29th 2008, 09:20 AM

Search Tags


/mathhelpforum @mathhelpforum