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.


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)$$


$$\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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.