离散数学复习大纲.docVIP

2013－2014学年度离散数学考试复习大纲 第四部分 图论总结 第14章 一、图及其基本概念 图的定义（边集、结点集） 图的表示 图的阶、顶点数及边数 顶点相邻、边相邻及边与顶点的关联 结点的度 简单图 完全图与正则图 通路及回路 图的连通性 （1）无向图的连通性：点割集与边割集，边连通度与点连通度 （2）有向图的连通性：强连通、单向连通、弱连通 10、图的矩阵表示 （1）有向图的邻接矩阵（图14.16通路与回路的计算） （2）无向图的关联矩阵 二、图的基本性质 握手定理及推论 握手定理及推论的应用（例14.2） 第15章 三、几种特殊的图 1、欧拉图 定义、判定（充要条件）及寻找欧拉通路、欧拉回路。 2、哈密顿图 定义、判定（必要条件、充分条件）；求解哈密顿通路、哈密顿回路；哈密图的应用（例15.4）。 3、二部图 定义、判定、互补结点子集、二部图是哈密顿图的条件（例15.3） 4、完全图 定义、判定及结点与边的关系 第16章 5、树 定义、性质、判定及结点与边的关系 6、生成树与最小生成树（例16.3） 根树 四、教材作业 1、P292页- P293页 8题、20题、29题、44题、45题 2、P306 9题、13题、14题 3、P318页- P319页 2题、25题、26题 第三部分 代数结构总结 第9章 一、运算 运算的定义 运算的封闭性 二元运算的特异元素 二元运算的性质 二、代数系统 1、代数系统的定义 2、代数系统的同态与同构 第10章 三、群 1、半群、独异点 2、群的定义、判定及证明（找出例10.1这些特殊代数系统的特异元素，及判断理由） 3、交换群 4、群的幂运算及元素的阶（理解定义后的例子，会求解） 4、子群与陪集 5、利用子群、陪集进行群分解 6、拉格朗日定理 7、群的性质 第11章 四、格 1、偏序集的定义 2、用哈斯图表示偏序集 3、偏序集中几特殊元素 4、格的定义、性质、判定及满足的算律 5、偏序集与格的关系 6、利用哈斯图判断一个偏序集是否为格 五、几种特殊的格 1、分配格及判断 2、有补格及判断 3、有补分配格判断 4、布尔格及判定（利用五角格与钻石格判断） 例11.1、例11.2、例11.7、例11.8 六、布尔代数的性质 七、教材作业 1、P178页-P179页 7题、9题 2、P202页-P203页 8题、9题、23题 3、P218页 1题、2题、9题 第二部分 集合论总结 第6章 一、集合 1、集合及集合的表示方法：列举法与描述法 2、集合的基数 3、集合的子集及幂集 二、集合间的关系 1、集合间的包含关系 2、集合间的相等关系 3、集合间的真包含关系 三、集合的运算 1、集合的并、交 2、集合的绝对补与相对补运算 3、集合的对称差运算 四、有穷集合的计数 1、用文氏图解决有穷集的计数 2、用包含排斥原理解决穷集的计数 例6.1 、例6.4 第7章 五、有序n元组与笛卡尔积 1、有序n元组与笛卡尔积 2、序偶 六、二元关系（简称为关系） 1、关系的定义 2、关系的定义域及值域 3、集合A上的几种特殊关系：恒等关系、全域关系、空关系 4、关系的表示方法（利用关系的表示判断关系的性质） （1）集合表示法 （2）图解表示法 （3）矩阵表示法 七、关系的性质 1、集合A上关系的五种性质 2、集合A上关系性质的判断 八、关系的运算 1、逆关系 2、关系的复合 九、集合A上的几种特殊关系 1、等价关系及性质 2\、等价关系、等价类（用关系图表示） 3、商集与划分 4、偏序关系及其性质 5、用哈斯图表示偏序关系 6、偏序集与格的关系 例7.4、例7.6、例7.11、例7.12、例7.15 、例7.17、例7.19、例7.21 第8章 十、函数的概念 1、函数的定义 2、函数的定义域及值域 十一、几种特殊的函数 1、单射 2、满射 3、双射 十二、函数的运算 1、求复合函数 2、求逆函数 例8.1、例8.5、例8.8 十三、教材作业 1、P96-100页 8题、9题、12（3）、21题 2、P130-133页 13题、16题、22题、26题、36题、40题 3、P160-163页 5题、19题 第一部分 数理逻辑总结 第1章 一、命题 1、命题联结词 2、命题符号化 二、命题公式 1、命题公式的类型及判断 2、命题公式的成真赋值与成假赋值 例1.3、例1.8 第2章 一、等值式 1、基本等值式 2、等值演算 3、用等值演算判断公式类型 4、用等值演算判断公式是否等值 二、析取范式与合取范式 1、主析取范式 2、主合取范式 3、用主析取范式判断公式类型 4、用主析取范式判断公式是否等值 例2.1、例2.5、例2.10 第3章