第9章代数系统---2015

数学与软件科学院－－张莉离散数学[e-mail]第9章代数系统简介§9.1二元运算及其性质§9.2代数系统§3几个典型的代数系统数学与软件科学院－－张莉离散数学[e-mail]本章的主要研究对象是各种各样的代数系统，即具有一些元运算的集合，代数系统的思想和方法已经渗透到现代科学的许多分支，它的结果已应用到计算机的不少方面，因此计算机科学工作者应初步掌握其基本的理论和方法。我们通过对具体代数系统的学习，应初步掌握对代数系统研究的一般方法：从简单到复杂、从具体到一般，从而发现代数系统的一般规律。数学与软件科学院－－张莉离散数学[e-mail]我们在前面已经研究过集合，那时没有过多地考虑一个集合内部元素之间的联系。现在我们要在一个集合的内部引入运算，并研究其运算规律，主要内容为：代数系统的运算的常用记法和运算表的概念，二元运算的各种性质；代数系统的定义；代数系统的各种性质。数学与软件科学院－－张莉离散数学[e-mail]§9.1二元运算及其性质DEFINITION9.1二元运算设S为集合，函数f:S×S→S称为S上的一个二元运算，简称为二元运算。例9.1：f:N×N→N，f(x,y)=x+y就是自然数集合上的一个二元运算，即普通的加法运算。考虑，普通的减法是不是自然数集合上的二元运算？实数R上的减法是不是二元运算？数学与软件科学院－－张莉离散数学[e-mail]由二元运算的定义可知，验证一个运算是否为集合S上的二元运算，主要考虑两点：(1)S中任何两个元素都可以进行这种运算，且运算的结果是唯一的。（函数）(2)S中任何两个元素的运算结果都属于S，即S对该运算是封闭的。通常用◦,,•,…等符号表示二元运算，称为算符。设f:S×S→S是S上的二元运算，对任意的x,yS，如果x与y的运算结果是z，即f(x,y)=z，则可利用算符◦简记为：x◦y=z.数学与软件科学院－－张莉离散数学[e-mail]5.11.实数集R上的加法，减法，乘法是二元运算。2.设Mn(R)表示所有n阶实矩阵的集合(n=2)，即：111212122212......()nnnijnnnnaaaaaaMRaRaaaMMMML则，矩阵加法和乘法都是Mn(R)上的二元运算。数学与软件科学院－－张莉离散数学[e-mail]9.2.n元运算设S为集合，n为正整数，则函数f:S×S×…×S→S称为S上的一个n元运算，简称为n元运算。n个类似的，也可以使用算符来表示n元运算，若f(x1,x2,…,xn)=y，则可利用算符◦简记为：◦(x1,x2,…,xn)=y或x1◦x2◦…◦xn=y.数学与软件科学院－－张莉离散数学[e-mail]对于有穷集S上的一元和二元运算可以用运算表给出：xi◦(xi)x1x2…xn◦(x1)◦(x2)…◦(xn)一元运算表的一般形式数学与软件科学院－－张莉离散数学[e-mail]◦x1x2…xnx1x2…xnx1◦x1x1◦x2…x1◦xnx2◦x1x2◦x2…x2◦xn…………xn◦x1xn◦x2…xn◦xn二元运算表的一般形式数学与软件科学院－－张莉离散数学[e-mail]设S={1,2}，给出P(S)上的运算ˉ和⊕的运算表，其中全集为S.EXAMPLE9.2{1,2}{2}{1}ØØ{1}{2}{1,2}xixi⊕Ø{1}{2}{1,2}Ø{1}{2}{1,2}Ø{1}{2}{1,2}{1}Ø{1,2}{2}{2}{1,2}Ø{1}{1,2}{2}{1}Ø数学与软件科学院－－张莉离散数学[e-mail]设S={1,2,3,4}，定义S上的二元运算如下：x◦y=(xy)mod5,x,yS.求◦的运算表。EXAMPLE9.3◦123412341234241331424321xy表示x乘y,是普通的乘法2◦3=1请同学们分析这个二元运算有什么特点？数学与软件科学院－－张莉离散数学[e-mail]9.3-9.5设◦和*为S上的二元运算，(1)◦在S上可交换：x,yS,x◦y=y◦x.(2)◦在S上可结合：x,y,zS,(x◦y)◦z=x◦(y◦z).(3)◦适合幂等律：xS,x◦x=x.(4)*对◦可分配：x,y,zS,x*(y◦z)=(x*y)◦(x*z).(5)◦和*满足吸收律：x,yS,x*(x◦y)=x,x◦(x*y)=x.幂集合上的∩，∪运算满足幂等律，可分配律，以及吸收率。数学与软件科学院－－张莉离散数学[e-mail]9.6设◦为S上的二元运算，el,er,e,l,r,S，(1)左幺元el：xS,el◦x=x.右幺元er：xS,x◦er=x.幺元e：e既是左幺元，又是右幺元。(2)左零元l：xS,l◦x=l.右零元r：xS,x◦r=r.零元：既是左零元，又是右零元。(3)x的左逆元yl：对xS,ylS,使得yl◦x=e.x的右逆元yr：对xS,yrS,使得x◦yr=e.x的逆元y：yS既是x的左逆元，又是x的右逆元。数学与软件科学院－－张莉离散数学[e-mail]自然数集N上的加法幺元为0，零元不存在;乘法的幺元为：1，零元为：0.P(S)上的∩运算幺元为_S__,零元为____;P(S)上的∪运算幺元为___,零元为__S___;EXAMPLE9.4数学与软件科学院－－张莉离散数学[e-mail]定理：9.1—9.3(1)设◦为S上的二元运算，el,er分别为运算◦的左幺元和右幺元，则有：el=er=e，且e为S上关于运算◦的唯一的幺元。（由定义证明）(2)设◦为S上的二元运算，l,r分别为运算◦的左零元和右零元，则有：l=r=，且为S上关于运算◦的唯一的零元。(3)设◦为S上可结合的二元运算，e为该运算的幺元，对于xS如果存在左逆元yl和右逆元yr，则有：yl=yr=y，且y是x的唯一的逆元。数学与软件科学院－－张莉离散数学[e-mail]证明：(2)=l◦r(因为l为左零元)l◦r=r(因为r为右零元)l=r，把l=r记作，假设S中存在零元’，则有：’=’◦=是S中关于运算◦的唯一的零元。数学与软件科学院－－张莉离散数学[e-mail]证明：(3)yl=yl◦e=yl◦(x◦yr)=(yl◦x)◦yr=e◦yr=yr，yl=yr，把yl=yr记作y，假设y’S是x的逆元，则有：y’=y’◦e=y’◦(x◦y)=(y’◦x)◦y=e◦y=y.对于可结合的二元运算来说，元素x的逆元如果存在则是唯一的。通常把这个唯一的逆元记作x-1.数学与软件科学院－－张莉离散数学[e-mail]9.7设◦为S上的二元运算，如果x,y,zS满足以下条件：(1)若x◦y=x◦z且x不是零元，则y=z，(2)若y◦x=z◦x且x不是零元，则y=z，就称运算◦满足消去律，其中(1)称作左消去律，(2)称作右消去律。数学与软件科学院－－张莉离散数学[e-mail](1)整数集合Z上的加法满足消去律。加法没有零元，x,y,zZ，都有：x+y=x+zy=z，y+x=z+xy=z.(2)整数集合Z上的乘法也满足消去律。0是乘法的零元，不能消去，任何非零的整数都可消去，x,y,zZ(x0)，都有：xy=xzy=z，yx=zxy=z.EXAMPLE9.5数学与软件科学院－－张莉离散数学[e-mail]（3）幂集P(S)上的∪运算不满足消去律。取A,B,CP(S)，由A∪B=A∪C不一定能得到B=C.（4）∩运算也不满足消去律。（5）运算满足消去律。运算不存在零元，A,B,CP(S)，都有：AB=ACB=C，BA=CAB=C.数学与软件科学院－－张莉离散数学[e-mail]§9.2代数系统DEFINITION9.8非空集合S和S上k个一元或二元运算f1,f2,…,fk组成的系统称为一个代数系统，简称代数，记作S,f1,f2,…,fk。例如，N,+,Z,+,·,R,+,·,P(S),∪,∩,ˉ都是代数系统。但，自然数集合N和普通减法-不能构成代数系统，因为两个自然数相减可能得到一个负数，所以不能写成N,-。数学与软件科学院－－张莉离散数学[e-mail]在某些代数系统中对于给定的二元运算存在幺元或零元，我们称之为该系统的特异元素或代数常数。例如，P(S),∪,∩,ˉ中的∪和∩的幺元分别为Ø和S，可将P(S),∪,∩,ˉ记为P(S),∪,∩,ˉ,Ø,S。数学与软件科学院－－张莉离散数学[e-mail]9.9子代数设V=S,f1,f2,…,fk是代数系统，BS，如果B对f1,f2,…,fk都是封闭的，且B和S含有相同的代数常数，则称B,f1,f2,…,fk是V的子代数系统，简称子代数。例如，N,+是Z,+的子代数：因为N对+是封闭的，且它们都没有代数常数。N,+,0是Z,+,0的子代数：因为N对+是封闭的，且它们都含有相同的代数常数0。N-{0},+是Z,+的子代数，但不是Z,+,0的子代数：因为Z,+,0的代数常数0N-{0}。数学与软件科学院－－张莉离散数学[e-mail]对任何代数系统V=S,f1,f2,…,fk，其代数一定存在。最大的子代数是V本身。如果令V中所有代数常数构成的集合是B，且B对V中所有的运算都是封闭的，则B就构成了V的最小的子代数。这种最大和最小的子代数称为V的平凡的子代数。真子代数：如果V的子代数V’=B,f1,f2,…,fk满足BS，则称V’是V的真子代数。数学与软件科学院－－张莉离散数学[e-mail]设V=Z,+,0，令nZ={nz|zZ}，n为自然数。证明nZ是V的子代数。EXAMPLE9.7证明：(1)nZZ；(2)nz1,nz2nZ(z1,z2Z)，则有nz1+nz2=n(z1+z2)nZ，即nZ对+运算是封闭的；(3)0=n·0nZ。∴nZ是Z,+,0的子代数。数学与软件科学院－－张莉离散数学[e-mail]9.10积代数设V1=S1,◦，V2=S2,*是代数系统，其中◦和*是二元运算。V1和V2的积代数V1V2是含有一个二元运算•的代数系统，即V1V2=S,•，其中，S=S1S2，且对x1,y1,x2,y2S1S2，有：x1,y1•x2,y2=x1◦x2,y1*y2.数学与软件科学院－－张莉离散数学[e-mail]设V1=Z,+，V2=M2(R),·，其中+和·分别表示整数加法和矩阵乘法，则V1V2=ZM2(R),◦，z1,M1,z2,M2ZM2