本书详细介绍了离散数学的相关理论、定理、算法等。

离散数学及其应用 第2版
徐凤生◎主编 巩建闽 宁玉富◎副主编

精品课程网站　http://211.64.47.133/web/jingpin/
本书是山东省省级精品课程“离散数学”的主讲教材，是全国教育科学“十一五”国家课题“我国高校应用型人才培养模式研究”重点子课题“应用型本科院校计算机专业课程体系构建研究”的研究成果。
离散数学是研究离散量的结构及其相互关系的数学学科，是计算机及相关专业的核心和骨干课程。 本书是作者结合多年的教学实践编写而成的，按“精、广、新”的要求组织教学内容，并本着实用的原则增加了上机实验内容等，确保了计算机专业学生能够获得应有的数学知识和解决问题的能力。
本书可作为高等院校计算机及相关专业离散数学课程的教材，也可供相关科技人员学习参考。

本书特点
内容涉猎面广，可满足不同层面学生的需求。
在内容安排上，突出由浅入深、循序渐进、通俗易懂的特点，讲述全面翔实，阐述简洁明了。
重点突出解题思路，注重培养学生的数学思维能力以及分析、解决问题的能力。
为了体现与前导课和后继课的联系，激发学生的学习兴趣，书中融入了一些编程的思想，并加进了上机实验内容。
为教师配有电子教案、习题答案和上机实验参考源程序，可登录华章网站（www.hzbook.com）下载。

目前，在计算机科学的研究和应用中遇到的许多重大问题，不仅是技术问题，而且是理论问题，至少是技术方面的理论问题。因此，无论学生今后从事计算机的理论研究，还是应用开发或者技术管理工作，都必须打下坚实的数学理论基础，以适应学科迅速发展和知识更新的需要，而离散数学是必备的数学基础。
离散数学是研究离散量的结构及其相互关系的数学学科。它是计算机及相关专业的核心和骨干课程，为数据结构、编译原理、数据库、算法分析和人工智能等课程提供必要的数学基础。
离散数学的特点是概念多、理论性强和高度抽象，学生学习起来往往比较困难。针对这种情况，我们在参考各种离散数学教材的基础上，结合作者多年的教学实践，编写了这本普通高等院校计算机及其相关专业本科生适用的离散数学教材。
本书按“精、广、新”的要求组织教学内容，并本着实用的原则增加了上机实验内容等，确保了计算机专业学生能够获得应有的数学知识和解决问题的能力。全书由六部分构成。第一部分数理逻辑（第1章和第2章），内容包括命题逻辑和谓词逻辑；第二部分集合论（第3章、第4章和第5章），内容包括集合的基本知识、排列与组合、递推关系、集合论在命题逻辑中的应用、关系、函数、经典集合的扩展等；第三部分数论（第6章和第7章），内容包括整除和同余；第四部分代数系统（第8章和第9章），内容包括代数系统的基本概念及性质、半群和群、环与域、布尔代数等；第五部分图论（第10章），内容包括图的基本概念及矩阵表示、几类重要的图、最短路径、关键路径等；第六部分计算机科学中的应用（第11章和第12章），内容包括形式语言与自动机、纠错码等。
本书由徐凤生任主编，巩建闽、宁玉富任副主编，参与编写工作的人员还包括郭长友、李天志、刘建军、潘东静、戎丽霞、王付山、张建臣、李海军。最后，全书由徐凤生统稿并定稿。
本书具有以下特色：
（1）内容涉猎面广，可满足不同层面学生的需求。
（2）讲述全面而翔实，阐述简洁而明了。
（3）重点突出解题思路，注重培养学生的数学思维能力和分析、解决问题的能力。
（4）为了体现与前导课和后继课的联系，激发学生的学习兴趣，书中融入了一些编程的思想，并加进了上机实验内容。
（5）例题丰富，题型多样，便于学生自学。
（6）通过典型例题的分析，使学生对所学知识的掌握更加系统化和条理化，更易于对所学知识融会贯通和举一反三。
（7）本书配有电子教案、习题答案和上机实验参考源程序，有需要的教师可与出版社直接联系或发送邮件至xfs@dzu.edu.cn与作者联系。
本教材的出版得到了德州学院教材出版基金的资助。在本书编写过程中，得到了德州学院计算机系一些老师的帮助，谨对他们表示衷心的感谢。另外，在编写中参阅了许多离散数学教材和相关资料，在此也向作者表示感谢。最后，还要特别感谢机械工业出版社华章分社的大力支持，使得本书得以顺利出版。
限于作者水平，书中不当和疏漏之处在所难免，敬请读者不吝指正。


