第一篇 数理逻辑 3
第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.1.1 谓词的概念 52
2.1 谓词和量词 52
第2章 谓词逻辑 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.6.1 四个基本的推理规则 64
2.6 谓词演算推理 64
2.5.2 前缀合取范式和前缀析取范式 64
2.6.2 推理规则的应用 66
2.7 应用 67
2.8 典型例题解析 70
本章小结 72
习题 72
第二篇 集合论 83
第3章 集合及其运算 83
3.1 集合的概念与性质 84
3.1.1 集合的概念 84
3.1.2 集合的表示 85
3.1.3 三个基本原理 86
3.1.4 集合的性质 87
3.2.1 Venn图 89
3.1.5 幂集 89
3.2 集合的运算 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.3 基数 158
6.1.2 有限集和无限集 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
第三篇 代数结构 201
第8章 群 201
8.1.1 运算 202
8.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.1 置换的定义 213
8.6 置换群 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
第四篇 图论 269
第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