I have this sentence in first order logic and I need to negate it.
$\forall x, y ((horse(x) \land rabbit(y)) \to outrun(x, y))$
As far as I know, to negate this I need it to have the opposite meaning. Right now the meaning is all horses can outrun all rabbits. So the negation would have to be no horses can outrun any rabbits. My initial idea is to use an existential with a negation which basically says that there does not exists a single horse that can outrun a rabbit. Would that be correct with the negation and if it is then would I need to change anything else in my sentence (particularly the implication)? In other words, would $\neg\exists x, y ((horse(x) \land rabbit(y)) \land outrun(x, y))$ be the correct negation?
Best Answer
The rule you should apply is $\neg (\forall x. P(x)) = \exists x. \neg P(x)$. This will bring you (after simplifying $\neg (a \rightarrow b)$ to $a ∧ \neg b$ ) to $\exists x y. (horse(x) ∧ rabbit(y) ∧ \neg outrun(x,y))$.
PS You should simply apply the rules, not change the rules such that the resulting formula reflects what you would like :).