DISCRETE MATHEMATICS MATH 302
Popular in Course
Popular in Mathematics (M)
This 12 page Class Notes was uploaded by Evert Christiansen on Wednesday October 21, 2015. The Class Notes belongs to MATH 302 at Texas A&M University taught by Staff in Fall. Since its upload, it has received 16 views. For similar materials see /class/226060/math-302-texas-a-m-university in Mathematics (M) at Texas A&M University.
Reviews for DISCRETE MATHEMATICS
Report this Material
What is Karma?
Karma is the currency of StudySoup.
Date Created: 10/21/15
MATH 302903 Practice Problems for Examination 1 Spring 2006 1 For each of the following sentences7 indicate whether it is a proposition7 and in the case that it is a proposition also indicate its truth value a 7 divides 13 7 1 b A function f R 7 R is differentiable if and only if f0 is a rational number c For every even integer 717 12713 7 2712 18 is even d E 0 e Q A f E z is of order em m 3 P Let n and m be positive integers Consider the following proposition P If n and m are both divisible by 3 then nm 1 is even77 Write the converse7 inverse7 and contrapositive of P CO Incorporate each of the following sentences into a false proposition 0CA a b f is bounded C W 8 d Every differentiable function f R 7 R is continuous e A Q B 7 O 4 Determine7 with proof7 the least integer n such that x4 lnz 7 3x2 4 is 9 Determine which of the following pairs of compound propositions are logically equiva lent a np A 11 and p 7 g b p7qT and p7TT7q c p7q7rand erq7r 03 For each of the following compound propositions7 indicate whether it is a tautology7 a contradiction or a contingency a p 7 Q V197 0 19M V519 019 7 q 7 7quot d pV Q1 0V g Show the following I a 4x7 3x5 9 is of order 7 b 4 3x 2x2 7 4 is of order 2 0 d 2x2 7 3x 7 9 is of order 2 zlnx 3z2x 7 is Oln s but not 01 00 Determine which ofthe following functions are injective and which are surjective Also7 determine the range of each function a f R 7 R given by f 10 2 b f R 7 R given by f 7 2z5 7z3 2x cfR7Rgivenbyf257 lf207 x 1fxlt0 d f 012 7 012374 given by f0 37 f1 47 and f2 0 9 Let A be a nonempty set and let f A 7 A and g A 7 A be functions Prove that if the composition 9 o f is surjective7 then 9 is surjective 10 Prove that7 for all integers 717 n is odd if and only if n3 is odd H E0 r U 03 1 Solutions a Not a proposition b False proposition c True proposition d False proposi tion e Not a proposition f Not a proposition g True proposition Converse If nm 1 is even then 71 and m are both divisible by 377 Inverse If one of n and m is not divisible by 3 then nm 1 is odd77 Contrapositive If nm 1 is odd then one of n and m is not divisible by 377 a There does not exist a set A such that Q Q A b For every function f R 7 R7 f is bounded c For every nite set A7 A 8 d If every differentiable function f R 7 R is continuous then 0 1 e For all subsets A7 B7 and C of R7 A Q B 7 C For all z gt 1 we have ln lt x x2 3 4 and 1 3 4 from which it follows using the triangle inequality that W4 lnz 7 3x2 41 x4lnx 3x2 4 S 5 3x5 4x5 8 Thus x4 lnz 7 3x2 4 is 0z5 Now suppose that x4 lnz 7 3x2 4 is 0z4 Then we can nd constants Qk gt 0 such that x4 lnx 7 3x2 4 S Cz or equivalently lnx 7 3x 4z 41 S C for all z gt k But lirnmH00 1 lnz 7 3x 4z 41 007 which produces a contradiction We conclude that 5 is the least integer n such that x4 lnz 7 3x2 4 is a Not equivalent b Not equivalent c Equivalent a Tautology b Contingency c Contingency d Contingency a For all z 2 1 we have 5 3 7 and 1 S 7 so that f 4x7 3x5 9 3 4x7 3x7 9x7 16z7 which shows that f is 0z7 Since fx 2 4x7 for all z E R7 f is 9z77 and so we conclude that f is of order x7 b For x 2 3 we have 22 7 4 2 sz z 1 3 2 and 2 2 3 2 so that 7243x2lt43x2 7 2x2 62 1 295 2 3 2x2 6x2 2x2 10z2 2 7 4 2 WM 195 Thus f is 0z2 On the other hand7 for z gt 2 we have 7243x2gt43x2 2 71 71 2 274 7 2 ix 32 22 Ex lf96l which shows that f is Therefore f is of order 2 c For x gt e we have 1 S lnx in which case lnx3x lnx3x 1 3 1 3 lt 7l 7lt7l 7l 2l 27 7 2 2n272nx2nx nx7 so that f is Oln Since 1 lnz3 JLHQWHLH 2 7007 f is not 01 d For all z 2 1 we have x S 2 and 1 3 2 in which case it follows using the triangle inequality that lfzl 12952 7395 i 91 2z23z 9 3 2x2 3952 9952 14z2 which shows that f is 0z2 On the other hand7 since lirnmnoo3x 922 07 we can nd a k gt 0 such that for all z gt k we have 32 9 S 2 and hence f 222 7 3x 9 2 222 7 2 2 which shows that f is Therefore f is of order 22 8 p a This function is neither injective since f71 in the range lts range is 200 f1 nor surjective since 0 is not b Since f gt 0 for all z E R f is strictly increasing and hence injective It is also surjective7 as can be shown using the fact that lirnmnwo f foo and lirnmH00 f 00 and the Intermediate Value Theorem Being surjective7 its range is R c This function is injective but not surjective lts range is foo7 0 U 500 d This function is injective but not surjective lts range is 034 Let a E A We need to nd an b E A such that gb 1 Since by assumption 9 o f is surjective7 there is a c E A such that g o f c 1 But then setting b fc we have gb gfc 17 as desired 10 Let n be an integer Suppose rst that n is odd Then we can write 71 25 1 for some 5 E Z Then 713 25 13 853 1252 65 1 2453 652 3s17 which is odd since 453 652 35 is an integer Now suppose that n is even Then we can write 71 25 for some 5 E Z Then 713 2s3 853 24537 which is even since 453 is an integer This shows that if n3 is odd then 71 must be odd We conclude that n is odd if and only if n3 is odd MATH 302903 Practice Problems for the Final Examination Spring 2006 1 Solve the following recurrence relations can 6an1 2 5 with initial condition 10 6 an 17an1 4n 1 with initial condition 10 0 c an 3an1 3 with initial condition 10 1 an 1W1 an 7 mks with initial conditions 10 1 a1 27 and a2 1 an 76an1 7 715 with initial conditions 10 71 and a1 2 2 De ne a relation R on the set of functions from 07 00 to R by ng if f is a Show that R is an equivalence relation b Which of the following pairs of functions are contained in the same equivalence class i ii iii M c Let f 07 00 7 R be an increasing function that satis es the recurrence relation f 2fz2 7 5x2 whenever z 2k for a positive integer k and let 9 000 7 R be de ned by g 3 2x 1 Give necessary and suf cient conditions on f for f and g to be in the same equivalence class z x3 and g 7x3 len x f f ln2 and g lnz3 f 5 f A M2 and g 6 z zem and g emln x 3 Determine the general form of the solutions to the recurrence relation can 7an1 7 15an2 1 96174 4 Determine with proof which of the following are equivalence relations a the relation R on Z gtlt Z de ned by a17a2Rb1b2 if 1le agbl b the relation R on the set of all functions from R to R de ned by ng if f S g for all z E R7 c the relation R on the set of all functions from R to R de ned by ng if f0 3 90 d the relation R on Z de ned by an if 0 3 mm 3 5 or n m 5 How many strings can be constructed from the letters in REARRANGEMENT a using all of the letters7 b using exactly four of the letters7 and c using exactly four of the letters with the requirement that exactly one N be used 6 Determine how many strings with ve or more characters can be formed from the letters in a SYMMETRY7 b REFLEXIVE7 and c RELATION 7 Let A be the set of all relations on 012 and let B be the set of all relations on 0123 a How many functions are there from A to B b How many injective functions are there from A to B c How many surjective functions are there from A to B d How many functions are there from the power set of A to the power set of B 8 Prove by induction that 4 11 is divisible by 3 for all positive integers n 9 Determine which of the following pairs of compound propositions are logically equiva lent a q a W 1 and 11 HPMD b p e q 7quot and 7quot V HM 10 C pea qandpvq 10 De ne the functions f7 9 07 00 a R by f 2 lnx and g 21 Deterrnine7 with proof7 the least integer n such that f o g is Solutions 1 a Note that method of Section 62 wont work here7 since the expression 2n5 added to the linear homogeneous part is not of the appropriate form Let Gz 20 anx be the associated generating function Then xGx 220 ansn 221 awlx and so Gz 7 6zGx Zanx 7 Z 6an1x a0 Em 7 6an1x n0 n1 n1 76 32 5z 6 2 71i5zni5 n1 n1 n0 n0 Thus an 17256 7 2 71 b We will take the approach of Section 62 we could also use generating functions The associated linear hornogeneous recurrence relation is an 17617 which has the characteristic equation 7 717 0 and hence has the general solution can 0417 where a is a constant We then know that the given recurrence relation without specifying the initial condition has a particular solution of the form p171 100 Substituting this into the recurrence relation we get 10171 100 1710171 1100 471 17 that is7 16101 4n 717101 16100 1 0 Since this holds for every n 2 17 we must have 16101 4 0 and 717101 16100 1 0 7 1 7 21 A A 7 n 1 21 Thus pl 7 71 and pg 7 7a Therefore the general solution is an 7 0417 7 Zn 7 Q where 04 1s a constant Considering now the initial condition7 we have 0 a0 Oz 7 a 7 a 1 1 7 a n 7 1 7 a and so 04 7 64 Thus the solution is an 7 6417 471 64 c We will solve this using generating functions we could also take the approach of Section 62 Let Gz 200 anx be the associated generating function Then 71 xGx 20 than 221 an71x and so G 7 3zG 2 ans 7 Z 30n71n a0 2an 7 3on71x n0 n1 n1 1 3nz 1 3n l71 i 1n1 n0 717395quot Thus Gz m 22071 13quotz 7 and so an n 13 d This is a linear hornogeneous recurrence relation with characteristic equation r3 7 r2 7 r 1 7quot 7 12r 1 0 We thus know that the general solution without specifying the initial conditions has the form an b on d71 where 190 d are constants Using the initial conditions we have 1 10 b d7 2 a1 b c 7 d7 1 a2 b 20 d and so b g c 07 and d 7 Thus the solution is an g 7 71 e We will follow the method of Section 62 we could also proceed using generating functions The associated linear hornogeneous recurrence relation is an 76an71 1772 which has the characteristic equation 72 6on71 7 7 r 7 r 71 0 and thus has the general solution can 04177 042 where 041042 are constants We then know that the given recurrence relation without specifying the initial conditions has a particular solution of the form p171 1005 for some constants 100101 Substituting this into the recurrence relation we get 3 9 76p1n 71p05 1 7p1n 7 2 1005 2 n5 7 10171 1005n a from which it can be deduced that pg 144 and pl 48 Therefore the general solution is an 0417 042 n 5 where 041 and 042 are constants Finally7 the initial conditions yield 1ao041042 1447 25 25 2 77 5 7 7 01 041Ot2 48144 from which we get 041 and 042 7 Thus the solution is an 7 1395 25 25 n 1152 En m5 39 a Let f9h be functions from 07 00 to R Since S for all 2 E 07 oo7 we see that R is re exive lf f2 is 92 then there exist constants CD gt 0 such that Cl92l S S Dl92l for all suf ciently large 27 so that D llf2l S S C llf2l for all suf ciently large 27 showing that 92 is f2 and hence that R is symmetric Now suppose that f2 is 92 and 92 is Then there are constants 01027D17D2 gt 0 such that Cll92l S S Cgl92l and Dllh2l S S Dglh2l for all suf ciently large 2 It follows that ClDllh2l S S Cnglh2l for all suf ciently large 27 showing that f2 is h2 and hence that R is transitive Thus R is an equivalence relation b Only the functions in the rst pair are contained in the same equivalence class This can be seen by computing lirnyH00 to be in i7 zero in ii7 and in nity in iii and iv c By the Master Theorern7 f2 is 022 Hence there exists a constant C gt 0 such that 3 022 for all suf ciently large 2 Now suppose that 92 is Then there exists a constant D gt 0 such that S le2l for all suf ciently large 2 But then 3 D022 for all suf ciently large 2 This is impossible since 502 00 Therefore f and 9 are never in the same equivalence class hm2700 This is a linear hornogeneous recurrence relation with characteristic equation 23 7 722 152 7 9 7quot 7 1r 7 32 0 Therefore the general form of the solutions is an 041 04271 043B where 041 042 043 are constants 4 03 a This relation is not transitive For example7 12R00 and 00R21 but 1723271l b This relation is not symmetric For example7 if f 0 and g 1 for all z E R then ng but g f c This relation is not symmetric Use the same example as in d By the de nition of the relation we that an if and only if n and m are contained in a common member of the partition 737271012345678 of Z Since equiva lence relations on a set correspond to partitions of that set7 we conclude that R is an equivalence relation see a agglzr b The number of possibilities with all letters different is 7 6 5 4 with three Rs or three Es 26 with two pairs of identical letters 21 and with exactly one pair of identical letters 36 5 Summing these numbers yields the answer c The number of possibilities with all letters different is 96 5 47 with three Rs or three Es 2G and with exactly one pair of identical letters 1 2 5 Now sum these numbers to obtain the answer a Suppose 5 S n S 8 Then the number of strings that can be formed using 71 letters with no repeated letters is 6l6 7 n if n S 6 and zero otherwise7 with two pairs of repeated letters Swill8 7 n7 and with exactly one pair of repeated letters g5l7 7 n if n S 7 and zero otherwise Summing all of these numbers over 71 57 67 77 8 yields the answer b Suppose 5 S n S 9 Then the number of strings that can be formed using 71 letters with no repeated letters is 7l7 7n if n S 7 and zero otherwise7 with exactly two Es E6l8 7 n if n S 8 and zero otherwise7 and with exactly three Es 6l9 7 n Summing all of these numbers over 71 57 67 77 87 9 we obtain the answer c Since there are no repeated letters7 the number of strings that can be formed using 71 letters for 0 S n S 8 is 8l8 7 n7 and so the answer is 8lamp 7 A relation on a set X is by de nition a subset of X gtlt X Thus there are 232 29 00 H O possible relations on 012 and 242 216 possible relations on 0123 Hence there are lBllAl 21629 21629 functions from A to B7 and 2 l6l2 lL6 7 29 injective functions from A to B Since the cardinality of B is larger than the cardinality of A7 there are no surjective functions from A to B Finally7 since the power set PA of A has 2quot l 229 elements and the power set PB of B has 2lBl 2216 elernents7 the 9 9 number of functions from PA to PB is lPBllPAl 22162 221622 The assertion holds for n 1 since 41 11 15 5 3 Now suppose we are given a positive integer n such that the assertion holds for n Then 4 11 3k for some integer k and so 4 1 11 4 4 11 7 33 43k 7 33 34k 711 Thus the assertion holds for n 7 17 and we obtain the result by induction The pairs of propositions in a and c are logically equivalent 39 we have WWW 4221 ln21 for all z E 07 00 Since llmmaoo M 07 we have lnz21 S x for all suf ciently large x Also7 x4221 S 42z4x4 4x4 for z 2 1 Thus for all suf ciently large x we have lltfogzl 7 964 2962 11nz2 1 3 4x5 and so f o g is 0z5 On the other hand7 lirnyH00 05 lirnnnoo 2x 41 lnz2 1 00 and so f o g is not 0z4 Therefore 5 is the least integer n such that f o g is