Discrete Mathematics and Its Applications 7ed

The solution manual has much more detailed answers than the back of the book. It's explanations are very useful and have already came in handy with the class.PI: 1/1 P2: 1/2 OC: 1.FRONT-7T Roscll-231IT MHIAOl7-Rosun-vScls May 13. 2011 10: 21e McGraw Hill CompaniesConnectLearnraw SucceedDISCRETE MATIIEMATICS AND ITS APPLICATIONS, SEVENTII EDITIONPublishi by McGraw-Hill, a business unit uf The McGraw-Hill CuImpanuies, Ine: 1221 Aveue of theAnlericas, New York, NY 10020. Copyright g 2012 by The McGPrevious editions o 2007, 2003, and 1999. No part of this publication may be reproduced or distributcdill any lorn ur by any Itans, or stored in a database ur retrieval system, without the prior written consent ofThe McGraw-llill Companies, Inc, including, but nol limited Lo, in ally network or olher electronic storageor transmission. or broadcast for distance lcarnirSune ancillaries, including electronic and print conponents, Illay lot be available Lo cusTomers outside thUnited Statcs.This bouk is printed onl aciu-lrec paper1234567890 DOW/DOW10987654321IsRN978-407-3383095MHID0-07-3383090Vice President& Fditor-in-Chief: Marty langeExecutive FAitor: Bill StenquisrDcvclopmcnt Editors: Lorraine K. Buczek/Rose Kernansenior Marketing Manager: CulProject yer: Robin A ReedDesignCover painting: laser Johns, Berween the Clock and the Bed, 1981. Oil on Canvas (72 x 126 1/4 inches)Collection of thc artist. Photograph by Glenn Sticgclman Cover Art o Jaspcr Johns/Licensed by VAGA, Ncw York, NYSt louis, MiI ead Photo Research Coordinator: Carrie K. BurgerProduction Services/Compositor: KPK Fditorial Services/PreTeXTypeface: /0.5/12 Ties RomanPrinter R.R. Dontrelleibrary of Congress Cataloging-in-Publication Dilcth HDiscrctc mathematics and its applications /Kcnncth H. Roscn - th cdISBN-07-33830901. Mathematics. 2. Computcr scicncc-Mathcmatics. I. Titlc51l-dc22FRONT-7T Roscll-2311T MHIAO17-Rosun-v5 cs May 13. 2011 10:ContentsAbout the author viThe Companion Website xviTo the student xvii1 The Foundations: Logic and Proofs1.⊥ Propositional Lof pre1.3 PropoEquivalenCes1. 4 Predicates and QuanTifiers.366 Rules of ir1.7 Introduction to proofsEnd-of- Chapter material2 Basic Structures: Sets, Functions, Sequences, Sums, and Matrices. 1151152.2 Sct Opct2.3 Functions2. 4 Sequences and Summations1562.6 MatricesEnd-of-Chapter Material3 Algorith3. 2 The Growth of functionsgorithms218End-of-Chapter Ma4 Number Theory and Cryptography∴∴Divisible4.2 Integer Representations and Algorithms4 3 Primes and greatest common divisors4.5 Applications of CongruencesEnd-of- Chapter materialFRONT-7T Roscll-231IT MHIAOl7-Rosun-vScls May 13. 2011 10-5 Induction and recursion3115.1 Mathenatical Indt5.2 Strong Induction and well-Orderin3335.3 Rccursivc Dcfinitions and Structural Induction5.5 Program6 Counting·····;··3856.1 The b:e Basics of Counting6.2 The Pigeonhole Principlc6.3 Permutations and Combinations6.5 Generalized permutations and combinations6. 6 Gcncrating Permutations and ComhinationsEnd-of-Chapter Materiat7 Discrete Probability4457.2 Probabilily Theory7.3 BaycsThcorcm7.4 Expcctcd Valuc and Variance477End-of-Chapter Materi8 Advanced Counting Techniques....···;····8. 1 Applications of Recurrence Relations5018. 2 Solving linear recurrence relations148.3 Dividc-and-Conqucr Algorithms and Recurrence Rclation8.4 Generating Functio8.5 Inclusion-Exclusion8.6 Applications of Inclusion-Exclusion,558End-of-Chapter Materiak5659 Relations9.1 Relations and Thcir Propcrtics9.2 n-ary RelaLions and Their Applications5839.3 Representing Relations9.4 Closures of relations5979.5上quiv9. 6 Partial orderings6l8End-of-Chapter Material633PI: 1/1 P2: 1/2 OC: 1.FRONT-7T Roscll-231IT MHIAOl7-Rosun-vScls May 13. 2011 10-10.1 Graphs and Graph Models10.3 Representing Graphs and Graph Isomorphism10.4 Connectivityuler and hamilton paths0.6 Shorlest-Path problems10.7 Planar Graphs.71810.8 Graph Coloring727End-of-Chapter materiat73511 Tree74511. 1 Introduction to 'lrees11.2 Applications of'Tr11. 3 Tree Traversal1 1.4 Spanning Trcc11.5 Minimum Spanning Tre797End-of-Chapter material80312 Boolean algebra81112.2 Representing Boolean Function...81912.4 Minimization of circuits....828End-of-C13 Modeling Computation∴………………………………84713.1 Languages and grammars3.2 Finitc-Statc Machines with OutputFinitc-Statc Machines with No Output.13.4 Language Recognition87813.5 'Turing machinesEnd-of-Chapter materialAppendixes...,A-11 Axioms for the real numbers and the positive integers2 Exponential and Logarithmic Functions3 PseudocodeSuggested Readings B-1Answers to Odd-Numbered rercises s-1Index of biographies 1-1Index -2PI: 1/1 P2: 1/2 OC: 1.FRONT-7T Roscll-2311T MHIAO17-Rosun-v5 cs May 13. 2011 10:about the authorcnncth H. Rosen has had a long carccr as a Distinguished Mcmbcr of the 'technical Staffat AT&'T Laboratories in Monmouth County, Ncw Jcrscy. He currently holds the positionof visiting Rescarch Professor at Monmouth Univcrsity where he teaches graduate courses incomputer scienceDr. Rosen received his B S. in Mathematics from the University of Michigan, Ann Arbor(1972), and his Ph D). in Mathematics from M I T (1976), where he wrote his thesis in the arcaof numbcr thcory under the direction of Harold Stark Bcforc joining Bcll Laboratories in 1982he held positions at the Univcrsity of Colorado, Bouldcr; The Ohio Statc Univcrsity. Columbus:and the University of Maine, Orono, where he was an associate professor of mathenaticsWhilc working at A'T'&'T' Labs, he taught at Monmouth Univcrsity. tcaching courscs in discrctcmathematics, coding thcory, and data sccurity. Hc currently tcachcs courscs in algorithm dcsignand in computer sccurity and cryptographyin mathematical modeling. He is the author of the widely used elementary Number theony undIts Applications. published by Pcarson, currently in its sixth edition, which has bccn translatedinto Chinesc. He is also thc author of Discrete Mathematics and Its Application.s, published byMcGraw-Hill, currcntly in its seventh edition. Discrete Mathernatics and Its Applications hassold orc than 350,000 copics in North America during its lifetime, and hundreds of thousandFrcnch, Gircck, Chincsc, Victnamcsc, and Korcan. Hc is also co-author of UNIX: The CompleteReference; UN/X System V Release 4: An introduction; and Best U//X Tips Ever, all published bOsborne McGraw-Hill. 'These books havc sold morc than 150,000 copics, with translations inChinese, Gcrman, Spanish, and Italian. Dr. Rosen is also the editor of thc Handbook of Discreteand Combinatorial Mathenatics, published by CRC Press, and he is the advisory editor of theCRC scrics of books in discrctc mathematics, consisting of morc than 5.5 volumes on diffcrcntaspccts of discrctc mathematics, most of which arc introduccd in this book. Dr. Rosen serves as anAssociate Editor for the journal Discrete Mathematies, where he works with submitted papers inseveral areas of discrete mathematics, including graph theory. enumeration, and number theoryHe is also interested in integraling mathemalical soflware into the educational and professionalenvironments, and worked on scvcral projects with Waterloo Maple Inc's MapleTM softwarcin both thesc arcas. Dr. Rosen has also worked with scvcral publishing companics on thcirAl Bell Laboratories and aT&T Laboratories, Dr. Rosen worked on a wide range of projects,including operations research studies, product line planning for computers and data communications cquipmcnt, and tcchnology assessment. Hc helped plan at'&'T's products and scrviccs inthe arca of multimedia, including vidco communications, spccch rccognition, spccch synthcsis,and imagc networking. He evaluated ncw tcchnology for usc by AT&T and did standards workin the area of image networking. he also invented many new services, and holds more than 55patents. One of his more interesting projecTs involved helping evaluale technology for the AT&Tction that was part of EPCOT CPI: 1/1 P2: 1/2 OC: 1.FRONT-7T Roscll-2311T MHIAO17-Rosun-v5 cs May 13. 2011 10:Prefacen writing this book, I was guided by my long-standing experience and interest in teachingdiscrete mathemaTics. For the studenT, my purpose was lo present material in a precisereadable manner, with the concepts and lechniques ol discrete mathenatics clearly presentedand denonstrated. My goal was to show the relevance and practicality of discrete mathematicsto students, who are oftcn skeptical. I wanted to give students studying computer scicnce all ofthe mathematical foundations they need for their future studies. I wanted to give mathematicsstudents an understanding of important Mathematical concepls together with a sense of whyese concepls are imporlant lor applications. And most importantly. I wanted to accomplishFor the instructor, my purpose was to design a flexible, comprehensive leaching tool usingproven pedagogiciques Inwanted toof matcrials that thcy could usc to teach discrctc mathematics cffcctivcly and cfticicntly in themost appropriate manncr for thcir particular sct of students. I hope that I havc achicved theseI have been extremely gratified by the tremendous success of this texl. The many improve-ments in the seventh edition have becn made possiblc by the fccdback and suggestions of a largenumber of instructors and students at many of the more than 600 North American schools andat any many universities in parts of the world, where this book has been successfully usedT'his text is designcd for a onc-or two-tcrm introductory discrete mathematics coursc takcby students in a widc varicty of majors, including mathematics, computer scicncc, and cnginccing. College algebra is the only explicit prerequisite, although a certain degree of mathemalicalmaturity is needed to study discrete mathematics in a meaningful way. This book has been designed to meel the needs of almost all Types of introductory discrete mathematics courses. It ishighly flexible and cxtrcmcly comprchcnsivc 'The book is designcd not only to be a succcssfultextbook, but also to serve as valuable resource students can consult throughout their studieand professional lileGoals of a Discrete mathematics CourseA discrctc mathematics coursc has more than onc purposc. Students should learn a particularsct of mathcmatical facts and how to apply thcm; morc importantly, such a coursc should teachstudents how to think logically and mathematically. To achieve these goals, this lext stressesmathematical reasoning and the difTerent ways problens are solved. Five imporlant themesre interwoven in this texL: mathemalical reasoning, combinatorial analysis. discrete structures,algorithmic thinking, and applications and modeling. A succcssful discrctc mathematics courschould carcfully blend and balance all fivc themes1. Mathematical Reasoning: Students must understand mathematical reasoning in order toread, comprehend, and construct mathematical arguments. This text starts with a discussionInethods of prool. Both the science and the art of constructing proofs are addressed. Thetechnique of mathematical induction is stressed through many difTerent types of exarnplesof such proofs and a carcful explanation of why mathcmatical induction is a valid proofPI: 1/1 P2: 1/2 OC: 1.FRONT-7T Roscll-231IT MHIAOl7-Rosun-vScls May 13. 2011 10-iii Prefab2. Combinatorial Analysis: An important problem-solving skill is the ability Lo count or enumerale objects. The discussion of enumeration in this book begins with the basic techniquesof counting. Thc stress is on pcrforming combinatorial analysis to solvc counting problcmsnd analyze algorithms, not on applying formulac3. Discrete structures: a coursc in discrctc mathematics should teach students how to workwith discrctc structurcs, which arc the ahstract mathcmatical structurcs used to representdiscrctc objects and relationships bctwccn these objects. These discrete structures includcsets, permutations, relations, graphs, trees, and finite-state machines.4. Algorithmic Thinhing: Ccrtain classes of problcms arc solved by the spccification of analgorithm. After an algorithm has been described, a computer program can be constructedimplementing it. The mathematical portions of this activity, which include the specificationof the algorithIll, the verification that it works properly, and the analysis ol the computermemory and timc rcquircd to pcrform it, arc all covcred in this text. Algorithms arc dcscribcdusing both English and an casily undcrstood form of pseudocode.5. Applications und Modeling: Discrete mathematics has applications to alrnost every conceivable area of studly. There are many applicalions 1o computer science and data networkingin this text, as wcll as applications to such diverse arcas as chemistry, biology, linguisticsgeography, business, and the Internet. These applications are natural and important usesdiscrete mathematics and are not contrived. Modeling with discrete mathematics is an exproblen-SolvingPuniLy lo develop byconstructing their own models in some of the exerciChanges in the Seventh EditionAlthough the sixth edition has bccn an cxtremcly cffcctivc text, many instructors, includinglongtime uscrs, havc requested changes designed to make this book morc cffcctivc. I havcdevoted a significant anount of lime and energy to satisfy their requests and I have worked hardLo find my own ways lo make the book more effeclive and more compelling lo students.Thc seventh edition is a major revision, with changes based on input from more than 40formal reviewers, fccdback from students and instructors, and author insights. T'he result is anew edition that oilers an improved organization of topics making the book a more electiveleaching lool. Substantial enhancements to the material devoted to logic, algorithIns, numberthis book more flexible andin thc seventh edition have bcen designcd to help students morc casily learn the matcrialAdditional cxplanations and examples havc bcen addcd to clarify matcrial where students oftcnhave dillicully New exercises, both routine and challenging, have been added. Highly relevantapplications, including many relaled to the Internel, lo compuler science, and Lo mathermaticalbiology, have been added. The companion website has benefited Tron extensive developmentactivity and now providcs tools students can usc to master kcy concepts and explore the worldof discrete mathematics, and many new tools under development will be released in the yearblication ol this bookhighlights some key changes, listed by the benelits they provide, may be useli i t might mcctI hope that instructors will closely cxaminc this ncw edition to discover howtheir needs. Although it is impractical to list all the changes in this editioMore Flexible Organizationn Applications of propositional logic are found in a new dcdicatcd scction, which bricflya Rccurrcncc relations arc now covcred in Chaptcr 2d Expanded coverage ol countability is now found in a dedicated section in Chapter 2PI: 1/1 P2: 1/2 OC: 1.FRONT-7T Roscll-231IT MHIACI7-Rosun-v5 cls May 13, 2011 10Preface ixa Separate chaplers now provide expanded coverage of algorithms( Chapter 3)and numbera More second and third level heads have been used to break sections into smaller coherentpartsTools for Easier Learninga Difficult discussions and proofs have been marked with the famous Bourbaki"dangerousbend ' symbol in the mareinI New marginal notes make connections, add interesting notes, and provide advice tou Morc details and addcd cxplanations, in both proofs and cxposition, make it casicr fostudents to read the booka Many ncw cxcrciscs, both routinc and challenging, havc bccn added, while many c:sting cxcrciscs havc becn improvedEnhanced Coverage of Logic, Sets, and Proofa ' The satisfiability problcm is addresscd in grcatcr depth, with Sudoku modeled in tcrmsof satisfiabilitya Hilbert 's grand Hotel is used lo help explain uncountabilityProofs throughout the book have bccn madc morc accessible by adding steps and rcasonsbehind these stcpsI A template for proofs by mathematical induction has bccn addedu The step that applies the inductive hypothesis in mathenatical induction proof is nowAlgoriI Explicit coverage of algorithmic paradigms, including brute forcc, greedy algorithms,and dynamic programing, is now provideda Uscful rules for big-O cstimates of logarithms, powers, and exponential functions haveNumber Theory and Ca Expanded coverage allows instructors to include just a littlc or a lot of numbcr thcory■ The relationship bnces has been explained morea The sieve of eratosthenes is now introduced earlier in the bookscs arc now covcred in morc dctailnumber theoluding check digits and hashI A new section on cryptography integrates previous coverage, and the notion oI a cryp-Cryptographic protocols, including digital signatures and key sharing are now covered