前言 1
第1章 命题逻辑 1
1.1 基本概念 1
1.1.1 命题 1
目录 1
1.1.2 连接词 2
1.1.3 公式 3
1.1.4 重言式 5
1.2 公式的等价关系 6
1.2.1 等价 6
习题 6
1.2.2 等价代换 7
1.2.3 对偶性 8
习题 9
1.3 范式 10
1.3.1 范式 10
1.3.2 主析取范式 10
1.3.3 主合取范式 12
1.3.4 判定问题 13
习题 14
1.4 公式的蕴涵关系 14
1.4.1 蕴涵 14
1.4.2 论证 16
习题 18
1.5 连接词的完备集合 18
习题 21
1.6 半形式化推导方法 21
1.6.1 推理规则 21
1.6.2 推导举例 22
1.6.3 间接推导方法 22
习题 23
第2章 谓词逻辑 25
2.1 谓词与量词 25
2.2.1 公式 28
2.2 合式公式 28
习题 28
2.2.2 自由变元和约束变元 29
习题 29
2.3 谓词演算中的永真公式 29
2.3.1 基本概念 29
2.3.2 谓词演算的基本永真式 30
2.3.3 谓词演算的基本永真式表 31
2.3.4 前缀范式 32
习题 32
2.4 谓词演算中的半形式化推导 32
2.4.1 推理规则 32
2.4.3 间接推导方法 33
2.4.2 推导举例 33
习题 34
第3章 集合 35
3.1 集合的基本概念 35
3.1.1 集合与元素 35
3.1.2 集合间的关系 36
3.1.3 幂集 37
习题 38
3.2 集合的运算 39
3.2.1 集合的交与并 39
3.2.2 集合的差与补 41
3.2.3 集合的对称差 42
习题 43
3.3 n元组与笛卡儿乘积 44
4.3.1 合成关系的定义 44
习题 45
第4章 二元关系 47
4.1 二元关系的概念 47
4.1.1 基本定义 47
习题 50
4.2 二元关系的基本特性 50
习题 52
4.3 合成关系与逆关系 54
4.3.2 合成关系的矩阵表示及图形表示 57
4.3.3 逆关系 58
习题 59
4.4 关系的闭包运算 60
习题 62
4.5 等价关系与相容关系 63
4.5.1 集合的覆盖与划分 63
4.5.2 等价关系与等价类 65
4.5.3 相容关系 67
习题 70
4.6 次序关系 71
4.6.1 次序关系 71
4.6.2 偏序集与哈斯图 72
习题 76
第5章 映射 79
5.1 映射的概念 79
习题 81
5.2 映射的合成 81
习题 83
5.3 逆映射 84
习题 85
5.4 集合的特征函数 85
习题 87
5.5 基数 87
5.5.1 基数的概念 87
5.5.2 可数集与不可数集 89
习题 92
第6章 图的基本概念 93
6.1 基本定义 93
习题 96
6.2 子图和图的同构 97
习题 98
6.3 通路与回路 99
习题 102
6.4 最短路算法 103
6.4.1 Moore算法（BFS算法） 103
6.4.2 Dijkstra算法 103
习题 104
6.5 图的连通性 105
习题 108
6.6 图的矩阵表示 108
6.6.1 邻接矩阵 109
6.6.2 可达性矩阵 111
6.6.3 无向图、多重图、带权图的矩阵表示法 112
习题 112
第7章 树 115
7.1 无向树 115
习题 117
7.2 根树 118
7.3 带权树 121
习题 121
习题 124
7.4 生成树 124
习题 125
7.5 最小生成树算法 126
7.5.1 Prim算法 126
7.5.2 Kruskal算法 127
习题 129
第8章 特殊图 131
8.1 欧拉图 131
习题 134
8.2 哈密顿图 135
习题 138
8.3 中国邮路问题与旅行推销员问题 139
8.3.1 中国邮路问题 139
8.3.2 旅行推销员问题 140
习题 141
8.4 平面图 142
8.4.1 平面图 142
8.4.2 欧拉公式 143
8.4.3 图的可平面性 145
8.4.4 平面图的对偶图 146
8.4.5 可着色性 148
习题 151
8.5 偶图与匹配 153
8.5.1 偶图 153
8.5.2 匹配 155
习题 156
第9章 代数结构 159
9.1 二元运算 159
习题 161
9.2 半群与群 161
习题 164
9.3 子群与正规子群 166
习题 170
9.4 循环群 171
习题 173
9.5 变换群 174
习题 176
9.6 同态与同构 176
习题 182
9.7 环与域 184
9.7.1 环 184
9.7.2 子环 186
9.7.3 域 187
习题 187
10.1.1 格的定义 191
10.1 格 191
第10章 格与布尔代数 191
10.1.2 子格、格同态 194
习题 197
10.2 特殊格 199
习题 205
10.3 布尔代数 206
习题 209
11.1.2 组合 211
11.1.4 举例 211
11.1.3 计数的基本法则 211
11.1.1 排列 211
11.1 排列与组合 211
第11章 组合与计数基础 211
习题 212
11.2 递推关系 213
11.2.1 母函数 213
11.2.2 递推关系 213
习题 214
11.3 容斥原理 215
习题 216
11.4 鸽巢原理 216
习题 216
部分习题答案及提示 217
参考文献 241