离散数学的代数理论

1、2022-6-27zhengjin,csu1 第六章第六章 代数代数 代数代数: : 也叫代数结构，或代数系统，是指定义有若干运算的集合。如整数集合，在其上定义了加法、乘法，就成为一个代数系统代数系统。 抽象代数：抽象代数：1. 不关心代数系统的具体集合是什么不关心代数系统的具体集合是什么2. 2. 不关心集合上的运算如何定义不关心集合上的运算如何定义3. 3. 假设这些运算满足某些规则假设这些运算满足某些规则 (如结合律，交换律，分配律等)，然后根据这样的抽象代数系统，来讨论该系统应具有的性质，使所得结论具有普遍意义。2022-6-27zhengjin,csu2本章主要内容本章主要内容1.代

2、数的基本概念，如代数的构成、代数的表示、代数的特异元素；子代数的概念 (6.1,6.2)2.代数间的同构、同态概念，同态象的概念 (6.3)3.一种特殊的等价关系同余关系,商代数 (6.4,6.5)4.特殊的代数：半群，独异点, 群 (6.6,6.7)5. 特殊的代数：环和域 (6.8)2022-6-27zhengjin,csu3代数的结构代数的结构代数由3部分构成： 1. 一个集合集合-（代数的载体） 2. 定义在载体上的运算运算 3. 载体中的特异元素，叫做代数的常数代数的常数 （么元和零元）（么元和零元）代数通常用载体载体、运算运算和常数常数的n重组表示 通俗地说：代数就是由集合及定义在

3、其上的运算及相关：代数就是由集合及定义在其上的运算及相关常数组成。常数组成。 2022-6-27zhengjin,csu4载体与载体上的运算载体与载体上的运算 （）运算的概念具有一定的广泛性与抽象性，它不仅包括日常用（）运算的概念具有一定的广泛性与抽象性，它不仅包括日常用的的“+ +”，“- -”， “”，“/ /” 等运算，也包括抽象的运算，如集等运算，也包括抽象的运算，如集合的合的“并并”， “交交”，字符串的，字符串的“并并”等。等。 （）在集合（）在集合S S上的运算可以有多个，如在实数域上的上的运算可以有多个，如在实数域上的 “+ +”， “”。运算可以是一元的，也可以是二元的，也可

