第九章代数系统

1、数学与软件科学院张莉 离散数学第九章第九章 代数系统的一般性质代数系统的一般性质1 二元运算及其性质二元运算及其性质2 代数系统及其子代数和积代数代数系统及其子代数和积代数3 代数系统的同态与同构代数系统的同态与同构4 题例分析题例分析数学与软件科学院张莉 离散数学 本章的主要研究对象是各种各样的代数系本章的主要研究对象是各种各样的代数系统，即统，即具有一些元运算的集合具有一些元运算的集合，代数系统的思想，代数系统的思想和方法已经渗透到现代科学的许多分支，它的结和方法已经渗透到现代科学的许多分支，它的结果已应用到计算机的不少方面，因此计算机科学果已应用到计算机的不少方面，因此计算机科学工作者应

2、初步掌握其基本的理论和方法。工作者应初步掌握其基本的理论和方法。 我们通过对具体代数系统的学习，应初步掌我们通过对具体代数系统的学习，应初步掌握对代数系统研究的一般方法：从简单到复杂、握对代数系统研究的一般方法：从简单到复杂、从具体到一般，从而发现代数系统的一般规律。从具体到一般，从而发现代数系统的一般规律。数学与软件科学院张莉 离散数学 我们在前面已经研究过集合，那时没有我们在前面已经研究过集合，那时没有过多地考虑一个集合内部元素之间的联系。过多地考虑一个集合内部元素之间的联系。现在我们要在一个集合的内部引入运算，并现在我们要在一个集合的内部引入运算，并研究其运算规律，主要内容为：研究其运算

3、规律，主要内容为：l 代数系统的运算的常用记法和运算表的概代数系统的运算的常用记法和运算表的概念，二元运算的各种性质；念，二元运算的各种性质；l 代数系统的定义；代数系统的定义； l 代数系统的各种性质。代数系统的各种性质。数学与软件科学院张莉 离散数学1 二元运算及其性质二元运算及其性质DEFINITION 5.1. 设设S为集合，函数为集合，函数 f :SSS称为称为S上上的一个二元运算，简称为的一个二元运算，简称为二元运算二元运算。如：如： f :NNN， f()=x+y就是自然数集合上就是自然数集合上的一个二元运算，即普通的加法运算。的一个二元运算，即普通的加法运算。考虑，考虑，普通的

4、减法是不是自然数集合上的二元运算普通的减法是不是自然数集合上的二元运算？数学与软件科学院张莉 离散数学 由二元运算的定义可知，验证一个运算是否为集由二元运算的定义可知，验证一个运算是否为集合合S上的二元运算，主要考虑两点：上的二元运算，主要考虑两点：(1) S中中任何任何两个元素两个元素都可以进行都可以进行这种运算，且运算这种运算，且运算的结果是唯一的。的结果是唯一的。（函数）（函数）(2) S中任何两个元素的运算中任何两个元素的运算结果都属于结果都属于S，即，即S对该对该运算是运算是封闭封闭的。的。 通常用通常用 ,等符号表示二元运算，称为等符号表示二元运算，称为算符算符。 设设f :SSS

5、是是S上的二元运算，对任意的上的二元运算，对任意的x,y S，如果如果x与与y的运算结果是的运算结果是z，即，即 f ()=z，则可利用，则可利用算符算符 简记为：简记为： x y=z.数学与软件科学院张莉 离散数学EXAMPLE 5. 1 实数集实数集R上的加法，减法，乘法是二元运算。上的加法，减法，乘法是二元运算。 设设Mn(R)表示所有表示所有n阶实矩阵的集合阶实矩阵的集合(n=2)，即：，即：111212122212.( )nnnijnnnnaaaaaaMRaRaaaMMMML则，矩阵加法和乘法都是则，矩阵加法和乘法都是Mn(R)上的二元运算。上的二元运算。数学与软件科学院张莉 离散数

6、学DEFINITION 5. 2. 设设S为集合，为集合，n为正整数，则函数为正整数，则函数 f :SSSS称为称为S上的一个上的一个n元运算，简称为元运算，简称为n元运算元运算。n个个 类似的，也可以使用算符来表示类似的，也可以使用算符来表示n元运算，若元运算，若 f () = y，则可利用算符，则可利用算符 简记为：简记为： (x1, x2, , xn) = y 或或 x1 x2 xn= y.数学与软件科学院张莉 离散数学 对于对于有穷集有穷集S上的一元和二元运算可以用上的一元和二元运算可以用运算表给出：运算表给出：xi (xi)x1x2xn (x1) (x2) (xn)一元运算表的一般形

