离散数学及其应用--第4版--英文

ABOUT THE AUTHOR Kenneth H. Rosen is a Distinguished Member ofthe Technical Staffin the New Concepts Area of AT&T Laboratories in Holmdel, New Jersey. Dr. Rosen received his B.S. in Mathematics from the University ofMichi- gan, Ann Arbor (1972), and his Ph.D. in Mathematics from M.I.T. (1976), where he wrote his thesis in the area of number theory under the direction of Harold Stark. Be- forejoining Bell Laboratories in 1982, he held positions at the University ofColorado, Boulder; the Ohio State University, Columbus; and the University of Maine, Orono, where he was an associate professor of mathematics. While working at AT&T Labs, Ken has taught in the evening program in computer science at Monmouth University, teaching courses in discrete mathematics, coding theory, and data security. Dr. Rosen has published numerous articles in professional joumals in the areas of number theory and mathematical modeling. He is the author ofthe textbooks Elemen- tary Number Theory and Its Applications, currently in its third edition, published by Addison-Wesley, and Discrete Mathematics and Its Applications, m its fourth edition, published by McGraw-Hill. Both books have been used extensively at hundreds of uni- versities. He is coauthor of UNIX System VRelease 4: An lntroduction, which has sold more than 100,000 copies and has been translated into Spanish and German, and Best UNIX Tips Ever, translated into Chinese, both published by Osbome McGraw-Hill. Ken is also the editor of the Handbook ofDiscrete Mathematics, a new publication to be published in 1999 by CRC Press, and he is the editor of the CRC series of books in discrete mathematics. Ken is also interested in integrating mathematical software into the educational and professional environments and is working on projects with Waterloo MAPLE software in both these areas. At Bell Laboratories and now AT&T Laboratories, Dr. Rosen has worked on a wide range of projects, including operations research studies and product line planning for computers and data communications equipment. He has helped plan AT&T's fu- ture products and services in the area of multimedia, including video communications, speech recognition, and image networking. He has evaluated new technology for use by AT&T. He has also invented many new services and holds or has submitted many patents. One of his more interesting projects involved helping evaluate technology for the AT&T attraction at EPCOT Center.

CONTENTS Preface ix The Companion Web Site xix TotheStudent xxi 1 The Foundations: Logic, Sets, and Functions 1.1Logic 1.2Propositional Equivalences 1.3Predicates and Quantifiers 1.4Sets 1.5Set Operations 1.6Functions 1.7Sequences and Summations 1.8The Growth of Functions Key Tenns and Results Review Questions Supplementary Exercises Computer Projects Computations and Explorations Writing Projects 2 The Fundamentals: Algorithms, the Integers, and Matrices 2.1Algorithms 2.2ComplexityofAlgorithms 2.3The Integers and Division 2.4Integers and Algorithms 2.5Applications of Number Theory 2.6Matrices Key Terms and Results Review Questions Supplementary Exercises Computer Projects Computations and Exploratiuns Writing Projects 3 Mathematical Reasoning 3.1MethodsofProof 3.2Mathematical Induction 3.3Recursive Definitions 3.4Recursive Algorithms 3.5Program Correctness Key Tenns and Results Review Questions Supplementary Exercises Computer Projects Computations and Explorations Writing Projects 4 Counting 4.1The Basics of Counting 4.2The Pigeonhole Principle 4.3Pennutations and Combinations 4.4Discrete Probability 4.5Probability Theory 4.6Generalized Pennutations and Combinations 4.7Generating Pennutations and Combinations Key Terms and Concepts Review Questions Supplementary Exercises Computer Projects Computations and Explorations Writing Projects 5 Advanced Counting Techniques 5.1Recurrence Relations 5.2Solving Recurrcnce Relarions 5.3Divide-and-Conquer Relations 5.4Generating Functions 5.5Inclusion-Exclusion 5.6Applications of Inclusion-Exclusion Key Terms and Results Review Questions Supplementary Exercises Computer Projects Computations and Explorations Writing Projects 6 Relations 6.lRelations and Their Properties 6.2n-ary Relations and Their Applications 6.3Representing Relations 6.4ClosurcsofRelations 6.5Equivalence Relations 6.6Partial Orderings Key Terms and Results Review Questions Supplementary Exercises Computer Projects Computations and Explorations Writing Prqjects 7 Graphs 7.1Introduction to Graphs 7.2Graph Tenninology 7.3Representing Graphs and Graph Isomorphism 7.4Connectivity 7.5Euler and Hamilton Paths 7.6Shortest Path Problems 7.7Planar Graphs 7.8Graph Coloring Key Terms and Results : Review Questions Supplementary Exercises Computer Projects Computations and Explorations Writing Projects 8 Trees 8.l Introduction to Trees 8.2 Applications ofTrees 8.3 Tree Traversal 8.4 Trees and Sorting 8.5 Spanning Trees 8.6 Minimum Spanning Trees Key Terms and Results Review Questions Supplementary Exercises Computer Projects Computations and Explorations Writing Projects 9 Boolean Algebra 9.1Boolean Functions 9.2Representing Boolean Functions 9.3Logic Gates 9.4MinimizationofCircuits Key Terms and Results Review Questions Supplementary Exercises Computer Projects Computations and Explorations Writing Projects 10 Modeling Computation 10.1Languages and Grammars 10.2Finite-State Machines with Output 10.3Finite-State Machines with No Output 10.4Language Recognition 10.5Turing Machines Key Tenns and Results Review Questions Supplementary Exercises Computer Projects Computations and Explorations Writing Projects Appendixes A-l A.1Exponential and Logarithmic Functions A.2Pseudocode Suggested Readings B-l Index of Biographies 1-1 Index 1-3 LISTOFSYMBOLS L-l