离散数学及其应用 原书第8版

本书是经典的离散数学教材，被全球数百所大学广为采用。书中全面而系统地介绍了离散数学的理论和方法，主要包括：逻辑和证明，集合、函数、序列、求和与矩阵，算法，数论和密码学，归纳与递归，计数，离散概率，关系，图，树，布尔代数，计算模型。全书取材广泛，除包括定义、定理的严格陈述外，还配备大量的例题、图表、应用实例和练习。第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.40-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
……