Class Note for MATH 300 at UMass(7)
Class Note for MATH 300 at UMass(7)
Popular in Course
Popular in Department
This 8 page Class Notes was uploaded by an elite notetaker on Friday February 6, 2015. The Class Notes belongs to a course at University of Massachusetts taught by a professor in Fall. Since its upload, it has received 18 views.
Reviews for Class Note for MATH 300 at UMass(7)
Report this Material
What is Karma?
Karma is the currency of StudySoup.
You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!
Date Created: 02/06/15
Math 300 Fall 2008 Note 1 Zhigang Han7 Umass at Amherst 1 Logic and Proofs 11 Logic Def 1 A statement or proposition is a sentence that is either TRUE or False Def 2 Let P and Q be statements 1 The logical conjunction P A Q P AND Q is a statement that is TRUE if both P and Q are TRUE7 and is FALSE otherwise 2 The logical disjunction P V Q P QR Q is a statement that is TRUE if either P is TRUE or Q is TRUE or both are TRUE7 and is FALSE otherwise 3 The logical negation N P NOT P is a statement that is TRUE if P is FALSE7 and is FALSE if P is TRUE 4 The logical implication or conditional statement P a Q If P then Q is a statement that is FALSE if P is TRUE and Q is FALSE7 and is TRUE otherwise Rmk In the de nition of the disjunction P V Q7 OR is inclusive ln fact7 we always use inclusive OR in mathematics Try to give yourself examples of both inclusive OR and exclusive OR in English Def 3 A truth table is a table which lists the truth values of a compound statement resulting from all possible combinations of the truth values of its components Rmk If a compound statement has 71 unknown components7 then there are 2 possible combinations Thus the truth table has 2 rows Eg 1 Truth tables for conjunction disjunction negation and implication Def 4 Two statements are logically equivalent if they have the same truth table Eg 2 Show that N P V Q and N P A N Q are equivalent Eg 3 Show that P gt Q and N P V Q are equivalent Def 5 The converse of P gt Q is Q gt P The inverse of P gt Q is N P gt N Q The contrapositive of P gt Q is N Q gt N P Eg 4 Show that P gt Q is equivalent to its contrapositive N Q gt N P Rink P gt Q is NOT always equivalent to its converse or inverse Def 6 The statement P Q Q P if and only if Q or simply P iff Q is de ned by P gt Q A Q gt P Rink If P gt Q we often say P is suf cient for Q and Q is necessary for P If P Q Q we say P is necessary and suf cient for Q Eg 5 Use common sense to nd the truth table for P Q Q then use the de nition of P Q Q to verify it Rink Note that P Q Q is TRUE if and only if P and Q have the same truth values ie P and Q are logically equivalent Eg 6 We can restate Eg 3 as P gt Q Q P V Q Prove this by constructing its truth table 12 Sets A set is a collection of objects the objects are called the elements or members of the set Def 1 If a is an element of the set S we say a belongs to S and write a E S If I is not an element of S we write 1 S One can describe a set by listing all its elements or by means of rules For instance A 124 and B ml1lt z lt 5 Standard notations 1 N 1 2 34 is the set of all natural numbers 2 Z 72 10 1 2 is the set of all integers 3 Q is the set of all rational numbers 4 R is the set of all real numbers Def 2 Let A and B be two sets 1 We say A is a subset of B denoted by A Q B or B Q A if z E A implies z E B 2 We say A and B are equal sets denoted by A B if A Q B and B Q A 3 We say A is a proper subset of B denoted by A C B or B D A if A is a subset of B but A is not equal to B 4 The intersection of A and B is de ned by A B xlm AAx B If A O B 0 we say A and B are disjoint 5 The union of A and B is de ned by AUB xlm AVx B 6 The Cartesian product of A and B is de ned by AXB zylm AAy B Eg 11fA 12 and B 23 then A B 2 Au B 123 and A X B 17 2 173 272 273 Eg 2 A set is called an empty set if it contains no elements Show that all empty sets are equal We denoted the unique empty set by 0 Eg 3 Prove that the empty set is a subset of any other set Eg 4 Let A and B be any two sets Show that A O B Q A U B 13 Quanti ers Def 1 Let Pm be a statement depending on m 1 The universal quanti cation of Pm is a statement 0 Pm for all values of m and is denoted by 0 Vm Here the symbol Vz for all is called the universal quanti er 2 The existential quanti cation of Pm is a statement 0 Pm for some value of m and is denoted by 0 3x Here the symbol Hz there exists is called the existential quanti er Rink The values of z is assumed to be in a particular set7 called the universe of discourse For instance7 it can be N Z or R Or we can directly specify the set S by stating as follows 0 Vm E S 0 3m 6 S Eg 1 The universal quanti cation Vz E R z2 gt 0 is FALSE7 but Vz E R x2 Z 0 is TRUE Eg 2 The existential quanti cation Hz 6 R z2 lt 0 is FALSE7 but Hz 6 R x2 g 0 is TRUE Quanti er negation rules 0 N Vz7 and 3m N Pm are equivalent 0 N Hz and Vm N Pm are equivalent Eg 3 Assume the universe of discourse is Z What do the following state ments mean in English Are they TRUE Can you negate them 0 Vm 3y x gt 0 3y Vz m 2 14 Counterexam ples Def 1 A conjecture is a result which is thought to be TRUE but has not been proven Rink A conjecture is often in the form of a universal quanti cation Vm Note that a conjecture is not necessarily TRUE One can either try to prove it or disprove it 1 To prove Vm Pz7 one has to show Pm is TRUE for all m 2 To disprove Vm Pz7 we need to show N Vz7 is TRUE By the quanti er negation rules7 N Vz7 is equivalent to 3m N There fore7 we only have to nd one value c such that Pm is FALSE This value c is called a counterexample Eg 1 Prove or disprove All prime numbers are odd Question How to disprove a conjecture Vm Pm gt Qm7 Answer Find a value c such that Pc is TRUE7 and 620 is FALSE Why N V907 PM QM ltgt Hz N a ltgt 3957 PM A N QM The 2nd step uses that fact that N P a Q is equivalent to P A N Q Verify this using truth tables Eg 2 Prove or disprove All continuous functions from R to R are differ entiable 15 Proofs A compound statement P can be TRUE or FALSE To prove P means to prove P is TRUE Now let s try to understand some familiar proof methods 0 Direct proof of P a Q Method Assume P is TRUE7 and use this to prove Q is TRUE Question Why can we assume P is TRUE Eg 1 Prove that ifA B A7 then A Q B 0 Direct proof of P ltgt Q Method Prove both P a Q and Q gt P Rink This is the de nition of P ltgt Q Eg 2 Prove that A O B A if and only ifA Q B o Contrapositive proof of P a Q Method Assume Q is FALSE7 and use it to prove P is FALSE Rink P a Q and N Q a N P are equivalent Eg 3 Show that if z E R satis es 2008 z 1 g 37 then x g 1 o Prove P by contradiction Method Assume P is FALSE7 and use this to deduce a contradiction Rink A contradiction has a FALSE value7 and N P a F is equivalent to P Eg 4 Prove that xi is irrational Eg 5 There are 15 people in a party Some of them exchange their handshakes with some of the others Show that at least two people have shaken the same number of hands o Prove P gt Q by contradiction Method Assume P is TRUE and Q is FALSE7 and use them to deduce a contradiction Rink P a Q and P A N Q a F are equivalent Eg 6 Prove the following Pigeonhole Principle by contradiction Pigeonhole principle If N 2 km 1 pigeons are placed in k pigeonholes7 then at least one pigeonhole contains at least m 1 pigeons Eg 7 In a class of 30 students7 show that there are at least 3 students Whose birthday are in the same month Eg 8 Place randomly 5 points in a square of area 16 ftz Show that there are at least 2 points Whose distance from each other is less than 3 ft o Prove P a Q VR Method Assume P is TRUE and Q is FALSE7 and use them to prove R is TRUE Rink P a Q V R and P A N Q a R are equivalent o Prove P VQ R Method Assume P is TRUE and use it to prove R is TRUE Then Assume Q is TRUE and use it to prove R is TRUE Rink P V Q a R and P a R A Q a R are equivalent Eg 9 Let 71 6 R Show that my 0 if and only ifz 0 or y O o Prove P a Q AR Method Assume P is TRUE7 and use it to prove Q and R are both TRUE Rink P a Q A R and P a Q A P a R are equivalent o Prove P AQ R Method Assume P is TRUE and Q is TRUE7 and use them to prove R is TRUE Eg 10 Let m7 n E Z Show that mm is odd if and only if m is odd and n is odd
Are you sure you want to buy this material for
You're already Subscribed!
Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'