# Negation of a quantified statement

I would like to negate the following:

$\exists x, \forall y, \forall z ((F(x,y) \land G(x,z)) \rightarrow H(y,z))$

Would the following proposed solution be correct?

(1) First simplify what is in the brackets - $((F(x,y) \land G(x,z)) \rightarrow H(y,z))$

$(\lnot(F(x,y) \land G(x,z)) \lor H(y,z))$

(2) $\forall x, \exists y, \exists z \lnot ( \lnot(F(x,y) \land G(x,z)) \lor H(y,z))$

$\equiv \forall x, \exists y, \exists z((F(x,y) \land G(x,z)) \land \lnot H(y,z))$

-
Yes, though you’ve done a little more work than necessary. If you remember that $\lnot(\varphi\to\psi)$ is $\varphi\land\lnot\psi$, you can go directly to $$\forall x\exists y\exists z\Big(F(x,y)\land G(x,z)\land\lnot H(y,z)\Big)\;.$$ – Brian M. Scott Nov 14 '12 at 21:36
cheers @BrianM.Scott – bosra Nov 14 '12 at 21:39

The negation of $P \Rightarrow Q$ is $$\neg(P \Rightarrow Q) \equiv (P \wedge \neg Q)$$ and the negation of "for all" is $$\neg (\forall x)(P(x)) \equiv (\exists x)(\neg P(x)).$$ Similarly, $$\neg (\exists x)(P(x)) \equiv (\forall x)(\neg P(x))$$ so your answer is correct.