目录
第一篇数 理 逻 辑
第1章命题逻辑/31.1命题及其表示3
1.1.1命题3
1.1.2命题的表示4
1.2联结词4
1.2.1否定5
1.2.2合取5
1.2.3析取6
1.2.4条件6
1.2.5双条件7
1.3命题公式与翻译8
1.3.1命题公式8
1.3.2翻译9
1.4真值表与等价式10
1.4.1真值表10
1.4.2等价式12
1.5重言式、蕴含式与对偶式14
1.5.1重言式14
1.5.2蕴含式15
1.5.3对偶式17
1.6联结词的完备集18
1.6.1不可兼析取18
1.6.2条件的否定19
1.6.3与非19
1.6.4或非19
1.6.5联结词的完备集20
1.7命题公式的范式21
1.7.1合取范式与析取范式21
1.7.2主析取范式23
1.7.3主合取范式26
1.7.4主析取范式与主合取范式之间的联系28
1.8推理理论29
1.8.1有效结论与推理规则29
1.8.2判断有效结论的常用方法31
1.9命题逻辑的应用35
1.10本章总结37
1.11本章习题38
第2章谓词逻辑/44
2.1谓词的概念与表示44
2.1.1谓词的定义44
2.1.2n元谓词45
2.2命题函数与量词46
2.2.1命题函数46
2.2.2量词47
2.3谓词公式与翻译48
2.3.1谓词公式48
2.3.2谓词公式的翻译49
2.4变元的约束50
2.4.1约束变元与自由变元50
2.4.2约束变元的换名与自由变元的代入51
2.4.3有限论域客体变元的枚举52
2.5谓词演算的等价式与蕴含式52
2.5.1谓词公式的赋值及分类52
2.5.2谓词演算的等价式53
2.5.3谓词演算的蕴含式55
2.5.4多个量词之间的等价关系与蕴含关系56
2.6前束范式57
2.7谓词演算的推理理论58
2.8本章总结61
2.9本章习题63
第二篇集合论
第3章集合/713.1集合的概念和表示法71
3.1.1集合的概念71
3.1.2集合的表示73
3.1.3特殊集合74
3.1.4集合之间的关系75
3.2集合的运算77
3.3序偶与笛卡儿积83
3.3.1序偶83
3.3.2笛卡儿积84
3.4包含排斥原理87
3.5集合的划分与覆盖89
3.6集合的应用90
3.7本章总结94
3.8本章习题97
第4章关系/102
4.1关系的概念与表示102
4.1.1关系的概念102
4.1.2关系的表示104
4.2关系的性质107
4.2.1关系的几种性质107
4.2.2性质的判别111
4.3复合关系和逆关系113
4.3.1复合关系113
4.3.2逆关系117
4.4关系的闭包运算119
4.4.1关系的闭包定义120
4.4.2关系闭包运算的相关定理120
4.5等价关系与等价类126
4.5.1等价关系126
4.5.2等价类127
4.5.3商集128
4.6相容关系130
4.6.1相容关系及其表示130
4.6.2相容类131
4.6.3最大相容类132
4.6.4完全覆盖133
4.7序关系134
4.7.1偏序关系及其表示134
4.7.2盖住关系135
4.7.3全序关系136
4.7.4特殊元素137
4.7.5良序集合139
4.8关系的应用140
4.9本章总结144
4.10本章习题145
第5章函数/153
5.1函数的概念153
5.2几种特殊的函数154
5.3函数的运算156
5.3.1复合函数156
5.3.2逆函数157
5.4函数的应用159
5.5本章总结163
5.6本章习题164
第三篇代 数 系 统
第6章代数结构/1696.1代数系统引论169
6.2基本运算及其性质170
6.3半群与独异点176
6.4群与子群178
6.5阿贝尔群与循环群182
6.5.1阿贝尔群（交换群）182
6.5.2循环群182
6.6置换群185
6.7陪集与拉格朗日定理186
6.7.1陪集186
6.7.2拉格朗日定理188
6.8同构与同态190
6.8.1同构190
6.8.2同态193
6.9环与域196
6.9.1环196
6.9.2域199
6.10代数结构的应用200
6.10.1计数问题201
6.10.2群码与纠错码204
6.11本章总结217
6.12本章习题219
第7章格与布尔代数/224
7.1格的定义224
7.2分配格229
7.3有补格231
7.4布尔代数233
7.4.1布尔代数的一般概念233
7.4.2子代数234
7.4.3布尔同态与布尔同构235
7.5布尔代数表达式238
7.6格与布尔代数的应用245
7.6.1布尔函数的表示法246
7.6.2逻辑电路设计方法249
7.6.3时序逻辑电路的设计253
7.7本章总结257
7.8本章习题259
第四篇图论
第8章图/2658.1图的基本概念265
8.2路、回路与连通性271
8.2.1路与回路271
8.2.2无向图的连通性272
8.2.3有向图的连通性275
8.3图的矩阵表示277
8.3.1邻接矩阵277
8.3.2可达矩阵280
8.3.3关联矩阵281
8.4图的应用283
8.4.1无向图的应用283
8.4.2有向图的应用284
8.4.3混合图的应用284
8.4.4一些特殊简单图及其应用284
8.5本章总结286
8.6本章习题288
第9章特殊图/291
9.1欧拉图291
9.2哈密尔顿图296
9.3平面图300
9.4对偶图303
9.5树与根树306
9.5.1树的概念306
9.5.2生成树308
9.5.3根树309
9.6树与根树的应用311
9.6.1最小生成树311
9.6.2最优树312
9.7本章总结313
9.8本章习题316
第10章上机实验/319
10.1实验一： 数理逻辑319
10.1.1真值表319
10.1.2合式公式等价性验证320
10.1.3主析取范式和主合取范式321
10.1.4有效结论321
10.2实验二： 集合论322
10.2.1集合基本计算322
10.2.2幂集323
10.2.3笛卡儿积323
10.2.4关系的性质324
10.2.5关系的复合运算325
10.2.6关系的闭包325
10.2.7偏序关系326
10.2.8函数特性判断326
10.3实验三： 代数系统327
10.3.1幺元和零元327
10.3.2群328
10.3.3半群、独异点和群328
10.4实验四： 图论328
10.4.1圈329
10.4.2连通图329
10.4.3可达矩阵330
10.4.4欧拉图331
10.4.5地图着色问题331
10.4.6哈夫曼编码332
参考文献/333
