离散数学课件离散二总复习

《离散数学课件离散二总复习》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、离散二总复习代数系统熟练掌握二元运算性质的判断及证明。掌握代数系统的同构定义和证明，了解同构性质的保持。熟练掌握半群,独异点和群的概念。熟悉群的阶、群中元素的阶以及群的基本性质。掌握子群的证明。熟悉陪集的定义和性质。熟悉Lagrange定理及其推论,学会简单应用。1、群中的简单证明主要包括：群中的等式（元素相等或集合相等）与元素的阶相关的命题群的其它简单命题，如交换性等。经常使用的工具：算律：结合律、消去律和特殊元素相关的等式，如单位元、逆元等。幂运算规则和元素的阶相关的性质。（如：a为2阶元的充分必要条件是a-1=a等）1、群中的简单证明习题1：设G为群，任取x

2、∈G，有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

3、x∈G∧xa=ax},下面证明H是G的子群。首先e属于H，H是G的非空子集。任取x,y∈H，有(xy-1)a=x(y-1a)=x(a-1y)-1=x(ay)-1=x(ya)-1=xa-1y-1=xay-1=axy-1=a(xy-1)因此

4、xy-1属于H。由判定定理命题得证。3、拉格朗日定理应用实例习题4：证明6阶群中必含有3阶元。应用习题1结论：只含有1阶和2阶元的群是Abel群。习题5：设H1，H2分别是群G的r,s阶子群，若r,s互素，证明H1∩H2={e}。3、拉格朗日定理应用实例4、同态与同构习题6：定义群G上的函数f，f(x)=x-1，x∈G，证明f为自同构当且仅当G为交换群。证明：必要性：任取x,y∈G,xy=f((xy)-1)=f(y-1x-1)=f(y-1)f(x-1)=yx充分性：易见f为双射。任取x,y∈G,有f(xy)=f(yx)=(yx)-1=x-1y-1=f(x)f(y)课后习题5-1

5、:(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、格的定义与性质偏序集构成格的条件：任意二元子集都有最大下界和最小上界。格的实例：正整数的因子格，幂集格，子群格。格的性质：对偶原理，格中运算律（交换、结合、幂等、吸收），保序性，分配不等式。格作为代数系统的定义。习题

6、1.判断下述偏序集是否构成格？如果不是说明理由。2.求下述命题的对偶命题。（1）(a∧b)∨b=b（2）b∨(c∧a)≤(b∨c)∧a习题3.证明题（1）(a∧b)∨b=b（2）(a∧b)∨(c∧d)≤(a∨c)∧(b∨d)2、子格与格同态格L的非空子集S构成L的子格的条件：S对L的两个运算封闭。函数f构成格同态的条件：f(a∧b)=f(a)∧f(b),f(a∨b)=f(a)∨f(b)格同态的保序性。习题1.求格L的所有子格。2.任取格L的元素a,令S={x

7、x∈L且x≤a},证明S是L的子格。3、分配格与有补格如果格中一个运算对另一个运算是可分配的，称这个格是分配格。分配格

8、的两种判别法：不存在与钻石格或五角格同构的子格；对于任意元素a,b,c,有a∧b=a∧c且a∨b=a∨cb=c.有界格的定义及其实例。格中元素的补元及其性质（分配格中补元的唯一性）有补格的定义习题1.判别格L是否为分配格。2.求出每个格的所有的补元，说明它们是否为有补格。4、布尔代数会判别一个格是布尔格。证明布尔代数中的等式。了解任意有限布尔代数都与某个幂集格同构。习题1.设是布尔代数，证明对于B中任意元素a,b（1）（2）习题2.判断下述代数系统是否为格？是不是布尔代数？（1）S={1,3,4,12}，x,y∈S，xy与xy分别表示x与y的最小

9、公倍数和最大公约数。（2）S={0,1,2}，为模3加法，为模2乘法（3）S={0,...,n},其中n≥2;任给x,y∈S,xy=max(x,y),xy=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图的基本概念无向图、有向图、关联与相邻、简单图、完全图、正则图、子图、补图；握手定理与推论；图的同构通路与回路及其分类无向图的连通性与连通度有向图的连通性及其分类图的矩阵表示及基本