《离散数学及其应用》参考书籍（英文原版，第七版，作者：Kenneth H. Rosen，2012）Discrete Mathematics and Its Applications（SEVENTH EDITION）

Kenneth H.Rosen Discrete Mathematics and Its Applications SEVENTH EDITION

Kenneth H. Rosen SEVENTH EDITION Discrete Mathematics and Its Applications

Discrete Mathematics and Its Applications Seventh Edition Kenneth H.Rosen Lbrore 习

Discrete Mathematics and Its Applications Seventh Edition Kenneth H. Rosen Monmouth University (and formerly AT&T Laboratories)

The McGraw-Hill Companies Mc Succeed CRETE MATHEMATICS AND ITS APPLICATIONS,SEVENTH EDITION Published by McGraw-Hill,a business unit of The MeGraw-Hill Companies,Ine,1221 Avenue of the ious editi s02007.2003.amd1999.Nop of this publication may be re or transmission,or broadcast for distance leamning Samia,iaedingehetoaeadpmnompomeas,agkeaahheouthnesoeike This book is printedncidree paper. 1234567890D0wD0wW10987654321 7023g30m Global Pu ng nt edit Brenda A roles Cover Designer. All credits appearing on this page or at the end of the book are considered to be an extension of the copyright page Library of Congress Cataloging-in-Publication Data 850 puter science-Mathematics I.Title 2011011060 www.mhhe.com

DISCRETE MATHEMATICS AND ITS APPLICATIONS, SEVENTH EDITION Published by McGraw-Hill, a business unit of The McGraw-Hill Companies, Inc., 1221 Avenue of the Americas, New York, NY 10020. Copyright © 2012 by The McGraw-Hill Companies, Inc. All rights reserved. Previous editions © 2007, 2003, and 1999. No part of this publication may be reproduced or distributed in any form or by any means, or stored in a database or retrieval system, 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 learning. Some ancillaries, including electronic and print components, may not be available to customers outside the United States. This book is printed on acid-free paper. 1 2 3 4 5 6 7 8 9 0 DOW/DOW 1 0 9 8 7 6 5 4 3 2 1 ISBN 978-0-07-338309-5 MHID 0-07-338309-0 Vice President & Editor-in-Chief: Marty Lange Editorial Director: Michael Lange Global Publisher: Raghothaman Srinivasan Executive Editor: Bill Stenquist Development Editors: Lorraine K. Buczek/Rose Kernan Senior Marketing Manager: Curt Reynolds Project Manager: Robin A. Reed Buyer: Sandy Ludovissy Design Coordinator: Brenda A. Rolwes Cover painting: Jasper Johns, Between the Clock and the Bed, 1981. Oil on Canvas (72 × 126 1/4 inches) Collection of the artist. Photograph by Glenn Stiegelman. Cover Art © Jasper Johns/Licensed by VAGA, New York, NY Cover Designer: Studio Montage, St. Louis, Missouri Lead Photo Research Coordinator: Carrie K. Burger Media Project Manager: Tammy Juran Production Services/Compositor: RPK Editorial Services/PreTeX, Inc. Typeface: 10.5/12 Times Roman Printer: R.R. Donnelley All credits appearing on this page or at the end of the book are considered to be an extension of the copyright page. Library of Congress Cataloging-in-Publication Data Rosen, Kenneth H. Discrete mathematics and its applications / Kenneth H. Rosen. — 7th ed. p. cm. Includes index. ISBN 0–07–338309–0 1. Mathematics. 2. Computer science—Mathematics. I. Title. QA39.3.R67 2012 511–dc22 2011011060 www.mhhe.com

Contents 1 The Foundations:Logic and Proofs..................................1 1.1 Propositional Logic 1 12 Applications of Propositional Logic 16 Propositional Equivalences ....25 1.4 Predicates andQuantifiers..............................................36 15 Nested Ouantifiers 57 16 Rules of Inference 69 17 Introduction to Proofs 1.8 Proof Methods and Strategy. End-of-Chapter Material .............. .109 2 Basic Structures:Sets,Functions,Sequences,Sums,and Matrices.115 Sets .115 Set Operations... ..127 3 Functions 44.138 24 Sequences and Summations .156 25 Cardinality of Sets 170 2.6 172 End-ofChapter Material.... 3A1 gorithms.… 191 1 Algorithms 191 32 The Growth of Functions.....................204 3.3 Complexity ofAlgorithms 218 End-of-Chapter Material. .232 4 Number Theory and Cryptography................................237 4.1 Divisibility and Modular Arithmetic.. .237 4.2 Integer Representations and Algorithms .245 43 Prin es and Greatest Common Divisor 257 44 4.5 Solving Congruences. Applications of Congruences 4.6 Cryptography.. ,294 End-of-Chapter Material...... .306

