Proofs Homework Set 1 - Mathematics | U-M LSA

1 Proofs Homework Set 1 MATH217 WINTER2011 Due January 12 Logical mathematical statement is either true or false. Starting from givenmathematical statements, we can use logical operations to form new mathematical statementswhich are again either true or false. LetPandQbe two statements. Here are the four basiclogical constructions: The statement PandQ is true if bothPandQare true statements. The statement PorQ is true if at least one ofPorQis true. The statement ifPthenQ is true if bothPandQare true, or ifPis false. The shorthandnotation for ifPthenQ isP= Q.

2 The statement Pif and only ifQ is true whenever bothP= QandQ= Pare truestatements. The shorthand notation for Pif and only ifQ isP whether the following statements are true or false. Justify your answers.(a) If9>5, then pigs don t ; the statements 9>5 and pigs don t fly are both true.(b) Ifx >0andx2<0, thenx ; the statement x2<0 is false, hence so is x >0andx2<0. (c) Ifx >0, thenx2<0orx3> Since x2<0is false, the statement x2<0orx3>0 is true precisely when x >0 is true.(d) If1 = 2, thenModern Familyis the best sitcom on ; the statement 1 = 2 is false.

3 (e)x >0if and only if2x > The statements x >0 = 2x >0 and 2x >0 = x >0 are both true.(f) Chickens have feathers if and only if2is not an Since chickens have feathers is true and 2is not an integer is false, thestatement if chickens have feathers then2is not an integer is a statementPis a statement that is true wheneverPis false and falsewheneverPis true. The negation ofPis denoted not P. For example, the negation of thestatement If it is raining, then it is cloudy is the statement It is raining, and it is not cloudy. These statements can never be true the negation of each of the statements below.

4 (a) The setScontains at least two negation is the setScontains at most one integer. (b) I wear glasses, or I can t read the negation is I don t wear glasses and I can read the chalkboard. Consider the following table of possible combinations:wear glassescan read chalkboarddon t wear glassescan read chalkboardwear glassescan t read chalkboarddon t wear glassescan t read chalkboardThe original statement covers the first, third and fourth lines (that is, at least one of I wearglasses and I can t read the chalkboard is true). Therefore the negation is the second line.

5 (c) I like cats and I dislike negation is I dislike cats or I like dogs. catsdogslikelikelikedislikedislikelikedi slikedislikeThe original statement covers only the second option, so its negation should cover the otherthree options.(d) If you study hard, then you will do well in this negation is you study hard and you won t do well in this class. (e) There is a student in class who will negation is every student in class will pass. (f) For every problem there is a negation is there is a problem with no solution. (g) There is a real number which is larger than every rational negation is no real number is larger than every rational number.

6 Converse and are two additional logical statements that can be formedfrom a given if-then statement: Theconverseof the statementP= Qis the statementQ= P. The converse may be trueor false, independent of the truth value of the original if-then statement. Why? the truth tables for both statements:PQP= QQ= PTTTTTFFTFTTFFFTTThe last two columns do not coincide. Thecontrapositiveof the statementP= Qis the statementnot Q= not P. Theoriginal if-then statement and its contrapositive have thesametruth value. Why? the truth tables for both statements:PQP= Qnot Qnot Pnot Q= not PTTTFFTTFFTFFFTTFTTFFTTTTThe columns corresponding toP= Qandnot Q= not both the converse and the contrapositive of the following four if-then statements.

7 (a) If9>5, then pigs don t Converse:If pigs don t fly, then9> :If pigs fly, then9 5.(b) Ifx >0andx2<0, thenx Converse:Ifx 1, thenx >0orx2< :Ifx > 1, thenx 0andx2 0.(c) Ifx >0, thenx2<0orx3> Converse:Ifx2<0orx3>0, thenx > :Ifx2 0andx3 0, thenx 0.(d) If1 = 2, thenModern Familyis the best sitcom on Converse:IfModern Familyis the best sitcom on television, then1 = :IfModern Familyis not the best sitcom on television., then16= a container with no distinguishing feature other than its contents. The objectscontained in a set are called theelementsof the set.

8 We writea Sto signify that the objectaisan element of the a set has no distinguishing feature other than its contents, there is a unique set containingno elements which is called theempty setand is denoted . Some other very common sets are thesetRof all real numbers, the setQof all rational numbers, the setZof all integers, and the setCof all complex numbers (which we will properly define later in the course).There are two important ways to specify a set. can list the contents of the set, in which case the set is denoted byenclosing the list in curly braces.

9 For example,Z={.. , 2, 1,0,1,2, ..}. can describe the contents of the set by a property of its (a)is a property of the objecta, then the set of all objectsasuch thatP(a)is true isdenoted by{a|P(a)}. For example,Q={ab|a, b Zandb6= 0}.LetXandSbe sets. We say thatSis asubsetofXifa S= a Xholds for all objectsa. We writeS Xto signify thatSis a subset ofX. This means thatSis a set consisting of someor all of the elements inX. The subset ofXconsisting of all elementsaofXsuch that propertyP(a)holds true is denoted{a X|P(a)}.Starting from given sets, we can use set operations to form new sets.

10 Given setsXandY, theintersectionofXandYis defined asX Y={a|a Xanda Y}. Given setsXandY, theunionofXandYis defined asX Y={a|a Xora Y}. (a) Use set comprehension notation to define the half-open interval[a, b)in the real {x R|a x < b}.(b) Find a common English description for the following set:{a Z|a= 2k+ 1for somek Z}. set of odd numbers.(c) LetX={1,2,3,4}. How many subsets doesXhave? To define a subset ofXwe need to specify which elements are in that subset. Foreach element ofXthere are two options: either it is in that subset or it is not. Hence we have24= 16subsets.]