第1章基础知识 1
1.1集合与子集 1
1.1.1集合的概念和表示 1
目 录 1
1.1.2集合之间的关系 2
1.1.3集合的运算 3
1.1.4集合运算的代数性质 5
练习1.1 6
1.2 序列 7
1.2.1 序列 7
1.2.2 特征函数 8
1.2.3串和正则表达式 10
练习1.2 13
1.3.1 素数 14
1.3整数的除法 14
1.3.2最大公约数 15
1.3.3最小公倍数 17
练习1.3 18
1.4 矩阵 18
1.4.1矩阵和运算 18
1.4.2布尔矩阵的运算 21
练习1.4 23
1.5数学结构 24
练习1.5 28
要点回顾1 30
自测题1 31
2.1.1 命题 33
2.1.2逻辑联结词与复合命题 33
2.1命题和逻辑运算 33
第2章逻辑 33
2.1.3谓词和量词 35
练习2.1 37
2.2条件命题 38
2.2.1蕴涵联结词和等价联结词 38
2.2.2三类命题 40
2.2.3命题运算的性质 41
2.2.4逻辑的应用 43
练习2.2 44
2.3证明方法 46
2.3.1直接证明法 46
2.3.2间接证明法 48
2.3.3反证法 48
练习2.3 49
2.3.4证明过程 49
2.4数学归纳法 50
2.4.1数学归纳法 50
2.4.2强归纳法 53
练习2.4 53
要点回顾2 56
自测题2 57
第3章计数 58
3.1叠加原理 58
练习3.1 59
3.2排列 59
练习3.2 62
3.3组合 62
练习3.3 65
3.4鸽巢原理 65
练习3.4 66
3.5.1样本空间 67
3.5概率基础 67
3.5.2事件 68
3.5.3给事件赋概率 68
3.5.4等可能结果 70
练习3.5 71
3.6递归关系 73
练习3.6 76
要点回顾3 76
自测题3 77
第4章关系 79
4.1乘积集合 79
练习4.1 80
4.2关系和有向图 81
4.2.1 关系 81
4.2.2 由关系得到的集合 82
4.2.3关系的矩阵 84
4.2.4关系的有向图 84
练习4.2 86
4.3关系和有向图中的路径 87
练习4.3 90
4.4关系的性质 91
4.4.1 自反的关系和反自反的关系 91
4.4.2对称的、不对称的、反对称的关系 92
4.4.3传递关系 95
练习4.4 95
4.5等价关系 97
4.5.1等价关系 97
4.5.2等价关系和划分 98
练习4.5 99
4.6关系的计算机表示 100
4.6.1线性表的表示 101
4.6.2关系的表示 102
4.6.3关系的矩阵表示方法的计算量 103
4.6.4关系的链表表示方法的计算量 104
4.6.5检查传递性的计算量对比 105
练习4.6 105
4.7关系的运算 107
4.7.1关系的运算 107
4.7.2关系的运算的性质 108
4.7.3合成 110
练习4.7 112
4.8闭包 115
4.8.1闭包 115
4.8.2传递闭包的WARSHALL算法 117
练习4.8 120
要点回顾4 121
自测题4 123
第5章 函数 124
5.1 函数 124
5.1.1 函数定义 124
5.1.2特殊的函数 125
5.1.3 反函数 126
练习5.1 128
5.2计算机科学中的函数 130
练习5.2 132
5.3函数的增长 133
练习5.3 135
5.4排列函数 137
5.4.1排列和循环 137
5.4.2奇排列和偶排列 139
练习5.4 141
自测题5 143
要点回顾5 143
第6章序关系和结构 145
6.1偏序集合 145
6.1.1偏序集合 145
6.1.2哈斯图 147
6.1.3拓扑排序 149
6.1.4 同构 149
练习6.1 150
6.2偏序集合的极值元素 153
练习6.2 156
6.3 格 158
6.3.1 格 158
6.3.2 同构格 160
6.3.3格的性质 161
6.3.4特殊的格 162
练习6.3 164
6.4有限布尔代数 166
6.4.1一类特殊的格 166
6.4.2布尔代数 168
6.4.3布尔代数的性质 169
练习6.4 171
6.5布尔代数上的函数 172
练习6.5 175
6.6电路设计 176
练习6.6 182
要点回顾6 183
自测题6 185
第7章树 187
7.1树 187
练习7.1 189
7.2.1标记树 190
7.2标记树 190
7.2.2定位二元树的计算机表示 191
练习7.2 193
7.3树搜索 193
7.3.1搜索二元树 194
7.3.2搜索一般的树 197
练习7.3 198
7.4无向树 200
7.4.1无向树 200
7.4.2连通关系的生成树 201
练习7.4 205
7.5最小生成树 206
练习7.5 209
要点回顾7 210
自测题7 211
8.1.1图 213
第8章图论 213
8.1图 213
8.1.2子图和商图 215
练习8.1 216
8.2欧拉路径及回路 218
练习8.2 220
8.3哈密尔顿路径及回路 221
练习8.3 222
8.4运输网 223
8.4.1运输网 223
8.4.2流 224
8.4.3 最大流 224
8.4.4最大流算法 225
8.4.5扩展的运输网 230
8.4.6匹配问题 231
练习8.4 233
8.5 图着色 235
8.5.1 图着色 235
8.5.2颜色多项式 236
练习8.5 237
要点回顾8 238
自测题8 239
第9章半群和群 241
9.1二元运算回顾 241
9.1.1二元运算 241
9.1.2二元运算的表格 242
9.1.3二元运算的性质 243
练习9.1 244
9.2.1半群 246
9.2半群 246
9.2.2子半群 247
9.2.3同构映射和同态 247
练习9.2 250
9.3半群的积和商 252
练习9.3 255
9.4群 257
练习9.4 263
9.5群的积和商 265
练习9.5 267
要点回顾9 268
自测题9 269
10.1.1语言 271
10.1.2语法 271
10.1语言 271
第10章语言和有限状态机 271
练习10.1 275
10.2语法和语言的表示 276
10.2.1 BNF符号 276
10.2.2 句法图 278
10.2.3正则语法和正则表达式 281
练习10.2 282
10.3有限状态机 284
10.3.1有限状态机 284
10.3.2摩尔机器 285
10.3.3机器一致和商机器 286
练习10.3 288
10.4半群、机器和语言 291
练习10.4 294
10.5机器和正则语言 296
练习10.5 300
10.6机器简化 301
练习10.6 304
要点回顾10 306
自测题10 307
第11章群和编码 309
11.1二进制编码和错误检测 309
11.1.1编码函数 309
11.1.2群码 312
练习11.1 314
11.2解码和纠错 316
练习11.2 321
要点回顾11 323
自测题11 324
附录A符号表 325
附录B术语表 329