How to prove universally-quantified formula is true by contraposition? > For all natural numbers $x$ and $y$, if $x+y$ is odd, then $x$ is odd or $y$ is odd. How do I prove the following statement is true by contraposition without using a truth table and theorems?

The contrapositive of "if $x+y$ is odd then either $x$ is odd or $y$ is odd" would be "if $x$ and $y$ are both even or both odd, then $x+y$ is even".

The sum of two even numbers, $2a$ and $2b$, is $2(a+b)$, which is even. The sum of two odd numbers, $2a+1$ and $2b+1$, is $2(a+b+1)$, which is even too. This is sufficient.

In fact, you can prove that the implication goes both ways very similarly.

_Edit_ : as originally stated, one could assume that "or" in "$x$ is odd or $y$ is odd" is not exclusive. In that case the statement only works in one direction, and the proof by contraposition involves proving the statement "$x$ even and $y$ even implies $x+y$ even", which is proved above.