广工离散数学复习纲要

复习方法：1针对精简的PPT复习(涵盖了全部的教学和考试内容)2作业（认真把做过的作业温习一遍，做到真正弄懂）3结合本复习大纲有针对性的复习，特别是大纲中文字加粗部分的内容。复习大纲：1第一章1.1与集合相关的概念和特殊集合：集合的定义、集合的表示、属于和不属于、子集、真子集、包含和真包含、幂集、空集、全集、基数、有限集、无限集等；1.2与集合运算相关的概念和定理：集合的交、并、差、补和对称差等五种运算的定义及相关定理。1.3代表性习题：7,13,24,292第二章2.1容斥原理和鸽笼原理的基本概念及正确使用。2.2代表性习题：18,193第三章3.1命题的概念、表示、分类、5种基本联接词的定义与使用、命题的正确符号化。3.2命题变元、命题公式的概念及公式的正确翻译。3.3等价关系及蕴含关系的概念、常用的等价关系以及蕴涵关系、等价关系和蕴涵关系之间的关系。3.4文字、短语、子句、析取范式、合取范式、极小项、极大项、主析取范式、主合取范式的概念。3.5求范式、主范式的方法、公式类型与主范式之间的关系,主析取和主合取范式之间的转换。3.6命题演算的推理方法——真值表技术、直接证明方法（规则P、规则T、规则CP），间接证明方法（反证法）。（PPT上第五章）3.7代表性习题：3,7,11,18,4第四章4.1谓词、量词、个体域和个体的概念；4.2原子谓词公式的概念，谓词演算的合式公式的概念，谓词公式的翻译；4.3自由变元，约束变元，辖域的概念，约束变元的改名规则和自由变元的代入规则；4.4谓词公式分为三类：逻辑有效公式、矛盾公式和可满足公式；4.5谓词演算的永真公式、等价关系的概念，常用的谓词演算的等价关系；4.6谓词逻辑的推理理论——直接证明方法和间接证明方法，用于消去量词的全称特指规则和存在特指规则，用于添加量词的全称推广规则和存在推广规则及应用。（PPT上第五章）4.7代表性习题：7,10,16,195第六章5.1序偶和笛卡儿积的概念5.2二元关系的概念和表示（特别是关系图和关系矩阵）5.3关系的交、并、补、差运算、复合运算和逆运算5.4关系性质的定义、关系性质的判定、关系性质的证明；5.5关系的自反、对称、和传递闭包的概念及计算。5.6代表性习题：3,17,19,216第七章6.1等价关系的概念及证明、等价类和商集的计算；6.2集合划分的定义、求给定集合的划分；6.3等价关系与集合划分的关系；6.4偏序关系、拟序关系、全序关系和良序关系的定义，它们之间的异同；6.5哈斯图的画法；6.6八个特殊元的定义和基本性质。6.7代表性习题：5,11,14,187第八章7.1函数的概念。注意函数与关系的区别和联系；7.2单射、满射和双射函数的概念，数学描述形式；7.3函数的复合运算，逆运算及运算性质。7.4代表性习题：4，88第九章8.1图的概念：图的定义、图的表示、图的操作、邻接点与邻接边、图的分类等。8.2图的基本性质：结点的度数、图的基本定理（握手定理）、完全图、补图、子图、真子图、生成子图、导出子图等。8.3通路与回路：通路与回路、简单（基本）通路与简单（基本）回路、通路与回路长度、结点间的短程线和距离、可达与可达性矩阵。8.4图的连通性：无向连通图与连通分支、强（单向、弱）连通图与强（单向、弱）分图、8.5利用邻接矩阵和可达性矩阵判断图的通路（回路）条数以及连通性等（定理9.3.1和定理9.3.4）。8.6代表性习题：5，24,26，279第十章9.1树的概念：树、森林、根树、根、叶、分支点、生成树、最小生成树等。9.2树的基本性质：m=n-1等。9.3与根树相关的概念：有向树、根树、根、叶、内点、分支点、层数、高、有序树、祖先与后代、父亲与儿子、k元树、k元完全树、k元有序树、k元有序完全树、子树、根树的遍历、最优树。9.4树的算法：破圈法、避圈法、广度优先搜索算法、Kruskal算法、Prim算法、哈夫曼算法、二元树的先(中、后)根次序遍历算法。9.5代表性习题：10,11,17,1910第十一章10.1基本概念：欧拉通路、欧拉回路、欧拉图、哈密顿通路、哈密顿回路、哈密顿图、偶图、匹配、平面图等；10.2判定方法：比如欧拉图和偶图都有简单的方法；10.2.1定理11.2.1，推论11.2.1，推论11.2.210.2.2定理11.3.1，推论11.3.1，定理11.3.2，定理11.3.310.2.3定理11.4.110.2.4定理11.5.3,推论11.5.310.3在哈密顿图、平面图、偶图中都分别有定理仅是必要条件，注意，此必要条件正方面的叙述无法用来判断一个图是否是哈密顿图、平面图，此时该定理是用处不大，但必要条件的等价逆叙述却非常的重要，用此逆叙述可以判断一个图不是哈密尔图、是非平面图等；10.4代表性习题：1,8,9,16,21,2211第十二章11.1代数运算的定义、代数运算的封闭性、代数系统的概念以及子代数的概念。11.2二元运算律，具体包含结合律、交换律、吸收律、分配律、幂等律以及可消去律。11.3代数系统中的特殊元素，有幺元（单位元）、可逆元、零元、可消去元、幂等元，以及特殊元素的一些基本性质。11.4代表性习题：3,412第十三章12.1半群与含幺半群的定义、元素幂的定义以及性质、循环半群与循环含幺半群的定义与性质。12.2群的定义与性质、元素的周期与性质、子群的定义、子群的判别定理12.3交换群和循环群的定义及性质12.4陪集的概念及性质、拉格朗日定理及其推论。12.5代表性习题：4,16