4、以是多元的。即是从运算可以是一元的，也可以是二元的，也可以是多元的。即是从S Sm m到到S S的函数。但一般代数系统在的函数。但一般代数系统在S S上的运算最多不超过三个，而且以上的运算最多不超过三个，而且以研究一元、二元为限。研究一元、二元为限。 2022-6-27zhengjin,csu5运算的表示运算的表示naaa21)()()(21naaaia)(ia),(),(),(),(),(),(),(),(),(212221212111nnnnnnaaaaaaaaaaaaaaaaaanaaa 21naaa2175311357ia)(ia753173717535753375317531p例如:

5、A=1,3,5,7 , 定义一种一元运算 和二元运算 * 表示如下:2022-6-27zhengjin,csu6载体上的运算载体上的运算（）运算符的表示：（）运算符的表示：“ ”或或“* *”、“”等。有时等。有时也用也用“+ +”，“”等表示。但此时等表示。但此时“+ +”，“”的含义的含义不一定就是普通算术运算中的不一定就是普通算术运算中的“加加”与与“乘乘”的含义，的含义，所有这些运算符的含义可以根据不同的定义而具有不所有这些运算符的含义可以根据不同的定义而具有不同的意义。同的意义。 （）运算在载体（）运算在载体S S上还应该是上还应该是封闭的封闭的。( (载体载体S S中的元中的元素经

6、某一运算后它的结果仍在素经某一运算后它的结果仍在S S中，则此称运算在集中，则此称运算在集合合S S上是封闭的上是封闭的) ) 2022-6-27zhengjin,csu7代数举例代数举例例例1 1 整数集，加法和常数0可构成代数： 记为： 例例2 2 幂集合(S)，集合的并，交，补运算，常数， 和S可构成代数。 记为：例例3 3 自然数集N，乘法和常数1可构成代数。 记为： 例例4 4 自然数集N，乘法、加法和常数0和1可构成代数。 记为：2022-6-27zhengjin,csu8代数分类代数分类通常我们不去研究单个的具体的代数，而是对代数进行分类研究。分类原则如下：1.1.有相同的构成成

7、分。（即如果两个代数包含同样个数的运算和有相同的构成成分。（即如果两个代数包含同样个数的运算和常数，且对应运算的元数相同，则这两个代数有相同的构成常数，且对应运算的元数相同，则这两个代数有相同的构成成分。）成分。）2.服从相同的公理规则。服从相同的公理规则。 如：交换律，结合律，分配律，吸收律等。如：交换律，结合律，分配律，吸收律等。 具有相同构成成分和服从相同的公理规则的代数就称为是同种类的。对同一种类的代数，根据它的公理推出的定理对该种类的一切代数都成立。2022-6-27zhengjin,csu9(1)如代数如代数和和有相同的构成成分有相同的构成成分. . ( (都只有一个运算都只有一个

8、运算, ,且都是二元运算且都是二元运算, ,和和1 1个常数个常数).).(2)代数代数 0,1, ,0,1 和和 (S), (S), ，, ,S,S (都有两个二元运算,两个常数)2022-6-27zhengjin,csu10公理规则公理规则例例3 3：对于自然数集对于自然数集N N，及定义其上的加法运算，及定义其上的加法运算+ +，构成的代数：，构成的代数：N0 服从公理规则：服从公理规则： a+ba+b= =b+ab+a 交换律交换律 ( (a+b)+ca+b)+c= =a+(b+ca+(b+c) ) 结合律结合律 a+0=a 0a+0=a 0是是么元么元（单位元）（单位元） 则：则：I

9、1和和 等是和其同一类的代数等是和其同一类的代数 ( (因为都只有一个二元运算，都满足交换律，结合律，一个常数因为都只有一个二元运算，都满足交换律，结合律，一个常数是么元是么元) )。 2022-6-27zhengjin,csu11公理规则公理规则例例4 4 考虑具有考虑具有 I0,1形式构成形式构成成分和下述公理的代数类成分和下述公理的代数类( + ( + ：加法，：加法， ：乘：乘法运算，法运算，- - ：一元运算，：一元运算，0 0和和1 1 ：常数：常数) )(1)(1) a+ba+b= =b+ab+a(2)(2) a.ba.b= =b.ab.a (3)(3) ( (a+b)+ca+b

10、)+c= =a+(b+ca+(b+c) ) (4)(4) ( (a.b).ca.b).c= =a.(b.ca.(b.c) )(5)(5) a.(b+ca.(b+c)=)=a.b+a.ca.b+a.c (6)(6) a+(-a)=0 a+(-a)=0 (7)(7) a+0=a a+0=a (8)(8) a.1=a a.1=a 则则Q0,1，R0,1是与之同一类的代是与之同一类的代数。数。2022-6-27zhengjin,csu12么元和零元么元和零元前面已介绍：代数常数是关于某些运算的特异元素，具体地说就前面已介绍：代数常数是关于某些运算的特异元素，具体地说就是下面要介绍的是下面要介绍的么元么

11、元和和零元零元定义定义1 1 设设* *是是S S上的二元运算，上的二元运算，1 1l l 是是S S的元素，如果对的元素，如果对S S中的每个中的每个元素元素x,x,有有 1 1l l * *x=xx=x 则称则称1 1l l对运算对运算* *的的左么元左么元。S S中的元素中的元素0 0l,l, , ,如果对如果对S S中的中的每一元素每一元素x,x,都有都有 0 0l l * *x=0 x=0l l 则称则称0 0l l是对运算是对运算* *的的左零元左零元。 类似地，有类似地，有右么元右么元和和右零元右零元的定义。的定义。 2022-6-27zhengjin,csu13例例5 5 代数

12、A的运算*如下表所示 很显然很显然: :a a是是* *的左么元的左么元a a也是也是* *的右么元，的右么元，b b是是* *的左零元。的左零元。 没有右零元。没有右零元。*a b c abca b c b b b c c b 判断方法：观察运算的行和列：观察运算的行和列：若存在某一行和上边行相同，则其若存在某一行和上边行相同，则其左边左边的元素就是运算的的元素就是运算的左么元左么元。若存在某一列与左列相同，则其若存在某一列与左列相同，则其上方上方的元素就是运算的的元素就是运算的右么元右么元。2022-6-27zhengjin,csu14么元和零元的定义么元和零元的定义定义定义2 2 设设*

13、 *是是S S上的二元运算，上的二元运算，1 1是是S S的元素，如果对的元素，如果对S S中的中的每一元素每一元素x,x,有有 1 1* *x=xx=x* *1=x1=x 则称则称元素元素1 1对运算对运算* *是么元是么元。若。若0 0是是S S中的元素，且对中的元素，且对S S中的中的每一元素每一元素x x，有，有 0 0* *x=xx=x* *0=00=0 则称则称元素元素0 0对运算对运算* *是零元是零元。 2022-6-27zhengjin,csu15例例6 6 (1)(1)代数代数I1,0， 表示乘法，有一个么元表示乘法，有一个么元1 1和零元和零元0 0 (2) (2)代数代

14、数N + 有么元有么元0 0，但无零元。，但无零元。 (3)(3)代数代数Nmin有一个零元有一个零元0 0，但无么元。，但无么元。2022-6-27zhengjin,csu16么元和零元的性质么元和零元的性质定理定理： 设设* *是是S S上的一个二元运算，若同时具有上的一个二元运算，若同时具有左么元左么元a a和和右么右么元元b b，则，则a=a=b,ab,a就是么元就是么元。 证明：由证明：由a a是左么元知：是左么元知：a a* *b=bb=b 由由b b是右么元知：是右么元知：a a* *b=a b=a 所以所以a=b,a=b, 所以所以a a也是右么元。也是右么元。a a就是么元就

15、是么元 ( (这个定理说明：如果这个定理说明：如果同时同时存在存在左么元左么元和和右么元右么元，则二者，则二者相等相等，且就是么元且就是么元，么元若存在，么元若存在，只有一个只有一个) ) 对于零元也有类似结果。对于零元也有类似结果。 定理：设定理：设* *是是S S上的一个二元运算，若上的一个二元运算，若同时同时具有具有左零元左零元a a和和右零元右零元b b，则，则a=a=b,ab,a就是零元就是零元。 2022-6-27zhengjin,csu17 逆元逆元 如果在一代数中存在么元，则可定义逆元。如果在一代数中存在么元，则可定义逆元。定义定义3 3 设设* *是是S S上的二元运算，上的

16、二元运算，1 1是对运算是对运算* *的的么元么元， 如果如果x x* *y=1,y=1,则对运算则对运算* *，x x是是y y的的左逆元左逆元，y y是是x x的的右逆右逆元元， 若若x x* *y=1y=1和和y y* *x=1x=1同时同时成立，则对运算成立，则对运算* *，x x是是y y的的逆元逆元( (当然当然y y也是也是x x的逆元的逆元) )，通常，通常x x的逆元记为的逆元记为: :x x-1-12022-6-27zhengjin,csu18例例 7 （1）代数代数A=A= 的运的运算算* *如右表定义：如右表定义： 对于运算对于运算* *： b b是是么元么元。 a a

17、的右逆元是的右逆元是c,cc,c的的左逆元是左逆元是a a， b b的的逆元逆元是是b.b.*a b c abca a b a b c a c c 2022-6-27zhengjin,csu19逆元的性质逆元的性质（2）代数代数有么元有么元0，但只有，但只有0有逆元，有逆元，而其它元素都无逆元。而其它元素都无逆元。 (3)(3)代数代数有么元有么元1 1，但只有，但只有0无逆元，无逆元，而其它元素都有逆元。而其它元素都有逆元。其它如例其它如例6(P166)(e,f,g)6(P166)(e,f,g)2022-6-27zhengjin,csu20逆元的唯一性逆元的唯一性定理定理 对于可结合运算对于

18、可结合运算* *，如果一个元素，如果一个元素x x有有左逆元左逆元a a 和和右逆元右逆元b b，则，则a=ba=b ( (即即逆元是唯一的逆元是唯一的) ) 证明：设证明：设1 1是运算是运算* *的的么元，则么元，则a a* *x=xx=x* *b=1b=1由由* *的的可结合性可结合性，得：，得：a=aa=a* *1=a1=a* *(x(x* *b)=(ab)=(a* *x)x)* *b=1b=1* *b=bb=b2022-6-27zhengjin,csu21定义定义4 4 设设* *是是S S上的二元运算，上的二元运算，a aS S, , 如果对于如果对于 每一每一x x、y yS S

19、都满足：都满足： 如果如果 a a* *x=ax=a* *y y或或 x x* *a=ya=y* *a a 则有则有x=y ,x=y ,则称则称a a是是可约的可约的或或可消去的可消去的。2022-6-27zhengjin,csu22定理定理：设设* *是是S S上的可结合运算，如果元素上的可结合运算，如果元素a a是是可逆的可逆的，则，则a a也是也是可约的可约的. .证明：由于证明：由于a a是可逆的，记是可逆的，记a a的逆元为的逆元为a a-1-1, , 设设a a* *x=ax=a* *y y，于是，于是 a a-1-1* *(a(a* *x)=ax)=a-1-1* *(a(a* *

20、y) y) 而而 a a-1-1* *(a(a* *x)=( ax)=( a-1-1* *a)a)* *x=xx=x a a-1-1* *(a(a* *y)=( ay)=( a-1-1* *a)a)* *y=yy=y所以所以 x=yx=y，即，即a a是可约的。是可约的。2022-6-27zhengjin,csu23但反之却不一定成立。即是可约的，则不一定是可逆的。但反之却不一定成立。即是可约的，则不一定是可逆的。如在整数集如在整数集I I中，对于乘法，除中，对于乘法，除0 0外的元素都是可约的，但外的元素都是可约的，但除除1 1之外，之外，都不是可逆的都不是可逆的。2022-6-27zhen

21、gjin,csu24本节要求本节要求o掌握代数系统的概念掌握代数系统的概念,对运算的对运算的封闭性封闭性、么元么元、零元零元、逆元逆元等等相关结论有清晰的理解，给定集合和集合上的运算，能够判相关结论有清晰的理解，给定集合和集合上的运算，能够判断该集合对运算是否封闭断该集合对运算是否封闭,能够通过运算表确定么元、零元、能够通过运算表确定么元、零元、逆元（如果存在的话）。对交换律、结合律、分配律等的表逆元（如果存在的话）。对交换律、结合律、分配律等的表示要十分清楚。给定集合及集合的二元运算表，能够判断运示要十分清楚。给定集合及集合的二元运算表，能够判断运算是否满足交换律、是否满足结合律。算是否满足

22、交换律、是否满足结合律。o掌握可约性的概念和相关结论。掌握可约性的概念和相关结论。2022-6-27zhengjin,csu25本节作业本节作业o 课堂作业： 1，5，9,4o 6，7，8，10，112022-6-27zhengjin,csu26课堂练习课堂练习o (S)，对运算的单位元（么元）是什么，零元是什么？对运算的单位元（么元）是什么？零元是什么？2(判断)设*是上的可结合运算，若aS是可逆的，则a也是可约的反之，也成立2022-6-27zhengjin,csu276.2 6.2 子代数子代数 以后常研究的代数形式：S k 代表二元运算。表示一元运算， k表示常数。定义定义1 1 设和

23、是集合S上的二元运算和一元运算，S是S的子集。如果a、bS，一定有abS, 则称S对运算是封闭的。如果aS,一定有aS,那么S对是封闭的。 例如：集合S=1,2,3,4，对加法不封闭，但对max,min,绝对值运算等是封闭的。2022-6-27zhengjin,csu28定义定义2 2 设设 A=A=Sk是一代数，如果是一代数，如果 (1)(1) S S S S (2) (2) S S对对S S上的运算上的运算 和封闭。和封闭。 (3)(3) k kSS 那么那么 A A=k是是A A的的子代数子代数。子代数的定义子代数的定义 例例7 (1) 7 (1) 代数系统代数系统E0是是I0的子代数。

24、的子代数。 (2) (2) 设设E E：偶数集合偶数集合 ，M M：奇整数集合，奇整数集合， 则则 E0是是I0的子代数，的子代数， 但但 M+不是不是I+的子代数。的子代数。 M,1是是I,1的子代数的子代数 2022-6-27zhengjin,csu29子代数的有关说法子代数的有关说法v 如果A是A的子代数，那么A和A有相同的构成成分和服从相同的公理。v A的最大子代数是它自己最大子代数是它自己。如果A的常数集合在A的运算下封闭，则它是A的最小子代最小子代数数。这两种子代数称为A的平凡子代数。v 其它子代数称为真子代数。 2022-6-27zhengjin,csu30课堂练习课堂练习o P

25、169 1,22022-6-27zhengjin,csu31两节小结两节小结1.掌握代数的概念2.代数的表示 (n重组表示）3.两个代数是否是同一种类的条件4.常用到的公理规则(方程式表示)5.会由运算表求代数的运算的(左、右)么元，零元，及逆元。)子代数的概念7.可逆与可约两个概念的相互关系. 2022-6-27zhengjin,csu326.3 同构与同态同构与同态 1. 同构同构 世界上存在着很多的代数系统，但有些代数系统，它们之间虽然表面上似乎不相同，但是它们实际上是“相同”的。 如两个代数系统: 与 仅仅是元素和运算符的表示形式不同，而它们的实质是一样的。 称它们是同构的。 0 1

26、010 1 1 * a b aba b b b 2022-6-27zhengjin,csu33同构的定义同构的定义同构的必要条件： (1) 它们必须有相同的构成成分构成成分。（2) 它们的载体的元素“个数个数”要相同要相同。 (3) 运算和常数必须遵循相同的规则相同的规则。2022-6-27zhengjin,csu34定义定义1 1 代数代数A=A=Sk和和A=A=S 是两个代数系统。是两个代数系统。如果存在一如果存在一双射函数双射函数 h h：S SS S, 对任意对任意S S中元素中元素a,ba,b, ,使得：使得： （1 1）h(ah(a* *b)=b)=h(ah(a) )* *h(bh

27、(b) () (运算运算* *保持保持) ) （2 2）h(h(a a)=)=h(ah(a) () (运算保持运算保持) ) （3 3）h(kh(k)=k ()=k (常数对应常数对应) ) 则称代数则称代数A A和和AA是同构的是同构的; ; 映射映射h h叫做从叫做从A A到到AA的同构的同构; ; A A叫做叫做A A在在h h下的同构象下的同构象; ; 如果如果A A和和AA是同构的，它们基本上是不同名的相同结构，简单地是同构的，它们基本上是不同名的相同结构，简单地调换符号就能从调换符号就能从A A得到代数得到代数AA。2022-6-27zhengjin,csu35例例8 8 代数系统

