《《离散数》复习知识点.doc》由会员分享，可在线阅读，更多相关《《离散数》复习知识点.doc（3页珍藏版）》请在三一文库上搜索。
1、第1章集合及其运算考核知识点1. 集合，元素，集合的表示，全集，空集2 集合的包含、相等，子集，幕集3. 集合的并、交、补、差、对称差等运算及其运算律4容斥原理考核要求1理解集合的概念，容斥原理.2. 理解集合的包含、子集、相等和幕集等概念，熟练掌握集合的表示方法和集合的并、 交、补、差和对称差等运算，会用文氏图表示集合的各种运算.3掌握用集合运算基本规律证明集合恒等式的方法.4掌握利用容斥原理进行计数的方法.第2章关系与函数考核知识点1. 有序对和笛卡儿积2关系及其运算性质3. 二元关系的矩阵与图4. 复合关系与逆关系5. 二元关系的性质6. 等价关系与等价类7. 偏序关系、复盖集与哈斯图，
2、极大 （小）元，最大（小）元，上（下）界，最小上界，最大 下界&函数反函数复合函数单射满射和双射考核要求1. 了解有序对和笛卡儿积的概念，掌握笛卡儿积的运算.2. 理解关系的概念：包括二元关系、空关系、全关系、恒等关系.掌握关系的集合表 示、关系矩阵和关系图，掌握关系的运算.3. 掌握求复合关系和逆关系的方法.4 .理解关系的性质（自反性和反自反性、对称性和反对称性、传递性），掌握其判别方法.5. 理解等价关系和偏序关系概念，掌握等价关系、偏序关系的判定，掌握等价类、复盖集的求法和作偏序关系哈斯图的方法.知道极大（小）元，最大（小）元的概念，会求极大（小）元、最大（小）元、最小上界和最大下界.
3、6. 理解函数概念：函数（映射），函数相等，复合函数和反函数.7. 理解单射、满射和双射等概念，掌握其判别方法.第3章图的基本概念与性质考核知识点1 图的概念与表示，有向图，无向图，简单图，完全图，结点的度数，图的同构，子 图、补图2通路，通路的长度，初级通路，简单通路，回路，初级回路，简单回路3图的连通性与连通度概念、判定，点割集与割点，边割集与割边4. 图的矩阵表示、邻接矩阵、可达性矩阵及其计算5 .最短路径考核要求1. 理解图的基本概念：结点、边、有向图，无向图、简单图、完全图、结点的度数、 图的同构子图等，理解握手定理.2. 了解通路与回路的概念：简单通路、初级通路和复杂通路，简单回路
4、、初级回路和 复杂回路，会求通路和回路的长度.3. 了解无向图的连通性，会求无向图的连通分支.了解点割集、割点、边割集、割边、 点连通度、边连通度等概念.4. 了解有向图的强连通性、单向连通性、弱连通性；会判别有向图连通性的类型.5. 理解图的矩阵表示法、邻接矩阵、可达性矩阵的概念，掌握邻接矩阵、可达性矩阵 的有关计算.6. 知道最短路径的概念，会最短路径的算法.第4章几种特殊图考核知识点1. 欧拉通路（回路），欧拉图2 .哈密顿通路（回路），哈密顿图3. 平面图，欧拉公式4. 对偶图及着色考核要求1. 了解欧拉回路、欧拉图的概念及性质，掌握欧拉图的判别方法.2. 了解汉密尔顿回路、汉密尔顿图
5、的概念及性质，掌握汉密尔顿图的判别方法.3. 了解平面图的概念：平面图、面、边界、面的次数和非平面图，掌握平面图的判别 方法，掌握欧拉公式的应用.4. 理解平面图与对偶图的关系、对偶图在图着色中的作用，掌握着色算法；5. 掌握图论中常用的证明方法.第5章树及其应用考核知识点1 .树的定义及性质Kruskal 算法2. 生成树与最小生成树的概念，最小生成树的3. 根树的概念及性质4. 最优树的概念，最优树的Huffman算法，前缀码的求法考核要求1. 了解无向树、树叶、分支点、平凡树、生成树和最小生成树等概念及性质，掌握最 小生成树的Kruskal算法.2. 了解有向树、根树、有序树、最优二元（
6、叉）树等概念及性质，掌握最优树的 算法.3掌握利用最优树产生前缀码的方法.第6章命题逻辑考核知识点1. 命题与联结词（否定、析取、合取、蕴含、等价 ），真值与真值表2命题公式的解释3. 命题公式的等值式与蕴涵式，等值演算4. 析取范式、合取范式、极小 （大）项，主析取范式、主合取范式的概念与求法5命题逻辑的推理理论考核要求1理解命题联结词概念，掌握命题公式的翻译（命题符号化）及判断语句是不是命题 的方法.2. 熟练掌握求给定公式真值表的方法.3. 掌握基本等值式以及用真值表法和等值演算法判别公式类型和公式等值的方法.4. 了解析取（合取）范式概念，理解极小（大）项的概念和主析取（合取）范式概念
7、,握用基本等值式或真值表将公式化为主析取（合取）范式的方法.5. 掌握命题公式的的直接证明方法与间接证明方法.第7章谓词逻辑考核知识点1 .谓词，量词，个体词，个体域，变元2. 谓词公式的解释3. 前束范式的概念与求法4. 谓词公式的等值式与蕴涵式5. 谓词逻辑的推理理论考核要求1.理解谓词、量词、个体词、个体域、全域、原子公式、谓词公式和变元等概念.掌 握谓词公式的翻译.2 .掌握在有限个体域下消去公式的量词和求公式在给定解释下真值的方法.3. 掌握谓词演算的等值式和重言蕴含式.4. 了解前束范式的概念，会求谓词公式的前束范式的方法.Huffma n熟练掌5. 了解谓词逻辑推理的规则，掌握谓词公式的证明与推导方法.