第1页 / 共1118页
第2页 / 共1118页
第3页 / 共1118页
第4页 / 共1118页
第5页 / 共1118页
第6页 / 共1118页
第7页 / 共1118页
第8页 / 共1118页
Discrete Mathematics and Its Applications, 8th Edition.pdf
Cover
Title Page
Copyright Page
Contents
About the Author
Preface
Acknowledgments
Online Resources
To the Student
1 The Foundations: Logic and Proofs
1.1 Propositional Logic
1.2 Applications of Propositional Logic
1.3 Propositional Equivalences
1.4 Predicates and Quantifiers
1.5 Nested Quantifiers
1.6 Rules of Inference
1.7 Introduction to Proofs
1.8 Proof Methods and Strategy
End-of-Chapter Material
2 Basic Structures: Sets, Functions, Sequences, Sums, and Matrices
2.1 Sets
2.2 Set Operations
2.3 Functions
2.4 Sequences and Summations
2.5 Cardinality of Sets
2.6 Matrices
End-of-Chapter Material
3 Algorithms
3.1 Algorithms
3.2 The Growth of Functions
3.3 Complexity of Algorithms
End-of-Chapter Material
4 Number Theory and Cryptography
4.1 Divisibility and Modular Arithmetic
4.2 Integer Representations and Algorithms
4.3 Primes and Greatest Common Divisors
4.4 Solving Congruences
4.5 Applications of Congruences
4.6 Cryptography
End-of-Chapter Material
5 Induction and Recursion
5.1 Mathematical Induction
5.2 Strong Induction and Well-Ordering
5.3 Recursive Definitions and Structural Induction
5.4 Recursive Algorithms
5.5 Program Correctness
End-of-Chapter Material
6 Counting
6.1 The Basics of Counting
6.2 The Pigeonhole Principle
6.3 Permutations and Combinations
6.4 Binomial Coefficients and Identities
6.5 Generalized Permutations and Combinations
6.6 Generating Permutations and Combinations
End-of-Chapter Material
7 Discrete Probability
7.1 An Introduction to Discrete Probability
7.2 Probability Theory
7.3 Bayes’ Theorem
7.4 Expected Value and Variance
End-of-Chapter Material
8 Advanced Counting Techniques
8.1 Applications of Recurrence Relations
8.2 Solving Linear Recurrence Relations
8.3 Divide-and-Conquer Algorithms and Recurrence Relations
8.4 Generating Functions
8.5 Inclusion–Exclusion
8.6 Applications of Inclusion–Exclusion
End-of-Chapter Material
9 Relations
9.1 Relations and Their Properties
9.2 n-ary Relations and Their Applications
9.3 Representing Relations
9.4 Closures of Relations
9.5 Equivalence Relations
9.6 Partial Orderings
End-of-Chapter Material
10 Graphs
10.1 Graphs and Graph Models
10.2 Graph Terminology and Special Types of Graphs
10.3 Representing Graphs and Graph Isomorphism
10.4 Connectivity
10.5 Euler and Hamilton Paths
10.6 Shortest-Path Problems
10.7 Planar Graphs
10.8 Graph Coloring
End-of-Chapter Material
11 Trees
11.1 Introduction to Trees
11.2 Applications of Trees
11.3 Tree Traversal
11.4 Spanning Trees
11.5 Minimum Spanning Trees
End-of-Chapter Material
12 Boolean Algebra
12.1 Boolean Functions
12.2 Representing Boolean Functions
12.3 Logic Gates
12.4 Minimization of Circuits
End-of-Chapter Material
13 Modeling Computation
13.1 Languages and Grammars
13.2 Finite-State Machines with Output
13.3 Finite-State Machines with No Output
13.4 Language Recognition
13.5 Turing Machines
End-of-Chapter Material
Appendices
1 Axioms for the Real Numbers and the Positive Integers
2 Exponential and Logarithmic Functions
3 Pseudocode
Suggested Readings
Answers to Odd-Numbered Exercises
Index of Biographies
Index
Kenneth H. Rosen
Discrete
Mathematics
and Its
Applications
E i g h t h E d i t i o n
Discrete
Mathematics
and Its
Applications
Eighth Edition
Kenneth H. Rosen
formerly AT&T Laboratories
DISCRETE MATHEMATICS AND ITS APPLICATIONS, EIGHTH EDITION
Published by McGraw-Hill Education, 2 Penn Plaza, New York, NY 10121. Copyright c 2019 by McGraw-Hill Education. All rights reserved. Printed
in the United States of America. Previous editions c 2012, 2007, and 2003. 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 McGraw-Hill Education, 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 LWI 21 20 19 18
ISBN 978-1-259-67651-2
MHID 1-259-67651-X
Product Developer: Nora Devlin
Marketing Manager: Alison Frederick
Content Project Manager: Peggy Selle
Buyer: Sandy Ludovissy
Design: Egzon Shaqiri
Content Licensing Specialist: Lorraine Buczek
Cover Image: cKarl Dehnam/Alamy Stock Photo
Compositor: Aptara, Inc.
All credits appearing on 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
Names: Rosen, Kenneth H., author.
Title: Discrete mathematics and its applications / Kenneth H. Rosen, Monmouth
University (and formerly AT&T Laboratories).
Description: Eighth edition. | New York, NY : McGraw-Hill, [2019] | Includes
bibliographical references and index.
Identifiers: LCCN 2018008740| ISBN 9781259676512 (alk. paper) |
ISBN 125967651X (alk. paper)
Subjects: LCSH: Mathematics. | Computer science–Mathematics.
Classification: LCC QA39.3 .R67 2019 | DDC 511–dc23 LC record available at
https://lccn.loc.gov/2018008740
The Internet addresses listed in the text were accurate at the time of publication. The inclusion of a website does not indicate an endorsement by the
authors or McGraw-Hill Education, and McGraw-Hill Education does not guarantee the accuracy of the information presented at these sites.
mheducation.com/highered
Contents
About the Author vi
Preface vii
Online Resources xvi
To the Student xix
1
The Foundations: Logic and Proofs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.1
Propositional Logic . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.2 Applications of Propositional Logic . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
1.3
Propositional Equivalences . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
1.4
Predicates and Quantifiers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
1.5 Nested Quantifiers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60
1.6 Rules of Inference . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73
Introduction to Proofs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 84
1.7
Proof Methods and Strategy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 96
1.8
End-of-Chapter Material . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 115
Basic Structures: Sets, Functions, Sequences, Sums,
and Matrices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 121
2
Sets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 121
2.1
Set Operations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 133
2.2
Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 147
2.3
2.4
Sequences and Summations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 165
2.5 Cardinality of Sets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 179
2.6 Matrices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 188
End-of-Chapter Material . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 195
Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 201
3
3.1 Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 201
3.2
The Growth of Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 216
3.3 Complexity of Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 231
End-of-Chapter Material . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 244
Number Theory and Cryptography. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .251
4
4.1 Divisibility and Modular Arithmetic . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 251
Integer Representations and Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 260
4.2
4.3
Primes and Greatest Common Divisors . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 271
4.4
Solving Congruences . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 290
4.5 Applications of Congruences . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 303
4.6 Cryptography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 310
End-of-Chapter Material . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 324
iii
iv Contents
5
Induction and Recursion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 331
5.1 Mathematical Induction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 331
5.2
Strong Induction and Well-Ordering . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 354
5.3 Recursive Definitions and Structural Induction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 365
5.4 Recursive Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 381
5.5
6
6.1
6.2
6.3
Program Correctness . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 393
End-of-Chapter Material . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 398
Counting . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 405
The Basics of Counting . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 405
The Pigeonhole Principle . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 420
Permutations and Combinations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 428
6.4 Binomial Coefficients and Identities . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 437
6.5 Generalized Permutations and Combinations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 445
6.6 Generating Permutations and Combinations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 457
End-of-Chapter Material . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 461
7
Discrete Probability. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .469
7.1 An Introduction to Discrete Probability . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 469
7.2
Probability Theory . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 477
7.3 Bayes’ Theorem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 494
7.4
Expected Value and Variance . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 503
End-of-Chapter Material . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 520
8
Advanced Counting Techniques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 527
8.1 Applications of Recurrence Relations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 527
8.2
Solving Linear Recurrence Relations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 540
8.3 Divide-and-Conquer Algorithms and Recurrence Relations . . . . . . . . . . . . . . . . . . . . . . 553
8.4 Generating Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 563
8.5
Inclusion–Exclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 579
8.6 Applications of Inclusion–Exclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 585
End-of-Chapter Material . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 592
9
Relations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 599
9.1 Relations and Their Properties . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 599
n-ary Relations and Their Applications . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 611
9.3 Representing Relations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 621
9.2
9.4 Closures of Relations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 628
9.5
9.6
Equivalence Relations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 638
Partial Orderings . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 650
End-of-Chapter Material . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 665
Contents v
10 Graphs. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .673
10.1 Graphs and Graph Models . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 673
10.2 Graph Terminology and Special Types of Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 685
10.3 Representing Graphs and Graph Isomorphism . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 703
10.4 Connectivity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 714
10.5 Euler and Hamilton Paths . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 728
10.6 Shortest-Path Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 743
10.7 Planar Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 753
10.8 Graph Coloring . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 762
End-of-Chapter Material . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 771
11 Trees. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .781
11.1 Introduction to Trees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 781
11.2 Applications of Trees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 793
11.3 Tree Traversal . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 808
11.4 Spanning Trees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 821
11.5 Minimum Spanning Trees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 835
End-of-Chapter Material . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 841
12 Boolean Algebra . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 847
12.1 Boolean Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 847
12.2 Representing Boolean Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 855
12.3 Logic Gates . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 858
12.4 Minimization of Circuits . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 864
End-of-Chapter Material . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 879
13 Modeling Computation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 885
13.1 Languages and Grammars . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 885
13.2 Finite-State Machines with Output . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 897
13.3 Finite-State Machines with No Output . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 904
13.4 Language Recognition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 917
13.5 Turing Machines . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 927
End-of-Chapter Material . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 938
Appendices. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .A-1
Axioms for the Real Numbers and the Positive Integers . . . . . . . . . . . . . . . . . . . . . . . . . . A-1
Exponential and Logarithmic Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . A-7
Pseudocode . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . A-11
1
2
3
Suggested Readings B-1
Answers to Odd-Numbered Exercises S-1
Index of Biographies I-1
Index I-2
About the Author
K enneth H. 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 number theory under the direction of Harold Stark. Before joining Bell Laboratories
in 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&T
Bell Laboratories (and AT&T Laboratories) in Monmouth County, New Jersey. While working
at 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 professor
of computer science at Monmouth University, where he has taught courses in algorithm design,
computer security and cryptography, and discrete mathematics.
Dr. Rosen has published numerous articles in professional journals on number theory and
on mathematical modeling. He is the author of the widely used Elementary Number Theory and
Its Applications, published by Pearson, currently in its sixth edition, which has been translated
into Chinese. He is also the author of Discrete Mathematics and Its Applications, published by
McGraw-Hill, currently in its eighth edition. Discrete Mathematics and Its Applications has sold
more than 450,000 copies in North America during its lifetime, and hundreds of thousands of
copies 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 of UNIX: The Complete Reference; UNIX System V Release 4: An Introduction; and Best
UNIX Tips Ever, all published by Osborne McGraw-Hill. These books have sold more than
150,000 copies, with translations into Chinese, German, Spanish, and Italian. Dr. Rosen is also
the editor of both the first and second editions (published in 1999 and 2018, respectively) of
the Handbook of Discrete and Combinatorial Mathematics, published by CRC Press. He has
served as the advisory editor of the CRC series of books in discrete mathematics, sponsoring
more than 70 volumes on diverse aspects of discrete mathematics, many of which are introduced
in this book. He is an advisory editor for the CRC series of mathematics textbooks, where he has
helped more than 30 authors write better texts. Dr. Rosen serves as an Associate Editor for the
journal Discrete Mathematics, where he handles papers in many areas, including graph theory,
enumeration, number theory, and cryptography.
Dr. Rosen has had a longstanding interest in integrating mathematical software into the
educational and professional environments. He has worked on several projects with Waterloo
Maple Inc.’s MapleTM software in both these areas. Dr. Rosen has devoted a great deal of energy
to ensuring that the online homework for Discrete Mathematics and its Applications is a superior
teaching tool. Dr. Rosen has also worked with several publishing companies on their homework
delivery platforms.
At 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 equipment, technology assessment and innovation, and many other efforts. He
helped plan AT&T’s products and services in the area of multimedia, including video com-
munications, speech recognition, speech synthesis, and image networking. He evaluated new
technology for use by AT&T and did standards work in the area of image networking. He also in-
vented many new services, and holds more than 70 patents. One of his more interesting projects
involved helping evaluate technology for the AT&T attraction that was part of EPCOT Cen-
ter. After leaving AT&T, Dr. Rosen has worked as a technology consultant for Google and for
AT&T.
vi
Preface
I n writing this book, I was guided by my long-standing experience and interest in teaching
discrete mathematics. For the student, my purpose was to present material in a precise, read-
able manner, with the concepts and techniques of discrete mathematics clearly presented and
demonstrated. My goal was to show the relevance and practicality of discrete mathematics to
students, who are often skeptical. I wanted to give students studying computer science all of
the mathematical foundations they need for their future studies. I wanted to give mathematics
students an understanding of important mathematical concepts together with a sense of why
these concepts are important for applications. And most importantly, I wanted to accomplish
these goals without watering down the material.
For the instructor, my purpose was to design a flexible, comprehensive teaching tool using
proven pedagogical techniques in mathematics. I wanted to provide instructors with a package
of materials that they could use to teach discrete mathematics effectively and efficiently in the
most appropriate manner for their particular set of students. I hope that I have achieved these
goals.
I have been extremely gratified by the tremendous success of this text, including its use
by more than one million students around the world over the last 30 years and its translation
into many different languages. The many improvements in the eighth edition have been made
possible by the feedback and suggestions of a large number of instructors and students at many
of the more than 600 North American schools, and at many universities in different parts of the
world, where this book has been successfully used. I have been able to significantly improve the
appeal and effectiveness of this book edition to edition because of the feedback I have received
and the significant investments that have been made in the evolution of the book.
This text is designed for a one- or two-term introductory discrete mathematics course taken
by students in a wide variety of majors, including mathematics, computer science, and engineer-
ing. College algebra is the only explicit prerequisite, although a certain degree of mathematical
maturity is needed to study discrete mathematics in a meaningful way. This book has been de-
signed to meet the needs of almost all types of introductory discrete mathematics courses. It is
highly flexible and extremely comprehensive. The book is designed not only to be a successful
textbook, but also to serve as a valuable resource students can consult throughout their studies
and professional life.
Goals of a Discrete Mathematics Course
A discrete mathematics course has more than one purpose. Students should learn a particular
set of mathematical facts and how to apply them; more importantly, such a course should teach
students how to think logically and mathematically. To achieve these goals, this text stresses
mathematical reasoning and the different ways problems are solved. Five important themes are
interwoven in this text: mathematical reasoning, combinatorial analysis, discrete structures, al-
gorithmic thinking, and applications and modeling. A successful discrete mathematics course
should carefully blend and balance all five themes.
1. Mathematical Reasoning: Students must understand mathematical reasoning in order to read,
comprehend, and construct mathematical arguments. This text starts with a discussion of
mathematical logic, which serves as the foundation for the subsequent discussions of methods
of proof. Both the science and the art of constructing proofs are addressed. The technique of
vii
相关推荐
2023年江西萍乡中考道德与法治真题及答案.doc
2012年重庆南川中考生物真题及答案.doc
2013年江西师范大学地理学综合及文艺理论基础考研真题.doc
2020年四川甘孜小升初语文真题及答案I卷.doc
2020年注册岩土工程师专业基础考试真题及答案.doc
2023-2024学年福建省厦门市九年级上学期数学月考试题及答案.doc
2021-2022学年辽宁省沈阳市大东区九年级上学期语文期末试题及答案.doc
2022-2023学年北京东城区初三第一学期物理期末试卷及答案.doc
2018上半年江西教师资格初中地理学科知识与教学能力真题及答案.doc
2012年河北国家公务员申论考试真题及答案-省级.doc
2020-2021学年江苏省扬州市江都区邵樊片九年级上学期数学第一次质量检测试题及答案.doc
2022下半年黑龙江教师资格证中学综合素质真题及答案.doc
