离散数学 第六章ppt课件

第六章几个典型的代数系统,第六章几个典型的代数系统,6.1半群与群6.1.1半群与独异点6.1.2群的定义与性质6.1.3子群6.1.4陪集与拉格朗日定理6.1.5正规子群与商群6.1.6循环群和置换群6.2环与域6.2.1环的定义与性质6.2.2整环与域6.3格与布尔代数,6.1半群与群,半群、可交换半群和独异点定义6.1设V=是代数系统,为二元运算,如果是可结合的,则称V为半群如果半群V=中的二元运算含有幺元,则称V为含幺半群,也可叫做独异点.定义6.2如果半群V=中的二元运算是可交换的,则称V为可交换半群.注:为了强调幺元的存在,有时将独异点记为,6.1.1半群与独异点,例6.1是半群,都是半群和独异点，其中+表示普通加法,幺元是0,是半群和独异点,其中表示矩阵乘法,矩阵乘法的幺元是n阶单位矩阵E.记作是半群和独异点,其中表示集合的对称差运算,其幺元是,记作是半群和独异点,其中Zn=0,1,n-1,表示模n加法,模n加法的幺元是0.其中:为可交换半群.,6.1.1半群与独异点,例6.2判断下述论断正确与否,在相应的括号中键入“Y”或“N”.(1)在实数集R上定义二元运算*为：对于任意的a,bR,a*b=a+b+ab(a)是一个代数系统；()(b)是一个半群；()(c)是一个独异点。()(2)在实数集R上定义二元运算为,对任意a,bR,ab=|a|b(其中表示通常数的乘法运算)(a)是一个代数系统；()(b)是一个半群；()(c)是一个独异点。(),6.1.1半群,N,Y,Y,Y,Y,Y,子半群和子独异点定义:半群的子代数叫做子半群,即:如果V=是半群,就是V的子半群,需要满足如下两个条件:T是S的非空子集;T对V中的运算是封闭的.定义:独异点的子代数叫做子独异点,对独异点V=,构成V的子独异点,需要满足如下条件:T是S的非空子集;T要对V中的运算封闭;eT.,6.1.1半群与独异点,群的定义定义6.3设是代数系统,为二元运算.如果是可结合的,存在幺元eG,并且G中的任意元素x,都有x-1G,则称G是群.例6.3,都是群;是群,其中表示集合的对称差运算,元素的逆元是自身;是群,其中Zn=0,1,n-1,表示模n加法,0的逆元是0,非0元素的逆元是n-x.,6.1.2群的定义与性质,6.1.2群的定义与性质,e为G中的幺元,是可交换的.任何G中的元素与自己运算的结果都等于e.在a,b,c三个元素中,任何两个元素运算的结果都等于另一个元素.一般称这个群为Klein四元群.,例6.4设Ge,a,b,c,为G上的二元运算,它由以下运算表给出,不难证明G是一个群.,6.1.2群的定义与性质,群的术语(1)若群G中的二元运算是可交换的,则称群G为交换群,也叫做阿贝尔(Abel)群例,都是群,也是阿贝尔(Abel)群;是群,也是阿贝尔(Abel)群;是群,也是阿贝尔(Abel)群.Klein四元群也是阿贝尔群(2)若群G中有无限多个元素,则称G为无限群,否则称为有限群,只含幺元的群为平凡群.例如,都是无限群.是有限群.Klein四元群也是有限群.,6.1.2群的定义与性质,群的术语(3)群的阶:对于有限群G,G中的元素个数也叫做G的阶,记作|G|.例如:是有限群,其阶是n;Klein四元群也是有限群,其阶是4.(4)xn定义:x0=e,xn+1=xnx,x-n=(x-1)n(5)元素x的阶:设G是群,xG,使得xke成立的最小的正整数k叫做x的阶(或周期).如果不存在正整数k,使xke,则称x是无限阶元.注:对有限阶的元素x,通常将它的阶记为|x|.在任何群G中幺元e的阶都是1,6.1.2群的定义与性质,群的术语例.在Klein四元群中,|a|=?,|b|=?,|c|=?,|e|=?,返回,6.1.2群的定义与性质,群的性质定理6.1设G为群,则G中的幂运算满足(群中元素的幂)(1)xG,(x-1)-1x(2)x,yG,(xy)-1y-1x-1(3)xG,xnxmxn+m(4)xG,(xn)mxnm(5)若G为交换群,则(ab)n=anbn,定理6.1的证明,(1)aG,(a-1)-1a(a-1)-1是a-1的逆元，a也是a-1的逆元。（或者：a-1是a的逆元，a也是a-1的逆元。）根据逆元的唯一性，(a-1)-1a。(2)a,bG，(ab)-1b-1a-1(b-1a-1)(ab)b-1(a-1a)bb-1be(ab)(b-1a-1)a(bb-1)a-1aa-1e故b-1a-1是ab的逆元。根据逆元的唯一性等式得证。,6.1.2群的定义与性质,群的性质定理6.2G为群,a,bG,则(1)G有唯一的单位元,G中每个元素恰有一个逆元;(2)G适合消去律,即对任意a,b,cG有若abac,则bc;若baca,则bc;(3)单位元是G的唯一的幂等元素;,6.1.3子群,子群的定义定义6.4设群,H是G的非空子集.如果H关于G中的运算*构成群,则称H为G的子群,记作HG.若H是G的子群,且HG,则称H是G的真子群.例如:在群中,取2Z2x|xZ,则2Z关于加法构成的子群.同样,0也是的子群.注意:类似于子代数,任何群G都存在子群,G和e是G的平凡子群.,6.1.3子群,子群的判断方法判定定理1设G为群,H是G的非空子集,H是G的子群当且仅当:(1)a,bH都有abH;(2)aH有a-1H.判定定理2设G为群,H是G的非空子集,则H是G的子群当且仅当a,bH都有ab-1H.判定定理3设G为群,H是G的非空子集.若H是有穷集,则H是G的子群当且仅当a,bH都有abH.,6.1.3子群,子群的判断方法例6.5设G为群,对任何xG,令Hxk|kZ,即x的所有幂的集合,则H是G的子群,称为由元素x生成的子群,记作.证明:G由x可知不为空.任取H中的元素xm,xl,都有xm(xl)-1xmx-lxm-lH根据判定定理二可知G.,6.1.3子群,例如,群中由2生成的子群包含2的各次幂,20=0,21=2,22=22=4,23=222=0,所以=0,2,4.对于Klein四元群G=e,a,b,c来说,由它的每个元素生成的子群是=e,=e,a,=e,b,=e,c,6.1.3子群,群的中心设G为群,令C是与G中所有的元素都可交换的元素构成的集合,即Ca|aGxG(ax=xa),称C为群G的中心.,6.1.4陪集与拉格朗日定理,陪集的定义定义6.4H是G的子群,aG,令Ha=ha|hH称Ha是子群H在G中的右陪集,称a为Ha的代表元素.例6.6设G=e,a,b,c是Klein四元群,H=e,a是G的子群,那么H的所有右陪集是:He=e,a=HHa=e,a=HHb=b,cHc=c,b注:类似地可以定义左陪集.,6.1.4陪集与拉格朗日定理,陪集的定义例6.6设A=1,2,3,f1,f2,f6是A上的双射函数,其中:f1=,f2=,f3=,f4=,f5=,f6=,令G=f1,f2,f3,f4,f5,f6,则G关于复合(本题为右复合)运算构成了群,G的子群H=f1,f2,求H的全部右陪集.Hf1=f1f1,f2f1=f1,f2=HHf2=f1f2,f2f2=f1,f2=HHf3=f1f3,f2f3=f3,f5Hf4=f1f4,f2f4=f4,f6Hf5=f1f5,f2f5=f5,f3Hf6=f1f6,f2f6=f6,f4,6.1.4陪集与拉格朗日定理,陪集的性质定理6.3(定理10.7-10.9):设H是G的子群,则He=HaG有aHaa,bG,aHbab-1HHa=Hb在G上定义关系R:a,bG,Rab-1H,则R是G上的等价关系,且aR=Ha.aG,HHa(指势相等)注意:左陪集的性质与此类似.,6.1.4陪集与拉格朗日定理,Lagrange定理对G的子群H来说,H的左陪集和右陪集一般是不相等的,但左右陪集的个数是相等的.因此将左右陪集数统称为H在G中的陪集数,也叫做H在G中的指数,记为G:H.定理6.4(定理10.10):设G是有限群,H是G的子群,则|G|=|H|G:H.推论1设G是n阶群,则aG,|a|是n的因子,且an=e.推论2对阶为素数的群G,必存在aG使得G=.,6.1.5正规子群和商群,正规子群定义6.5设H是G的子群,如果aG都有Ha=aH,则称H是G的正规子群,记作HG.定义6.6设G是群,N是G的正规子群,令G/N是N在G中的全体左陪集(或右陪集)构成的集合,即G/N=Ng|gG在G/N上定义二元运算如下:Na,NbG/N,NaNb=NabG/N关于构成了群,称为G的商群.,6.1.6循环群和置换群,循环群定义6.7在群G中,如果存在aG使得G=ak|kZ则称G为循环群,记作G=,称a为G的生成元.循环群必定是阿贝尔群,但阿贝尔群不一定是循环群.证明:设是一个循环群,它的生成元是a,那么,对于任意x,yG,必有r,sZ,使得x=as,y=at,而且x*y=as*at=as+t=at*as=y*x由此可见是一个阿贝尔群.例如,是一个循环群,其生成元是1或-1.,循环群在循环群G=中,生成元a的阶与群G的阶是一样的.如果a是有限阶元,|a|n,则称G为n阶循环群.如果a是无限阶元,则称G为无限阶循环群.例如:是无限阶循环群;是n阶循环群.注意:(1)对无限阶循环群G=,G的生成元是a和a-1;(2)对n阶循环群G=,G的生成元是at当且仅当t与n互素,如12阶循环群中,与12互素的数有1、5、7、11.那么G的生成元有a1=a、a5、a7、a11.(3)N阶循环群G=,对于n的每个正因子d,G恰好有一个d阶子群H=.,6.1.6循环群和置换群,6.1.6循环群和置换群,n元置换定义6.7设S1,2,n,S上的任何双射函数:SS构成了S上n个元素的置换,称为n元置换.例如,S=1,2,3,令:SS,且有:(1)=2,(2)=3,(3)=1则将1,2,3分别置换成2,3,1,此置换常被记为=采用这种记法,一般的n元置换可记为,n元置换n个不同元素有n!种排列的方法,所以,S上有n!个置换.例如,上有3!=6种不同的置换,即,6.1.6循环群和置换群,n元置换对于n元置换也可以用不交的轮换之积来表示.=(a1a2am),mn那么的映射关系是a1a2,a2a3,am-1am,ama1,而其他的元素都有aa.称为m次轮换.这样,任何n元置换都可表成不交的轮换之积.,6.1.6循环群和置换群,n元置换例如,是1,2,6上的置换,且=那么的映射关系是16,25,33,44,52,61.去掉3和4这两个保持不变的元素,可得16,61,25,52所以=(16)(25)(3)(4),6.1.6循环群和置换群,n元置换又如,也是1,2,6上的置换,且=则有=(14325)(6)为使表达式简洁,可以去掉1次轮换那么有=(16)(25)=(14325),6.1.6循环群和置换群,n元置换用轮换法表示1,2,3上的置换可记为：1=(1),2=(12),3=(13),4=(23),5=(123),6=(132)轮换可以进一步表示成对换之积,如6=(13)(12)奇置换:能表示成奇数个对换之积的置换;偶置换:能表示成偶数个对换之积的置换.,6.1.6循环群和置换群,n元对称群、n元置换群设S=1,2,n,S上的n!个置换构成集合Sn,其中恒等置换Is=(1)Sn.在Sn上规定二元运算,对于任意n元置换,Sn,表示与的复合(乘法).显然也是S上的n元置换,所以,Sn对运算是封闭的,且是可结合的.任取Sn中的置换,有Is=Is=所以,恒等置换Is=(1)是Sn中的幺元.,6.1.6循环群和置换群,n元对称群、n元置换群与的逆置换的复合为Is,因此:-1=就是的逆元.即:Sn关于置换的复含构成一个群,称之为S上的n元对称群.Sn的任何子群称为S上的n元置换群.,6.1.6循环群和置换群,n元对称群、n元置换群例如S3=(1),(12),(13),(23),(123),(132),S3的运算表如表6.1所示.(注意它与例6.6中G的联系),6.1.6循环群和置换群,从上表6.1可以看到:(13)(12)(12)(13)所以,S3不是阿贝尔群,在S3中,(12),(13)和(23)都是2阶元,而(123)和(132)是3阶元.S3有6个子群,即=(1),=(1),(12),=(1),(13),=(1),(23),=(1),(123),(132),其中(1)和S3是平凡的,除S3自己以外,都是S3的真子群.设An是Sn上所有偶置换组成的集合,An是Sn子群,叫做n元交错群.,6.1.6循环群和置换群,6.2环与域,6.2.1环定义6.8设是代数系统,R为集合,+和为二元运算,如果(1)为阿贝尔群,(2)为半群,(3)乘法对加法+适合分配律,则称是环.例如:,都是环,+和表示普通加法和乘法,分别叫整数环Z、有理数环Q、实数环R和复数环C.是环,+,分别是矩阵加法和乘法.注:环中关于加法的逆元称为负元,记为-x;关于乘法的逆元称为逆元,记为x-1,6.2环与域,6.2.2交换环和含幺环在环中,如果乘法适合交换律,则称R是交换环.如果对于乘法有幺元,则称R是含幺环.为了区别含幺环中加法幺元和乘法幺元,通常把加法幺元记作0,乘法幺元记作1.可以证明加法幺元0恰好是乘法的零元.例如:,都是交换环吗?它们是含幺环吗?,6.2环与域,6.2.3左零因子、右零因子、无零因子环在环中,如果存在a,bR,a0,b0,但ab0,则称a为R中的左零因子,b为R中的右零因子.如果环R中既不含左零因子,也不含右零因子,即a,bR,ab0a0b0则称R为无零因子环.,6.2环与域,6.2.3整环和域整环:若环是交换、含幺和无零因子的,称R为整环.域:设环整环,且R至少含有2个元素,若aR(a0)有a-1R,则称R是域.例如:有理数集Q、实数集R和复数集C关于普通的加法和乘法都构成了域,整数集Z只能构成整数环,而不是域,因为并不是任意非零整数的倒数都属于Z.,例6.6设S为下列集合,+和.为普通加法和乘法.(1)Sxx2nnZ.(2)Sxx2n+1nZ.(3)SxxZx0N,问S和+,能否构成整环？能否构成域？为什么？,6.2环与域,解:(1)不是整环也不是域,因为乘法幺元是1,1S.(2)不是整环也不是域,因为S不是环,普通加法的幺元是0,0S,(3)S不是环,因为除0以外任何正整数x的加法逆元是一x,而一xS当然也不是整环和域.,6.2.4环的性质定理6.6设是环,则(1)aR,a00a0.(2)a,bR,(-a)ba(-b)-(ab).(3)a,bR,(-a)(-b)ab.(4)a,b,cR,a(b-c)=ab-ac,(b-c)aba-ca.,6.2环与域,6.3格和布尔代数,6.3.1格定义6.10设是偏序集,如果x,yS,x,y都有最小上界和最大下界,则称S关于构成一个格.xy表示x和y的最小上界xy表示x和y的最大下界.例6.7设n为正整数,Sn为n的正因子的集合,D为整除关系,则构成格.x,ySn,xy是x,y的最小公倍数x,y,xy是x,y的最大公约数(x,y),6.3格和布尔代数,格,和xy是x,y的最小公倍数x,y,xy是x,y的最大公约数(x,y),155,例6.8判断图中偏序集是否构成格,说明为什么.,6.3格和布尔代数,6.3格和布尔代数,6.3.2对偶原理对偶命题:设f是含有格中的元素以及符号=,的命题,令f*是将f中的改写成,将改写成,改写成,改写成所得到的命题,称为f的对偶命题.根据格的对偶原理,若f对一切格为真,则f*也对一切格为真.例如,若在格中有(ab)cc成立,则有(ab)cc成立.,定理6.7设为格,则运算和适合交换律、结合律、幂等律和吸收律,即(1)a,bL,有abba,abba(2)a,b,cL,有(ab)ca(bc),(ab)ca(bc).(3)aL,有aaa,aaa.(4)a,bL,有a(ab)a,a(ab)a.,6.3格和布尔代数,6.3格和布尔代数,格的另一个等价的定义设是具有两个二元运算的代数系统,且对于*和运算适合交换律、结合律、吸收律,则可以适当定义S中的偏序使得构成一个格,且a,bSab=a*b,ab=ab.,6.3格和布尔代数,6.3.3分配格定义6.11设是格,若a,b,cL有a(bc)(ab)(ac)a(bc)(ab)(ac)成立,则称L为分配格.,图中(1)、(2)、(3)、(4)是分配格吗？(3)a(bc)aea(ab)(ac)ddd(4)b(ac)beb(ba)(bc)dc=c.,6.3格和布尔代数,6.3.4全上界和全下界定义6.12若在格中存在一个元素a,bL,a