6 代数系统.ppt

1、第6章 代数系统初步,大连海事大学 计算机科学与技术学院,第3篇 代数系统,代数系统又称代数结构或抽象代数，是近代数学研究的主要对象。代数系统是指集合及其运算所组成的一个整体（或系统）。 我们研究代数系统主要是研究它的代数性质，即代数运算所表达的性质，而集合和映射是研究代数系统的基础。 典型的代数系统主要包括群、环、域、格与布尔代数等内容。,第6章 代数系统初步,定义代数结构之前，先说明在一个集合上的运算. 6.1 代数运算 1. 代数运算 定义 设X是个非空集合, f: Xn X的映射，则称f为X中的一个n元运算。 其中n称为运算的元数或阶。 当n=1时，称f为一元运算， 当n=2时，称f为

2、二元运算。（重点讨论二元运算） 注 X中的任意两个元素进行二元运算f之后，其运算结果仍然在X之中封闭性 封闭性表明了n元运算与一般函数的区别。,例 在数理逻辑中，否定是谓词集合上的一元运算，合取和析取是谓词集合上的二元运算； 在集合论中，并与交是集合上的二元运算； 在整数算术中，加、减、乘运算是二元运算，而除运算便不是二元运算，因为它不满足封闭性。,二元运算举例,设A=x|x=2n,nN 问：乘法运算是否封闭？对加法运算呢？,乘法运算：,对于任意的2r 、 2sA,2r2s =,2r+s,A,乘法运算在A上封闭；,加法运算：,21+22 =6, A,加法运算在A上不封闭；,举例,判断乘法运算是

3、否在下列各N的子集上封闭？ (1)A1=0,1 (2)A2=1,2 (3)A3=x|x为素数 (4)A4=x|x为偶数 (5)A5=x|x为奇数,22=4A2,23=6A3,2. 二元运算的性质 设 * 和是X上的二元运算， x,y,z X，则 1) 封闭性： 若x,yX，则x*yX; 2) 可交换性：x*y=y*x; 3) 可结合性：x*y*z=x*(y*z)=(x*y)*z; 4) 可分配性：若x*(yz)=(x*y)(x*z) (yz)*x=(y*x)(z*x) 则称*对可分配。 5) 吸收律：设*和是定义在集合A上的两个可交换的二元运算，若有x*(xy)=x, x(x*y)=x . 则