7、式一元运算表的一般形式数学与软件科学院张莉 离散数学 x1 x2 xnx1x2xnx1 x1 x1 x2 x1 xnx2 x1 x2 x2 x2 xn xn x1 xn x2 xn xn二元运算表的一般形式二元运算表的一般形式数学与软件科学院张莉 离散数学 设设S=1, 2，给出，给出P(S)上的运算上的运算和和 的的运算表，其中全集为运算表，其中全集为S.EXAMPLE 5.2 1,221121,2xixi 1 2 1,2121,2 1 2 1,21 1,2 2 2 1,2 1 1,2 2 1 数学与软件科学院张莉 离散数学 设设S=1,2,3,4，定义，定义S上的二元运算如下：上的二元运算

8、如下：x y=(xy) mod 5, x, y S. 求求 的运算表。的运算表。EXAMPLE 5.3 1 2 3 41234 1 2 3 4 2 4 1 3 3 1 4 2 4 3 2 1xy表示x乘y,是普通的乘法2 3=1请同学们分析这个二元运算有什么特点？请同学们分析这个二元运算有什么特点？数学与软件科学院张莉 离散数学DEFINITION5.3 5.7 设设 和和*为为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,

9、 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.幂集合上的，运算满足幂等律，可分配律，以及吸收率。数学与软件科学院张莉 离散数学DEFINITION 5.85.10. 设设 为为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,

10、 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的右逆元。的右逆元。数学与软件科学院张莉 离散数学自然数集自然数集N上的加法幺元为上的加法幺元为0，零元，零元不存在不存在;乘法的幺元为：乘法的幺元为：1，零元为：，零元为：0.P(S)上的上的运算幺元为运算幺元为_S_,零元为零元为_;P(

11、S)上的上的运算幺元为运算幺元为_,零元为零元为_S_;EXAMPLE 5.4数学与软件科学院张莉 离散数学定理：定理：5.15.3(1) 设设 为为S上的二元运算，上的二元运算，el, er分别为运算分别为运算 的的左幺元和右幺元，则有：左幺元和右幺元，则有：el=er=e，且，且e为为S上关于上关于运算运算 的唯一的幺元。（的唯一的幺元。（由定义证明由定义证明）(2) 设设 为为S上的二元运算，上的二元运算， l, r分别为运算分别为运算 的的左零元和右零元，则有：左零元和右零元，则有： l= r= ，且，且 为为S上关于上关于运算运算 的唯一的零元。（的唯一的零元。（由定义证明由定义证明

12、）(3) 设设 为为S上可结合的二元运算，上可结合的二元运算，e为为该运算的幺该运算的幺元，对于元，对于x S如果存在左逆元如果存在左逆元yl和右逆元和右逆元yr，则有：，则有： yl= yr=y，且，且y是是x的唯一的逆元。（的唯一的逆元。（由定义证明由定义证明）数学与软件科学院张莉 离散数学证明：证明：(2) l = l r (因为l为左零元) l r = r (因为r为右零元) l = r ，把l = r记作，假设S中存在零元，则有： = = 是S中关于运算 的唯一的零元。数学与软件科学院张莉 离散数学证明：证明：(3) yl = yl e = yl (x yr) = (yl x) yr

13、= e yr = yr， yl = yr ，把yl = yr记作y，假设yS是x的逆元，则有： y= y e = y (x y) = (y x) y = e y = y. 对于可结合的二元运算来说，元素x的逆元如果存在则是唯一的。通常把这个唯一的逆元记作通常把这个唯一的逆元记作x-1.数学与软件科学院张莉 离散数学DEFINITION 5.11 设设 为为S上的二元运算，如果上的二元运算，如果 x, y, z S满足以下满足以下条件：条件：(1) 若若x y = x z且且x不是零元，则不是零元，则y = z， (2) 若若y x = z x且且x不是零元，则不是零元，则y = z，就称运算就

