离散数学及其应用（英文版.第5版） (2010 年度畅销榜NO.3279 )

本书第4版是全球500多所大学的指定教材，获得了极大的成功。中文版也已被国内大学广泛采用为教材。第5版在前四版的基础上做了大量的改进，使其成为更有效的教学工具。 \r\n\r\n\r\n\r\n\r\n　　本书可作为1至2个学期的离散数学课入门教材，适用于数、计算机科学、工程等专业的学生。\r\n\r\n\r\n　　第5版的特点 \r\n\r\n\r\n　　 ◆易入门：实践证明本书对初学者来说易读易懂 \r\n\r\n\r\n　　 ◆灵活：本教材为灵活使用做了精心设计，各章对其前面内容的依赖降到最小 \r\n\r\n\r\n　　 ◆广泛的课堂实践：本书已在500多所学校得到了多年检验 \r\n\r\n\r\n　　 ◆实例：书中有700多个实例，用于阐明要领联系不同内容，并引入各种应用 \r\n\r\n\r\n　　 ◆应用：本书涉及的应用领域很广，包括计算机科学、数据网络、心理学、化学、 工程、语言学、生物学、商业和互联网 \r\n\r\n\r\n\r\n\r\n　　 ◆历史资料：本书以脚注的形式给出了60多位数学和计算机科学家的传记，并配有照片\r\n\r\n\r\n　　 ◆关键术语和结论：每一章后面都列出了本章的关键术语和结论\r\n\r\n\r\n　　 ◆练习、复习题、补充练习：正文中有3500多道练习，每章最后都有一组复习题才一组丰富而多样的补充练习\r\n\r\n\r\n　　 ◆计算机课题：每一章后面还有一组计算机课题，把学生已经学到的计算和离散数学的内容结合在一起\r\n\r\n\r\n\r\n\r\n\r\n　　相关链接\r\n\r\n\r\n　　 \r\n\r\n\r\n　　 \r\n
\r\n

