Discrete Mathematical Structures (Classic Version), 6th Edition Solution Manual

Preview (16 of 176 Pages)

100%

Purchase to unlock

Loading page image...

DISCRETEMATHEMATICALSTRUCTURESSixth EditionKOLMANBUSBYROSSRESOURCEMANUALSHARON CUTLER ROSSGeorgia Perimeter College

Loading page image...

CONTENTSNotes to the Instructor.............................................................................................................................................1Chapter NotesChapter 1.......................................................................................................................................................... 2Chapter 2.......................................................................................................................................................... 2Chapter 3.......................................................................................................................................................... 2Chapter 4.......................................................................................................................................................... 3Chapter 5.......................................................................................................................................................... 3Chapter 6.......................................................................................................................................................... 3Chapter 7.......................................................................................................................................................... 3Chapter 8.......................................................................................................................................................... 3Chapter 9.......................................................................................................................................................... 4Chapter 10........................................................................................................................................................ 4Chapter 11........................................................................................................................................................ 4Student Experiments......................................................................................................................................... 5Sample Test ItemsChapter 1 Test Items7Chapter 2 Test Items8Chapter 3 Test Items10Chapter 4 Test Items10Chapter 5 Test Items13Chapter 6 Test Items15Chapter 7 Test Items18Chapter 8 Test Items20Chapter 9 Test Items23Chapter 10 Test Items25Chapter 11 Test Items27Answers (Even and Odd Exercises)Chapter 1 Answers28Chapter 2 Answers39Chapter 3 Answers53Chapter 4 Answers59Chapter 5 Answers73Chapter 6 Answers79Chapter 7 Answers91Chapter 8 Answers103Chapter 9 Answers113

Loading page image...

Chapter 10 Answers............................................................................................................................................. 122Chapter 11 Answers............................................................................................................................................. 135Appendix A Answers........................................................................................................................................... 138Appendices B and C Notes................................................................................................................................. 140Sample Test Item AnswersChapter 1 Test Item Answers141Chapter 2 Test Item Answers142Chapter 3 Test Item Answers144Chapter 4 Test Item Answers145Chapter 5 Test Item Answers148Chapter 6 Test Item Answers149Chapter 7 Test Item Answers152Chapter 8 Test Item Answers155Chapter 9 Test Item Answers157Chapter 10 Test Item Answers159Chapter 11 Test Item Answers161Answers for Self-TestsChapter 1 Test Answers163Chapter 2 Test Answers163Chapter 3 Test Answers165Chapter 4 Test Answers165Chapter 5 Test Answers166Chapter 6 Test Answers167Chapter 7 Test Answers168Chapter 8 Test Answers170Chapter 9 Test Answers172Chapter 10 Test Answers172Chapter 11 Test Answers174

Loading page image...