Contents About the Author vi Preface vii The Companion Website xvi To the Student xvii 1 The Foundations: Logic and Proofs ..................................1 1.1 Propositional Logic ............................................................1 1.2 Applications of Propositional Logic . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 1.3 Propositional Equivalences . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25 1.4 Predicates and Quantifiers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36 1.5 Nested Quantifiers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57 1.6 Rules of Inference . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69 1.7 Introduction to Proofs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80 1.8 Proof Methods and Strategy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 92 End-of-Chapter Material . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 109 2 Basic Structures: Sets, Functions, Sequences, Sums, and Matrices . 115 2.1 Sets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 115 2.2 Set Operations. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .127 2.3 Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 138 2.4 Sequences and Summations. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 156 2.5 Cardinality of Sets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 170 2.6 Matrices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 177 End-of-Chapter Material . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 185 3 Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 191 3.1 Algorithms. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 191 3.2 The Growth of Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 204 3.3 Complexity of Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 218 End-of-Chapter Material . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 232 4 Number Theory and Cryptography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 237 4.1 Divisibility and Modular Arithmetic . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 237 4.2 Integer Representations and Algorithms. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 245 4.3 Primes and Greatest Common Divisors . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 257 4.4 Solving Congruences. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .274 4.5 Applications of Congruences. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 287 4.6 Cryptography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 294 End-of-Chapter Material . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 306 iii

iv Contents 5 Induction and Recursion .311 5.1 Mathematical Induction ” .311 Strong Induction and Well-Ordering. 333 Recursive Definitions and Structural Induction. 344 54 Recursive algorithms 360 5.5 Program Correctness 372 End-of-Chapter Material 377 6 Counting......... .385 6 1 The Basics of Counting 385 6.2 The Pigeonhole Princi 399 Permutations and Combinations 407 6.4 Binomial Coefficients and Identities............................... .415 6.5 Generalized Permutations and Combinations .423 66 Generating Permutations and Combinations 434 End-of-Chapter Material 439 7 Discrete Probability.............................................. .445 7.1 An Introduction to Diserete Probability 445 7.2 Probability Theory.......................... 73 Baves'Theorem. .468 7.4 Expected Value and Variance....... .477 End-of-Chapter Material. 494 8 Advanced Counting Techniques...................................501 8.1 Applications of Recurrence Relations 501 82S0 Iving linear recurrence relations 514 8.3 Divide-and-Conquer Algorithms and Recurrence Relations 527 Generating Functions.............................. 8 5 Inclusion-Exclusion .552 8.6 Applications of Inclusion-Exclusion 558 -of-Chapter Material 565 9 Relations.. .573 9.1 Relations and Their Properties 573 n-ary Relat and Their Applications 9.3 Representing Relations 591 9.4 Closures of kelations 597 95 Equivalence relations 607 9.6 Partial Orderings 618 -of-Chapter Material 633

iv Contents 5 Induction and Recursion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 311 5.1 Mathematical Induction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 311 5.2 Strong Induction and Well-Ordering . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 333 5.3 Recursive Definitions and Structural Induction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 344 5.4 Recursive Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 360 5.5 Program Correctness. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 372 End-of-Chapter Material . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 377 6 Counting . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 385 6.1 The Basics of Counting. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .385 6.2 The Pigeonhole Principle . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 399 6.3 Permutations and Combinations. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 407 6.4 Binomial Coefficients and Identities . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 415 6.5 Generalized Permutations and Combinations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 423 6.6 Generating Permutations and Combinations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 434 End-of-Chapter Material . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 439 7 Discrete Probability . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 445 7.1 An Introduction to Discrete Probability . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 445 7.2 Probability Theory . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 452 7.3 Bayes’ Theorem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 468 7.4 Expected Value and Variance . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 477 End-of-Chapter Material . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 494 8 Advanced Counting Techniques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 501 8.1 Applications of Recurrence Relations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 501 8.2 Solving Linear Recurrence Relations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 514 8.3 Divide-and-Conquer Algorithms and Recurrence Relations. . . . . . . . . . . . . . . . . . . . . . .527 8.4 Generating Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 537 8.5 Inclusion–Exclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 552 8.6 Applications of Inclusion–Exclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 558 End-of-Chapter Material . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 565 9 Relations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 573 9.1 Relations and Their Properties . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 573 9.2 n-ary Relations and Their Applications. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 583 9.3 Representing Relations. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 591 9.4 Closures of Relations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 597 9.5 Equivalence Relations. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 607 9.6 Partial Orderings . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 618 End-of-Chapter Material . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 633