第一部分 数理逻辑 1
第1章 命题逻辑演算系统 1
1.1命题逻辑演算系统的概念 1
1.1.1命题 1
1.1.2联结词 4
1.2命题公式与真值表 7
1.2.1命题公式与命题函数 8
1.2.2命题公式的真值表 10
1.2.3永真式与永假式 11
1.2.4其他联结词 13
1.2.5最小联结词组 14
1.3等价式与蕴含式 15
1.3.1命题公式的等价 16
1.3.2命题公式的蕴含 17
1.3.3等价的判定 18
1.3.4蕴含的判定 19
1.4范式与对偶式 21
1.4.1对偶公式 21
1.4.2范式 24
1.4.3主范式 25
1.5命题演算的推理理论 30
1.5.1有效推理的概念 30
1.5.2推理过程 31
习题 35
第2章 一阶谓词逻辑演算系统 40
2.1谓词命题 40
2.1.1原子命题的谓词表示 40
2.1.2量词 42
2.1.3论域 42
2.1.4含量词的谓词命题 44
2.2谓词命题公式及约束变量 45
2.2.1谓词命题公式 45
2.2.2谓词公式的解释与赋值 47
2.2.3谓词公式的等价与蕴含 49
2.2.4约束变量与自由变量 50
2.2.5代入实例 51
2.3谓词逻辑演算的等价式和蕴含式 53
2.3.1等价式与蕴含式 53
2.3.2多元谓词及其量词 55
2.3.3前束范式与Skolem范式 56
2.4谓词逻辑演算的推理理论 57
习题 63
第二部分 集合论 67
第3章 集合与关系 67
3.1集合及集合运算 67
3.1.1集合的概念 67
3.1.2集合的表示法 68
3.1.3集合公理 68
3.1.4集合的运算 74
3.1.5集合的运算性质 76
3.2三个基本原理 80
3.2.1排列组合的复习 80
3.2.2鸽巢原理 81
3.2.3包含排斥原理 82
3.2.4生成函数 84
3.3笛卡儿（Descartes）积与关系 87
3.3.1序偶与笛卡儿积 87
3.3.2关系的概念 91
3.3.3关系的表示 93
3.3.4关系的性质 94
3.4关系的运算 97
3.4.1关系的集合运算 98
3.4.2关系的复合运算 98
3.4.3关系的逆运算 102
3.4.4关系的闭包运算 104
3.5等价关系与相容关系 109
3.5.1划分与覆盖 109
3.5.2等价关系与等价类 111
3.5.3相容关系与相容类 115
3.6次序关系 117
3.6.1偏序关系 118
3.6.2 Hasse图 119
3.6.3上确界与下确界 121
3.6.4良序关系 123
习题 123
第4章 函数 131
4.1函数的概念 131
4.1.1函数的定义 131
4.1.2函数的特性 133
4.2复合函数与逆函数 136
4.2.1复合函数 136
4.2.2逆函数 137
4.2.3函数的运算性质 138
4.3序数与自然数 140
4.3.1等势与劣势 140
4.3.2自然数 142
4.3.3序数 146
4.4基数 147
4.4.1基数的定义 147
4.4.2可数集与不可数集 148
4.4.3基数的比较 151
习题 153
第三部分 代数系统 155
第5章 代数结构 155
5.1置换及其运算 155
5.1.1置换与轮换 155
5.1.2轮换的运算性质及方法 158
5.1.3几个轮换运算的等式 163
5.2数论初步 163
5.2.1整数 164
5.2.2辗转相除法 165
5.2.3整数的互质性 168
5.2.4整数的同余性 169
5.3代数系统的概念 173
5.3.1代数系统 173
5.3.2子代数系统 177
5.4代数结构与子结构 178
5.4.1代数结构 179
5.4.2子代数结构 186
5.5同态，同构与同余 187
5.5.1同态与同构 187
5.5.2同余关系 192
5.6几种典型的群 196
5.6.1交换群 196
5.6.2循环群 196
5.6.3置换群 198
5.6.4变换群与凯莱（Cayley）定理 200
5.7陪集与拉格朗日定理 202
5.7.1陪集 202
5.7.2拉格朗日（Lagrange）定理 204
5.7.3正规子群 205
5.7.4同态定理 208
5.8商代数与积代数 209
5.8.1商代数 209
5.8.2积代数 211
5.9环与域 212
5.9.1环 212
5.9.2整环和域 214
5.9.3环同态与理想 216
习题 220
第6章 格与布尔代数 226
6.1格的概念 226
6.1.1格与子格 226
6.1.2格的性质 229
6.1.3格的同态 233
6.2几种典型的格 236
6.2.1分配格 236
6.2.2模格 239
6.2.3有界格 241
6.2.4有补格 242
6.2.5布尔（Boolean）格 243
6.3 Stone表示定理 247
6.4布尔表达式 250
6.4.1布尔表达式 250
6.4.2布尔函数 251
6.4.3布尔表达式的析取范式与合取范式 252
习题 257
第四部分 图论 259
第7章 图论 259
7.1图的基本概念 259
7.1.1图的概念与定义 259
7.1.2常用的术语 260
7.1.3顶点的度数 262
7.1.4子图与补图 263
7.1.5图同构 265
7.1.6图的运算 266
7.2路与连通性 268
7.2.1路与通路 268
7.2.2无向连通 270
7.2.3有向连通 273
7.3图的矩阵 276
7.3.1邻接矩阵 276
7.3.2完全关联矩阵 279
7.3.3可达矩阵 283
7.3.4回路矩阵 284
7.3.5割集矩阵 286
7.4欧拉图与哈密尔顿图 287
7.4.1 Euler图 288
7.4.2 Hamilton图 292
7.5树及其应用 295
7.5.1无向树 295
7.5.2生成树 299
7.5.3生成树的个数 302
7.5.4有向树及根树 304
7.5.5哈夫曼（Huffman）树 306
7.5.6树的应用 308
7.6通路问题 310
7.6.1关键路径 310
7.6.2最短通路 312
7.6.3最优通路 315
7.7平面图 318
7.7.1平面图的概念 318
7.7.2对偶图 321
7.8图的着色 322
7.8.1色数与五色定理 322
7.8.2色多项式 324
7.9二分图与匹配 327
7.9.1独立集与二分图 328
7.9.2匹配 329
7.10网络流 333
7.10.1基本概念 334
7.10.2最大流与最小割 335
习题 338
附录 中英文名词对照 346
参考文献 355