离散数学及其应用(英文影印版.第6版)

　　本书是介绍离散数学理论和方法的经典教材，已经成为采用率最高的离散数学教材，仅在美国就被600多所高校用作教材，获得了极大的成功。中文版也已被国内大学广泛采用为教材。第6版在前五版的基础上做了大量的改进，使其成为更有效的教学工具。.
　　 本书可作为1至2个学期的离散数学课入门教材，适用于数学，计算机科学。计算机工程．信息技术等专业的学生。
　　 第6版的特点
　　 ·易入门：实践证明本书对初学者来说易读易懂。
　　 ·灵活：本教材为灵活使用做了精心设计，各章对其前面内容的依赖降到最小。
　　 ·写作风格：直接和实用。
　　 ·数学严密性和准确性：书中所有定义和定理的陈述都十分详细，以确保语言的准确性和数学所需的严密性。
　　 ·实例：书中有750多个实例，用于阐明概念，联系不同内容，并引入各种应用。
　　 ·应用：书中叙述的应用展示了离散数学在解决现实问题中的使用价值，涉及的应用领域包括计算机科学。数据网络、心理学，化学，工程。语言学、生物学、商业和互联网等。..
　　 ·算法：离散数学的结论常常要用算法来表示，因此本书每一章都介绍了一些关键算法。这些算法既可以用文字叙述，也可以用更易于理解的结构化伪码来叙述。附录a．3对伪码作了描述和规范。本书对所有算法的计算复杂性也都给出了初步的分析。
　　 ·历史资料：本书对许多主题的背景作了简要介绍，并以脚注的形式给出了65位对离散数学做出过重要贡献的数学家和计算机科学家的简短传记。
　　 ·关键术语和结论：每一章后面都列出了本章的关键术语和结论。
　　 ·丰富的练习、复习题和补充练习：新版增加了400多道练习，使全书的总练习数达到3800多道。本书不仅提供了足够多的简单习题用于练习基本技巧，还提供了大量的中等难度的练习和许多有挑战性的练习，以满足不同层次学生的学习需求。同时，每章最后都有一组复习题和一组丰富多样的补充练习。
　　 ·计算机课题：每一章后面还有一组计算机课题，大约有150个这样的题目，把学生已经学到的计算和离散数学的内容结合在一起。
　　 ·计算和研究：每一章的结论部分都有一组计算和研究性问题，为学生提供了通过计算发现新事实或新思想的机会。
　　 ·写作题目：每一章后面都有一组应该书面完成的题目。要完成这类题目，学生需要查阅参考文献，把数学概念和书面写作的过程结合在一起，以帮助学生研究和思考正文中没有深入探讨的思想，便于其未来的学习和研究。...

contents.
preface
about the author
to the student
list of symbols
1 the foundations: logic and proofs
1.1 propositional logic
1.2 propositional equivalences
1.3 predicates and quantifiers
1.4 nested quantifiers
1.5 rules oflnference
1.6 introduction to proofs
1.7 proof methods and strategy
end-of-chapter material
2 basic structures: sets, functions, sequences, and sums
2.1 sets
2.2 set operations
2.3 functions
2.4 sequences and summations
end-of-chapter material

　　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 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 sixth 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 schools where this book has been successfully used. There are many enhancements in this edition. The companion website has been substantially enhanced and more closely integrated with the text, providing helpful material to make it easier for students and instructors to achieve their goals.
　　This text is designed for a oneor two-term 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.
　　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 an 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 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 and analyze algorithms, 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 ofpseudocode.
　　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 Intemet. 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 Sixth Edition
　　The fifth edition of this book has been used successfully at over 600 schools in the United States, dozens of Canadian universities, and at universities throughout Europe, Asia, and Oceania. Although the fifth 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 and I have worked hard to find my own ways to make the book better.
　　The result is a sixth edition that offers both instructors and students much more than the fifth edition did. Most significantly, an improved organization of topics has been implemented in this sixth edition, making the book a more effective teaching tool. Changes have been implemented that make this book more effective for students who need as much help as possible, as well as for those students who want to be challenged to the maximum degree. Substantial enhancements to the material devoted to logic, method of proof, and proof strategies are designed to help students master mathematical 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 exercise sets. Highly relevant applications, including many related to the Intemet and computer science, have been added. The MathZone 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 proved to be easily read and understood by beginning students. There are no mathematical prerequisites beyond college algebra for almost all of this text. Students needing extra help will find tools on the MathZone 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.