CHAPTER NOTESCHAPTER 1FUNDAMENTALSSets are fundamental to many later discussions and definitions so we have chosen to begin with them.Sequences, matrices, and properties of the integers also recur throughout the text in the development of examplesas well as of basic ideas.Material on base n representations gives us a tool for beginning a discussion ofcryptology. The last section pulls together some general ideas such as properties of operations and helps studentssee the similarities among the topics discussed earlier in the chapter.There is a danger that students will seediscrete mathematics as a hodge-podge of unrelated ideas. By comparing and contrasting sets, integers, andmatrices and operations on them, students begin the transition to a more global view — mathematical structures.These concepts are reinforced in later chapters.For many students the level of abstraction of many topics indiscrete mathematics presents a problem.This may be the student's first mathematics course that is not skill-oriented and procedure-driven.The change from thinking about the distributive property to a distributiveproperty does not come easily to most students.Working from familiar situations such as integer arithmetic andsets facilitates this change.Although they are formally defined in Chapter 5, functions are used informally here in the discussion ofcomputer representations of sets.CHAPTER 2LOGICWhile a number of discrete mathematics texts begin with logic, we chose to cover in Chapter 1 topics thatare both more familiar and more concrete for students.This choice leads to some small inconsistencies inChapter 1 where students are asked to prove some simple statements.However, the students have seen proofsbefore, so this is not a serious problem.Swapping the order of the two chapters is possible if one feels stronglyabout beginning with logic. In a course taught for computer science majors, it is easy to tie much of Chapter 2 towriting guards for loops and proving code.Students with programming experience will also have experience indetermining the truth value of compound statements that can be utilized.The idea of a mathematical structure is used to connect the system of logical statements and operations onthem to ideas in Chapter 1.While several types of proof are discussed in this chapter, the use of mathematical induction is emphasized,especially its role in proving code.We relate the structure of a proof based on mathematical induction to earlierwork with implication.In particular, the induction step does not say "Assume that P(/c) is true."Studentsfrequently stumble over the word "assume" and do not see why they can not just "assume P(n)" and be done. Thestrong form of mathematical induction is also included. Both forms of induction recur throughout the text both inexamples and in exercises.Two new sections provide more experiences with proofs and problem solving.In Section 2.5 we explorehow mathematical statements are created and give more proof practice.By engaging students in the writing ofmathematical statements, we demystify a common mathematical process and help students think mathematically.The last section uses sudoku puzzles as a hook to develop the problem-solving technique of modeling severalproblems in terms of an older problem.CHAPTER 3COUNTINGWe use the notationsnPrandnCrfor the number of permutations and combinations, respectively, ofnobjects takenrata time.These notations are the same as, or similar to, those used on many calculators andavoid the anomalous (™) which is often a problem for students. Permutations and combinations with repeats arealso discussed.Counting techniques are necessary for algorithm analysis.Another tool for algorithm analysis is anunderstanding of recurrence relations.A section in this chapter covers the basic ideas of how to solve linearhomogeneous recurrence relations.Recurrence relations are also one of a number of uses and examples ofrecursion throughout the text. We believe that students need to spend time with this concept and consequently wehave woven it through the book.A brief introduction to probability provides an application of the counting methods discussed as well asconcepts needed for future discussions; e.g., probabilistic algorithms.Page 2Discrete Mathematical Structures

Loading page image...

CHAPTER 4RELATIONS AND DIGRAPHSThis chapter is the core of the text.Relations are used as the foundation of virtually all that follows.Properties and representations of relations are presented in detail.Verbal descriptions, sets of ordered pairs,incidence matrices, and digraphs are presented as representations together with discussion of how to determine, inthat representation, whether a relation has a specified property.The use of multiple representations enablesstudents to acquire the concept of a relation more easily and with greater understanding.A taste of relational databases shows an application of ordered n-tuples before we restrict ourselves toordered pairs.The generation of new relations from given relations is covered for composition, union, intersection,complement, power, and closure. The inheritance of properties by the new relations is explored in examples andexercises.The idea of an equivalence relation and its corresponding partition is a powerful one developed in thischapter and used in a number of later sections. Experiment 4 offers a strong reinforcement of this relationship.The exercises in this chapter are particularly rich sources of opportunities for students to build their proofskills.CHAPTER 5FUNCTIONSFunctions are presented as a special type of relation. One-to-one correspondence is a key idea for later workand appears here as a function with certain characteristics.One-to-one functions are applied to the creation ofsubstitution codes.The use of mod functions with check digits is also presented.Special emphasis is given tofunctions that are commonly used in computer science either in developing code or in analyzing algorithms.These include floor and ceiling functions, mod functions, and Boolean functions. Also, we extend the concept ofa characteristic function to define a fuzzy set and have students revisit set operations and proofs usingcharacteristic functions.The chapter continues with a low-level introduction to the growth of functions including big-Oh notationand theta classes. This section also gives us a chance to return to some algorithms from earlier chapters.Permutations are revisited from the point of view of functions in the final section. As one-to-one functions,they are used to develop some simple cryptography schemes.CHAPTER 6ORDER RELATIONS AND STRUCTURESWe return in this chapter to the theme of types of relations, namely partial orders (posets), lattices, andBoolean algebras.Section 7.1 contains the first appearance of isomorphism, a concept of great use in latersections and chapters.Lattices and Boolean algebras are also a way to return to the idea of a mathematicalstructure introduced in Chapter 1.The connections among Boolean algebras, Boolean functions, and circuitdesign are developed.Although circuit design and simplification are rarely done by hand any more, we thinksome experience with Karnaugh maps and basic ideas in this field is beneficial for students. A symbolic versionof Karnaugh maps is included in the exercises.CHAPTER 7TREESTrees are presented as yet another type of relation with (naturally) most emphasis on their graphicalrepresentation. The groundwork is laid in this chapter for the use of a tree as an abstract data type. Huffman codetrees introduce coding for efficiency.This relates to earlier (and later) discussions of coding for security andcoding for error detection and correction.The two versions of Prim's algorithm are synthesized in a matrix-basedmethod for weighted graphs.Recursive procedures for traversing a tree bring the student to the idea of recursion again. Spanning treesand minimal spanning trees illustrate for the student ways in which trees are natural models for real-worldsituations.By this time students have seen a number of algorithms and have developed some intuition aboutrecursion, backtracking, greedy algorithms, and other standard programming tools.CHAPTER 8TOPICS IN GRAPH THEORYGraphs, in particular digraphs, are used to represent relations in Chapter 4, but students are likely to seegraphs used in a number of other contexts.This chapter looks at graphs as entities in their own right.As withother topics, our aim is to present a solid foundation, but to leave deep results to later courses.Page 3