Preface vii \r\n\r\n The Companion Website xvii \r\n\r\n To the Student xix \r\n\r\n \r\n\r\n 1 The Foundations: Logic and Proof Sets,and Functions \r\n\r\n l.l Logic \r\n\r\n l.2 Propositional Equivalences \r\n\r\n l.3 Predicates and Quantifiers \r\n\r\n l.4 Nested Quantifiers \r\n\r\n l.5 Methods of Proof \r\n\r\n l.6 Sets \r\n\r\n l.7 Set Operations \r\n\r\n l.8 Functions \r\n\r\n End-of-Chapter Material \r\n\r\n \r\n\r\n 2 The Fundamentals: Algorithms, the Integers,and Matrices \r\n\r\n 2.l Algorithms \r\n\r\n 2.2 The Growth of Functions \r\n\r\n 2.3 Complexity of Algorithms \r\n\r\n 2.4 The Integers and Division \r\n\r\n 2.5 Integers and Algorithms \r\n\r\n 2.6 Applications of Number Theory \r\n\r\n 2.7 Matrices \r\n\r\n End-of Chapter Material \r\n\r\n \r\n\r\n 3 Mathematical Reasoning, Induction,and Recursion \r\n\r\n 3. l Proof Strategy \r\n\r\n 3.2 Sequences and Summations \r\n\r\n 3.3 Mathematical Induction \r\n\r\n 3.4 Recursive Definitions and Structural Induction \r\n\r\n 3.5 Recursive Algorithms \r\n\r\n 3.6 Program Correctness \r\n\r\n End-of-Chapter Material \r\n\r\n \r\n\r\n 4 Counting \r\n\r\n 4.l The Basics of Counting \r\n\r\n 4.2 The Pigeonhole Principle \r\n\r\n 4.3 Permutations and Combinations \r\n\r\n 4.4 Binomial Coefficients \r\n\r\n 4.5 Generalized Permutations and Combinations \r\n\r\n 4.6 Generating Permutations and Combinations \r\n\r\n End-of-Chapter Material \r\n\r\n \r\n\r\n 5 Discrete Probability \r\n\r\n 5. l An Introduction to Discrete Probability \r\n\r\n 5.2 Probability Theory \r\n\r\n 5.3 Expected Value and Variance \r\n\r\n End-of-Chapter Material \r\n\r\n \r\n\r\n 6 Advanced Counting Techniques \r\n\r\n 6.l Recurrence Relations \r\n\r\n 6.2 Solving Recurrence Relations \r\n\r\n 6.3 Divide-and-Conquer Algorithms and Recurrence Relations \r\n\r\n 6.4 Generating Functions \r\n\r\n 6.5 Inclusion--Exclusion \r\n\r\n 6.6 Applications of Inclusion-Exclusion \r\n\r\n End-of-Chapter Material \r\n\r\n \r\n\r\n 7 Relations \r\n\r\n 7.l Relations and Their Properties \r\n\r\n 7.2 n-ary Relations and Their Applications \r\n\r\n 7.3 Representing Relations \r\n\r\n 7.4 Closures of Relations \r\n\r\n 7.5 Equivalence Relations \r\n\r\n 7.6 Partial Orderings \r\n\r\n End-of-Chapter Material \r\n\r\n \r\n\r\n 8 Graphs \r\n\r\n 8. l Introduction to Graphs \r\n\r\n 8.2 Graph Terminology \r\n\r\n 8.3 Representing Graphs and Graph Isomorphism \r\n\r\n 8.4 Connectivity \r\n\r\n 8.5 Euler and Hamilton Paths \r\n\r\n 8.6 Shortest-Path Problems \r\n\r\n 8.7 Planar Graphs \r\n\r\n 8.8 Graph Coloring \r\n\r\n End-of-Chapter Material \r\n\r\n \r\n\r\n 9 Trees \r\n\r\n 9.l Introduction to Trees \r\n\r\n 9.2 Applications of Trees \r\n\r\n 9.3 Tree Traversal \r\n\r\n 9.4 Spanning Trees \r\n\r\n 9.5 Minimum Spanning Trees \r\n\r\n End-of-Chapter Material \r\n\r\n \r\n\r\n 10 BooleanAlgebra \r\n\r\n l0.l Boolean Functions \r\n\r\n l0.2 Representing Boolean Functions \r\n\r\n l0.3 Logic Gates \r\n\r\n l0.4 Minimization of Circuits \r\n\r\n End-of-Chapter Material \r\n\r\n \r\n\r\n 11 Modeling Computation \r\n\r\n ll.l Languages and Grammars \r\n\r\n ll.2 Finite-State Machines with Output \r\n\r\n ll.3 Finite-State Machines with No Output \r\n\r\n ll.4 Language Recognition \r\n\r\n 11.5 Turing Machines \r\n\r\n End-of Chapter Material \r\n\r\n \r\n\r\n Appendixes \r\n\r\n A.l Exponential and Logarithmic Functions \r\n\r\n A.2 Pseudocode \r\n\r\n Suggested Readings B-l \r\n\r\n Answers to Odd-Numbered Exercises S-l \r\n\r\n Photo Credits C-l \r\n\r\n Index of Biographies I-l \r\n\r\n Index I-2 \r\n\r\n \r\n\r\n \r\n
\r\n

Kenneth H. Rosen is a Distinguished Member of the Technical Staff in AT&T Laboratories in Middletown, New Jersey. Dr.Rosen received his B.S. in Mathematics from the University of Michigan, Ann Arbor(l972), and his Ph.D. in Mathematics from M.I.T (l976), where he wrote his thesis in the area of number theory under the direction of Harold Stark. Before joining Bell Laboratories in l982, he held positions at the University of Colorado, Boulder; the Ohio State University Columbus; and the University

