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

1、12021/3/10离散数学离散数学22021/3/10第第9章章 代数系统简介代数系统简介9.1 二元运算及其性质9.2 代数系统9.3 几个典型的代数系统32021/3/109.1二元运算及其性质二元运算及其性质一、二元运算的定义(定义9.1)设S为集合，函数f:SSS称为S上的二元运算，简称为二元运算。如何判断一个运算是否为集合S上的二元运算？vS中任意两个元素均可以进行这种运算，且运算的 结果是唯一的。vS中任意两个元素的运算结果都属于S，即S对该运 算是封闭的。42021/3/109.1二元运算及其性质二元运算及其性质例1：NNNf:yxyxf),()2yxyxf),() 3yxyx

2、f),()4yxyxf),() 1ZZZf:yxyxf),()2yxyxf),() 3yxyxf),()4yxyxf),() 152021/3/109.1二元运算及其性质二元运算及其性质例2：)*(*:是非零实数其中RRRRfyxyxf),()2yxyxf),() 3yxyxf),()4yxyxf),() 1例3：S为任意集合，则在f:P(A)P(A)P(A)上， 、是否为二元运算？62021/3/109.1二元运算及其性质二元运算及其性质二、n元运算的定义(定义9.2)设S为集合，n为正整数，则函数f：SSSS称为S上的一个n元运算，简称为n n元运算元运算。（1）当n=1时，则函数f:SS

3、为S上的一元运算，如(x)=y（2）当n=2时，则函数f:SSS为S上的二元运算。 (x，y)=z（3）当n=3时，则函数f:SSSS为S上的三元运算。 (x，y，z)=t72021/3/109.1二元运算及其性质二元运算及其性质例4：在整数集合Z、有理数集合Q、实数集合R上，一 个数的相反数、倒数是否为这些集合上的一元运 算？例5：在幂集P(S)上，如果规定全集为S，则求集合的 绝对补运算是否为P(S)上的一元运算？82021/3/109.1二元运算及其性质二元运算及其性质例6：设S=1,2,给出P(S)上的运算和的运算表， 其中全集为S。aiai1,211221,2P(S)=,1,2,1,

4、2121,2121,2111,22221,211,21,22192021/3/109.1二元运算及其性质二元运算及其性质例7：设S=1,2,3,4,定义S上的二元关系如下：xy=(x*y)mod 5 x,yS。求的运算列表。123411234224133314244321102021/3/109.1二元运算及其性质二元运算及其性质三、二元运算的主要性质设为S上的二元运算.如果对于任意的x,yS都有 xy=yx则称运算在S上是可交换的,或者说运算在S上适合交换律.（1）交换律（定义9.3）注:对于二元运算矩阵来说,二元运算满足交换律,则二元 运算矩阵关于主对角线对称。112021/3/109.1

5、二元运算及其性质二元运算及其性质设为S上的二元运算.如果对于任意的x,y,zS都有 (xy)z=x(yz)则称运算在S上是可结合的,或者说运算在S上适合结合律.（2）结合律（定义9.3）注:整数集Z、自然数集N、有理数集Q、实数集R上的加法和 乘法都是可结合的；矩阵的加法和乘法也是可结合的； 集合的、也是可结合的；函数的复合运算也是可 结合的。122021/3/109.1二元运算及其性质二元运算及其性质设为S上的二元运算,如果对于任意的xS都有 xx=x则称运算在S上适合等幂律.（3）幂等律（定义9.3）集合的、是复合等幂律的。132021/3/109.1二元运算及其性质二元运算及其性质设和*

6、是S上的两个二元运算,如果对于任意的x，y，zS有 x*(yz)=(x*y)(x*z) (左分配律)(yz)*x=(y*x)(z*x) (右分配律)则称运算*对是可分配的，也称*对适合分配律。（4）分配律（定义9.4）142021/3/109.1二元运算及其性质二元运算及其性质设和*是S上的两个可交换的二元运算,如果对于任意的x，yS有 x*(xy)=x x(x*y)=x则称运算*和满足吸收律。（5）吸收律（定义9.5）例如：幂集P(S)上的和运算满足吸收律。即A,BP(S)有 A(A B)=AA(A B)=A152021/3/109.1二元运算及其性质二元运算及其性质四、单位元和幺元lere

