离散数学 复习

1、1西安交通大学西安交通大学电子与信息工程学院电子与信息工程学院计算机系计算机系2离散数学 第三章第三章 集集 合合 重点要求重点要求 w掌握集合、子集、全集、空集、单元素集等概念掌握集合、子集、全集、空集、单元素集等概念, ,掌握集合的四大掌握集合的四大性质性质: :任意性任意性(抽象性抽象性)、确定性、无序性、无重复性、确定性、无序性、无重复性, ,熟悉常用的表熟悉常用的表示集合的方法以及用文氏图来表示集合的方法示集合的方法以及用文氏图来表示集合的方法, ,能够判定元素与集能够判定元素与集合合, ,集合与集合之间的关系集合与集合之间的关系. .理解两个集合间的包含关系和相等关系理解两个集合间

2、的包含关系和相等关系(外延性原理外延性原理)的定义和性质的定义和性质, ,能够利用这些定义、性质来证明两个能够利用这些定义、性质来证明两个更复杂的集合的包含和相等。更复杂的集合的包含和相等。w掌握幂集的定义及计算有限集的幂集所含元素个数，所使用的计掌握幂集的定义及计算有限集的幂集所含元素个数，所使用的计算、证明的方法和思想。算、证明的方法和思想。w理解理解差别在于级别差别在于级别! !的判定集合间关系的思想。的判定集合间关系的思想。w掌握集合的五种基本运算掌握集合的五种基本运算: :交、并、余交、并、余(补补)、差和对称差、差和对称差(环和环和)的的定义定义, ,并熟记集合运算的基本定理并熟记

3、集合运算的基本定理(公式公式), ,能够熟练的利用它们来证能够熟练的利用它们来证明更复杂的集合公式。明更复杂的集合公式。属于属于 包含包含 相等相等 并集并集 差集差集 对称差（环和）对称差（环和） 幂集幂集3离散数学 第四章第四章 关关 系系 重点要求重点要求 w掌握序偶和笛卡尔积的概念掌握序偶和笛卡尔积的概念。（。（元组元组 叉积叉积）w掌握二元关系的形式定义及其各种表示方法：序偶，矩阵，关系图掌握二元关系的形式定义及其各种表示方法：序偶，矩阵，关系图等；能正确使用集合表达式，关系距阵，关系图等表示给定的关系，等；能正确使用集合表达式，关系距阵，关系图等表示给定的关系，并要求能够从一种形式

4、写出另一种形式。并要求能够从一种形式写出另一种形式。w特殊关系：全关系、空关系、幺关系特殊关系：全关系、空关系、幺关系w掌握关系的运算，包括集合运算以及关系的复合和关系的逆运算。掌握关系的运算，包括集合运算以及关系的复合和关系的逆运算。 关系，反对称关系关系，反对称关系, 对称差对称差(环和环和)关系，传递关系关系，传递关系, 并关系并关系w掌握二元关系的各种特殊性质：掌握二元关系的各种特殊性质：自反，反自反，对称，反对称，传自反，反自反，对称，反对称，传递递等，并理解这些性质如何反映在关系图上，关系矩阵上等。等，并理解这些性质如何反映在关系图上，关系矩阵上等。w掌握集合中二元关系的闭包的意义

5、和其基本性质，能求出有限集上掌握集合中二元关系的闭包的意义和其基本性质，能求出有限集上的二元关系的闭包。的二元关系的闭包。4离散数学w掌握等价关系的概念，并掌握覆盖、划分、等价类、商集的定掌握等价关系的概念，并掌握覆盖、划分、等价类、商集的定义和基本性质，弄清楚等价关系与划分之间的关系。牢记等价关义和基本性质，弄清楚等价关系与划分之间的关系。牢记等价关系的系的分类分类作用。作用。等价关系等价关系(R A2) 自反性：自反性： x A，(x, x) R对称性：对称性： x, y A，(x，y) R (y，x) R传递性：传递性： x, y, z A，(x，y) R且且(y，z) R (x，z)

6、R 代表元，等价类代表元，等价类aR = x : x A xRa反对称性：反对称性： x, y A，(x，y) R且且(y，x) R x=yw掌握半序、半序集等概念，以及半序集的可比较性、极大元、掌握半序、半序集等概念，以及半序集的可比较性、极大元、极小元、极小元、最大元、最小元、上界、下界、最大下界、最小上界最大元、最小元、上界、下界、最大下界、最小上界、直接后继等概念。牢记半序关系的直接后继等概念。牢记半序关系的非线性非线性特性。特性。w能画出能画出有限半序集的哈斯图有限半序集的哈斯图, ,并根据图讨论半序集的某些性质。并根据图讨论半序集的某些性质。w掌握掌握全序集、良序集全序集、良序集等

