离散数学第讲省公开课一等奖全国示范课微课金奖PPT课件.pptx

,第十一章 半群与群,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,离散数学第20讲,回顾上节课基本知识点：,1、二元运算定义及其性质,2、代数系统,？,想一想，我们上节课学习了什么？,1,第1页,离散数学第20讲,1、半群、独异点、群定义。,2、相关性质、运算和判定方法。,？,今天学习什么呢？,2,第2页,第十一章 半群与群,11.1 半群与独异点,含有一个二元运算代数系统,定义11.1,(1)设V=是代数系统，,。,为二元运算，假如,。,是可结合，则称V为,半群,。,(2)设V=是半群，若e,S,是关于,。,运算单位元，则称V是,幺半群,，也叫,独异点,。有时记作。,3,第3页,例11.1 考查以下代数系统哪些是半群？哪些是,幺半群,？,(1),。,(2),其中M,n,(R)为n阶实矩阵。,(3),其中,为集合B上对称差运算,。(,P101集合运算性质,),(4),其中Z,n,=0,1,n-1,为模n加法运算,即xy=(x+y)mod n,。,(5),其中,。,为集合S上复合运算。,(6),其中为非零实数集合，,。,运算定义为：,a,b,S,a,。,b=b,第十一章 半群与群,4,第4页,第十一章 半群与群,练习 考查以下集合和运算哪些能够组成半群？哪些能够组成幺半群？,(1)S,1,=1,1/2,2,1/3,3,1/4,*为普通乘法。,(2)S,2,=a,1,a,2,a,n,n,Z,*定义为:a,i,*a,j,=a,i,i,j,S,2,。,(3)S,3,=0,1,*为普通乘法。,(4)S,4,=1,2,3,6,x*y表示求x和y最小公倍数，x,y,S,4,。,(5)S,5,=0,1,*为模2加法。,解：,(1)不是代数运算。,(2)是半群。,(3)独异点，幺元为1。,(4)独异点，幺元为1。,(5)独异点，幺元为0。,5,第5页,第十一章 半群与群,半群幂运算,对于半群V=中，x,S，,要求：,x,1,=x,x,n+1,=x,n,。x,n,Z,+,用数学归纳法易证得：x,n,。x,m,=x,n+m,(x,n,),m,=x,nm,m,n,Z,+,独异点是特殊半群，故也含有以上幂运算，只是：,x,0,=e,x,n+1,=x,n,。x,n,N,本页知识只需了解，不作重点要求。,6,第6页,第十一章 半群与群,子半群半群子代数,假如V=是半群，T,S，假如 T 对 V 中。运算封闭，则就是V子半群。,子独异点独异点子代数,假如V=是独异点，T,S，假如 T 对 V 中。运算。封闭，且e,T,，则就是V子独异点。,7,第7页,第十一章 半群与群,例题11.2,设半群V,1,=,独异点V,2,=,其中.为矩阵乘法,S=a,d,R ,e为2阶单位矩阵 ,则,a 0,0 d,1 0,0 1,T=a,R,a 0,0 0,V,3,=是否为半群或独异点?是否为V,1,子半群或V,2,子独异点?其中,8,第8页,第十一章 半群与群,解:,T,对矩阵乘法.是可结合,故V,3,是半群。,T,S,V,3,是V,1,子半群。,V,3,存在自己幺元,1 0,0 0,V,3,是独异点。,V,3,不是V,2,子独异点，因为V,2,幺元e=,T,1 0,0 1,9,第9页,第十一章 半群与群,11.2 群定义和性质,定义11.4,设是代数系统，,。,为二元运算，假如,。,是,可结合,，存在,单位元e,S,，,且,x,G,都,x,-1,G,，则称G为,群,。,例 考查以下代数系统哪些是群？,(1),。,(2),M,n,(R)为n阶实矩阵。,(3),为集合B上对称差运算,。,(4),其中Z,n,=0,1,n-1,为模n加法运算,即xy=(x+y)mod n,。,10,第10页,第十一章 半群与群,练习1：考查以下代数系统哪些是群？,(1),其中G=a,n,|a,Z,+,n,Z,*为普通乘法。,(2),其中*为普通乘法。,(3),其中*为普通加法。,解：,(1)是群，其中单位元为a,0,a,n,逆元为a-,n,。,(2)是群，其中单位元为1,x逆元为1/x。,(3)不是群。,11,第11页,第十一章 半群与群,练习2：,设V=,其中*定义以下：,a，bZ,a*b=a+b-2 请验证V是群。,解：,显然*运算在Z上,是封闭。,a，b,cZ,(a*b)*c=(a+b-2)*c=(a+b-2)+c-2=a+b+c-4,a*(b*c)=a*(b+c-2)=a+(b+c-2)-2=a+b+c-4,*运算是可结合,。,aZ,a*2=a+2-2=a=2+a-2=2*a,2是*运算,单位元。,aZ都存在逆元,a-1=4-a,总而言之，V是群,。,12,第12页,第十一章 半群与群,定义11.5 群中惯用概念或术语,(1),若群G是有穷集，则称G是有限群，不然称为无限群。群G基数称为群G阶。,(2)只含单位元群称为平凡群。,(3)若群G中二元运算是可交换，则称G是可交换群或阿贝尔(Abel)群。,13,第13页,第十一章 半群与群,练习：考查以下代数系统哪些是有限群，无限群，可交换群？,(1),其中G=a,n,|a,Z,+,n,Z,*为普通乘法。,(2),其中Z,n,=0,1,n-1,为模n加法运算,即xy=(x+y)mod n,。,(3),M,n,(R)为可逆矩阵。,解：,(1)无限群，可交换群。,(2)n阶有限群，可交换群。,(3)无限群。,14,第14页,第十一章 半群与群,定义11.6 群幂运算,设G是,群，a,G,n,Z,则an次幂,e n=0,a,n,=a,n-1,a n0,(a,-1,),m,n0,n=-m,练习：在,中,求3,0,、3,3,、3,-2,。,解,：3,0,=0,3,3,=3,2,3,1,=3,1,3,1,3,1,=1,3,-2,=(3,-1,),2,=(1),2,=1,1,=2,15,第15页,第十一章 半群与群,定义11.7,设G是群，a,G,使得等式,a,k,=e,成立最小正整数k称为a阶，也称为a周期，记作|a|=k,也称a为k阶元。若不存在这么正整数k,则称a为无限阶元,。,16,第16页,第十一章 半群与群,练习：在中,求各元素阶。,解：1,4,=1,1 1 1,=0 1为4阶元,同理可求得：2为2阶元,3为4阶元,0为1阶元,17,第17页,第十一章 半群与群,定理11.1,设G为,群，,则G中幂运算满足：,(1),a,G,(a,-1,),-1,=a。,(2),a,b,G,(ab),-1,=b,-1,a,-1,。,(3),a,G,a,n,a,m,=a,n+m,n,m,Z,。,(4),a,G,(a,n,),m,=a,nm,n,m,Z,。,(5)若G为交换群，则(ab,),n,=a,n,b,n,n,Z,。,18,第18页,第十一章 半群与群,证实关键点：,(1)a,-1,是a逆元，而a也是a,-1,逆元，由逆元唯一性知(a,-1,),-1,=a。,(2)abb,-1,a,-1,=aea,-1,=aa,-1,=e 且 b,-1,a,-1,ab=b,-1,eb=bb,-1,=e,(ab),-1,=b,-1,a,-1,(3)、(4)应用数学归纳法，参见书本P234。,(5)(ab)n=ababab=aabb=an bn,n个ab n个a n个b,19,第19页,第十一章 半群与群,定理11.2,设G为群，,a,b,G,方程ax=b和ya=b在G中有唯一解.,证实：,先证实方程ax=b在G中有唯一解.,(1)解存在性证实.,将a,-1,b代入方程左边x得,a(a,-1,b)=(a a,-1,)b=eb=b,a,-1,b是方程解,20,第20页,第十一章 半群与群,(2)解唯一性证实,设c也是方程ax=b解,则应有ac=b,从而有,c=ec=(a-1 a)c=a-1(ac)=a-1b,a-1b 是方程ax=b唯一解.,同理可证实方程ya=b在G中有唯一解.(,自己练习,),21,第21页,第十一章 半群与群,例题11.5,设群G为，其中,为集合对称差运算,解以下方程,a,x=和 y,a,b=b.,证实：,由定理11.2得知:,X=a,-1,又已知群G单位元为,则a,-1,=a,X=a,=a,同理,y=b,a,b,-1,=b,a,b=a,22,第22页,第十一章 半群与群,定理11.3,设G为,群，则G中适合消去律,即对,a,b,c,G有,(1)若 ab=ac,则b=c.,(2)若 ba=ca,则b=c.,(,请自己证实,),23,第23页,第十一章 半群与群,例题11.6,设G为,群,a,b,G,k,Z,+,证实：(a,-1,ba),k,=a,-1,ba,b,k,=b,证实：先证“,”k个,(a,-1,ba),k,=a,-1,ba=,(,a,-1,ba)(,a,-1,ba)(,a,-1,ba)=a,-1,ba=a,-1,b,k,a=a,-1,ba,=b,k,=b,再证“,”k个,(a,-1,ba),k,=,(,a,-1,ba)(,a,-1,ba)(,a,-1,ba)=a,-1,b,k,a=a,-1,ba(b,k,=b),练习,设G为,群,a,b,G,且(ab),2,=a,2,b,2,，证实ab=ba.,证实：(ab),2,=a,2,b,2,=,abab=aabb =ab=ba(,消去律,),24,第24页,离散数学第20讲,本讲小结,1、了解半群、独异点、群概念,2、掌握半群、独异点、群判断,3、掌握半群、独异点、群相关性质,25,第25页,