本书是经典的离散数学教材，被全球数百所大学广为采用。本科教学版缩减了篇幅，保留的主要内容包括：逻辑和证明，集合、函数、序列、求和与矩阵，计数，关系，图，树，布尔代数。全书取材广泛，除包括定义、定理的严格陈述外，还配备大量的例题、图表、应用实例和练习。第8版做了与时俱进的更新，成为更加实用的教学工具。本书可作为高等院校数学、计算机科学和计算机工程等专业的教材，也可作为科技领域从业人员的参考书。

无

本书是根据我多年来讲授离散数学的经验和兴趣写成的。对学生而言，我的目的是为他们提供内容准确且可读性强的教材，清晰地介绍并展示离散数学中的概念和技术。对于那些爱怀疑的学生，我的目标是展示离散数学的相关性和实用性。对于计算机科学专业的学生，我希望为他们将来的学习提供一切必需的数学基础。而对于数学专业的学生，我希望帮助他们理解重要的数学概念，并且意识到为什么这些概念对应用来说很重要。最重要的是，希望本书既能达到这些目标，又不含太多的水分。
对教师而言，我的目的是利用数学中行之有效的教学技术来设计一个灵活而全面的教学工具：只要有本书在手，教师就能迅速地从中筛选内容，以最适合特定学生的方式有效地开展离散数学的教学工作。希望我已经实现了这些目标。
在过去的30年中，本书取得了极大的成功，被世界各地超过100万名学生使用，并被翻译成多种语言，对此我感到非常欣慰。此次第8版所做的许多改进，正是得益于大量读者的反馈和建议。在这些读者中，既有来自北美600多所学校的师生，又有来自全球各地众多高校的读者，他们都曾将本书成功用作教材。由于所收到的这些反馈，以及在不断更新中所投入的大量精力，我才能够在每次升级时显著提高本书的吸引力和有效性。
本教材是为一学期或两学期的离散数学入门课程而设计的，适用于数学、计算机科学、工程等各类专业的学生。大学代数是唯一要求的先修课程，不过，要想真正学好离散数学，还是需要有一定的数学素养。本书的设计目标是满足各种类型离散数学入门课程的需求，内容高度灵活且非常全面。我希望本书不仅是一本成功的教科书，而且成为学生在日后的学习和职业生涯中可以参考的有价值的资源。
离散数学课程的目标
离散数学课程有多个目标。学生应该学会一系列特定的数学知识并知道怎样应用它们，更重要的是，这门课应教会学生怎样运用数学逻辑思维。为了达到这些目标，本教材特别强调数学推理以及问题求解的不同方法。本书中，五个重要主题将交织在一起：数学推理，组合分析，离散结构，算法思维，以及应用与建模。一门成功的离散数学课程应该小心谨慎地融合并平衡所有五个主题。
●数学推理。学生必须理解数学推理以便阅读、领会并构造数学论证。本书开篇即讨论数理逻辑，这为后续讨论证明方法打下了基础。本书描述了构造证明的方法与技巧两个方面。本书特别强调数学归纳法，不仅给出了这种证明技术的许多不同类型的实例，还详细地解释了数学归纳法为什么是一种有效的证明技术。
●组合分析。一个重要的解题技巧就是计数或枚举对象。本书中关于枚举的讨论从计数的基本技术着手。重点是运用组合分析方法来解决计数问题并分析算法，而不是简单地应用公式。
●离散结构。离散数学课程应该教会学生如何处理离散结构，即表示离散对象以及对象之间关系的抽象数学结构。这些离散结构包括集合、置换、关系、图、树和有限状态机等。
●算法思维。有些类型的问题可以通过算法的规范说明来求解。当一个算法被清楚地描述后，就可以编写计算机程序来实现之。该活动涉及的数学部分包括该算法的规范说明、正确性的验证，以及执行算法所需要的计算机内存和时间分析等，这些在本书中均有阐述。算法将采用自然语言
原书采用英语，而中译版则采用汉语。——译者注和一种易于理解的伪代码形式来描述。
●应用与建模。离散数学在几乎每个可以想到的研究领域中都有应用。许多应用涉及本书提到的计算机科学和数据网络，还有一些应用涉及更为广泛的领域，如化学、生物学、语言学、地理学、商业和互联网等。这些是离散数学的自然而又重要的应用，而非人为编造的。用离散数学来建模是一项十分重要的问题求解技巧，学生可通过一些练习来自己构造模型，从而掌握这一技巧。
本书特色
易理解性。实践证明，本书对于初学者来说是易读易懂的。书中绝大部分内容不需要比大学代数更多的数学预备知识，需要额外帮助的学生可以在配套网站找到相应工具，以将数学素养提升到本书要求的水准。书中少数几处需要用到微积分知识的地方都已注明。大多数学生应该很容易理解用于表示算法的伪代码，无论是否正式学过程序设计语言。本书不要求正规计算机科学方面的预备知识。
每章都是从易于理解和易于领会的水平开始。一旦详细介绍了基本数学概念，就会给出稍难一些的内容以及在其他研究领域中的应用。
灵活性。为了便于灵活使用，本书做了精心的设计。各章对之前章节的依赖程度都被降到最低。每章分成长度大致相等的若干节，每节又根据内容划分成若干小节以方便教学。教师可以利用章节划分灵活地安排讲课进度。
写作风格。本书的写作风格是直接而又实用的。书中使用准确的数学语言，但没有采用过多的形式化与抽象，在数学命题中的记号和词语表达间做了精心的平衡。
数学严谨性和准确性。书中所有定义和定理的陈述都十分谨慎，这样学生可以欣赏语言的准确性和数学所需的严谨性。证明则是先由动机引入，然后再慢慢展开，并且所有步骤都经过了详细论证。
例题。全书共有超过400道例题，用来阐述概念、建立不同主题之间的关联以及介绍应用。在大部分例题中，首先提出问题，然后再以适量的细节给出解法。
应用。本书中的应用展示了离散数学在解决现实世界中的问题时的实用性。这些应用涉及广泛的领域，包括计算机科学、数据网络、心理学、化学、工程学、语言学、生物学、商业和互联网。
算法。离散数学的结论常常要用算法来表述，故书中多数章节都介绍了一些关键算法。这些算法采用文字叙述，同时也采用一种易于理解的结构化伪代码来描述。对于本书中的所有算法，都简要分析了其计算复杂度。
关键术语和结论。每章最后列出关键术语和结论。关键术语只列出学生必须学会的那些，而非该章中定义的每个术语。
练习。书中包含2000多道练习题，涵盖大量不同类型的问题。不仅提供了足够多的简单练习用于培养基本技能，还提供了大量中等难度的练习和许多具有挑战性的练习。练习的叙述清晰而无歧义，并按难易程度进行了分级。练习中还包含一些特殊的讨论来展开正文中没有涉及的新概念，使得学生能够通过自己的努力来发现新的想法。
那些比平均难度稍难的练习用一个星号（*）标记，而那些更具挑战性的练习则用两个星号（**）来标记。需要用微积分知识求解的练习会明确指出。有些练习的结果要在正文中用到，我们用符号来标识这类题目。本书最后给出了所有奇数编号练习的答案或解题纲要。答案中大部分证明的步骤都十分清晰。
复习题。每章后面都有一组复习题。设计这些问题是为了帮助学生重点学习该章最重要的概念和技术。要回答这些复习题，学生必须写出较长的答案，而不是仅做一些计算或给出简答。
补充练习。每章后面都有一组丰富多样的补充练习。这些练习通常比每节后面的练习难度更大。补充练习旨在强化该章中的概念，并把不同主题更有效地综合起来。
计算机课题。每章后面还有一组计算机课题。全书共有大约150道计算机课题，用于将学生在计算和离散数学中所学到的内容联系起来。对于那些从数学角度或程序设计角度来看难度超过平均水平的计算机课题，我们用一个星号（*）标记，而那些非常具有挑战性的题目则用两个星号（**）标记。
计算和探索。每章后面都有一组计算和探索性的问题，共有大约120道。完成这些练习需要借助现有的软件工具，诸如学生或教师自己编写的程序，或像Maple或Mathematica这样的数学计算软件包。这些练习大多为学生提供了通过计算来发现一些新事实或想法的机会。（其中一些练习在配套的在线练习册《探索离散数学》（Exploring Discrete Mathematics）中也有讨论。）
写作课题。每章后面都有一组写作课题，要完成这类题目，学生需要参考数学方面的文献。有些题目本质上是关于历史知识的，需要学生查找原始资料；其他题目则将带领学生通往新内容和新思想。这些练习旨在向学生展示正文中没有深入探讨的想法，通过把数学概念和写作过程结合起来，帮助学生面对未来可能的研究领域。（在网络版或印刷版的《学生解题指南》（Student’s Solutions Guide）中可以找到为这些题目准备的参考文献。）
教辅资源
关于本书教辅资源，只有使用本书作为教材的教师才可以申请，需要的教师可向麦格劳·希尔教育出版公司北京代表处申请，电话01057997618/7600，传真01059575582，电子邮件instructorchina@mheducationcom。——编辑注
《学生解题指南》。这本可以单独购买的学生手册包含所有奇数编号练习的完整解答。这些解答解释了为什么要用某种特定的方法以及为什么这种方法管用。对于有些问题，还给出了一两种其他可能的解法，以说明一个问题可以用多种不同方法来求解。指南的内容还包括：为每章后面的写作课题推荐的参考文献；关于如何撰写证明的指南；在离散数学学习中学生常犯的各类错误；为每章提供的考试样例及解答，以帮助学生准备考试。
《教师资料手册》。本手册在网站上提供，教师也可以申请印刷版，手册中包含书中所有偶数编号练习的完整解答。手册的内容还包括：关于如何讲授本书每章内容的建议，包括每节中应强调的重点以及如何组织内容；为每章提供的考试样例，以及一个包含1500多道考试题目的可选试题库，对于所有考试样例及试题库中的题目都给出了解答；针对不同的侧重点以及不同学生能力水平的课程教学大纲样本。
致谢
感谢所有将本书用作教材的教师和学生，他们来自不同的学校，并向我提供了很多有价值的反馈和有益的建议。正是有了他们的反馈，才使本书变得更为出色。特别感谢Jerrold Grossman和Dan Jordan，作为第8版的技术评审，他们以“鹰眼”般敏锐的目光确保了本书的准确性。在本书出版过程中的各个阶段，他们两位多次审阅了本书的每个角落，帮助消除了之前勘误表中的错误，并防止出现新的错误。
感谢Dan Jordan为《学生解题指南》和《教师资源手册》做出的贡献。他在更新这些教辅资源方面完成了令人钦佩的工作。感谢Jerrold Grossman，他是本书前7版教辅资源的作者，并为Dan提供了非常有价值的帮助。还要感谢许许多多曾经为本书创建并维护在线资源的人。特别感谢Dan Jordan和Rochus Boerner，他们所做的大量工作解决了配套网站的诸多问题（后面会介绍这个网站）。
感谢第8版以及所有之前版本的审稿人。他们给予我许多有益的批评和鼓励，希望这一版不会辜负他们的期望。自从本书第1版出版以来，已经有超过200位审稿人，其中有许多来自美国以外的国家。近期审稿人列表如下。
近期审稿人

