计算机科学丛书 离散数学及其应用 原书第8版
作者：美肯尼思H.罗森KennethH.Rosen美戴维A.帕特森
出版时间：2019年版
丛编项： 计算机科学丛书
内容简介
本书是经典的离散数学教材，被全球数百所大学广为采用。书中全面而系统地介绍了离散数学的理论和方法，主要包括：逻辑和证明，集合、函数、序列、求和与矩阵，算法，数论和密码学，归纳与递归，计数，离散概率，关系，图，树，布尔代数，计算模型。全书取材广泛，除包括定义、定理的严格陈述外，还配备大量的例题、图表、应用实例和练习。第8版做了与时俱进的更新，成为更加实用的教学工具。本书可作为高等院校数学、计算机科学和计算机工程等专业的教材，也可作为科技领域从业人员的参考书。
目录
出版者的话
译者序
前言
在线资源
致学生
作者简介
符号表
第1章 基础：逻辑和证明1
1.1 命题逻辑1
1.1.1 引言1
1.1.2 命题1
1.1.3 条件语句4
1.1.4 复合命题的真值表7
1.1.5 逻辑运算符的优先级8
1.1.6 逻辑运算和比特运算8
练习9
1.2 命题逻辑的应用15
1.2.1 引言15
1.2.2 语句翻译15
1.2.3 系统规范说明16
1.2.4 布尔搜索16
1.2.5 逻辑谜题17
1.2.6 逻辑电路18
练习20
1.3 命题等价式23
1.3.1 引言23
1.3.2 逻辑等价式23
1.3.3 德·摩根律的运用25
1.3.4 构造新的逻辑等价式26
1.3.5 可满足性28
1.3.6 可满足性的应用28
1.3.7 可满足性问题求解30
练习31
1.4 谓词和量词34
1.4.1 引言34
1.4.2 谓词34
1.4.3 量词37
1.4.4 有限域上的量词39
1.4.5 受限域的量词39
1.4.6 量词的优先级40
1.4.7 变量绑定40
1.4.8 涉及量词的逻辑等价式40
1.4.9 量化表达式的否定41
1.4.10 语句到逻辑表达式的翻译42
1.4.11 系统规范说明中量词的使用43
1.4.12 选自路易斯·卡罗尔的例子44
1.4.13 逻辑程序设计45
练习46
1.5 嵌套量词51
1.5.1 引言51
1.5.2 理解涉及嵌套量词的语句51
1.5.3 量词的顺序52
1.5.4 数学语句到嵌套量词语句的翻译53
1.5.5 嵌套量词到自然语言的翻译54
1.5.6 汉语语句到逻辑表达式的翻译54
1.5.7 嵌套量词的否定55
练习56
1.6 推理规则62
1.6.1 引言62
1.6.2 命题逻辑的有效论证62
1.6.3 命题逻辑的推理规则63
1.6.4 使用推理规则建立论证65
1.6.5 消解律66
1.6.6 谬误66
1.6.7 量化命题的推理规则67
1.6.8 命题和量化命题推理规则的组合使用68
练习69
1.7 证明导论72
1.7.1 引言72
1.7.2 一些专用术语72
1.7.3 理解定理是如何陈述的73
1.7.4 证明定理的方法73
1.7.5 直接证明法73
1.7.6 反证法74
1.7.7 归谬证明法76
1.7.8 证明中的错误78
1.7.9 良好的开端79
练习80
1.8 证明的方法和策略81
1.8.1 引言81
1.8.2 穷举证明法和分情形证明法81
1.8.3 存在性证明84
1.8.4 唯一性证明86
1.8.5 证明策略87
1.8.6 寻找反例89
1.8.7 证明策略实践90
1.8.8 拼接90
1.8.9 开放问题的作用92
1.8.10 其他证明方法93
练习94
关键术语和结论96
复习题97
补充练习98
计算机课题100
计算和探索101
写作课题101
第2章 基本结构：集合、函数、序列、求和与矩阵102
2.1 集合102
2.1.1 引言102
2.1.2 文氏图104
2.1.3 子集105
2.1.4 集合的大小106
2.1.5 幂集107
2.1.6 笛卡儿积107
2.1.7 使用带量词的集合符号109
2.1.8 真值集和量词109
练习109
2.2 集合运算112
2.2.1 引言112
2.2.2 集合恒等式114
2.2.3 扩展的并集和交集116
2.2.4 集合的计算机表示117
2.2.5 多重集118
练习119
2.3 函数123
2.3.1 引言123
2.3.2 一对一函数和映上函数125
2.3.3 反函数和函数合成128
2.3.4 函数的图130
2.3.5 一些重要的函数130
2.3.6 部分函数133
练习133
2.4 序列与求和138
2.4.1 引言138
2.4.2 序列138
2.4.3 递推关系139
2.4.4 特殊的整数序列141
2.4.5 求和144
练习147
2.5 集合的基数150
2.5.1 引言150
2.5.2 可数集合151
2.5.3 不可数集合153
练习155
2.6 矩阵157
2.6.1 引言157
2.6.2 矩阵算术158
2.6.3 矩阵的转置和幂159
2.6.4 0-1矩阵160
练习161
关键术语和结论164
复习题166
补充练习166
计算机课题168
计算和探索169
写作课题169
第3章 算法170
3.1 算法170
3.1.1 引言170
3.1.2 搜索算法172
3.1.3 排序174
3.1.4 字符串匹配176
3.1.5 贪婪算法177
3.1.6 停机问题179
练习180
3.2 函数的增长183
3.2.1 引言183
3.2.2 大O记号184
3.2.3 一些重要函数的大O估算187
3.2.4 函数组合的增长190
3.2.5 大Ω与大Θ记号191
练习192
3.3 算法的复杂度196
3.3.1 引言196
3.3.2 时间复杂度196
3.3.3 矩阵乘法的复杂度198
3.3.4 算法范型199
3.3.5 理解算法的复杂度201
练习203
关键术语和结论207
复习题208
补充练习209
计算机课题211
计算和探索211
写作课题212
第4章 数论和密码学213
4.1 整除性和模算术213
4.1.1 引言213
4.1.2 除法213
