SURVEY MATH PROBLEMS I
SURVEY MATH PROBLEMS I MATH 645
Popular in Course
Popular in Mathematics (M)
This 5 page Class Notes was uploaded by Evert Christiansen on Wednesday October 21, 2015. The Class Notes belongs to MATH 645 at Texas A&M University taught by Staff in Fall. Since its upload, it has received 30 views. For similar materials see /class/226050/math-645-texas-a-m-university in Mathematics (M) at Texas A&M University.
Reviews for SURVEY MATH PROBLEMS I
Report this Material
What is Karma?
Karma is the currency of StudySoup.
Date Created: 10/21/15
Lecture 5 Copyright Sue Geller 2006 This weeks topic is Hamiltonian graphs in which we want to hit every vertex once without repeating a vertex7 but it doesnt matter what edges we use lndeed7 in most graphs we wont use all the edges As is in the reading7 Alexander Hamilton started the study of Hamiltonian graphs by creating a traveling salesmen game Since we are skipping Exercise 377 I include the proof of Dirac7s Theorem here so that you can use it in your solutions to the assigned Problems Proof Suppose that there are n vertices After adding edges7 we may assume that there is a path of the form 017027vn where 01 and 1 are not adjacent I claim that the degree condition implies that7 if we look at all the vertices adjacent to 11m there must be one7 say 1 whose successor is adjacent to 01 For 01 is connected to at least 712 vertices and ml is connected to at least 712 vertices but 01 is not connected to 1 Therefore they both must be connected to at least one vertex7 11k Then a Hamiltonian cycle is 117 7vk7vmvnil77vk17 139 Problem 37 hint Change the problem into one for a graph constructed from the information given On Problem 38 be sure to prove your characterization7 ie7 a necessary and suf cient condition that the graph have a path that is both Eulerian and Hamiltonian Lecture 1 Copyright Sue Geller 2006 This week we concentrate on the basics of logic7 something you are assumed to have seen before But that doesnt mean you remember it So here is a review De nition A statement is a sentence that is either true or false Some examples of statements are 0 John Doe is taller than Fred Kiddidlehopper 0 Saturday it will rain 0 3 4 5 6 Some sentences which are not statements are 0 ls Suzy a blonde o X is 27 1 Basic Logical Connectives De nitions Given statements P and Q7 we can combine them with various connectives 1 and A P and Q is true only when both P and Q are both true 2 or V P or Q is true if one or the other or both P and Q is true Note that this is different from common English usage You can tell someone is a mathematician when they answer a wait staff7s question of Do you want cherry pie7 brownies7 or cheesecake77 with a Yes 3 not Not P has the opposite truth value from P 4 implies i P implies Q or equivalently P i Q is true unless P is true and Q is false This one often gives people problems How can starting with something false produce a true statement But it does In fact starting with something false you can prove anything using proper logic This tells us the importance of starting with true assumptions There is an old story about Bertrand Russell an eminent mathemati cian at the turn of the 20th century It seems he was lecturing the London Philosophical Society on just this point After he had lectured rather pompously for over an hour a gentleman in the back rose and said Sir assuming that 2 1 prove that you are the Pope Without a moments thought Bertrand Russell replied I am a man The Pope is a man So we are two men Since two equals one I am the Pope 9 if and only if or biconditional or gt1 P gt Q is true when P and Q are both true or both false but is false otherwise Notice the difference between implies and if and only if We were brought up tending to assume that if meant if and only if as in the parental If you clean your room you may go to the movies The parent meant if and only if but stated it as an if not actually saying that if you dont clean your room you may not go to the movies An exception to the if doesnt mean if and only if is in mathematical de nitions I could have de ned statement A sentence is a statement if and only if it can be determined to be true or false That would be proper but mathematicians are lazy and would more frequently write A sentence is a statement if it can be determined to be true or false I will use the convention of if for if and only if in de nitions Another format in which to display the truth or falsehood of a logical statement is a truth table Starting with columns for the basic statements PQRS one then makes columns to to build up your statement The following is a truth table for the logical connectives ln fact7 one can show that two logical expressions are equivalent by show ing they have the same truth values in all circumstances For example7 it is not necessary to have the connective because P i Q is equivalent to P V Q7 as can be seen in the following truth table a a a V 2 Implies and its Relatives An equivalent way of writing P implies Q is If P7 then Q77 the form usually used in English writing7 and is called an implication There are three statements that are gotten from the implication o Converse lf Q7 then P o Inverse lf P then Q o Contrapositive lf Q then P We can see that the implication and the contrapositive are equivalent be cause both are equivalent to P V Q Similarly7 the inverse and the converse are equivalent But the converse and inverse are not equivalent to the impli cation and the contrapositive A simple example is the implication If there is light coming through the windlow7 then there is light in the room77 The converse is If there is light in the room7 then there is light coming through the windlow77 a false statement at night or in a room without windows So be careful with your implications but remember that you can prove the contrapositive and still have proven the implication 3 3 Quanti ers There are two basic quanti es7 for all V and there exists For all has many forms in English 7 for each7 for any7 any7 every7 for every There exists may be expressed as sorne7 for sorne7 there is an These are used in sentences with variables in them For exarnple7 0 There is an integer that is positive 0 Every positive real number has a positive real square root 0 For every 6 gt 07 there exists a 6 gt 0 such that7 if lx 7 al lt 67 then lfW fal lt 6 ln general there exists requires a such that In syrnbols we often use symbols for the statements or simply cornbine words and English For exarnple7 Vs E R4 7 E R4r or V6gt036gt0suchthat lx7al lt6 lfx7fal lt6 4 Negation By using a truth table try it you can see that P Q is equivalent to P V Q and similarly that P V Q is equivalent to P Q Thus7 since P i Q is equivalent to P V Q7 P i Q is equivalent to P Q But what about quanti ers The negation of VzPz is not For no x7 Pz but 3z Px Sirnilarly7 the negation of 3xPz is Vx PQ For exarnple7 the negation of the third example above is 36 gt 0V6 gt 07 lx 7al lt 6 7 fal 2 6