28、R1同构于R0因为：作映射h: R+R h(x)= log x h显然是双射的。且：h(x*y)=log(x*y)=logx+logy=h(x)+h(y) h(1)=log1=0 所以和同构。2022-6-27zhengjin,csu36例例9 9 集合A=1，2,3，4，函数f:AA， f=, 设 F=f0,f1,f2,f3,则代数与代数同构运算表可分别表示如下表示：作映射作映射h:Fh:FN N4 4 h(fh(fi i)=i ,(i=0,1,2,3)=i ,(i=0,1,2,3) f0 f1 f2 f3 f0 f1f2 f3f0 f1 f2 f3 f1 f2 f3 f0f2 f3 f0

29、f1 f3 f0 f1 f2 +4 0 1 2 30 1 2 30 1 2 31 2 3 02 3 0 13 0 1 22022-6-27zhengjin,csu37不同构例不同构例例10 代数 和不同构.证明:反证法. 假设h是从 到的一个同构。I+ 中有无限多的质数，因h是从N到I+ 的一个双射函数，故有x N且x=2,和某质数p,使h(x)=p,如果h是从 到的同构。则（1）h(x)=h(x+0)=h(x)*h(0) (2) h(x)=h(x-1+1)=h(x-1)*h(1)因p是质数，只有因子p和1，所以据（1）知：h(x)=1或h(0)=1据（2）知h(x-1)=1或h(1)=1而0

30、1x-1x因此在映射h下，1至少有两个原象，因此h不可能是双射。这与h是同构矛盾！2022-6-27zhengjin,csu38同构关系是等价关系同构关系是等价关系定理：定理：设 C 是代数集合，A、A是C的任意元素，R是关系，定义：ARAARA当且仅当当且仅当A A和和A A同构同构。则R是C上的等价关系。 自反性：任何一个代数与它自己同构。(作恒等变换即可：是 双射，且运算保持) 对称性 ：(根据双射函数的逆函数也是双射函数证明之) 传递性：(根据两个双射函数的合成还是双射证明之) 由于同构关系是等价关系，所以我们设所有的代数系统构成一个集合A，我们可按同构关系R将其分类，得到商集A/R，

31、由于同构的代数系统具有相同的性质，故实际上代数系统所需要研究的总体不是A，而是A/R.o 2022-6-27zhengjin,csu396.3.2 同态同态 (1) (1) 如果我们将同构的条件放宽一点，如果我们将同构的条件放宽一点， 放弃同构中放弃同构中h: h: S SS S必须是双射的要求，则我们可以得到比同构范围必须是双射的要求，则我们可以得到比同构范围更广的一些关系。更广的一些关系。(2) (2) 我们希望放宽后的关系，使两个代数系统不一定要我们希望放宽后的关系，使两个代数系统不一定要有相同的基数，但是能在一定意义上保持其性质，为此有相同的基数，但是能在一定意义上保持其性质，为此我们

32、引入同态的概念。我们引入同态的概念。2022-6-27zhengjin,csu40同态的定义同态的定义定义定义2 2 设代数设代数A=A=Sk和和 A=A=S 具有相同的构成成具有相同的构成成分分。 如果存在一函数一函数 h h：S SS S,对S中任意元素a,b,使得： h(ah(a* *b)=b)=h(ah(a) )* *h(bh(b) ) (运算*保持) h(h(a a)=)=h(ah(a) ) （运算保持) h(kh(k)=k)=k (常数对应)则称 h h：从：从A A到到AA的同态的同态， 称为称为A A在映射在映射h h下的同态象。下的同态象。 2022-6-27zhengjin