4、称*和满足吸收律。 例 实数集合上的加和乘运算是可交换和可结合的；减运算不可交换，乘运算对于加运算是可分配的。,二元运算性质举例,在N上定义两个二元运算*和，对任意的x,yN，有： x*y=max(x,y) xy=min(x,y) 验证：*和满足吸收律。,解答,x*(xy)=,x*(min(x,y),=max(x,min(x,y)=,xy,x=y,xy,max(x,y)=,max(x,x)=,max(x,x)=,x,x,x,x(x*y)=,x(max(x,y),=min(x,max(x,y)=,xy,x=y,xy,min(x,x)=,x,min(x,x)=,x,min(x,y)=,x,*和满足

5、吸收律,例1有理数集合Q上的二元运算*定义为a*b=a+b-ab, 问运算*是否可交换? 可结合? 解 a,b,cQ,有 a*b=a+b-ab=b+a-ba=b*a, 运算*是可交换的。 又(a*b)*c=(a+b-ab)*c= (a+b-ab)+c (a+b-ab)c = a+b-ab +c -ac-bc+abc = a+b +c -ab-ac-bc+abc a*(b*c)=a*(b+c-bc)=a+ b+c-bc a(b+c-bc) = a+b +c -ab-ac-bc+abc (a*b)*c = a*(b*c) , 故运算*是可结合的。,例2 A是非空集合，*是A上的二元运算，并a*b=

6、b, 证明*是可结合的，但是不可交换。 证 a,b,cA, 有 (a*b)*c=b*c=c ; a*(b*c)=a*c=c; 故(a*b)*c= a*(b*c)， *是可结合的。 a*b=b b*a=a, 故*是不可交换的。 例3 *是A上的二元运算，对任意的a,b,c,dA,有 a*a =a, 且 (a*b)* (c*d) = (a*c)* (b*d) 求证：a*(b*c)=(a*b)* (a*c) 证 a,b,cA, 有 (a*b)* (a*c) = (a*a)*(b*c)=a*(b*c),3. 二元运算中的特异元 幺元e（左幺元el 、右幺元er ） 设*是集合X中的二元运算， （1）如

7、果有一个元素el X，且对每一个xX都有el *x=x, 则称el 为关于*运算的左幺元； （2）如果有一个元素er X，且对每一个xX都有x* er =x, 则称er为关于*运算的右幺元； 定理 设*是集合X中的运算，如果X对运算*同时存在左幺元和右幺元，则必有el = er =e ,使得对任意的xX有 x*e=e*x=x 此时e唯一，被称为集合X关于运算*的幺元（单位元素） 例 实数集合R上的加法运算：幺元是0 实数集合R上的乘法运算：幺元是1,2) 零元0（左零元0l 、右零元0r ） 设*是集合X中的二元运算 （1）如果有一个元素0l X，且对每一个xX都有0l *x= 0l,则称0l

8、为关于*运算的左零元； （2）如果有一个元素0r X，且对每一个xX都有x*0r = 0r,则称0r为关于*运算的右零元； 定理 设*是集合X中的运算，如果X对运算*同时存在左零元和右零元，则必有0l = 0r = 0, 使得对任意的xX有 x* 0 = 0 *x= 0 此时， 0是唯一的，并称它为集合X关于运算*的零元。 例 实数集合R上的乘法运算：零元是0,3) 等幂元：设*是集合X中的二元运算,且xX，如果有x*x=x,则称x对于*运算是等幂的； x称为等幂元。 例 对任何运算来说，幺元和零元都是等幂元。,4) 逆元（左逆元xl 、右逆元xr ） 设*是集合X中的运算,且X中对于*存在幺

9、元e，令xX （1）如果有一个元素xlX，能使得xl*x= e,则称xl为x的左逆元，并称x是左可逆的； （2）如果有一个元素xrX，能使得x*xr= e,则称xr为x的右逆元，并称x是右可逆的； （3）如果x既左可逆的又是右可逆的，则称x是可逆的。,定理 设*是集合X中的一个可结合的二元运算，且对于*有幺元e,若元素xX是可逆的，则它的左逆元和右逆元必相等，记为x-1, 并称x-1是x的逆元且唯一。 注 幺元的逆元是其本身；零元不可逆。 例 实数集合R上的加法运算：幺元是0，元素x的逆元-x 实数集合R上的乘法运算：幺元是1，元素x的逆元1/x,例 设I是整数集合，x*y=x+y-xy。求出

10、幺元，并指出每个元素的逆元。 解 对任意的xX，若幺元e存在，则x*e=e*x= x+e-xe=x，故得出存在e=0. 对任意xX，若其逆元x-1存在，则x* x-1 = x+x-1-xx-1=0， x-1=x/(x-1)为整, 故只有2和0有逆元，2-1 =2， 0-1 =0。,5）可约的或可消去的 设*是集合X中的运算，且a X, x,yX. 若对每个x,y都有 a*x = a*y x=y 左可约 x*a = y*a x=y 右可约 则称a是可约的或可消去的。 例 定理 设*是集合X中的运算，且*是可结合的，若a X 对*运算是可逆的，则a也是可约的。 证 设x,yX,并设a*x=a*y。

11、由*是可结合的,a是可逆的， 有 a*x=a*y a-1 *(a*x)= a-1 *(a*y) (a-1 *a)*x = (a-1 *a) *y e*x= e*y x = y 同样，可得 x*a=y*a x = y 故， a是可约的,6) 由运算表求特异元： （1）左幺元：如果某一个元素使得某一行不改变； 右幺元：如果某一个元素使得某一列不改变； （2）左零元：如果某一个元素使得某一行均为该元素； 右零元：如果某一个元素使得某一列均为该元素； （3）逆元：幺元所对应的元素互为逆元； （4）等幂元：只考虑主对角线上的元素 例 A=a,b,c,d上的运算*可交换否， 求幺元，逆元,等幂元 运算表关

