广工离散数学复习纲要_广东工业大学离散数学

广工离散数学复习纲要由刀豆文库小编整理，希望给你工作、学习、生活带来方便，猜你可能喜欢“广东工业大学离散数学”。

复习方法：2 3 针对精简的PPT复习(涵盖了全部的教学和考试内容)作业（认真把做过的作业温习一遍，做到真正弄懂）

结合本复习大纲有针对性的复习，特别是大纲中文字加粗部分的内容。

复习大纲：第一章

1.1 与集合相关的概念和特殊集合：集合的定义、集合的表示、属于和不属于、子集、真子集、包含和真包含、幂集、空集、全集、基数、有限集、无限集等；

1.2 与集合运算相关的概念和定理：集合的交、并、差、补和对称差等五种运算的定义及相关定理。

1.3 代表性习题：7, 13, 24, 29

第二章

2.1 容斥原理和鸽笼原理的基本概念及正确使用。2.2 代表性习题：18, 19

第三章

3.1 命题的概念、表示、分类、5种基本联接词的定义与使用、命题的正确符号化。3.2 命题变元、命题公式的概念及公式的正确翻译。3.3 等价关系及蕴含关系的概念、常用的等价关系以及蕴涵关系、等价关系和蕴涵关系之间的关系。

3.4 文字、短语、子句、析取范式、合取范式、极小项、极大项、主析取范式、主合取范式的概念。

3.5 求范式、主范式的方法、公式类型与主范式之间的关系, 主析取和主合取范式之间的转换。

3.6 命题演算的推理方法——真值表技术、直接证明方法（规则P、规则T、规则CP），间接证明方法（反证法）。（PPT上第五章）3.7 代表性习题：3, 7, 11, 18，第四章

4.1 谓词、量词、个体域和个体的概念；

4.2 原子谓词公式的概念，谓词演算的合式公式的概念，谓词公式的翻译；

4.3 自由变元，约束变元，辖域的概念，约束变元的改名规则和自由变元的代入规则； 4.4 谓词公式分为三类：逻辑有效公式、矛盾公式和可满足公式；

4.5 谓词演算的永真公式、等价关系的概念，常用的谓词演算的等价关系；

4.6 谓词逻辑的推理理论——直接证明方法和间接证明方法，用于消去量词的全称特指规则和存在特指规则，用于添加量词的全称推广规则和存在推广规则及应用。（PPT上第五章）

4.7 代表性习题：7, 10, 16, 19 25 第六章

5.1 序偶和笛卡儿积的概念

5.2 二元关系的概念和表示（特别是关系图和关系矩阵）5.3 关系的交、并、补、差运算、复合运算和逆运算

5.4 关系性质的定义、关系性质的判定、关系性质的证明； 5.5 关系的自反、对称、和传递闭包的概念及计算。5.6 代表性习题：3, 17,19,21

第七章

6.1 等价关系的概念及证明、等价类和商集的计算； 6.2 集合划分的定义、求给定集合的划分； 6.3 等价关系与集合划分的关系；

6.4 偏序关系、拟序关系、全序关系和良序关系的定义，它们之间的异同； 6.5 哈斯图的画法；

6.6 八个特殊元的定义和基本性质。6.7 代表性习题：5, 11,14,18

第八章

7.1 函数的概念。注意函数与关系的区别和联系； 7.2 单射、满射和双射函数的概念，数学描述形式； 7.3 函数的复合运算，逆运算及运算性质。7.4 代表性习题：4，8

第九章

8.1 图的概念：图的定义、图的表示、图的操作、邻接点与邻接边、图的分类等。8.2 图的基本性质：结点的度数、图的基本定理（握手定理）、完全图、补图、子图、真子图、生成子图、导出子图等。

8.3 通路与回路：通路与回路、简单（基本）通路与简单（基本）回路、通路与回路长度、结点间的短程线和距离、可达与可达性矩阵。

8.4 图的连通性：无向连通图与连通分支、强（单向、弱）连通图与强（单向、弱）分图、8.5 利用邻接矩阵和可达性矩阵判断图的通路（回路）条数以及连通性等（定理9.3.1和定理9.3.4）。

8.6 代表性习题：5，24, 26，27

第十章

9.1 树的概念： 树、森林、根树、根、叶、分支点、生成树、最小生成树等。9.2 树的基本性质：m = n-1等。

9.3 与根树相关的概念：有向树、根树、根、叶、内点、分支点、层数、高、有序树、祖先与后代、父亲与儿子、k元树、k元完全树、k元有序树、k元有序完全树、子树、根树的遍历、最优树。

9.4 树的算法： 破圈法、避圈法、广度优先搜索算法、Kruskal算法、Prim算法、哈夫曼算法、二元树的先(中、后)根次序遍历算法。9.5 代表性习题：10,11,17,19 610 第十一章

10.1 基本概念：欧拉通路、欧拉回路、欧拉图、哈密顿通路、哈密顿回路、哈密顿图、偶图、匹配、平面图等；

10.2 判定方法：比如欧拉图和偶图都有简单的方法；

10.2.1 定理11.2.1，推论11.2.1，推论11.2.2

10.2.2 定理11.3.1，推论11.3.1，定理11.3.2，定理11.3.3 10.2.3 定理11.4.1

10.2.4 定理11.5.3, 推论11.5.3

10.3 在哈密顿图、平面图、偶图中都分别有定理仅是必要条件，注意，此必要条件正方面的叙述无法用来判断一个图是否是哈密顿图、平面图，此时该定理是用处不大，但必要条件的等价逆叙述却非常的重要，用此逆叙述可以判断一个图不是哈密尔图、是非平面图等； 10.4 代表性习题：1, 8, 9,16,21,22 第十二章

11.1 代数运算的定义、代数运算的封闭性、代数系统的概念以及子代数的概念。

11.2 二元运算律，具体包含结合律、交换律、吸收律、分配律、幂等律以及可消去律。11.3 代数系统中的特殊元素，有幺元（单位元）、可逆元、零元、可消去元、幂等元，以及特殊元素的一些基本性质。11.4 代表性习题：3, 4 12 第十三章

12.1 半群与含幺半群的定义、元素幂的定义以及性质、循环半群与循环含幺半群的定义与性质。

12.2 群的定义与性质、元素的周期与性质、子群的定义、子群的判别定理 12.3 交换群和循环群的定义及性质

12.4 陪集的概念及性质、拉格朗日定理及其推论。12.5 代表性习题：4, 16