第1章 数理逻辑与推理基础 1
1.1 命题逻辑 1
1.1.1 命题及其表示法 1
1.1.2 逻辑联结词 2
1.1.3 命题公式 3
1.1.4 命题等价定律 5
1.1.5 命题公式的范式 9
1.1.6 蕴涵关系 16
1.1.7 推理 17
1.2 谓词逻辑 24
1.2.1 谓词的概念与谓词公式 24
1.2.2 谓词逻辑公式 27
1.2.3 量词等价定律 29
1.2.4 谓词公式的范式 31
1.2.5 谓词逻辑的推理 33
1.3 归纳方法 41
1.3.1 数学归纳法的形式 41
1.3.2 数学归纳法的应用 42
第2章 集合与函数 47
2.1 集合的概念 47
2.2 集合的运算 50
2.3 笛卡儿积 56
2.4 函数 58
2.5 容斥原理 60
2.6 无限集的基数比较 63
2.7 与整数有关的函数及其应用 67
2.7.1 从R到Z的常用函数 67
2.7.2 从Z×Z到Z的常用函数 68
2.7.3 余数函数 68
2.7.4 模与余数的应用 69
2.7.5 整数的进制表示 73
第3章 二元关系 76
3.1 二元关系的概念 76
3.2 二元关系的运算 77
3.3 二元关系的性质 82
3.4 等价关系 90
3.4.1 等价关系的概念 90
3.4.2 等价关系的运算 92
3.4.3 等价关系的运算与划分的关系 93
3.5 半序关系 95
3.6 字典顺序和拓扑排序 101
3.6.1 字典顺序 101
3.6.2 拓扑排序 102
3.7 格与布尔代数 104
第4章 图论基础 108
4.1 图的概念 108
4.1.1 图的术语 108
4.1.2 图的模型 112
4.2 道路与图的连通性 113
4.3 图的矩阵表示 115
4.4 加权图中的最短道路问题 123
4.5 欧拉道路与哈密顿道路 129
4.5.1 欧拉道路与欧拉回路 129
4.5.2 欧拉定理的应用 131
4.5.3 哈密顿道路与哈密顿回路 133
4.5.4 哈密顿道路的应用 137
4.6 平面图 140
4.7 图的着色 143
4.8 树 148
4.8.1 无向树 148
4.8.2 有根树 150
4.8.3 二元树及其应用 153
4.8.4 生成树 159
4.8.5 最小生成树 162
第5章 组合数学基础 170
5.1 鸽巢原理 170
5.2 计数与球盒模型 175
5.2.1 基本计数原理 175
5.2.2 典型计数问题 178
5.2.3 环形排列的CP数 184
5.3 递推关系 191
5.4 生成函数 198
5.4.1 生成函数的概念 198
5.4.2 用生成函数解递推关系 205
5.4.3 生成函数与计数 208
5.5 排列与组合的生成算法 213
第6章 代数系统 220
6.1 代数系统基础 220
6.1.1 二元运算与代数系统 220
6.1.2 二元运算的性质 222
6.1.3 代数系统的零元、单位元和逆元 223
6.2 群 226
6.3 陪集及其应用 230
6.3.1 陪集与拉格朗日定理 230
6.3.2 群码 232
6.4 同构与同态 234
6.5 环与域 241
6.5.1 环与域的概念 241
6.5.2 多项式环与循环码 245
附录A 自然数集与数学归纳法原理 249
附录B 级数公式 253
参考文献 254
参考答案 255