离散数学第五版第九章(耿素云、屈婉玲、张立昂编著)ppt课件

.,离散数学,.,第9章代数系统简介,9.1二元运算及其性质9.2代数系统9.3几个典型的代数系统,.,9.1二元运算及其性质,一、二元运算的定义(定义9.1),设S为集合，函数f:SSS称为S上的二元运算，简称为二元运算。,如何判断一个运算是否为集合S上的二元运算？,S中任意两个元素均可以进行这种运算，且运算的结果是唯一的。,S中任意两个元素的运算结果都属于S，即S对该运算是封闭的。,.,9.1二元运算及其性质,例1：,.,9.1二元运算及其性质,例2：,例3：S为任意集合，则在f:P(A)P(A)P(A)上，、是否为二元运算？,.,9.1二元运算及其性质,二、n元运算的定义(定义9.2),设S为集合，n为正整数，则函数f：SSSS称为S上的一个n元运算，简称为n元运算。,（1）当n=1时，则函数f:SS为S上的一元运算，如(x)=y,（2）当n=2时，则函数f:SSS为S上的二元运算。(x，y)=z,（3）当n=3时，则函数f:SSSS为S上的三元运算。(x，y，z)=t,.,9.1二元运算及其性质,例4：在整数集合Z、有理数集合Q、实数集合R上，一个数的相反数、倒数是否为这些集合上的一元运算？,例5：在幂集P(S)上，如果规定全集为S，则求集合的绝对补运算是否为P(S)上的一元运算？,.,9.1二元运算及其性质,例6：设S=1,2,给出P(S)上的运算和的运算表，其中全集为S。,P(S)=,1,2,1,2,.,9.1二元运算及其性质,例7：设S=1,2,3,4,定义S上的二元关系如下：xy=(x*y)mod5x,yS。求的运算列表。,.,9.1二元运算及其性质,三、二元运算的主要性质,设为S上的二元运算.如果对于任意的x,yS都有xy=yx则称运算在S上是可交换的,或者说运算在S上适合交换律.,（1）交换律（定义9.3）,注:对于二元运算矩阵来说,二元运算满足交换律,则二元运算矩阵关于主对角线对称。,.,9.1二元运算及其性质,设为S上的二元运算.如果对于任意的x,y,zS都有(xy)z=x(yz)则称运算在S上是可结合的,或者说运算在S上适合结合律.,（2）结合律（定义9.3）,注:整数集Z、自然数集N、有理数集Q、实数集R上的加法和乘法都是可结合的；矩阵的加法和乘法也是可结合的；集合的、也是可结合的；函数的复合运算也是可结合的。,.,9.1二元运算及其性质,设为S上的二元运算,如果对于任意的xS都有xx=x则称运算在S上适合等幂律.,（3）幂等律（定义9.3）,集合的、是复合等幂律的。,.,9.1二元运算及其性质,设和*是S上的两个二元运算,如果对于任意的x，y，zS有x*(yz)=(x*y)(x*z)(左分配律)(yz)*x=(y*x)(z*x)(右分配律)则称运算*对是可分配的，也称*对适合分配律。,（4）分配律（定义9.4）,.,9.1二元运算及其性质,设和*是S上的两个可交换的二元运算,如果对于任意的x，yS有x*(xy)=xx(x*y)=x则称运算*和满足吸收律。,（5）吸收律（定义9.5）,例如：幂集P(S)上的和运算满足吸收律。即A,BP(S)有A(AB)=AA(AB)=A,.,9.1二元运算及其性质,四、单位元和幺元,设为S上的二元运算,如果存在(或)S使得对于任何xS都有x=x(或x=x)则称(或)是S中关于运算的一个左幺元(或右幺元)。若eS关于运算既是左幺元又是右幺元，则称e为S上关于运算的幺元。,幺元的定义（定义9.6）,.,9.1二元运算及其性质,例8：自然数集N上的加法幺元，幺元是。自然数集N上的乘法幺元，幺元是。自然数集N上的除法幺元，幺元是。幂集P(S)上的运算幺元，幺元是。幂集P(S)上的运算幺元，幺元是。,.,9.1二元运算及其性质,设为S上的二元运算,，分别为运算的左幺元和右幺元，则有=e且e为S上关于运算的唯一的幺元。,单位元和幺元的唯一定理（定理9.1）,.,9.1二元运算及其性质,四、零元,设为S上的二元运算,如果存在(或)S使得对于任何xS都有x=(或x=)则称(或)是S中关于运算的一个左零元(或右零元)。若S关于运算既是左零元又是右零元，则称为S上关于运算的零元。,零元的定义（定义9.6）,.,9.1二元运算及其性质,例9：自然数集N上的加法零元，零元是。自然数集N上的乘法零元，零元是。自然数集N上的除法零元，零元是。幂集P(S)上的运算零元，零元是。幂集P(S)上的运算零元，零元是。,.,9.1二元运算及其性质,设为S上的二元运算,，分别为运算的左零元和右零元，则有=且为S上关于运算的唯一的零元。,零元的唯一定理（定理9.2）,.,9.1二元运算及其性质,设为S上的二元运算,e，分别为运算的幺元和零元，如果S至少有两个元素，则e。,幺元与零元的定理,证明：假设e=,则xS有x=ex=x=则x=e,S中只有一个元素又因为S中至少有两个元素，矛盾所以：e,.,9.1二元运算及其性质,五、逆元,逆元的定义（定义9.6）,设为S上的二元运算,eS为运算的幺元，对于xS，如果存在使得则称是x的左逆元（或右逆元）。若yS既是x的左逆元又是x的右逆元，则称y是x的逆元。如果x的逆元存在，则称x是可逆的。,.,9.1二元运算及其性质,逆元的唯一定理（定理9.3）,设为S上可结合的二元运算,eS为运算的单位元，对于xS，如果存在左逆元和右逆元则有则y是x的唯一逆元。,.,9.1二元运算及其性质,六、消去律（定义9.7）,设为S上的二元运算,如果对于任意的x,y,zS满足以下条件：(1)若xy=xz且x，则y=z。(2)若yx=zx且x，则y=z。那么称运算满足消去律，其中(1)称作左消去律，(2)称作右消去律。,.,9.1二元运算及其性质,例10：设是字母的有穷集，称为字母表，中的有限个字母组成的序列称为上的串，对任何串，串中字母的个数叫做串的长度，记作|，长度是0的串叫空串，记作，对任给的自然数k，令它是上所有长度为k的串的集合，特别的：串的连接运算：,.,第九章代数系统的一般性质,9.1二元运算及其性质9.2代数系统9.3几个典型的代数系统,.,9.2代数系统,一、代数系统的定义(定义9.8),非空集合S和S上k个运算f1,f2fk(其中fi为ni元运算，i=1，2,，k)组成的系统称为一个代数系统，简称代数，记作。,判断代数系统的方法：判断该系统中的每个运算是否为n元运算。,.,9.2代数系统,例11：、是否为代数系统？,是否为代数系统？,.,9.2代数系统,二、特异元素、代数常数的定义,代数系统中对于给定的二元运算存在幺元或零元，并且它们对该系统的性质起着重要的作用，称之为该系统的特异元素或代数常数。,例如：、,.,9.2代数系统,三、子代数系统、子代数的定义(定义9.13),设V=S,f1,f2,fk是代数系统，BS且B，如果B对f1,f2,fk都是封闭的，且B和S含有相同的代数常数，则称是V的子代数系统，简称子代数。,例如：v1=v2=,.,9.2代数系统,例12：设V=，令nZ=nz|zZ.n为自然数，那么，是否为V的子代数？,.,9.2代数系统,四、平凡子代数与真子代数的定义,对任何代数系统V=S,f1,f2,fk，最大的子代数就是V本身。如果令V中所有的代数常数构成的集合是B，且B对V中所有的运算都是封闭的，则，B就构成了V的最小子代数。这种最小和最大子代数称为V的平凡子代数。,如果代数系统V的子代数V=B,f1,f2,fk，满足BS，则称V为V的真子代数。,.,9.2代数系统,五、积代数定义（定义9.14）,设V1=,V2=是代数系统，和*为二元运算。V1和V2的积代数V1V2是含有一个二元运算的代书系统，即V1V2=,其中S=S1S2,对任意的,S1S2有=,.,9.2代数系统,例13：设V1=，V2=,求V1与V2的积代数。,V1V2=,其中：=,.,9.2代数系统,六、同态的定义(定义9.15),设V1=,V2=是代数系统，和*是二元运算。如果存在映射：S1S2，若x，yS1都有(xb)=(x)*(y)则称是V1到V2的同态映射，简称同态。,.,9.2代数系统,例14：(1)G1=，G2=,令：ZZn，(x)=(x)modn则是否为G1到G2的同态？,.,9.2代数系统,例15：(2)G1=，G2=,令：RR+，(x)=ex则是否为G1到G2的同态？,.,9.2代数系统,七、同态象的定义(定义9.16),设是V1=到V2=的同态，则称是V1在下的象。,.,9.2代数系统,八、满同态、单同态、同构和自同态(定义9.17),(1)若：G1G2是满射的，则称为满同态，这时也称G2是G1的同态像，记作。,(2)若：G1G2是单射的，则称为单同态。,(3)若：G1G2是双射的，则称为同构，记作。,(4)若G1=G2，则称是群G的自同态。,.,9.2代数系统,例16：设V=，其中为普通成法。对任意xR+令1(x)=|x|，2(x)=2x,3(x)=x2,4(x)=1/x,5(x)=-x,则分析他们是否为V到V的同态，如果是，则分别为什么同态。,.,第九章代数系统简介,9.1二元运算及其性质9.2代数系统9.3几个典型的代数系统半群与群,.,(1)半群与群,一、半群的定义(定义9.13),（1）设V=是代数系统，为二元运算，如果是可结合的，则称V为半群。,（2）设V=是半群，若eS是关于运算的单位元，则称V是含幺半群，也叫独异点。有时也将独异点V记作。,.,(1)半群与群,例1：,(1),都是半群，其中+表示普通加法。,(2)是半群，其中是有穷字母表，表示连接运算。,(3)是半群，也是独异点，其中为集合的对称差运算。,(4)是半群，其中Zn=0,1,n-1,表示模n的加法。,.,(1)半群与群,二、幂运算的定义,半群V=，对于任意xS，规定：普通乘法的幂、关系的幂等都遵循这个幂运算规则。,幂运算的运算规则：,对独异点有：,.,(1)半群与群,三、子半群的定义,半群的子代数叫做子半群，独异点的子代数叫做子独异点。若V=是半群，TS，只要T对V中的运算封闭，那么就是V的子半群。而对独异点V=来说，TS，不仅T对V中的运算封闭，而且eT，这时才构成V的子独异点。,.,(1)半群与群,例2：设独异点V1=，V2=,V2是否为V1的子独异点？,.,(1)半群与群,四、积半群,设V1=，V2=是半群（或独异点），则V1V2=也是半群，且：，S1S2，=称V1V2为V1和V2的积半群。,若V1和V2是独异点，其单位元为e1和e2，则是V1V2中的单位元。因此V1V2也是独异点。,.,(1)半群与群,五、半群的同构,(1)设V1=，V2=是半群，:S1S2。若对任意的x，yS1有(xy)=(x)*(y)则称为半群V1到V2的同态映射，简称为同态。,(2)设V1=，V2=是独异点，:S1S2。若对任意的x，yS1有(xy)=(x)*(y)且(e1)=e2则称为独异点V1到V2的同态映射，简称为同态。,.,(1)半群与群,例3：设半群V1=，独异点V2=。其中为矩阵乘法，e为2阶单位矩阵。令则是半群V1=到自身的同态，称V1的自同态。但不是独异点V2=自同态。,.,(1)半群与群,六、群的定义(定义9.14),设是代数系统，为二元运算。如果运算是可结合的，存在单位元eG，并且对于G中的任何元素x都有G，则称为群。,.,(1)半群与群,例6：,(1),，其中+表示普通加法。,(2)其中是有穷字母表，表示连接运算。,(3)，其中为集合的对称差运算。,(4)，其中Zn=0,1,n-1,表示模n的加法。,.,(1)半群与群,例7：设G=e,a,b,c,为G上的二元运算,它由一下运算表给出。判断是否为群?,.,(1)半群与群,例8：设,是群,在G1G2上定义二元运算如下：,G1G2,=称是G1与G2的直积。则是否是群？,.,(1)半群与群,七、群的相关概念定义,(1)若群G是有穷集，则称G是有限群，否则称为无限群。群G的基数称为群G的阶。,(2)只含单位元的群称为平凡群。,(3)若群G中的二元运算是可交换的，则称G为交换群或阿贝尔群。,.,(1)半群与群,八、群的幂次定义,设G是群，aG，nZ，则a的n次幂,.,(1)半群与群,九、元素的阶、无限阶元,设G是群，aG，使得等式成立的最小正整数k称为a的阶，记作|a|=k，这是也称a为k阶元。若不存在这样的正整数k，则称a为无限阶元。,.,(1)半群与群,十、群中元素阶的性质,为群，aG，且|a|=r。设k是整数，则,例：设G是群，a，bG是有限阶元。证明,.,(1)半群与群,十一、群的幂运算定理(定理9.4),设G是群，则G中的幂运算满足：,.,(1)半群与群,十二、方程唯一解定理(定理9.5),G为群，a,bG，方程ax=b和ya=b在G中有解且有唯一解。,例9：设群G=，其中为集合的对称差运算。解下列方程：aX=，Ya,b=b,.,(1)半群与群,十三、群中二元运算的消去律(定理9.6),G为群，则G中适合消去律，即对任意a,b,cG有(1)若ab=ac，则b=c。(2)若ba=ca，则b=c。,例10：设G为群，a,bG，k，证明,.,(1)半群与群,例11：设G为群，a，bG，且证明ab=ba。,.,(1)半群与群,十四、子群的定义(定义9.15),设群，H是G的非空子集，如果H关于G中的运算*构成群，则称H是G的子群，记作HG。若H是G的子群，HG，则称H是G的真子群，记作HG。,注：G和e是G的平凡子群。,.,(1)半群与群,十五、子群判定定理一(定理9.8),设G是群，H是G的非空子集。如对任意x,yH都有xy-1H则H是G的子群。,.,(1)半群与群,例：设G为群，令即的所有幂构成的集合，则求证是的子群。,.,(1)半群与群,十六、循环群的定义(定义9.16),设G是群，若存在aG使得G=|kZ则称G是循环群，记作G=，称a为G的生成元。,注：(1)任何素数阶的群都是循环群。(2)循环群的生成元可能不止一个。,.,(1)半群与群,例13：,(1)G=是否为循环群？,(2)G=是否为循环群？,(3)G=是否为循环群？,(4)G=，是模n的加法，则G是否为循环群？,(5)G=P(A),是否为循环群？,(6)G=nZ,+是否为循环群？,.,(1)半群与群,例14：设A=1,2,3,4,5,构成群，其中为集合的对称差。（1）求解群方程1,3X=3,4,5（2）令B=1,4,5，求由B生成的循环子群,.,(1)半群与群,十七、循环群生成元的求法,设G=是循环群。（1）若G是无限循环群，则G只有两个生成元，即a和（2）若G是n阶循环群，则G含有(n)个生成元。对于任何小于等于n且与n互素的正整数r，是G的生成元。,.,(1)半群与群,例15：,(1)设G=e,a,a11是12阶循环群，则它的生成元有几个，分别是什么？,(2)G=是模9的整数加群，则它的生成原有几个，分别是什么？,(3)G=，则G上的生成元有几个，分别是什么？,.,(1)半群与群,十八、循环群的子群求法,（1）设G=是循环群，则其所有的子群均为循环群（2）设G=是无限循环群，则G的子群除e外都是无限循环群。（3）设G=是n阶循环群，则对n的每个正因子d，G恰好含有一个d阶子群。,.,(1)半群与群,例16：G=是无限循环群，其生成元为1和1，则列出G的所有循环子群。,=0=0Z,=，-1,0,1,=Z,=-4，-2,0,2,4,=2Z,=-2n，-n,0,n,2n,=nZ,.,(1)半群与群,例17：G=是12阶循环群，列出G的所有子群。,=Z12,=0,2,4,6,8,10,=0,3,6,9,=0,4,8,=0,6,12的正因子为：1,2,3,4,6,12,=0,.,(1)半群与群,例18：设G1=e,a2,a-2,a4,a-4,是无限循环群，则G1的子群是什么？,=e,=e,a2m,a-2m,a4m,a-4m,m是正整数,.,(1)半群与群,例19