In 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, readable 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 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 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. The many improvements in the fifth edition have been made possible by the feedback and suggestions of a large number of instructors and students at many of the more than 500 schools where this book has been successfully used. There are many enhancements in this edition. The ancillary package has been enriched, and a companion website provides helpful material,making it easier for students and instructors to achieve their goals.

This text is designed for a one-or two-term introductory discrete mathematics course to be taken by students in a wide variety of majors, including mathematics, computer science, and engineering. College algebra is the only explicit prerequisite.

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 mathematically To achieve these goals, this text stresses mathematical reasoning and the different ways problems are solved. Five impor tant themes are interwoven in this text: mathematical reasoning, combinatorial analysis,discrete structures, algorithmic 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 The technique of mathematical induction is stressed through many different types of examples of such proofs and a careful explanation of why mathematical induction is a valid proof technique.

2. Combinatorial Analysis: An important problem-solving skill is the ability to count or enumerate objects. The discussion of enumeration in this book begins with the basic techniques of counting. The stress is on performing combinatorial analysis to solve counting problems, not on applying formulae.

3. Discrete Structures: A course in discrete mathematics should teach students how to work with discrete structures, which are the abstract mathematical structures used to represent discrete objects and relationships between these objects. These discrete structures include sets, permutations, relations, graphs, trees, and finite-state machines.

4. Algorithmic Thinking: Certain classes of problems are solved by the specification of an algorithm. After an algorithm has been described, a computer program can be constructed implementing it. The mathematical portions of this activity, which include the specification of the algorithm, the verification that it works properly, and the analysis of the computer memory and time required to perform it, are all covered in this text. Algorithms are described using both English and an easily understood form of pseudocode.

5. Applications and Modeling: Discrete mathematics has applications to almost every conceivable area of study There are many applications to computer science and data networking in this text, as well as applications to such diverse areas as chemistry botany, zoology, linguistics, geography business, and the Internet. These applications are natural and important uses of discrete mathematics and are not contrived. Modeling with discrete mathematics is an extremely important problem-solving skill, which students have the opportunity to develop by constructing their own models in some of the exercises.

Changes in the Fifth Edition

The fourth edition of this book has been used successfully at over 500 schools in the United States, dozens of Canadian universities, and at universities throughout Europe, Asia, and Oceania. Although the fourth edition has been an extremely effective text, many instructors, including longtime users, have requested changes designed to make this book more effective. I have devoted a significant amount of time and energy to satisfy these requests.

The result is a fifth edition that offers both instructors and students much more than the fourth edition did. Most significantly an improved organization of topics has been implemented in this fifth edition, making the book a more effective teaching tool.Substantial enhancements to the material devoted to logic, method of proof, and proof strategies are designed to help students master matheinatical reasoning. Additional explanations and examples have been added to clarify material.where students often have difficulty New exercises, both routine and challenging, have been inserted into the exer cise sets. Highly relevant applications. including many related to the Web and computer science, have been added. The companion website has benefited from extensive development activity and now provides tools students can use to master key concepts and explore the world of discrete mathematics.

Special Features

ACCESSIBILITY This text has proven to be easily read and understood by beginning students. There are no mathematical prerequisites beyond college algebra for almost all of this text. The few places in the book where calculus is referred to are explicitly noted. Most students should easily understand the pseudocode used in the text to express algorithms, regardless of whether they have formally studied programming languages. There is no formal computer science prerequisite.

Each chapter begins at an easily understood and accessible level. Once basic mathematical concepts have been carefully developed, more difficult material and applications to other areas of study are presented.

FLEXIBILITY This text has been carefully designed for flexible use. The dependence of chapters on previous material has been minimized. Each chapter is divided into sections of approximately the same length, and each section is divided into subsections that form natural blocks of material for teaching. Instructors can easily pace their lectures using these blocks.

WRITING STYLE The writing style in this book is direct and pragmatic. Precise mathematical language is used without excessive formalism and abstraction. Care has been taken to balance the mix of notation and words in mathematical statements.

