离散数学

本书针对离散数学领域的关键问题，通过大量实例深入浅出地介绍数理逻辑、集合论、图论、代数结构和布尔代数、组合数学理论和算法等与计算机科学密切相关的主题，既注重各部分内容之间的紧密联系，又深入探讨各部分内容的概念、理论、算法和实际应用。本书叙述严谨，推理详尽。各章配有大量的习题，可帮助读者迅速掌握有关知识。本书内容丰富、结构清晰、通俗易懂、注重实用，既适合作为计算机和相关专业"离散数学"课程的教材，也可作为工程技术人员的参考书。

前言
第1章命题逻辑1
1.1引言1
1.2命题与命题联结词1
1.2.1命题的概念1
1.2.2命题标识符和命题分类3
1.2.3命题联结词3
1.3翻译、命题公式和真值表7
1.3.1翻译7
1.3.2命题公式9
1.3.3真值情况和真值表10
1.4永真式、永假式和等价关系12
1.5等价式和蕴涵式14
1.5.1等价公式14
1.5.2等价定律公式14
1.5.3子公式15
1.5.4证明两个公式等价的方法16
1.5.5蕴涵式19
1.5.6永真蕴涵关系的判断20
1.6其他联结词22
1.6.1其他联结词的定义22
1.6.2与非联结词↑的性质23
1.6.3或非联结词↓的性质23
1.6.4异或联结词的性质24
1.6.5小联结词组25
1.7对偶与范式26
1.7.1对偶27
1.7.2范式29
1.7.3主析取范式31
1.7.4主合取范式35
1.7.5主范式的应用37
1.8命题演算的推理理论39
1.8.1推理的基本概念39
1.8.2判断有效结论的方法和规则41
本章习题48
第2章谓词逻辑53
2.1谓词的基本概念53
2.2个体、谓词及表达式54
2.3命题函数57
2.4量词59
2.5谓词公式与翻译62
2.5.1谓词公式62
2.5.2谓词逻辑的翻译63
2.6变元的约束65
2.7谓词公式的永真式、永假式、等价式和蕴涵式68
2.7.1判定方法和基本公式69
2.7.2谓词等价式和蕴涵式70
2.7.3谓词公式的范式72
2.7.4多个量词的使用74
2.8谓词演算的推理理论76
2.8.14个与量词有关的推理规则76
2.8.2谓词逻辑中推理的论证78
2.8.3演算中常见的错误83
本章习题84
第3章集合及其运算86
3.1集合的概念与表示86
3.1.1集合的概念86
3.1.2集合的表示87
3.1.3集合的相等或包含关系88
3.1.4集合的基数90
3.2集合的运算90
3.3基本的集合运算律93
3.4包含排斥原理99
本章习题103
第4章二元关系105
4.1序偶和笛卡儿乘积105
4.2关系及其表示108
4.3复合关系和逆关系112
4.4关系的性质118
4.5关系的闭包124
4.6等价关系132
4.7序关系135
本章习题139
第5章函数141
5.1函数的概念141
5.2函数的类型143
5.3复合函数147
5.4逆函数149
本章习题153
第6章代数结构155
6.1代数系统的一般概念155
6.2代数系统的运算性质157
6.3代数系统的同态和同构164
6.4半群和独异点168
6.5子半群和子独异点172
6.6群和子群173
6.7交换群和循环群181
6.8子群的陪集及拉格朗日定理184
6.9置换群188
6.10环和域190
本章习题196
第7章格和布尔代数199
7.1格的基本概念199
7.2格的基本性质202
7.3几种特殊的格207
7.4有界格和有补格212
7.5布尔代数214
本章习题216
第8章图论219
8.1图的基本定义及相关术语219
8.1.1图的概念219
8.1.2图的边点之间的关系221
8.1.3图的分类222
8.2结点的度数及其计算224
8.3子图、补图和图的同构227
8.3.1子图的概念227
8.3.2补图的概念229
8.3.3图的同构概念230
8.4通路、回路和连通性232
8.4.1通路和回路的概念232
8.4.2简单有向图的连通性235
8.4.3无向图的连通性238
8.5图的矩阵表示241
8.5.1无向图与有向图的关联矩阵241
8.5.2图的邻接矩阵242
8.5.3有向图的可达矩阵244
8.6欧拉图与哈密顿图245
8.6.1欧拉图245
8.6.2哈密顿图251
8.7路径和关键路径257
8.7.1路径的概念257
8.7.2路径在实际中的应用259
8.7.3欧拉图的应用——中国邮路问题259
8.7.4哈密顿回路和货郎担问题260
8.8平面图262
8.8.1平面图的概念262
8.8.2平面图的面263
8.8.3平面图的判定264
8.9对偶与着色269
8.9.1对偶的基本概念269
8.9.2平面图的对偶图的做法269
8.9.3对偶图的性质270
8.9.4图的着色271
8.9.5地图的着色与平面图的点着色272
本章习题273
第9章树277
9.1无向树及其性质277
9.1.1树的基本概念277
9.1.2无向树的性质277
9.2生成树和小生成树280
9.3有向树、根树和二叉树285
9.4树的遍历289
9.5很优树与Huffman算法290
9.6很好前缀码291
本章习题293
第10章技术方法和分类原理295
10.1基本原理295
10.1.1乘法原理295
10.1.2加法原理296
10.2排列与组合297
10.3可重复的排列与组合301
10.4鸽巢原理303
本章习题306
附录A模拟试卷1308
附录B模拟试卷2311
参考文献313