第1章 离散数学基础 3
1.1 算法 3
1.1.1 算法的定义 3
1.1.2 算法的基本特征 4
1.1.3 算法设计方法 5
1.1.4 算法表示 12
1.1.5 算法的复杂度分析 17
1.2 可计算性问题 20
1.3 模和同余 22
1.4 递归 25
1.5 密码学初步 28
1.6 计数 29
小结 30
习题 31
第2章 命题逻辑 34
2.1 命题与联结词 35
2.1.1 命题及其表示 35
2.1.2 联结词 36
2.1.3 最小功能完备集 42
2.2 命题公式与重言式 44
2.2.1 命题公式 44
2.2.2 指派与真值表 44
2.2.3 重言式 46
2.3 范式 48
2.3.1 对偶原理 48
2.3.2 范式 49
2.3.3 主析取范式 51
2.3.4 主合取范式 54
2.4 基于命题的推理 57
2.4.1 推理理论 57
2.4.2 CP规则 61
2.4.3 归谬法 62
小结 64
习题 65
第3章 谓词逻辑 69
3.1 谓词 69
3.2 量词 70
3.2.1 全称量词 70
3.2.2 存在量词 70
3.2.3 量词分析 73
3.3 谓词公式 74
3.4 谓词演算 75
3.5 谓词演算中的推理规则 76
3.5.1 推理规则 76
3.5.2 含有量词的永真式 79
3.6 三元谓词向二元谓词的转换 80
3.7 基于谓词的知识表示 81
3.8 基于谓词演算的程序正确性证明 83
小结 85
习题 85
第4章 集合论 89
4.1 集合的基本概念 89
4.1.1 集合及其表示 89
4.1.2 子集 91
4.1.3 基数 93
4.1.4 幂集 93
4.1.5 悖论 94
4.2 集合的运算 97
4.2.1 集合的并与交 97
4.2.2 集合的差与补 98
4.2.3 环和与环积 99
4.2.4 集合的笛卡儿积 100
4.3 集合运算定律 102
4.4 集合计数 104
4.5 可列集与无限集 107
4.6 集合的计算机表示 109
4.7 自然数集合与数学归纳法 109
小结 111
习题 111
第5章 关系 116
5.1 关系的基本概念 116
5.2 二元关系 119
5.3 二元关系的表示 121
5.3.1 集合表示法 121
5.3.2 关系图 121
5.3.3 关系矩阵 122
5.3.4 表格法 124
5.4 关系的基本性质 124
5.4.1 自反性 124
5.4.2 反自反性 125
5.4.3 对称性 126
5.4.4 反对称性 126
5.4.5 传递性 128
5.5 等价关系与集合划分 132
5.5.1 等价关系 133
5.5.2 等价类 134
5.5.3 集合的划分 136
5.6 相容关系与集合覆盖 138
5.6.1 相容关系 138
5.6.2 相容类 138
5.6.3 覆盖 141
5.7 偏序关系与哈斯图 142
5.7.1 哈斯图与偏序集 142
5.7.2 偏序集中的特殊元素 144
5.8 关系运算 146
5.8.1 复合关系和逆关系 147
5.8.2 逆关系 148
5.8.3 限制与闭包 149
小结 150
习题 151
第6章 函数 155
6.1 函数的定义 156
6.2 特殊函数 158
6.3 函数的运算 160
6.3.1 函数合成 160
6.3.2 逆函数 162
小结 165
习题 165
第7章 图论 168
7.1 图的基本概念 168
7.1.1 图的基本概念 168
7.1.2 度 169
7.1.3 正则图与完全图 170
7.1.4 子图与补图 171
7.1.5 赋权图 172
7.1.6 同构图 172
7.2 图的存储 173
7.2.1 邻接矩阵 173
7.2.2 边目录表示法 175
7.2.3 邻接编目法 175
7.2.4 多重链表 176
7.2.5 十字链表 176
7.3 连通与回路 177
7.3.1 可达与连通 177
7.3.2 欧拉图 180
7.3.3 汉密尔顿图 182
7.4 平面图与对偶图 183
7.4.1 平面图 183
7.4.2 对偶图 186
7.5 二部图与匹配 188
7.6 网络规划 190
7.6.1 规划图 191
7.6.2 结构与优化 192
7.6.3 规划图的绘制 195
7.6.4 规划图参数 197
7.6.5 规划图的优化分析 201
7.7 最短路径模型 205
7.8 图的着色 210
7.9 自补图 210
小结 213
习题 214
第8章 树 218
8.1 无向树 218
8.2 生成树 219
8.3 有向树 221
8.4 二叉树 223
8.5 二叉树的遍历 225
8.6 代数表达式的波兰表示 227
8.7 前缀码与哈夫曼树 230
8.8 决策树 231
8.8.1 决策树实例分析 232
8.8.2 不确定事件的决策分析 234
8.8.3 逆推技术 235
8.8.4 临界值分析 237
8.9 树的存储 238
小结 240
习题 240
第9章 代数结构 245
9.1 代数运算 245
9.1.1 代数运算的基本概念 245
9.1.2 代数运算的表示 247
9.1.3 代数运算的性质 248
9.2 代数系统 250
9.2.1 代数系统的基本概念和表示 250
9.2.2 代数系统中的特殊元素 250
9.3 同构 255
小结 257
习题 257
第10章 群与环 259
10.1 群 260
10.1.1 半群 260
10.1.2 群 262
10.1.3 子群 265
10.1.4 元素的阶数 266
10.1.5 若干特殊群 267
10.2 环和域 272
10.2.1 环 272
10.2.2 域 273
小结 274
习题 275
第11章 格与布尔代数 277
11.1 格 277
11.2 布尔函数 280
11.2.1 布尔函数运算 280
11.2.2 布尔表达式 280
11.2.3 布尔代数中的恒等式 281
11.2.4 对偶性 283
11.2.5 布尔代数的研究意义 283
11.3 布尔函数的表示和构造 283
11.3.1 积之和展开式 283
11.3.2 函数的完备性 284
11.4 逻辑门电路设计 285
11.5 卡诺图 286
11.5.1 卡诺图概述 287
11.5.2 三变元卡诺图 288
11.5.3 四变元卡诺图 289
11.5.4 奎因·莫可拉斯基方法 291
小结 293
习题 293
第12章 附注 296
12.1 国外人物简介 296
12.1.1 欧几里得 296
12.1.2 斐波那契 297
12.1.3 笛卡儿 298
12.1.4 费马 298
12.1.5 欧拉 300
12.1.6 高斯 301
12.1.7 巴贝奇 303
12.1.8 汉密顿 306
12.1.9 黎曼 306
12.1.10 康托尔 307
12.1.11 希尔伯特 309
12.1.12 罗素 309
12.1.13 图灵 310
12.1.14 迪卡斯特拉 310
12.1.15 Ike Nassi 311
12.1.16 哈夫曼 311
12.1.17 刘维尔 312
12.1.18 香农 313
12.1.19 泊松 314
12.1.20 阿贝尔 315
12.1.21 拉格朗日 316
12.1.22 伽罗华 319
12.1.23 卡诺 320
12.2 国内人物简介 320
12.2.1 华罗庚 320
12.2.2 闵嗣鹤 322
12.2.3 柯召 323
12.2.4 王元 325
12.2.5 陈景润 326
12.2.6 潘承洞 327
12.2.7 管梅谷 328
12.3 名词解释 328
12.3.1 图灵机 328
12.3.2 图灵试验 328
12.3.3 图灵奖 329
12.3.4 希尔伯特的23个问题 329
12.3.5 哈斯图 332
参考文献 333