感谢阅读过本书的学生，他们提供了很多建议并报告了一些勘误。在蒙茅斯大学时，曾经上过我的离散数学课程的学生，包括本科生和研究生，从方方面面帮助我改进了书中内容。
还要感谢麦格劳希尔高等教育（本书的出版商）的工作人员，以及Aptara的生产人员。我还想感谢兰登书屋原来的编辑Wayne Yuhasz，以及本书之前的许多编辑，他们的见解和技巧是本书成功的有力保障。

我想对产品经理Nora Devlin表示深深的谢意，她所完成的工作已远远超出了既定的职责。她不仅能力出众，而且责任心强，努力解决了新版本开发过程中出现的各种问题。
还要感谢Peggy Selle，作为内容产品经理，她管理着本书的生产过程。她全程跟踪本书的流程，并帮助解决生产过程中出现的许多问题。感谢Aptara的高级产品经理Sarita Yadav和她的同事，他们的努力工作确保了本书的生产质量。
我还要对麦格劳希尔高等教育的科学、工程和数学（SEM）部门的同仁表示感谢，他们对新版本以及相关的媒体内容给予了大力支持，包括：
●Mike Ryan，高等教育副总裁，负责作品统筹和学习内容管理
●Kathleen McMahon，数学与物理科学部门常务主管
●Caroline Celano，数学部门主管
●Alison Frederick，市场经理
●Robin Reed，首席产品开发师
●Sandy Ludovissey，采购人
●Egzon Shaqiri，设计师
●Tammy Juran，评估内容项目经理
●Cynthia Northrup，数字内容部门主管
●Ruth CzarneckiLichstein，业务产品经理
●Megan Platt，编辑协调人
●Lora Neyens和Jolynn Kilburg，项目经理
●Lorraine Buczek，内容授权专家

