内容提要 
目录 
CIP 
序言 
前言 
作译者 
书摘 
书评 
最佳拍档 
《离散数学及其应用》一书是介绍离散数学理论和方法的经典教材，全书内容全面、由浅入深、通俗易懂，已经成为全球采用率最高的离散数学教材，被众多名校用作教材，并获得了极大的成功。作者参考教师和学生的反馈，并结合自身对教育的洞察，在第7版中做了大量的改进，使其成为更有效的教学工具。 本书基于该书第7版进行改编，保留了国内离散数学课程涉及的基本内容，更加适合作为国内高校计算机及相关专业本科生的离散数学课程教材。 具体改编情况如下： 第1章中补充了关于标准型的基础内容。 保留了逻辑和证明、集合、函数、计数和高级计数技术、关系、图、树和布尔代数等国内本科离散数学课程涉及的核心知识和基本内容。 删去了在其他课程中讲授的内容，如算法、数论和密码学、归纳和递归、离散概率、计算模型等。 对于保留章节，删去了编号为偶数的练习题。 删去了一些知识点的相关历史资料。 

The Adapter 's Words iv
Preface vi
About the Author xi
The Companion Website xii
To the Student xiv
List of Symbols xvii
1 The Foundations: Logic and Proofs..................................1
1.1 Propositional Logic............................................................1
1.2 Applications of Propositional Logic.............................................13
1.3 Propositional Equivalences....................................................20
1.4 Predicates and Quantifiers.....................................................32
1.5 Nested Quantifiers............................................................49
1.6 Rules of Inference............................................................59
1.7 Introduction to Proofs.........................................................70
1.8 Proof Methods and Strategy....................................................80
EndofChapter Material.....................................................96
2 Basic Structures: Sets, Functions, Sequences, Sums, and Matrices .........101
2.1 Sets........................................................................101
2.2 Set Operations...............................................................111
2.3 Functions...................................................................121
2.4 Sequences and Summations...................................................137
2.5 Cardinality of Sets...........................................................149
2.6 Matrices....................................................................156
EndofChapter Material.....................................................163
3 Counting...169
3.1 The Basics of Counting.......................................................169
3.2 The Pigeonhole Principle.......................................................181
3.3 Permutations and Combinations.......................................................188
3.4 Binomial Coefficients and Identities.......................................................195
3.5 Generalized Permutations and Combinations.......................................................202
3.6 Generating ermutations and Combinations.......................................................212
EndofChapter Material.....................................................216
4 Advanced Counting Techniques...................................223
4.1 Applications of Recurrence Relations...................................223
4.2 Solving Linear Recurrence Relations...................................233
4.3 DivideandConquer Algorithms and Recurrence Relations.......................245
4.4 Generating Functions.......................254
4.5 Inclusion朎xclusion.........................................................268
4.6 Applications of Inclusion朎xclusion...........................................273
EndofChapter Material...........................................279
5 Relations...........................................287
5.1 Relations and Their Properties...........................................287
5.2 nary Relations and Their Applications.........................................296
5.3 Representing Relations.........................................303
5.4 Closures of Relations.........................................309
5.5 Equivalence Relations........................................................318
5.6 Partial Orderings........................................................327
EndofChapter Material........................................................340
6 Graphs............................................................347
6.1 Graphs and Graph Models....................................................347
6.2 Graph Terminology and Special Types of Graphs................................356
6.3 Representing Graphs and Graph Isomorphism..................................372
6.4 Connectivity................................................................380
6.5 Euler and Hamilton Paths.....................................................393
6.6 ShortestPath Problems.......................................................404
6.7 Planar Graphs...............................................................414
6.8 Graph Coloring..............................................................421
EndofChapter Material.....................................................429
7 Trees...............................................................439
7.1 Introduction to Trees.........................................................439
7.2 Applications of Trees.........................................................450
7.3 Tree Traversal...............................................................463
7.4 Spanning Trees..............................................................475
7.5 Minimum Spanning Trees....................................................486
EndofChapter Material.....................................................491
8 Boolean Algebra...................................................497
8.1 Boolean Functions...........................................................497
8.2 Representing Boolean Functions..............................................504
8.3 Logic Gates.................................................................507
8.4 Minimization of Circuits.....................................................513
EndofChapter Material.....................................................525
Suggested Readings .....................................................531
Answers to Exercises 