7、概念；等概念；良序集良序集定理定理3;5离散数学 第五章第五章 函函 数数 重点要求重点要求 w要求掌握函数、元素的像、集合的像等基本概念要求掌握函数、元素的像、集合的像等基本概念,理解元素及集合理解元素及集合的象及原象的定义及相关的性质的象及原象的定义及相关的性质。给定一个函数给定一个函数,能够确定一个点能够确定一个点的象的象,一个一个集合集合的象的象,能够确定一个点的原象能够确定一个点的原象,一个一个集合集合的原象。的原象。w弄清单射弄清单射、满射满射、双射之间的区别双射之间的区别。给定一个函数给定一个函数,要能够确定它要能够确定它是否是单射是否是单射、满射满射、双射等双射等。单射函数：单

8、射函数： x1, x2 X，f( (x1) )= f( (x2) ) x1 = x2满射函数：满射函数： y Y， x X，使，使f( (x) )= yw掌握逆函数和复合函数的定义和性质掌握逆函数和复合函数的定义和性质,并弄清楚它们存在的条件和并弄清楚它们存在的条件和相关定理。能够确定两个函数的复合函数等相关定理。能够确定两个函数的复合函数等。 双射函数的逆函数定理双射函数的逆函数定理 复合函数定理复合函数定理w掌握掌握集合集合的势的势、可数集、不可数集等概念、可数集、不可数集等概念。无限集合无限集合 可数集合可数集合 6离散数学 第六章第六章 代数系统代数系统 重点要求重点要求 w掌握代数系

9、统的概念掌握代数系统的概念,定义定义: 运算的封闭性运算的封闭性、幺元幺元、零元零元、逆元逆元及及相关的结论有清晰的理解相关的结论有清晰的理解。给定集合和集合上的运算能够判断该给定集合和集合上的运算能够判断该集合对运算是否封闭集合对运算是否封闭; ;能够通过运算表确定幺元、能够通过运算表确定幺元、零元零元、逆元等逆元等(如如果存在的话果存在的话); 对交换律对交换律、结合律结合律、分配律分配律、吸收律吸收律、消去律、消去律等的等的表示要十分清楚表示要十分清楚;给定集合和二元运算表能够判断运算是否满足结给定集合和二元运算表能够判断运算是否满足结合律等等合律等等。w掌握代数系统的同态和同构的定义能

