第 一篇　数理逻辑

第 1章　命题逻辑　3
1.1　命题　4
1.1.1　命题的概念　4
1.1.2　命题的分类　5
1.2　联结词　5
1.2.1　否定联结词　6
1.2.2　合取联结词　6
1.2.3　析取联结词　7
1.2.4　条件联结词　8
1.2.5　双条件联结词　9
1.3　命题公式与翻译　10
1.3.1　命题公式的定义　10
1.3.2　真值表　11
1.3.3　命题的翻译　12
1.4　命题公式的等价、蕴涵　13
1.4.1　重言式和矛盾式　13
1.4.2　命题公式的等价关系　14
1.4.3　置换　16
1.4.4　命题公式的蕴涵关系　17
1.5　对偶与范式　19
1.5.1　对偶式　19
1.5.2　析取范式与合取范式　21
1.5.3　主析取范式　21
1.5.4　主合取范式　23
1.6　其他联结词　25
1.6.1　不可兼析取联结词　26
1.6.2　条件否定联结词　27
1.6.3　与非联结词　28
1.6.4　或非联结词　28
1.6.5　联结词之间的关系　29
1.7　命题演算推理　29
1.7.1　有效论证的概念　29
1.7.2　真值表法　30
1.7.3　直接证法　32
1.7.4　间接证法　34
1.8　应用　36
1.9　典型例题解析　40
本章小结　45
习题　45

第 2章　谓词逻辑　52
2.1　谓词和量词　52
2.1.1　谓词的概念　52
2.1.2　全称量词和存在量词　54
2.2　谓词公式与翻译　56
2.2.1　谓词公式的定义　56
2.2.2　谓词公式的翻译　56
2.3　约束变元与自由变元　57
2.4　谓词公式的等价、蕴涵　59
2.4.1　一些基本概念　59
2.4.2　量词与联结词﹁之间的关系　59
2.4.3　量词辖域的扩张与收缩　60
2.4.4　量词与命题联结词之间的一些等价、蕴涵式　60
2.5　前缀范式　63
2.5.1　前缀范式的定义　63
2.5.2　前缀合取范式和前缀析取范式　64
2.6　谓词演算推理　64
2.6.1　四个基本的推理规则　64
2.6.2　推理规则的应用　66
2.7　应用　67
2.8　典型例题解析　70
本章小结　72
习题　72

第 二篇　集合论

第3章　集合及其运算　83
3.1　集合的概念与性质　84
3.1.1　集合的概念　84
3.1.2　集合的表示　85
3.1.3　三个基本原理　86
3.1.4　集合的性质　87
3.1.5　幂集　89
3.2　集合的运算　89
3.2.1　Venn图　89
3.2.2　集合的运算　90
3.2.3　集合的运算性质　93
3.3　序偶和笛卡尔积　94
3.3.1　序偶　94
3.3.2　笛卡尔积　94
3.4　数学归纳法　96
3.4.1　集合的归纳定义　96
3.4.2　自然数的集合论定义*　97
3.4.3　数学归纳法　98
3.5　典型例题解析　99
本章小结　101
习题　102

第4章　关系　106
4.1　关系的概念及性质　107
4.1.1　关系的概念　107
4.1.2　关系的表示方法　107
4.1.3　关系的性质　109
4.2　关系的运算　110
4.2.1　复合运算　111
4.2.2　逆运算　114
4.2.3　闭包运算　115
4.3　等价关系、等价类与划分　120
4.4　相容关系、相容类与覆盖　124
4.5　偏序关系　127
4.6　典型例题解析　131
本章小结　136
习题　137

第5章　函数　141
5.1　函数的概念　141
5.2　函数的分类　143
5.2.1　满射、单射和双射　143
5.2.2　合成映射、恒等映射及逆映射　144
5.3　特征函数　149
5.4　典型例题解析　152
本章小结　153
习题　154

第6章　基数　157
6.1　基本概念　157
6.1.1　等势　157
6.1.2　有限集和无限集　158
6.1.3　基数　158
6.2　可数集和不可数集　159
6.2.1　基本概念　159
6.2.2　连续统的势　161
6.2.3　无限集的性质　162
6.3　基数的比较　163
6.3.1　基数的比较　163
6.3.2　基数的性质　165
6.4　典型例题解析　168
本章小结　169
习题　169

第7章　集合论的发展与应用　172
7.1　计数原理*　172
7.1.1　计数的基础　172
7.1.2　容斥原理　174
7.1.3　鸽笼原理　177
7.1.4　重集　179
7.2　模糊集基础*　180
7.2.1　发展简介　180
7.2.2　模糊集合的概念与方法　181
7.2.3　模糊理论的其他应用　190
7.3　集合的应用　193
7.3.1　关系在信息模型设计中的应用　193
7.3.2　关系数据库　193
本章小结　197
习题　197

第三篇　代数结构

第8章　群　201
8.1　代数系统的基本概念　202
8.1.1　运算　202
8.1.2　代数系统、子代数与积代数　204
8.2　半群与独异点　206
8.3　群　207
8.3.1　群　207
8.3.2　群的性质　208
8.4　子群　209
8.4.1　子群的定义　209
8.4.2　子群的判别条件　209
8.5　阿贝尔群与循环群　210
8.5.1　阿贝尔群　210
8.5.2　循环群　211
8.6　置换群　213
8.6.1　置换的定义　213
8.6.2　置换群　214
8.7　拉格朗日定理　216
8.8　同态及同构　219
8.8.1　同态映射　219
8.8.2　同构映射　220
8.8.3　同态核　221
8.9　典型例题解析　223
本章小结　226
习题　226

第9章　格与布尔代数　228
9.1　格　229
9.1.1　格的定义　229
9.1.2　格的性质　232
9.1.3　格的同态与同构　235
9.1.4　几种特殊的格　238
9.2　布尔代数　244
9.2.1　布尔代数的定义　244
9.2.2　布尔代数的性质　245
9.2.3　亨廷顿(Huntington)公理　246
9.2.4　有限布尔代数　248
9.2.5　布尔表达式与布尔函数　252
9.2.6　布尔代数的同态与同构　253
9.3　应用　255
9.3.1　开关电路函数　255
9.3.2　全加器的逻辑设计　256
9.4　典型例题解析　257
本章小结　265
习题　265

第四篇　图论

第 10章　图　269
10.1　图模型　270
10.2　图的分类　275
10.3　图的连通性　278
10.4　图的矩阵表示　283
10.5　典型例题解析　290
本章小结　294
习题　295

第 11章　特殊图　297
11.1　欧拉图与Hamilton图　297
11.1.1　欧拉图　297
11.1.2　Hamilton图　299
11.1.3　应用举例　303
11.2　二分图与匹配　304
11.2.1　二分图的基本概念　305
11.2.2　匹配　306
11.2.3　分配问题　308
11.3　平面图、对偶图与地图着色　309
11.3.1　平面图　309
11.3.2　对偶图与地图着色　313
11.4　网络及**大流问题　316
11.5　典型例题解析　319
本章小结　325
习题　325

第 12章　树　329
12.1　树的概念　329
12.2　生成树　331
12.3　根树、二叉树及其应用　335
12.3.1　根树　335
12.3.2　二叉树及其遍历　336
12.3.3　应用举例　340
12.4　典型例题解析　343
本章小结　346
习题　346

第 13章　超图概述*　348
13.1　基本概念　348
13.2　超图的链和圈　349
13.3　E-C-R性质和Helly性质　350
本章小结　351

参考文献　352