Loading page image...

Euler and Hamiltonian paths and circuits are topics that arise naturally in many applications of graph theory.They are also ideas that students find accessible, and the fundamental theorems are nice examples of existencetheorems.Sections on transport networks and matching problems offer another context for the application of graphtheory. The section on coloring graphs is an opportunity for students to work with counting techniques, functions,graphs, and relations. We also point out another case of using one model to solve a variety of problems.CHAPTER 9SEMIGROUPS AND GROUPSThis chapter is another extension of the ideas in Section 1.6 on mathematicalstructures. We believe thatstudents should learn to deal with situations like the change of definition of binary operation in Section 9.1.Certainly we could have defined operation in the same way in Sections 1.6 and 9.1, but asking students to dealwith a different version is useful. The main structures in this chapter are semigroups and groups. Many ideas andexamples defined earlier are pulled together here to give the students lots of examples of operations, properties,semigroups, and groups.The results of Experiment A (Appendix B) can be discussed again if it has beenassigned.Equivalence relations reappear as congruence relations and isomorphism is redefined to preserveoperations.A final section gives a brief introduction to rings and fields.In particular, we developfor use inChapter 11.CHAPTER 10LANGUAGES AND FINITE STATE MACHINESCompiler and theory of languages courses for computer science majors generally expect students to absorbvery quickly formal presentations of languages and topics such as parsing and derivation.The intent of thischapter is to lay some groundwork for these courses, and others. Approaching a phrase structure grammar as onemore mathematical structure lets students use experience gained earlier in the course to aid in acquiring theseconcepts. Sections 10.1 and 10.2 go very smoothly for nearly all students.Finite-state machines as language recognizers complete the chapter. The ideas are developed through a niceblend of earlier work — semigroups, graphs, functions, and equivalence relations.CHAPTER 11GROUPS AND CODINGThis is an authors' choice chapter. There are a number of topics appropriate for courses using this text thatwould have allowed us to apply ideas from earlier chapters.In earlier editions we focused on codes for errordetection and correction.Now we also present the culmination of the cryptology (codes for security) thread thatbegins in Chapter 1. These ideas use many topics from earlier chapters and are inherently interesting to students.Page 4Discrete Mathematical Structures

Loading page image...

