### Create a StudySoup account

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

Already have a StudySoup account? Login here

# DISCRETE MATH I MATH 574

GPA 3.51

### View Full Document

## 24

## 0

## Popular in Course

## Popular in Mathematics (M)

This 7 page Class Notes was uploaded by Cassidy Grimes on Monday October 26, 2015. The Class Notes belongs to MATH 574 at University of South Carolina - Columbia taught by Staff in Fall. Since its upload, it has received 24 views. For similar materials see /class/229549/math-574-university-of-south-carolina-columbia in Mathematics (M) at University of South Carolina - Columbia.

## Reviews for DISCRETE MATH 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/26/15

NAME MATH 574 THIRD TESTPRACTICE ONLY THIS IS A CLOSED BOOK7 CLOSED NOTES TEST7 USE OF CAL CULATORS IS NOT ALLOWED SHOW DETAILS OF YOUR WORK AND SUPPORT YOUR STATEMENTS WITH ARGUMENTS YOU MAY USE THE BACK SIDE OF THE TEST RESULTS MAY BE LEFT AS AN EXPRESSION INVOLVING POWERS OR BINOMIAL COEFFICIENTS7 UNLESS numerical ANSWER WAS REQUIRED 1 Evaluate numerically 2 What is the number of 4 digit PIN codes that use at least one even number 3 What is the number of even numbers that use exactly 7 digits 4 How many words can you make of the letters FIRST using each letter once 5 A committee has 5 women and 4 men members How many 4 member subcommittees can be formed which represents both men and women 6 How many ways can you select 6 fruits out of 3 bananas7 25 kiwis7 4 oranges and 6 apples 7 How many ways can you rearrange the letters of the word GLOSSITIS 8 How many poker hands 5 cards out of 52 have exactly one King 9 Prove the identity 10 A mail order company sends one of 99 different gifts to each of the rst 1000 customers How many ways can they send the gifts 11 How many ways can we put 6 identical balls into 3 identical boxes7 if some boxes may be empty 12 How many ways can we put 6 different coins into 3 identical boxes7 if each box has to contain at least one coin 13 What is the coef cient of x6 in the expansion of x 7 m 14 Show that any integer n 2 8 amount can be paid exactly with 3 and 5 dollar coins 15 Show that for all n 2 1 integer7 the Fibonacci number Fn is at most 2W1 BONUS PROBLEM Prove the following identity ltgt lt2gt l107 NAME MATH 574 SECOND TESTPRACTICE THIS IS A CLOSED BOOK7 CLOSED NOTES TEST7 USE OF CALCU LATORS IS NOT ALLOWED SHOW DETAILS OF YOUR WORK AND SUPPORT YOUR STATEMENTS WITH ARGUMENTS YOU MAY USE THE BACK SIDE OF THE TEST TEST COVERS Section 167 177 217 227 237 41 1 Let us consider f IR a R de ned by f 1 2 and g IR a R de ned by g 2x 2 a Is any of f and g surjection andor injection b Express the compositions f o g and g o f 2 As usual7 lN denotes the set of natural numbers 07 17 27 We con sider the functions f17f27f37f4 with domain N and codornain N Fill in the following table with YES and NO answers 4 Let f A a B be a function7 and T75 be arbitrary subsets of B What is the relationship between f 1SU T and f 1S U f 1T7 Support your statement with a proof 5 Prove for all integer 717 we have 6 Let U denote the universe of discourse7 and Q denote emptyset Eval uate the following a Q N X Q o X 0 i U in X i X aDe ne the graph of the function f A a B De ne that f A a B is an injection De ne that f A a B is a surjection De ne the composite numbers e State the principle of Mathematical lnduction 8 Show by mathematical induction that for all n 2 1 we have 473n1 gn2 n 9 Prove by mathematical induction that for all n 2 57 3 2 n 13 10 Show by mathematical induction that for all natural numbers 717 the expression 9 7 1 is a multiple of 8 11 Conjecture a closed form for the sum 1 3 5 2n 7 1 and prove your conjecture by induction 12 Show on Venn diagram AUBUO AUB O OUA B 13 For each of the following statements7 either prove that the relation is true by Venn diagram or membership table or give an example to show that it may be false aA BUOA BUO b BUO AB AUA O 14 Decide for each statement whether true or false a 5 E 5 b 5 6 237475 c 5 6 2737475 5 C 237475 e we 237475 f U c 2737475 33533333 C f v CL Notes about Exam 2 Math 574 Summer 2007 1 Exam 2 Tuesday June 19 The exam covers sections 41 51 52 53 and 54 2 The material on the 01d MATH 574 exams which is covered on your exam 2 Exam 17s Summer 2007 1 2 3 1992 1 2 4 1987 1 2 3 4 5 6 7 Exam 27s Spring 2006 3 5 9 1992 2 3 4 1987 4 7 8 9 Exam 37s Spring 2006 1 2 3 4 5 6 7 8 1992 2 3 4 Exam 47s Spring 2006 1 2 3 Final Exams Spring 2006 1 2 5 8 1992 4 6 8 9 11 1987 1 2 8 9 10 3 The material on the 01d MATH 174 exams which is covered on your exam 2 Exam 37s 1998 5 2003 2 3 7 8 Exam 47s 1998 3 5 7 9 11 12 2003 2 5 7 Final Exams 1998 5 6 16 23 24 2003 7 8 10 12 17 NAME MATH 574 FIRST TESTiPRACTICE ONLY THIS IS A CLOSED BOOK CLOSED NOTES TEST USE OF CALCULATORS IS NOT ALLOWED SHOW DETAILS OF YOUR WORK CIRCLE THE CORRECT ANSWER FOR THE MULTIPLE CHOICE QUESTIONS ANY MULTIPLE ANSWER SCORES 0 POINT ONLY ONE ANSWER IS CORRECT FOR MULTIPLE CHOICE QUESTIONS 1 Which of the following sentences is a true proposition 3 7 10 7r l 7 7r 2 I wish I did the homework 7 7 2 4 e Joe is not smart and 9 24 b c d e 5 2 Which is the negation of the following sentence All criminals are liars or pickpockets a Some criminals are not liars or not pickpockets b Some criminals are not liars c All criminals are not liars or not pickpockets d Some criminals are not liars and not pickpockets Some criminals are not liars or not pickpockets 110693 93 D e Which of the following propositions is a contradiction P H P p q 5 19 V q 19 V 5p OU QDWQD CL V B lt 2 6 nbp A w a b c d e 5 4 Let Hx y denote that person at wrote a letter to person y and R y denote that person y receives a letter from person at Which is a correct formalization of the following sentence If everybody writes a letter to everybody then nobody receives a letter from anybody a l3VyHyl any chmy b 396Vyl1ly clA Vy vcl awl c VyHmeml a Hltmgti d lechHWwN VyWnMaw 6 lechHWwN Vy vcnRy a b c d e 5 5 Let Ly denote that x loves y Which of the following sentences spell out correctly the following formula V ay lxya gt a Everybody loves somebody b Everybody is not loved by somebody c Nobody loves everybody d Somebody does not love anybody e Everybody does not love somebody a b c d e 5 6 Let Px y mean that x y 2 The domain is real numbers for both variables Write out with formula negate the formula and then translate back to English the negated formula a For every real number there exists a real numbers such that the sum of the two numbers equals two b The sum of any two reals numbers equals two c There exists a real number such that adding any real number to it the result is two 7 Prove the following theorem There are two irrational numbers such that their sum is rational Write sentences 8 Prove that the last digit of the square of any integer is one of 014569 9 In the following proofs decide if the proof is correct or not and name the proof technique or point out the error in the proof a Theorem The square of an integer is always of the form 4k or 4k 1 Proof Take for example the integer 3 32 9 4 2 1 so the second alternative holds with k 2 Take now for example the integer 6 62 36 4 9 so the first alternative holds with k 9 b Theorem There is no greatest natural number Proof For contradiction assume a natural number x is the greatest one By definition of greatest this means that for all natural numbers n n S x Take x 1 this is also a natural number since we can add one to every natural number Furthermore we have x lt x 1 But at l is a natural number and therefore by the earlier argument at l S x The inequalities x lt x l and x l S x are the negations of each other so we reached a contradiction c Theorem Every even number that is at least 4 is composite Proof By definition of even numbers every even number has the form 215 with some integer 15 Since the number is at least 4 t is at least 2 Therefore when we write the number as 215 write it as a product of two integers each bigger than one This is the definition of composite numbers d Theorem If n 6 2 n2 for a natural number n then H S 3 Proof Assume n 6 lt 112 Then 0 lt n2 7 n 7 6 n 2n 7 3 Observe that this inequality fails for n 0 123 Therefore we must have n 2 4 10 Show that some positive integers cannot be written as the sum of 3 squares 02 is allowed among the squares 11 Decide if the following is true For every positive integer n if n is a prime then H 1 is not a prime 12 1f Joe is a robber then he is not on the beach77 a Make the negated statement b Make the contrapositive c Make the converse 13 Decide whether the following theorem is true and whether its proof is correct Explain For any real number at x is rational if and only if x 1 is rational Assume that x is rational Then at pq with p q integers and q 31 0 By the laws of algebra x 1 pq 1 p qq where p q is an integer and still 1 31 0 By the definition of rational numbers at 1 is rational Assume now that x is irrational we have to show that x 1 is irrational as well We do proof by contradiction Assume that x is irrational but at 1 is rational Write x 1 11 with integer a b such that b 31 0 Then at ab 71a 7 bb is rational so at is rational and irrational the required contradiction 14 Let Q y denote ac times y equals zero and the domain for both variables is real numbers What is the truth value of a V mey b HnyQWw 6 VWyQW y lt VyWQW y d VWyQW y e Wigwam

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

#### "I was shooting for a perfect 4.0 GPA this semester. Having StudySoup as a study aid was critical to helping me achieve my goal...and I nailed it!"

#### "When you're taking detailed notes and trying to help everyone else out in the class, it really helps you learn and understand the material...plus I made $280 on my first study guide!"

#### "There's no way I would have passed my Organic Chemistry class this semester without the notes and study guides I got from StudySoup."

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