24 2 Logically Speaking (a)Suppose Arnie says,"If I am a truth-teller,then each person living on this island is a truth-teller or a liar."Can you say whether Arnie is a truth-teller or liar?If so,which one is he? (b)Suppose that Arnie had said,"If I am a truth-teller,then so is Barnie."Can you tell what Arnie and Barnie are?If so,what are they? Problem 2.17.Write a truth table for(PA(P-O))-Q.What can you conclude? Problem 2.18.Police at Small Unnamed University have received a report that a student was skateboarding in the hall.They rush to the scene of the crime to deter- mine who the guilty party is,and they are met by three students:Alan,Bernard,and Charlotte.When questioned,Alan says,"If Bernard did not do it,then it was Char- lotte."Bernard says,"Alan and Charlotte did it together or Charlotte did it alone," and Charlotte says,.“We all did it together..” (a)If the police know that exactly one person committed the crime,and exactly one person is lying,who is the guilty party? (b)As it turns out,exactly one person committed the crime and all the students are lying.Who is the guilty party? Problem 2.19.Show that if two statements,P and O,are equivalent,then their nega- tions,P and-0,are also equivalent. Problem 2.20.We know that each of the three statements below is correct.What can we conclude?Why? 1.If he was killed before noon,then his body temperature is at most 20C. 2.His body temperature is at most 20C and the police know who murdered him. 3.If the police know who murdered him,then he was killed before noon. Problem 2.21.We have been avoiding the use of "either...or"in this text because the English language uses this construction ambiguously and the interpretation often depends on the context.Consider the following two statements: l.“Either Peter or Paul ran in the race.” 2."You're either with us or against us." (a)Write the (intended)statement form for each of the two statements. (b)Give two more examples of the use of"either A or B"in the English language such that in the first of your examples both A and B occur,and in the second of your examples exactly one of A and B can occur. (c)The symbol V is sometimes used for the "exclusive disjunction";that is,a connective that yields a true statement if and only if exactly one of the two statements is true.Give an equivalent statement form of PVO using only the connectives introduced earlier in this text. (d)The negation"neither...nor"is interpreted exclusively as the negation of the regular disjunction in the English language.Give the truth table for the state- ment form"neither P nor O"and give a meaningful English statement that is in this form
24 2 Logically Speaking (a) Suppose Arnie says, “If I am a truth-teller, then each person living on this island is a truth-teller or a liar.” Can you say whether Arnie is a truth-teller or liar? If so, which one is he? (b) Suppose that Arnie had said, “If I am a truth-teller, then so is Barnie.” Can you tell what Arnie and Barnie are? If so, what are they? Problem 2.17. Write a truth table for (P∧(P → Q)) → Q. What can you conclude? Problem 2.18. Police at Small Unnamed University have received a report that a student was skateboarding in the hall. They rush to the scene of the crime to determine who the guilty party is, and they are met by three students: Alan, Bernard, and Charlotte. When questioned, Alan says, “If Bernard did not do it, then it was Charlotte.” Bernard says, “Alan and Charlotte did it together or Charlotte did it alone,” and Charlotte says, “We all did it together.” (a) If the police know that exactly one person committed the crime, and exactly one person is lying, who is the guilty party? (b) As it turns out, exactly one person committed the crime and all the students are lying. Who is the guilty party? Problem 2.19. Show that if two statements, P and Q, are equivalent, then their negations, ¬P and ¬Q, are also equivalent. Problem 2.20. We know that each of the three statements below is correct. What can we conclude? Why? 1. If he was killed before noon, then his body temperature is at most 20◦C. 2. His body temperature is at most 20◦C and the police know who murdered him. 3. If the police know who murdered him, then he was killed before noon. Problem 2.21. We have been avoiding the use of “either...or” in this text because the English language uses this construction ambiguously and the interpretation often depends on the context. Consider the following two statements: 1. “Either Peter or Paul ran in the race.” 2. “You’re either with us or against us.” (a) Write the (intended) statement form for each of the two statements. (b) Give two more examples of the use of “either A or B” in the English language such that in the first of your examples both A and B occur, and in the second of your examples exactly one of A and B can occur. (c) The symbol ∨˙ is sometimes used for the “exclusive disjunction”; that is, a connective that yields a true statement if and only if exactly one of the two statements is true. Give an equivalent statement form of P∨˙ Q using only the connectives introduced earlier in this text. (d) The negation “neither...nor” is interpreted exclusively as the negation of the regular disjunction in the English language. Give the truth table for the statement form “neither P nor Q” and give a meaningful English statement that is in this form
Chapter 3 Introducing the Contrapositive and Converse In the last chapter (see Theorem 2.7)we saw that two statement forms,P and O,that have the same truth table are equivalent.This was also expressed by showing that the equivalence,P+O,is a tautology.When you are confronted with a mathematical statement that you need to prove,you will often find it helpful to paraphrase it.You will use tautologies to do so,since you don't want to change the truth value of your statement.Some useful tautologies appeared in Theorem 2.9.More appear below and throughout this chapter. Theorem 3.1.Let P.O,and R denote statement forms.Then the following are tau- tologies: (Distributive property) (PA(OVR))((PAO)V(PAR)): (PV(OAR))((PVO)A(PVR)): (Associative property) (PA(OAR)((PAO)AR): (PV(OVR))((PVO)VR); (Commutative property)(PAO)(OAP): (PVQ)→(QVP). At this point,you should be able to construct the truth tables for everything above and you should be able to show that all of them are tautologies. Exercise 3.2.Negate the following: (a)(PAQ)V(PAR); b)P→(QAR) Tautologies allow us to replace one statement by another.For example,suppose you want to show that an integer is odd or prime.You can show that the integer is prime or odd;that won't change things because these two statements are equivalent. U.Daepp and P.Gorkin,Reading.Writing.and Proving:A Closer Look at Mathematics, 25 Undergraduate Texts in Mathematics,DOI 10.1007/978-1-4419-9479-0_3, Springer Science+Business Media,LLC 2011
Chapter 3 Introducing the Contrapositive and Converse In the last chapter (see Theorem 2.7) we saw that two statement forms, P and Q, that have the same truth table are equivalent. This was also expressed by showing that the equivalence, P ↔ Q, is a tautology. When you are confronted with a mathematical statement that you need to prove, you will often find it helpful to paraphrase it. You will use tautologies to do so, since you don’t want to change the truth value of your statement. Some useful tautologies appeared in Theorem 2.9. More appear below and throughout this chapter. Theorem 3.1. Let P,Q, and R denote statement forms. Then the following are tautologies: (Distributive property) (P∧(Q∨R)) ↔ ((P∧Q)∨(P∧R)); (P∨(Q∧R)) ↔ ((P∨Q)∧(P∨R)); (Associative property) (P∧(Q∧R)) ↔ ((P∧Q)∧R); (P∨(Q∨R)) ↔ ((P∨Q)∨R); (Commutative property) (P∧Q) ↔ (Q∧P); (P∨Q) ↔ (Q∨P). At this point, you should be able to construct the truth tables for everything above and you should be able to show that all of them are tautologies. Exercise 3.2. Negate the following: (a) (P∧Q)∨(P∧R); (b) P → (Q∧R). Tautologies allow us to replace one statement by another. For example, suppose you want to show that an integer is odd or prime. You can show that the integer is prime or odd; that won’t change things because these two statements are equivalent. © Springer Science+Business Media, LLC 2011 U. Daepp and P. Gorkin, Reading, Writing, and Proving: A Closer Look at Mathematics, 25 Undergraduate Texts in Mathematics, DOI 10.1007/978-1-4419-9479-0_3
26 3 Introducing the Contrapositive and Converse This is a fairly obvious change that usually won't make much of a difference.The same holds if you want to show x is prime and odd;you can show that it is odd and prime if that's easier and you will have accomplished the same thing.Similarly,if you want to show that it is not the case that x is prime and odd,you can show thatx is not prime or not odd. For implications,restating what you want to prove can really make a difference. We need to make sure,however,that what we have is equivalent to our original statement.So recall that we showed,in the last chapter,that P-O is equivalent to -PVO. Now consider0-P,which is called the contrapositive of the implication P-O.We need to compare the two truth tables below: PQP→Q P|QQ→-P TTT TT 分 TFF TF F FT T FT T FF 2 FF 2 So the fact that the truth tables are the same and Theorem 2.7 tell us that the statement forms are logically equivalent.What this means to us is that,if we are trying to prove that an implication is true and we don't see how to do it,we should consider the contrapositive of that statement.Here's how it works in practice. Theorem 3.3.Letx be an integer.If x2 is odd,then x is odd. First we need to understand the problem.What does it mean for a numberx to be odd?Our definition of "odd number"is the following:An integer x is odd if there is an integer n such that x=2n+1.So we are assuming that x2=2n+1 for some integer n and trying to show x =2m+1 for some integer m.It's hard to see where to go from here,we think. Remember that Polya suggests restating the problem,so let's try that.Let P be the sentence"x2 is odd"and o be the sentence"x is odd."Then we see that we wish to prove that Po is true.But this is logically equivalent to0-P,which translates into"Ifx is not odd,then x2 is not odd."We can do better than that,since an integer is odd or even.So we can show that"If x is even,then x2 is even"and that will be equivalent.Let's see if that's easier. Theorem (Contrapositive of the statement of Theorem 3.3).Let x be an integer.If x is even,then x2 is even. The first step is to understand the problem.The second step is to prove it.We'll do that here: "Understanding the problem."When is an integer even?Our definition of "even number"is the following:An integer x is even if there is an integer n such that x=2n.So we need to show thatx=2m,where m is an integer,assuming that x=2n,where n is an integer.We began by understanding the problem,now we are ready to solve it
26 3 Introducing the Contrapositive and Converse This is a fairly obvious change that usually won’t make much of a difference. The same holds if you want to show x is prime and odd; you can show that it is odd and prime if that’s easier and you will have accomplished the same thing. Similarly, if you want to show that it is not the case that x is prime and odd, you can show that x is not prime or not odd. For implications, restating what you want to prove can really make a difference. We need to make sure, however, that what we have is equivalent to our original statement. So recall that we showed, in the last chapter, that P → Q is equivalent to ¬P∨Q. Now consider ¬Q → ¬P, which is called the contrapositive of the implication P → Q. We need to compare the two truth tables below: P Q P → Q T T T T F F F T T F F T P Q ¬Q → ¬P T T T T F F F T T F F T So the fact that the truth tables are the same and Theorem 2.7 tell us that the statement forms are logically equivalent. What this means to us is that, if we are trying to prove that an implication is true and we don’t see how to do it, we should consider the contrapositive of that statement. Here’s how it works in practice. Theorem 3.3. Let x be an integer. If x2 is odd, then x is odd. First we need to understand the problem. What does it mean for a number x to be odd? Our definition of “odd number” is the following: An integer x is odd if there is an integer n such that x = 2n+1. So we are assuming that x2 = 2n+1 for some integer n and trying to show x = 2m+1 for some integer m. It’s hard to see where to go from here, we think. Remember that Polya suggests restating the problem, so let’s try that. Let ´ P be the sentence “x2 is odd” and Q be the sentence “x is odd.” Then we see that we wish to prove that P → Q is true. But this is logically equivalent to ¬Q → ¬P, which translates into “If x is not odd, then x2 is not odd.” We can do better than that, since an integer is odd or even. So we can show that “If x is even, then x2 is even” and that will be equivalent. Let’s see if that’s easier. Theorem (Contrapositive of the statement of Theorem 3.3). Let x be an integer. If x is even, then x2 is even. The first step is to understand the problem. The second step is to prove it. We’ll do that here: “Understanding the problem.” When is an integer even? Our definition of “even number” is the following: An integer x is even if there is an integer n such that x = 2n. So we need to show that x2 = 2m, where m is an integer, assuming that x = 2n, where n is an integer. We began by understanding the problem, now we are ready to solve it
3 Introducing the Contrapositive and Converse 27 Proof.Let x be even.Then there is an integer n such that x=2n.Therefore,x2 =(2n)2=2(2n2).Let m 2n2.Then x2=2m and m is an integer.Therefore x2 is even. 0 Of course,this takes care of the original theorem,since it is equivalent to the one we proved.Thus,using the contrapositive is one possible way to attempt to prove that an implication is true.We will soon have a number of ways to attack a problem. Try to keep them all in mind. Some other related remarks:Notation is more important than it may seem.In the theorem above,we assume that x is even and try to showx2 is even.If we assume thatx=2n and accidentally try to show x2=2n (rather than x2=2m),we're stuck because we assumed erroneously thatx=x2.In other words,our notation would force us to show that x=0 orx=1,which is not what we should be doing.We introduced an error because of poor notation.So it's important that one symbol be an n and one be an m. Also,note that we begin the proof by saying what we are assuming,and end the proof by saying what we are concluding.That helps the reader too.Finally,we keep checking that m and n are integers.That's because that is very important;if they weren't integers,x wouldn't have to be even. So the contrapositive was very helpful here.You do need to be careful though. It must be the contrapositive and not the converse.The converse of an implication P-O is the statement form -P.Looking at the truth tables for each of these given below, PQP→Q PQQ→P TT T TT■ T T F and TF T F T T FT F FF T FF T we see that they are different.Unfortunately,though the contrapositive and converse of a statement are really very different,students often confuse them.We'll take just a moment to convince you that it is very important not to do this. Suppose our statement is,"If I am a Hobbit,then I am under 5 feet tall."This is a true statement,as every Tolkien reader knows.The converse is "If I am under 5 feet tall,then I am a Hobbit."This latter statement is not true,since lots of children are under 5 feet tall,but most of them are not Hobbits.As a mathematical example, consider the sentence about integers"Ifx is seven,then x is prime,"and its converse "If x is prime,then x is seven."Recall that an integer p is prime if p >I and p cannot be written as a product of two positive integers,both different from p.Thus, the original sentence is true for all x,while the converse above is not.On the other hand,you agree that for all x the contrapositive "If x is not prime,then x is not seven,"is true,as it must be.But this is trickier when we don't really understand what we are saying as well as we understand this statement.Remember,make sure you understand the problem.We present some examples and exercises for you to try your hand at
3 Introducing the Contrapositive and Converse 27 Proof. Let x be even. Then there is an integer n such that x = 2n. Therefore, x2 = (2n)2 = 2(2n2). Let m = 2n2. Then x2 = 2m and m is an integer. Therefore x2 is even. ut Of course, this takes care of the original theorem, since it is equivalent to the one we proved. Thus, using the contrapositive is one possible way to attempt to prove that an implication is true. We will soon have a number of ways to attack a problem. Try to keep them all in mind. Some other related remarks: Notation is more important than it may seem. In the theorem above, we assume that x is even and try to show x2 is even. If we assume that x = 2n and accidentally try to show x2 = 2n (rather than x2 = 2m), we’re stuck because we assumed erroneously that x = x2. In other words, our notation would force us to show that x = 0 or x = 1, which is not what we should be doing. We introduced an error because of poor notation. So it’s important that one symbol be an n and one be an m. Also, note that we begin the proof by saying what we are assuming, and end the proof by saying what we are concluding. That helps the reader too. Finally, we keep checking that m and n are integers. That’s because that is very important; if they weren’t integers, x wouldn’t have to be even. So the contrapositive was very helpful here. You do need to be careful though. It must be the contrapositive and not the converse. The converse of an implication P → Q is the statement form Q → P. Looking at the truth tables for each of these given below, P Q P → Q T T T T F F F T T F F T and P Q Q → P T T T T F T F T F F F T we see that they are different. Unfortunately, though the contrapositive and converse of a statement are really very different, students often confuse them. We’ll take just a moment to convince you that it is very important not to do this. Suppose our statement is, “If I am a Hobbit, then I am under 5 feet tall.” This is a true statement, as every Tolkien reader knows. The converse is “If I am under 5 feet tall, then I am a Hobbit.” This latter statement is not true, since lots of children are under 5 feet tall, but most of them are not Hobbits. As a mathematical example, consider the sentence about integers “If x is seven, then x is prime,” and its converse “If x is prime, then x is seven.” Recall that an integer p is prime if p > 1 and p cannot be written as a product of two positive integers, both different from p. Thus, the original sentence is true for all x, while the converse above is not. On the other hand, you agree that for all x the contrapositive “If x is not prime, then x is not seven,” is true, as it must be. But this is trickier when we don’t really understand what we are saying as well as we understand this statement. Remember, make sure you understand the problem. We present some examples and exercises for you to try your hand at
28 3 Introducing the Contrapositive and Converse Example 3.4.Consider the slightly odd sentence:"If the sky is green,then 2+2 =4."What are the converse and the contrapositive of this implication?Which of the following (if any)is true:the statement,the converse,or the contrapositive? The converse is:"If 2+2=4,then the sky is green."The contrapositive is:"If 2+2≠4，then the sky is not green.” To decide on the validity of the statements we have to agree on the truth of each part.We are quite confident that 2+2=4,so this part is true.We abbreviate the statement with A (for arithmetic).Since we have never seen a(natural)green sky before,we suggest that"the sky is green,"abbreviated by S,should be considered as false.With this in place,we look at the relevant parts of the truth tables. SAS→AA→S-A→-S FTTFT So the original statement and its contrapositive are true,while the converse is false. Of course we knew beforehand that the original statement and the contrapositive would have the same answer because they are equivalent statements. O Now it's your turn. Exercise 3.5.Consider the sentence "If n is odd,then n2-n-6 is even." (a)State the contrapositive. (b)State the converse. O We should also mention one more possibility that comes up frequently:the in- verse of an implication PO is the statement formP-.As you will show in the exercise below,this form is nothing new.The inverse of an implication can be expressed in terms of our earlier definitions. Exercise 3.6.Consider the implication P-O. (a)Write the truth table for the inverse of P-O. (b)Express the inverse of an implication in terms of the converse and contrapos- itive in two different ways. (c)State the relation between the inverse of P-O and the converse of P-O. and give a reason for your answer. O Definitions Definition 3.1.An integer x is odd if there is an integer n such that x=2n+1. Definition 3.2.An integer x is even if there is an integer n such that x=2n Definition 3.3.An integer p is prime if p>1 and p cannot be written as a product of two positive integers,both different from p
28 3 Introducing the Contrapositive and Converse Example 3.4. Consider the slightly odd sentence: “If the sky is green, then 2 + 2 = 4.” What are the converse and the contrapositive of this implication? Which of the following (if any) is true: the statement, the converse, or the contrapositive? The converse is: “If 2+2 = 4, then the sky is green.” The contrapositive is: “If 2+2 6= 4, then the sky is not green.” To decide on the validity of the statements we have to agree on the truth of each part. We are quite confident that 2 + 2 = 4, so this part is true. We abbreviate the statement with A (for arithmetic). Since we have never seen a (natural) green sky before, we suggest that “the sky is green,” abbreviated by S, should be considered as false. With this in place, we look at the relevant parts of the truth tables. S A S → A A → S ¬A → ¬S F T T F T So the original statement and its contrapositive are true, while the converse is false. Of course we knew beforehand that the original statement and the contrapositive would have the same answer because they are equivalent statements. Now it’s your turn. Exercise 3.5. Consider the sentence “If n is odd, then n2 −n−6 is even.” (a) State the contrapositive. (b) State the converse. We should also mention one more possibility that comes up frequently: the inverse of an implication P → Q is the statement form ¬P → ¬Q. As you will show in the exercise below, this form is nothing new. The inverse of an implication can be expressed in terms of our earlier definitions. Exercise 3.6. Consider the implication P → Q. (a) Write the truth table for the inverse of P → Q. (b) Express the inverse of an implication in terms of the converse and contrapositive in two different ways. (c) State the relation between the inverse of P → Q and the converse of P → Q, and give a reason for your answer. Definitions Definition 3.1. An integer x is odd if there is an integer n such that x = 2n+1. Definition 3.2. An integer x is even if there is an integer n such that x = 2n. Definition 3.3. An integer p is prime if p > 1 and p cannot be written as a product of two positive integers, both different from p