EXTENSIVE CLASSROOM USE This book has been used at over 500 schools,and more than 400 have dsed it more than once. The feedback from instructors and students at many of the schools has helped make this fifth edition an even more successful teaching tool than previous editions.

MATHEMATICAL RIGOR AND PRECISION All definitions and theorems in this text are stated extremely carefully so that students will appreciate the precision of language and rigor needed in mathematics. Proofs are motivated and developed slowly;their steps are all carefully justified. Recursive definitions are explained and used extensively.

WORKED EXAMPLES Over 700 examples are used to illustrate concepts, relate different topics, and introduce applications. In most examples, a question is first posed,then its solution is presented with the appropriate amount of detail.

APPLICATIONS The applications included in this text demonstrate the utility of discrete mathematics in the solution of real-world problems. This text includes applications to a wide variety of areas, including computer science, data networking, psychology,chemistry, engineering, linguistics, biology business. and the Internet.

ALGORITHMS Results in discrete mathematics are often expressed in terms of algorithms; hence, key algorithms are introduced in each chapter of the book. These algorithms are expressed in words and in an easily understood form of structured pseudocode, which is described and specified in Appendix A.2. The computational complexity of the algorithms in the text is also analyzed at an elementary level.

HISTORICAL INFOTMATION The background of many topics is succinctly described in the text. Brief biographies of more than 60 mathematicians and computer scientists, accompanied by photos or images, are included as footnotes. These biographies include information about the lives, careers, and accomplishments of these impor tant contributors to discrete mathematics and images of these contributors are displayed.In addition, numerous historical footnotes are included that supplement the historical information in the main body of the text.

KEY TERMS AND RESULTS A list of key terms and results follows each chapter.The key terms incIude only the most important that students should learn, not every term defined in the chapter.

EXERCISES There are over 3500 exercises in the text. There are many different types of questions posed. There is an ample supply of straightforward exercises that develop basic skills, a large number of intermediate exercises, and many challenging exercises. Exercises are stated clearly and unambiguously, and all are carefully graded for level of difficulty. Exercise sets contain special discussions, with exercises, that develop new concepts not covered in the text, enabling students to discover new ideas through their own work.

Exercises that are somewhat more difficult than average are marked with a single star; those that are much more challenging are marked with two stars. Exercises whose solutions require calculus are explicitly noted. Exercises that develop results used in the text are clearly identified with the symbol. Answers or outlined solutions to all odd-numbered exercises are provided at the back of the text. The solutions include proofs in which most of the steps are clearly spelled out.

REVIEW QUESTIONS A set of review questions is provided at the end of each chapter. These questions are designed to help students focus their study on the most important concepts and techniques of that chapter. To answer these questions students need to write long answers, rather than just perform calculations or give short replies.

SUPPLEMEM EXERCISE SETS Each chapter is followed by a rich and varied set of supplementary exercises. These exercises are generally more difficult than those in the exercise sets following the sections. The supplementary exercises reinforce the concepts of the chapter and integrate different topics more effectively

COMPUTER PROJECTS Each chapter is followed by a set of computer projects.

The approximately 150 computer projects tie together what students may have learned in computing and in discrete mathematics. Computer projects that are more difficult than average, from both a mathematical and a programming point of view are marked with a star, and those that are extremely challenging are marked with two stars.

COMPUTATIONS AND EXPLORATIONS A set of computations and explorations is included at the conclusion of each chapter. These exercises (approximately 100in total) are designed to be completed using existing software tools, such as programs that students or instructors have written or mathematical computation packages such as

MAPLE or Mathematica. Many of these exercises give students the opportunity to uncover new facts and ideas through computation. (Some of these exercises are discussed in the book, Exploring Discrete Mathematics with MAPLE.)

