编辑推荐
《计算机科学丛书:离散数学及其应用(原书第7版)(本科教学版)》由机械工业出版社出版。
作者简介
关于作者Discrete Mathematics and Its Applications,7EKenneth H.Rosen 作为位于新泽西州蒙茅斯县的AT＆T实验室杰出技术会员已经拥有一段很长的职业生涯。目前他在蒙茅斯大学任访问研究教授，为研究生讲授计算机科学课程。
Rosen博士于1972年获得位于安娜堡的密歇根大学数学学士学位，1976年获得麻省理工学院数学博士学位，在哈罗德·斯塔克（Harold Stark）的指导下他撰写了数论方面的博士论文。1982年加入贝尔实验室之前，他曾就职于科罗拉多大学博尔德分校；哥伦布市的俄亥俄州立大学；在欧洛诺市的缅因大学任数学副教授。在AT&T工作时，他在蒙茅斯大学任教，教授离散数学、编码理论和数据安全方面的课程。他目前教授算法设计以及计算机安全和密码学方面的课程。
Rosen博士在数论及数学建模的专业期刊上发表了大量论文。他是《初等数论及其应用》（Elementary Number Theory and Its Applications）的作者，该书由Pearson(培生)出版并广为采用，目前第6版也已经翻译成了中文。他也是《离散数学及其应用》(Discrete Mathematics and Its Applications)的作者，该书由McGraw-Hill(麦格劳希尔)出版，目前是第7版。《离散数学及其应用》(Discrete Mathematics and Its Applications)自出版以来在北美发行超过350 000册，在世界其余各地发行成千上万册。这本书也已经被翻译成法文、希腊文、中文、越南文和韩文。他还是《UNIX：参考大全》(UNIX:The Complete Reference)、《UNIX系统V版本4：简介》(UNIX System V Release4:An Introduction)、《佳UNIX小技巧》(Best UNIX Tips Ever)的合著者，这些书均由奥斯本/麦格劳希尔出版。这些书发行超过150 000册，并翻译成中文、德文、西班牙文和意大利文。Rosen博士还是由CRC出版社出版的《离散及组合数学手册》(Handbook of Discrete and Combinatorial Mathematics)的编辑，他是CRC离散数学丛书的顾问编辑，丛书包括超过55卷论述离散数学的不同方面，其中大多数内容在这本手册中有介绍。Rosen博士现任《离散数学》（Discrete Mathematics）期刊副主编，负责审阅提交的论文，涉及离散数多个领域，包括图论、枚举和数论。他对将数学软件集成到教育和专业环境中很有兴趣，并在这些方面参与和Waterloo Maple Inc.的MapleTM软件的一些合作项目。Rosen博士还和多家出版公司合作开发作业交付平台。
在贝尔实验室和AT&T实验室期间，Rosen博士所从事的项目涉猎广泛，包括运筹学研究、计算机和通信设备的产品线规划和技术评估。他帮助规划AT&T在多媒体领域的产品和服务，包括视频会议、语音识别、语音合成和图像联网。他为AT&T使用新技术做评估，并在图像联网领域从事标准化工作。他还发明了许多新服务，并持有超过55项专利。他的一个有趣的项目涉及帮助评估AT&T为提高吸引力而采用的技术，这也是EPCOT中心的一部分。
目录
出版者的话
改编者序
译者序
前言
配套网站
致学生
关于作者
符号表
第1章基础：逻辑和证明1
1.1命题逻辑1
1.1.1引言1
1.1.2命题1
1.1.3条件语句4
1.1.4复合命题的真值表7
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命题等价式16
1.3.1引言16
1.3.2逻辑等价式17
1.3.3德·摩根律的运用19
1.3.4构造新的逻辑等价式19
1.3.5命题的可满足性20
1.3.6可满足性的应用20
1.3.7可满足性问题求解22
练习22
1.4谓词和量词24
1.4.1引言24
1.4.2谓词24
1.4.3量词25
1.4.4约束论域的量词28
1.4.5量词的优先级29
1.4.6变量绑定29
1.4.7涉及量词的逻辑等价式29
1.4.8量化表达式的否定30
1.4.9语句到逻辑表达式的翻译31
1.4.10系统规范说明中量词的使用32
1.4.11选自路易斯·卡罗尔的例子33
1.4.12逻辑程序设计33
练习34
1.5嵌套量词37
1.5.1引言37
1.5.2理解涉及嵌套量词的语句37
1.5.3量词的顺序38
1.5.4数学语句到嵌套量词语句的翻译39
1.5.5嵌套量词到自然语言的翻译40
1.5.6汉语语句到逻辑表达式的翻译40
1.5.7嵌套量词的否定41
练习42
1.6推理规则45
1.6.1引言45
1.6.2命题逻辑的有效论证45
1.6.3命题逻辑的推理规则46
1.6.4使用推理规则建立论证48
1.6.5消解律49
1.6.6谬误49
1.6.7量化命题的推理规则50
1.6.8命题和量化命题推理规则的组合使用51
练习52
1.7证明导论53
1.7.1引言53
1.7.2一些专用术语53
1.7.3理解定理是如何陈述的54
1.7.4证明定理的方法54
1.7.5直接证明法54
1.7.6反证法55
1.7.7归谬证明法57
1.7.8证明中的错误59
1.7.9良好的开端60
练习60
1.8证明的方法和策略61
1.8.1引言61
1.8.2穷举证明法和分情形证明法61
1.8.3存在性证明65
……
1.8.5证明策略66
1.8.6寻找反例68
1.8.7证明策略实践68
1.8.8拼接68
1.8.9开放问题的作用71
1.8.10其他证明方法71
练习72
关键术语和结论73
复习题75
补充练习75
计算机课题78
计算和探索78
写作课题78
第2章基本结构：集合、函数、序列、求和与矩阵79
2.1集合79
2.1.1引言79
2.1.2文氏图81
2.1.3子集81
2.1.4集合的大小82
2.1.5幂集83
2.1.6笛卡儿积83
2.1.7使用带量词的集合符号84
2.1.8真值集和量词84
练习85
2.2集合运算86
2.2.1引言86
2.2.2集合恒等式88
2.2.3扩展的并集和交集90
2.2.4集合的计算机表示91
练习92
2.3函数94
2.3.1引言94
2.3.2一对一函数和映上函数96
2.3.3反函数和函数组合98
2.3.4函数的图100
2.3.5一些重要的函数101
2.3.6部分函数103
练习103
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可数集116
2.5.3不可数集合118
练习120
2.6矩阵121
2.6.1引言121
2.6.2矩阵算术122
2.6.3矩阵的转置和幂123
2.6.40—1矩阵124
练习125
关键术语和结论126
复习题128
补充练习129
计算机课题131
计算和探索131
写作课题131
第3章计数132
3.1计数的基础132
3.1.1引言132
3.1.2基本的计数原则132
3.1.3比较复杂的计数问题136
3.1.4减法法则（两个集合的容斥原理）137
3.1.5除法法则138
3.1.6树图138
练习139
3.2鸽巢原理141
3.2.1引言141
3.2.2广义鸽巢原理142
3.2.3鸽巢原理的几个简单应用144
练习145
3.3排列与组合146
3.3.1引言146
3.3.2排列146
3.3.3组合148
练习150
3.4二项式系数和恒等式151
3.4.1二项式定理151
3.4.2帕斯卡恒等式和三角形153
3.4.3其他的二项式系数恒等式154
练习155
3.5排列与组合的推广157
3.5.1引言157
3.5.2有重复的排列157
3.5.3有重复的组合157
3.5.4具有不可区别物体的集合的排列160
3.5.5把物体放入盒子161
练习163
3.6生成排列和组合165
3.6.1引言165
3.6.2生成排列165
3.6.3生成组合166
练习167
关键术语和结论168
复习题169
补充练习170
计算机课题173
计算和探索173
写作课题174
第4章高级计数技术175
4.1递推关系的应用175
4.1.1引言175
4.1.2用递推关系构造模型176
4.1.3算法与递推关系180
练习181
4.2求解线性递推关系184
4.2.1引言184
4.2.2求解常系数线性齐次递推关系184
4.2.3常系数线性非齐次的递推关系188
练习190
4.3分治算法和递推关系191
4.3.1引言191
4.3.2分治递推关系192
练习197
4.4生成函数198
4.4.1引言198
4.4.2关于幂级数的有用事实198
4.4.3计数问题与生成函数201
4.4.4使用生成函数求解递推关系204
4.4.5使用生成函数证明恒等式205
练习206
4.5容斥208
4.5.1引言208
4.5.2容斥原理208
练习211
4.6容斥原理的应用212
4.6.1引言212
4.6.2容斥原理的另一种形式212
4.6.3埃拉托色尼筛213
4.6.4映上函数的个数213
4.6.5错位排列214
练习216
关键术语和结论216
复习题217
补充练习218
计算机课题221
计算和探索221
写作课题221
第5章关系223
5.1关系及其性质223
5.1.1引言223
5.1.2函数作为关系224
5.1.3集合的关系224
5.1.4关系的性质225
5.1.5关系的组合227
练习228
5.2n元关系及其应用230
5.2.1引言230
5.2.2n元关系231
5.2.3数据库和关系231
5.2.4n元关系的运算232
5.2.5SQL234
练习235
5.3关系的表示236
5.3.1引言236
5.3.2用矩阵表示关系236
5.3.3用图表示关系238
练习239
5.4关系的闭包240
5.4.1引言240
5.4.2闭包241
5.4.3有向图中的路径241
5.4.4传递闭包242
5.4.5沃舍尔算法245
练习247
5.5等价关系247
5.5.1引言247
5.5.2等价关系248
5.5.3等价类249
5.5.4等价类与划分250
练习253
5.6偏序255
5.6.1引言255
5.6.2字典顺序256
5.6.3哈塞图257
5.6.4极大元与极小元259
5.6.5格260
5.6.6拓扑排序261
练习263
关键术语和结论265
复习题267
补充练习268
计算机课题271
计算和探索272
写作课题272
第6章图273
6.1图和图模型273
6.1.1图模型276
练习279
6.2图的术语和几种特殊的图281
6.2.1引言281
6.2.2基本术语281
6.2.3一些特殊的简单图283
6.2.4二分图284
6.2.5二分图和匹配286
6.2.6特殊类型图的一些应用288
6.2.7从旧图构造新图289
练习291
6.3图的表示和图的同构293
6.3.1引言293
6.3.2图的表示293
6.3.3邻接矩阵293
6.3.4关联矩阵295
6.3.5图的同构296
6.3.6判定两个简单图是否同构296
练习298
6.4连通性301
6.4.1引言301
6.4.2通路301
6.4.3无向图的连通性303
6.4.4图是如何连通的304
6.4.5有向图的连通性306
6.4.6通路与同构307
6.4.7计算顶点之间的通路数308
练习308
6.5欧拉通路与哈密顿通路311
6.5.1引言311
6.5.2欧拉通路与欧拉回路311
6.5.3哈密顿通路与哈密顿回路315
6.5.4哈密顿回路的应用316
练习318
6.6最短通路问题320
6.6.1引言320
6.6.2最短通路算法322
6.6.3旅行商问题325
练习326
6.7平面图328
6.7.1引言328
6.7.2欧拉公式329
6.7.3库拉图斯基定理332
练习333
6.8图着色334
6.8.1引言334
6.8.2图着色的应用337
练习338
关键术语和结论340
复习题343
补充练习344
计算机课题348
计算和探索349
写作课题349
第7章树351
7.1树的概述351
7.1.1有根树352
7.1.2树作为模型355
7.1.3树的性质356
练习358
7.2树的应用360
7.2.1引言360
7.2.2二叉搜索树360
7.2.3决策树362
7.2.4前缀码364
7.2.5博弈树365
练习369
7.3树的遍历371
7.3.1引言371
7.3.2通用地址系统371
7.3.3遍历算法372
7.3.4中缀、前缀和后缀记法377
练习379
7.4生成树380
7.4.1引言380
7.4.2深度优先搜索382
7.4.3宽度优先搜索384
7.4.4回溯的应用385
7.4.5有向图中的深度优先搜索387
练习388
7.5最小生成树390
7.5.1引言390
练习
关键术语和结论
复习题
补充练习
计算机课题
计算和探索
写作课题
第8章布尔代数
8.1布尔函数
8.1.1引言
8.1.2布尔表达式和布尔函数
8.1.3布尔代数恒等式
8.1.4对偶性
8.1.5布尔代数的抽象定义
练习
8.2布尔函数的表示
8.2.1积之和展开式
8.2.2函数完备性
练习
8.3逻辑门电路
8.3.1引言
8.3.2门的组合
8.3.3电路的例子
8.3.4加法器
练习
8.4电路的极小化
8.4.1引言
8.4.2卡诺图
8.4.3无须在意的条件
8.4.4奎因—莫可拉斯基方法
练习
关键术语和结论
复习题
补充练习
计算机课题
计算和探索
写作课题
推荐读物
参考文献
练习答案
序言
改编者序Discrete Mathematics and Its Applications,7EKenneth H.Rosen编著的《离散数学及其应用》一书包括计算机专业学生必须掌握的数学基础知识，并且给出许多应用离散数学解决现实问题的实例，一些知识点给出相关的历史背景知识，配有大量计算、研究和实践的题目及推荐参考读物。该书内容全面，由浅入深，通俗易懂，被全球很多大学使用，是一本非常优秀的教材。
近年来，国内的许多高校都采用国外的优秀原版书作为教材。而《离散数学及其应用》原版书篇幅较长，使得部分中国学生难以阅读。为了将这本优秀教材介绍给更多的中国学生，在保留原作者写作风格的前提下，我们删减了部分章节内容编成此本科教学版，以适合中国学生的使用和阅读。
原书中的一些内容，如第3、4、5、7、13章（算法、数论和密码学、归纳与递归、离散概率、计算模型），在其他课程中已有讲授或单独作为一门课程讲授，我们在本科教学版中将这些内容删除，保留了逻辑和证明、集合、函数、计数和高级计数技术、关系、图、树和布尔代数等内容。
原书有0多道各种类型的练习题，其中包括帮助学生掌握基本概念的练习、提高应用离散数学知识解决问题的计算机课题及计算和探索题目，以及需要查阅课外资料扩展学习的写作课题。题目按难易程度分级，分为简单、难度适中和难度较大各种类型。为了保持原书的特点，对于保留的章节，我们删去了每节后的偶数练习题，这样可以使得原书的各种类型、不同难度的习题都得以保留。关于一些知识点的相关历史背景知识未作保留，目的是减少本书的篇幅。
感谢原书作者Kenneth H.Rosen教授和McGraw-Hill出版社的授权，感谢机械工业出版社的努力，使更多的中国学生可以使用这本优秀教材。感谢同行和读者提出的宝贵建议。本科教学版力求保持原书的特点并符合本科离散数学教学大纲的要求，但难免存在不足之处，可能会给读者阅读造成一定影响，欢迎广大师生和读者提出宝贵意见。
陈琼2016年11月于华南理工大学译者序Discrete Mathematics and Its Applications,7E离散数学一直被IEEE & ACM确定为计算机专业最核心的课程（最新版CC2005），也是《中国计算机科学与技术学科教程2002》中界定的计算机科学与技术专业的核心基础课程。当你学习离散数学时，你会发现离散数学为许多计算机专业课程提供理论基础，尤其是为大多数计算机算法提供基础。
本书清晰地介绍了离散数学中的概念和技术，并向读者展示其相关性和实用性，给计算机科学专业的学生将来的学习提供一切必需的数学基础。
本书的优秀之处不仅在于作者对离散数学知识点精心编排，而且其行文流畅、通俗易懂，拥有大量有趣而实用的例子，推荐读物吸引读者广泛的好奇心，丰富的练习帮助读者掌握离散数学的概念和技巧。本书最大的优势在于它的配套网站中给出了一系列丰富的课外资源，既可以辅助教师根据实际情况安排教学活动，又能够帮助学生评估自身学习状况，学习撰写证明并避免常见错误，从各个方面提高学生学习和解决问题的能力，引领学生探索离散数学的新应用。
本书译自Kenneth H. Rosen所著的《Discrete Mathematics and Its Applications, Seventh Edition》。这本书在北美及全球有600多所大学采用，在中国也已经被多所大学采纳作为计算机系的离散数学教材。作者一直根据广大教师和学生的反馈意见不断完善这本书，使其能适应计算机科学及应用的发展。自出版以来这本书在北美发行超过350 000册，同时这本书也已经被翻译成法文、希腊文、中文、越南文和韩文等。因此，本书是一本不俗的教科书。
如果你有幸读到本书，那恭喜你了。你可以参考作者的建议或按自己的兴趣阅读本书，我相信你一定能从本书中获益匪浅。
本书第7版做了重大修订，翻译工作是在第6版译稿的基础上进行的。感谢第6版的译者袁崇义、屈婉玲、张桂芸。第7版翻译分工如下：作者简介、前言、配套网站、致学生，以及第1章和第2章（含练习答案）、推荐读物由徐六通（本书英文原版第7版正式评阅人之一）翻译，第3章和第4章（含练习答案）由吴斌翻译，第5章至第8章（含练习答案）由杨娟翻译。由于译者水平所限，本书难免有不妥的地方，敬请读者不吝赐教。
译者2014年10月于北京
文摘
版权页：
插图：
《计算机科学丛书:离散数学及其应用(原书第7版)(本科教学版)》由机械工业出版社出版。
作者简介
关于作者Discrete Mathematics and Its Applications,7EKenneth H.Rosen 作为位于新泽西州蒙茅斯县的AT＆T实验室杰出技术会员已经拥有一段很长的职业生涯。目前他在蒙茅斯大学任访问研究教授，为研究生讲授计算机科学课程。
Rosen博士于1972年获得位于安娜堡的密歇根大学数学学士学位，1976年获得麻省理工学院数学博士学位，在哈罗德·斯塔克（Harold Stark）的指导下他撰写了数论方面的博士论文。1982年加入贝尔实验室之前，他曾就职于科罗拉多大学博尔德分校；哥伦布市的俄亥俄州立大学；在欧洛诺市的缅因大学任数学副教授。在AT&T工作时，他在蒙茅斯大学任教，教授离散数学、编码理论和数据安全方面的课程。他目前教授算法设计以及计算机安全和密码学方面的课程。
Rosen博士在数论及数学建模的专业期刊上发表了大量论文。他是《初等数论及其应用》（Elementary Number Theory and Its Applications）的作者，该书由Pearson(培生)出版并广为采用，目前第6版也已经翻译成了中文。他也是《离散数学及其应用》(Discrete Mathematics and Its Applications)的作者，该书由McGraw-Hill(麦格劳希尔)出版，目前是第7版。《离散数学及其应用》(Discrete Mathematics and Its Applications)自出版以来在北美发行超过350 000册，在世界其余各地发行成千上万册。这本书也已经被翻译成法文、希腊文、中文、越南文和韩文。他还是《UNIX：参考大全》(UNIX:The Complete Reference)、《UNIX系统V版本4：简介》(UNIX System V Release4:An Introduction)、《佳UNIX小技巧》(Best UNIX Tips Ever)的合著者，这些书均由奥斯本/麦格劳希尔出版。这些书发行超过150 000册，并翻译成中文、德文、西班牙文和意大利文。Rosen博士还是由CRC出版社出版的《离散及组合数学手册》(Handbook of Discrete and Combinatorial Mathematics)的编辑，他是CRC离散数学丛书的顾问编辑，丛书包括超过55卷论述离散数学的不同方面，其中大多数内容在这本手册中有介绍。Rosen博士现任《离散数学》（Discrete Mathematics）期刊副主编，负责审阅提交的论文，涉及离散数多个领域，包括图论、枚举和数论。他对将数学软件集成到教育和专业环境中很有兴趣，并在这些方面参与和Waterloo Maple Inc.的MapleTM软件的一些合作项目。Rosen博士还和多家出版公司合作开发作业交付平台。
在贝尔实验室和AT&T实验室期间，Rosen博士所从事的项目涉猎广泛，包括运筹学研究、计算机和通信设备的产品线规划和技术评估。他帮助规划AT&T在多媒体领域的产品和服务，包括视频会议、语音识别、语音合成和图像联网。他为AT&T使用新技术做评估，并在图像联网领域从事标准化工作。他还发明了许多新服务，并持有超过55项专利。他的一个有趣的项目涉及帮助评估AT&T为提高吸引力而采用的技术，这也是EPCOT中心的一部分。
目录
出版者的话
改编者序
译者序
前言
配套网站
致学生
关于作者
符号表
第1章基础：逻辑和证明1
1.1命题逻辑1
1.1.1引言1
1.1.2命题1
1.1.3条件语句4
1.1.4复合命题的真值表7
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命题等价式16
1.3.1引言16
1.3.2逻辑等价式17
1.3.3德·摩根律的运用19
1.3.4构造新的逻辑等价式19
1.3.5命题的可满足性20
1.3.6可满足性的应用20
1.3.7可满足性问题求解22
练习22
1.4谓词和量词24
1.4.1引言24
1.4.2谓词24
1.4.3量词25
1.4.4约束论域的量词28
1.4.5量词的优先级29
1.4.6变量绑定29
1.4.7涉及量词的逻辑等价式29
1.4.8量化表达式的否定30
1.4.9语句到逻辑表达式的翻译31
1.4.10系统规范说明中量词的使用32
1.4.11选自路易斯·卡罗尔的例子33
1.4.12逻辑程序设计33
练习34
1.5嵌套量词37
1.5.1引言37
1.5.2理解涉及嵌套量词的语句37
1.5.3量词的顺序38
1.5.4数学语句到嵌套量词语句的翻译39
1.5.5嵌套量词到自然语言的翻译40
1.5.6汉语语句到逻辑表达式的翻译40
1.5.7嵌套量词的否定41
练习42
1.6推理规则45
1.6.1引言45
1.6.2命题逻辑的有效论证45
1.6.3命题逻辑的推理规则46
1.6.4使用推理规则建立论证48
1.6.5消解律49
1.6.6谬误49
1.6.7量化命题的推理规则50
1.6.8命题和量化命题推理规则的组合使用51
练习52
1.7证明导论53
1.7.1引言53
1.7.2一些专用术语53
1.7.3理解定理是如何陈述的54
1.7.4证明定理的方法54
1.7.5直接证明法54
1.7.6反证法55
1.7.7归谬证明法57
1.7.8证明中的错误59
1.7.9良好的开端60
练习60
1.8证明的方法和策略61
1.8.1引言61
1.8.2穷举证明法和分情形证明法61
1.8.3存在性证明65
……
1.8.5证明策略66
1.8.6寻找反例68
1.8.7证明策略实践68
1.8.8拼接68
1.8.9开放问题的作用71
1.8.10其他证明方法71
练习72
关键术语和结论73
复习题75
补充练习75
计算机课题78
计算和探索78
写作课题78
第2章基本结构：集合、函数、序列、求和与矩阵79
2.1集合79
2.1.1引言79
2.1.2文氏图81
2.1.3子集81
2.1.4集合的大小82
2.1.5幂集83
2.1.6笛卡儿积83
2.1.7使用带量词的集合符号84
2.1.8真值集和量词84
练习85
2.2集合运算86
2.2.1引言86
2.2.2集合恒等式88
2.2.3扩展的并集和交集90
2.2.4集合的计算机表示91
练习92
2.3函数94
2.3.1引言94
2.3.2一对一函数和映上函数96
2.3.3反函数和函数组合98
2.3.4函数的图100
2.3.5一些重要的函数101
2.3.6部分函数103
练习103
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可数集116
2.5.3不可数集合118
练习120
2.6矩阵121
2.6.1引言121
2.6.2矩阵算术122
2.6.3矩阵的转置和幂123
2.6.40—1矩阵124
练习125
关键术语和结论126
复习题128
补充练习129
计算机课题131
计算和探索131
写作课题131
第3章计数132
3.1计数的基础132
3.1.1引言132
3.1.2基本的计数原则132
3.1.3比较复杂的计数问题136
3.1.4减法法则（两个集合的容斥原理）137
3.1.5除法法则138
3.1.6树图138
练习139
3.2鸽巢原理141
3.2.1引言141
3.2.2广义鸽巢原理142
3.2.3鸽巢原理的几个简单应用144
练习145
3.3排列与组合146
3.3.1引言146
3.3.2排列146
3.3.3组合148
练习150
3.4二项式系数和恒等式151
3.4.1二项式定理151
3.4.2帕斯卡恒等式和三角形153
3.4.3其他的二项式系数恒等式154
练习155
3.5排列与组合的推广157
3.5.1引言157
3.5.2有重复的排列157
3.5.3有重复的组合157
3.5.4具有不可区别物体的集合的排列160
3.5.5把物体放入盒子161
练习163
3.6生成排列和组合165
3.6.1引言165
3.6.2生成排列165
3.6.3生成组合166
练习167
关键术语和结论168
复习题169
补充练习170
计算机课题173
计算和探索173
写作课题174
第4章高级计数技术175
4.1递推关系的应用175
4.1.1引言175
4.1.2用递推关系构造模型176
4.1.3算法与递推关系180
练习181
4.2求解线性递推关系184
4.2.1引言184
4.2.2求解常系数线性齐次递推关系184
4.2.3常系数线性非齐次的递推关系188
练习190
4.3分治算法和递推关系191
4.3.1引言191
4.3.2分治递推关系192
练习197
4.4生成函数198
4.4.1引言198
4.4.2关于幂级数的有用事实198
4.4.3计数问题与生成函数201
4.4.4使用生成函数求解递推关系204
4.4.5使用生成函数证明恒等式205
练习206
4.5容斥208
4.5.1引言208
4.5.2容斥原理208
练习211
4.6容斥原理的应用212
4.6.1引言212
4.6.2容斥原理的另一种形式212
4.6.3埃拉托色尼筛213
4.6.4映上函数的个数213
4.6.5错位排列214
练习216
关键术语和结论216
复习题217
补充练习218
计算机课题221
计算和探索221
写作课题221
第5章关系223
5.1关系及其性质223
5.1.1引言223
5.1.2函数作为关系224
5.1.3集合的关系224
5.1.4关系的性质225
5.1.5关系的组合227
练习228
5.2n元关系及其应用230
5.2.1引言230
5.2.2n元关系231
5.2.3数据库和关系231
5.2.4n元关系的运算232
5.2.5SQL234
练习235
5.3关系的表示236
5.3.1引言236
5.3.2用矩阵表示关系236
5.3.3用图表示关系238
练习239
5.4关系的闭包240
5.4.1引言240
5.4.2闭包241
5.4.3有向图中的路径241
5.4.4传递闭包242
5.4.5沃舍尔算法245
练习247
5.5等价关系247
5.5.1引言247
5.5.2等价关系248
5.5.3等价类249
5.5.4等价类与划分250
练习253
5.6偏序255
5.6.1引言255
5.6.2字典顺序256
5.6.3哈塞图257
5.6.4极大元与极小元259
5.6.5格260
5.6.6拓扑排序261
练习263
关键术语和结论265
复习题267
补充练习268
计算机课题271
计算和探索272
写作课题272
第6章图273
6.1图和图模型273
6.1.1图模型276
练习279
6.2图的术语和几种特殊的图281
6.2.1引言281
6.2.2基本术语281
6.2.3一些特殊的简单图283
6.2.4二分图284
6.2.5二分图和匹配286
6.2.6特殊类型图的一些应用288
6.2.7从旧图构造新图289
练习291
6.3图的表示和图的同构293
6.3.1引言293
6.3.2图的表示293
6.3.3邻接矩阵293
6.3.4关联矩阵295
6.3.5图的同构296
6.3.6判定两个简单图是否同构296
练习298
6.4连通性301
6.4.1引言301
6.4.2通路301
6.4.3无向图的连通性303
6.4.4图是如何连通的304
6.4.5有向图的连通性306
6.4.6通路与同构307
6.4.7计算顶点之间的通路数308
练习308
6.5欧拉通路与哈密顿通路311
6.5.1引言311
6.5.2欧拉通路与欧拉回路311
6.5.3哈密顿通路与哈密顿回路315
6.5.4哈密顿回路的应用316
练习318
6.6最短通路问题320
6.6.1引言320
6.6.2最短通路算法322
6.6.3旅行商问题325
练习326
6.7平面图328
6.7.1引言328
6.7.2欧拉公式329
6.7.3库拉图斯基定理332
练习333
6.8图着色334
6.8.1引言334
6.8.2图着色的应用337
练习338
关键术语和结论340
复习题343
补充练习344
计算机课题348
计算和探索349
写作课题349
第7章树351
7.1树的概述351
7.1.1有根树352
7.1.2树作为模型355
7.1.3树的性质356
练习358
7.2树的应用360
7.2.1引言360
7.2.2二叉搜索树360
7.2.3决策树362
7.2.4前缀码364
7.2.5博弈树365
练习369
7.3树的遍历371
7.3.1引言371
7.3.2通用地址系统371
7.3.3遍历算法372
7.3.4中缀、前缀和后缀记法377
练习379
7.4生成树380
7.4.1引言380
7.4.2深度优先搜索382
7.4.3宽度优先搜索384
7.4.4回溯的应用385
7.4.5有向图中的深度优先搜索387
练习388
7.5最小生成树390
7.5.1引言390
练习
关键术语和结论
复习题
补充练习
计算机课题
计算和探索
写作课题
第8章布尔代数
8.1布尔函数
8.1.1引言
8.1.2布尔表达式和布尔函数
8.1.3布尔代数恒等式
8.1.4对偶性
8.1.5布尔代数的抽象定义
练习
8.2布尔函数的表示
8.2.1积之和展开式
8.2.2函数完备性
练习
8.3逻辑门电路
8.3.1引言
8.3.2门的组合
8.3.3电路的例子
8.3.4加法器
练习
8.4电路的极小化
8.4.1引言
8.4.2卡诺图
8.4.3无须在意的条件
8.4.4奎因—莫可拉斯基方法
练习
关键术语和结论
复习题
补充练习
计算机课题
计算和探索
写作课题
推荐读物
参考文献
练习答案
序言
改编者序Discrete Mathematics and Its Applications,7EKenneth H.Rosen编著的《离散数学及其应用》一书包括计算机专业学生必须掌握的数学基础知识，并且给出许多应用离散数学解决现实问题的实例，一些知识点给出相关的历史背景知识，配有大量计算、研究和实践的题目及推荐参考读物。该书内容全面，由浅入深，通俗易懂，被全球很多大学使用，是一本非常优秀的教材。
近年来，国内的许多高校都采用国外的优秀原版书作为教材。而《离散数学及其应用》原版书篇幅较长，使得部分中国学生难以阅读。为了将这本优秀教材介绍给更多的中国学生，在保留原作者写作风格的前提下，我们删减了部分章节内容编成此本科教学版，以适合中国学生的使用和阅读。
原书中的一些内容，如第3、4、5、7、13章（算法、数论和密码学、归纳与递归、离散概率、计算模型），在其他课程中已有讲授或单独作为一门课程讲授，我们在本科教学版中将这些内容删除，保留了逻辑和证明、集合、函数、计数和高级计数技术、关系、图、树和布尔代数等内容。
原书有0多道各种类型的练习题，其中包括帮助学生掌握基本概念的练习、提高应用离散数学知识解决问题的计算机课题及计算和探索题目，以及需要查阅课外资料扩展学习的写作课题。题目按难易程度分级，分为简单、难度适中和难度较大各种类型。为了保持原书的特点，对于保留的章节，我们删去了每节后的偶数练习题，这样可以使得原书的各种类型、不同难度的习题都得以保留。关于一些知识点的相关历史背景知识未作保留，目的是减少本书的篇幅。
感谢原书作者Kenneth H.Rosen教授和McGraw-Hill出版社的授权，感谢机械工业出版社的努力，使更多的中国学生可以使用这本优秀教材。感谢同行和读者提出的宝贵建议。本科教学版力求保持原书的特点并符合本科离散数学教学大纲的要求，但难免存在不足之处，可能会给读者阅读造成一定影响，欢迎广大师生和读者提出宝贵意见。
陈琼2016年11月于华南理工大学译者序Discrete Mathematics and Its Applications,7E离散数学一直被IEEE & ACM确定为计算机专业最核心的课程（最新版CC2005），也是《中国计算机科学与技术学科教程2002》中界定的计算机科学与技术专业的核心基础课程。当你学习离散数学时，你会发现离散数学为许多计算机专业课程提供理论基础，尤其是为大多数计算机算法提供基础。
本书清晰地介绍了离散数学中的概念和技术，并向读者展示其相关性和实用性，给计算机科学专业的学生将来的学习提供一切必需的数学基础。
本书的优秀之处不仅在于作者对离散数学知识点精心编排，而且其行文流畅、通俗易懂，拥有大量有趣而实用的例子，推荐读物吸引读者广泛的好奇心，丰富的练习帮助读者掌握离散数学的概念和技巧。本书最大的优势在于它的配套网站中给出了一系列丰富的课外资源，既可以辅助教师根据实际情况安排教学活动，又能够帮助学生评估自身学习状况，学习撰写证明并避免常见错误，从各个方面提高学生学习和解决问题的能力，引领学生探索离散数学的新应用。
本书译自Kenneth H. Rosen所著的《Discrete Mathematics and Its Applications, Seventh Edition》。这本书在北美及全球有600多所大学采用，在中国也已经被多所大学采纳作为计算机系的离散数学教材。作者一直根据广大教师和学生的反馈意见不断完善这本书，使其能适应计算机科学及应用的发展。自出版以来这本书在北美发行超过350 000册，同时这本书也已经被翻译成法文、希腊文、中文、越南文和韩文等。因此，本书是一本不俗的教科书。
如果你有幸读到本书，那恭喜你了。你可以参考作者的建议或按自己的兴趣阅读本书，我相信你一定能从本书中获益匪浅。
本书第7版做了重大修订，翻译工作是在第6版译稿的基础上进行的。感谢第6版的译者袁崇义、屈婉玲、张桂芸。第7版翻译分工如下：作者简介、前言、配套网站、致学生，以及第1章和第2章（含练习答案）、推荐读物由徐六通（本书英文原版第7版正式评阅人之一）翻译，第3章和第4章（含练习答案）由吴斌翻译，第5章至第8章（含练习答案）由杨娟翻译。由于译者水平所限，本书难免有不妥的地方，敬请读者不吝赐教。
译者2014年10月于北京
文摘
版权页：
插图：
| ISBN | 9787111555391 |
|---|---|
| 出版社 | 机械工业出版社 |
| 作者 | 肯尼思 H.罗森 (Kenneth H.Rosen) |
| 尺寸 | 16 |