12、于主对角线对称，*可交换。 幺元为a，使其行与列均不变。 零元：不存在。 逆元：因a为幺元，a-1=a,b-1=d,d-1=b, 等幂元：a, b, c,举例,已知二元运算*、 、的运算表，求各运算的特异元素。,解答,(1)第2、4行没改变 和均为左幺元； 无右幺元； (2)无左、右零元； (3)无逆元； (4)、均为等幂元。,解答,(1)第1行没改变，所以为左幺元； 第1列没改变，所以为右幺元； 为幺元 (2)无左、右零元； (3)-1;-1;-1; (4)为等幂元。,解答,(1)第1行没改变，所以为左幺元； 第1列没改变，所以为右幺元； 为幺元 (2)无左、右零元； (3)-1;-1; -

13、1;-1 ; -1 =; (4)、 为等幂元。,6.2 代数系统的概念 1 代数系统的定义 设X为非空集合，为X上代数运算的非空集合， 称序偶 X, 为一个代数系统（或代数结构）。 称集合X为 X, 的定义域。如果X有限，则称 X, 为有限代数系统。 并称|X|为 X, 的阶。 若=1，2，. n为有限集合，则将 X, 记为X, 1，2，. n 。 2 代数系统需满足的条件 （1）非空集合X； （2）有一些建立在集合X上的代数运算（封闭性）；,代数系统举例,设A=1，2，3，4，6，12 A上的运算*定义为：a*b=|a-b| （1）写出二元运算的运算表； （2）能构成代数系统吗？,解答,由运

14、算表可知*运算在集合A上不封闭 所以： 不能构成代数系统,0,1,2,3,5,11,1,0,1,2,4,10,2,1,0,1,3,9,3,2,1,0,2,8,5,4,3,2,0,6,11,10,9,8,6,0,代数系统举例,N4=0，1，2，3 , i+4j=(i+j)(mod4) 问：是代数系统吗？,验证+4在N4集合上是否满足封闭性,0,1,2,3,1,2,3,0,2,3,0,1,3,0,1,2,由运算表可知运算满足封闭性,是代数系统,例1 (S)，是代数系统。 例2 给定f=, 集合F=f0, f1, f2, f3，证 F, 是代数系统。 解 由运算表可见， 合成运算对于 集合F是封闭的

15、。 故 F, 是代数系统。,例3 已知 整数集合I上模m同余是等价关系， 设m=4 令Z4表示生成的等价类集合， Z4=0,1,2,3, 定义Z4上的代数运算+4 ： i +4 j =(i+j)(mod4) （i, j=0,1,2,3） 解 由运算表可见， +4对集合Z4是封闭的。 故是代数系统。,3 子代数系统 设 X, 为代数系统，若非空SX，对于每个皆封闭，则 S, 也是代数系统，并称其为 X, 的子代数系统或子代数； 若S是X的真子集，则称 S, 为 X, 的真子系统或真子代数。 例 代数系统，令N=0,2,4,6, NN且是的真子代数。,6.3 同态与同构 表面上不同的两个代数系统往

