第一篇 数理逻辑第1章 命题逻辑 3
1.1 命题与联结词 3
1.1.1 命题及其表示 3
1.1.2 联结词 4
1.2 命题公式与翻译 5
1.2.1 命题公式 5
1.2.2 命题的翻译 6
1.3 真值表与等价公式 7
1.3.1 真值表 7
1.3.2 公式分类 8
1.3.3 等价公式 9
1.3.4 代入规则和替换规则 10
1.4 对偶原理与蕴含式 11
1.4.1 对偶原理 11
1.4.2 蕴含式 12
1.5 联结词的扩充与功能完全组 14
1.5.1 其他联结词 14
1.5.2 联结词的功能完全组 16
1.6 范式 17
1.6.1 析取范式与合取范式 17
1.6.2 主析取范式与主合取范式 19
1.7 命题逻辑的推理理论 24
1.7.1 推理的基本概念 24
1.7.2 推理常用方法 25
习题一 28
第2章 谓词逻辑 33
2.1 谓词逻辑的基本概念 33
2.1.1 个体、谓词和命题的谓词形式 33
2.1.2 原子谓词 34
2.1.3 量词 34
2.2 谓词公式与翻译 35
2.2.1 谓词公式 35
2.2.2 谓词逻辑的翻译 36
2.3 变元的约束 37
2.4 谓词演算的等价式与蕴含式 39
2.5 谓词公式范式 43
2.5.1 前束范式 43
2.5.2 斯柯伦范式 43
2.6 谓词演算的推理理论 44
2.6.1 有关量词的规则 44
2.6.2 谓词逻辑推理实例 45
习题二 47
第二篇 集合论 53
第3章 集合与关系 53
3.1 集合的基本概念 53
3.2 集合的运算与性质 55
3.2.1 集合的运算 55
3.2.2 集合的运算与性质 57
3.3 序偶与笛卡尔积 58
3.3.1 序偶及序偶的推广 58
3.3.2 笛卡尔积 59
3.4 关系及其表示方法 61
3.4.1 关系 61
3.4.2 几种特殊的关系 62
3.4.3 关系的表示方法 62
3.5 关系的性质 63
3.5.1 关系的五种特殊性质 64
3.5.2 关系图、关系矩阵与关系的性质 64
3.6 关系的运算 65
3.6.1 关系的集合运算 65
3.6.2 复合关系 65
3.6.3 逆关系 68
3.6.4 闭包运算 70
3.7 集合的划分和覆盖 74
3.8 等价关系 76
3.8.1 等价关系的定义 76
3.8.2 等价类及其性质 76
3.8.3 等价关系与划分的一一对应 77
3.9 相容关系 79
3.10 偏序关系 81
3.10.1 偏序关系的定义 81
3.10.2 偏序关系的哈斯图 81
3.10.3 偏序集中特殊位置的元素 83
习题三 85
第4章 函数 87
4.1 函数的概念 87
4.1.1 函数的定义 87
4.1.2 函数的相等 88
4.1.3 特殊的函数 89
4.2 函数的运算 90
4.2.1 复合函数 90
4.2.2 逆函数 93
习题四 94
第三篇 代数系统第5章 代数系统 99
5.1 代数系统的基本概念 99
5.2 运算及其性质 100
5.3 同态与同构 105
5.4 同余关系 112
习题五 115
第6章 典型代数系统 118
6.1 半群与群 118
6.1.1 半群与独异点 118
6.1.2 群的定义与性质 123
6.1.3 阿贝尔群、置换群与循环群 125
6.1.4 子群、陪集与拉格朗日定理 131
6.1.5 群同态与群同构 136
6.2 环与域 139
6.2.1 环 139
6.2.2 域 143
6.3 格与布尔代数 144
6.3.1 格 144
6.3.2 布尔代数 152
习题六 159
第四篇 图论 165
第7章 图论基础 165
7.1 图的基本概念 165
7.2 路与回路 169
7.3 图的矩阵表示 174
习题七 185
第8章 几类典型的图 188
8.1 欧拉图与哈密尔顿图 188
8.1.1 欧拉图 188
8.1.2 哈密尔顿图 190
8.2 二部图和平面图 194
8.2.1 二部图 194
8.2.2 平面图 198
8.3 树 204
8.3.1 树与生成树 204
8.3.2 根树及其应用 210
习题八 215
第五篇 组合学 221
第9章 基本计数原理 221
9.1 排列与组合 221
9.1.1 加法原理与乘法原理 221
9.1.2 集合的排列和组合 222
9.1.3 重集的排列和组合 225
9.2 容斥原理 228
9.2.1 容斥原理 228
9.2.2 容斥原理的应用 230
9.3 鸽巢原理 233
9.4 二项式定理和二项式系数 235
9.4.1 二项式定理 235
9.4.2 Pascal三角形和组合等式 236
9.4.3 二项式系数的推广和Newton二项式定理 239
9.5 集合的分划与第二类Stirling数 240
9.6 正整数的分拆 242
9.7 分配问题 244
习题九 248
第10章 生成函数、递推关系与Pólya计数 251
10.1 生成函数 251
10.1.1 离散数值函数 251
10.1.2 生成函数及其性质 254
10.1.3 用生成函数法解组合问题 257
10.1.4 指数型生成函数 258
10.2 递推关系 262
10.2.1 两个递推关系的实例 262
10.2.2 递推关系和常系数线性递推关系 263
10.2.3 利用特征方程求解常系数线性递推关系 264
10.2.4 利用生成函数法求解常系数线性递推关系 268
10.3 Pólya计数 270
10.3.1 引论 270
10.3.2 计数问题的数学模型 274
10.3.3 Burnside引理 275
10.3.4 映射的等价类 281
10.3.5 Pólya计数定理 283
习题十 289
参考文献 295