STUDENT EXPERIMENTSExtended-time assignments in which students, individually or collaboratively, investigate, conjecture, andjustify are an excellent way for students to take ownership of the mathematics they study.Each of theexperiments is designed for a 10—14 day time frame.Some experiments extend concepts in the text; otherspreview topics.All require students to write about the mathematics they have done.A typical grading rubric isthe following.This assignment is worth a maximum of 35 points of the 100 point experiment grade.Be sure toanswer each question using standard written English. Points will be distributed as follows:10 pointsclarity and completeness of presentation15 pointscorrectness of computations and mathematics10 pointsstyle and neatnessYou are encouraged to use word-processing.Reading through all the reports before grading seems to speed up the process.Encourage students to talk with you if they are stuck, but it works best to confine yourself to lots ofquestions and only tiny hints. What students may need most is to hear (repeatedly perhaps) that these are doableassignments.Experiment 1whengoalsweighted voting systemsafter Section 1.1present a novel application of power setsbegin the course with something freshExperiment 2whengoalfinite geometriesafter Chapter 2'provide practice in logical problem solving and proving conjecturesExperiment 3whengoalsMarkov chainsafter Section 3.4introduce the concept of a Markov chainapply probability ideasExperiment 4whengoalscompatibility relationsafter Section 4.5extend idea of equivalence relationreinforce connection between equivalence relation and partitionbuild parallel structure for compatibility relation and coveringinvestigate inheritance of propertiesExperiment 5whengoalssimple algorithm analysisafter Section 5.3; also needs Appendix A and Section 3.5perform simple algorithm analysisintroduce two simple search algorithmsutilize recurrence relationsExperiment 6whengoalsPetri netsafter Section 6.6adapt digraphs to a new useintroduce the basic concepts of operating systemsPage 5

Loading page image...

Experiment 7whengoalsB-treesafter Section 7.3introduce concept of a B-treeinvestigate characteristics of B-treesExperiment 8whengoalcliquesafter Section 8.6, but if question 7 is omitted, it may be assigned after Section 4.4provide practice with relations, digraphs, and graphsprovide another method for determining x()Experiment 9whengoalssubgroupsafter Section 9.4introduce order of an elementinvestigate the relationship between an element's order and the group's orderinvestigate the relationship between the orders of subgroups and groupsExperiment 10whengoalspushdown automataafter Section 10.3preview concept of a pushdown automatonuse stack operations of push and popExperiment Awhengoalsmodular arithmeticafter Section 1.6, but before Chapter 9; needs Example 4, Section 4.5provide experience with modular arithmeticdevelop criteria to determine ifhas unique solutions to certain equationsbuild examples of groups for later useExperiment BwhenTowers of Hanoiafter Section 3.5, but if question 4 is restated, students need not have seenrecurrence relationsgoalsgive experience with recursionpractice mathematical induction proofsExperiment CwhengoalsCatalan numbersafter Section 5.2create models for the Catalan numbersdemonstrate the power of modeling as a problem-solving toolpractice proof techniquesPage 6Discrete Mathematical Structures

Loading page image...

Sample Test ItemsChapter 1 Test ItemsLetA= {x |x= 3m,mG Z},B= {0, 2, 4, 6, . . . }, C ={y | y2< 150}, andD = {y | y2+ 4 = 0}.(a) Tell if each of the following is true or false.(i){6, 12} CA(ii){6, 12} C c(m)BCA(iv)D C 0(b) Tell if each of the following is true or false.(t)DUACc(u)AnD = D(Hi)BAACC(iv)CCAUBLet 4 = {1, 2, 3, 4},B = {x | xG Z+andx2<16}, C = {1,2, 3},D = {x \ x e Zandx2= 4 } ,and E = {x | xG Z andx2—— 4}.Tell if each of the following is true or false.(a)A = C(b)ACB(c)C GB( i ) D C E( e ) E C A( f ) C C ( J A 7 ) )Draw a Venn diagram that shows the relationships among the five sets given in Question 2.LetS —{0,a, {b}}.(a) Give P(S).(b) What is | P(5) |?(c) Tell if each of the following is true or false.(i)0 G 5(u){a, b} c s(Hi){b}C S(iv)0 C S( v ) { b } e S( v i ) { } A S{}(vii){$} e S(viii){ a } A S = SLet 4 ={x | x= 3n,ne Z+},B = { x \ x=4m, m G Z+}, C ={t11 -2n — 1,nG Z+},andD —{s |s = 2k, k GZ}. Use Z as the universal set and compute:(a)A A B( b ) A © C( c ) B(d)D - C(e)B A DLetJ = {M, A , N } , B = {F, A, U, S, T},L= {S, I, A, M } , a n d U = {M, A, T, H, I, S , F , U , N } .1.2.3.4.5.6.Compute:(a) (J UK) AL(b)( J ® L ) A ( L - J )Prove that ifAClB = AUB,thenA = B.The records of 200 students at Verysmall College show the following courses taken:104 students took Latin46 students took Latin and Greek9 students took all three languages103 students took Greek35 students took Sanskrit24 students took Greek and Sanskrit28 students have taken none of these languages(a) How many students took only Greek?(b) How many students took only Latin and Sanskrit?Prove thatAU(AClB) = A.Write a formula for the nth term of the sequence 2, 5, 8, 11, 14, . . . .Define a sequence as follows: a0= 2, cq = 3,an= 2an1— San_2-Give the first six terms7.8.9.10.11.12.of this sequence.LetU — {m, n, o, p, q, r, s, t, u, v}, A ={o,u}, B= {m, o, s,t}, C= {n,p,r}, andD ={n,o, r, t, u,u}.Represent each of the following sets by an array of zeros and ones.(a)AUC(b)B A D(c)CU(AAD)(d)(AAB)UCLetI= {0, 1}. Describe the regular subsets of 7* corresponding to the following regularexpressions.(a) (01)*10*1(b) 110*10*( c ) ( l V 0 ) * 0 1 1(d) 0*10*(10*10*)*LetI — {a, b,c}. In each part below is listed a string in 7* and a regular expression over 7. Foreach, state whether the string belongs to the regular set corresponding to the expression.(a)abcabc*(b)abc(a*bV c)*(c)abc(a V b)*c(d)abc(a5)* V cCompute GCD(1350, 297) and write it as s(1350) + i(297).Use the Euclidean algorithm to compute GCD(4389, 7293).Compute LCM(180, 294).Letgbe the mod-13 function. Compute each of the following.(a)5(92)(b) 5(8)(c) 5(182)(d)g(U5)13.14.15.16.17.18.Page 7

