# Negation of statements

I have a statement; for all integers $t$, $j$ (if $t$ is odd and $j$ is even, then $t+j$ is odd).

$$\forall t,j \in\mathbb{Z}:(O(t) \wedge E(j) )\implies O(t+j)$$ where

$E(z)$: $z$ is even

$O(z)$: $z$ is odd.

I am asked to prove this by negation, I am having trouble figuring out the negation that I should prove. Is it any of these?

$$\forall x,y: p \wedge q \implies r.$$

Would I be taking the negation in parts (negation $p$ and $q$ then of $p$ implies $r$) which would be $$\exists x,y: (\neg p \vee \neg q )\wedge \neg r$$ "for some integers $x$ and $y$, if $x$ is not odd, or $y$ is not even and $x+y$ is not odd"

Or would i only follow the negation of $$p \implies q$$ which would be:

$$\exists x,y: (p \wedge q) \wedge \neg r$$

"for some integers $x$ and $y$, $x$ is odd and $y$ is even and $x+y$ is not odd"

Are any of the above correct? I am having a hard time because making them back into english is weird.

## 1 Answer

Take it one step at a time. The negation of

$$\forall t,j \in\mathbb{Z}\,\big((O(t) \wedge E(j) )\to O(t+j)\big)$$

is

$$\neg\forall t,j\in\mathbb{Z}\,\big((O(t) \wedge E(j) )\to O(t+j)\big)\;.\tag{1}$$

$\neg\forall x\,\varphi(x)$, the negation of $\forall x\,\varphi(x)$, is equivalent to $\exists x\,\big(\neg\varphi(x)\big)$, so $(1)$ is equivalent to

$$\exists t,j\in\mathbb{Z}\,\Big(\neg\big((O(t) \wedge E(j) )\implies O(t+j)\big)\Big)\;.\tag{2}$$

To simplify this further, you have to simplify something of the form $\neg(p\to q)$. The negation of an implication $p\to q$ is $p\land\neg q$, asserting that the antecedent is true, but the consequent is false. Thus, $(2)$ simplifies to

$$\exists t,j\in\mathbb{Z}\,\Big(\big(O(t)\land E(j)\big)\land\neg O(t+j)\Big)\;,$$

from which we can remove the inner parentheses to get

$$\exists t,j\in\mathbb{Z}\,\big(O(t)\land E(j)\land\neg O(t+j)\big)\;.\tag{3}$$

In words, there are an odd integer and an even integer whose sum is not odd.

If your system includes the fact that $\neg O(x)$ is equivalent to $E(x)$, you can further simplify $(3)$ to

$$\exists t,j\in\mathbb{Z}\,\big(O(t)\land E(j)\land E(t+j)\big)\;.$$

In words, there are an odd integer and an even integer whose sum is even.

• Thank you, this was a perfect explanation – splinks Jul 30 '16 at 21:40
• @splinks: You’re welcome! – Brian M. Scott Jul 30 '16 at 21:42