7、设为S上的二元运算,如果存在 (或 )S使得对于任何xS都有 x = x(或 x =x)则称 (或 )是S中关于运算的一个左幺元(或右幺元)。若eS关于运算既是左幺元又是右幺元，则称e为S上关于运算的幺元。lerelere 幺元的定义（定义9.6）162021/3/109.1二元运算及其性质二元运算及其性质例8：自然数集N上的加法 幺元，幺元是 。自然数集N上的乘法 幺元，幺元是 。自然数集N上的除法 幺元，幺元是 。幂集P(S)上的运算 幺元，幺元是 。幂集P(S)上的运算 幺元，幺元是 。172021/3/109.1二元运算及其性质二元运算及其性质lere设为S上的二元运算, ， 分别为运

8、算的左幺元和右幺元，则有 = =e且e为S上关于运算的唯一的幺元。lere 单位元和幺元的唯一定理（定理9.1）eeeeeeeeeeerlrlrllrrl所以：做为右幺元）（将做为左幺元）（将证： 182021/3/109.1二元运算及其性质二元运算及其性质四、零元lr设为S上的二元运算,如果存在 (或 )S使得对于任何xS都有 x = (或 x = )则称 (或 )是S中关于运算的一个左零元(或右零元)。若S关于运算既是左零元又是右零元，则称为S上关于运算的零元。lrlr 零元的定义（定义9.6）lr192021/3/109.1二元运算及其性质二元运算及其性质例9：自然数集N上的加法 零元，

9、零元是 。自然数集N上的乘法 零元，零元是 。自然数集N上的除法 零元，零元是 。幂集P(S)上的运算 零元，零元是 。幂集P(S)上的运算 零元，零元是 。202021/3/109.1二元运算及其性质二元运算及其性质lr设为S上的二元运算, ， 分别为运算的左零元和右零元，则有 = =且为S上关于运算的唯一的零元。lr 零元的唯一定理（定理9.2）rlrrrlllrl所以：做为右零元）（将做为左零元）（将证： 212021/3/109.1二元运算及其性质二元运算及其性质设为S上的二元运算, e，分别为运算的幺元和零元，如果S至少有两个元素，则e。 幺元与零元的定理证明：假设e=,则xS有x=

