Discrete Mathematics and Its Applications, Eighth Edition

1 Discrete Mathematics Applicationsand ItsKenneth H. RosenEighth EditionDiscreteMathematicsand ItsApplicationsEighth EditionKenneth H. Rosenformerly AT&T LaboratoriesDISCRETE Mathematics AND ITS APPLICATIONS, Eighth EDITIONP ublished by McGraw-Hill Education, 2 Penn Plaza, New York, NY 10121. Copyrightc 2019 by McGraw-Hill Education. All rights reserved. Printedin the United States of America. Previous editionsc 2012, 2007, and 2003. No part of this publication may be reproduced or distributed in any form orby any means, or stored in a database or retrieval system, without the prior written consent of McGraw-Hill Education, including, but not limited to, inanynetwork or other electronic storage or transmission, or broadcast for distance ancillaries, including electronic and print components, may not be available to customers outside the United book is printed on acid-free 978-1-259-67651-2 MHID 1-259-67651-XProduct Developer:Nora DevlinMarketing Manager:Alison FrederickContent Project Manager:Peggy SelleBuyer:Sandy LudovissyDesign:Egzon ShaqiriContent Licensing Specialist:Lorraine BuczekCover Image.

2 C Karl Dehnam/Alamy Stock PhotoCompositor: Aptara, credits appearing on page or at the end of the book are considered to be an extension of the copyright of Congress Cataloging-in-Publication DataNames: Rosen, Kenneth H., : Discrete Mathematics and its applications / Kenneth H. Rosen, MonmouthUniversity (and formerly AT&T Laboratories).Description: Eighth Edition .|New York, NY : McGraw-Hill, [2019]|Includesbibliographical references and : LCCN 2018008740|ISBN 9781259676512 (alk. paper)|ISBN 125967651X (alk. paper)Subjects: LCSH: Mathematics .|Computer science : LCC .R67 2019|DDC 511 dc23 LC record available Internet addresses listed in the text were accurate at the time of publication.

3 The inclusion of a website does not indicate an endorsement by theauthors or McGraw-Hill Education, and McGraw-Hill Education does not guarantee the accuracy of the information presented at these the AuthorviPrefaceviiOnline ResourcesxviTo the Studentxix1 The Foundations: Logic and Logic .. of Propositional Logic .. Equivalences .. and Quantifiers .. Quantifiers .. of Inference .. to Proofs .. Methods and Strategy .. 96 End-of-Chapter Basic Structures: Sets, Functions, Sequences, Sums,and .. Operations .. and Summations .. of Sets .. 188 End-of-Chapter .. Growth of Functions .. of Algorithms .. 231 End-of-Chapter Number Theory and and Modular Arithmetic.

4 Representations and Algorithms .. and Greatest Common Divisors .. Congruences .. of Congruences .. 310 End-of-Chapter Induction and Induction .. Induction and Well-Ordering .. Definitions and Structural Induction .. Algorithms .. Correctness .. 393 End-of-Chapter Basics of Counting .. Pigeonhole Principle .. and Combinations .. Coefficients and Identities .. Permutations and Combinations .. Permutations and Combinations .. 457 End-of-Chapter Discrete Introduction to Discrete Probability .. Theory .. Theorem .. Value and Variance .. 503 End-of-Chapter Advanced Counting of Recurrence Relations .. Linear Recurrence Relations .. Algorithms and Recurrence Relations.

5 Functions .. Exclusion .. of Inclusion Exclusion .. 585 End-of-Chapter and Their Properties .. Relations and Their Applications .. Relations .. of Relations .. Relations .. Orderings .. 650 End-of-Chapter Graphs and Graph Models .. Graph Terminology and Special Types of Graphs .. Representing Graphs and Graph Isomorphism .. Connectivity .. Euler and Hamilton Paths .. Shortest-Path Problems .. Planar Graphs .. Graph Coloring .. 762 End-of-Chapter Introduction to Trees .. Applications of Trees .. Spanning Trees .. Minimum Spanning Trees .. 835 End-of-Chapter Boolean Boolean Functions .. Representing Boolean Functions.

6 Logic Gates .. Minimization of Circuits .. 864 End-of-Chapter Modeling Languages and Grammars .. Finite-State Machines with Output .. Finite-State Machines with No Output .. Language Recognition .. Turing Machines .. 927 End-of-Chapter for the Real Numbers and the Positive Integers .. A-12 Exponential and Logarithmic Functions .. A-73 Pseudocode .. A-11 Suggested ReadingsB-1 Answers to Odd-Numbered ExercisesS-1 Index of BiographiesI-1 IndexI-2 About the AuthorKenneth H. Rosenreceived his in Mathematics from the University of Michigan,Ann Arbor (1972), and his in Mathematics from (1976), where he wrotehis thesis in number theory under the direction of Harold Stark.

7 Before joining Bell Laboratoriesin 1982, he held positions at the University of Colorado, Boulder; The Ohio State University,Columbus; and the University of Maine, Orono, where he was an associate professor of math-ematics. He enjoyed a long career as a Distinguished Member of the Technical Staff at AT&TBell Laboratories (and AT&T Laboratories) in Monmouth County, New Jersey. While workingat Bell Labs, he taught at Monmouth University, teaching courses in Discrete Mathematics , cod-ing theory, and data security. After leaving AT&T Labs, he became a visiting research professorof computer science at Monmouth University, where he has taught courses in algorithm design,computer security and cryptography, and Discrete Rosen has published numerous articles in professional journals on number theory andon mathematical modeling.

8 He is the author of the widely usedElementary Number Theory andIts Applications, published by Pearson, currently in its sixth Edition , which has been translatedinto Chinese. He is also the author ofDiscrete Mathematics and Its Applications, published byMcGraw-Hill, currently in its Eighth Mathematics and Its Applicationshas soldmore than 450,000 copies in North America during its lifetime, and hundreds of thousands ofcopies throughout the rest of the world. This book has also been translated into many languages,including Spanish, French, Portuguese, Greek, Chinese, Vietnamese, and Korean. He is also co-author ofUNIX: The Complete Reference;UNIX System V Release 4: An Introduction; andBestUNIX Tips Ever, all published by Osborne McGraw-Hill.

9 These books have sold more than150,000 copies, with translations into Chinese, German, Spanish, and Italian. Dr. Rosen is alsothe editor of both the first and second editions (published in 1999 and 2018, respectively) oftheHandbook of Discrete and Combinatorial Mathematics , published by CRC Press. He hasserved as the advisory editor of the CRC series of books in Discrete Mathematics , sponsoringmore than 70 volumes on diverse aspects of Discrete Mathematics , many of which are introducedin this book. He is an advisory editor for the CRC series of Mathematics textbooks, where he hashelped more than 30 authors write better texts. Dr. Rosen serves as an Associate Editor for thejournalDiscrete Mathematics , where he handles papers in many areas, including graph theory,enumeration, number theory, and Rosen has had a longstanding interest in integrating mathematical software into theeducational and professional environments.

10 He has worked on several projects with WaterlooMaple Inc. s MapleTMsoftware in both these areas. Dr. Rosen has devoted a great deal of energyto ensuring that the online homework forDiscrete Mathematics and its Applicationsis a superiorteaching tool. Dr. Rosen has also worked with several publishing companies on their homeworkdelivery Bell Laboratories and AT&T Laboratories, Dr. Rosen worked on a wide range ofprojects, including operations research studies, product line planning for computers and datacommunications equipment, technology assessment and innovation, and many other efforts. Hehelped plan AT&T s products and services in the area of multimedia, including video com-munications, speech recognition, speech synthesis, and image networking.