第零部分 准备知识 1
0.1 离散数学的作用和学习 1
0.2 集合的概念及表示 3
第一部分 数理逻辑 7
第一章 命题逻辑基本概念 7
1.1 命题及其符号化 7
1.2 合式公式和真值赋值 13
1.3 真值表 16
习题一 18
第二章 命题逻辑等值演算 21
2.1 等值关系 21
2.2 联结词的全功能集 25
2.3 范式 27
2.4 数字逻辑电路初步 32
习题二 40
第三章 命题逻辑推理 42
3.1 推理的形式结构 42
3.2 自然推理系统P 45
3.3 常见的证明方法 46
3.4 命题逻辑机器证明 50
习题三 51
第四章 谓词逻辑的基本理论 53
4.1 谓词和量词 53
4.2 一阶语言 57
4.3 一阶逻辑等值演算 64
4.4 一阶逻辑形式推理 67
习题四 73
第二部分 集合论 77
第五章 集合代数 77
5.1 子集和补集 77
5.2 集合运算和性质 79
5.3 有限集的计数问题 85
5.4 有序对与卡氏积 88
习题五 91
第六章 二元关系 93
6.1 二元关系及其表示 93
6.2 二元关系的性质 95
6.3 二元关系的运算 98
6.4 特殊关系及其性质 109
习题六 118
第七章 函数 121
7.1 函数的基本概念 121
7.2 函数的合成 125
7.3 反函数和函数的可逆性 127
7.4 特殊函数 130
7.5 集合的计数理论 136
习题七 140
第三部分 代数系统 142
第八章 代数结构 142
8.1 代数系统基本概念 142
8.2 半群和群 148
8.3 环和域 161
8.4 差错编码初步 165
8.5 差错解码初步 172
习题八 174
第九章 格与布尔代数 177
9.1 格的定义和性质 177
9.2 分配格与有补格 182
9.3 布尔代数 185
习题九 187
第四部分 图论 191
第十章 图 191
10.1 图的基本概念 191
10.2 图的运算 197
10.3 图的连通性 200
10.4 图的矩阵表示 205
习题十 213
第十一章 通路应用问题 216
11.1 最短径问题 216
11.2 关键路径问题 219
11.3 网络最大流量问题 221
11.4 穿程问题 225
习题十一 230
第十二章 树 232
12.1 无向树基本概念 232
12.2 生成树 233
12.3 最小生成树 240
12.4 根树 242
12.5 二叉树应用 247
习题十二 251
第十三章 平面图 253
13.1 平面图基本概念 253
13.2 欧拉公式 253
13.3 平面图的判断 257
13.4 对偶图及着色 259
习题十三 263
第十四章 偶图与匹配 264
14.1 偶图的判断 264
14.2 匹配 265
习题十四 270
附录1 数学工具 271
附录1.1 数制进位 271
附录1.2 排列组合基本概念 274
附录1.3 矩阵基本概念 274
附录2 习题参考答案 277