Skip to content
Textbook Guides

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

Maximize your understanding with Discrete Mathematical Structures (Classic Version), 6th Edition Solution Manual, a detailed solutions manual for all your textbook problems.

Preview 16 of 176 pages

See the first 16 pages exactly as they appear in the document.

  1. Page 1
    Read page 1 as text

    DISCRETE MATHEMATICAL STRUCTURES Sixth Edition KOLMAN BUSBY ROSS RESOURCE MANUAL SHARON CUTLER ROSS Georgia Perimeter College

  2. Page 2
  3. Page 3
    Read page 3 as text

    CONTENTS Notes to the Instructor............................................................................................................................................. 1 Chapter Notes Chapter 1.......................................................................................................................................................... 2 Chapter 2.......................................................................................................................................................... 2 Chapter 3.......................................................................................................................................................... 2 Chapter 4.......................................................................................................................................................... 3 Chapter 5.......................................................................................................................................................... 3 Chapter 6.......................................................................................................................................................... 3 Chapter 7.......................................................................................................................................................... 3 Chapter 8.......................................................................................................................................................... 3 Chapter 9.......................................................................................................................................................... 4 Chapter 10........................................................................................................................................................ 4 Chapter 11........................................................................................................................................................ 4 Student Experiments......................................................................................................................................... 5 Sample Test Items Chapter 1 Test Items 7 Chapter 2 Test Items 8 Chapter 3 Test Items 10 Chapter 4 Test Items 10 Chapter 5 Test Items 13 Chapter 6 Test Items 15 Chapter 7 Test Items 18 Chapter 8 Test Items 20 Chapter 9 Test Items 23 Chapter 10 Test Items 25 Chapter 11 Test Items 27 Answers (Even and Odd Exercises) Chapter 1 Answers 28 Chapter 2 Answers 39 Chapter 3 Answers 53 Chapter 4 Answers 59 Chapter 5 Answers 73 Chapter 6 Answers 79 Chapter 7 Answers 91 Chapter 8 Answers 103 Chapter 9 Answers 113

  4. Page 4
    Read page 4 as text

    Chapter 10 Answers............................................................................................................................................. 122 Chapter 11 Answers............................................................................................................................................. 135 Appendix A Answers........................................................................................................................................... 138 Appendices B and C Notes................................................................................................................................. 140 Sample Test Item Answers Chapter 1 Test Item Answers 141 Chapter 2 Test Item Answers 142 Chapter 3 Test Item Answers 144 Chapter 4 Test Item Answers 145 Chapter 5 Test Item Answers 148 Chapter 6 Test Item Answers 149 Chapter 7 Test Item Answers 152 Chapter 8 Test Item Answers 155 Chapter 9 Test Item Answers 157 Chapter 10 Test Item Answers 159 Chapter 11 Test Item Answers 161 Answers for Self-Tests Chapter 1 Test Answers 163 Chapter 2 Test Answers 163 Chapter 3 Test Answers 165 Chapter 4 Test Answers 165 Chapter 5 Test Answers 166 Chapter 6 Test Answers 167 Chapter 7 Test Answers 168 Chapter 8 Test Answers 170 Chapter 9 Test Answers 172 Chapter 10 Test Answers 172 Chapter 11 Test Answers 174

  5. Page 5
    Read page 5 as text

    CHAPTER NOTES CHAPTER 1 FUNDAMENTALS Sets 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 examples as well as of basic ideas. Material on base n representations gives us a tool for beginning a discussion of cryptology. The last section pulls together some general ideas such as properties of operations and helps students see the similarities among the topics discussed earlier in the chapter. There is a danger that students will see discrete mathematics as a hodge-podge of unrelated ideas. By comparing and contrasting sets, integers, and matrices 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 in discrete 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 distributive property does not come easily to most students. Working from familiar situations such as integer arithmetic and sets facilitates this change. Although they are formally defined in Chapter 5, functions are used informally here in the discussion of computer representations of sets. CHAPTER 2 LOGIC While a number of discrete mathematics texts begin with logic, we chose to cover in Chapter 1 topics that are both more familiar and more concrete for students. This choice leads to some small inconsistencies in Chapter 1 where students are asked to prove some simple statements. However, the students have seen proofs before, so this is not a serious problem. Swapping the order of the two chapters is possible if one feels strongly about beginning with logic. In a course taught for computer science majors, it is easy to tie much of Chapter 2 to writing guards for loops and proving code. Students with programming experience will also have experience in determining 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 on them 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 earlier work with implication. In particular, the induction step does not say "Assume that P(/c) is true." Students frequently stumble over the word "assume" and do not see why they can not just "assume P(n)" and be done. The strong form of mathematical induction is also included. Both forms of induction recur throughout the text both in examples and in exercises. Two new sections provide more experiences with proofs and problem solving. In Section 2.5 we explore how mathematical statements are created and give more proof practice. By engaging students in the writing of mathematical 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 several problems in terms of an older problem. CHAPTER 3 COUNTING We use the notations n P r and n C r for the number of permutations and combinations, respectively, of n objects taken r at a time. These notations are the same as, or similar to, those used on many calculators and avoid the anomalous (™) which is often a problem for students. Permutations and combinations with repeats are also discussed. Counting techniques are necessary for algorithm analysis. Another tool for algorithm analysis is an understanding of recurrence relations. A section in this chapter covers the basic ideas of how to solve linear homogeneous recurrence relations. Recurrence relations are also one of a number of uses and examples of recursion throughout the text. We believe that students need to spend time with this concept and consequently we have woven it through the book. A brief introduction to probability provides an application of the counting methods discussed as well as concepts needed for future discussions; e.g., probabilistic algorithms. Page 2 Discrete Mathematical Structures

  6. Page 6
    Read page 6 as text

    CHAPTER 4 RELATIONS AND DIGRAPHS This 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, in that representation, whether a relation has a specified property. The use of multiple representations enables students 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 to ordered 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 and exercises. The idea of an equivalence relation and its corresponding partition is a powerful one developed in this chapter 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 proof skills. CHAPTER 5 FUNCTIONS Functions are presented as a special type of relation. One-to-one correspondence is a key idea for later work and appears here as a function with certain characteristics. One-to-one functions are applied to the creation of substitution codes. The use of mod functions with check digits is also presented. Special emphasis is given to functions 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 of a characteristic function to define a fuzzy set and have students revisit set operations and proofs using characteristic functions. The chapter continues with a low-level introduction to the growth of functions including big-Oh notation and 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 6 ORDER RELATIONS AND STRUCTURES We return in this chapter to the theme of types of relations, namely partial orders (posets), lattices, and Boolean algebras. Section 7.1 contains the first appearance of isomorphism, a concept of great use in later sections and chapters. Lattices and Boolean algebras are also a way to return to the idea of a mathematical structure introduced in Chapter 1. The connections among Boolean algebras, Boolean functions, and circuit design are developed. Although circuit design and simplification are rarely done by hand any more, we think some experience with Karnaugh maps and basic ideas in this field is beneficial for students. A symbolic version of Karnaugh maps is included in the exercises. CHAPTER 7 TREES Trees are presented as yet another type of relation with (naturally) most emphasis on their graphical representation. The groundwork is laid in this chapter for the use of a tree as an abstract data type. Huffman code trees introduce coding for efficiency. This relates to earlier (and later) discussions of coding for security and coding for error detection and correction. The two versions of Prim's algorithm are synthesized in a matrix-based method for weighted graphs. Recursive procedures for traversing a tree bring the student to the idea of recursion again. Spanning trees and minimal spanning trees illustrate for the student ways in which trees are natural models for real-world situations. By this time students have seen a number of algorithms and have developed some intuition about recursion, backtracking, greedy algorithms, and other standard programming tools. CHAPTER 8 TOPICS IN GRAPH THEORY Graphs, in particular digraphs, are used to represent relations in Chapter 4, but students are likely to see graphs used in a number of other contexts. This chapter looks at graphs as entities in their own right. As with other topics, our aim is to present a solid foundation, but to leave deep results to later courses. Page 3

  7. Page 7
    Read page 7 as text

    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 existence theorems. Sections on transport networks and matching problems offer another context for the application of graph theory. 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 9 SEMIGROUPS AND GROUPS This chapter is another extension of the ideas in Section 1.6 on mathematical structures. We believe that students 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 deal with a different version is useful. The main structures in this chapter are semigroups and groups. Many ideas and examples 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 been assigned. Equivalence relations reappear as congruence relations and isomorphism is redefined to preserve operations. A final section gives a brief introduction to rings and fields. In particular, we develop for use in Chapter 11. CHAPTER 10 LANGUAGES AND FINITE STATE MACHINES Compiler and theory of languages courses for computer science majors generally expect students to absorb very quickly formal presentations of languages and topics such as parsing and derivation. The intent of this chapter is to lay some groundwork for these courses, and others. Approaching a phrase structure grammar as one more mathematical structure lets students use experience gained earlier in the course to aid in acquiring these concepts. 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 nice blend of earlier work — semigroups, graphs, functions, and equivalence relations. CHAPTER 1 1 GROUPS AND CODING This is an authors' choice chapter. There are a number of topics appropriate for courses using this text that would have allowed us to apply ideas from earlier chapters. In earlier editions we focused on codes for error detection and correction. Now we also present the culmination of the cryptology (codes for security) thread that begins in Chapter 1. These ideas use many topics from earlier chapters and are inherently interesting to students. Page 4 Discrete Mathematical Structures

  8. Page 8
    Read page 8 as text

    STUDENT EXPERIMENTS Extended-time assignments in which students, individually or collaboratively, investigate, conjecture, and justify are an excellent way for students to take ownership of the mathematics they study. Each of the experiments is designed for a 10—14 day time frame. Some experiments extend concepts in the text; others preview topics. All require students to write about the mathematics they have done. A typical grading rubric is the following. This assignment is worth a maximum of 35 points of the 100 point experiment grade. Be sure to answer each question using standard written English. Points will be distributed as follows: 1 0 points clarity and completeness of presentation 15 points correctness of computations and mathematics 10 points style and neatness You 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 of questions and only tiny hints. What students may need most is to hear (repeatedly perhaps) that these are doable assignments. Experiment 1 when goals weighted voting systems after Section 1 .1 present a novel application of power sets begin the course with something fresh Experiment 2 when goal finite geometries after Chapter 2 ' provide practice in logical problem solving and proving conjectures Experiment 3 when goals Markov chains after Section 3.4 introduce the concept of a Markov chain apply probability ideas Experiment 4 when goals compatibility relations after Section 4.5 extend idea of equivalence relation reinforce connection between equivalence relation and partition build parallel structure for compatibility relation and covering investigate inheritance of properties Experiment 5 when goals simple algorithm analysis after Section 5.3; also needs Appendix A and Section 3.5 perform simple algorithm analysis introduce two simple search algorithms utilize recurrence relations Experiment 6 when goals Petri nets after Section 6.6 adapt digraphs to a new use introduce the basic concepts of operating systems Page 5

  9. Page 9
    Read page 9 as text

    Experiment 7 when goals B-trees after Section 7.3 introduce concept of a B-tree investigate characteristics of B-trees Experiment 8 when goal cliques after Section 8.6, but if question 7 is omitted, it may be assigned after Section 4.4 provide practice with relations, digraphs, and graphs provide another method for determining x( ) Experiment 9 when goals subgroups after Section 9.4 introduce order of an element investigate the relationship between an element's order and the group's order investigate the relationship between the orders of subgroups and groups Experiment 10 when goals pushdown automata after Section 10.3 preview concept of a pushdown automaton use stack operations of push and pop Experiment A when goals modular arithmetic after Section 1.6, but before Chapter 9; needs Example 4, Section 4.5 provide experience with modular arithmetic develop criteria to determine if has unique solutions to certain equations build examples of groups for later use Experiment B when Towers of Hanoi after Section 3.5, but if question 4 is restated, students need not have seen recurrence relations goals give experience with recursion practice mathematical induction proofs Experiment C when goals Catalan numbers after Section 5.2 create models for the Catalan numbers demonstrate the power of modeling as a problem-solving tool practice proof techniques Page 6 Discrete Mathematical Structures

  10. Page 10
    Read page 10 as text

    Sample Test Items Chapter 1 Test Items Let A = {x | x = 3m, m G Z}, B = {0, 2, 4, 6, . . . }, C = {y | y 2 < 150}, and D = {y | y 2 + 4 = 0}. (a) Tell if each of the following is true or false. (i) {6, 12} C A (ii) {6, 12} C c (m) B C A (iv) D C 0 (b) Tell if each of the following is true or false. (t) D U A C c (u) A n D = D (Hi) B A A C C (iv) C C A U B Let 4 = {1, 2, 3, 4}, B = {x | x G Z + and x 2 < 16}, C = {1,2, 3}, D = {x \ x e Z and x 2 = 4 } , and E = { x | x G Z and x 2 — — 4}. Tell if each of the following is true or false. (a) A = C (b) A C B (c) C G B ( 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. Let S — {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 = S Let 4 = {x | x = 3n, n e Z + }, B = { x \ x = 4m, m G Z + }, C = {t 1 1 - 2n — 1, n G Z + }, and D — {s | s = 2k, k G Z}. Use Z as the universal set and compute: (a) A A B ( b ) A © C ( c ) B (d) D - C (e) B A D LetJ = {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 if A Cl B = A U B, then A = B. The records of 200 students at Verysmall College show the following courses taken: 104 students took Latin 46 students took Latin and Greek 9 students took all three languages 103 students took Greek 35 students took Sanskrit 24 students took Greek and Sanskrit 28 students have taken none of these languages (a) How many students took only Greek? (b) How many students took only Latin and Sanskrit? Prove that A U (A Cl B) = A. Write a formula for the nth term of the sequence 2, 5, 8, 11, 14, . . . . Define a sequence as follows: a 0 = 2, cq = 3, a n = 2a n 1 — Sa n _ 2 - Give the first six terms 7. 8. 9. 10. 11. 12. of this sequence. Let U — {m, n, o, p, q, r, s, t, u, v}, A = {o, u}, B = {m, o, s, t}, C = {n, p, r}, and D = {n, o, r, t, u, u}. Represent each of the following sets by an array of zeros and ones. (a) A U C (b) B A D (c) C U (A A D) (d) (A A B) U C Let I = {0, 1}. Describe the regular subsets of 7* corresponding to the following regular expressions. (a) (01)*10*1 (b) 110*10* ( c ) ( l V 0 ) * 0 1 1 (d) 0*10*(10*10*)* Let I — {a, b, c}. In each part below is listed a string in 7* and a regular expression over 7. For each, state whether the string belongs to the regular set corresponding to the expression. (a) abc abc* (b) abc (a*b V c)* (c) abc (a V b)*c (d) abc (a5)* V c Compute GCD(1350, 297) and write it as s(1350) + i(297). Use the Euclidean algorithm to compute GCD(4389, 7293). Compute LCM(180, 294). Let g be 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

  11. Page 11
    Read page 11 as text

    Write the base 8 expansion of each of the following numbers. (a) 12 (b) 139 (c) 486 Write the base 10 expansion of each of the following numbers. (a) (123)5 Let A = (c) (1011011)2 1 4 (b) (71) 8 and B = 6 3 6 - 2 4 - 3 5 0 . Compute, if possible, each of the following. 19. 20. 21. A T 6' 3 (c) 1 4 (b) BA and B (a) AB Let A = 4 - 3 6 - 2 5 0 . Compute, if possible, each of the following. 22. (a) A + B (b) A T B (c) A- 1 23. Describe all 2 x 2 matrices A such that A 2 is symmetric. '1 0 1 r ’0 0 1 o' 0 1 0 1 and D = 0 1 0 0 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 1 . Compute each of the following. Let C — 24. (a) C 0 D (b) C V D (c) C A D 25. Define a b = y and aV6 = a — b. Let R = (even integers, □ , V). Show that R is closed with respect to □ . 26. Let R = (even integers, □ , V) as defined in Question 25. Give the identity element, if one exists, for: (a) (b) V 27. Let R be the mathematical structure in Question 25. Show that R has a distributive property. 28. Show that A C A U B. 29 Show that A Cl B C A. 30. Show that A — A = { } . 31. Let a and b be integers. Show that if p is a prime such that p | ab, then p | a or p | b. 32. Let A be a Boolean matrix, (a) Show that A V A = A. (b) Show that A A A = A. Chapter 2 Test Items 1. Let p: Jack is nimble, q: Jill is quick, and r: Jose jumped over the candlestick. (a) Write each of the following in terms of p, 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 (p A r) (zzz) ~ (p V q) 2. Determine the truth value for each of the following statements where x and y are integers. (a) Vx By x + y is even. (b) Bx By x + y is 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 A r) A p) V ( ~ (p A r) V q) . 7. Let p: Jack is nimble, q: Jill is quick, and r: 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 8 Discrete Mathematical Structures

  12. Page 12
    Read page 12 as text

    (b) Write an English sentence that corresponds to each of the following. (0 ( ~ q) => p (H) M = > (jii) (rV q) O p 8. If p => q is true, what is the truth value of (pVg) => ~ ql Explain your reasoning. 9. Make a truth table for the statement ( ~ p) A (p => q). 10. Let p: If you do your homework and you ask questions, then you will succeed in discrete mathematics. (a) Define simple statements and use them to write p in symbolic form. (b) Give the converse of p in English and in symbolic form. (c) Give the contrapositive of p in 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 _____________ . r p 13. Prove or disprove by giving a counterexample that the sum of any three consecutive even integers is divisible by 6. 14. Prove or disprove by giving a counterexample that the sum of any three consecutive odd integers is divisible by 3. 15. Prove that the following statement is true by using mathematical induction. _L _i_ _L _1 _____ I ______ 1 _____ - n 1-3 3-5 ( 2 n - l ) ( 2 n + l ) 2n+l 16. Prove that I 3 + 2 3 + 3 3 + • ■ ■ + n 3 = - . 17. Prove that 1 + 5 + 9 4 ----- + (4n — 3) = n(2n — 1). 18. Prove that 5 n — 3 is divisible by 2. 19. Prove that 1 + 2 + 34----- + n < . 20. Prove that n 5 — n is divisible by 5 for n > 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 input X is a positive integer. FUNCTION F(A) 1. Z<- 1 2. C<r- 1 3. WHILE (C < X) a. Z < — Z + 2C + 1 b. C < - C + l 4. RETURN Z END OF FUNCTION F (a) Prove that Z = C 2 is a loop invariant and give the value of Z when the loop terminates. (b) Describe what the function F produces. Page 9

  13. Page 13
    Read page 13 as text

    Chapter 3 Test Items 1. 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 CLEVELAND 2. 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 many different 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 seven members from the upper house. If there are 29 eligible members of the lower house and 18 eligible members of the upper house, how many different committees are possible? 7. Prove that n P r = r ■ n _]P r _L + n - i P r . 8. Prove that m + n C r = m C i ' n C r - i - i=l 9. 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 least people in a city of 2,384 people have the same pair of first and last initials. 11. Suppose your history book has 648 pages and 14 chapters. Prove that at least one chapter has 45 pages. 12. A baker has decorated the top of a cake with 52 small hard candies. If the cake is cut into 12 equal-size pieces, at least one piece must have candies 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 the probability 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 at random 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 Toads and 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 to represent the group if (a) one representative is chosen? (b) two representatives are chosen? 18. Let p(A) — 0.24, p(B} = 0.68, and p(A Pl 5) = 0.15. (a) What is p(A U 5)? (b) Are A and B mutually exclusive events? Justify your answer. 19. Find an explicit formula for the sequence defined by — 3, a n = 3a n - 1 + 1. 20. Solve the recurrence relation b n = — 15b n _ 2 , = 2, 6 2 = 16. 21. Solve the recurrence relation c n = — Sc -j — 16c n _ 2 , cj = — 1, C2 = 8. 22. Develop a formula for the solution of a recurrence relation of the form a n = a n _ 1 + m, a x = m. Chapter 4 Test Items 1. Let A be the set of positive divisors of 15 and B — {a, b, c}. (a) What is \A x B |? (b) List A x B. 2. Prove that if A C B, then ,4 x C C B x C. 3. Give all two-element partitions of {a, b, c, d}. Page 10 Discrete Mathematical Structures

  14. Page 14
    Read page 14 as text

    Often email records show the date received, the sender, the subject, message size, and the status of the message (read, deleted, et al.). Use the operations select, project, and standard set operations 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? Let 5 = {a, b} . How many relations are there on F’(S)? Let A = {a, b, c, d} and R be a relation on A whose matrix is Mp = 1 0 1 0 0 0 1 1 1 1 1 0 1 0 0 0 4. 5. 6. 7. 8. 9. (a) Give R as a set. (b) Draw the digraph of R. Let B = {1,2, 3,4, 5} and R be the relation on A whose digraph is given in Figure 1 . (b) GiveMtf. (a) Give R as a set. 1 X Figure 1 Let C = {3,7, 11}. Define a relation on C by xRy if and only if x — y < 4. (a) Draw the digraph of R. (b) GiveM#. Let A = {1,2, 3,4, 5} and R be the relation on A whose digraph is given in Figure 2. (a) List all paths of length 3. . (b) List all cycles. Figure 2 Using the relation R whose digraph is given in Figure 2, (a) Give the matrix of R 2 . (b) List the elements of 7? 4 . (c) Draw the digraph of R 3 . Let 5 = {1, 2, 3, 4} and?? = {(2, 4), (4, 3), (3, 2), (2, 1), (1, 1)}. (a) Draw the digraphs of R and R 2 . (b) Give Mj? and M . Fl 1 0 11 10. 11. 12. 13. 14. (c) Give Mtfoo . Let R be a relation defined by Mj? = 0 1 0 1 (b) Give Mj?oo (a) Give M . Determine whether the relation R on the set A is reflexive, irreflexive, symmetric, asymmetric, antisymmetric, or transitive, where A = {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)}. Let D = {1,2, 3,4, 5} and R be the relation on D whose matrix is 1 0 0 0 1 0 0 0 1 0 1 0 1 0 1 0 0 0 0 1 1 0 1 0 0 AU? = Determine whether R is reflexive, irreflexive, symmetric, asymmetric, antisymmetric, or transitive. Page 11

  15. Page 15
    Read page 15 as text

    15. Let B = {1, 2, 3, 4, 5} and R be a relation on B whose digraph is given in Figure 3. Determine whether R is reflexive, irreflexive, symmetric, asymmetric, antisymmetric, or transitive. Figure 3 Explain why we can define the symmetric closure of a relation, but not the asymmetric closure of a relation. 16. 17. 18. 19. 20. Let t be a fixed real number. Define a relation on R as follows: xRy if and only if there exists an integer m such that x — y = mt. (Note that m will depend on x and y.) Prove that R is an equivalence relation. Let A = x Z + , and define R on A as follows: (a?, y)R(u, v) if and only if 2 | (x — u) and 3 | (y — u). (a) Prove that R is an equivalence relation. (b) Compute [(5, 4)], the equivalence class of (5, 4). Let C = {1,2, 3,4}, = C x C, and define an equivalence relation R on A by (u, v)R(x, y) if and only if uv = xy. Compute the corresponding partition of A. Let A — {a,b, c, d, e, f} and R be the relation on A defined by ’1 0 1 0 1 0‘ 0 1 0 1 0 0 A/T 1 0 1 0 1 0 M i ? _ o i o i o o - 1 0 1 0 1 0 0 0 0 0 0 1 (a) Prove R is an equivalence relation. (b) Give the partition of A corresponding to R. Let B — {1,2, 3,4, 5} and R be a relation on B whose digraph is given in Figure 3. Define arrays VERT, TAIL, HEAD, and NEXT, describing R as a linked list. Give a linked list representation of the relation given by the matrix in Question 20. The following arrays describe a relation R on the set A = {1, 2, 3, 4, 5}. Draw the digraph of R. 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] Let A = {a, 6, c, d}, B = {1, 2, 3}, and C — { □ , A, O } . Let R, and S be the following relations from A to B and from B to C, 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) e S o R? (b) Is (c, A) G S o RR (c) Compute S o R. Let A — B — the set of real numbers. Let R be the relation < and S be the relation > . Describe (a) R n S ; (b) R U S . Let A — the set of all people in the Social Security database. Let aRb if and only if a and b receive the same benefits; let aSb if and only if a and b have the same last name. Describe R n S . Let R. be a relation from A to B. prove that (a) Dom(J? - 1 ) - Ran(B). (b) Ran T 1 ) = Dom( ). 21. 22. 23. 24. 25. 26. 27. 1 1 0 1 1 1 0 0 0 0 1 0 0 1 0 1 Let R be a relation defined by = 28. (a) Give M R -i . Let R be a relation on a set A. (b) Give M . 29. (a) Prove that if R is transitive, then R 1 is transitive. (b) Prove that if Dom(7?) = A, then Ro R~ l is reflexive. Page 12 Discrete Mathematical Structures

  16. Page 16
    Read page 16 as text

    Let R and 5 be relations defined by the matrices 30. 0 1 0 0 1 1 0 1 1 1 1 0 0 1 1 1 1 0 1 1 0 1 0 1 1 0 1 0 1 1 0 1 M s (b) Give Mfl-.ns. (d) GiveM 5 2 and M oo. (a) Give M EU £. (c) Give Using the digraph in Figure 4, give (a) the associated matrix and (b) the matrix of the transitive closure of the relation. 31. 2 Figure 4 Let R be a relation defined by the digraph in Figure 5. Use Warshall's algorithm to find the matrix of the connectivity relation based on R. 32. 2 Figure 5 1 1 0 0 0 1 0 0 1 0 0 0 0 0 1 1 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 1 1 Let R be a relation defined by the matrix Mj? = 33. Using Warshall's algorithm, compute the matrix of the transitive closure of R. 34. Let R and 5 be relations on a set A described by the matrices ’1 0 0 1 o' '0 1 1 1 0 0 1 0 1 0 1 0 0 1 0 1 1 0 1 0 and M s =' 1 0 1 1 0 1 0 1 1 1 1 1 1 1 0 0 1 0 0 1 1 0 0 0 1 Use Warshall's algorithm to compute the transitive closure of R U S. Chapter 5 Test Items 1. Let ,4 = {a, b, c, d}, B — {1,2, 3}, and S — {(a, 1), (b, 1), (c, 2), (b, 3)}. Is S a function? Is S -1 a function? Explain your answers. 2. L e t y 4 = 5 = R. Let f: A B be the function defined by /(a?) — 3x — 4. (a) Show that f is one to one and onto. (b) F i n d / -1 . 3. Prove that if f: A B and g: B C are one-to-one functions, then g o f is one to one. 4. Prove that if f: A B and g: B C are onto functions, then g o f is onto. Page 13

160 more pages in the full document

Unlock it once and it stays in your library, ready to chat with or turn into flashcards.

Unlock the full document

More Mathematics study materials

See all

Study this document with CramX

Once it is in your library, every tool can work from it.