第0章 基础知识 1
0.1 集合及子集 1
0.1.1 集合及其表示 1
0.1.2 子集 2
0.1.3 幂集 3
0.2 集合上的运算 4
0.2.1 集合的并 4
0.2.2 集合的交 4
0.2.3 集合的差 5
0.2.4 集合的对称差 6
0.3 多重集合 9
0.4 序列 10
0.4.1 序列和数组 10
0.4.2 特征函数 12
0.4.3 集合及子集的计算机表示 13
0.4.4 串和正则表达式 14
0.5.1 整除及素数 16
0.5 整数的分解 16
0.5.2 最大公因数 17
0.5.3 最小公倍数 20
0.5.4 某些算法的伪代码 21
0.6 矩阵 22
0.6.1 矩阵的定义 22
0.6.2 矩阵的运算 23
0.6.3 布尔矩阵运算 26
0.7 算法和算法语言 28
0.7.1 算法简介 28
0.7.2 算法概念 29
0.7.3 算法语言 31
0.7.4 递归算法 34
0.8 数学结构 36
0.9 习题 39
本章小结 45
1.1.1 命题 46
1.1 命题和逻辑运算 46
第1章 逻辑 46
A 命题逻辑 46
1.1.2 逻辑联结词和复合命题 47
1.1.3 逻辑和位运算 51
1.2 合式公式和语义 51
1.2.1 语法 52
1.2.2 语义 52
1.3 逻辑等价 53
1.4 真值函数和范式 57
1.4.1 真值函数和合式公式 57
1.4.2 析取范式 59
1.4.3 合取范式 60
1.4.4 用等价替换方法构造主范式 61
1.5 联结词的完备集 63
1.5.1 联结词的完备集 63
1.5.2 一些计算机应用 64
1.6.1 形式推演规则 66
1.6 形式推理系统 66
1.6.2 形式可推演性的一些性质 69
1.6.3 形式推演实例 73
B 一阶逻辑 76
1.7 谓词和量词 76
1.7.1 谓词 76
1.7.2 量词 77
1.7.3 Lewis Carroll例 79
1.8 合式公式和语义 80
1.8.1 合式公式 80
1.8.2 语义 82
1.8.3 自然语言的形式化 83
1.9 逻辑等价和蕴涵 85
1.10 范式 90
1.11 一阶逻辑的形式推理系统 93
1.12.1 归纳推理和演绎推理 97
1.12 数学归纳法 97
1.12.2 数学归纳法 99
1.12.3 数学归纳法在证明不等式中的应用 102
1.12.4 数学归纳法在其它方面的应用 103
1.13 习题 106
本章小结 111
2.1 计数的两个基本原理 114
2.1.1 加法原理 114
第2章 计数 114
2.1.2 乘法原理 115
2.2 排列与组合 115
2.2.1 排列 115
2.2.2 组合 119
2.2.3 二项式定理 121
2.2.4 多项式定理 124
2.3 鸽笼原理 124
2.3.1 鸽笼原理的简单形式 125
2.3.2 鸽笼原理的一般形式 126
2.3.3 Ramsey数 128
2.4 容斥原理 130
2.4.1 引 130
2.4.2 容斥原理 131
2.4.3 容斥原理的应用 135
2.5 概率初步 140
2.5.1 引 140
2.5.2 样本空间 140
2.5.3 事件 141
2.5.4 对事件赋予概率 142
2.5.5 可望相等结果 143
2.6 递归关系 145
2.6.1 递归关系模型 146
2.6.2 递归关系的基本解法 151
2.7 习题 159
本章小结 164
3.1.2 集合的笛卡儿乘积 166
3.1.1 有序对 166
第3章 关系和有向图 166
3.1 集合的积 166
3.2 关系和有向图 168
3.2.1 二元关系的定义 168
3.2.2 关系矩阵 171
3.2.3 关系图 172
3.2.4 n元关系及其应用 173
3.3 复合关系和逆关系 175
3.3.1 复合关系 175
3.3.2 逆关系 178
3.4 关系图中的通路 179
3.5 关系的性质 183
3.6 等价关系和集合的划分 187
3.6.1 等价关系 187
3.6.2 集合的划分 190
3.6.3 有限集合上等价关系的计数 191
3.7.1 关系闭包的基本概念 193
3.7 关系的闭包 193
3.7.2 求传递闭包的Warshall算法 196
3.8 习题 200
本章小结 204
第4章 函数 206
4.1 函数的基本概念 206
4.1.1 函数 206
4.1.2 偏函数 208
4.2 特殊函数 209
4.3 函数的运算 213
4.4 基数 216
4.4.1 基数 216
4.4.2 可数集与不可数集 218
4.4.3 基数的比较 220
4.5 用于计算机科学的函数 221
4.5.1 一般函数 221
4.5.2 散列函数 223
4.6 函数的增长 224
4.6.1 大O 224
4.6.2 大Θ 225
4.6.3 确定函数Θ类的规则 226
4.7 置换 226
4.7.1 置换的基本概念 227
4.7.2 置换的表示 227
4.7.3 置换的积 227
4.7.4 循环 228
4.8 习题 231
本章小结 234
第5章 群、环和域 236
5.1 预备知识 236
5.1.1 一些基本运算 236
5.1.2 特殊元素 240
5.1.3 同态与同构 244
5.2.1 半群 246
5.2 半群和独异点 246
5.2.2 独异点 249
5.3 半群的积和商 251
5.3.1 半群的积 251
5.3.2 半群的商 251
5.4 群和子群 254
5.4.1 群 255
5.4.2 群同态和同构 258
5.4.3 子群 262
5.5 循环群 265
5.6 对称群和置换群 269
5.7 陪集和拉格朗日定理 272
5.8 群的积和商 276
5.9 环和域 279
5.10 习题 282
本章小结 288
6.1.1 偏序 291
第6章 偏序集 291
6.1 偏序集 291
6.1.2 哈斯图 294
6.1.3 序同构 296
6.2 偏序集的特殊元素 297
6.3 格 303
6.3.1 格和子格 303
6.3.2 格和偏序集 305
6.3.3 格同构 309
6.3.4 分配格 310
6.3.5 有界格 312
6.3.6 有补格 313
6.4 有限布尔代数 315
6.5 布尔函数 320
6.6 电路设计 322
6.7 习题 329
本章小结 335
7.1 图的基本概念 339
第7章 图论 339
7.1.1 图的定义、表示和一些术语 340
7.1.2 图的同构 341
7.1.3 关联矩阵和邻接矩阵 344
7.1.4 子图和商图 345
7.1.5 顶点的度 347
7.1.6 路和连通 350
7.1.7 回路 352
7.1.8 最短路问题 353
7.1.9 图模型 356
7.2 无向树 357
7.2.1 无向树的定义和基本性质 357
7.2.2 生成树和最小生成树 360
7.3 有向树及根树 364
7.3.1 有向树及根树的定义 364
7.3.2 有序树 366
7.3.3 树搜索 370
7.3.4 前缀码和最优树 375
7.4 图的连通度 379
7.4.1 割边和割集 379
7.4.2 割点 380
7.4.3 图的连通度 381
7.5 欧拉图和哈密尔顿图 383
7.5.1 欧拉图 383
7.5.2 中国邮递员问题 388
7.5.3 哈密尔顿图 389
7.5.4 葛莱码及巡回售货员问题 394
7.5.5 存储器轮 396
7.6 可平面性 397
7.6.1 平面图和可平面图 397
7.6.2 平面图的欧拉公式及其应用 399
7.6.3 可平面图的判定 400
7.6.4 可平面性与哈密尔顿图 402
7.6.5 平面图的对偶图 407
7.7 习题 409
本章小结 419
第8章 匹配、Menger定理及网络和流 422
8.1 图的匹配与匈牙利算法 422
8.1.1 匹配 422
8.1.2 二部图的匹配和覆盖 424
8.1.3 匈牙利算法 426
8.1.4 拉丁方、相异代表系及(0，1)矩阵 427
8.2 Menger定理 430
8.3 网络和流 433
8.3.1 网络中的流 433
8.3.2 网络的截 434
8.3.3 求最大流问题 436
8.3.4 最小费用最大流 439
8.3.5 网络表示及数据结构 442
8.4 互联网的拓扑结构 445
8.4.1 图和互联网 445
8.4.2 网络设计的基本原则 446
8.4.3 典型互联网的拓扑结构 447
8.4.4 网络的其它拓扑结构 455
8.5 习题 460
本章小结 463
第9章 语言和有限状态机 465
9.1 语言和文法 465
9.1.1 引 465
9.1.2 文法和语言 466
9.2 特殊文法和语言表示 470
9.2.1 BNF范式 470
9.2.2 句法图 472
9.2.3 正规文法和正则表达式 475
9.3 有限状态机 476
9.3.1 有限状态机及摩尔机 476
9.3.2 机器同余及商机器 478
9.4 半群、机器和语言 480
9.5 机器和正规语言 483
9.6 机器的简化 487
9.7 习题 491
本章小结 498
第10章 数、群和编码 500
10.1 同余类 500
10.2 解一次同余 505
10.2.1 解一次同余方程 505
10.2.2 解一次同余方程组、孙子定理 507
10.3.1 数字通信和检错的基本概念 508
10.3 二进制信息的编码和错误检测 508
10.3.2 群码 512
10.4 解码和错误纠正 517
10.4.1 解码和纠错的基本概念 517
10.4.2 与群码有关的最大似然解码函数 519
10.5 习题 523
本章小结 526
参考文献 529