3 Introducing the Contrapositive and Converse 29 Solutions to Exercises Solution (3.2).The equivalences are given below. (a)The negation may be stated as (PV-O)A(-PV-R),since -((PAO)V(PAR))(-(PAO)A-(PAR)) ((PV-0)A(-PV-R)) (b)The negation may be stated as PA(OV-R),since (P→(QAR)(PA(QAR) →(PA(QVR) Solution (3.5). (a)The contrapositive is"If n2-n-6 is odd,then n is even." (b)The converse is "If n2-n-6 is even,then n is odd." Solution (3.6). (a) PlQ-P→Q TT T TF T F FF T (b)The inverse of an implication is the converse of the contrapositive of the im- plication and this,in turn,is equivalent to the contrapositive of the converse of the implication. (c)The inverse of the implication P-o is equivalent to the converse of the implication P-O.To see this,compare the truth table of the inverse given in(a)with the truth table of the converse from page 27.They are the same and thus,by Theorem 2.7,the inverse is equivalent to the converse. Problems Problem 3.1.(a)Write a tautology involving only logical symbols,the implica- tion P-O,its converse,and Po. (b)Can you write a tautology involving only P-O and its contrapositive?If so, how?If not,why not? Problem#3.2.(a)Let x be an integer.Prove that if x is odd,then x2 is odd.Make sure you state your assumption as the first line and your conclusion as the last line
3 Introducing the Contrapositive and Converse 29 Solutions to Exercises Solution (3.2). The equivalences are given below. (a) The negation may be stated as (¬P∨ ¬Q)∧(¬P∨ ¬R), since ¬((P∧Q)∨(P∧R)) ↔ (¬(P∧Q)∧ ¬(P∧R)) ↔ ((¬P∨ ¬Q)∧(¬P∨ ¬R)). (b) The negation may be stated as P∧(¬Q∨ ¬R), since ¬(P → (Q∧R)) ↔ (P∧ ¬(Q∧R)) ↔ (P∧(¬Q∨ ¬R)). Solution (3.5). (a) The contrapositive is “If n2 −n−6 is odd, then n is even.” (b) The converse is “If n2 −n−6 is even, then n is odd.” Solution (3.6). (a) P Q ¬P → ¬Q T T T T F T F T F F F T (b) The inverse of an implication is the converse of the contrapositive of the implication and this, in turn, is equivalent to the contrapositive of the converse of the implication. (c) The inverse of the implication P → Q is equivalent to the converse of the implication P → Q. To see this, compare the truth table of the inverse given in (a) with the truth table of the converse from page 27. They are the same and thus, by Theorem 2.7, the inverse is equivalent to the converse. Problems Problem 3.1. (a) Write a tautology involving only logical symbols, the implication P → Q, its converse, and P ↔ Q. (b) Can you write a tautology involving only P → Q and its contrapositive? If so, how? If not, why not? Problem# 3.2. (a) Let x be an integer. Prove that if x is odd, then x2 is odd. Make sure you state your assumption as the first line and your conclusion as the last line
30 3 Introducing the Contrapositive and Converse (b)State the contrapositive of what you just proved. (c)Combining the result of part (a)with Theorem 3.3 gives a stronger result.Say precisely what that result is. Problem 3.3.For each of the following,write out the contrapositive and the con- verse of the sentence. (a)If you are the President of the United States,then you live in a white house. (b)If you are going to bake a souffle,then you need eggs. (c)If x is a real number,then x is an integer. (d)If x is a real number,thenx2<0. Problem 3.4.State the contrapositive of each of the following. (a)If it rains,then it pours. (b)If I had a bell,I would ring the bell in the morning. (c)The house is red,if the house is not blue. (d)Dinner is cooked only if I make it. Problem 3.5.State the converse of each of the following. (a)If it rains,then it pours. (b)If I am young,then I am restless. (c)I am alone,if it is Saturday. (d)I eat fish only if it is cooked. Problem 3.6.State the inverse of each of the following. (a)If it rains,then it pours. (b)If I am living abroad,then I need brownies. (c)To run quickly,it is sufficient to have long legs. (d)To make good chocolate chip cookies,it is necessary to have baking soda. Problem 3.7.Consider the statement form P-Q. (a)Write the negation of the converse of this statement form in as simple a form as possible. (b)Write the negation of the contrapositive of this statement form in as simple a form as possible. (c)Write the negation of the inverse of this statement form in as simple a form as possible. Problem 3.8.Consider the sentence:"The horses eat the grass only if they are led to the pasture..” (a)Write the negation of the converse of this sentence.Your answer has to be simple and as eloquent as possible. (b)Is the sentence in (a)the same as the converse of the negation of the original sentence?Explain your answer
30 3 Introducing the Contrapositive and Converse (b) State the contrapositive of what you just proved. (c) Combining the result of part (a) with Theorem 3.3 gives a stronger result. Say precisely what that result is. Problem 3.3. For each of the following, write out the contrapositive and the converse of the sentence. (a) If you are the President of the United States, then you live in a white house. (b) If you are going to bake a souffle, then you need eggs. ´ (c) If x is a real number, then x is an integer. (d) If x is a real number, then x2 < 0. Problem 3.4. State the contrapositive of each of the following. (a) If it rains, then it pours. (b) If I had a bell, I would ring the bell in the morning. (c) The house is red, if the house is not blue. (d) Dinner is cooked only if I make it. Problem 3.5. State the converse of each of the following. (a) If it rains, then it pours. (b) If I am young, then I am restless. (c) I am alone, if it is Saturday. (d) I eat fish only if it is cooked. Problem 3.6. State the inverse of each of the following. (a) If it rains, then it pours. (b) If I am living abroad, then I need brownies. (c) To run quickly, it is sufficient to have long legs. (d) To make good chocolate chip cookies, it is necessary to have baking soda. Problem 3.7. Consider the statement form P → Q. (a) Write the negation of the converse of this statement form in as simple a form as possible. (b) Write the negation of the contrapositive of this statement form in as simple a form as possible. (c) Write the negation of the inverse of this statement form in as simple a form as possible. Problem 3.8. Consider the sentence: “The horses eat the grass only if they are led to the pasture.” (a) Write the negation of the converse of this sentence. Your answer has to be simple and as eloquent as possible. (b) Is the sentence in (a) the same as the converse of the negation of the original sentence? Explain your answer
3 Introducing the Contrapositive and Converse 31 Problem 3.9.Let x and y be real numbers.Show that ifxy,then 2x+42y+4. (Hint:Use the contrapositive.) Problem 3.10.Matilda always eats at least one of the following for breakfast:ce- real,bread,or yogurt.On Monday,she is especially picky. If she eats cereal and bread,she also eats yogurt.If she eats bread or yogurt,she also eats cereal.She never eats both cereal and yogurt.She always eats bread or cereal. Can you say what Matilda eats on Monday?If so,what does she eat? Problem 3.11.Consider the following statement. If the coat is green,then the moon is full or the cow jumps over it. (a)This odd statement is composed of several substatements.Identify each sub- statement,assign a letter to it,and write down the original statement as a statement form using these letters and logical connectives. (b)Find the contrapositive of the original statement form from part(a).Use this to write the contrapositive of the original statement as an English sentence. (c)Find the converse of the original statement form from part (a).Use this to write the converse of the original statement as an English sentence. (d)Find the negation of the original statement form from part(a).Use this to write the negation of the original statement as an English sentence. (e)Are some of the statements in this problem (the original or the ones you ob- tained)equivalent?If so,which ones? Problem 3.12.Consider the two statement forms PO and P-(OVP). (a)Make a truth table for each of these statement forms. (b)What can you conclude from your solution to part (a)? Problem 3.13.Karl's favorite brownie recipe uses semisweet chocolate,very little flour,and less than 1/4 cup sugar.He has four recipes:one French,one Swiss, one German,and one American.Each of the four has at least two of the qualities Karl wants in a brownie recipe.Exactly three use very little flour,exactly three use semisweet chocolate,and exactly three use less than 1/4 cup sugar. The Swiss and the German recipes use different kinds of chocolate.The Amer- ican and the German recipes use the same amount of flour,but different kinds of chocolate.The French and the American recipes use the same amount of flour.The German and American recipes do not both use less than 1/4 cup sugar. Karl is very excited because one of these is his favorite recipe.Which one is it? Problem 3.14.Let n be an integer.Prove that if 3n is odd,then n is odd. Problem 3.15.Letx be a natural number.Prove that if x is odd,then v2x is not an integer. Problem 3.16.Let x and y be real numbers.Show that ifxy and x,y>0,then x2≠y2
3 Introducing the Contrapositive and Converse 31 Problem 3.9. Let x and y be real numbers. Show that if x 6= y, then 2x+4 6= 2y+4. (Hint: Use the contrapositive.) Problem 3.10. Matilda always eats at least one of the following for breakfast: cereal, bread, or yogurt. On Monday, she is especially picky. If she eats cereal and bread, she also eats yogurt. If she eats bread or yogurt, she also eats cereal. She never eats both cereal and yogurt. She always eats bread or cereal. Can you say what Matilda eats on Monday? If so, what does she eat? Problem 3.11. Consider the following statement. If the coat is green, then the moon is full or the cow jumps over it. (a) This odd statement is composed of several substatements. Identify each substatement, assign a letter to it, and write down the original statement as a statement form using these letters and logical connectives. (b) Find the contrapositive of the original statement form from part (a). Use this to write the contrapositive of the original statement as an English sentence. (c) Find the converse of the original statement form from part (a). Use this to write the converse of the original statement as an English sentence. (d) Find the negation of the original statement form from part (a). Use this to write the negation of the original statement as an English sentence. (e) Are some of the statements in this problem (the original or the ones you obtained) equivalent? If so, which ones? Problem 3.12. Consider the two statement forms P → Q and P → (Q∨ ¬P). (a) Make a truth table for each of these statement forms. (b) What can you conclude from your solution to part (a)? Problem 3.13. Karl’s favorite brownie recipe uses semisweet chocolate, very little flour, and less than 1/4 cup sugar. He has four recipes: one French, one Swiss, one German, and one American. Each of the four has at least two of the qualities Karl wants in a brownie recipe. Exactly three use very little flour, exactly three use semisweet chocolate, and exactly three use less than 1/4 cup sugar. The Swiss and the German recipes use different kinds of chocolate. The American and the German recipes use the same amount of flour, but different kinds of chocolate. The French and the American recipes use the same amount of flour. The German and American recipes do not both use less than 1/4 cup sugar. Karl is very excited because one of these is his favorite recipe. Which one is it? Problem 3.14. Let n be an integer. Prove that if 3n is odd, then n is odd. Problem 3.15. Let x be a natural number. Prove that if x is odd, then √ 2x is not an integer. Problem 3.16. Let x and y be real numbers. Show that if x 6= y and x, y ≥ 0, then x2 6= y2
32 3 Introducing the Contrapositive and Converse Problem 3.17.In the statement below,G is a group and H is a normal subgroup of G.(You need not know what“group,”“normal subgroup,”or"p-group”mean to do this problem!) "If H and G/H are p-groups,then G is a p-group." (a)State the converse of this statement. (b)State the contrapositive of this statement. (c)Consider the following:"G is a p-group if and only if H and G/H are p- groups."Write this in terms of your answers to the first two parts of this problem. Problem 3.18.Prove that if the product of two integers x and y is odd,then both integers are odd.Describe your method of proof. Problem 3.19.Consider the statement"If Simon takes German or French,then he cannot take Russian." (a)State the contrapositive of this implication. (b)State the converse of this implication. For parts (c)and (d),assume the original statement is true. (c)Suppose someone tells you that Simon did not take German.What,if any- thing,can you conclude about Simon?Why? (d)Suppose someone tells you that Simon took French.What,if anything,can you conclude about Simon?Why? Problem 3.20.Consider the statement form (PVO)(RAQ). (a)Write out the truth table for this form. (b)Make up a meaningful English statement that has this form. (c)Write the contrapositive of your English statement.Simplify the sentence as much as you can
32 3 Introducing the Contrapositive and Converse Problem 3.17. In the statement below, G is a group and H is a normal subgroup of G. (You need not know what “group,” “normal subgroup,” or “p-group” mean to do this problem!) “If H and G/H are p-groups, then G is a p-group.” (a) State the converse of this statement. (b) State the contrapositive of this statement. (c) Consider the following: “G is a p-group if and only if H and G/H are pgroups.” Write this in terms of your answers to the first two parts of this problem. Problem 3.18. Prove that if the product of two integers x and y is odd, then both integers are odd. Describe your method of proof. Problem 3.19. Consider the statement “If Simon takes German or French, then he cannot take Russian.” (a) State the contrapositive of this implication. (b) State the converse of this implication. For parts (c) and (d), assume the original statement is true. (c) Suppose someone tells you that Simon did not take German. What, if anything, can you conclude about Simon? Why? (d) Suppose someone tells you that Simon took French. What, if anything, can you conclude about Simon? Why? Problem 3.20. Consider the statement form (P∨ ¬Q) → (R∧Q). (a) Write out the truth table for this form. (b) Make up a meaningful English statement that has this form. (c) Write the contrapositive of your English statement. Simplify the sentence as much as you can
Chapter 4 Set Notation and Quantifiers Consider the sentence "The equation x2+2x=15 has a unique solution."Thus far, we've approached such things intuitively.It's time now to tackle this head on.Is it true?False?It depends on whichx we have in mind,of course.We turn to a rigorous way to make our sentencex2+2x=15 into a statement.But before we get to the heart of this chapter,it will be useful to have notation for the things with which we frequently work. We will need to understand the possible set of values that the variable x can assume.Now we will follow the point of view that many mathematicians follow: while we think of a set as a collection of objects,we will define neither set nor object.What we will do instead is to say,carefully and precisely,how these two words can be used and we do so with axiomatic statements.(The system most people use now,the Zermelo-Fraenkel system together with the axiom of choice,is stated in the Appendix for reference.We will say much more about sets in Chapter 6 and in subsequent chapters.)At this point we will concentrate on understanding the notation and commonly used symbols. We will write xEX to indicate that x is an element of X.(Some people read x∈Xas“x belongs to X,”others read it“x is an element of X.")Usually we will be considering things of a particular type.The set of all possible objects that are considered in the context in which we work is called the universe,which is also sometimes called the domain of discourse.We will usually denote the universe by X.In some cases the universe may consist of all real numbers,or it may consist of all right triangles;it might even consist of all cows living in France.The set may consist of all positive real numbers,all isosceles right triangles,or all white cows living in France.And the elements might be the real number a,the isosceles right triangle with legs of length 1,or Farmer Boursin's white cow Elsie,which lives in Dijon,France,and produces a mighty fine cheese.Some people even allow the universe to be the "set of all sets,"even though this universe is no set at all (see the Spotlight:Paradoxes on page 67). When it is clear,implicitly,what the universe is,we may not mention it explicitly. But when there is any doubt at all,we will carefully state what the universe is.Once we do that,we can denote a set by writing S=X:x satisfies P.The brackets U.Daepp and P.Gorkin,Reading.Writing.and Proving:A Closer Look at Mathematics, 33 Undergraduate Texts in Mathematics,DOI 10.1007/978-1-4419-9479-0_4, Springer Science+Business Media,LLC 2011
Chapter 4 Set Notation and Quantifiers Consider the sentence “The equation x2 +2x = 15 has a unique solution.” Thus far, we’ve approached such things intuitively. It’s time now to tackle this head on. Is it true? False? It depends on which x we have in mind, of course. We turn to a rigorous way to make our sentence x2 + 2x = 15 into a statement. But before we get to the heart of this chapter, it will be useful to have notation for the things with which we frequently work. We will need to understand the possible set of values that the variable x can assume. Now we will follow the point of view that many mathematicians follow: while we think of a set as a collection of objects, we will define neither set nor object. What we will do instead is to say, carefully and precisely, how these two words can be used and we do so with axiomatic statements. (The system most people use now, the Zermelo–Fraenkel system together with the axiom of choice, is stated in the Appendix for reference. We will say much more about sets in Chapter 6 and in subsequent chapters.) At this point we will concentrate on understanding the notation and commonly used symbols. We will write x ∈ X to indicate that x is an element of X. (Some people read x ∈ X as “x belongs to X,” others read it “x is an element of X.”) Usually we will be considering things of a particular type. The set of all possible objects that are considered in the context in which we work is called the universe, which is also sometimes called the domain of discourse. We will usually denote the universe by X. In some cases the universe may consist of all real numbers, or it may consist of all right triangles; it might even consist of all cows living in France. The set may consist of all positive real numbers, all isosceles right triangles, or all white cows living in France. And the elements might be the real number π, the isosceles right triangle with legs of length 1, or Farmer Boursin’s white cow Elsie, which lives in Dijon, France, and produces a mighty fine cheese. Some people even allow the universe to be the “set of all sets,” even though this universe is no set at all (see the Spotlight: Paradoxes on page 67). When it is clear, implicitly, what the universe is, we may not mention it explicitly. But when there is any doubt at all, we will carefully state what the universe is. Once we do that, we can denote a set by writing S = {x ∈ X : x satisfies P}. The brackets © Springer Science+Business Media, LLC 2011 U. Daepp and P. Gorkin, Reading, Writing, and Proving: A Closer Look at Mathematics, 33 Undergraduate Texts in Mathematics, DOI 10.1007/978-1-4419-9479-0_4