第十章 代数系统.ppt

第三部分代数结构代数结构也叫做抽象代数，主要研究抽象的代数系统。抽象的代数系统也是一种数学模型，可以用它表示实际世界中的离散结构。例如在形式语言中常将有穷字符表记为，由上的有限个字符（包括0个字符）可以构成一个字符串，称为上的字。上的全体字符串构成集合*。设,是*上的两个字，将连接在后面得到*上的字。如果将这种连接看作*上的一种运算，那么这种运算不可交换，但是可结合。集合*关于连接运算就构成了一个代数系统，它恰好是抽象代数系统-半群的一个实例。抽象代数在计算机中有着广泛的应用，例如自动机理论、编码理论、形式语义学、代数规范、密码学等等都要用到抽象代数的知识。代数结构的主要研究对象就是各种典型的抽象代数系统。10.1二元运算及其性质一、二元运算与一元运算的定义定义定义10.1 设S为集合,函数f：SSS称为S上的二元运算,简称为二元运算二元运算。例如f：NNN,f()=x+y就是自然数集合N上的二元运算,即普通的加法运算。普通的减法不是自然数集合N上的二元运算,因为两个自然数相减可能得到负数,而负数不是自然数。这时也称N对减法运算不封闭。例如实数集合R上不可以定义除法运算,因为0R,而0不能做除数。但在R*=R0上就可以定义除法运算了,因为x,yR*,都有x/yR*。验证一个运算是否为集合S上的二元运算主要考虑两点：(1)S中任何两个元素都可以进行这种运算,且运算的结果是唯一的唯一的。(2)S中任何两个元素的运算结果都属于S,即S对该运算是封闭的封闭的。算符：二元运算的符号化表示。通常用*，设f:SSS是S上的二元运算，对任意的x,yS，如果f()=z，可记为xy=z例1：设R为实数集合，如下定义R上的二元运算*：x,yR,x*y=x，计算3*4，（-5）*0.2，0*0.5解：解：3*4=3,(-5)*0.2=-5,0*0.5=0定义定义10.2设S为集合,函数f：SS称为S上的一个一元运算,简称为一元运算一元运算。(6)在n(n2)阶实矩阵的集合Mn(R)上,求一个矩阵的转置矩阵是Mn(R)上的一元运算。例例10.2(1)求一个数的相反数是Z,Q和R上的一元运算。(2)求一个数的倒数是Q*,R*上的一元运算。(3)求一个复数的共轭复数是复数集合C上的一元运算。(4)在P(S)上,如果规定全集为S,则求集合的绝对补运算是P(S)上的一元运算。(5)设S为集合,令A为S上所有双射函数的集合,ASS,则求一个双射函数的反函数为A上的一元运算。同样可以用算符来标记，若f(x)=y，则记为（x）=y，或x=y如：相反数-x，求绝对补集A解析公式就是使用算符和表达式给出参与运算的元素和运算结果之间的映射规则。表示二元或一元运算的方法有两种：解析公式解析公式和运算表运算表。对于有穷集上的一元和二元运算，可以用有穷表给出。表10.1和10.2是一元运算表运算表和二元运算表运算表的一般形式。其中a1,a2,an是S中的元素,为算符。aiaia1a2ana1a2ana1a2ana1a2ana1a1a1a2a1ana2a1a2a2a2anana1ana2anan表10.1表10.2例3：给出对应的运算表：1)设A=1，2，1/2，对xA，规定x=1/x2)设A=1,2,3,4，对x,yA，规定xy=max(x,y)aiai121/212123412341234223433344444二元运算的性质定义定义10.3 设为S上的二元运算,1)如果对于任意的x,yS,有xy=yx,则称运算在S上满足交换律交换律。2)如果对于任意的x,y,zS有(xy)z=x(yz),则称运算在S上满足结合律结合律。3)如果对于任意的xS有xx=x,则称运算在S上满足幂等律幂等律。如果S中的某些x满足xx=x，则称x为运算的幂等元幂等元。P(S)上的、都是可交换的，但相对补运算不是；R上的加法、乘法都是可交换的，但减法运算不是；AA上的函数的复合运算不是可交换的，因为一般fggfP(S)上的、；函数的复合都是可结合的；矩阵的加法是可交换的，但矩阵的乘法不是；R上的加法、乘法都是可结合的，但减法运算不是；矩阵的加法、乘法是可结合的；对适合结合律的二元运算，在只由一个该运算的算符连接起来的表达式中，可以（xy）（uv）=xyuv如：（2+3）+（4+5）=2+3+4+5P(S)上的、适合幂等律；而、相对补运算不适合幂等律；有幂等元；普通的+、*不适合幂等律；但有幂等元0，1；定义定义10.4设和*为S上两个不同的二元运算,1)如果对于任意的x,y,zS有2)(x*y)z=(xz)*(yz)（右分配律）3)和z(x*y)=(zx)*(zy)（左分配律）4)则称运算对*运算满足分配律分配律。如P(S)上的、互可分配的；R上的*对+是可分配的；若*对运算分配律成立，则*对运算广义分配律也成立X*(y1y2yn)=(x*y1)(x*y2)(x*yn)(y1y2yn)*X=(y1*x)(y2*x)(yn*x)即：2)如果和*都可交换都可交换,并且对于任意的x,yS有x(x*y)=x和x*(xy)=x,则称和*运算满足吸收律吸收律。如P(S)上的、满足吸收律；例4：对任意的x,yZ+，定义二元运算*：X*y=max(x,y)，讨论具体的性质。解：满足交换律，结合律，幂等律。特异元素：单位元、零元和逆元特异元素：单位元、零元和逆元定义定义10.510.5设为S上的二元运算,1)如果存在el（或er）S,使得对任意xS都有2)elx=x(或xer=x),3)则称el(或er)是S中关于运算的左左(或右或右)单位单位元元。若eS关于运算既是左单位元又是右单位元,4)则称e为S上关于运算的单位元单位元。也叫做幺元幺元。例5：a,bR*,有ab=a则每个元素都是右单位元，无左单位元，无单位元。定理1：若有el，erS，则一定有el=er=e且唯一。证明：el=eler=er所以有el=er，即单位元e若不唯一，存在e也是S中的单位元，则有e=ee=e所以唯一。2)如果存在l（或r）S,使得对任意xS都有lx=l(或xr=r),则称l(或r)是S中关于运算的左左(或右或右)零元零元。若S关于运算既是左零元又是右零元,则称为S上关于运算的零元零元。在上例中，有左零元，任何元素都是；无右零元。定理2：若有l，rS，则一定有l=r=且唯一。证明：l=lx=lr=r所以有l=r，即零元若不唯一，存在也是S中的单位元，则有=x=所以唯一。定理3：若e，分别是S中关于运算的单位元、零元，如果S中至少有两个元素，则e.证明：假设e=，则对xS有x=ex=x=与S中至少有两个元素矛盾。3)令e为S中关于运算的单位元。对于xS,如果存在yl（或yr）S使得ylx=e（或xyr=e）,则称yl(或yr)是x的左逆元左逆元(或右逆元或右逆元)。若yS既是x的左逆元又是x的右逆元,则称y为x的逆元逆元。如果x的逆元存在,就称x是可逆的可逆的。集合运算单位元零元逆元Z,Q,R普通+普通*01无0 x的逆元-xx(x0)的逆元1/xMn(R)矩阵+矩阵*全0矩阵单位矩阵无全0矩阵M的逆元-M可逆矩阵M的逆元为M-1P(S)SS只有有逆元，为只有S有逆元，为S定理4：设是S上可结合可结合的二元运算，e为该运算的单位元，对于xS，如果存在yl，yr，则有yl=yr=y，且y是x的唯一逆元唯一逆元。证明：yl=yle=yl(xyr)=eyr=yr令yl=yr=y，若存在yS，也是x的逆元，则y=ye=y(xy)=ey=y对可逆的元素x只有唯一的逆元，通常记作x-1。说明：1、单位元、零元存在，一定唯一，整个集合中只有一个；2、逆元与元素有关，不同元素对应着不同的的逆元，有的元素有，有的元素没有；3、如果运算是可结合的，那么对于集合中可逆的元素，逆元一定是唯一的。定义10.6对x,y,zS，满足yx=zx且x，则y=z(右消去律）若xy=xz且x，则y=z(左消去律）则称运算满足消去律。如：AB=ACB=CBA=CAB=C则在P(S)上满足消去律又如+、*在Z上满足消去律；而、不满足。例5：设Q为有理数集合，xyQ，x*y=x+y-xy，指出该运算的性质，并求出它的单位元，零元和所有可逆元素的逆元。*运算满足交换律，因为对x,yQ，X*y=x+y-xy=y+x-yx=y*x*运算满足结合律，因为对x,yQ，(x*y)*z=(x+y-xy)*z=x+y-xy+z-xz-yz+xyzx*(y*z)=x*(y+z-yz)=x+y+z-yz-xy-xz+xyz所以x*(y*z)=(x*y)*z*运算不满足幂等律，因为2Q，但2*2=2+2-2*2=02*运算满足消去律，因为x,y,zQ，x1,有x*y=x*zx+y-xy=x+z-xzy-xy=z-xzy-z=x(y-z)y=z由于*是可交换的，右消去律显然成立。xQ，有x*0=x=0*x，0是*运算的单位元。xQ，有x*1=1=1*x，1是*运算的零元。xQ，欲使x*y=y*x=0成立，即x+y-xy=0解得y=x/(x-1)(x1)从而有x-1=x/(x-1)例6：说明下面的三个二元运算是否满足交换律、结合律、消去律和幂等律:*abcaabcbbcaccababcaabcbbbbccbcabcaabcbabccabc*运算适合交换律、结合律、和消去律，不适合幂等律。单位元为a，无零元，a-1=a,b-1=c,c-1=b。运算适合交换律、结合律、幂等律，不适合消去律。单位元为a，零元为b，只有a-1=a。运算适合结合律和幂等律，不适合交换律、消去律。无单位元，无零元，没有可逆元素。10.2代数系统定义定义10.6 非空集合S和S上k个一元或二元运算f1,f2,fk组成的系统称为一个代数系统代数系统,简称代数代数,记做。例如,都是代数系统。是代数系统是代数系统,其中Zn0,1,n-1,和分别表示模n的加法和乘法对于x,yZn,xy=(xy)modn,xy=(xy)modn；也是代数系统,其中含有两个二元运算和以及一个一元运算。在某些代数系统中存在着一些特定的元素,它们对于系统的一元或二元运算起着重要的作用,例如二元运算的单位元和零元。在定义代数系统的时候,如果把含有这样的特定元素也作为系统的性质,比如规定系统的二元运算必须含有单位元，这时称这些元素为该代数系统的特异元素特异元素或代数常数代数常数。有时为了强调某个代数系统是含有代数常数的系统,也可以把这些代数常数列到系统的表达式中。例如中的+运算有单位元0,为了强调0的存在,可以将记做。又如：定义定义10.7如果两个代数系统中运算的个数相同,对应运算的元数相同,且代数常数的个数也相同,则称这两个代数系统具有相同的构成成分相同的构成成分,也称它们是同类型同类型的代数系统。例如V1=和V2=是同类型的代数系统,它们都含有两个二元运算、一个一元运算和两个代数常数。同类型的代数系统仅仅是构成成分相同,不一定具有相同的运算性质。V1V2+和可交换，可结合和可交换，可结合对+可分配和互相可分配+和不遵从幂等律和都有幂等律+和没有吸收律和有吸收律+和都有消去律和一般没有消去律定义定义10.8设V=是代数系统,B是S的非空子集,如果B对f1,f2,fk都是封闭的,且B和S含有相同的代数常数,则称是V的子代数系统子代数系统,简称子代数子代数。有时将子代数系统简记为B。例如N是的子代数,因为N对加法运算是封闭的。N也是的子代数,因为N对加法运算是封闭的,且N中含有代数常数0。N-0是的子代数,但不是的子代数因为的代数常数0N0。子代数和原代数不仅具有相同的构成成分,是同类型的代数系统,而且对应的二元运算都具有相同的运算性质。因为任何二元运算的性质如果在原代数上成立,那么在它的子集上显然也是成立的。在这个意义上讲,子代数在许多方面与原代数非常相似,不过可能小一些就是了。对于任何代数系统V=,其子代数一定存在。最大的在代数就是最大的在代数就是V本身本身。如果令V中所有代数常数构中所有代数常数构成的集合成的集合是B,且B对V中所有的运算都是封闭的,则B就构成了V的最小的子代数。这种最大和最小的子代数称为V的平凡的子代数平凡的子代数。若B是S的真子集,则B构成的子代数称为V的真子代数真子代数例例10.7设V=,令nZ=nz|zZ,n为自然数,则nZ是V的子代数。证：证：任取nZ中的两个元素nz1,nz2(z1,z2Z),则有nz1+nz2=n(z1+z2)nZ即nZ对+运算是封闭的又0=n0nZ所以nZ是V的子代数当n=1和0时,nZ是V的平凡的子代数,其它的都是V的非平凡的真子代数。定定义10.7设V1=,V2=是同类型的代数系统，和*为二元运算，在集合AB上如下定义二元运算：,AB,有=称V=为V1和V2的积代数代数,记作V1V2。称V1和V2为V的因子代数因子代数例例10.8 设设V1和和V2分别为模分别为模3和模和模2加的代数系统，加的代数系统，给出给出V1V2的运算表，并说明它的运算是否具有交换律与结合律，是否具有单位元？V1V2中的运算具有交换律与结合律，单位元是定理定理5 设V1=,V2=是同类型的代数系统，V1V2=是它们的积代数。代数。（1）如果）如果和*运算是可交换（可结合、幂等）的，那么 运算是可交换（可结合、幂等）的；（2）如果e1和e2（1和2）分别和*运算的单位元（零元），那么（）也是 运算的单位元（零元）。（3）如果x和y分别为和*运算的可逆元素，那么也是 运算的可逆元素，其逆元就是。积代数的定义可以推广到具有多个运算的同类型的代数系统。在具有两个不同的二元运算的情况下，积代数也保留因子代数中的分配律和吸收律等性质。但消去律是一个例外。