Loading page image...

Write the base 8 expansion of each of the following numbers.(a) 12(b) 139(c) 486Write the base 10 expansion of each of the following numbers.(a) (123)5LetA=(c)(1011011)214(b) (71)8andB =636- 24- 350. Compute, if possible, each of the following.19.20.21.AT6'3(c)14(b)BAandB(a)ABLetA =4- 36- 250. Compute, if possible, each of the following.22.(a) A + B(b) ATB(c) A-123.Describe all 2 x 2 matrices A such that A2is symmetric.'101r’001o'0101and D =01001111100000000001. Compute each of the following.LetC —24.(a)C 0 D(b)C V D(c)C A D25.Defineab=yand aV6 =a — b.LetR= (even integers,□, V).Show thatRis closed withrespect to□.26.LetR= (even integers,□, V) as defined in Question 25. Give the identity element, if one exists, for:(a)(b)V27.LetRbe the mathematical structure in Question 25. Show thatRhas a distributive property.28.Show thatACAUB.29Show thatAClBCA.30.Show thatA — A = { }.31.Letaandbbe integers. Show that ifpis a prime such thatp| ab,thenp| aorp| b.32.LetAbe a Boolean matrix, (a) Show thatA V A = A.(b) Show thatAAA = A.Chapter 2 Test Items1.Letp:Jack is nimble,q:Jill is quick, andr:Jose jumped over the candlestick.(a) Write each of the following in terms ofp, q, r,and logical connectives.(z) Jack is nimble or Jill is not quick.(zz) Jose jumped over the candlestick and Jack is nimble.(zzz) Jack is nimble and Jill is quick, or Jose did not jump over the candlestick.(b) Write an English sentence that corresponds to each of the following.(z)~p A ~ r(zz)q V (pA r)(zzz) ~ (p Vq)2.Determine the truth value for each of the following statements wherexandyare integers.(a) VxByx + yis even.(b)BxByx + yis even.3.Make a truth table for the statement ~ (p A ~ (p V q)).4.Make a truth table for the statement p V ( ~ p V q) .5.Make a truth table for the statement ( ~ p V~q)A (p V ~ r).6.Make a truth table for the statement ((q Ar)A p) V ( ~ (p A r) V q) .7.Letp:Jack is nimble,q:Jill is quick, andr:Jose jumped over the candlestick.(a)Write the negation of each of the following sentences.(z) If Jack is nimble, then Jill is quick.(zz) Jose jumps over the candlestick and Jill is not quick.Page 8Discrete Mathematical Structures

Loading page image...

