第1篇 数理逻辑 3
第1章 命题逻辑 3
1.1命题与连接词 3
1.1.1命题的概念 3
1.1.2逻辑连接词 4
1.2命题公式及命题公式的翻译 7
1.2.1命题公式 7
1.2.2命题的翻译 7
1.2.3命题公式的解释 8
1.3等价公式及公式的分类 10
1.3.1等价公式的定义和性质 10
1.3.2基本等价公式 11
1.3.3置换规则 11
1.3.4公式的分类 12
1.4蕴含式与对偶式 14
1.4.1蕴含式 14
1.4.2对偶式 16
1.5其他连接词与最小连接词组 18
1.5.1其他连接词 18
1.5.2最小连接词组 19
1.6范式 20
1.6.1简单合取式与简单析取式 21
1.6.2公式的范式 21
1.7公式的主范式 22
1.7.1主析取范式 23
1.7.2主合取范式 25
1.7.3主析取范式与主合取范式之间的关系 28
1.7.4主范式的应用 29
1.8推理理论 29
1.8.1有效论证 30
1.8.2推理方法 30
习题 34
第2章 谓词逻辑 38
2.1谓词逻辑的基本概念 38
2.1.1个体、谓词 38
2.1.2命题函数 39
2.1.3量词 39
2.2谓词公式与翻译 40
2.2.1谓词公式 40
2.2.2谓词公式的翻译 41
2.3约束变元与自由变元 42
2.4谓词演算的等价式及蕴含式 44
2.4.1量词的转换律 44
2.4.2量词辖域的扩张律与收缩律 45
2.4.3量词的分配律 46
2.4.4多个量词的使用 47
2.5前束范式 48
2.6谓词演算的推理理论 50
2.6.1推理规则 50
2.6.2推理实例 51
习题 55
第2篇 集合论 61
第3章 集合的基本概念和运算 61
3.1集合的基本概念 61
3.2集合的基本运算 63
3.2.1集合的运算 63
3.2.2集合运算算律 65
3.3集合中元素的计数 66
3.3.1容斥原理 66
3.3.2容斥原理实例 69
3.4笛卡儿乘积 70
3.4.1有序对 70
3.4.2笛卡儿积 71
3.4.3 n阶笛卡儿积 73
习题 74
第4章 关系 77
4.1关系的概念 77
4.2关系的表示与性质 79
4.2.1关系的矩阵表示 79
4.2.2关系的图形表示法 79
4.2.3关系的性质 80
4.3关系的运算 81
4.3.1关系的逆运算 81
4.3.2关系的合成运算 83
4.4关系的闭包运算 86
4.5相容关系与覆盖 91
4.5.1关系图法 93
4.5.2关系矩阵法 93
4.6等价关系与划分 94
4.7偏序关系 96
习题 100
第5章 函数 106
5.1函数的基本概念和性质 106
5.1.1函数的定义 106
5.1.2函数的性质 108
5.2函数的复合与反函数 113
5.2.1函数的复合运算 113
5.2.2函数的逆运算 115
习题 118
第3篇 代数系统 123
第6章 代数系统一般性质 123
6.1二元运算及其性质 123
6.1.1二元运算 123
6.1.2二元运算律 125
6.1.3二元运算特殊元 126
6.1.4二元运算实例 128
6.2代数系统 130
6.3代数系统的同态与同构 132
6.3.1同态与同构 132
6.3.2同态与同构实例 133
6.3.3同态与同构的性质 136
6.4同余关系与商代数 136
6.4.1同余关系 136
6.4.2商代数 137
习题 137
第7章 典型的代数系统 141
7.1半群与群 141
7.1.1半群与独异点 141
7.1.2群的定义与性质 144
7.1.3子群 147
7.1.4陪集与拉格朗日定理 150
7.1.5正规子群与商群 155
7.1.6群的同态与同构 157
7.1.7循环群 158
7.1.8置换群 161
7.2环和域 164
7.2.1环的定义 164
7.2.2整环与域 165
7.2.3环的性质 166
7.2.4子环、理想与商环 168
7.3格与布尔代数 169
7.3.1格的定义与性质 169
7.3.2子格与格同态 172
7.3.3分配格 174
7.3.4有补格 175
7.3.5布尔代数 175
习题 178
第4篇 图论 185
第8章图 185
8.1图的基本概念 185
8.1.1图的定义 185
8.1.2子图 190
8.1.3图的同构 191
8.1.4图的运算 192
8.2图的连通性 193
8.2.1通路和回路 193
8.2.2图的连通性 195
8.2.3图的连通度 198
8.3图的矩阵表示 200
8.3.1图的关联矩阵 200
8.3.2图的邻接矩阵 201
8.3.3图的可达矩阵 204
习题 206
第9章 欧拉图和哈密顿图 209
9.1欧拉图 209
9.1.1欧拉图的引入和定义 209
9.1.2欧拉图的判定 211
9.1.3欧拉图的难点 214
9.1.4欧拉图的应用 215
9.2哈密顿图 219
9.2.1哈密顿图的引入和定义 219
9.2.2哈密顿图的判定 220
9.2.3哈密顿图的难点 226
9.2.4哈密顿图的应用 227
习题 229
第10章 特殊图 233
10.1树 233
10.1.1树的定义与性质 233
10.1.2生成树 236
10.1.3最小生成树 237
10.1.4根树定义与分类 239
10.1.5最优树与哈夫曼算法 242
10.2二分图 243
10.2.1二分图的引入和定义 243
10.2.2二分图的判定 243
10.2.3匹配 245
10.3平面图 249
10.3.1平面图的引入和定义 249
10.3.2平面图的欧拉公式 251
10.3.3平面图判定 253
10.3.4平面图的对偶图 253
10.3.5平面图的可着色性 254
10.3.6平面图的应用 256
习题 256
参考文献 259