离散数学
作者：眭碧霞主编
出版时间： 2004年版
丛编项： 21世尼高职高专计算机科学与应用专业系列教材
内容简介
本书是教育部教育科学“十五”国家规划课题研究成果，是本书作者在多年教授离散数学所获得的经验基础上编写的，其目的是为学生提供准确而可读的教材，使离散数学的概念和技术得以清晰地介绍和演示。离散数学作为计算机科学基础理论的核心课程，其使用面积较广。本书主要介绍数理逻辑和集合论，并从集合论入手，依次介绍关系、代数、系统、图论和数理逻辑。回避先从数理逻辑开始，用逻辑联结词来处理内容。通过学习本书，学生能够达到以下目标：（1）对数理逻辑与集合论的基本概念有较深入全面的了解；（2）系统地掌握命题演算、谓词演算及朴素集合论的经典内容；（3）学会形式化演绎推理和定理证明的基本方法；（4）强化抽象思维能力、逻辑推理能力和缜密概括能力的培养，进而提高分析问题、解决问题的能力；（5）为计算机专业后续课程的学习和科研工作的参与打下坚实的基础。本书的主要特色是适用面广，考虑到教学规律和学生的认知过程，向学生们展示离散数学的实用性。为非数学专业，特别是计算机科学专业的学生提供一切必需的数学基础。并且对数学专业的学生理解离散数学及其应用也是一本不错的参考书。本书可供应用型院校的计算机科学及相关专业的学生使用。
目录
第0章?基础知识1
0.1?集合及子集1
0.1.1?集合及其表示1
0.1.2?子集2
0.1.3?幂集3
0.2?集合上的运算4
0.2.1?集合的并4
0.2.2?集合的交4
0.2.3?集合的差5
0.2.4?集合的对称差6
0.3?多重集合9
0.4?序列10
0.4.1?序列和数组10
0.4.2?特征函数12
0.4.3?集合及子集的计算机表示13
0.4.4?串和正则表达式14
0.5?整数的分解16
0.5.1?整除及素数16
0.5.2?最大公因数17
0.5.3?最小公倍数20
0.5.4?某些算法的伪代码21
0.6?矩阵22
0.6.1?矩阵的定义22
0.6.2?矩阵的运算23
0.6.3?布尔矩阵运算26
0.7?算法和算法语言28
0.7.1?算法简介28
0.7.2?算法概念29
0.7.3?算法语言31
0.7.4?递归算法34
0.8?数学结构36
0.9?习题39
本章小结45
第1章?逻辑46
A命题逻辑46
1.1?命题和逻辑运算46
1.1.1?命题46
1.1.2?逻辑联结词和复合命题47
1.1.3?逻辑和位运算51
1.2?合式公式和语义51
1.2.1?语法52
1.2.2?语义52
1.3?逻辑等价53
1.4?真值函数和范式57
1.4.1?真值函数和合式公式57
1.4.2?析取范式59
1.4.3?合取范式60
1.4.4?用等价替换方法构造主范式61
1.5?联结词的完备集63
1.5.1?联结词的完备集63
1.5.2?一些计算机应用64
1.6?形式推理系统66
1.6.1?形式推演规则66
1.6.2?形式可推演性的一些性质69
1.6.3?形式推演实例73
B一阶逻辑76
1.7?谓词和量词76
1.7.1?谓词76
1.7.2?量词77
1.7.3?Lewis?Carroll?例79
1.8?合式公式和语义80
1.8.1?合式公式80
1.8.2?语义82
1.8.3?自然语言的形式化83
1.9?逻辑等价和蕴涵85
1.10?范式90
1.11?一阶逻辑的形式推理系统93
1.12?数学归纳法97
1.12.1?归纳推理和演绎推理97
1.12.2?数学归纳法99
1.12.3?数学归纳法在证明不等式中的应用102
1.12.4?数学归纳法在其它方面的应用103
1.13?习题106
本章小结111
第2章?计数114
2.1?计数的两个基本原理114
2.1.1?加法原理114
2.1.2?乘法原理115
2.2?排列与组合115
2.2.1?排列115
2.2.2?组合119
2.2.3?二项式定理121
2.2.4?多项式定理124
2.3?鸽笼原理124
2.3.1?鸽笼原理的简单形式125
2.3.2?鸽笼原理的一般形式126
2.3.3?Ramsey数128
2.4?容斥原理130
2.4.1?引130
2.4.2?容斥原理131
2.4.3?容斥原理的应用135
2.5?概率初步140
2.5.1?引140
2.5.2?样本空间140
2.5.3?事件141
2.5.4?对事件赋予概率142
2.5.5?可望相等结果143
2.6?递归关系145
2.6.1?递归关系模型146
2.6.2?递归关系的基本解法151
2.7?习题159
本章小结164
第3章?关系和有向图166
3.1?集合的积166
3.1.1?有序对166
3.1.2?集合的笛卡儿乘积166
3.2?关系和有向图168
3.2.1?二元关系的定义168
3.2.2?关系矩阵171
3.2.3?关系图172
3.2.4?n元关系及其应用173
3.3?复合关系和逆关系175
3.3.1?复合关系175
3.3.2?逆关系178
3.4?关系图中的通路179
3.5?关系的性质183
3.6?等价关系和集合的划分187
3.6.1?等价关系187
3.6.2?集合的划分190
3.6.3?有限集合上等价关系的计数191
3.7?关系的闭包193
3.7.1?关系闭包的基本概念193
3.7.2?求传递闭包的Warshall?算法196
3.8?习题200
本章小结204
第4章?函数206
4.1?函数的基本概念206
4.1.1?函数206
4.1.2?偏函数208
4.2?特殊函数209
4.3?函数的运算213
4.4?基数216
4.4.1?基数216
4.4.2?可数集与不可数集218
4.4.3?基数的比较220
4.5?用于计算机科学的函数221
4.5.1?一般函数221
4.5.2?散列函数223
4.6?函数的增长224
4.6.1?大O224
4.6.2?大Θ225
4.6.3?确定函数Θ类的规则226
4.7?置换226
4.7.1?置换的基本概念227
4.7.2?置换的表示227
4.7.3?置换的积227
4.7.4?循环228
4.8?习题231
本章小结234
第5章?群、环和域236
5.1?预备知识236
5.1.1?一些基本运算236
5.1.2?特殊元素240
5.1.3?同态与同构244
5.2?半群和独异点246
5.2.1?半群246
5.2.2