Kenneth H. Rosen

计算机\离散数学

本书是介绍离散数学理论和方法的经典教材，被全球数百所高校采用，获得了极大的成功。第8版做了与时俱进的修改，同时更新了配套教辅资源，成为更加实用的教学工具。本科教学版缩减了篇幅，适用于数学、计算机科学、计算机工程、信息技术等专业的学生。

本书特色
·章节：保留了逻辑和证明、基本结构、计数和高级计数、关系、图、数和布尔代数等内容，删除了算法、数论和密码学、归纳与递归、离散概率、计算模型等内容。
·例题：共400多道例题，用于阐明概念、建立不同主题之间的关联以及介绍实际应用。
·应用：涉及的领域包括计算机科学、数据网络、心理学、化学、工程学、语言学、生物学、商业和因特网等，展示了离散数学的实用性。
·算法：每一章都介绍了一些关键算法，提供伪代码，并简要分析其计算复杂度。
·练习、复习题和补充练习：共有2000多道难度各异的练习题，可以满足不同层次学生的需求。此外，还有一些研究性题目，帮助学生通过计算来探索新知识和新想法。

[美]肯尼思·H. 罗森（Kenneth H. Rosen） 著：肯尼思·H. 罗森（Kenneth H. Rosen） 于1972年获密歇根大学安娜堡分校数学学士学位，1976年获麻省理工学院数学博士学位。Rosen曾就职于科罗拉多大学、俄亥俄州立大学、缅因大学和蒙茅斯大学，教授离散数学、算法设计和计算机安全方面的课程；他还曾加盟贝尔实验室，并且是AT&T贝尔实验室的杰出技术人员。他的著作《初等数论及其应用》和《离散数学及其应用》均被翻译成多种语言，在全球数百所大学中广为采用。