14、称运算 满足满足消去律消去律，其中，其中(1)称作称作左消去律左消去律，(2)称作称作右消去律右消去律。数学与软件科学院张莉 离散数学(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.EXAMPLE 5

15、.5 数学与软件科学院张莉 离散数学（3） 幂集幂集P(S)上的上的运算不满足消去律。运算不满足消去律。取取A, B, C P(S)，由，由AB=AC不一定能得不一定能得到到B=C.同样，同样，运算也不满足消去律。运算也不满足消去律。但但 运算满足消去律。运算满足消去律。 运算不存在零元，运算不存在零元， A, B, C P(S)，都有：，都有：A B=A CB=C，B A=C AB=C.数学与软件科学院张莉 离散数学对于下面给定的集合和该集合上的二元运算，指出该对于下面给定的集合和该集合上的二元运算，指出该运算的性质，并求出它的运算的性质，并求出它的幺元、幺元、零元零元和和所有的逆元所有的逆

16、元。(1) Z+， x, y Z+，x*y=lcm(x, y)，即求，即求x和和y的最小公的最小公倍数。倍数。(2) Q， x, y Q，x*y=x+y-xy.EXAMPLE 5.6 解：解：(1) *运算可交换，可结合，是幂等的。运算可交换，可结合，是幂等的。 x Z+，x*1=x，1*x=x，1为幺元为幺元，不存在零元不存在零元。只有只有1有逆元有逆元，是它自己，其它整数无逆元。，是它自己，其它整数无逆元。数学与软件科学院张莉 离散数学(2) *运算满足交换律，x, yQ，x*y = x+y-xy = y+x-yx = y*x.*运算满足结合律，x, y, zQ，有(x*y)*z=(x+y

17、-xy)*z=(x+y-xy)+z-(x+y-xy)z =x+y+z-xy-xz-yz+xyz，x*(y*z)=x*(y+z-yz)=x+(y+z-yz)-x(y+z-yz) =x+y+z-xy-xz-yz+xyz，(x*y)*z=x*(y*z).*运算不满足幂等律，5Q，但5*5=5+5-55= -155.*运算满足消去律，x, y, zQ，x1（1为零元），证明左消去律成立：若使x*y=x*z，即x+y-xy=x+z-xz，只有y=z时成立。同理可证右消去律也成立。数学与软件科学院张莉 离散数学xQ，有x*0=x+0-x0=x, 0*x=0+x-0 x=x，0是幺元。xQ，有x*1=x+1

18、-x1=1, 1*x=1+x-1x=1，1是零元。xQ，欲使x*y=0和y*x=0，即x+y-xy=0，解得 即).1x(1xxy).1x(1xxx1数学与软件科学院张莉 离散数学2 代数系统及其子代数和积代数代数系统及其子代数和积代数DEFINITION 5.12 非空集合非空集合S和和S上上k个一元或二元运算个一元或二元运算f1, f2, , fk组成的系统称为一个组成的系统称为一个代数系统代数系统，简，简称称代数代数，记作，记作。例如，例如，,都是代数系统。都是代数系统。但，自然数集合但，自然数集合N和普通减法和普通减法-不能构成代数系统，因为两个自不能构成代数系统，因为两个自然数相减可

19、能得到一个负数，所以不能写成然数相减可能得到一个负数，所以不能写成。数学与软件科学院张莉 离散数学 在某些代数系统中对于给定的二元运算存在某些代数系统中对于给定的二元运算存在幺元或零元，我们称之为该系统的在幺元或零元，我们称之为该系统的特异元特异元素素或或代数常数代数常数。例如，例如，中的中的和和的幺元分别的幺元分别为为和和S，可将，可将记为记为 。数学与软件科学院张莉 离散数学DEFINITION5.13 设设V=是代数系统，是代数系统，B S，如果，如果B对对f1, f2, , fk都是封闭的，且都是封闭的，且B和和S含有相同的代数常数，含有相同的代数常数，则称则称是是V的的子代数系统子代

20、数系统，简称，简称子代数子代数。例如，例如，是是的子代数：因为的子代数：因为N对对+是封闭是封闭的，且它们都没有代数常数。的，且它们都没有代数常数。是是的子代数：因为的子代数：因为N对对+是封闭的，是封闭的，且它们都含有相同的代数常数且它们都含有相同的代数常数0。是是的子代数，但不是的子代数，但不是的子的子代数：因为代数：因为的代数常数的代数常数0 N-0。数学与软件科学院张莉 离散数学平凡的子代数平凡的子代数：最大和最小的子代数。最大和最小的子代数。最大的子代最大的子代数数是是V本身。如果令本身。如果令V中所有代数常数构成的集合中所有代数常数构成的集合是是B，且，且B对对V中所有的运算都是封

21、闭的，则中所有的运算都是封闭的，则B就构成就构成了了V的的最小的子代数最小的子代数。真子代数真子代数：如果如果V的子代数的子代数V=满足满足B S，则称，则称V是是V的真子代数。的真子代数。数学与软件科学院张莉 离散数学设设V=，令，令nZ=nz|z Z，n为自然数。为自然数。证明证明nZ是是V的子代数。的子代数。EXAMPLE 5 .7 证明：证明：(1) nZZ；(2) nz1, nz2nZ(z1, z2Z)，则有nz1+nz2=n(z1+z2)nZ，即nZ对+运算是封闭的；(3) 0=n0nZ。nZ是的子代数。数学与软件科学院张莉 离散数学DEFINITION 5.14. 设设V1=，V

22、2=是代数系统，是代数系统，其中其中 和和*是二元运算。是二元运算。V1和和V2的的积代数积代数V1 V2是含有一个二元运算是含有一个二元运算的代数系统，即的代数系统，即V1 V2=，其中，其中，S=S1 S2，且对，且对 , S1 S2，有，有 =.数学与软件科学院张莉 离散数学设设V1=，V2=，其中，其中+和和分别分别表示整数加法和矩阵乘法，则表示整数加法和矩阵乘法，则V1 V2=， , Z M2(R)，有，有 = .EXAMPLE 5.8 .021231012211015，例如：例如：数学与软件科学院张莉 离散数学 设设V1=，V2=，则则V1和和V2的的积代数积代数V1 V2=，其中

23、，其中，a=。的的代代数数常常数数。是是积积代代数数其其中中，则则，例例如如，21222211001, 01001, 0,),(,),(0 ,VVRMZVV1001 RMVZV1数学与软件科学院张莉 离散数学积代数性质积代数性质 如果V1和V2中的二元运算都是可交换的(可结合的或幂等的)，则积代数中相应的二元运算也是可交换的(可结合的幂等的)。如果e1,e2分别为V1,V2的幺元，那么就是积代数V1V2的幺元。同样可以得到逆元的性质。数学与软件科学院张莉 离散数学3 代数系统的同态与同构代数系统的同态与同构DEFINITION 5.15 设设V1=，V2=，其中，其中， 和和*是是二元运算，二

24、元运算，k1 S1，k2 S2是代数常数是代数常数，如果映射，如果映射 : S1S2满足以下条件：满足以下条件： x, y S1，都有：，都有： (x y)= (x) * (y) (k1)=k2.则称则称 是是V1到到V2的的同态映射同态映射，简称，简称同态同态。 设设V1=，V2=，其中，其中， 和和*是是二二元运算，如果映射元运算，如果映射 : S1S2满足以下条件：满足以下条件： x, y S1，都有：，都有： (x y)= (x) * (y)则称则称 是是V1到到V2的的同态映射同态映射，简称，简称同态同态。数学与软件科学院张莉 离散数学 设设V1=，V2=，其中，其中+为普通为普通加

25、法，加法， 为模为模n加法，即加法，即 x, y Zn，有，有x y=(x+y) mod n，这里这里Zn=0, 1, , n-1。令。令 : ZZn， (x)=(x) mod n，则则 是是V1到到V2的同态。的同态。EXAMPLE 5.9 x, y Z，有：，有： (x+y)=(x+y) mod n=(x) mod n (y) mod n = (x) (y).数学与软件科学院张莉 离散数学 设设V1=，V2=，其中，其中R为实数为实数集合，集合，+和和为普通加法和乘法。为普通加法和乘法。令令 : RR， (x)=ex，则则 是是V1到到V2的同态。的同态。EXAMPLE 5.10 x, y

26、 R，有：，有： (x+y) = ex+y = ex ey = (x) (y).数学与软件科学院张莉 离散数学 设设V1=，V2=，其中，其中， 和和 是二元运算，是二元运算，和和是一元运算，是一元运算，k1 S1，k2 S2是代数常数，如果映射是代数常数，如果映射 : S1S2满足以满足以下条件：下条件： x, y S1，都有：，都有： (x y)= (x) (y)， (x)= (x)， (k1)=k2.则称则称 是是V1到到V2的的同态映射同态映射，简称，简称同态同态。同态映射推广到含有同态映射推广到含有k个运算的代数系统个运算的代数系统数学与软件科学院张莉 离散数学 设设V1=，V2=，

27、其中，其中+和和 分别表示普通加法和乘法，分别表示普通加法和乘法，-x表示求表示求x的相反数，的相反数，x -1表示求表示求x的倒数。的倒数。令令 : RR+ ， (x)=ex，则则 是是V1到到V2的同态。的同态。EXAMPLE 5.11 x, y R，有：，有： (x+y)= ex+y = ex ey = (x) (y), (-x)= e-x = (ex)-1= ( (x)-1.数学与软件科学院张莉 离散数学 设设V1=，V2=，其中，其中+为为普通加法，普通加法， 为模为模n加法，加法，令令 : ZZn， (x)=(x) mod n，则则 是是V1到到V2的同态。的同态。EXAMPLE 5.12 x, y Z，有：，有： (x+y) = (x+y) mod n = (x) mod