离散数学第五版第九章(耿素云、屈婉玲、张立昂编著)省名师优质课赛课获奖课件市赛课一等奖课件.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,An Introduction to Database Systenm,*,本资料仅供参考，不能作为科学依据。谢谢。本资料仅供参考，不能作为科学依据。谢谢,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,An Introduction to Database Systenm,*,本资料仅供参考，不能作为科学依据。谢谢。本资料仅供参考，不能作为科学依据。谢谢,离散数学,第1页,第,9,章,代数系统介绍,9.1,二元运算及其性质,9.2,代数系统,9.3,几个经典代数系统,第2页,9.1,二元运算及其性质,一、二元运算定义,(,定义,9.1),设,S,为集合,，函数,f:SSS,称为,S,上二元运算，简称为二元运算。,怎样判断一个运算是否为集合,S,上二元运算？,S,中任意两个元素均能够进行这种运算，且运算,结果是唯一。,S,中任意两个元素运算结果都属于,S,，即,S,对该运,算是封闭。,第3页,9.1,二元运算及其性质,例,1,：,第4页,9.1,二元运算及其性质,例,2,：,例,3,：,S,为任意集合，则在,f:P(A)P(A),P(A),上，,、是否为二元运算？,第5页,9.1,二元运算及其性质,二、,n,元运算定义,(,定义,9.2),设,S,为集合，,n,为正整数，则函数,f,：,SS,S,S,称为,S,上一个,n,元运算，简称为,n,元运算,。,（,1,）当,n=1,时，则函数,f:S,S,为,S,上一元运算，如,(x)=y,（,2,）,当,n=2,时，则函数,f:,SS,S,为,S,上二元运算。,(x,，,y)=z,（,3,）,当,n=3,时，则函数,f:,SSS,S,为,S,上三元运算。,(x,，,y,，,z)=t,第6页,9.1,二元运算及其性质,例,4,：在整数集合,Z,、有理数集合,Q,、实数集合,R,上,，一,个数相反数、倒数是否为这些集合上一元运,算？,例,5,：在幂集,P(S),上，假如要求全集为,S,，则求集合,绝对补运算是否为,P(S),上一元运算,？,第7页,9.1,二元运算及其性质,例,6,：设,S=1,2,给出,P(S),上运算和,运算表，,其中全集为,S,。,ai,ai,1,2,1,1,2,2,1,2,P(S)=,1,2,1,2,1,2,1,2,1,2,1,2,1,1,1,2,2,2,2,1,2,1,1,2,1,2,2,1,第8页,9.1,二元运算及其性质,例,7,：设,S=1,2,3,4,定义,S,上二元关系以下：,x,y=(x*y)mod 5,x,yS,。,求运算列表。,1,2,3,4,1,1,2,3,4,2,2,4,1,3,3,3,1,4,2,4,4,3,2,1,第9页,9.1,二元运算及其性质,三、二元运算主要性质,设,为,S,上二元运算,.,假如对于任意,x,yS,都有,xy=yx,则称运算在,S,上是可交换,或者说运算在,S,上适合交换律,.,（,1,）,交换律（定义,9.3,）,注,:,对于二元运算矩阵来说,二元运算满足交换律,则二元,运算矩阵关于主对角线对称。,第10页,9.1,二元运算及其性质,设,为,S,上二元运算,.,假如对于任意,x,y,zS,都有,(xy)z=x(yz),则称运算在,S,上是可结合,或者说运算在,S,上适合结合律,.,（,2,）,结合律（定义,9.3,）,注,:,整数集,Z,、自然数集,N,、有理数集,Q,、实数集,R,上加法和,乘法都是可结合；矩阵加法和乘法也是可结合；,集合,、也是可结合；函数复合运算也是可,结合,。,第11页,9.1,二元运算及其性质,设,为,S,上二元运算,假如对于任意,xS,都有,xx=x,则称运算在,S,上适合等幂律,.,（,3,）,幂等律（定义,9.3,）,集合,、是复合等幂律。,第12页,9.1,二元运算及其性质,设,和*是,S,上两个二元运算,假如对于任意,x,，,y,，,zS,有,x*(yz)=(x*y)(x*z)(,左分配律,),(yz)*x=(y*x)(z*x)(,右分配律,),则称运算*对是可分配，也称*对适合分配律。,（,4,）,分配律（定义,9.4,）,第13页,9.1,二元运算及其性质,设,和*是,S,上两个,可交换二元运算,假如对于任意,x,，,yS,有,x*(xy)=x,x(x*y)=x,则称运算*和满足吸收律。,（,5,）,吸收律（定义,9.5,）,比如：幂集,P(S),上,和运算满足吸收律。即,A,BP(S),有,A(A B)=A,A(A B)=A,第14页,9.1,二元运算及其性质,四、单位元和幺元,设,为,S,上二元运算,假如存在,(,或,)S,使得对于任何,xS,都有,x=x(,或,x =x),则称,(,或,),是,S,中关于运算一个左幺元,(,或右幺,元,),。若,eS,关于运算既是左幺元又是右幺元，则称,e,为,S,上关于运算幺元。,幺元定义（定义,9.6,）,第15页,9.1,二元运算及其性质,例,8,：,自然数集,N,上加法,幺元，幺元是,。,自然数集,N,上乘法,幺元，幺元是,。,自然数集,N,上除法,幺元，幺元是,。,幂集,P(S),上运算,幺元，幺元是,。,幂集,P(S),上运算,幺元，幺元是,。,第16页,9.1,二元运算及其性质,设,为,S,上二元运算,，分别为运算左幺元和,右幺元，则有,=e,且,e,为,S,上关于运算唯一幺元。,单位元和幺元唯一定理（定理,9.1,）,第17页,9.1,二元运算及其性质,四、零元,设,为,S,上二元运算,假如存在,(,或,)S,使得对于任何,xS,都有,x=(,或,x =),则称,(,或,),是,S,中关于运算一个左零元,(,或右零元,),。,若,S,关于运算既是左零元又是右零元，则称为,S,上关于,运算零元。,零元定义（定义,9.6,）,第18页,9.1,二元运算及其性质,例,9,：,自然数集,N,上加法,零元，零元是,。,自然数集,N,上乘法,零元，零元是,。,自然数集,N,上除法,零元，零元是,。,幂集,P(S),上运算,零元，零元是,。,幂集,P(S),上运算,零元，零元是,。,第19页,9.1,二元运算及其性质,设,为,S,上二元运算,，分别为运算左零元和,右零元，则有,=,且为,S,上关于运算唯一零元。,零元唯一定理（定理,9.2,）,第20页,9.1,二元运算及其性质,设,为S,上二元运算,e,，分别为运算幺元和,零元，假如,S,最少有两个元素，则,e,。,幺元与零元定理,证实：假设,e=,则,xS,有,x=e x=x=,则,x=e,S,中只有一个元素,又因为,S,中最少有两个元素，矛盾,所以：,e,第21页,9.1,二元运算及其性质,五、逆元,逆元定义（定义,9.6,）,设,为,S,上二元运算,eS,为运算幺元，对于,xS,，,假如存在 使得,则称 是,x,左逆元（或右逆元）。若,yS,既是,x,左逆元又是,x,右逆元，则称,y,是,x,逆元。假如,x,逆元,存在，则称,x,是可逆。,第22页,9.1,二元运算及其性质,逆元唯一定理（定理,9.3,）,设,为,S,上,可结合,二元运算,eS,为运算单位元，对于,xS,，,假如存在左逆元 和右逆元 则有,则,y,是,x,唯一逆元。,第23页,9.1,二元运算及其性质,六、消去律（定义,9.7,）,设,为,S,上二元运算,假如对于任意,x,y,zS,满足以下,条件：,(1),若,xy=xz,且,x,，则,y=z,。,(2),若,yx=zx,且,x,，则,y=z,。,那么称运算满足消去律，其中,(1),称作左消去律，,(2),称作,右消去律。,第24页,9.1,二元运算及其性质,例,10,：设,是字母有穷集，称为字母表，中有限个字母组成序列称为上串，对任何串，串中字母个数叫做串长度，记作,|,，长度是,0串叫空串，记作，对任给自然数,k,，令,它是上全部长度为,k,串集合，尤其：,串连接运算：,第25页,第九章,代数系统普通性质,9.1,二元运算及其性质,9.2,代数系统,9.3,几个经典代数系统,第26页,9.2,代数系统,一、代数系统定义,(,定义,9.8),非空集合,S,和,S,上,k,个运算,f,1,f,2,f,k,(,其中,f,i,为,n,i,元运算，,i=1,，,2,，,k),组成系统称为一个代数系统，简称代数，记作,。,判断代数系统方法：,判断该系统中每个运算是否为,n,元运算。,第27页,9.2,代数系统,例,11,：,、,、,、,是否为代数系统？,是否为代数系统？,第28页9.2,代数系统,二、特异元素、代数常数定义,代数系统中对于给定二元运算存在幺元或零元，而且它们对该系统性质起着主要作用，称之为该系统,特异元素,或,代数常数,。,比如：,、,、,第29页,9.2,代数系统,三、子代数系统、子代数定义,(,定义,9.13),设,V=S,f,1,f,2,f,k,是代数系统，,B,S,且,B,，假如,B,对,f,1,f,2,f,k,都是封闭，且,B,和,S,含有相同代数常数，则称,是,V,子代数系统，简称子代数。,比如：,v1=,v2=,第30页,9.2,代数系统,例,12,：,设,V=,，令,nZ=nz|z,Z,.n,为自然数，,那么，,是否为,V,子代数？,第31页,9.2,代数系统,四、平凡子代数与真子代数定义,对任何代数系统,V=S,f,1,f,2,f,k,，最大子代数就是,V,本身。假如令,V,中全部代数常数组成集合是,B,，且,B,对,V,中全部运算都是封闭，则，,B,就组成了,V,最小子代数。这种最小和最大子代数称为,V,平凡子代数。,假如代数系统,V,子代数,V,=B,f1,f2,fk,，满足,B,S,，则称,V,为,V,真子代数。,第32页,9.2,代数系统,五、积代数定义（定义,9.14,）,设,V,1,=,V,2,=,是代数系统，,和*为二元运算。,V,1,和,V,2,积代数,V,1,V,2,是含有一个二元运算代书系统，即,V,1,V,2,=,其中,S=S,1,S,2,对任意,S,1,S,2,有,=,第33页,9.2,代数系统,例,13,：,设,V,1,=,，,V,2,=,求,V,1,与,V,2,积代数。,V1V2=,其中：,=,第34页,9.2,代数系统,六、同态定义,(,定义,9.15),设,V,1,=,V,2,=,是代数系统，,和*是二元运算。假如存在映射,：,S,1,S,2,，若,x,，,yS,1,都有,(x,b)=(x)*(y),则称是,V,1,到,V,2,同态映射,，简称,同态,。,第35页,9.2,代数系统,例,14,：,(1)G,1,=,，,G,2,=,令,：,Z,Z,n,，,(x)=(x)mod,n则是否为,G,1,到,G,2,同态？,第36页,9.2,代数系统,例,15,：,(2)G,1,=,，,G,2,=,令,：,RR,+,，,(x)=e,x,则是否为,G1,到,G2,同态,？,第37页,9.2,代数系统,七、同态象定义,(,定义,9.16),设,是,V,1,=,到,V,2,=,同态，则称,是,V,1,在,下象。,第38页,9.2,代数系统,八、满同态、单同态、同构和自同态,(,定义,9.17),(1),若,：,G,1,G,2,是满射，则称为,满同态,，这时也称,G2,是,G1,同态像,，记作 。,(2),若,：,G,1,G,2,是单射，则称为,单同态,。,(3),若,：,G,1,G,2,是双射，则称为,同构,，记作 。,(4),若,G,1,=G,2,，则称是群,G,自同态,。,第39页,9.2,代数系统,例,16,：,设,V=,，其中,为普通成法。对任意,xR,+,令,1,(x)=|x|,，,2,(x)=2x,3,(x)=x,2,4,(x)=1/x,5,(x)=-x,则分析他们是否为,V,到,V,同态，假如是，则分别为何同态。,第40页,第九章 代数系统介绍,9.1,二元运算及其性质,9.2,代数系统,9.3,几个经典代数系统,半群与群,第41页,(1),半群与群,一、半群定义,(,定义,9.13),（,1,）设,V=,是代数系统，,为二元运算，假如,是可结合，则称,V,为,半群,。,（,2,）设,V=,是半群，,若,eS,是关于,运算单位,元，则称,V,是,含幺半群,，也叫,独异点,。有时也将,独异点,V,记作,。,第42页,(1),半群与群,例,1,：,(1),都是半群，其中,+,表示普通加法。,(2),是半群，其中 是有穷字母表，表示连接运算,。,(3),是半群，也是独异点，其中为集合对称差运算,。,(4),是半群，其中,Z,n,=0,1,n-1,表示模,n,加法,。,第43页,(1),半群与群,二、幂运算定义,半群,V=,，对于任意,x,S,，要求：,普通乘法幂、关系幂等都遵照这个幂运算规则。,幂运算运算规则：,对独异点有：,第44页,(1),半群与群,三、子半群定义,半群子代数叫做,子半群,，独异点子代数叫做,子独,异点,。若,V=,是半群，,T,S,，只要,T,对,V,中运算,封闭，那么,就是,V,子半群,。而对独异点,V=,来说，,T,S,，不但,T,对,V,中运算封闭，而,且,eT,，这时,才组成,V,子独异点,。,第45页,(1),半群与群,例,2,：设独异点,V,1,=,，,V,2,=,V,2,是否为,V,1,子独异点？,第46页,(1),半群与群,四、积半群,设,V,1,=,，,V,2,=,是半群（或独异点），,则,V,1,V,2,=,也是半群，且,：,，,S,1,S,2,，,=,称,V1V2,为,V,1,和,V,2,积半群,。,若,V,1,和,V,2,是独异点，其单位元为,e,1,和,e,2,，则,是,V,1,V,2,中单位元。所以,V,1,V,2,也是独异点。,第47页,(1),半群与群,五、半群同构,(1),设,V,1,=,，,V,2,=,是半群，,:S,1,S,2,。若对任意,x,，,yS,1,有,(xy)=(x),*,(y),则称为半群,V,1,到,V,2,同态映射,，简称为,同态,。,(2),设,V,1,=,，,V,2,=,是独异点，,:S,1,S,2,。,若对任意,x,，,yS,1,有,(xy)=(x),*,(y),且,(e,1,)=e,2,则称为独异点,V,1,到,V,2,同态映射,，简称为,同态,。,第48页,(1),半群与群,例,3,：设半群,V,1,=,，独异点,V,2,=,。其中,为矩阵乘法，,e,为,2,阶单位矩阵。令,则是半群,V,1,=,到本身同态，称,V,1,自同态。但,不是独异点,V,2,=,自同态。,第49页,(1),半群与群,六、群定义,(,定义,9.14),设,是代数系统，,为二元运算。假如,运算是可,结合，存在单位元,eG,，而且对于,G,中任何元素,x,都有 ,G,，则称,为群。,第50页,(1),半群与群,例,6,：,(1),，其中,+,表示普通加法。,(2),其中 是有穷字母表，表示连接运算,。,(3),，其中为集合对称差运算,。,(4),，其中,Z,n,=0,1,n-1,表示模,n,加法,。,第51页,(1),半群与群,例,7,：设,G=e,a,b,c,为,G,上二元运算,它由一下运,算表给出,。判断,是否为群,?,e,a,b,c,e,e,a,b,c,a,a,e,c,b,b,b,c,e,a,c,c,b,a,e,第52页,(1),半群与群,例,8,：设,是群,在,G,1,G,2,上定义二元运算,以下：,G,1,G,2,=,称,是,G,1,与,G,2,直积。则,是否,是群？,第53页,(1),半群与群,七、群相关概念定义,(1),若群,G,是有穷集，则称,G,是,有限群,，不然称为,无限群,。,群,G,基数称为群,G,阶,。,(2),只含单位元群称为,平凡群,。,(3),若群,G,中二元运算是,可交换,，则称,G,为,交换群,或,阿贝尔群,。,第54页,(1),半群与群,八、群幂次定义,注：,半群和特异点不一样，群中元素能够定义负整数次幂。,设,G,是群，,a,G,，,nZ,，则,an,次幂,第55页,(1),半群与群,九、元素阶、无限阶元,设,G,是群，,a,G,，使得等式,成立最小正整数,k,称为,a,阶,，记作,|a|=k,，这是也称,a,为,k,阶元,。若不存在这么正整数,k,，则称,a,为,无限阶,元,。,第56页,(1),半群与群,十、群中元素阶性质,为群，,aG,，且,|a|=r,。设,k,是整数，则,例：设,G,是群，,a,，,b,G,是有限阶元。证实,第57页,(1),半群与群,十一、群幂运算定理,(,定理,9.4),设,G,是群，则,G,中幂运算满足：,第58页,(1),半群与群,十二、方程唯一解定理,(,定理,9.5),G,为群，,a,bG,，方程,ax=b,和,ya=b,在,G,中有解且有唯一解。,例,9,：设群,G=,，其中,为集合对称差运,算,。解以下方程：,a X=,，,Y a,b=b,第59页,(1),半群与群,十三、群中二元运算消去律,(,定理,9.6),G,为群，,则,G,中适合消去律，即对任意,a,b,cG,有,(1),若,ab=ac,，则,b=c,。,(2),若,ba=ca,，则b=c,。,例,10,：设,G,为群，,a,bG,，,k,，证实,第60页,(1),半群与群,例,11,：设,G,为群，,a,，,b,G,，且,证实,ab=ba,。,第61页,(1),半群与群,十四、子群定义,(,定义,9.15),设,群,，,H,是,G,非空子集，假如,H,关于,G,中运算*组成群，则称,H,是,G,子群，记作,H G,。若,H,是,G,子群，,HG,，则称,H,是,G,真子群，记作,HG,。,注：,G,和,e,是,G,平凡子群。,第62页,(1),半群与群,十五、子群判定定理一,(,定理,9.8),设,G,是,群，,H,是,G,非空子集。如对任意,x,yH,都有,xy,-1,H,则,H,是,G,子群。,第63页,(1),半群与群,例：设,G,为群，,，令,即全部幂组成集合，则求证是子群。,第64页,(1),半群与群,十六、循环群定义,(,定义,9.16),设,G,是群，若存在,aG,使得,G=|kZ,则称,G,是,循环群,，记作,G=,，称,a,为,G,生成元,。,注：,(1),任何素数阶群都是循环群。,(2),循环群生成元可能不止一个。,第65页,(1),半群与群,例,13,：,(1)G=,是否为循环群？,(2)G=,是否为循环群？,(3)G=,是否为循环群？,(4)G=,，,是模,n,加法，则,G,是否为循环群？,(5)G=P(A),是否为循环群？,(6)G=nZ,+,是否为循环群？,第66页,(1),半群与群,例,14,：设,A=1,2,3,4,5,组成群，其中,为集,合对称差。,（,1,）求解群方程,1,3X=3,4,5,（,2,）令,B=1,4,5,，求由,B,生成循环子群,第67页,(1),半群与群,十七、循环群生成元求法,设,G=,是循环群。,（,1,）若,G,是无限循环群，则,G,只有两个生成元，即,a,和,（,2,）若,G,是,n,阶循环群，则,G,含有,(n),个生成元。对于任何,小于等于,n,且与,n,互素正整数,r,，是,G,生成元。,第68页,(1),半群与群,例,15,：,(1),设,G=e,a,a,11,是,12,阶循环群，则它生成元,有几个，分别是什么？,(2)G=,是模,9,整数加群，则它生成原有几个，,分别是什么？,(3)G=,，则,G,上生成元有几个，分别是什么？,第69页,(1),半群与群,十八、循环群子群求法,（,1,）设,G=,是循环群，则其全部子群均为循环群,（,2,）,设,G=,是无限循环群，则,G,子群除,e,外都是无限,循环群。,（,3,）设,G=,是,n,阶循环群，则对,n,每个正因子,d,，,G,恰好含,有一个,d,阶子群。,第70页,(1),半群与群,例,16,：,G=,是无限循环群，其生成元为,1,和,1,，则,列出,G,全部循环子群。,=0=0Z,=,，,-1,0,1,=Z,4,，,-2,0,2,4,=2Z,=-2n,，,-n,0,n,2n,=nZ,第71页,(1),半群与群,例,17,：,G=,是,12,阶循环群，列出,G,全部子群。,=Z,12,=0,2,4,6,8,10,=0,3,6,9,=0,4,8,=0,6,12,正因子为：,1,2,3,4,6,12,=0,第72页,(1),半群与群,例,18,：设,G,1,=e,a,2,a,-2,a,4,a,-4,是无限循环群，,则,G,1,子群是什么？,=e,=e,a,2m,a,-2m,a,4m,a,-4m,m,是正整数,第73页,(1),半群与群,例,19,：设,G,2,=,是,9,阶循环群，则,G,2,子群是什么？,=G,2,=e,a,6,a,12,9,正因子有：,1,3,9,=e,第74页,(1),半群与群,十九、置换定义,(,定义,9.17),设,S=1,2,n,，,S,上任何双射函数,：,SS,称为,S,上,n,元置换。普通将,n,元置换记为,第75页,(1),半群与群,S=1,2,3,4,5,则,都是五元置换。,1,2,3,4,5,1,2,3,4,5,1,2,3,4,5,1,2,3,4,5,第76页,(1),半群与群,二十、,k,阶轮换定义,设,是,S=1,2,n,上,n,元置换，若,(i,1,)=i,2,(i,2,)=i,3,(i,k,)=i,1,且保持,S,中其它元素不变，则称为,S,上,k,阶轮换，记作,(i,1,i,2,i,k,),。若,k=2,，则也称为,S,上对换。,第77页,(1),半群与群,例,20,：,是几阶轮换？,呢？,第78页,(1),半群与群,例,21,：设,S=1,2,8,它们轮换表示式是什么？,怎样用对换来表示它们？,=(15236)(4)(78),=(18342)(567),第79页,(1),半群与群,二十一、,n,元对称群定义,S,n,：全部,n,元置换集合；,：两个,n,元置换积；,则,为,n,元对称群。,第80页,(1),半群与群,例,22,：设,S=1,2,3,则,3,元对称群以下：,S,3,=(1),(1,2),(1,3),(2,3),(1,2,3),(1,3,2),(1),(1,2),(1,3),(2,3),(1,2,3),(1,3,2),(1),(1),(1,2),(1,3),(2,3),(1,2,3),(1,3,2),(1,2),(1,2),(1),(1,2,3),(1,3,2),(1,3),(2,3),(1,3),(1,3),(1,3,2),(1),(1,2,3),(2,3),(1,2),(2,3),(2,3),(1,2,3),(1,3,2),(1),(1,2),(1,3),(1,2,3),(1,2,3),(2,3),(1,2),(1,3),(1,3,2),(1),(1,3,2),(1,3,2),(1,3),(2,3),(1,2),(1),(1,2,3),第81页,11.7,循环群与置换群,二十二、,n,元置换群定义,S,n,全部子群都叫,n,元置换群。,第82页,11.7,循环群与置换群,例,23,：,S,3,=(1),(1,2),(1,3),(2,3),(1,2,3),(1,3,2),子群有：,1,阶子群：,(1);,2,阶子群：,(1),(1,2);,2,阶子群：,(1),(1,3);,2,阶子群：,(1),(2,3);,3,阶子群：,(1),(1,2,3),(1,3,2);,6,阶子群：,(1),(1,2),(1,3),(2,3),(1,2,3),(1,3,2),。,第83页,