### Create a StudySoup account

#### Be part of our community, it's free to join!

Already have a StudySoup account? Login here

# SURVEY MATH PROBLEMS I MATH 645

Texas A&M

GPA 3.92

### View Full Document

## 30

## 0

## 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.

## Popular in Mathematics (M)

## Reviews for SURVEY MATH PROBLEMS I

### 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: 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

### BOOM! Enjoy Your Free Notes!

We've added these Notes to your profile, click here to view them now.

### 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'

## Why people love StudySoup

#### "Knowing I can count on the Elite Notetaker in my class allows me to focus on what the professor is saying instead of just scribbling notes the whole time and falling behind."

#### "I signed up to be an Elite Notetaker with 2 of my sorority sisters this semester. We just posted our notes weekly and were each making over $600 per month. I LOVE StudySoup!"

#### "Knowing I can count on the Elite Notetaker in my class allows me to focus on what the professor is saying instead of just scribbling notes the whole time and falling behind."

#### "It's a great way for students to improve their educational experience and it seemed like a product that everybody wants, so all the people participating are winning."

### Refund Policy

#### STUDYSOUP CANCELLATION POLICY

All subscriptions to StudySoup are paid in full at the time of subscribing. To change your credit card information or to cancel your subscription, go to "Edit Settings". All credit card information will be available there. If you should decide to cancel your subscription, it will continue to be valid until the next payment period, as all payments for the current period were made in advance. For special circumstances, please email support@studysoup.com

#### STUDYSOUP REFUND POLICY

StudySoup has more than 1 million course-specific study resources to help students study smarter. If you’re having trouble finding what you’re looking for, our customer support team can help you find what you need! Feel free to contact them here: support@studysoup.com

Recurring Subscriptions: If you have canceled your recurring subscription on the day of renewal and have not downloaded any documents, you may request a refund by submitting an email to support@studysoup.com

Satisfaction Guarantee: If you’re not satisfied with your subscription, you can contact us for further help. Contact must be made within 3 business days of your subscription purchase and your refund request will be subject for review.

Please Note: Refunds can never be provided more than 30 days after the initial purchase date regardless of your activity on the site.