离散学 期末复习大纲 (07级软件+背景专业)
离散数学 期末复习大纲 （07级软件+背景专业）
命题逻辑 重点 、命题(简单命题,复合命题)及符号化(联结词) 2、公式类型(可满足,永真,永假 3、等值演算(证明A台B) 4、联结词完备集(用指定联结词表示任意公式) 5、主析(主合)取范式,成真(假)赋值 6、推理证明(推理规则)
命题逻辑 重点: 1、命题(简单命题, 复合命题)及符号化(联结词) 2、公式类型(可满足,永真,永假) 3、等值演算( 证明A B) 4、联结词完备集 ( 用指定联结词表示任意公式) 5、主析（主合）取范式, 成真(假)赋值 6、推理证明(推理规则)
一阶逻辑 重点: 1.一阶逻辑下命题符号化(个体域、联结词、量词、特性谓词) 2判断公式类型(可满足式永真,永假 3求谓词公式的前束范式(一阶逻辑等值式的应用) 阶逻辑推理证明 (重在+、∨-、彐,彐-规则的应用)
一阶逻辑 重点: 1.一阶逻辑下命题符号化(个体域、联结词、量词、特性谓词) 2.判断公式类型(可满足式,永真,永假) 3.求谓词公式的前束范式(一阶逻辑等值式的应用) 4. 一阶逻辑推理证明 (重在+、 - 、 +, - 规则的应用)
集合 重点 1、集合的运算、幂集、子集、文氏图 2、集合等式(包含式)的证明(公式的应用)
集合 重点: 1、集合的运算、幂集、子集、文氏图 2、集合等式（包含式）的证明（公式的应用）
二元关系和函数 重点: 1、有序对、笛卡儿积 2、二元关系的表示方法(集合、关系矩阵、关系图) 3、关系的运算(合成、逆、闭包、幂运算) 4、关系的性质(自反、反自反、对称、反对称、传递) 5、等价关系(证明、商集、等价类、划分) 6、偏序关系(证明、哈斯图、特殊元素) 7、函数的性质的判断(单射、满射、双射) 8、函数的运算(逆、合成)
二元关系和函数 重点: 1、有序对、笛卡儿积 2、二元关系的表示方法（集合、关系矩阵、关系图） 3、关系的运算（合成、逆、闭包、幂运算） 4、关系的性质（自反、反自反、对称、反对称、传递） 5、 等价关系（证明、商集、等价类、划分） 6、偏序关系(证明、哈斯图、特殊元素) 7、函数的性质的判断（单射、满射、双射） 8、函数的运算（逆、合成）
代数系统 重点 1、代数系统的概念(二元运算、子代数、封闭性、其它 性质(结合律、幂等律、交换律、消去律)) 2、代数系统的特殊元素判断(幺元、零元、逆元) 3、半群、含幺半群(独异点)的判断 4、群的证明(四个性质:封闭性、结合性、存在幺元、 每个元素存在逆元) 5、 Klein四元群、阿贝尔群(可交换群) 6、群中元素的阶(周期)、循环群的生成元
代数系统 重点: 1、代数系统的概念（二元运算、子代数、封闭性、其它 性质（结合律、幂等律、交换律、消去律）） 2、代数系统的特殊元素判断（幺元、零元、逆元） 3、半群、含幺半群（独异点）的判断 4、群的证明（四个性质：封闭性、结合性、存在幺元、 每个元素存在逆元） 5、Klein四元群、阿贝尔群（可交换群） 6、群中元素的阶（周期）、循环群的生成元
图 重点 1、无向图、有向图 2、顶点的度、握手定理、度序列 3、简单图、多重图、完全图、子图(生成子图 导出子图)、补图、同构 4、通路、回路(简单通路、初级通路)、通路长度、距离 5、连通图、连通分支、点割集、边割集 6、关联矩阵、邻接矩阵、可达矩阵 7、二部图(判定条件)、完全二部图(K,m) 8、欧拉图的判定(欧拉通路、判定条件) 、哈密尔顿图(哈密尔顿通路) 10、平面图、非平面图、平面嵌入
图 重点: 1、无向图、有向图 2、顶点的度、 握手定理、度序列 3、简单图、多重图、完全图、子图（生成子图、 导出子图）、补图、同构 4、通路、回路（简单通路、初级通路）、通路长度、距离 5、连通图、连通分支、点割集、边割集 6、关联矩阵、邻接矩阵、可达矩阵 7、二部图（判定条件）、完全二部图（Kn,m) 8、欧拉图的判定（欧拉通路、判定条件） 9、哈密尔顿图（哈密尔顿通路） 10、平面图、非平面图、平面嵌入
注: (1)大纲中列出的内容是主要概念在大纲中未出现的也可 能会少量涉及到(上课未讲过的概念不会出现) (2)大纲中红色字体表示大题(综合题)的出题范围 3)题型一般为:判断、选择、填空、综合; (4)考试允许带一张手写A4纸张(可双面写,不许复印、打 印,非A4纸不许带入考场,不得转借,违反规定均按舞弊 处理)
注: (1)大纲中列出的内容是主要概念, 在大纲中未出现的也可 能会少量涉及到（上课未讲过的概念不会出现）; (2)大纲中红色字体表示大题(综合题)的出题范围; (3)题型一般为：判断、选择、填空、综合; (4) 考试允许带一张手写A4纸张(可双面写，不许复印、打 印，非A4纸不许带入考场，不得转借，违反规定均按舞弊 处理）