第一部分 数理逻辑 3
第一章 命题逻辑基本概念 3
1.1 命题及其符号化 3
1.1.1 命题 3
1.1.2 命题符号化 4
1.2 合式公式和真值赋值 10
1.2.1 合式公式及层次 10
1.2.2 真值赋值及公式分类 12
1.3 真值表和真值函数 14
习题一 16
第二章 命题逻辑等值演算 19
2.1 等值关系 19
2.2 联结词的全功能集 24
2.3 范式 27
2.4.1 门电路和触发器 34
2.4 数字逻辑电路初步 34
2.4.2 组合逻辑电路的设计 36
2.4.3 时序逻辑电路的设计 38
习题二 42
第三章 命题逻辑自然推理 44
3.1 推理的形式结构 44
3.2 自然推理系统P 47
3.3 常见的证明方法 49
习题三 53
第四章 谓词逻辑的基本概念 54
4.1 谓词和量词 55
4.2 一阶语言 59
4.2.1 一阶语言 60
4.2.2 解释和赋值 63
4.2.3 公式的分类 66
4.3 一阶逻辑等值演算 67
4.3.1 等值演算 67
4.3.2 前束范式 69
4.4 一阶逻辑形式推理 71
4.4.1 推理定律 71
4.4.2 推理规则 72
习题四 75
第二部分 集合论 79
第五章 集合代数 79
5.1 集合的概念及表示 79
5.2 集合运算 85
5.3 集合定律 89
5.4 有限集的计数问题 90
5.5 有序对与卡氏积 94
习题五 96
第六章 二元关系 99
6.1 二元关系及其表示 99
6.2 二元关系的性质 102
6.3.1 关系的限制和像 104
6.3 二元关系的运算 104
6.3.2 关系的逆 106
6.3.3 关系的合成 106
6.3.4 关系的闭包 109
6.4 特殊关系及其性质 117
6.4.1 等价关系及性质 117
6.4.2 相容关系及性质 120
6.4.3 序关系及性质 123
习题六 127
第七章 函数 130
7.1 函数基本概念 130
7.2 函数的合成 134
7.3 反函数 137
7.4 特殊函数 140
7.4.1 特征函数 140
7.4.2 变换函数和置换函数 142
7.5 集合的基数 146
习题七 150
第三部分 代数系统 152
第八章 代数结构 152
8.1 代数系统基本概念 152
8.1.1 代数运算及其性质 152
8.1.2 代数系统 156
8.1.3 积代数和商代数 157
8.2 半群和群 159
8.2.1 半群 159
8.2.2 群 161
8.2.3 子群和陪集 170
8.3 环和域 174
8.4 差错编码初步 179
8.5 差错解码初步 185
习题八 188
第九章 格与布尔代数 191
9.1 格的定义和性质 191
9.2 分配格与有补格 197
9.3 布尔代数 200
习题九 203
第四部分 图论 207
第十章 图 207
10.1 图的基本概念 207
10.1.1 有向图和无向图 207
10.1.2 关联和相邻或邻接 209
10.1.3 点的度数 209
10.1.4 特殊图 211
10.1.5 图的同构 213
10.2 图的运算 214
10.3 图的连通性 218
10.3.1 通路和回路 218
10.3.2 无向图的连通性 219
10.3.3 有向图的连通性 222
10.4.1 无向图的矩阵表示 225
10.4 图的矩阵表示 225
10.4.2 有向图的矩阵表示 230
习题十 234
第十一章 通路应用问题 236
11.1 最短径问题 236
11.2 关键路径问题 240
11.3 网络最大流量问题 242
11.4 穿程问题 248
11.4.1 欧拉图 248
11.4.2 哈密顿图 250
习题十一 254
第十二章 树 256
12.1 无向树基本概念 256
12.2 生成树 258
12.2.1 生成树及其做法 258
12.2.2 生成树的应用 262
12.3 最小生成树 266
12.4 根树 269
12.5 二叉树应用 275
习题十二 279
第十三章 平面图 281
13.1 平面图基本概念 281
13.2 欧拉公式 284
13.3 平面图的判断 287
13.4 对偶图及着色 289
习题十三 293
第十四章 偶图与匹配 295
14.1 偶图的判断 295
14.2 匹配 296
习题十四 300
附录1 数学工具 302
附录2 习题答案或提示 308
参考文献 348