内容简介
离散数学 第二版
作 者： 贲可荣，袁景凌，高志华 编著
出版时间：2011
丛编项： 高等学校计算机教育规划教材
内容简介
离散数学是数学中专门用来研究离散对象及其关系的一个分支，是计算机科学与技术专业的一门重要基础课。它所研究的对象是离散的数量关系和离散的数学结构模型。《离散数学（第2版）》共10章，主要包含数理逻辑、集合与关系、函数、组合计数、图和树、代数系统、自动机和初等数论等内容。《离散数学（第2版）》中的“历史注记”可以帮助读者理解数学，洞察内在本质。 《离散数学（第2版）》体系严谨，选材精炼，讲解翔实，例题丰富，注重理论与计算机科学技术的实际问题相结合，《离散数学（第2版）》选配了大量难度适当的习题，并给出奇数题的答案，适合教学。《离散数学（第2版）》适合作为计算机和相关专业本科生“离散数学”的教学用书，亦可作为对离散数学感兴趣的人员的参考书。
目录
第1章 命题逻辑1
1.1 现代逻辑学的基本研究方法1
1.2 命题及其表示法3
1.2.1 命题的概念3
1.2.2 联结词4
1.3 命题公式与语句形式化7
1.3.1 命题公式的定义7
1.3.2 公式的层次8
1.3.3 语句形式化8
1.3.4 复合命题真假值9
1.3.5 真值表10
1.4 重言式11
1.4.1 重言式概述11
1.4.2 逻辑等价式13
1.4.3 等值演算15
1.5 对偶与范式16
1.5.1 对偶16
1.5.2 简单合取式和简单析取式16
1.5.3 范式17
1.5.4 范式的唯一性--主范式19
1.6 其他联结词24
1.6.1 n元真值函数24
1.6.2 真值函数与命题公式的关系25
1.6.3 联结词完备集25
1.6.4 单元素联结词构成的联结词完备集26
1.7 命题演算的推理理论27
1.7.1 有效推理27
1.7.2 有效推理的等价定理29离散数学（第2版）
1.7.3 重言蕴涵式31
1.7.4 形式推理系统32
1.7.5 自然推理系统p235
1.8 命题演算中的归结推理42
1.8.1 归结推理规则42
1.8.2 归结反演43
1.8.3 命题逻辑归结反演的合理性和完备性44
习题44
第2章 谓词逻辑53
2.1 谓词逻辑的基本概念53
2.1.1 个体词54
2.1.2 谓词54
2.1.3 量词55
2.2 谓词逻辑公式与翻译56
2.2.1 一阶语言56
2.2.2 自由与约束57
2.2.3 闭公式58
2.2.4 谓词逻辑公式的解释59
2.2.5 谓词逻辑命题符号化60
2.2.6 一阶公式的分类63
2.3 谓词逻辑等值演算64
2.3.1 基本等价式与置换规则64
2.3.2 谓词逻辑前束范式68
2.4 谓词演算的推理理论69
2.4.1 推理定律69
2.4.2 量词消去与引入规则70
2.4.3 一阶谓词演算公理系统f171
2.4.4 自然推理系统f272
2.5 谓词演算中的归结推理74
2.5.1 子句型74
2.5.2 置换和合一76
2.5.3 合一算法78
2.5.4 归结式79
2.5.5 归结反演及其完备性80
2.6 逻辑在计算机科学中的作用81
2.6.1 逻辑与计算81
2.6.2 逻辑与计算机的起源82
2.6.3 逻辑与程序设计83
习题84
第3章 集合与关系90
3.1 集合的概念和表示法90
3.1.1 集合的表示90
3.1.2 基本概念92
3.2 集合的运算93
3.2.1 集合的基本运算93
3.2.2 有穷计数集93
3.2.3 广义交和广义并95
3.3 有序对与笛卡儿积97
3.4 关系及其表示99
3.4.1 基本概念99
3.4.2 关系表示法100
3.5 关系的运算102
3.5.1 基本概念102
3.5.2 复合关系103
3.5.3 逆关系104
3.5.4 关系幂106
3.5.5 幂运算的性质107
3.6 关系的性质109
3.6.1 关系的5种基本性质109
3.6.2 关系性质的等价描述 110
3.7 关系的闭包113
3.7.1 基本概念114
3.7.2 闭包的性质118
3.8 集合的划分与覆盖119
3.9 等价关系和等价类120
3.9.1 等价关系120
3.9.2 等价类的性质122
3.9.3 商集与划分123
3.10 相容关系和相容类124
3.11 偏序关系125
3.12 偏序集与哈斯图126
3.13 包含排斥原理129
习题130
第4章 函数137
4.1 函数的定义137
4.1.1 函数和像137
4.1.2 函数的性质139
4.1.3 常用函数140
4.2 复合函数和反函数141
4.2.1 复合函数 141
4.2.2 反函数143
4.3 特征函数与模糊子集145
4.4 基数的概念147
4.4.1 后继与归纳集147
4.4.2 自然数，有穷集，无穷集148
4.4.3 基数152
4.5 可数集与不可数集153
4.6 数学归纳法155
习题158
第5章 组合计数与离散概率162
5.1 基本原理162
5.1.1 加法原理162
5.1.2 乘法原理163
5.2 排列与组合164
5.2.1 排列164
5.2.2 组合164
5.3 排列组合生成算法165
5.3.1 排列生成算法165
5.3.2 组合生成算法 166
5.4 广义的排列和组合169
5.5 二项式系数和组合恒等式171
5.5.1 二项式定理171
5.5.2 组合恒等式172
5.6 鸽笼原理174
5.6.1 鸽笼原理的简单形式174
5.6.2 鸽笼原理的一般形式174
5.7 递推关系及应用176
5.7.1 递推定义函数176
5.7.2 递推定义集合178
5.7.3 递推关系模型179
5.7.4 求解递推关系181
5.7.5 递推在算法分析中的应用183
5.7.6 生成函数187
5.8 离散概率190
5.8.1 随机事件与概率190
5.8.2 有限概率191
5.8.3 条件概率与独立性 193
5.8.4 bayes定理194
习题195
第6章 图论198
6.1 图的基本概念198
6.1.1 图的定义和表示198
6.1.2 图的同构 202
6.1.3 完全图与正则图 204
6.1.4 子图与补图204
6.1.5 通路与回路206
6.2 图的连通性208
6.2.1 无向图的连通性208
6.2.2 有向图的连通性209
6.3 图的矩阵表示210
6.3.1 关联矩阵210
6.3.2 有向图的邻接矩阵211
6.3.3 有向图的可达矩阵 212
6.4 欧拉图213
6.5 哈密顿图215
6.6 二部图218
6.6.1 二部图及判别定理218
6.6.2 完备匹配219
6.7 平面图221
6.7.1 平面图及其判定定理221
6.7.2 平面图的对偶图226
6.8 带权图228
习题229
第7章 树及其应用237
7.1 概述237
7.1.1 树的定义及相关术语237
7.1.2 树的性质239
7.2 生成树240
7.3 最小生成树243
7.4 树的遍历246
7.5 二叉树248
7.5.1 二叉树的性质248
7.5.2 二叉搜索树249
7.5.3 哈夫曼树250
7.6 决策树252
7.6.1 决策树的定义252
7.6.2 最短时间排序253
7.7 树的同构254
7.8 博弈树258
7.8.1 博弈树的概念258
7.8.2 极大极小分析法258
习题260
第8章 代数系统264
8.1 二元运算及其性质264
8.1.1 定义和表示 264
8.1.2 二元运算的性质 266
8.2 代数系统268
8.2.1 定义和实例268
8.2.2 子代数系统270
8.2.3 代数系统的同态与同构270
8.3 半群与独异点271
8.3.1 定义与性质271
8.3.2 子系统与直积273
8.4 群273
8.4.1 群的定义 273
8.4.2 群的性质 275
8.4.3 子群的定义 278
8.4.4 特殊的群279
8.4.5 陪集与拉格朗日定理282
8.4.6 正规子群与商群283
8.4.7 群的同态与同构实例286
8.5 环与域288
8.5.1 环288
8.5.2 域289
8.6 格与布尔代数290
8.6.1 格290
8.6.2 布尔代数295
8.7 组合电路297
习题299
第9章 自动机、文法和语言306
9.1 串和语言306
9.2 形式文法307
9.3 有限状态机310
9.4 有限状态自动机312
9.5 不确定有限状态自动机315
9.6 语言和自动机之间的关系318
习题319
第10章 初等数论322
10.1 素数322
10.2 最大公约数与最小公倍数323
10.3 同余326
10.4 一次同余方程和中国剩余定理328
10.4.1 一次同余方程328
10.4.2 中国剩余定理329
10.5 欧拉定理和费马小定理330
10.6 数论在密码学中的应用331
10.6.1 公钥密码学331
10.6.2 rsa密码332
习题333
附录 历史注记335
习题答案348
参考文献370