10、判断两个给定代数系统间的掌握代数系统的同态和同构的定义能判断两个给定代数系统间的某个映射是否为同态同构映射某个映射是否为同态同构映射。 同态公式同态公式： x1, x2 X，f( (x1*x2) )= f( (x1) ) f( (x2) ) 满同态，定理满同态，定理3 (同态遗传性定理同态遗传性定理(五条五条)；w掌握半群及含幺半群等概念掌握半群及含幺半群等概念。7离散数学w掌握群的概念掌握群的概念,并能灵活运用群的一些基本性质并能灵活运用群的一些基本性质,理解群的同态和同理解群的同态和同构构。给定一个代数系统及其运算给定一个代数系统及其运算,能够判断是否为半群能够判断是否为半群、含幺半群含幺

11、半群、群等群等。 封闭性，幺元，逆元，反身律，鞋袜律，交换律，结合律，交封闭性，幺元，逆元，反身律，鞋袜律，交换律，结合律，交换群，循环群、左右陪集换群，循环群、左右陪集，幂等元，幂等元 ，群的阶、元素的阶，群的阶、元素的阶 反身律：反身律：(a-1)-1 =a 鞋袜律：鞋袜律：(a* *b)-1 = b-1* *a-1 w掌握子群的概念并清楚其判别方法掌握子群的概念并清楚其判别方法。w掌握环掌握环、整环整环、除环、除环的定义的定义, ,并熟悉环的基本性质并熟悉环的基本性质。给定集合及两给定集合及两个二元运算能够判断其是否为环个二元运算能够判断其是否为环、整环整环、除环、除环等等。w牢记消去律

12、牢记消去律、无零因子、有逆元三者间的两层关系及其运用、无零因子、有逆元三者间的两层关系及其运用。 环环(R)，子环，子环(S) 非空性：非空性：S 包含性：包含性：S R8离散数学 减法封闭性：减法封闭性： x, y S，x S y S x y S 乘法封闭性：乘法封闭性： x, y S，x S y S x y S 无零因子环无零因子环(S)； x, y S，x, y 0 x y 0w掌握域及有限域的定义掌握域及有限域的定义。 域，素域，有限域；域，素域，有限域；9离散数学 第七章第七章 格与布尔代数格与布尔代数 重点要求重点要求 w掌握格的两种定义掌握格的两种定义(半序格、代数格半序格、代数

13、格)及其等价性证明，能够对由及其等价性证明，能够对由半序集所确定的哈斯图判定其是否为格，能够对有关格的一些论半序集所确定的哈斯图判定其是否为格，能够对有关格的一些论题进行证明或构造反例而将其否证。题进行证明或构造反例而将其否证。w熟记格运算的基本运算性质熟记格运算的基本运算性质(交换律、结合律、吸收律、幂等律交换律、结合律、吸收律、幂等律)及其与序的关系及其与序的关系(等价性、保序性等价性、保序性)，并会灵活运用。，并会灵活运用。格同态格同态 半序格半序格, 定理定理4 (a b a*b = a a b = b)； 10离散数学w掌握分配不等式、模不等式等性质的证明及应用。掌握分配不等式、模不

14、等式等性质的证明及应用。w掌握分配律、零壹律、互补律等的定义，并清楚它们之间的关系，掌握分配律、零壹律、互补律等的定义，并清楚它们之间的关系，对于具体给出的格所对应的哈斯图，应能判断是否为分配格、有界对于具体给出的格所对应的哈斯图，应能判断是否为分配格、有界格或有补格等。格或有补格等。 分配格，分配律；分配格，分配律； 有界格，最小元，最大元，有界格，最小元，最大元， ( a L)(0 a 1) 即即 0*a=0 a*1=a 有补格，补元，互补律，唯一性有补格，补元，互补律，唯一性, ,定理定理1212，有界分配格补元唯一，有界分配格补元唯一w掌握布尔代数的概念和几个重要的特例，熟记布尔代数的

15、许多重掌握布尔代数的概念和几个重要的特例，熟记布尔代数的许多重要的基本性质及其与序的关系，并会灵活运用。要的基本性质及其与序的关系，并会灵活运用。w掌握格和布尔代数的对偶原理掌握格和布尔代数的对偶原理,并会灵活运用。并会灵活运用。w掌握布尔代数的原子概念掌握布尔代数的原子概念,和布尔表达式的原子表示的概念和布尔表达式的原子表示的概念,并会灵并会灵活运用。熟悉布尔代数的斯笃定理的内容及证明。活运用。熟悉布尔代数的斯笃定理的内容及证明。11离散数学12离散数学w 能够利用能够利用K ning算算法法求哈密顿路或密顿圈，求哈密顿路或密顿圈，能够利用能够利用翻边翻边法法求求有向哈密顿路或有向密顿圈，有

16、向哈密顿路或有向密顿圈，能够利用能够利用近邻法近邻法、交换法、交换法求解货求解货郎担问题郎担问题(最优哈密顿圈最优哈密顿圈)。 哈密顿圈，哈密顿图，结点的度，哈密顿圈，哈密顿图，结点的度，D.KD.Knignig定理定理3 3及其推论及其推论1 1 w 掌握掌握二分图（偶图）二分图（偶图）、奇圈、偶圈、二分图定理、奇圈、偶圈、二分图定理1 1，匹配、完美，匹配、完美匹配、最大匹配匹配、最大匹配等等概念，概念，掌握偶图的掌握偶图的判别性定理及判别法判别性定理及判别法- -标号标号法（着色法），法（着色法），能够利用能够利用匈牙利匈牙利法以增广路法以增广路求偶图的求偶图的最大匹配最大匹配。w 掌握

17、平面图掌握平面图、非、非平面图平面图、区域、区域( (面面) ) 等等概念概念。 掌握平面图的掌握平面图的欧欧拉公式及其拉公式及其必要性判别法和推论、拉边法，必要性判别法和推论、拉边法，了解了解Kuratowski平平面图面图最后定理，并能用其判别一个图的平面性最后定理，并能用其判别一个图的平面性。K K技术技术w 掌握掌握树树、树叶、树叉、树枝、森林、树叶、树叉、树枝、森林、生成树生成树、等概念。掌握树、等概念。掌握树的若干等价命题，并能够利用它们判断或证明树的有关结论，的若干等价命题，并能够利用它们判断或证明树的有关结论，掌握求连通图的生成树的破圈法和避圈法，掌握求带权连通图掌握求连通图的生成树的破圈法和避圈法，掌握求带权连通图的的最小生成树最小生成树的的Kruskal算法和管氏破圈算法算法和管氏破圈算法。13离散数学书后习题：书后习题：w 3: 3: 作业作业w 4 4： 作业作业w 5 5： 作业作业 + 6 7 8 9 10+ 6 7 8 9 10w 6 6： 作业作业 + 54 55 58 65+ 54 55 5