33、,csu41有关同态的定义有关同态的定义 若h是单射的，则称h是单一同态； 若h是满射的，则称h是满同态， 只有是满同态时，才称A和A同态。 (若A=A,称h是自同态) 提醒：提醒： h h(S(S) )可能真包含于可能真包含于S S，也可能等于，也可能等于S S2022-6-27zhengjin,csu42同态的例子同态的例子例例 映射映射f:II,f(xI,f(x)=)=kx,kkx,k中整数，中整数，f f是从，到，的自同态是从，到，的自同态因为因为: : (1)f(x+y)=(1)f(x+y)=k(x+yk(x+y)=)=kx+kykx+ky= =f(x)+f(yf(x)+f(y) )

34、 (2)f(0)=0 (2)f(0)=0所以所以f f是从是从，到，的自同态，到，的自同态且如果且如果k0,k0,则则f f是单射的，是单射的，f f是单一同态；是单一同态；若若k=1k=1或或k=-1,k=-1,则则f f是双射此时是双射此时f f是自同构是自同构v 2022-6-27zhengjin,csu43例设例设 f:R R, f(x)=2x f是从，到，的单一同态是从，到，的单一同态因为因为 :(1) f(x+y)=2(x+y)=2x.2y=f(x).f(y)(2) f(0)=20=1(3) f是单射的是单射的2022-6-27zhengjin,csu44例设例设f:NNNk k(

35、k(k0),f(x)=x (mod 0),f(x)=x (mod k),fk),f是从，是从，到到k k,+,+k k,0,0的满同态的满同态因为：因为： (1) (1) f(x+yf(x+y)=()=(x+y)(modx+y)(mod k)= k)=x(modx(mod k)+k)+k k y(mody(mod k) k) = =f(xf(x) +) +k k f(yf(y) ) (2) f(0)=0 (2) f(0)=0且且f f是满射是满射2022-6-27zhengjin,csu45P172v 定理定理6.3-2 设设h h是从代数是从代数 A=A= Sk和和A=A=S 的的同态同态,