(b) Write an English sentence that corresponds to each of the following.(0(~q) => p(H)M = >(jii) (rV q)Op8.Ifp => qis true, what is the truth value of(pVg)=>~qlExplain your reasoning.9.Make a truth table for the statement (~p)A(p=>q).10.Letp:If you do your homework and you ask questions, then you will succeed in discretemathematics.(a) Define simple statements and use them to writepin symbolic form.(b) Give the converse ofpin English and in symbolic form.(c) Give the contrapositive ofpin English and in symbolic form.11.Translate into symbolic form and test the validity of the argument.(a)If I do not practice, then I will not win the match.I practice./.I will win the match.(b)If I work, then I cannot study.Either I study or I pass my mathematics class.I work./.I pass my mathematics class.12.Determine whether the given argument is valid or not. Explain your reasoning.(a)p =>( q \ / r )(b)(~p) => (~q)(X z__q _____________.rp13.Prove or disprove by giving a counterexample that the sum of any three consecutive even integersis divisible by 6.14.Prove or disprove by giving a counterexample that the sum of any three consecutive odd integersis divisible by 3.15.Prove that the following statement is true by using mathematical induction._L_i__L_1_____I ______1_____-n1-33-5( 2 n - l ) ( 2 n + l )2n+l16.Prove that I3+23+ 33+•■■+ n3=-.17.Prove that1 + 5 + 9 4-----+(4n—3)=n(2n—1).18.Prove that 5n—3 is divisible by 2.19.Prove that1 +2+34-----+ n <.20.Prove thatn5—nis divisible by 5 forn >1.21.Prove that n! >2"- 1.22.Prove that every integer greater than 24 can be written as the sum of a multiple of 5 and a multiple of 7.23.Consider the following function where the inputXis a positive integer.FUNCTIONF(A)1.Z<- 12.C<r-13.WHILE(C<X)a.Z<—Z + 2C + 1b.C < - C + l4.RETURNZEND OF FUNCTION F(a) Prove that Z = C2is a loop invariant and give the value of Z when the loop terminates.(b) Describe what the function F produces.Page 9

Loading page image...

Chapter 3 Test Items1.Compute the number of(a) arrangements of the letters of FINAL(b) baseball lineups for a 15-member team(c) distinct arrangements of the letters of CLEVELAND2.How many three-letter "words" can be formed from the letters of COMPUTER if(a) no letter may be repeated?(b) letters may be repeated?3.A palindrome is a string that reads the same forwards as backwards like POP. How many seven-letter palindromes can be made using the English alphabet?4.A fair six-sided die is rolled 4 times. If the results of each roll are recorded, how many(a) record sequences are possible?(b) record sequences end 5, 6?5.Doughnut Whirl has 16 different types of doughnuts this morning. If you allow repeats, how manydifferent ways can a six-doughnut box be filled?6.The Acian parliament needs to form a joint committee of six members from the lower house and sevenmembers from the upper house.If there are 29 eligible members of the lower house and 18 eligiblemembers of the upper house, how many different committees are possible?7.Prove thatnPr= r■n_]Pr_L +n- i Pr.8.Prove thatm + nCr=m C i' n C r - i -i=l9.How many choices does a student have if she must answer(a) eight out of ten questions on a quiz?(b) eight out of ten questions on a quiz and must answer the first three questions?10.Complete and prove the following statement. At leastpeople in a city of 2,384 people have thesame pair of first and last initials.11.Suppose your history book has 648 pages and 14 chapters. Prove that at least one chapter has 45pages.12.A baker has decorated the top of a cake with 52 small hard candies. If the cake is cut into 12 equal-sizepieces, at least one piece must havecandies on it. Justify your answer.13.What is the probability that exactly 3 sixes will be recorded when 5 fair dice are tossed?14.Chris has five different pairs of gloves in a drawer. If two gloves are chosen at random, what is theprobability that the gloves will be a matched pair?15.A basket contains three apples, five bananas, four oranges, and six pears. A piece of fruit is chosen atrandom from the basket. Compute the probability that(a) an apple or a pear is chosen.(b) the fruit chosen is not an orange.16.In the state tournament, the probability of the Marmots winning is 0.40. The other two teams, the Toadsand the Emus, are equally likely to win. What is the probability that(a) the Marmots will not win?(b) either the Toads or the Marmots will win?17.Suppose your company work group has 10 members. What is the probability that you will be chosen torepresent the group if(a) one representative is chosen?(b) two representatives are chosen?18.Letp(A) —0.24,p(B} =0.68, andp(APl5) = 0.15.(a) What isp(AU 5)?(b)AreAandBmutually exclusive events? Justify your answer.19.Find an explicit formula for the sequence defined by— 3, an= 3an-1+ 1.20.Solve the recurrence relationbn=— 15bn_2,= 2, 62= 16.21.Solve the recurrence relationcn=— Sc -j— 16cn_2, cj =— 1, C2 = 8.22.Develop a formula for the solution of a recurrence relation of the forman= an_1+ m, ax= m.Chapter 4 Test Items1.LetAbe the set of positive divisors of 15 andB —{a,b,c}.(a) What is\AxB |?(b) ListAxB.2.Prove thatif ACB,then ,4xCCBxC.3.Give all two-element partitions of{a, b, c, d}.Page 10Discrete Mathematical Structures

Loading page image...

Often email records show the date received, the sender, the subject, message size, and the statusof the message (read, deleted, et al.). Use the operations select, project, and standard setoperations to describe answers to the following queries. Assume the database is named EMAIL.(a) How many messages with the subject "Saturday night" have been received?(b) Who sent messages to you on January 11, 2008?Let5 ={a, b}.How many relations are there on F’(S)?LetA={a, b, c, d}andRbe a relation onAwhose matrix is Mp=1 01 0001 11 1 1 01 0004.5.6.7.8.9.(a) GiveRas a set.(b) Draw the digraph ofR.LetB={1,2, 3,4, 5} andRbe the relation onAwhose digraph is given in Figure 1.(b)GiveMtf.(a) GiveRas a set.1 XFigure 1LetC={3,7, 11}. Define a relation onCbyxRyif and only ifx—y<4.(a) Draw the digraph ofR.(b)GiveM#.LetA={1,2, 3,4, 5} andRbe the relation onAwhose digraph is given in Figure 2.(a) List all paths of length 3..(b) List all cycles.Figure 2Using the relationRwhose digraph is given in Figure 2,(a) Give the matrix ofR2.(b) List the elements of7?4.(c) Draw the digraph ofR3.Let5 ={1, 2, 3, 4} and??={(2, 4), (4, 3), (3, 2), (2, 1), (1, 1)}.(a) Draw the digraphs ofRandR2.(b) Give Mj? and M.Fl101110.11.12.13.14.(c) GiveMtfoo.LetRbe a relation defined by Mj?=01 01(b) Give Mj?oo(a) Give M.Determine whether the relationRon the setAis reflexive, irreflexive, symmetric, asymmetric,antisymmetric, or transitive, whereA ={1, 2, 3, 4} and?? = {(1, 1), (2, 2), (3, 3), (1, 2), (2, 1), (1, 4), (3, 2), (3, 1), (3, 4), (4, 2), (4, 1)}.LetD ={1,2, 3,4, 5} andRbe the relation onDwhose matrix is1000100010101010000110100AU?=Determine whetherRis reflexive, irreflexive, symmetric, asymmetric, antisymmetric, or transitive.Page 11

Loading page image...

15.LetB= {1, 2, 3, 4, 5} andRbe a relation onBwhose digraph is given in Figure 3. Determine whetherRis reflexive, irreflexive, symmetric, asymmetric, antisymmetric, or transitive.Figure 3Explain why we can define the symmetric closure of a relation, but not the asymmetric closure of arelation.16.17.18.19.20.Lettbe a fixed real number. Define a relation on R as follows:xRyif and only if there exists an integermsuch thatx — y = mt.(Note thatmwill depend onxandy.)Prove thatRis an equivalence relation.LetA =x Z+, and defineRonAas follows: (a?,y)R(u, v)if and only if 2 |(x — u)and 3 |(y— u).(a) Prove thatRis an equivalence relation.(b) Compute [(5, 4)], the equivalence class of (5, 4).Let C = {1,2, 3,4},=CxC,and define an equivalence relationRonAby(u, v)R(x, y)if and only ifuv = xy.Compute the corresponding partition ofA.LetA — {a,b, c, d, e, f}andRbe the relation onAdefined by’101010‘01 01 00A/T1 01 01 0M i ? _o i o i o o -1 01 01 0000001(a) ProveRis an equivalence relation.(b) Give the partition ofAcorresponding toR.LetB —{1,2, 3,4, 5} andRbe a relation onBwhose digraph is given in Figure 3. Define arrays VERT,TAIL, HEAD, and NEXT, describingRas a linked list.Give a linked list representation of the relation given by the matrix in Question 20.The following arrays describe a relationRon the setA ={1, 2, 3, 4, 5}. Draw the digraph ofR.VERT= [4, 2, 7, 1, 9]TAIL= [ 4 , 2 , 2 , 1, 1, 1 , 3 , 3 , 5,5, 1]HEAD= [2, 3, 5, 2, 1, 5, 2, 4, 5, 4, 4]NEXT= [0, 3, 0, 5, 6, 11, 8, 0, 10, 0, 0]LetA ={a, 6, c,d}, B ={1, 2, 3}, andC —{□,A, O } .LetR,andSbe the following relationsfromAtoBand fromBtoC,respectively.R= {(a, 1), (a, 2), (6, 2),(b,3), (c, 1),(d,3),(d,2)}S= {(1,□),(2, A), (3, A), (1, O ) } .(a) Is (6, A) eSoR?(b) Is (c, A) GS o RR(c) ComputeSoR.LetA — B —the set of real numbers. LetRbe the relation< andSbe the relation> .Describe (a)R n S ;(b)R U S .LetA— the set of all people in the Social Security database. LetaRbif and only ifaandbreceive thesame benefits; letaSbif and only ifaandbhave the same last name. DescribeR n S .LetR.be a relation fromAtoB.prove that(a) Dom(J?- 1) -Ran(B).(b) RanT1) = Dom().21.22.23.24.25.26.27.1 1 011 1 00001 001 01LetRbe a relation defined by=28.(a) Give MR-i.LetRbe a relation on a setA.(b) Give M.29.(a) Prove that ifRis transitive, thenR1is transitive.(b) Prove that if Dom(7?) =A,thenRo R~lis reflexive.Page 12Discrete Mathematical Structures

