目　录

第 1章　命题逻辑　1
1.1　命题及联结词　1
1.1.1　命题　1
1.1.2　命题联结词　2
1.2　命题公式及其分类　5
1.2.1　命题公式　6
1.2.2　命题公式的解释与真值表　7
1.2.3　命题公式的分类　8
1.2.4　命题公式的基本等价关系　10
1.3　命题公式的范式　13
1.3.1　析取范式和合取范式　14
1.3.2　主析取范式和主合取范式　14
1.4　命题逻辑推理与证明技术　18
1.4.1　形式推理　18
1.4.2　推理规则　18
1.4.3　判定有效性的方法　19
1.5　其他联结词　21
1.6　命题逻辑的应用　22
习题1　26

第 2章　谓词逻辑　28
2.1　谓词逻辑的基本概念　28
2.1.1　个体词与谓词　28
2.1.2　量词　30
2.1.3　谓词的翻译　31
2.2　谓词公式与解释　32
2.2.1　谓词的合式公式　32
2.2.2　自由变元和约束变元　33
2.2.3　谓词公式的解释　34
2.2.4　谓词公式的分类　35
2.2.5　谓词公式的基本等值式　35
2.3　谓词公式的范式　37
2.3.1　谓词公式的前束范式　37
2.3.2　Skolem标准型　38
2.4　谓词逻辑推理　38
2.4.1　谓词逻辑的推理　38
2.4.2　谓词逻辑推理方法　39
2.5　谓词逻辑的应用　41
习题2　45

第3章　集合与关系　48
3.1　集合的基本概念　48
3.1.1　集合与元素　48
3.1.2　集合间的关系　49
3.2　集合的运算　50
3.3　容斥原理　51
3.4　序偶与笛卡儿积　53
3.4.1　序偶　53
3.4.2　笛卡儿积　54
3.5　关系及其表示　56
3.5.1　关系的定义　56
3.5.2　关系的表示　57
3.5.3　几种特殊的关系　58
3.6　关系的性质及其判定方法　59
3.6.1　关系的性质　59
3.6.2　关系性质的判定　60
3.7　复合关系和逆关系　62
3.7.1　复合关系　62
3.7.2　复合关系的矩阵表示及图形表示　64
3.7.3　逆关系　66
3.8　关系的闭包运算　68
3.9　等价关系与相容关系　71
3.9.1　集合的划分和覆盖　71
3.9.2　等价关系与等价类　72
3.9.3　相容关系　75
3.10　偏序关系　77
3.10.1　偏序关系的定义　77
3.10.2　偏序关系的哈斯图　77
3.10.3　偏序集中特殊元素　79
3.10.4　两种特殊的偏序集　81
3.11　集合和关系的应用　81
3.11.1　关系在关系数据库中的应用　81
3.11.2　等价关系的应用　84
3.11.3　同余关系和偏序关系的应用　85
习题3　87

第4章　函数　89
4.1　函数的概念　89
4.2　特殊函数　92
4.3　复合函数和反函数　94
4.3.1　复合函数　94
4.3.2　反函数　96
4.4　置换　98
4.5　基数　99
4.5.1　无限集合　99
4.5.2　基数的概念　100
4.5.3　可数集与不可数集　101
4.6　 函数的应用　104
4.6.1　一些有趣的双射函数　104
4.6.2　哈希函数　105
习题4　110

第5章　图的基本理论　112
5.1　图的定义及相关概念　112
5.1.1　图的定义及其表示　113
5.1.2　图的同构　114
5.1.3　子图　115
5.1.4　图的运算　116
5.2　通路、回路与连通性　117
5.2.1　通路、回路　117
5.2.2　无向图的连通性　118
5.2.3　有向图的连通性　119
5.3　图的矩阵表示　120
5.3.1　图的关联矩阵　120
5.3.2　图的邻接矩阵　121
5.3.3　可达矩阵　123
5.4　图中通路的应用　124
习题5　125

第6章　特殊图　128
6.1　树　128
6.1.1　无向树及其性质　128
6.1.2　生成树与**小生成树　130
6.1.3　根树的基本概念　133
6.1.4　**优树　134
6.1.5　二叉树的遍历　135
6.2　欧拉图　135
6.3　哈密顿图　138
6.4　二部图　141
6.4.1　二部图定义及其判定定理　141
6.4.2　二部图中的匹配　141
6.5　平面图　143
6.5.1　平面图的基本概念　143
6.5.2　欧拉公式　144
6.5.3　平面图的判断定理　145
6.5.4　平面图的对偶图　146
6.6　特殊图的应用　147
6.6.1　根树的应用　147
6.6.2　欧拉图的应用　150
6.6.3　哈密顿图的应用　152
6.6.4　二部图的应用　154
习题6　155

第7章　代数系统基础　158
7.1　代数运算　158
7.1.1　什么是运算　158
7.1.2　运算的定义　159
7.2　代数系统及运算的性质　161
7.2.1　代数系统　161
7.2.2　二元运算的性质　161
7.3　代数系统中的特殊元及子代数系统　163
7.3.1　代数系统中的特殊元　163
7.3.2　子代数系统　166
7.4　代数系统的同态与同构　166
7.5　常用的代数系统分类　169
习题7　171

第8章　几个典型的代数系统　174
8.1　半群与幺半群　174
8.1.1　半群和循环半群　174
8.1.2　幺半群与循环幺半群　175
8.2　群　176
8.2.1　群的定义及性质　177
8.2.2　子群及同态　181
8.2.3　特殊群　183
8.2.4　陪集与拉格朗日定理　185
8.3　环与域　188
8.3.1　环与域的定义　188
8.3.2　环与域的性质　189
8.3.3　子环及环同态　190
8.4　格与布尔代数　191
8.4.1　格的概念与性质　192
8.4.2　子格及格同态　195
8.4.3　几种特殊格　197
8.4.4　布尔代数　200
8.4.5　布尔表达式　203
8.5　典型代数系统的应用　204
8.5.1　半群的应用——有穷(限)自动机　204
8.5.2　群论的应用——纠错码　208
8.5.3　布尔代数的应用——全加器的电路设计　216
习题8　219