Investigate!26
Decide which of the following are valid proofs of the following statement.
If \(a b\) is an even number, then \(a\) or \(b\) is even.
-
Suppose \(a\) and \(b\) are odd. That is, \(a=2k+1\) and \(b=2m+1\) for some integers \(k\) and \(m\). Then
\begin{align*}
ab \amp =(2k+1)(2m+1)\\
\amp =4km+2k+2m+1\\
\amp =2(2km+k+m)+1.
\end{align*}
Therefore \(ab\) is odd.
-
Assume that \(a\) or \(b\) is even - say it is \(a\) (the case where \(b\) is even will be identical). That is, \(a=2k\) for some integer \(k\). Then
\begin{align*}
ab \amp =(2k)b\\
\amp =2(kb).
\end{align*}
Thus \(ab\) is even.
-
Suppose that \(ab\) is even but \(a\) and \(b\) are both odd. Namely, \(ab = 2n\), \(a=2k+1\) and \(b=2j+1\) for some integers \(n\), \(k\), and \(j\). Then
\begin{align*}
2n \amp =(2k+1)(2j+1)\\
2n \amp =4kj+2k+2j+1\\
n \amp = 2kj+k+j+\frac{1}{2}.
\end{align*}
But since \(2kj+k+j\) is an integer, this says that the integer \(n\) is equal to a non-integer, which is impossible.
-
Let \(ab\) be an even number, say \(ab=2n\), and \(a\) be an odd number, say \(a=2k+1\).
\begin{align*}
ab \amp =(2k+1)b\\
2n \amp =2kb+b\\
2n-2kb\amp =b\\
2(n-kb)\amp =b.
\end{align*}
Therefore \(b\) must be even.
When reading or writing a proof, or even just trying to understand a mathematical statement, it can be very helpful to rephrase the statement. But how do you know you are doing so correctly? How do you know the two statements are equivalent?
One way is to make a truth table for each and ensure that the final columns of both are identical. We saw earlier that \(P \imp Q\) is logically equivalent to \(\neg P \vee Q\) because their truth tables agreed. Now we can just remember this fact. If we see the statement, “if Sam is a man then Chris is a woman,” we can instead think of it as “Sam is a woman or Chris is a woman.” You might also be tempted to rephrase further: “Sam or Chris is a woman.” This is okay of course, but that this second rephrasing is allowed is due to the meaning of “is,” not any of our logical connectives.
Here are some common logical equivalences which can help rephrase mathematical statements:
Double Negation
\begin{equation*}
\neg \neg P \mbox{ is logically equivalent to } P.
\end{equation*}
Example: “It is not the case that \(c\) is not odd” means “\(c\) is odd.”
No surprise there. Now let's see how negation plays with conjunctions and disjunctions.
De Morgan's Laws
\begin{equation*}
\neg(P \wedge Q) \mbox{ is logically equivalent to } \neg P \vee \neg Q.
\end{equation*}
Example: “\(c\) is not even or \(c\) is not prime” means “\(c\) is not both odd and prime”
Do you believe De Morgan's laws? If not, make a truth table for each of them. I think most of us get these right most of the time without thinking about them too hard. If I told you that I had popcorn and goobers at the movies, but then you found out it was opposite day (so my statement was false) then you would agree, I hope, that I either did not have popcorn or did not have goobers (or didn't have either). You would not insist that I could not have had either.
I should warn you that often in English, we are sloppy about our and's, or's and not's. When you write about mathematics, you should be careful and write what you mean. If you are not sure what to write, rephrasing carefully using De Morgan's laws can help you make sure that statement matches your intended meaning.
Here are some rules for implications:
Negation of Implication
In words: The only way for an implication to be false is for the “if” part to be true and the “then” part to be false.
This is very important, and not obvious. Implications are tricky. Look again at the truth table for \(P \imp Q\):
| \(P\) |
\(Q\) |
\(P\imp Q\) |
|
|
|
| T |
T |
T |
| T |
F |
F |
| F |
T |
T |
| F |
F |
T |
There is only one way for the implication to be false: \(P\) is true and \(Q\) is false. Another way to see that this is true is by using De Morgan's Laws. We saw earlier that \(P \imp Q\) can be rephrased as \(\neg P \vee Q\) so we have
\begin{equation*}
\neg (P \imp Q) \mbox{ is logically equivalent to } \neg( \neg P \vee Q).
\end{equation*}
But by De Morgan's laws, \(\neg( \neg P \vee Q)\) is equivalent to \(\neg \neg P \wedge \neg Q\). By double negation \(\neg \neg P\) is the same as \(P\).
While we are thinking about implications, we should talk about the converse and contrapositive:
Converse and Contrapositive
A related, but lesser used, term is the inverse of an implication. The inverse of \(P \imp Q\) is \(\neg P \imp \neg Q\). Notice that the inverse of an implication is the contrapositive of the converse. Read that one more time. Good. Since implications and their contrapositives are logically equivalent, the inverse and converse of an implication are logically equivalent to each other, but not to the original implication.
1
Determine whether the following two statements are logically equivalent: \(\neg(P \imp Q)\) and \(P \wedge \neg Q\). Explain how you know you are correct.
2
Are the statements \(P \imp (Q\vee R)\) and \((P \imp Q) \vee (P \imp R)\) logically equivalent?
3
Simplify the following statements (so that negation only appears right before variables).
- \(\neg(P \imp \neg Q)\).
- \((\neg P \vee \neg Q) \imp \neg (\neg Q \wedge R)\).
- \(\neg((P \imp \neg Q) \vee \neg (R \wedge \neg R))\).
It is false that if Sam is not a man then Chris is a woman, and that Chris is not a woman.