Loading page image...

LetRand 5 be relations defined by the matrices30.01001101111001111 01 101 011 01 01 1 01Ms(b) Give Mfl-.ns.(d) GiveM52 and Moo.(a) Give MEU£.(c) GiveUsing the digraph in Figure 4, give(a) the associated matrix and (b) the matrix of the transitive closure of the relation.31.2Figure 4LetRbe a relation defined by the digraph in Figure 5. Use Warshall's algorithm to find thematrix of the connectivity relation based onR.32.2Figure 5110001001000001 1 00000010000010000011LetRbe a relation defined by the matrixMj? =33.Using Warshall's algorithm, compute the matrix of the transitive closure ofR.34.LetRand 5 be relations on a setAdescribed by the matrices’1001o''01110010101001011010andMs='1011010111111100100110001Use Warshall's algorithm to compute the transitive closure ofRUS.Chapter 5 Test Items1.Let ,4 ={a, b, c, d}, B —{1,2, 3}, andS —{(a, 1),(b,1), (c, 2),(b,3)}.IsSa function? Is S-1a function? Explain your answers.2.L e t y 4 = 5 = R.Letf: ABbe the function defined by /(a?)— 3x— 4.(a) Show thatfis one to one and onto.(b) F i n d /-1.3.Prove that iff: ABandg: BCare one-to-one functions, thengofis one to one.4.Prove that iff: ABandg: BCare onto functions, thengofis onto.Page 13

Preview Mode

This document has 176 pages. Sign in to access the full document!

Report

Study Now!

Document Details

Related Documents

AP Calculus AB Scoring Guide Unit 6 Progress Check

Clinical Psychologist

Module 4 Matrices

MATH 1324 Homework 5 Answers

Ap progress 1 5 all 5

The Fundamental Theorem of Calculus and Definite I

AP Calculus AB Scoring Guide

Investigating the Rising Cost of MTA Transit Fare

Module 11 Geometry

AP Calculus AB Unit 5 Progress Check Scoring Guide

Company

Explore

Study Tools