10、e x= x=则 x=e ,S中只有一个元素又因为S中至少有两个元素，矛盾所以： e222021/3/109.1二元运算及其性质二元运算及其性质五、逆元 逆元的定义（定义9.6）设为S上的二元运算,eS为运算的幺元，对于xS，如果存在 使得 则称 是x的左逆元（或右逆元）。若yS既是x的左逆元又是x的右逆元，则称y是x的逆元。如果x的逆元存在，则称x是可逆的。)(SySyrl或)(eyxexyrl或 )(rlyy或232021/3/109.1二元运算及其性质二元运算及其性质 逆元的唯一定理（定理9.3）rrrlrlllyyeyxyyxyeyy )()(证：设为S上可结合的二元运算,eS为运算的

11、单位元，对于xS，如果存在左逆元 和右逆元 则有 则y是x的唯一逆元。ly yyyrlry242021/3/109.1二元运算及其性质二元运算及其性质六、消去律（定义9.7）设为S上的二元运算,如果对于任意的x,y,zS满足以下条件：(1)若xy=xz且x，则y=z。(2)若yx=zx且x，则y=z。 那么称运算满足消去律，其中(1)称作左消去律，(2)称作右消去律。252021/3/109.1二元运算及其性质二元运算及其性质例10：设是字母的有穷集，称为字母表，中的有限个字母组成的序列称为上的串，对任何串，串中字母的个数叫做串的长度，记作|，长度是0的串叫空串，记作，对任给的自然数k，令它是

12、上所有长度为k的串的集合，特别的：串的连接运算：, 2 , 1,|21kjvvvvjkiiiik10*210nmnmbbbaaabbbaaaa212121321*,262021/3/10第九章第九章 代数系统的一般性质代数系统的一般性质9.1 二元运算及其性质9.2 代数系统9.3 几个典型的代数系统272021/3/109.2 代数系统代数系统一、代数系统的定义(定义9.8)非空集合S和S上k个运算f1,f2fk(其中fi为ni元运算，i=1，2,，k)组成的系统称为一个代数系统，简称代数，记作。判断代数系统的方法：判断该系统中的每个运算是否为n元运算。282021/3/109.2 代数系统

13、代数系统例11：、是否为代数系统？, 是否为代数系统？292021/3/109.2 代数系统代数系统二、特异元素、代数常数的定义代数系统中对于给定的二元运算存在幺元或零元，并且它们对该系统的性质起着重要的作用，称之为该系统的特异元素特异元素或代数常数代数常数。例如：、302021/3/109.2 代数系统代数系统三、子代数系统、子代数的定义(定义9.13)设V=S,f1,f2,fk是代数系统，BS且B，如果B对f1,f2,fk都是封闭的，且B和S含有相同的代数常数，则称是V的子代数系统，简称子代数。例如：v1= v2=312021/3/109.2 代数系统代数系统例12：设V=，令nZ=nz|

14、zZ.n为自然数，那么，是否为V的子代数？322021/3/109.2 代数系统代数系统四、平凡子代数与真子代数的定义对任何代数系统V=S,f1,f2,fk，最大的子代数就是V本身。如果令V中所有的代数常数构成的集合是B，且B对V中所有的运算都是封闭的，则，B就构成了V的最小子代数。这种最小和最大子代数称为V的平凡子代数。如果代数系统V的子代数V=B,f1,f2,fk，满足 BS，则称V为V的真子代数。332021/3/109.2 代数系统代数系统五、积代数定义（定义9.14）设V1=,V2=是代数系统，和*为二元运算。V1和V2的积代数V1V2是含有一个二元运算的代书系统，即V1V2=,其中

15、S=S1S2,对任意的,S1S2有=342021/3/109.2 代数系统代数系统例13：设V1=，V2=,求V1与V2的积代数。V1V2=ZZ,其中：=352021/3/109.2 代数系统代数系统六、同态的定义(定义9.15)设V1=,V2=是代数系统， 和*是二元运算。如果存在映射：S1S2，若x，yS1都有 (xb)=(x)*(y)则称是V1到V2的同态映射，简称同态。362021/3/109.2 代数系统代数系统例14：(1)G1=，G2=,令：ZZn，(x)=(x)modn 则是否为G1到G2的同态？372021/3/109.2 代数系统代数系统例15：(2)G1=，G2=,令：R

16、R+ ，(x)= ex 则是否为G1到G2的同态？382021/3/109.2 代数系统代数系统七、同态象的定义(定义9.16)设是是V1=到V2=的同态，则称是V1在下的象。392021/3/109.2 代数系统代数系统八、满同态、单同态、同构和自同态(定义9.17)(1)若：G1G2是满射的，则称为满同态，这时也称 G2是G1的同态像，记作 。21GG(2)若：G1G2是单射的，则称为单同态。(3)若：G1G2是双射的，则称为同构，记作 。21GG(4)若G1=G2，则称是群G的自同态。402021/3/109.2 代数系统代数系统例16：设V=，其中为普通成法。对任意xR+令1(x)=|

17、x|， 2(x)=2x, 3(x)=x2, 4(x)=1/x, 5(x)=-x,则分析他们是否为V到V的同态，如果是，则分别为什么同态。412021/3/10第九章第九章 代数系统简介代数系统简介n9.1 二元运算及其性质n9.2 代数系统n9.3 几个典型的代数系统n半群与群422021/3/10(1)半群与群半群与群一、半群的定义(定义9.13)（1）设V=是代数系统，为二元运算，如果 是可结合的，则称V为半群。（2）设V=是半群，若eS是关于运算的单位元，则称V是含幺半群，也叫独异点。有时也将 独异点V记作。432021/3/10(1)半群与群半群与群例1：(1),都是半群，其中+表示普

18、通加法。(2)是半群，其中 是有穷字母表， 表示连接运算。*(3)是半群，也是独异点，其中为集合的对称差运算。(4)是半群，其中Zn =0,1,n-1,表示模n的加法。442021/3/10(1)半群与群半群与群二、幂运算的定义半群V=，对于任意xS，规定：普通乘法的幂、关系的幂等都遵循这个幂运算规则。Znxxxxxnn ，11幂运算的运算规则：nmmnmnmnxxZmnxxx)(, ，对独异点有：ex 0452021/3/10(1)半群与群半群与群三、子半群的定义半群的子代数叫做子半群，独异点的子代数叫做子独异点。若V=是半群，TS，只要T对V中的运算封闭，那么就是V的子半群。而对独异点V=

19、来说，TS，不仅T对V中的运算封闭，而且eT，这时才构成V的子独异点。462021/3/10(1)半群与群半群与群例2：设独异点V1=，V2=,V2是否为V1的子独异点？472021/3/10(1)半群与群半群与群四、积半群设V1=，V2=是半群（或独异点），则V1V2=也是半群，且：，S1S2，=称V1V2 为V1和V2的积半群。若V1和V2是独异点，其单位元为e1和e2，则是V1V2中的单位元。因此V1V2也是独异点。482021/3/10(1)半群与群半群与群五、半群的同构(1)设V1=，V2=是半群，:S1S2。若对任意 的x，yS1有 (xy)=(x)*(y) 则称为半群V1到V2的

20、同态映射，简称为同态。 (2)设V1=，V2=是独异点，:S1S2。 若对任意的x，yS1有 (xy)=(x)*(y) 且(e1)=e2 则称为独异点V1到V2的同态映射，简称为同态。 492021/3/10(1)半群与群半群与群例3：设半群V1=，独异点V2=。其中为矩阵乘法，e为2阶单位矩阵。令则是半群V1=到自身的同态，称V1的自同态。但不是独异点 V2=自同态。,|RdaaSb 00 SdaadaSS 00 00000:，502021/3/10(1)半群与群半群与群六、群的定义(定义9.14)设是代数系统，为二元运算。如果运算是可结合的，存在单位元eG，并且对于G中的任何元素x都有 G

21、，则称为群。1x512021/3/10(1)半群与群半群与群例6：(1),，其中+表示普通加法。*(2)其中 是有穷字母表， 表示连接运算。(3)，其中为集合的对称差运算。(4)，其中Zn =0,1,n-1,表示模n的加法。522021/3/10(1)半群与群半群与群例7：设G=e,a,b,c, 为G上的二元运算,它由一下运 算表给出。判断是否为群?eabceeabcaaecbbbceaccbae532021/3/10(1)半群与群半群与群例8：设,是群,在G1G2上定义二元运算 如下：,G1G2, = 称是G1与G2的直积。则是否 是群？542021/3/10(1)半群与群半群与群七、群的相

22、关概念定义(1)若群G是有穷集，则称G是有限群，否则称为无限群。 群G的基数称为群G的阶。(2)只含单位元的群称为平凡群。(3)若群G中的二元运算是可交换的，则称G为交换群或 阿贝尔群。552021/3/10(1)半群与群半群与群八、群的幂次定义注：半群和特异点不同，群中元素可以定义负整数次幂。设G是群，aG，nZ，则a的n次幂mnnanaaneamnn, 0)(0011 562021/3/10(1)半群与群半群与群九、元素的阶、无限阶元设G是群，aG，使得等式成立的最小正整数k称为a的阶，记作|a|=k，这是也称a为k阶元。若不存在这样的正整数k，则称a为无限阶元。eak572021/3/1

23、0(1)半群与群半群与群十、群中元素阶的性质为群，aG，且|a|=r。设k是整数，则整除能被当且仅当rkeak )1(|)2(1aa | 例：设G是群，a，bG是有限阶元。证明| ) 1 (1aabb| )2(baab 582021/3/10(1)半群与群半群与群十一、 群的幂运算定理(定理9.4)设G是群，则G中的幂运算满足：aaGa11)()1(， 111)()2(ababGba， ZmnaaaGamnmn， )3(ZmnaaGanmmn，)()4( 592021/3/10(1)半群与群半群与群十二、方程唯一解定理(定理9.5)G为群，a,bG，方程ax=b和ya=b在G中有解且有唯一解。

24、例9：设群G=，其中为集合的对称差运 算。解下列方程： a X=，Y a,b=b602021/3/10(1)半群与群半群与群十三、群中二元运算的消去律(定理9.6)G为群，则G中适合消去律，即对任意a,b,cG有(1)若ab=ac，则b=c。(2)若ba=ca，则b=c。Z例10：设G为群，a,bG，k ，证明bbbaabaakk11)(612021/3/10(1)半群与群半群与群例11：设G为群，a，bG，且 证明ab=ba。222)(baab622021/3/10(1)半群与群半群与群十四、子群的定义(定义9.15)设群，H是G的非空子集，如果H关于G中的运算*构成群，则称H是G的子群，记

25、作H G。若H是G的子群，HG，则称H是G的真子群，记作HG。注： G和e是G的平凡子群。632021/3/10(1)半群与群半群与群十五、子群判定定理一(定理9.8)设G是群，H是G的非空子集。如对任意x,yH都有xy-1H则H是G的子群。642021/3/10(1)半群与群半群与群例：设G为群，令即的所有幂构成的集合，则求证是的子群。652021/3/10(1)半群与群半群与群十六、循环群的定义(定义9.16)设G是群，若存在aG使得 G= |kZ则称G是循环群，记作G=，称a为G的生成元。ka注：(1)任何素数阶的群都是循环群。 (2)循环群的生成元可能不止一个。662021/3/10(

26、1)半群与群半群与群例13：(1)G=是否为循环群？(2)G=是否为循环群？(3)G=是否为循环群？(4)G=，是模n的加法，则G是否为循环群？(5)G=P(A),是否为循环群？(6)G=nZ,+是否为循环群？672021/3/10(1)半群与群半群与群例14：设A=1,2,3,4,5,构成群，其中为集 合的对称差。 （1）求解群方程1,3X=3,4,5 （2）令B=1,4,5，求由B生成的循环子群682021/3/10(1)半群与群半群与群十七、循环群生成元的求法设G=是循环群。（1）若G是无限循环群，则G只有两个生成元，即a和（2）若G是n阶循环群，则G含有(n)个生成元。对于任何 小于等

27、于n且与n互素的正整数r， 是G的生成元。1ara692021/3/10(1)半群与群半群与群例15：(1)设G=e,a,a11是12阶循环群，则它的生成元 有几个，分别是什么？(2)G=是模9的整数加群，则它的生成原有几个， 分别是什么？(3)G=，则G上的生成元有几个，分别是什么？702021/3/10(1)半群与群半群与群十八、循环群的子群求法（1）设G=是循环群，则其所有的子群均为循环群（2）设G=是无限循环群，则G的子群除e外都是无限 循环群。（3）设G=是n阶循环群，则对n的每个正因子d，G恰好含 有一个d阶子群。712021/3/10(1)半群与群半群与群例16：G=是无限循环群

28、，其生成元为1和1，则 列出G的所有循环子群。=0=0Z=，-1,0,1,=Z=-4，-2,0,2,4,=2Z=-2n，-n,0,n,2n,=nZ722021/3/10(1)半群与群半群与群例17：G=是12阶循环群，列出G的所有子群。=Z12=0,2,4,6,8,10=0,3,6,9=0,4,8=0,612的正因子为：1,2,3,4,6,12=0732021/3/10(1)半群与群半群与群例18：设G1=e,a2,a-2,a4,a-4,是无限循环群， 则G1的子群是什么？=e=e,a2m,a-2m ,a4m,a-4m, m是正整数742021/3/10(1)半群与群半群与群例19：设G2=是9阶循环群，则G2的子群是什么？=G2=e,a6,a129的正因子有：1,3,9=e752021/3/10(1)半群与群半群与群十九、置换的定义(定义9.17)设S=1,2,n，S上的任何双射函数：SS称为S上的n元置换。一般将n元置换记为)( )2( ) 1 ( 2 1 nn762021/3/10(1)半群与群半群与群S=1,2,3,4,5 则4 1 2 3 5 5 4 3 2 15 2 1 3 4 5 4 3 2 1都是五元置换。12345123451234512345772021/3/10(1)半群与群半群与群二十、k阶轮换的定义设是S=1,2,n上的n