徐六通 杨娟 吴斌 译 陈琼 改编：暂无简介

从在路边小摊贩处扫码完成支付到为黑洞拍摄第一张照片，再到各类世纪工程的竣工，这一切进步与奇迹的背后都离不开计算机科学与技术的飞速发展。
如果你也想为将来的奇迹做出自己的贡献，就必须先了解计算是什么、计算机的工作原理是什么、计算机是如何解题的等问题。你需要学习的第一门基础课就是离散数学。什么是离散数学？离散数学是致力于研究离散对象的数学分支。说得更通俗一点，就是利用计算机进行问题求解时，一切问题背后的原理性东西均属于离散数学的范畴，或者说离散数学就是计算机科学的数学语言。
离散数学一直被IEEECS和ACM认定为计算机专业最核心的课程，也是我国计算机科学与技术专业的核心基础课程。当你学习这门课程的时候，会发现离散数学为许多计算机专业课程提供了理论基础，尤其是为课程中大量的算法提供了基础。
本书英文版自出版以来在北美发行超过450000册，目前已经被翻译成西班牙文、法文、葡萄牙文、希腊文、中文、越南文和韩文等，在世界各地发行数十万册。
第8版对许多内容进行了完善、更新、补充和润色，所有这一切都是为了使本书成为现代离散数学课程的更加有效的教学工具。本书清晰地介绍并展示了离散数学中的概念和技术，行文流畅，通俗易懂。书中包含大量有趣而实用的例子，吸引读者广泛好奇心的推荐读物，以及帮助读者掌握离散数学的概念和技巧的丰富练习题，为计算机科学学生将来的学习提供了一切必需的数学基础。此外，本书还提供了一个非常有价值的网站资源——在线学习中心（OLC），帮助学生评估自身学习状况，学习撰写证明并避免常见错误，从各个方面提高学生学习和实际解决问题的能力，引领学生探索离散数学的新应用。
在本次翻译工作中，徐六通翻译全书（完整版）前言、第1章至第4章、附录及推荐读物，吴斌翻译第5章至第8章，杨娟翻译第9章至第13章。由于译者水平所限，尽管已经修正了之前版本中的一些错误，但是难免还会有不妥的地方，敬请读者不吝赐教。

