Negation of quantifiers and predicates

Printable View

March 18th 2010, 04:56 AM
jvignacio

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
March 18th 2010, 05:38 AM
emakarov

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)
March 18th 2010, 05:59 AM
jvignacio

Quote:

Originally Posted by emakarov

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 :)
March 18th 2010, 10:58 AM
emakarov

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.
March 19th 2010, 06:08 PM
jvignacio

Quote:

Originally Posted by emakarov

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!!