图书在版编目（CIP）数据
离散数学及其应用（英文精编版·第7版）/（美）肯尼思H. 罗森（Kenneth H. Rosen）著. —北京：机械工业出版社，2016.12
（经典原版书库）
书名原文：Discrete Mathematics and Its Applications, Seventh Edition, English Abridgement
ISBN 9787111555360
Ⅰ. 离… Ⅱ. 肯… Ⅲ. 离散数学–高等学校–教材–英文 Ⅳ. O158
中国版本图书馆CIP数据核字（2016）第301589号 


In writing this book, I was guided by my longstanding 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 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. The many improvements in the seventh 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 any many universities in parts of the world, where this book has been successfully used.
This text is designed for a oneor twoterm introductory discrete mathematics course taken by students in a wide variety of majors, including mathematics, computer science, and engineering. 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 designed 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 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, 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. Both the science and the art of constructing proofs are addressed. 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 problemsolving 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 and analyz ealgorithms, 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 finitestate 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 beconstructed 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, biology, 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 problemsolving skill, which students have the opportunity to develop by constructing their own models in some of the exercises.
Features of the Book
ACCESSIBILITY This text has proved to be easily read and understood by beginning students. There are no mathematical prerequisites beyond college algebra for almost all the content of the text. Students needing extra help will find tools on the companion website for bringing their mathematical maturity up to the level of the 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.
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. The axioms used in proofs and the basic properties that follow from them are explicitly described in an appendix, giving students a clear idea of what they can assume in a proof. Recursive definitions are explained and used extensively.
WORKED EXAMPLES Many 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 realworld 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. The computational complexity of the algorithms in the text is also analyzed at an elementary level.
KEY TERMS AND RESULTS A list of key terms and results follows each chapter. The key terms include only the most important that students should learn, and not every term defined in the chapter.
EXERCISES There are many exercises in the text, with 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 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 right pointing hand symbol +. Answers or outlined solutions to all oddnumbered 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.
SUPPLEMENTARY 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 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 are designed to be completed using existing software tools, such as programs that students or instruc tors have written or mathematical computation packages such as MapleTM or MathematicaTM. Many of these exercises give students the opportunity to uncover new facts and ideas through computation. (Some of these exercises are discussed in the Exploring Discrete Mathematics companion workbooks available online.)
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 mathematical concepts together with the writing process and help expose students to possible areas for future study. (Suggested references for these projects can be found online or in the printed Student抯 Solutions Guide.)
SUGGESTED READINGS A list of suggested readings for the overall book and for each chapter is provided after the appendices. These suggested readings include books at or below the level of this text, more difficult books, expository articles, and articles in which discoveriesi in discrete mathematics were originally published. Some of these publications are classics, published many years ago, while others have been published in the last few years.
Ancillaries
STUDENT扴 SOLUTIONS GUIDE This student manual, available separately, contains full solutions to all oddnumbered problems in the exercise set. These solutions explain why a particular method is used and why it works. For some exercises, one or two other possible approacher are described to show what a problem can be solved in several different ways. Suggested references for the writing projects fornd at the end of each chapter are also included in this volume. Also included are a guide to writing proofs and an extensive description of common mistakes students make in discrete mathematics, plus sample tests and a sample crib sheet for each chapter designed to help students prepare for exam.
(ISBN10:0077353501) (ISBN13:9780077353506)
INSTRUCTOR扴 RESOURCE GUIDE This manual, available on the website and in printed form by request for instructors, contains full solutions to evennumbered exercises in the text. Suggestions on how to teach the material in each chapter of the book are provided, including the points to stress in each section and how to put the material into perspective. It also offers sample tests for each chapter and a test bank containing over 1500 exam questions to choose from. Answers to all sample tests and test bank questions are included. Finally, several sample syllabi are presented for courses with differing emphases and student ability levels.
(ISBN10:0077353498) (ISBN13:9780077353490)
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, JeanClaude Evard, and Georgia Mederer for their technical reviews of the seventh edition and their 揺agle 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 seventh and the six previous editions. These reviewers have provided much helpful criticism and encouragement to me. I hope this edition lives up to their high expectations.
Reviewers for the Seventh Edition
Philip Barry T.J.Duda Jerry Ianni
University of Minnesota, Minneapolis Columbus State Community College LaGuardia Community College
Miklos Bona Bruce Elenbogen Ravi Janardan
University of Florida University of Michigan, Dearborn University of Minnesota, Minneapolis
Kirby Brown Norma Elias Norliza Katuk
Queens College Purdue University, CalumetHammond University of Utara Malaysia
John Carter Herbert Enderton William Klostermeyer
University of Toronto University of California, Los Angeles University of North Florida
Narendra Chaudhari Anthony Evans Przemo Kranz
Nanyang Technological University Wright State University University of Mississippi
Allan Cochran Kim Factor Jaromy Kuhl
University of Arkansas Marquette University University of West Florida
Daniel Cunningham Margaret Fleck Loredana Lanzani
Buffalo State College University of Illinois, Champaign University of Arkansas, Fayetteville
George Davis Peter Gillespie Steven Leonhardi
Georgia State University Fayetteville State University Winona State University
Andrzej Derdzinski Johannes Hattingh Xu Liutong
The Ohio State University Georgia State University Beijing University of Posts and Telecommunications
Ronald Dotzel Ken Holladay Vladimir Logvinenko
University of MissouriSt.Louis University of New Orleans De Anza Community College
Darrell Minor Chris Rodger Christopher Swanson
Columbus State Community College Auburn University Ashland University
Keith Olson Sukhit Singh Bon Sy
Utah Valley University Texas State University, San Marcos Queens College
Yongyuth Permpoontanalarp David Snyder Matthew Walsh
King Mongkut抯 University of Technology, Thonburi Texas State University, San Marcos IndianaPurdue University, Fort Wayne
Galin Piatniskaia Wasin So Gideon Weinstein
University of Missouri, St.Louis San Jose State University Western Governors University
Stefan Robila Bogdan Suceava David Wilczynski
Montclair State University California State University, Fullerton University of Southern California
I would like to thank Bill Stenquist, Executive Editor, for his advocacy, enthusiasm, and support. His assistance with this edition has been essential. I would also like to thank the original editor, Wayne Yuhasz, whose insights and skills helped ensure the book抯 success, as well as all the many other previous editors of this book.
I want to express my appreciation to the staff of RPK Editorial Services for their valuable work on this edition, including Rose Kernan, who served as both the developmental editor and the production editor, and the other members of the RPK team, Fred Dahl, Martha McMaster, Erin Wagner, Harlan James, and Shelly GergerKnecthl. I thank Paul Mailhot of PreTeX,Inc., the compositor, for the tremendous amount to work he devoted to producing this edition, and for his intimate knowledge of LaTeX. Thanks also to Danny Meldung of Photo Affairs, Inc., who was resourceful obtaining images for the new biographical footnotes.
The accuracy and quality of this new edition owe much to Jerry Grossman and JeanClaude Evard, who checked the entire manuscript for technical accuracy and Georgia Mederer, who checked the accuracy of the answers at the end of the book and the solutions in the Student抯 Solutions Guide and Instructor抯 Resource Guide. Asusual,I cannot thank Jerry Grossman enough for all his work authoring these two essential ancillaries.
I would also express my appreciation the Science, Engineering, and Mathematics (SEM) Division of McGrawHill Higher Education for their valuable support for this new edition and the associated media content. In particular, thanks go to Kurt Strand:President, SEM, McGrawHill Higher Education, Marty Lange:EditorinChief, SEM, Michael Lange: Editorial Director, Raghothaman Srinivasan: Global Publisher, Bill Stenquist: Executive Editor, Curt Reynolds: Executive Marketing Manager, Robin A. Reed: Project Manager, Sandy Ludovissey: Buyer, Lorraine Buczek: Inhouse Developmental Editor, Brenda Rowles: Design Coordinator, Carrie K.Burger: Lead Photo Research Coordinator, and Tammy Juran: Media Project Manager.
Kenneth H. Rosen 

肯尼思 H. 罗森（Kenneth H. Rosen） 于1972年获密歇根大学安娜堡分校数学学士学位，1976年获麻省理工学院数学博士学位，其博士论文研究的是数论，导师是Harold Stark 。Rosen曾就职于科罗拉多大学、俄亥俄州立大学、缅因大学，后加盟贝尔实验室，现为AT&T实验室杰出成员。此外，他还是CRC出版社离散数学丛书的主编。Rosen博士在专业期刊上发表过许多关于数论和数学建模的文章。《初等数论及其应用》和《离散数学及其应用》这两本书均被国际上几百所大学广为采用。 