译者
2019年8月于北京

出版者的话
改编者序
译者序
前言
在线资源
致学生
作者简介
符号表
第1章基础：逻辑和证明1
11命题逻辑1
111引言1
112命题1
113条件语句4
114复合命题的真值表6
115逻辑运算符的优先级7
116逻辑运算和比特运算7
奇数编号练习8
12命题逻辑的应用11
121引言11
122语句翻译11
123系统规范说明12
124布尔搜索12
125逻辑谜题13
126逻辑电路14
奇数编号练习15
13命题等价式17
131引言17
132逻辑等价式17
133德·摩根律的运用20
134构造新的逻辑等价式20
135可满足性21
136可满足性的应用21
137可满足性问题求解24
奇数编号练习24
14谓词和量词26
141引言26
142谓词26
143量词27
144有限域上的量词30
145受限域的量词30
146量词的优先级31
147变量绑定31
148涉及量词的逻辑等价式31
149量化表达式的否定32
1410语句到逻辑表达式的翻译33
1411系统规范说明中量词的使用34
1412选自路易斯·卡罗尔的例子35
1413逻辑程序设计35
奇数编号练习36
15嵌套量词39
151引言39
152理解涉及嵌套量词的语句39
153量词的顺序40
154数学语句到嵌套量词语句的翻译41
155嵌套量词到自然语言的翻译42
156汉语语句到逻辑表达式的翻译43
157嵌套量词的否定43
奇数编号练习44
16推理规则47
161引言47
162命题逻辑的有效论证47
163命题逻辑的推理规则48
164使用推理规则建立论证50
165消解律51
166谬误51
167量化命题的推理规则52
168命题和量化命题推理规则的组合使用53
奇数编号练习54
17证明导论56
171引言56
172一些专用术语56
173理解定理是如何陈述的56
174证明定理的方法56
175直接证明法57
176反证法58
177归谬证明法60
178证明中的错误62
179良好的开端63
奇数编号练习63
18证明的方法和策略64
181引言64
182穷举证明法和分情形证明法64
183存在性证明67
184唯一性证明69
185证明策略69
186寻找反例71
187证明策略实践71
188拼接72
189开放问题的作用74
1810其他证明方法74
奇数编号练习75
章末资料（在线）
标注“在线”的章节，请访问华章网站（wwwhzbookcom）下载。——编辑注
第2章基本结构：集合、函数、序列、求和与矩阵77
21集合77
211引言77
212文氏图79
213子集79
214集合的大小80
215幂集81
216笛卡儿积81
217使用带量词的集合符号83
218真值集和量词83
奇数编号练习83
22集合运算84
221引言84
222集合恒等式87
223扩展的并集和交集89
224集合的计算机表示90
225多重集91
奇数编号练习92
23函数94
231引言94
232一对一函数和映上函数96
233反函数和函数合成98
234函数的图101
235一些重要的函数101
236部分函数103
奇数编号练习104
24序列与求和106
241引言106
242序列106
243递推关系107
244特殊的整数序列109
245求和111
奇数编号练习114
25集合的基数116
251引言116
252可数集合117
253不可数集合119
奇数编号练习121
26矩阵122
261引言122
262矩阵算术123
263矩阵的转置和幂124
26401矩阵125
奇数编号练习126
章末资料（在线）
第3章计数128
31计数的基础128
311引言128
312基本的计数原则128
313比较复杂的计数问题132
314减法法则（两个集合的容斥原理）133
315除法法则135
316树图135
奇数编号练习136
32鸽巢原理138
321引言138
322广义鸽巢原理139
323鸽巢原理的几个简单应用141
奇数编号练习142
33排列与组合143
331引言143
332排列143
333组合145
奇数编号练习147
34二项式系数和恒等式149
341二项式定理149
342帕斯卡恒等式和三角形151
343其他的二项式系数恒等式152
奇数编号练习153
35排列与组合的推广155
351引言155
352有重复的排列155
353有重复的组合155
354具有不可区别物体的集合的排列158
355把物体放入盒子159
奇数编号练习161
36生成排列和组合163
361引言163
362生成排列163
363生成组合165
奇数编号练习166
章末资料（在线）
第4章高级计数技术167
41递推关系的应用167
411引言167
412用递推关系构造模型168
413算法与递推关系172
奇数编号练习174
42求解线性递推关系176
421引言176
422求解常系数线性齐次递推关系176
423求解常系数线性非齐次递推关系180
奇数编号练习182
43分治算法和递推关系184
431引言184
432分治递推关系184
奇数编号练习189
44生成函数191
441引言191
442关于幂级数的有用事实191
443计数问题与生成函数194
444使用生成函数求解递推关系197
445使用生成函数证明恒等式198
奇数编号练习199
45容斥201
451引言201
452容斥原理202
奇数编号练习205
46容斥原理的应用205
461引言205
462容斥原理的另一种形式206
463埃拉托斯特尼筛法206
464映上函数的个数207
465错位排列208
奇数编号练习209
章末资料（在线）
第5章关系211
51关系及其性质211
511引言211
512函数作为关系212
513集合的关系212
514关系的性质213
515关系的组合215
奇数编号练习217
52n元关系及其应用219
521引言219
522n元关系220
523数据库和关系220
524n元关系的运算221
525SQL223
526数据挖掘中的关联规则224
奇数编号练习226
53关系的表示227
531引言227
532用矩阵表示关系227
533用图表示关系229
奇数编号练习231
54关系的闭包232
541引言232
542不同类型的闭包232
543有向图中的路径233
544传递闭包234
545沃舍尔算法236
奇数编号练习239
55等价关系239
551引言239
552等价关系240
553等价类241
554等价类与划分243
奇数编号练习245
56偏序247
561引言247
562字典顺序249
563哈塞图250
564极大元与极小元251
565格253
566拓扑排序254
奇数编号练习256
章末资料（在线）
第6章图259
61图和图模型259
611图模型261
奇数编号练习266
62图的术语和几种特殊的图268
621引言268
622基本术语268
623一些特殊的简单图270
624二分图271
625二分图和匹配273
626特殊类型图的一些应用276
627从旧图构造新图277
奇数编号练习279
63图的表示和图的同构281
631引言281
632图的表示281
633邻接矩阵282
634关联矩阵283
635图的同构284
636判定两个简单图是否同构284
奇数编号练习287
64连通性290
641引言290
642通路290
643无向图的连通性292
644图是如何连通的293
645有向图的连通性295
646通路与同构296
647计算顶点之间的通路数297
奇数编号练习298
65欧拉通路与哈密顿通路300
651引言300
652欧拉通路与欧拉回路300
653哈密顿通路与哈密顿回路304
654哈密顿回路的应用306
奇数编号练习307
66最短通路问题309
661引言309
662最短通路算法311
663旅行商问题315
奇数编号练习316
67平面图318
671引言318
672欧拉公式319
673库拉图斯基定理321
奇数编号练习323
68图着色324
681引言324
682图着色的应用327
奇数编号练习328
章末资料（在线）
第7章树331
71树的概述331
711有根树332
712树作为模型335
713树的性质336
奇数编号练习338
72树的应用340
721引言340
722二叉搜索树340
723决策树342
724前缀码344
725博弈树346
奇数编号练习349
73树的遍历351
731引言351
732通用地址系统352
733遍历算法352
734中缀、前缀和后缀记法358
奇数编号练习360
74生成树362
741引言362
742深度优先搜索363
743宽度优先搜索365
744回溯的应用367
745有向图中的深度优先搜索369
奇数编号练习370
75最小生成树371
751引言371
752最小生成树算法372
奇数编号练习375
章末资料（在线）
第8章布尔代数377
81布尔函数377
811引言377
812布尔表达式和布尔函数378
813布尔代数恒等式379
814对偶性380
815布尔代数的抽象定义381
奇数编号练习382
82布尔函数的表示382
821积之和展开式383
822函数完备性384
奇数编号练习384
83逻辑门电路385
831引言385
832门的组合385
833电路的例子386
834加法器388
奇数编号练习389
84电路的极小化390
841引言390
842卡诺图391
843无须在意的条件396
844奎因莫可拉斯基方法396
奇数编号练习399
章末资料（在线）
推荐读物（在线）
参考文献（在线）
奇数编号练习答案（在线）
请访问华章网站www.hzbook.com下载。