36、 ,那么：那么：A A的的同态象同态象 是是AA的的子代数子代数( (根据子代数的定义以及根据子代数的定义以及h h是是A A到到A A的同态可容易得出的同态可容易得出这个结论这个结论.).)2022-6-27zhengjin,csu46A与与A的同态象的关系的同态象的关系A的同态象是A的缩影：即A中有关运算和常数的性质在A的同态象的同态象中被保持即下面的定理3.2022-6-27zhengjin,csu47 设设h h是从代数是从代数 A=A=到到A=的的同态，同态，*，*，都是二元运算，都是二元运算，A A* *=是是A的同态象。的同态象。 （1）如果）如果*是可交换是可交换(结合结合)的

37、，则的，则*也是也是可交换可交换( (结合结合) )的，的，和和也如此。也如此。 （2 2）对运算）对运算*，有么元，有么元( (零元零元)e)e，则对运算，则对运算*，在代数，在代数A A* *中也有中也有么元么元( (零元零元) )h(eh(e).).对于对于， 也有如此结论。也有如此结论。定理定理6.3-3 P1732022-6-27zhengjin,csu483）对于运算）对于运算*，如果，如果xS有逆元有逆元x-1存在，则对于存在，则对于*，在代数，在代数A*中，中，h(x)有逆元有逆元(h(x) -1。4）如果运算）如果运算*对运算对运算是可分配的，则在是可分配的，则在A*中，中，

38、*对对也是可分配的。也是可分配的。(证明较简单，只要根据同态的含义就可证出，教材证明较简单，只要根据同态的含义就可证出，教材P173有详细的证明，一定要掌握同构，同态的有详细的证明，一定要掌握同构，同态的定义及真正含义定义及真正含义 )。 2022-6-27zhengjin,csu49 例1 h:Rh:R R , R ,且且h(xh(x)=e)=ex x, ,则则h h是从代数是从代数A=A=到到A=A=的同态的同态, ,在在h h下下A A的同态象的同态象R,.,1是是AA的子代数的子代数. . ( (因为因为: :h(x+yh(x+y)=)=e e(x+y(x+y) )= =e ex x.

39、e.ey y= =h(x).h(yh(x).h(y) ) h(0)=e h(0)=e0 0=1=1同态象是子代数的例子同态象是子代数的例子2022-6-27zhengjin,csu50o 例3 设S=a,b,c,d, S=0,1,2,3,代数A=和B=由下表定义:* 0 1 2 30 12 30 1 1 01 1 2 11 2 3 20 1 2 3* a b c d a bc da b c db b d dc d c dd d d dH定义如下定义如下:h:SSS h(ah(a)=)=h(ch(c)=0,h(b)=)=0,h(b)=h(dh(d)=1)=12022-6-27zhengjin,c

40、su51 (1) 显然h保持运算. (2)由于不考虑常数,所以h是A到B的同态。 同态象保持代数A的可交换性和可结合性。 (3)但代数B不可结合,且代数A有么元a和零元d,故h(a)=0和h(d)分别是同态象的么元和零元,但不是代数B的么元和零元. B中么元是3,零元不存在.2022-6-27zhengjin,csu52本节要求: 掌握代数系统的同态与同构的定义.o 能判断两个给定的代数系统是否是同构的,是否是同态的.2022-6-27zhengjin,csu53本节作业o 课堂作业:1,3o 书面作业:4,8,92022-6-27zhengjin,csu546.4 同余关系同余关系例例1 1

41、 代数上的关系R如下： R=x,yI,且x-y能被3整除显然这是一个等价关系，它将I划分为三类： 0R=,-6,-3,0,3, 1R=,-5,-2,1,4,2R=,-4,-1,2,5, 这个关系R有一个特点：它能把所划分的类0R,1R,2R中两个类的元素相加后所得结果均在相同的类内。 上述关系上述关系R R是一个是一个 同余关系同余关系，将这种概念推广，凡满足此种特性的等价关系均称为同余关系。 2022-6-27zhengjin,csu55同余关系的定义同余关系的定义 同余关系，是一种比等价关系还要强的关系。 为了叙述简单，我们把代数A=作为讨论对象, *是二元运算，是一元运算, 并把a*b

42、写成 ab定义定义1 1 设 是代数A=的载体S上的一个等价关系，a,b,c是S的任意元素：(1) 当a a b b,若有 ac ac bcbc 和和ca ca cbcb,则称等价关系 在运算 *下，具有置换性质。或者说，等价关系 在运算 *下，仍能保持。(2) 当a a b,b,若有a a b b，则称等价关系 在运算下仍能保持。2022-6-27zhengjin,csu56定义定义2 2 在代数载体上的等价关系 ，如果在代数运算下，仍能保持，那么称 是关于运算的同余关系。2022-6-27zhengjin,csu57例1 给定代数给定代数A=，是如下定义的，是如下定义的 一元运算：一元运算

43、： a=a2 设设 是是I上的模上的模k同余关系。同余关系。 设设a b，即，即:a-b=nk a-b= a2-b2=(a+b)(a-b)=nk(a+b)所以所以a b ，故，故 是关于运算的同余关系。是关于运算的同余关系。2022-6-27zhengjin,csu58定义定义3 3 设设 是代数是代数A=SA= 的载体的载体S S上的等价关系，上的等价关系，如果对一切如果对一切a,b,cSa,b,cS, ,都有：都有：(1)(1) 若若a a b,b,则则ac ac bcbc且且ca ca cbcb ( (对运算对运算* *是同余的是同余的) )(2)(2) 若若a a b b，则，则a a

44、 b (b (对运算是同余的对运算是同余的) ) 则称则称为为代数代数A A上的同余关系上的同余关系。 的等价类叫做关系的等价类叫做关系 的的同余类同余类。 (即如果等价关系对代数的每一运算都是同余关系，此等价关系才是该代数上的同余关系)2022-6-27zhengjin,csu59例例2 2 对任一代数对任一代数A=SA=1，相等关系和全域关系都是，相等关系和全域关系都是A A上上的同余关系。的同余关系。 证明：设证明：设 是相等关系。设是相等关系。设a a b,b,即即a=ba=b 则对则对S S中任意元素中任意元素c,acc,ac= =bcbc且且ca=ca=cbcb 所以所以ac ac

45、 bcbc且且ca ca cbcb. . 所以相等关系所以相等关系 是是A A上的同余关系。上的同余关系。 对于全域关系对于全域关系 ，即对，即对S S中的任何两元素中的任何两元素a,ba,b，都有，都有a a b, b, 当当然对任意然对任意c, c, 因为因为ac,bcac,bc属于属于S S，所以，所以ac ac bcbc, ,同理同理ca ca cbcb. . 所以全域关系所以全域关系是是A A上的同余关系。上的同余关系。 2022-6-27zhengjin,csu60同余关系示意图同余关系示意图定理：定理： 等价关系 关于二元运算*是一个同余关系当且仅当：a b且c d 时，有ac

46、bd 用图来表示此定理的合理性。图中每个小方格代表一个等价类 提醒：要掌握同余关系的内在含义提醒：要掌握同余关系的内在含义 a b cdac bd2022-6-27zhengjin,csu61由一个同态可以诱导出一个同余关系由一个同态可以诱导出一个同余关系o 从具有载体从具有载体S的代数的代数A到具有载体到具有载体S的代数的代数A的的任何一个同态任何一个同态h可诱导出一个可诱导出一个S上的自然等价关系上的自然等价关系.即即 a b 当且仅当当且仅当 h(a)=h(b) 下面的定理证明如果下面的定理证明如果h是一同态是一同态,那么诱导出的等那么诱导出的等价关系价关系 是是A上的同余关系上的同余关

47、系.2022-6-27zhengjin,csu62定理6.4-2 P178 设设h h是从代数是从代数 A= SA= 到到A=SA=的的同态同态, ,那么那么h h诱导出的诱导出的S S上的等价关系上的等价关系 是是代数代数A A上的同余关上的同余关系系. .证明要点证明要点: （1） 如果如果 a b,那么那么a a b b （2） 如果如果a b， c d, ac bd2022-6-27zhengjin,csu63本节小结本节小结掌握同余关系的定义掌握同余关系的定义掌握同余关系的特征掌握同余关系的特征会判断代数上的集合中元素的关系是否会判断代数上的集合中元素的关系是否是同余关系（看是否对每

48、个运算都满足置是同余关系（看是否对每个运算都满足置换性质）换性质）2022-6-27zhengjin,csu64本节作业本节作业P178: 课堂作业：，课堂作业：，课后作业课后作业；，2022-6-27zhengjin,csu656.5 6.5 商代数商代数( (不讲）不讲） 从已有代数可以构造出新的代数(如：商代数和积代数商代数和积代数）研究对象：Sk其中*是代表二元运算，是一元运算，k是常数。所得结论适于任意结构的代数。 2022-6-27zhengjin,csu66商代数的定义商代数的定义定义定义1 1 设设 是代数A= 上的同余关系，A的关于 的商代数，记为：A/ S/ k其中*和分别

49、定义如下：对所有 a,bS/, aa * *b=ab=a* *bb a=a=aa 这样，就由一个代数和其上的同余关系由一个代数和其上的同余关系 ，得到一个集合的划分，得到一个集合的划分（作为新代数的载体），再在划分上定义相关运算符就得到（作为新代数的载体），再在划分上定义相关运算符就得到一个新的代数：一个新的代数：商代数商代数。通常，代数的所有公理性质在商代数中仍能保持，代数A和商代数A/ 是同种类的代数。 2022-6-27zhengjin,csu67商代数的构造商代数的构造-例例例例.1.1 设h是从A=到A=的同态。 h: SkSm,h(x)=nx Sj=xxI且xj,j,k,m,nN并

50、满足nkm ，令 表示h诱导的A上的同余关系，求商代数A/ 2022-6-27zhengjin,csu68解： 当n=0时，由于nkm，且j,k,m,nN， 所以m=0 所以对Sk中任意元素x，h(x)=0, 所以由h诱导的等价关系 Sk Sk ，故S Sk k/ / =k=k 商代数A/ A/ =k= k+k=k 当n0时，x ynx=ny x=y 因此等价关系是Sk上的相等关系， Sk/ =xxI且xk 商代数 A/ A/ = x+y=x+y (提醒：必须掌握商代数的含义，才能构造出商代数)2022-6-27zhengjin,csu69商代数的特性商代数的特性商代数的运算和常数保留原代数的

51、性质：商代数的运算和常数保留原代数的性质：(1)如果运算*是可交换的,那么*也是可交换的. a*b=a*b=b*a=b*a(2)如果运算*是可结合的,那么 *也是可结合的.(3)若k 是*的么元（零元）,则k是*的么元(零元).等等.代数A和商代数A/是同种类的代数.2022-6-27zhengjin,csu70定理6.5-1 (P 180)如果是代数A=上的同余关系,那么规范映射h:SS/ 是从代数A到商代数 A/ 的同态， 称为与相关的自然同态此定理说明：由一个同余关系可诱导出一个同态由一个同余关系可诱导出一个同态2022-6-27zhengjin,csu71证明要点：设h是从S到S/ 的

52、规范映射。（即 h:SS/ , h(a)=a ）证明要点：根据同态的定义，要证明以下几点：(1) A和A/ 有相同的构成成份。(2) h(a*b)=h(a)*h(b) (3) h(a)= h(a) (4) 常数对应常数对应：即h(k)=k2022-6-27zhengjin,csu72例5.2: 设代数A=,(“+”表示普通加法,“-” 代表一元减法),上的同余关系定义如下： x y 当且仅当 x-y=nk 显然 是代数A上的同余关系, 商代数A/ = 其中 x+y=x+y -x=-x规范映射h:III/ / , ,h(xh(x)=x)=x是从代数A=到A/ = 的一个满同态.2022-6-27

53、zhengjin,csu73定理6.5-2 (P 181)设设f 是从是从A=到到A=的的同态同态,同态象为同态象为: 是是A上由上由f诱导的同余关系诱导的同余关系,那么那么,从商代数从商代数A/ =到到存在同构存在同构.这一定理说明商代数和同态象之间的关系这一定理说明商代数和同态象之间的关系.2022-6-27zhengjin,csu74证明要点：定义h如下: h:S/ f(S),h(xf(S),h(x)=)=f(xf(x) )证明证明h h是一同构是一同构. .证明要点证明要点: : (1) (1) 证明证明h h是良定的是良定的. .即如果即如果x=y,x=y,则则 h(xh(x)=)=

54、h(yh(y) (2) (2) 证明证明h h是双射函数是双射函数 (3) (3) 证明证明h h保持运算保持运算 即即h(xh(x * *”y)=”y)=h(xh(x)* *h(yh(y) 和和h(h(x)=h(x) (4) (4) 证明常数对应证明常数对应. . h(kh(k)=k)=k2022-6-27zhengjin,csu75定理结论定理结论o 由同态 f 诱导出一个A上的同余关系o 在关系下产生商代数A/ o 从S到S/ 的规范映射是代数A和其商代数A/ 之间的自然同态o A的商代数A/ 和A在f下的同态象之间是同构的.2022-6-27zhengjin,csu76 设h 是从A=

55、到A=的一个满同态, 是由h诱导的S上的等价关系. x y 当且仅当 h(x)=h(y)证明: A/ 同构于A提示:(应用定理6.5-2)课堂练习课堂练习:2022-6-27zhengjin,csu77本节小结本节小结o 掌握构造商代数的前提o 掌握商代数的构造方法 三个方面: 载体,运算符,常数o 一个代数A和其商代数之间的关系2022-6-27zhengjin,csu78本节作业o P 182: 1,2,32022-6-27zhengjin,csu796.6 6.6 半群，独异点和群半群，独异点和群 半群是最简单的代数结构，但已有丰富的理论，且在计算机和自动机理论中得到了应用。2022-6

56、-27zhengjin,csu80定义定义1 1 设是一非空集合，设是一非空集合，* *是上的二元运算，如果是上的二元运算，如果* *是可结合的，则称是可结合的，则称 为为半群半群。即对所有即对所有x x、y y、z z S S x x* *(y(y* *z)=(xz)=(x* *y)y)* *z z定义定义2 2 对于对于S,1,其中其中* *是二元运算是二元运算,1,1是么元是么元, ,并且满并且满足结合律的代数称为足结合律的代数称为独异点独异点, ,也称为含也称为含么半群么半群. (. (有时有时将么元记为将么元记为:e) :e) （即含么半群称为独异点即含么半群称为独异点） 将子代数的

57、概念运用于半群和独异点就得到子半群和将子代数的概念运用于半群和独异点就得到子半群和子独异点的概念。子独异点的概念。2022-6-27zhengjin,csu81定义定义3 3 如果是半群，T是S的子集且对运算*封闭，那么就称为的子半群。 显然：子半群也是半群(因对运算封闭，所以是子代数，且结合律继承)定义4 如果是独异点，T是S的子集且对运算*封闭，且eT，则是子独异点。 (显然，子独异点是独异点。因子独异点是子代数，对运算*封闭，含么元，结合律继承) 2022-6-27zhengjin,csu82例1 (1) 是半群 (Sk=xxI?xk(2)代数是独异点,(*表示普通乘法），也是独异点.(

58、3)代数和都是独异点。(4)有理数集Q中的*定义如下: a*b=a+b-ab 问题:是半群吗? 其中有单位元吗?2022-6-27zhengjin,csu83定义定义5 5 在半群(独异点)中，若运算是可交换的则称此半群为可交换半群(可交换独异点)定理 在任何可交换独异点中,S的等幂元素集合T可构成子独异点. 证明要点: (1) eT (2) 若a,b T,则a*b T , 即(a*b)*(a*b)=a*b 2022-6-27zhengjin,csu84独异点中元素的幂的定义独异点中元素的幂的定义独异点中元素独异点中元素a a的幂的定义：的幂的定义：(1) a(1) a0 0=e=e(2) a

59、(2) an+1n+1=a=an n* *a a显然：幂运算满足如下定律：显然：幂运算满足如下定律：(1)(1)a ai i* *a aj j= =a ai+ji+j (2) ( (2) (a ai i) )j j= =a aijij 2022-6-27zhengjin,csu85定义定义6 6 设 是独异点(或是半群)，如果存在一个元素gS,对于每个元素aS,都有一个相应的hN,a=gh 则称此独异点为循环独异点(循环半群)。称元素g是此循环独异点的生成元，或者说此循环独异点(循环半群)是由g生成的。 2022-6-27zhengjin,csu86o 定理 :循环独异点都是可交换的.2022

60、-6-27zhengjin,csu87 例例2 代数代数，由右表给定，由右表给定(1)请证明此代数是一个循环独异点,并求出生成元. (2)把这个独异点的每一元素都表示成生成元的幂. (3)列出这个独异点的所有等幂元素 *a b c d abcd a b c db c d ac d a bd a b c例 是循环独异点吗？请找出其生成元2022-6-27zhengjin,csu88o 例2 (P185-186)2022-6-27zhengjin,csu89半群半群(独异点独异点)同态同态 将同态的概念应用于特殊代数将同态的概念应用于特殊代数- -半群和独异点半群和独异点( (以以后还有群后还有群