离散数学(第2版)

"1．面向计算机类专业学生的未来发展，以知识、能力与素质的培养为主线，重构课程教学内容，注重离散数学在计算机课程体系的基础性和核心性； 2．通过对典型例题分析，突出对解题思路和解题方法的培养，提升计算机类专业学生的核心能力； 3．注重离散数学对后续课程的基础性作用； 4．借助相关知识点的产生、发展历程和应用场景，让学生全面了解离散数学在计算机科学发展的核心地位和作用。 "

本书共分12章，内容包含矩阵知识初步、排列组合与数论初步、命题逻辑、谓词逻辑、集合论基础、关系、特殊关系、图论基础、特殊图、代数系统、群论和其他代数系统。本书以训练学生的思维能力为核心，以培养计算机类专业的应用型人才为目的，将计算机数学与算法设计进行有效结合，全面提高学生的程序设计能力和应用创新能力。通过对典型的例题进行分析，培养学生分析问题和解决问题的能力。同时，对一些内容进行延伸，将计算机数学基础与后续的专业知识进行完美结合。本书可以作为数学类专业、计算机类专业的本科教材，也可以作为程序设计大赛培训的参考用书。

"张小峰，鲁东大学信息与电气工程学院副教授，担任鲁东大学ACM教练，长期从事程序设计基础、离散数学、数据结构、算法分析与设计等课程的教学工作。 "

第1章矩阵知识初步1
1.1矩阵的概念1
1.2矩阵的运算3
1.3布尔矩阵5
阅读材料6
习题111
第2章排列组合与数论初步12
2.1基本计数原则12
2.1.1加法原则12
2.1.2乘法原则13
2.2排列13
2.3组合15
2.4鸽笼原理18
2.5素数18
2.6优选公约数与最小公倍数21
阅读材料24
习题231
第3章命题逻辑33
3.1命题与命题联结词33
3.1.1命题33
3.1.2命题联结词34
3.2命题公式38
3.3命题公式的等值演算42
3.4命题联结词的完备集46
3.5范式48
3.5.1析取范式和合取范式48
3.5.2主析取范式和主合取范式49
3.5.3范式的应用53
3.6命题逻辑的推理57
3.6.1推理的基本概念57
3.6.2推理的基本方法58
习题365
第4章谓词逻辑68
4.1谓词逻辑的基本概念68
4.2谓词公式71
4.3谓词公式的等价与蕴涵74
4.4范式79
4.5谓词逻辑的蕴涵推理80
阅读材料86
习题495
第5章集合论基础98
5.1集合的概念与表示98
5.2集合之间的关系100
5.3集合的运算102
5.4序偶与笛卡儿积106
5.5容斥原理107
阅读材料111
习题5114
第6章关系116
6.1关系的定义116
6.2关系的表示118
6.3关系的运算119
6.3.1关系的集合运算119
6.3.2关系的复合运算119
6.3.3关系的幂运算125
6.3.4关系的逆运算126
6.4关系的性质127
6.4.1自反性与反自反性128
6.4.2对称性与反对称性130
6.4.3传递性133
6.5关系的闭包135
阅读材料138
习题6141
第7章特殊关系143
7.1等价关系143
7.2偏序关系148
7.3相容关系152
7.4函数154
7.4.1函数的定义154
7.4.2函数的性质155
7.4.3函数的运算156
阅读材料158
习题7159
第8章图论基础162
8.1图的基本概念162
8.1.1图162
8.1.2图的表示165
8.1.3图的同构166
8.1.4图的操作167
8.2通路与回路170
8.3图的连通性174
8.3.1无向图的连通性174
8.3.2有向图的连通性178
习题8184
第9章特殊图187
9.1欧拉图187
9.2哈密顿图191
9.3二分图194
9.3.1二分图的概念与判定194
9.3.2完备匹配197
9.4平面图203
9.4.1平面图的概念与判定方法203
9.4.2平面图的对偶图206
9.5图的着色207
9.5.1结点着色208
9.5.2边着色211
9.6树213
9.6.1树的定义213
9.6.2生成树与最小生成树216
9.7根树220
9.7.1有向树与根树220
9.7.2根树的遍历222
9.7.3哈夫曼树225
习题9228
第10章代数系统230
10.1代数运算230
10.2运算的性质与特殊元素231
10.2.1运算的性质231
10.2.2特殊元素234
10.3代数系统的同态与同构238
10.4子代数240
习题10241
第11章群论242
11.1半群242
11.2群244
11.2.1群的基本概念245
11.2.2阿贝尔群247
11.2.3群同态与群同构247
11.3元素的周期与循环群248
11.3.1元素的周期249
11.3.2循环群249
11.4子群251
11.5置换群与伯恩赛德定理254
11.6陪集与拉格朗日定理259
11.7正规子群与商群261
阅读材料265
习题11269
第12章其他代数系统270
12.1环270
12.2域272
12.3格272
12.3.1格的定义273
12.3.2格的另一种定义274
12.3.3分配格、有界格与布尔格276
12.4布尔代数276
习题12281
参考文献282