编者

出版者的话
前言
教学建议
第1章　命题逻辑 1
1.1　命题与联结词 1
1.1.1　命题的基本概念 1
1.1.2　命题分类及命题标识符 2
1.1.3　命题联结词 2
1.2　命题公式、翻译与真值表 4
1.2.1　命题公式 4
1.2.2　命题的符号化 4
1.2.3　真值表 5
1.3　公式分类与等价式 6
1.3.1　公式分类 6
1.3.2　等价公式（等值演算） 6
1.3.3　基本等价式——命题定律 7
1.3.4　代入规则和替换规则 7
1.3.5　证明两个命题公式等价的方法 8
1.4　对偶式与蕴涵式 9
1.4.1　对偶式 9
1.4.2　蕴涵式 10
1.4.3　蕴涵式的证明方法 11
1.5　联结词的扩充与全功能联结词组 11
1.5.1　联结词的扩充 11
1.5.2　与非、或非、异或的性质 12
1.5.3　全功能联结词组 13
1.6　公式标准型——范式 13
1.6.1　简单合取式与简单析取式 13
1.6.2　析取范式与合取范式 13
1.6.3　范式的应用 14
1.7　公式主范式 15
1.7.1　主析取范式 15
1.7.2　主合取范式 17
1.7.3　主范式的应用 19
1.8　命题逻辑的推理理论 20
1.8.1　推理规则 20
1.8.2　推理定律 21
1.8.3　判断有效结论的常用方法 21
1.9　典型例题分析 24
1.10　上机实验 28
习题 29
第2章　谓词逻辑 33
2.1　基本概念 33
2.1.1　个体、谓词和命题的谓词形式 33
2.1.2　量词 34
2.2　谓词公式与翻译 35
2.2.1　谓词公式 35
2.2.2　谓词逻辑的翻译 36
2.3　自由变元和约束变元 36
2.4　谓词公式的解释与分类 37
2.4.1　谓词公式的解释 37
2.4.2　谓词公式的分类 38
2.5　谓词演算的等价式与蕴涵式 39
2.5.1　等价式 39
2.5.2　蕴涵式 41
2.6　谓词演算中的公式范式 42
2.6.1　前束范式 42
2.6.2　斯柯林范式 43
2.7　谓词演算的推理理论 43
2.8　典型例题分析 47
习题 49
第3章　集合 53
3.1　集合的概念与表示法 53
3.1.1　集合的概念 53
3.1.2　集合的表示法 53
3.1.3　集合的包含与相等 54
3.1.4　空集、集族、幂集和全集 55
3.1.5　有限幂集元素的编码表示 56
3.2　集合的运算与性质 56
3.2.1　集合的交、并和补 56
3.2.2　集合的对称差 58
3.2.3　集合的广义并和广义交 58
3.2.4　集合的文氏图 59
3.3　集合的划分与覆盖 59
3.4　排列与组合 61
3.4.1　加法原理与乘法原理 61
3.4.2　排列 61
3.4.3　组合 62
3.4.4　排列与组合的生成 62
3.5　归纳原理 63
3.5.1　结构归纳原理 63
3.5.2　数学归纳原理 64
3.6　容斥原理和抽屉原理 65
3.6.1　容斥原理 65
3.6.2　抽屉原理（鸽巢原理） 66
3.7　递推关系 67
3.7.1　递推关系的概念 67
3.7.2　递推关系的求解 67
3.8　集合论在命题逻辑中的应用 69
3.8.1　命题逻辑中的集合表示 69
3.8.2　应用举例 71
3.9　典型例题分析 71
3.10　上机实验 73
习题 74
第4章　关系 77
4.1　序偶与笛卡儿积 77
4.1.1　序偶及有序n元组 77
4.1.2　笛卡儿积 77
4.2　关系及其表示 79
4.2.1　关系 79
4.2.2　关系矩阵与关系图 81
4.3　复合关系及逆关系 81
4.4　关系的性质 83
4.5　关系的闭包 85
4.6　等价关系和等价类 90
4.7　相容关系 92
4.8　偏序关系 94
4.9　典型例题分析 97
4.10　上机实验 99
习题 99
第5章　函数 102
5.1　函数的概念 102
5.1.1　函数定义 102
5.1.2　函数性质 103
5.2　逆函数和复合函数 104
5.2.1　逆函数 104
5.2.2　函数的复合 104
5.2.3　几种特殊的函数 107
5.3　集合的基数 107
5.3.1　基数的概念 108
5.3.2　可数集与不可数集 108
5.3.3　基数的比较 109
5.4　经典集合的扩展 110
5.4.1　Fuzzy集 110
5.4.2　Vague集 111
5.4.3　Rough集 112
5.5　典型例题分析 113
5.6　上机实验 115
习题 115
第6章　整除 117
6.1　因数和倍数 117
6.2　素数和合数 117
6.3　带余除法与辗转相除法 118
6.4　最大公因数和最小公倍数 119
6.5　算术基本定理 121
6.6　典型例题分析 122
6.7　上机实验 124
习题 124
第7章　同余 125
7.1　同余及其性质 125
7.2　剩余类和剩余系 127
7.3　欧拉定理与威尔逊定理 128
7.4　一次同余式 130
7.5　一次同余式组 132
7.6　数论在密码学中的应用 133
7.6.1　仿射加密法 134
7.6.2　RSA系统 135
7.6.3　MH系统 136
7.7　典型例题分析 137
7.8　上机实验 138
习题 138
第8章　代数系统 140
8.1　代数系统的定义 140
8.2　代数系统的性质 141
8.3　代数系统的同态与同构 145
8.4　同余关系 147
8.5　商代数与积代数 148
8.6　半群和独异点 149
8.6.1　半群 149
8.6.2　独异点 150
8.7　群与子群 151
8.7.1　群 151
8.7.2　元素的阶 152
8.7.3　子群 153
8.8　循环群和置换群 154
8.8.1　循环群 154
8.8.2　置换群 156
8.9　陪集和正规子群 159
8.9.1　陪集 159
8.9.2　正规子群 161
8.10　群的同态与同构 162
8.11　环与域 164
8.11.1　环 164
8.11.2　子环与理想 166
8.11.3　域 166
8.11.4　环的同态与同构 168
8.12　典型例题分析 169
8.13　上机实验 173
习题 173
第9章　格与布尔代数 177
9.1　格的定义与性质 177
9.2　子格与格同态 179
9.3　特殊的格 180
9.4　布尔代数 181
9.5　典型例题分析 184
习题 185
第10章　图 186
10.1　图的基本概念 186
10.1.1　图 186
10.1.2　子图与补图 187
10.1.3　结点的度 188
10.1.4　图的同构 190
10.2　路、回路与连通性 191
10.3　图的矩阵表示 195
10.4　欧拉图与哈密顿图 198
10.4.1　欧拉图 198
10.4.2　哈密顿图 200
10.5　二部图与匹配 202
10.6　平面图 204
10.6.1　平面图的基本概念 204
10.6.2　欧拉公式 205
10.6.3　平面图的判定 206
10.6.4　平面图的对偶图 207
10.7　树及其应用 208
10.7.1　无向树及生成树 208
10.7.2　根树及其应用 211
10.8　着色问题 216
10.8.1　图中结点的着色 216
10.8.2　地图的着色与平面图
10.8.2　的点着色 217
10.8.3　边着色 218
10.9　最短路径和关键路径 218
10.9.1　最短路径问题 218
10.9.2　关键路径问题 220
10.10　典型例题分析 222
10.11　上机实验 225
习题 229
第11章　形式语言与自动机简介 235
11.1　语言及其表示 235
11.1.1　语言 235
11.1.2　文法 236
11.1.3　识别器 237
11.2　正规语言与有限自动机 238
11.2.1　确定的有限自动机 238
11.2.2　不确定的有限自动机 241
11.3　上下文无关语言与下推自动机 243
11.3.1　上下文无关语言 244
11.3.2　下推自动机 244
11.3.3　下推自动机与上下文
11.3.3　无关语言的关系 246
11.4　图灵机 247
11.4.1　图灵识别器 247
11.4.2　用于计算的图灵机 249
11.5　线性界限自动机 250
11.6　典型例题分析 250
11.7　上机实验 251
习题 252
第12章　纠错码简介 253
12.1　纠错码的基本概念 253
12.2　纠错码的纠错能力 255
12.3　纠错码的选择 257
12.4　群码的校正 261
12.5　典型例题分析 262
12.6　上机实验 263
习题 264
参考文献 265

计算机\离散数学