A question regarding contrapositive for implications

Question

I am slightly confused about the negation for an implication after encountering two questions as follows:

"Let P be the statement: If 3 is even, then 6 is even or divisible by 5. Write the negation and contrapositive":

The way I approached it was to think of it as follows as a negation of the implication and think of 3 'sub-statements (s,r,t) then $s \implies (r \vee t)$ where s is the statement that 3 is even, r is the statement that 6 is even, t is the statement that 6 is divisible by 5. Doing it my way would result in the contrapositive being: if 6 is odd and indivisible by 5, then 3 is odd. The negation would be 3 is even, and 6 is odd, and 6 is not divisible by 5.

This turned out to be inconsistent with the solution as it is given by the negation being: If 3 is even, and neither 6 is even nor divisible by 5. And the contrapositive of this statement is: If neither 6 is even nor divisible by 5, then 3 is odd.

However I then encountered another question given as follows:

"Let $x,y \in Z$. Prove that if $xy $ is odd, then $x$ and $y$ are odd."

To prove this question, I tried to use the contrapositive. Following the previous question, I thought that we were not supposed to negate the statement that $x$ and $y$ are odd.

Hence, I simply based the proof on the contrapositive as being if $x$ and $y$ are even, then $xy$ is even. However, this turned out to be incorrect as the proof considered 3 cases using contrapositive as follows:

1) $x$ is even

2) $x$ is odd, $y$ is even

3) $x$ is odd, and $y$ is odd

Hence, I am assuming that the contrapositive is the statement that $x \vee y$ is even.

So now I am a bit confused about the negation of an implication stated in words since the second question was consistent with my original way of thinking but the first was not. Could someone please help clarify ? Is it under the context of the first question such that it did not consider the negation of the "and" (but this was not mentioned in the second)?

I would greatly appreciate advice. Thank you

Answer 1

$\def\imp{\rightarrow}$Whoever wrote the 'solution' you ask about is wrong. The negation of a statement in first-order logic is always the statement that says exactly the opposite, so the negation of $p \imp q$ is always $p \land \neg q$.

But for your second example:

Take any $x,y \in \mathbb{Z}$. Prove that if $xy$ is odd, then $x$ and $y$ are odd.

Your contrapositive of the inner statement is wrong. It is of the form $p \imp q \land r$, which is equivalent to $\neg ( q \land r ) \imp \neg p$. If you distribute the negation over the conjunction, you get a disjunction. And the 'solution' is again nonsense. You only have two possible cases, namely "$x$ is even" and "$y$ is even".

Answer 2

The negation of of $p \rightarrow q$ is just $ p \wedge \neg q$

Thus the negation of $p\rightarrow(q \wedge r)$ is $p\wedge \neg (q \wedge r) $

In words this says that: The statement that it is false that $p$ implies that both $q$ and $r$ are true is equivalent to the statement that $p$ is true and one of $q$ and $r$ is false.

The contrapositive of an implication $ p \rightarrow q $ is the statement $\neg q \rightarrow \neg p $

Thus the contrapositive of $p\rightarrow(q \wedge r)$ is $\neg(q \wedge r)\rightarrow \neg p$

In words this says that if $p$ implies that both $q$ and $r$ are true is equivalent to the statement that one of $q$ and $r$ being false is implies that $p$ is false.

I recognise that I haven't addressed your question directly, but you can't go wrong if you use the definitions properly.