16、往有共同的性质。,例 是代数系统， 运算+,的性质有 1) 可交换性 2) 可结合性 3) 可分配性 对+可分配: a(b+c)= ab+ac 4) 幺元 关于的幺元为1,关于+的幺元为0. 5) 逆元 关于+的逆元：任意aI, a-1 = -a 6) 可约性 关于，对任意aI, a0， a是可约的，即 ab= ac b= c 是代数系统, 具有代数系统的以上6种性质. 注 隐约体会到不同代数系统之间有内在的联系。,1 同态与同构的概念 设U=和V=是两个代数系统，和*都是二元运算，函数g：XY，若对任意的x,yX，有： g(xy)=g(x)*g(y) (运算的象=象的运算） 则称g是代数系统

17、U到V的一个同态映射（简称同态）。 并称代数系统U和V同态，记作 X Y。 如果g是满射的，则g为满同态； 如果g是单射的，则g称为单一同态； 如果g是双射的，则g称为同构映射；并称U和V同构,记作X Y。,同态的一般定义(略),设V1= ，V2=是两个同类型的代数系统； f: 12为类型映射，如果存在函数 g：S1S2 ，使得对任意的n元运算1及任意的元素a1,a2,anS1均有： g()=f() 则称V1与V2同态。,解释,两个代数系统同态： （1）两个代数系统同类型； （2）运算的象=象的运算,同态举例,证明：和是同态的，其中： B=正，负，零，*运算的运算表如下：,解答,(1)显然和是

18、同类型的； (2)g:IB,(3)验证运算的象=象的运算,g(I)=,i0,i0,i=0,正,负,零,(3)运算的象=象的运算,i0,j0时:g(ij)=正，g(i)*g(j)=正*正=正 i0,j0,j=0时:g(ij)=零，g(i)*g(j)=正*零=零 i0时:g(ij)=负，g(i)*g(j)=负*正=负 i0时:g(ij)=零，g(i)*g(j)=零*正=零 i=0,j0时:g(ij)=零，g(i)*g(j)=零*负=零 i=0,j=0时:g(ij)=零，g(i)*g(j)=零*零=零,单一同态举例,证明：,单一同态,实数集合,g:RR,对于xR,g(x)=2x,证明,(1)显然和同

19、类型 (2)运算的象=象的运算 对于任意的x,yR，有： g(x+y) =2x+y =2x2y=g(x)g(y) (3) g映射是单射函数,y=2x,例 6.3.4 给定代数系统U=, V=, W= f:XY是U到V的同态，g:YZ是V到W的同态,证明gf: XZ是U到W的同态。 证 对任意的a,bX, gf(ab)=g(f(ab)=g(f(a)*f(b) (因f是同态) =g(f(a)g(f(b) (因g是同态) =(gf)(a)(gf)(b),2 自同态与自同构 设是一个代数系统， 如果f是由到的同态，则称f为自同态。 如果f是由到的同构，则称f为自同构。 例6.3.3 给定代数系统和，

20、对于任意的xI，定义映射f:II，且给定为：f(x)=3x。 证明f是从 到的同态映射，且是自同态。 证 对任意的x1,x2I, f(x1+x2)=3(x1+x2)=3x1+3x2=f(x1)+f(x2) 故 f是一个同态，并且是自同态。,例 把上例扩展一下： 给定，其中I为整数集合，+为一般加法。作函数f:II，且 f(x)=kx，其中x,kI. 则 当k0时，f为到的单一同态映射。 当k=1时，f为从到的同构映射。 当k=0时， f为同态映射，但既非单一、又非满同态,3.同态与同构的性质 满同态对保持性质是单方向的： 若代数系统到代数系统存在满同态映射，则所具有的性质（交换律，结合律，分配

21、律,幺元，零元，逆元等）， 均保持，但反之不然。 同构对保持性质是双方向的： 同构可以双方向地保持两个代数系统的运算性质（交换律，结合律，分配律,幺元，零元，逆元等）。 同构的两个代数系统运算体现的规律性是相同的（这是本质现象，而他们的差别是表面的），同构的两个代数系统被认为是（代数）相等的。,定理 给定和且f为其满同态映射，则 (1) 或满足结合律*或也满足结合律。 (2) 或满足交换律*或也满足交换律。 (3) 对于满足分配律*对于满足分配律。 (4) e1和e2分别是关于和的幺元f(e1)和f(e2)分别为关于*和的幺元。 (5)1和2分别是关于和的零元f(1)和f(2)分别为关于*和的

22、零元。 (6) 对每个xX均存在关于的逆元x-1 对每个f(x)Y也均存在关于*的逆元f(x-1)；,定理 给定和且f为其同构映射，则 (1) 或满足结合律*或也满足结合律。 (2) 或满足交换律*或也满足交换律。 (3) 对于满足分配律*对于满足分配律。 (4) e1和e2分别是关于和的幺元f(e1)和f(e2)分别为关于*和的幺元。 (5)1和2分别是关于和的零元f(1)和f(2)分别为关于*和的零元。 (6) 对每个xX均存在关于的逆元x-1 对每个f(x)Y也均存在关于*的逆元f(x-1)；,例 与是个满同态，满同态映射为f则： （1）+运算可交换，+m运算也可交换； （2）+运算可结

23、合，+m运算也可结合； （3）对“+”存在幺元e=0,对“+m”存在幺元e=f(0); （4）对“+”某一元素xI，存在逆元 x-1 =-x，则对“+m”某一元素f(x)A,存在逆元f( x-1)=f(-x); 例 P158定理6.3.1的证明,同构举例,S=4,5,6,运算见表(a) P=1,2,3,运算*见表(b) 证明与同构。,表(a),表(b),解答,（1）显然与同类型； （2）寻找双射函数g：SP 方法：特异元素对应特异元素 在中e=6 在中e=3,g(6)=3,g(5)=2,g(4)=1,g(5)=1,g(4)=2,或者,g1(4)=1,g1(5)=2,g1(6)=3 g2(4)=

24、2,g2(5)=1,g2(6)=3,（3）运算的象象的运算,g1(4)=1,g1(5)=2,g1(6)=3 例：g(45)=g(5)=2 g(4)*g(5)=1*2=2 g2(4)=2,g2(5)=1,g2(6)=3 例：g(46)=g(4)=2 g(4)*g(6)=2*3=2 g1 、g2均为同构映射,例 代数系统 F, 与Z4，+4 同构。,两个同构的代数系统，在两个代数系统的运算表中，除了标记不同以外，其表的结构是完全相同的。 而且运算表中两行或两列互换，不改变运算表的性质。 将运算表a进行两行或两列的多次互换，变成与运算表b结构相同的表。,变换运算表的方法,g1,一致,g2,1、2列交

25、换,1,2行交换,一致,同构举例,S=a,b,c,d,运算见表(a) P=1,2,3,4,运算*见表(b) 则与同构。,表(a),表(b),解答,（1）显然与同类型； （2）寻找双射函数g：SP 由表(a)的第4行和表(b)的第1行可知： g(a)=2,g(b)=4 在中c是等幂元 在中3是等幂元,g(c)=3,g(a)=2,g(b)=4, g(c)=3, g(d)=1,变换运算表,g,1,2列交换,2,4列交换,1,2行交换,2,4行交换,一致,4 同余关系 1）代换性质（定义6.4.1） 给定代数系统,其中* 是二元运算。设E是集合X中的等价关系，对任意的x1,x2X，和y1,y2X，当且

26、仅当 (x1Ex2)(y1Ey2) (x1*y1)E(x2*y2) 则称等价关系E对运算*具有代换性质。 2）同余关系（定义6.4.2） 给定代数系统U=，其中*是二元运算。设E是集合X中的等价关系。如果等价关系E对运算*具有代换性质，则称E为代数系统U中的同余关系。 与此对应，称等价关系E的等价类称为同余类。,例 6.4.1 给定代数系统，定义等价关系R为： 对任意i1,i2I,有 i1Ri2|i1|=|i2| 证等价关系R对于运算+,是否有代换性质。 解 (1)对于+运算：设a,-a,bI，显然|a|=|-a|,|b|=|b|,故 aR(-a)，bRb，而aR(-a) bRb 不能(a+b

27、)R(-a+b)， 故R对+没有代换性质 (2)对于运算: 对任意i1,i2I和j1,j2I, 如果有i1Ri2和j1Rj2, 则|i1|=|i2|和|j1|=|j2|，因此必有 |i1j1|=|i2j2|(i1j1) R (i2j2) 故有 i1Ri2 j1Rj2 (i1j1) R (i2j2) 成立。,|a+b| |-a+b|,例 6.4.2 给定代数系统U=，R为I中的模3同余关系（等价关系），即：R=|x,yIx-y可被3整除 证R是U中的同余关系。 证 对任意x1,x2I和y1,y2I, 如果有x1Rx2且y1Ry2, 则x1x2和y1y2都可被3整除，因 (x1+y1)(x2+y2

28、)=(x1x2)+(y1y2), 能被3整除， 即 (x1+y1)R(x2+y2), 即 x1Rx2y1Ry2(x1+y1)R(x2+y2) 故 R是U中的同余关系。,例 6.4.3 代数系统,其中*是I上的一元运算，定义为：*(i)= i2 (mod m)，定义等价关系R为： 对任意i1,i2I, i1Ri2i1 (mod m)=i2(mod m) 证R是代数系统中的同余关系。 证 要证R是同余关系，只需证R对*有代换性质，即 i1Ri2（*i1）R（*i2） 对任意i1,i2I, 如果有i1Ri2, 则有i1 (mod m)=i2(mod m) 可写成 i1 =am+r, i2 =bm+r

29、 *(i1)= i12 (mod m)=(am+r)2(mod m)=(r)2(mod m) *(i2)= i22 (mod m)=(bm+r)2(mod m)=(r)2(mod m) 故*(i1)= *(i2)，故*(i1) (mod m)=*(i2) (mod m) 所以 i1Ri2 （*i1）R（*i2） 故 R是同余关系。,揭示同态与同余关系的定理 ： 定理 给定代数系统U=和V=，和*都是二元运算，设f：XY是从X到Y的映射，则对应同态f，可定义一个U中的关系Rf ，即对任意的x1, x2X，有： x1Rfx2 f(x1)=f(x2) 则称Rf是U中的一个同余关系。 给定一个同态，可

30、确定一个同余关系。,5 商代数 定义 给定代数系统U=及其上的同余关系E，试构成一个新的代数系统W=,其中 (1) X/E=xE|xX (2) x1Ex2E=x1x2E 其中x1，x2X 则称代数系统W=为U关于E的商代数。 可记作 U/E .,例 6.5.1 代数系统U=，R为I中的模3同余关系 （等价关系），即：R=|x,yIx-y可被3整除 试构成U的商代数。 解 I/R=0R,1R,2R, 定义一个代数运算如下： iRjR=(i+j)(mod3)R 故能构成U的商代数U/R = .,商代数举例,设代数系统F=,其中A=a1,a2,a3,a4,a5 *和的运算表如下：,R为A上的等价关系

31、, A/R= a1 ,a3,a2,a5,a4,证明： R是F上的同余关系，并求F的商代数。,证明,(1)R是F上的同余关系 R关于*运算具有代换性质 R关于运算具有代换性质 (2)求F的商代数,证明: R关于*具有代换性质,A/R= a1 ,a3,a2,a5,a4 R=,a1Ra1:,*a1= a4,(a4Ra4),*a1R*a1,a1Ra3:,*a1= a4,*a3= a4,(a4Ra4),*a1R*a3,a3Ra1:,*a3= a4,*a1= a4,(a4Ra4),*a3R*a1,R关于*具有代换性质(续),a3Ra3:,*a3= a4,(a4Ra4),*a3R*a3,a2Ra2:,*a2

32、= a3,(a3Ra3),*a2R*a2,a2Ra5:,*a2= a3,*a5= a1,(a3Ra1),*a2R*a5,a5Ra2:,*a5= a1,*a2= a3,(a1Ra3),*a5R*a2,R关于*具有代换性质(续),a5Ra5:,*a5= a1,(a1Ra1),*a5R*a5,a4Ra4:,*a4= a2,(a2Ra2),*a4R*a4,对任意的x,yA,xRy,*xR*y, R关于*具有代换性质,证明: R关于具有代换性质,a1Ra1:,a1= a3,(a3Ra3),a1Ra1,a1Ra3:,a1= a3,a3= a1,(a3Ra1),a1Ra3,a3Ra1:,a3= a1,a1= a3,(a1Ra3),a3Ra1,a3Ra3:,a3= a1,(a1Ra1),a3Ra3,a2Ra2:,a2= a2,(a2Ra2),a2Ra2,证明: R关于具有代换性质,a2Ra5:,a2= a2,a5= a5,(a2Ra5),a2Ra5,a5Ra2:,a5= a5,a2= a2,(a5Ra2),a5Ra2,a5Ra5:,a5= a5,(a5Ra5),a5