Use a proof by contraposition to show that?

Question

Need help.

1) Use a proof by contraposition to show that if m and n are integers such that m + n is odd, then m is odd or n is odd.

Idk how to do it but this is what i think.

Proof by Contraposition

• Suppose m and n are two even integers.
• there exists integers s and t such that m = 2a and n = 2b
• adding we obtain, a+b = 2a+2b= 2(a+b)
• since this represents m+n as 2 times integer a+b, we can conclude that m+n is even

Is that how i Do this question? If not can someone tell me my mistakes and help me solve it.

Thank You.

Answer 1

You should read about the contrapositive. You can think about it as a form of writing a logical statement.

Normally, we write if P then Q (this is a positive statement).

The contrapositive is if (NOT P) then (NOT Q). Exercise: determine that it is equivalent to the positive.

In your case, the positive statement is: if (m + n is odd) then (m is odd or n is odd).

The contrapositive statement is: if NOT (m is odd or n is odd) then NOT (m+n is odd).

Using DeMorgan's Laws, you can simplify this: if ((NOT m is odd) and (NOT n is odd)) then NOT (m+n is odd).

Which simplifies to: if (m is even and n is even) then (m+n is even).

(You may want to take a moment to convince yourself that this is logically equivalent to your original proposition.)

Anyway, we now have if (m is even and n is even) then (m+n is even).

This statement is easy to prove. If $m$ is even, then $m = 2p$ for some integer $p$ and if $n$ is even, then $n = 2q$ for some integer $q$. Then $m+n = 2p + 2q = 2(p+q)$. And since $2(p+q)$ is clearly divisible by $2$, it is even.

Since you proved the contrapositive, the original proposition (its logical equivalent) is also proven. We're done!

Answer 2

You are right. Hence you proved the contraposition (not B implies not A) of what you need, and it is logically the same as proving the proposition (A implies B).

Answer 3

Proof by contrapositive means instead of proving $p \implies q$ you want to prove $\lnot q \implies \lnot p$. So for this instead of proving $m, n \in \mathbb{Z}$ and $m + n$ is odd, then either $m$ or $n$ is odd, you want to prove that if $m$ and $n$ are both even, that $m + n$ is even. We can say that for all even numbers $e$, that $\frac{e}{2}\in\mathbb{Z}$, using this we can say that if $m$ and $n$ are both even that $(m + n) = 2\left(\frac{m}{2} + \frac{n}{2}\right)$. As both $\frac{m}{2}$ and $\frac{n}{2}$ are integers, then $\left(\frac{m}{2} + \frac{n}{2}\right)$ is an integer as well. For all $z \in \mathbb{Z}$, $2z$ is even, thus $2\left(\frac{m}{2} + \frac{n}{2}\right)$ must be even.