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