How to negate a complicated statement. For all $x \in \mathbb{Z}$, if there exists $y \in \mathbb{Z}$ such that $x = 2y+1$ then there exists $z \in \mathbb{Z}$ such that $x^2 = 2z + 1$.
This is the statement that I am having trouble negating, because it uses the phrase'such that' twice. 
 A: I myself prefer words, as do most humans.

For all $x \in \mathbb{Z}$, if there exists $y \in \mathbb{Z}$ such that $x = 2y+1$ then there exists $z \in \mathbb{Z}$ such that $x^2 = 2z + 1$.

This can be translated into something more intelligible.

For all integers $x$ (for all $x \in \mathbb{Z}$), if $x$ is odd (if there exists an $y \in \mathbb{Z}$ such that $x = 2y+1$) then $x^2$ is odd (then there exists $z \in \mathbb{Z}$ such that $x^2 = 2z + 1$).

Now, even more succinctly, one could write

If an integer is odd then so is its square.

Now this statement is easy to negate, right?
A: $$\forall x (\exists y P(x,y))\to (\exists z Q(x,z))$$
We first rewrite $a\to b$ as $b\vee \neg a$:
$$\forall x(\exists z Q(x,z))\vee \neg  (\exists y P(x,y))$$
or
$$\forall x(\exists z Q(x,z))\vee   (\forall  y \neg P(x,y))$$
Now we are ready to negate:
$$\neg \forall x(\exists z Q(x,z))\vee   (\forall  y \neg P(x,y))\equiv$$
$$\exists x \neg ((\exists z Q(x,z))\vee   (\forall  y \neg P(x,y)))\equiv$$
Now use De Morgan's law:
$$\exists x  (\neg (\exists z Q(x,z))\wedge   \neg(\forall  y \neg P(x,y)))\equiv$$
$$\exists x  (\forall z \neg Q(x,z)\wedge   \exists  y \neg \neg P(x,y))\equiv$$
$$\exists x  (\forall z \neg Q(x,z)\wedge   \exists  y P(x,y))$$
A: Let us first put the statement into formula:
$$ \forall x\in \mathbb Z : (\exists y \in \mathbb Z : x = 2y+1) \implies (\exists z \in \mathbb Z : x^2 = 2z + 1). $$
Now, negating is just switch the quantifiers and negating the sub statements:
$$ \exists x\in \mathbb Z : (\exists y \in \mathbb Z : x = 2y+1) \land \lnot (\exists z \in \mathbb Z : x^2 = 2z + 1), $$
which is the same as
$$ \exists x\in \mathbb Z : (\exists y \in \mathbb Z : x = 2y+1) \land (\forall z \in \mathbb Z : x^2 \ne 2z + 1). $$
A: Maybe adding commas and parenthesis helps:
$\forall x \in \mathbb{Z},\quad  [( \exists y \in \mathbb{Z} : x = 2y+1)\implies \exists z \in \mathbb{Z}:x^2 = 2z + 1]$.
This negates to
$\exists  x \in \mathbb{Z},\quad [ (\exists y\in \mathbb{Z}: x = 2y+1)$ does not imply $\exists z \in \mathbb{Z}:x^2 = 2z + 1]$.
Which can be rewritten as
$\exists  x \in \mathbb{Z},\quad [\exists y\in \mathbb{Z}: (x = 2y+1\&\nexists z \in \mathbb{Z}:x^2 = 2z + 1]$.
Which can be read as ' there exists an x such that the existence of a y which fullfils the requirement does not imply the existence of a z wich fullfils the 2nd req' , or ' for at least one x, we can find at least one y fulfilling the requirement, and there will not be a z fulfilling the 2nd req'.
The req is belong in $Z$ and $x=2y+1$. The 2nd is belong in $Z$ and $x^2 = 2z + 1$.
