Is this a valid proof of "For all integers m and n, if mn is even, then m is even, or n is even"? Theorem: For all integers $m$ and $n$, if $mn$ is even, then $m$ is even, or $n$ is even.
Proof: Assume for all integers $m$ and $n$, if $mn$ is even, then $m$ is odd and $n$ is odd.
By the definition of odd, $m = 2k + 1$, and $n = 2r + 1$, where $k$ and $r$ are particular but arbitrary integers.
$mn = (2k + 1)(2r + 1)$
$= 4(kr)2 + 2k + 2r + 1$
$= 2((kr)2 + k + r) + 1$
Since $k$ and $r$ are integers, we can replace $(kr)2 + k + r$ with $p$, where $p$ is the integer value of $(kr)2 + k + r$.  By the definition of odd, $mn = 2(p) + 1$ is odd, which contradicts $mn$ is even.  Hence the supposition is false, therefore the theorem is true.
 A: No, this is not a valid proof. The underlying rule of logic you apply is that the negation of $\forall m\,\forall n\enspace (P\implies Q)$ is $\forall m\,\forall n\enspace (P\implies \neg Q)$, which is wrong: the negation is a counter-example, i.e. $\exists m\,\exists n\enspace(P\wedge( \neg Q))$.
The simplest proof would be by contrapositive, i.e. proving that if none of $m,n$ is even, then $mn$ can't be even.
A: The claim can be formalized as
$$
(\forall m\in \mathbb{Z})(\forall n\in \mathbb{Z})[mn \text{ is even} \to (m \text{ is even }) \lor (n \text{ is even})].
$$
To prove it start by assuming that $mn$ is even and that $m$ is not even (a number can either be even or odd but not both). Then there exists $k\in\mathbb{Z}$ s.t.
$m = 2k+1$
and so $mn = (2k+1)n$ is even.  Assume, for the sake of a contradiction that $n$ is odd, i.e. $n = 2k^\prime+1$ for some $k^\prime\in \mathbb{Z}$. Then
$$mn = (2k+1)(2k^\prime+1) = 4(kk^\prime) + 2k + 2k^\prime +1 = 2p+1,$$
with $p = 2(kk^\prime) + k + k^\prime$ an integer. But this contradicts the assumption that $mn$ is even, so $n$ must be even. Q.E.D.
