Contrary logic
Can you invert the logic to prove these statements?
Age
16 to 18
Challenge level
Problem
This problem is in two parts. The first uses logic in the context of English language whereas the second uses logic in the clearer context of mathematics
Part 1. Which of the following are certainly true, which are certainly false. How many statements form equivalent pairs? Are there any parts of the problem which are debatable or unclear?
If my team wins the world cup tomorrow then I'll be happy
tomorrow.
If I am happy tomorrow then my team will win the world cup
tomorrow.
If I am not happy tomorrow then my team will not win the world
cup tomorrow.
If my team does not win the world cup tomorrow then I will not
be happy tomorrow.
If this is maize then it grew from a seed
If this grew from a seed then it is maize
If this did not grow from a seed then it is not maize
If this is not maize then it did not grow from a seed
If Rover is a dog then Rover is an animal
If Rover is not an animal then Rover is not a dog
If Rover is not a dog then Rover is an animal
If Rover is an animal then Rover is a dog
These ideas will help you to understand part 2.
Part 2. In mathematical logic the implication arrows $\Rightarrow$ and $\Leftrightarrow$ are used to connect expressions as follows:
$p\Rightarrow q$ means 'IF $p$ is true THEN $q$ is true.
$p\Leftrightarrow q$ means both $p\Rightarrow q$ AND $q \Rightarrow p$ simultaneously.
Convince yourself that
$$
\left(p\Rightarrow q\right) \Leftrightarrow \left((NOT q) \Rightarrow (NOT p)\right)
$$
The expression on the right is called the contrapositive of the statement on the left. Since they are linked by $\Leftrightarrow$, proving one side will automatically prove the other.
Consider these statements involving positive integers $n$ and $m$.
1: $n+m$ is odd $\Rightarrow n\neq m$.
2: $n+m$ is even $\Rightarrow$ $n$ and $m$ are either both even or both odd
3: $n^2$ is even $\Rightarrow n$ is even.
4: $n^3$ is odd $\Rightarrow n$ is odd.
5: $n$ mod (4) = 2 or 3 $\Rightarrow$ $n$ is not a perfect square.
Write out the contrapositive versions of these statements and use these to prove the statements. You can assume that an even number can be written as $2N$ and an odd number as $2M+1$.
Getting Started
With this question, you need to work through each piece slowly and
carefully. Take your time to understand the symbols and say the
equations out loud.
Student Solutions
We got two great solutions from Alex, from Stoke-on-Trent Sixth Form College and Jamie from the Omagh Academy. The solution here is a combination of their responses
To begin, Alex formally split the worded statements into their correct logical expressions and correctly noted that several pairs were logically equivalent
Let p represent my team winning the world cup tomorrow, and q represent my happiness tomorrow. The statements can be written in terms of p and q as follows:
p => q
q => p
(NOT q) => (NOT p)
(NOT p) => (NOT q)
The first and third statements are logically identical, as are the second and fourth, by the logical rule in part 2 of the question. If p represented the object being maize, and q represent it having grown from a seed then the same relationship between the statements would apply: they are again logically identical.
If p represents that Rover is a dog, and q represents that Rover is an animal then the statements can be written in terms of p and q as follows:
p => q
(NOT q) => (NOT p)
(NOT p) => q
q => p
The first and second statements are logically equivalent identical, the same as with the world cup and maize parts.
Jamie gave us an excellent discussion on whether the statements were, or were not, true or false. Jamie quite rightly noted that the statements were not really clear enough to be declared True or False and, rather nicely, suggested ways in which the statements could be altered to make more sense
If my team wins the world cup tomorrow then I'll be happy tomorrow.
This statement is unclear or debatable, since although his team winning the world cup tomorrow may make him happy, something else could happen which may make him unhappy: some event may befall him. It is unsound because he does not know what tomorrow will bring.
If my team does not win the world cup tomorrow then I will not be happy tomorrow.
This statement is the contrapositive argument of the above statement, and is also debatable for the same reason, that something may happen tomorrow that may make him happy, yet he assumes he will be entirely sad if his team loses.
If I am happy tomorrow then my team will win the world cup tomorrow
Ths statement is false because it is saying that the man's happiness tomorrow is a necessary and sufficient condition for his team to win the world cup, despite the fact that his happiness has no plausible effect on the outcome of the match.
If I am not happy tomorrow then my team will not win the world cup tomorrow
Again this statement is false as it is saying that the man's happiness tomorrow is a necessary and sufficient condition for his team to win the world cup. It forms a pair with the previous statement.
If this is maize then it grew from a seed
This is true since maize must grow from a seed it is a plant, and all plants grow from a seed. Otherwise, if it did not grow from a seed, it cannot be maize, so the next statement (if this did not grow from a seed then it is not maize ) must also be true, and so they form an equivalent pair.
If this grew from a seed then it is maize
This is not true: although maize grows from a seed, it is possible that it could be any other plant that also grows from a seed. A true statement would be 'If this grew from a seed, then it could be maize.'
If this is not maize then it did not grow from a seed
This is false, since it could be any other plant that does grow from a seed.
If Rover is a dog then Rover is an animal
This statement is true since all dogs are animals.
If Rover is not an animal then Rover is not a dog
This statement is also true since all dogs are animals, so if Rover is not an animal, Rover cannot be a dog. This statement goes along with the previous statement, since they both work on the fact that all dogs are animals.
If Rover is not a dog then Rover is an animal
This statement is false: saying that Rover is not a dog is equivalent to saying that Rover could be anything apart from a dog; since not everything is an animal, the statement is false.(Editor: I love this answer!)
If Rover is an animal then Rover is a dog
This is false since clearly not all animals are dogs. A true statement would be 'If Rover is an animal, then Rover could be a dog'.
It has been noted that it might be possible to argue very pedantically against all of these statements. This is because they are phrased in English language with all of its vagueness and imprecision. The world cup statement clearly only makes sense 'conversationally' and brings to bear ideas that in usual language statements are neither entirely true nor entirely false. Even the second and third sets of statements are subject to some debate: Although several of the staments might be very likely to be true or false, perhaps they might be false for the following, albeit improbable reasons :
What if the maize were grown in a lab as a clone?
What if maize were a girl's name?
What if Rover is the name of a play, and the word 'dog' used in the slang sense to refer to something worthless or of extremely poor quality?
Jamie and Alex both went on to give great answers to the mathematically sound second part, demonstrating the clarity of sound logical thinking so important to mathematicians
1. $ (n+m)\mbox{ odd}\Rightarrow n\neq m$
The negation of $n+m$ odd is $n+m$ even and the negation of $n\neq m$ is $n=m$, so the first contrapositive statement is
$$ n=m\Rightarrow (n+m)\mbox{ even}$$
To prove this, note that when $n=m$, $n+m$ is equivalent to $2n$, which is even. This proves the contrapositive statement, so the initial statement must also be true.
2.$(n+m)\mbox{ even}\Rightarrow n \mbox{ and } m \mbox{ are either both even or both odd}$
The negation of ($n$ and $m$ are either both even or both odd) is (one of $n$ and $m$ is even, and the other odd), so the contrapositive statement is
$$(\mbox{one of } n \mbox{ and } m \mbox{ is even, and the other odd})\Rightarrow (n+m) \mbox{ is odd}$$
To prove this, write the even integer as $2N$, and the odd one as $2M+1$, so that their sum is $2N+2M+1 = 2(N+M)+1$. This is odd, and the statement is therefore proved.
3. $n^2$ is even $\Rightarrow n$ is even.
The contrapositive of this statement is ($n$ odd $\Rightarrow n^2$ odd)
To prove this assume that $n$ is odd so that $n = 2M+1$. Then $n^2 = (2M+1)^2 = 4M^2+4M+1$, which is odd. This proves the result.
4. $n^3$ is odd $\Rightarrow n$ is odd.
The contrapositive of this statement is ($n$ even $\Rightarrow n^3$ even)
To prove this assume that $n$ is even so that $n=2N$. Then $n^3=8N$ which is even. So the result is proved.
5. $n \mbox{ mod }(4) = 2 \mbox{ or } 3 \Rightarrow n$ is not a perfect square.
The contrapositive of this is
($n$ is a perfect square $\Rightarrow n \mbox{ mod }(4) = 0 \mbox{ or } 1$)
To prove this start by noting that since $n$ is a perfect square, its square root is a whole number. So, $\sqrt{n}$ is either even or odd, and so one of $2N$ or $2M+1$. The square of $2N$ is $4N^2$, which is congruent to $0 \mbox{ mod }4$. The square of $2M+1$ is $4(M^2 + M)+1$, which is congruent to $1 \mbox{ \mod }4$. Therefore $n$ is congruent to $(0 \mbox{ mod }4)$ or $(1 \mbox{ mod }4)$. This proves the result.
Teachers' Resources
Why do this problem?
This problem takes students' logical thinking one step beyond the logical thinking required to follow direct proofs. It will sharpen their understanding of proof and mathematical thinking to a level beyond that normally required in school mathematics, albeit in a simple context.Possible approach
The first part of the problem works very well as a group
discussion. Initially students might automatically decide that
certain of the statements are true or false. But are they
absolutely true or
absolutely false ? The
discussion should lead the group to understand that the statements
are mathematically vague, unclear or depend on a personal opinion.
Thus, although in normal everday language the statements would
typically be considered unambiguous, mathematically they are
unacceptable.
Despite their logical vagueness, the statements are useful to
understand the concept of the contrapositive: that a statement
$A\Rightarrow B$ is equivalent to the statement $NOT(B)\Rightarrow
NOT(A)$.
Of course, to understand these statements, students will
really need to understand the meaning of the implication arrows
$\Rightarrow$ and $\Leftrightarrow$. A good activitiy is to try to
get students to explain really clearly these concepts to each
other. Holes in understanding will soon become apparent.
Once students grasp thes points, they can move onto the
clearer, more formal mathematics in the second part of the
question.
A final, powerful part of this activity is that students
should try to explain their results to each other in words. This is
a really good device for sharpening up mathematical thinking. Can
students explain the contrapositive to the class? Do listeners
think that their explanation is clear and simple? Can they explain
their proofs in the same way?
Don't forget to marvel at the beautiful simplicity of the
contrapositive once the results have been proved!
Key questions
Why might these statements be unclear? How might we make them
clear?
Do you understand the meaning of the arrows exactly?
Can you explain your proofs clearly to an audience?
Possible extension
Can students create other mathematical statements which can be
proved by contrapositive?
Can students create other sets of logical statements as in the
first part of the question to test out on their peers?
Possible support
It is best first to tackle IFFY
logic before attempting this question.
Students having difficulty with creating the proofs might
benefit from being the 'critical audience' to students who can
construct the proofs. Can the solvers convince the audience of
their results? Once those having difficulty have heard a couple of
proofs, they might more clearly see the way to creating their own
proofs.