WRITING PROJECTS Each chapter is followed by a set of writing projects. To do these projects students need to consult the mathematical literature. Some of these projects are historical in nature and may involve looking up original sources. Others are designed to serve as gateways to new topics and ideas. All are designed to expose students to ideas not covered in depth in the text. These projects tie together mathematical concepts and the writing process and help expose students to possible areas for future study (Suggested references for these projects can be found in the Student Solutions Guide)

APPENDIXES There are two appendixes to the text. The first covers exponentiaI and logarithmic functions, reviewing some basic material used heavily in the course; the second specifies the pseudocode used to describe algorithms in this text.

SUGGESTED READINGS A list of suggested readings for each chapter is provided in a section at the end of the text. These suggested readings include books at or below the level of this text, more difficult books, expository articles, and articles in which discoveries in discrete mathematics were originally published.

How to Use This Book

This text has been carefully written and constructed to support discrete mathematics courses at several levels and with differing foci. The following table identifies the core and optional sections. An introductory one-term course in discrete mathematics at the sophomore level can be based on the core sections of the text, with other sections covered at the discretion of the instructor. A two-term introductory course could include all the optional mathematics sections in addition to the core sections. Acourse with a strong computer science emphasis can be taught by covering some or all of the optional computer science sections.

Ancillaries

STUDENT SOLUTIONS GUIDE This student manual, available separately, contains full solutions to all the odd-numbered problems in the exercise sets. These solutions explain why a particular method is used and why it works. For some exercises, one or two other possible approaches are described to show that a problem can be solved in several different ways.Suggested references for the writing projects found at the end of each chapter are also included in this volume. The guide contains a guide to writing proofs and an extensive description of common mistakes students make in discrete mathematics It also includes sample tests and a sample crib sheet for each chapter, both designed to help students prepare for exams. Students find this guide extremely useful.

INSTRUCTOR'S RESOURCE GUIDE This manual contains full solutions to even-numbered exercises in the text. It also provides suggestions on how to teach the material in each chapter of the book, including the points to stress in each section and how to put the material into perspective. Furthermore, the manual contains a test bank of sample examination questions for each chapter, including some sample tests as well as the solutions to the sample questions. Finally sample syllabi are presented.

APPLICATIONS OF DISCRETE MATHEMATICS This ancillary, available in print format or downloadable from the website, can be used either in conjunction with the text or independently It contains more than 20 chapters (each with its own set of exercises) written by instructors who have used the text. Following a common format similar to that of the text, the chapters in this book can be used as a text for a separate course, for a student seminar, or for a student doing independent study.

TEST BANK An extensive test bank of more than l600 questions is available for use on Windows or Macintosh systems. Instructors can use this software to create their own tests by selecting questions of their choice or by random selection. Instructors can add their own headings and instructions, print scrambled versions of the same test, and edit the existing questions or add their own. A printed version of this test bank, including the questions and their answers, is included in the Instructor's Resource Guide.

EXPLORING DISCRETE MATHEMATICS AND ITS APPLICATIONS WITH MAPLE This ancillary is designed to help students use the MAPLE computer algebra system to do a wide range of computations in discrete mathematics. For each chapterof this text, this ancillary includes the following: a description of relevant MAPLE functions and how they are used, MAPLE programs that carry out relevant computations,suggestions and examples showing how MAPLE can be used for the computations and explorations at the end of each chapter, and exercises that can be worked using MAPLE.

Acknowledgments

I would like to thank the many instructors and students at a variety of schools who have used this book and provided me with their valuable feedback and helpful suggestions.

Their input has made this a much better book than it would have been otherwise. I especially want to thank Jerrold Grossman and John Michaels for their technical reviews of the fifth edition and their "eagle eyes," which have helped ensure the accuracy of this book. I also appreciate the help provided by all those who have submitted comments via the website.

I thank the reviewers of this fifth and the four previous editions. These reviewers have provided much helpful criticism and encouragement to me. I hope this edition lives up to their high expectations.

无封面