离散数学及其应用第六版答案

离散数学及其应用第六版答案，偶数答案
McGraw-Hill higher education A Division of The McGraw-Hill Companies Instructor's Resource Guide for DISCRETE MATHEMATICS AND ITS APPLICATIONS. FIFTH EDITION KENNETH H, ROSEN Published by Mc Graw-Hill Higher Education, an imprint of The McGraw-Hill Companies, Inc, 1221 Avenue of the Americas, New York, NY 10020. Copyright o The McGraw-Hill Companies Inc, 2003, 1999, 1995. All rights reserved The contents, or parts thereof, may be reproduced in print form solely for classroom use with DISCRETE MATHEMATICS AND ITS APPLICATIONS, provided such reproductions bear copy right notice, but may not be reproduced in any other form or for any other purpose without the prior written consent of The McGraw-Hill Companies, Inc, including, but not limited to. in any network or other electronic storage or transmission, or broadcast for distance learnin This book is printed on acid-tree paper 234567890 CUS CUS09876543 ISBN0-07-247480-7 www.mhbe.com reface This Instructor's Resource Guide for Discrete Mathematics and Its Applications, fifth edition, consists of six items that an instructor of a course in discrete mathematics using the text should find useful The bulk of this guide consists of solutions to all the even-numbered exercises the text, and thus complements the Student Solutions Guide for Discrete Math ematics and Its Applications, fifth edition, which contains solutions to the ode numbered exercises. It is assumed that the user of the present manual has access to that Guide as well. The solutions presented here are not necessarily the on ways of solving these problems, of course, nor are the answers unique in all cases These are complete solutions, although they are somewhat less expository than the student-oriented solutions in the student solutions guide Several detailed course outlines are shown, for courses with different emphases and different student backgrounds and ability levels. These suggested syllabi include courses with a mathematics emphasis, courses with a computer science emphasis one-term courses, and two-term courses To aid instructors in moving from the fourth edition to the fifth edition, we have provided tables showing where material and exercises appearing in the fourth edition can be found in the fifth edition This Guide contains detailed teaching suggestions for instructors. There are chap ter overviews, followed by remarks on each section. Goals and prerequisites are stated, advice on teaching the section is presented and comments on the exercise sets are offered Two sample tests are provided for each chapter and two sample final examina- tions-the first easier than the second in each case. Solutions for the test questions are included. Instructors can draw on these sample tests when constructing tests for their own classes, or they can provide them to students as samples with which to prepare for the actual exams Finally, this Guide contains a test bank of over 1300 exam questions. Answers are included In addition to this Guide, you will find the website created for Discrete Mathematics and Its applications an invaluable resource. Included at the site are a web guide to discrete mathematics that provides useful links keyed to the text, additional examples and exercises, a bulletin board. a shared course material link where other instructors nsing this tect have posted their lecture notes, and other material you may find useful Theaddressiswww.mhhe.com/rosen 1ll I want to thank Jerry Grossman for his extensive advice and assistance in the prepa ration of this Guide, Paul Lorczak, Georgia Mederer, Lyndon Weberg, and Suzanne Zeitman for double-checking the solutions, and students at Monmouth College and Oakland University for their input on preliminary versions of solutions to the exer cises. The test bank was produced by John Michaels, for whose excellent work I am most grateful. Some questions and answers for this bank were contributed by Tao Jiang, Nancy Kinnersley, Antonette Logar, Thomas Roe, Zoltan Szekely, and Bharti Temkin, to whom i also extend my appreciation. It is possible that there are a few errors here, despite our best efforts at eliminating them. I would appreciate hearing about all that you find, be they typographical or mathematical. Any other comments that will improve subsequent editions of this book are always greatly appreciated. You can locate the link for reporting possible errors intheInformationCenterwithinthewebsitewww.mhhe.com/rosen Kenneth h. rosen Contents Preface Solutions for even-numbered exercises CHAPTER 1 The Foundations: Logic and Proof, Sets, and Functions 1.1 ogIc 2 Propositional Equivalences 7 1.3 Predicates and Quantifiers 11 1.4 Nested Quantifiers 16 1.5 Methods of proof 21 1. 6 Sets 28 1.7 Set Operations 29 8 Functions 32 Supplementary Exercises for Chapter 1 40 CHAPTER 2 The Fundamentals: Algorithms, the Integers, and Matrices 44 2. 1 Algorithms 2. 2 The Growth of Functions 50 2.3 Complexity of algorithms 55 2.4 The Integers and Division 57 2.5 Integers and algorithms 61 2.6 Applications of Number Theory 64 2.7 Matrices Supplementary Exercises for Chapter 2 74 CHAPTER 3 Mathematical Reasoning, Induction, and Recursion 80 3.1 roof Strategy 80 3.2 Sequences and Summations 83 3.3 Mathematical Induction 87 3.4 Recursive Definitions and Structural induction 95 3.5 Recursive algorithms 100 3.6 Program Correctness 105 Supplementary Exercises for Chapter 3. 106 CHAPTER 4 Counting 116 4.1 The Basics of Counting 116 4.2 The Pigeonhole Principle 121 4.3 Permutations and Combinations 123 4.4 Binomial coefficients 27 4.5 Generalized Permutations and Combinations 130 4.6 Generating Permutations and Combinations 133 Supplementary Exercises for Chapter 4 134 CHAPTER 5 Discrete Probability 139 5.1 An Introduction to Discrete Probability 139 5.2 Probability The Expected value and variance 146 upplementary Exercises for Chapter 5 149 CHAPTER 6 Advanced Counting Techniques 153 6.1 Recurrence relations 153 6.2 Solving Recurrence Relations 162 6.3 Divide-and-Conquer algorithms and Recurrence relations 168 6. 4 Generating Functions 172 6.5 Inclusion-Exclusion 183 6.6 Applications of Inclusion-Exclusion 185 Supplementary Exercises for Chapter 6 186 CHAPTER T Relations 189 7. 1 Relations and Their Properties 189 7.2 n-ary Relations and Their Applications 194 7.3 Representing Relations 196 7. 4 closures of relations 199 7.5 Equivalence Relations 202 7.6 Partial Orderings 206 Supplementary Exercises for Chapter 7 211 CHAPTER 8 Graphs 8.1 Introduction to Graphs 214 8.2 Graph Terminology 215 8.3 Representing Graphs and Graph Isomorphism 220 8.4 Connectivity 226 8.5 Euler and hamilton Paths 230 8. 6 Shortest-Path Problems 233 8.7 Planar Graphs 236 8.8 Graph Coloring 238 Supplementary Exercises for Chapter 8 241 CHAPTER 9 Trees 246 9.1 Introduction to Trees 246 9.2 Applications of Trees 250 9.3 Tree Traversal 258 9. 4 Spanning Trees 262 9.5 Minimum Spanning Trees 267 Supplementary Exercises for Chapter 9 269 CHAPTER 10 Boolean Algebra 274 10.1 Boolean Functions 274 10.2 Representing Boolean Functions 277 10.3 Logic G 279 10.4 Minimization of Circuits 283 Supplementary Exercises for Chapter 10 291 CHAPTER 11 Modeling Computation 294 11.1 Languages and Grammars 294 11.2 Finite-State Machines with Output 298 11.3 Finite-State Machines with No output 301 11. 4 Language Recognition 304 11.5 Turing Machines 307 Supplementary Exercises for Chapter 11 308 APPENDIXES 311 Appendix 1 Exponential and Logarithmic Functions 311 Appendix 2 Pseudocode 311 Suggested Syllabi 312 Migrating from the Fourth Edition to the Fifth Edition 316 Teaching Suggestions 324 C matter 324 Chapter 2 328 Chapter 3 332 Chapter 4 337 Chapter 5 340 Chapter 6 341 CcC hapter 7 345 hapter 8 348 hapter 9 351 Chapter 10 354 Chapter 11 356 Appendixes 358 Sample Tests for an Introductory Course in Discrete Mathematics 360 Chapter 1 361 Chapter 2 365 Chapter 3 369 Chapter 4 373 Chapter 5 377 Chapter 6 381 Chapter 7 385 Chapter 8 389 Chapter 9 393 Chapter 10 397 Chapter 11 401 Final Examinations 405 Test Bank for Discrete Mathematics 411 Chapter 1 411 Chapter 2 437 Chapter 3 447 Chapter 4 453 Chapter 5 464 Chapter 6 468 Chapter 7 479 Chapter 8 487 Chapter 9 499 Chapter 10 510 Chapter 11 517 Section 1.1 Logic CHAPTER 1 The Foundations: Logic and Proof, Sets, and Functions sEC山oN11Logc 2. Propositions must have clearly defined truth values, so a proposition must be a declarative sentence with no free variables a) not a proposition-a command b)Not a proposition-a question c)A proposition that is false, as anyone who has been to maine knows d) not a proposition-its truth value depends on the value of a e) Not a proposition-its truth value depends on the value of a(for example, if 3=2, then the statement is true f)On the surface, this should probably be classified as not a proposition, since it contains free variables. If, for example, r and z are both Bill Clinton, then it is not clear what the truth value would be. On the other hand, if it is assumed that the variables are all meant to represent real numbers, then one could make the observation that for all possible values of the variables, the statement is true. Hence we could call this a(true) roposition 4. a)i did not buy a lottery ticket thi b) Either I bought a lottery ticket this week or [in the inclusive sense! I won the million dollar jackpot on Frid c) If I bought a lottery ticket this week, then i won the million dollar jackpot on Friday d)i bought a lottery ticket this week and i won the million dollar jackpot on friday e)i bought a lottery ticket this week if and only if I won the million dollar jackpot on Friday. f)If i did not buy a lottery ticket this week, then i did not win the million dollar jackpot on Friday. g i did not buy a lottery ticket this week, and i did not win the million dollar jackpot on friday h)Either i did not buy a lottery ticket this week, or else i did buy one and won the million dollar jackpot on frida 6. a The election is not decided ) The election is decided, or the votes have been counted c)The election is not decided, and the votes have been counted d)If the votes have been counted then the election is decider e) If the votes have not been counted, then the election is not decided f If the election is not decided then the votes have not been counted g The election is decided if and only if the votes have been counted h) Either the votes have not been counted, or else the election is not decided and the votes have been counted Note that we were able to incorporate the parentheses by using the words either and else 8. a)If you have the flu, then you miss the final exam