《离散数学课件离散二总复习》由会员分享，可在线阅读，更多相关《离散数学课件离散二总复习（35页珍藏版）》请在金锄头文库上搜索。
1、离散二总复习,代数系统,熟练掌握二元运算性质的判断及证明。 掌握代数系统的同构定义和证明，了解同构性质的保持。 熟练掌握半群,独异点和群的概念。 熟悉群的阶、群中元素的阶以及群的基本性质。 掌握子群的证明。 熟悉陪集的定义和性质。 熟悉Lagrange定理及其推论,学会简单应用。,1、群中的简单证明,主要包括： 群中的等式（元素相等或集合相等） 与元素的阶相关的命题 群的其它简单命题，如交换性等。 经常使用的工具： 算律：结合律、消去律 和特殊元素相关的等式，如单位元、逆元等。 幂运算规则 和元素的阶相关的性质。（如：a为2阶元的充分必要条件是a-1=a等）,1、群中的简单证明,习题1： 设G
2、为群，任取xG ，有x2=e, 证明G是交换群。,证明： x2=e x-1=x 可证明在群G中,1、群中的简单证明,习题2： 偶数阶群中必含2阶元。,证明： 如果元素x的阶大于2，则x -1 x ， x与它的逆元成对出现，由于群中元素个数为偶数个，则除幺元e外，一定有2阶元。,2、子群的证明,习题3： 设G为群，a是G中的2 阶元，证明G中与a可交换的元素构成G的子群。,证明： 令H= x | xGxa=ax, 下面证明H是G的子群。 首先e属于H，H是G的非空子集。 任取x, yH，有 (xy-1) a = x(y-1 a) = x(a-1y)-1 = x(ay)-1 = x(ya)-1 =
3、 x a-1y-1 = x ay-1 = axy-1 = a(xy-1) 因此xy-1属于H。由判定定理命题得证。,3、拉格朗日定理应用实例,习题4： 证明6阶群中必含有3阶元。,应用习题1结论：只含有1阶和2阶元的群是Abel群。,习题5： 设H1，H2分别是群G的r, s 阶子群，若r, s互素，证明H1H2=e。,3、拉格朗日定理应用实例,4、同态与同构,习题6： 定义群G上的函数f，f(x)=x-1，xG ，证明f为自同构当且仅当G为交换群。,证明： 必要性：任取x,yG, xy = f(xy)-1) = f(y-1x-1) = f(y-1)f(x-1) = yx 充分性：易见f为双射
4、。任取x,yG, 有 f(xy) = f(yx) = (yx)-1 = x-1y-1 = f(x)f(y),课后习题,5-1: (2) 5-2: (2) (3) 5-3: (1) (3) (5) 5-4: (1) (2) (3) (5) 5-7: (1) (2) (3) (5) (8) 5-8: (2) (3) (11) 第九章：7, 17, 18 第十章：2, 8, 18,格与布尔代数,掌握格的定义，了解格的性质及格同态。 能够证明格中的等式和不等式。 能判别格L的子集S是否构成子格。 能够判断格，分配格，有补格和布尔格。 掌握布尔代数中的运算性质。,1、格的定义与性质,偏序集构成格的条件：
5、任意二元子集都有最大下界和最小上界。 格的实例：正整数的因子格，幂集格，子群格。 格的性质：对偶原理，格中运算律（交换、结合、幂等、吸收），保序性，分配不等式。 格作为代数系统的定义。,习题,1. 判断下述偏序集是否构成格？如果不是说明理由。,2. 求下述命题的对偶命题。,习题,3. 证明题,2、子格与格同态,格L的非空子集S构成L的子格的条件：S对L的两个运算封闭。 函数f构成格同态的条件： f(ab)=f(a)f (b), f(ab)=f (a)f (b) 格同态的保序性。,习题,1. 求格L的所有子格。,2. 任取格L的元素a, 令S=x|xL且xa, 证明S是L的子格。,3、分配格与有
6、补格,如果格中一个运算对另一个运算是可分配的，称这个格是分配格。 分配格的两种判别法：不存在与钻石格或五角格同构的子格；对于任意元素a,b,c,有 ab= ac且a b = ac b=c. 有界格的定义及其实例。 格中元素的补元及其性质（分配格中补元的唯一性） 有补格的定义,习题,1. 判别格L是否为分配格。,2.求出每个格的所有的补元，说明它们是否为有补格。,4、布尔代数,会判别一个格是布尔格。 证明布尔代数中的等式。 了解任意有限布尔代数都与某个幂集格同构。,习题,1. 设是布尔代数，证明对于B中任意元素a, b,习题,2. 判断下述代数系统是否为格？是不是布尔代数？,（1）S=1,3,4
7、,12，x,yS，xy与xy分别表示x与y的最小公倍数和最大公约数。 （2）S=0,1,2， 为模3加法， 为模2乘法 （3）S=0,.,n ,其中n2;任给x,yS, xy=max(x,y), xy=min(x,y)。,课后习题,6-1: (1) (2) (5) (7) 6-2: (2) (5) 6-3: (1) (3) (6) 6-4: (2) (6) 第十一章：1, 8, 14, 16,图的基本概念,无向图、有向图、关联与相邻、简单图、完全图、正则图、子图、补图；握手定理与推论；图的同构 通路与回路及其分类 无向图的连通性与连通度 有向图的连通性及其分类 图的矩阵表示及基本含义,图的基本
8、概念,无向图、有向图、关联与相邻、简单图、完全图、正则图、子图、补图；握手定理与推论；图的同构 通路与回路及其分类 无向图的连通性与连通度 有向图的连通性及其分类 图的矩阵表示及基本含义,课后习题,第十四章: 1, 3, 5, 8, 10, 14, 15, 16, 21, 23, 25, 30, 31, 35, 44, 45, 46, 47, 49,欧拉图和汉密尔顿图,掌握欧拉图、半欧拉图的定义及判别定理 掌握汉密顿图、半汉密顿图的定义 能够用汉密顿图的必要条件和充分条件分别进行判断。 要特别注意的是，不能将必要条件当作充分条件，也不要将充分条件当必要条件 掌握欧拉图和汉密尔顿图的简单应用,课
9、后习题,第十五章: 1, 2, 8, 9, 12, 13, 14, 15, 20,树,掌握无向树的定义及性质 熟练求解无向树 准确求解给定带权连通图的最小生成树 掌握基本回路、基本割集的概念，并会计算 理解根树及其分类等概念 熟练掌握求最优树及最佳前缀码的方法 掌握二叉树的遍历,课后习题,第十六章: 2, 3, 4, 9, 13, 19, 20, 24, 25, 29, 31, 33, 35, 36, 37, 39, 41,平面图,掌握基本概念：平面图、平面嵌入、面、次数、极大平面图、极小非平面图、对偶图 掌握极大平面图的主要性质和判别方法 熟练掌握欧拉公式及推广，并能用欧拉公式及推广形式证明
10、有关命题 会用库拉图斯基定理判定非平面图 掌握平面图与它的对偶图阶数、边数、面数之间的关系,课后习题,第十七章: 5, 7, 8, 12, 16, 17, 19, 20, 21, 24,匹配与着色,熟练掌握匹配、点着色、边着色、面着色、色数等概念 会用二部图中匹配的理论解简单问题 理解地图面着色与它的对偶图点着色之间的关系 会用点色数及边色数解决一些实际问题.,课后习题,第十八章: 16，17，18， 19，20，21，25，27，28，32，33，35,初等数论,熟练掌握整除、素数、合数的概念及其性质, 掌握素数判断，素因子分解 熟练掌握最大公约数和最小公倍数的概念及其性质, 会求最大公约数和最小公倍数, 掌握辗转相除法（欧几里得算法） 熟练掌握同余的概念及其性质, 掌握模m逆的概念及存在的充分必要条件, 会用扩展欧几里得算法求解模m逆. 掌握伪随机数产生和加密解密的简单应用,课后习题,第十九章: 5, 6, 13, 17, 25, 35, 50,
