离散数学复习大纲.ppt

离散数学期末复****大纲命题逻辑1、命题(概念) 2、命题符号化(联结词)3、命题公式真值4、公式类型(可满足式、永真式、永假式)5、等值演算( 证明A??B)(可通过真值表法验证)6、主析取(合取)范式, 成真(成假)赋值(真值表法、等值演算法)7、推理证明(11个推理规则)一阶逻辑1、一阶逻辑下命题符号化(个体域、联结词、量词、特性谓词)2、一阶逻辑公式真值(存在量词、全称量词)3、判断公式类型(可满足式,永真,永假)4、求谓词公式的前束范式(一阶逻辑等值式的应用)集合1、集合的运算(并、交、补、对称差)、幂集、子集、文氏图2、集合等式(包含式)的证明(公式的应用)二元关系和函数1、有序对、笛卡儿积2、二元关系的表示方法(集合、关系矩阵、关系图)3、关系的运算(合成、逆)、关系的幂运算4、关系的闭包(自反、对称、传递) 5、关系的性质(自反、反自反、对称、反对称、传递)(分别通过定义、关系图、关系矩阵判断)6、等价关系(定义、证明、等价类、商集、划分)7、偏序关系(定义、证明、哈斯图、特殊元素)8、函数的性质的判断(单射、满射、双射)9、函数的运算(逆、合成)代数系统1、代数系统的概念(二元运算、子代数、封闭性)2、二元运算的性质(结合律、幂等律、交换律)3、代数系统的特殊元素判断(幺元、零元、逆元)4、半群、含幺半群(独异点)的判断5、群的证明(四个性质:封闭性、结合性、存在幺元、每个元素存在逆元)、相关定理6、Klein四元群、阿贝尔群(可交换群)7、群中元素的阶、循环群(<z6, ?>)的生成元图1、顶点的度、握手定理、度序列2、简单图、完全图(Kn)、子图(生成子图)、补图、同构3、连通图(强连通图判定定理)、连通分支、点割集、边割集4、关联矩阵(性质)、邻接矩阵、可达矩阵5、二部图(判定条件)、完全二部图(Kn,m)6、欧拉图的判定(判定条件)7、哈密尔顿图(判定条件(必要、充分))8、平面图(面数)、握手定理、欧拉公式9、树的概念特别说明:(1)大纲中列出的内容是主要概念, 在大纲中未出现的也可能会少量涉及到; (2)大纲中红色字体表示重点、大题(综合题)的出题范围; (3) 考试只允许带一张手写A4纸张(可双面写,不许复印、打印)