离散数学 第六章 代数精.ppt

《离散数学 第六章 代数精.ppt》由会员分享，可在线阅读，更多相关《离散数学 第六章 代数精.ppt（175页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、离散数学离散数学 第六章第六章 代数代数第1页，本讲稿共175页2022/10/15第六章 代 数 6.1 6.1 代数结构代数结构6.2 6.2 子代数子代数6.3 6.3 同态同态6.4 6.4 同余关系同余关系6.5 6.5 商代数商代数6.6 6.6 半群和独异点半群和独异点6.7 6.7 群群6.8 6.8 环和域环和域第2页，本讲稿共175页 32022/10/156.16.1代数结构代数结构u代数系统代数系统一个非空集合A，连同若干个定义在该集合上的运算f1,f2,fn，所组成的系统称为一个代数系统，简称代数，记为。第3页，本讲稿共175页2022/10/156.16.1代数结构

2、代数结构u 代数系统的组成代数系统的组成n 载体（一个非空集合A）n 定义在载体上的运算(f1,f2,fn)n 代数常元第4页，本讲稿共175页2022/10/156.16.1代数结构代数结构u【例题【例题1】(a)正整数集合I+，以及定义在该集合上的普通加法运算“+”组成一个代数系统。(b)一个有限集合S，由S的幂集(S)，及定义在(S)上的交、并、补运算组成一个代数系统 。第5页，本讲稿共175页2022/10/156.16.1代数结构代数结构u代数运算代数运算 设A1,A2,An,A是非空集合，f是从A1A2An 到A的一个映射，则称f为从集合A1A2An到A的一个n元代数运算，简称运算

3、，n称为代数运算的阶。xnx3fx2x1y第6页，本讲稿共175页 72022/10/156.16.1代数结构代数结构u运算的封闭性运算的封闭性 设f是从A1A2An到A的一个n元运算，若A=A1=A2=An，则称该n元运算在集合A上是封闭的，亦称f是A上的n元运算。特别地，设f是从A到A的映射，则称f是一个在A上封闭的一元运算。设f是从A2到A的映射，则称f是一个在A上的封闭的二元运算。第7页，本讲稿共175页2022/10/156.16.1代数结构代数结构u【例题【例题2】一台自动售货机能接受五角和一元的硬币。当人们投入任意两枚上述硬币时，自动售货机将供应出相应的饮料，如下表5角1元5角雪

4、碧可乐1元可乐酷儿第8页，本讲稿共175页2022/10/156.16.1代数结构代数结构 设集合A5角，1元，集合B雪碧，可乐，酷儿，则上表其实是一个从AA到B的一个映射，也即一个从A2到B的一个二元运算。问运算在A上是否封闭？第9页，本讲稿共175页2022/10/156.16.1代数结构代数结构u【例题3】设有正整数集I+，“+”是I+上的普通加法运算。在I+上定义二元运算*为：任取x,yI+,x*y=x+y。令 S=2k|kI+=2,4,6,8,T=n|n I+,n能整除30=1,2,3,5,6,10,15,30问运算*在S和T上是否封闭?第10页，本讲稿共175页2022/10/15

5、6.16.1代数结构代数结构u运算表运算表 当集合A是有限集时，例如A=a1,a2,an，则A上一元代数运算和二元代数运算分别用如表(a)和(b)所示的运算表来表示。a1 a2 ana1a2an a1 a1 a1 a2 a1 an a2 a1 a2 a2 a2 an an a1 an a2 an an(ai)a1a2an(a1)(a2)(an)(a)(b)运算符运算符集合集合A A运算结果运算结果第11页，本讲稿共175页 122022/10/156.16.1代数结构代数结构u代数运算的性质一代数运算的性质一n交换律 设*是定义在集合A上的一个二元运算，如果任取x,yA，都有x*y=y*x，则

6、称该二元运算是可交换的。n【例题4】设Q是有理数集合，是Q上的二元运算，对任意a,bQ,ab=a+b-ab,其中+和是普通的加法、乘法运算，问是否是可交换的？第12页，本讲稿共175页2022/10/156.16.1代数结构代数结构u代数运算的性质二代数运算的性质二n结合律 设*是定义在集合A上的一个二元运算，如果对于任意x,y,zA，都有x*(y*z)=(x*y)*z,则称该二元运算是可结合的。n【例题5】设A是一个非空集合，*是A上的一个二元运算，对于任意a,b A,有a*b=b,证明运算*是可结合的。第13页，本讲稿共175页 142022/10/156.16.1代数结构代数结构u代数运

7、算的性质三代数运算的性质三n分配律 设*和 是定义在集合A上的二元运算，如果对任意的a,b,cA，都有 *对 左可分配 *对 右可分配则称*对 是可分配的。第14页，本讲稿共175页 152022/10/156.16.1代数结构代数结构u代数运算的性质三代数运算的性质三n【例题6】设集合A=,在A上定义两个二元运算*和，如下表(a)和(b)所示。运算对运算*可分配吗？运算*对运算呢？*(a)(b)第15页，本讲稿共175页 162022/10/156.16.1代数结构代数结构u代数运算的性质四代数运算的性质四n吸收律 设*和 是定义在集合A上的两个可交换的二元运算，如果对于任意的x,yA,都有

8、 则称运算*和 满足吸收律。第16页，本讲稿共175页 172022/10/156.16.1代数结构代数结构u代数运算的性质五代数运算的性质五n等幂律 设*是定义在集合A上的一个二元运算，如果对于任意xA,都有x*x=x,则称运算*满足等幂律。第17页，本讲稿共175页 182022/10/156.16.1代数结构代数结构n【例题7】设(S)是集合S上的幂集，在(S)上定义两个二元运算：集合的并运算和集合的交运算，验证和满足吸收律和等幂律。解答：和运算是可交换的。A,B(S),有 A(AB)=A A(AB)=A所以和满足吸收律。又有 A A=A A A=A所以和满足等幂律。第18页，本讲稿共1

9、75页2022/10/156.16.1代数结构代数结构u代数运算的性质六代数运算的性质六n消去律 设*是定义在集合上的一个二元运算，元素aA,如果对于任意x,y A,都有 a*x=a*y x=y a是左可消去的 x*a=y*a x=y a是右可消去的 则称a关于运算*是可消去的。若A中的所有元素都是可消去的，则称运算*满足消去律。第19页，本讲稿共175页 202022/10/156.16.1代数结构代数结构u代数常元代数常元n代数系统中，针对某一代数运算表现出具有某些特殊性质的元素称为代数常元，常见的有：幺元、零元、逆元、等幂元等。n幺元 左幺元：设*是定义在集合A上的一个二元运算，若存在元

10、素el，对于A中的每一个元素x，都有 el*x=x则称el为A中关于运算*的左幺元。第20页，本讲稿共175页 212022/10/156.16.1代数结构代数结构n幺元 右幺元：设*是定义在集合A上的一个二元运算，若存在元素er，对于A中每一个元素x,都有 x*er=x则称er为A中关于运算*的右幺元。第21页，本讲稿共175页 222022/10/156.16.1代数结构代数结构n幺元 幺元：设*是定义在集合A上一个二元运算，若A中有一个运算e,它既是左幺元，又是右幺元，则称e为A中关于运算*的幺元，亦称作单位元。e*x=x*e=x第22页，本讲稿共175页 232022/10/156.1

11、6.1代数结构代数结构n【例题8】设集合S=a,b,c,d,S上定义的两个二元运算*和的运算表如下表所示，试求出其中的左幺元和右幺元。*a b c dabcdd a b ca b c da b c ca b c da b c d abcda b d cb a c dc d a bd d b c(a)(b)第23页，本讲稿共175页 242022/10/156.16.1代数结构代数结构u定理设*是定义在集合A上的一个二元运算，且在A中有关于运算*的左幺元el和右幺元er,则el=er=e,且A中的幺元是唯一的。证明：证明：设el 和er分别是A中关于运算*的左幺元和右幺元，则有 el=el*er

12、=er=e 假设另有幺元eA,则有e=e*e=e,结论得证。第24页，本讲稿共175页 252022/10/156.16.1代数结构代数结构u代数常元代数常元n零元 左零元：设*是定义在集合A上的一个二元运算，如果有一个元素lA,对于任意的元素xA都有l*x=l，则称l为A中关于运算*的左零元。右零元：如果有一个元素rA,对于任意的元素xA都有x*r=r，则称r为A中关于运算*的右零元。第25页，本讲稿共175页 262022/10/156.16.1代数结构代数结构n零元 零元：如果A中的一个元素，它既是左零元，又是右零元，则称为A中关于运算*的零元。*x=x*=第26页，本讲稿共175页 2

13、72022/10/156.16.1代数结构代数结构u【例题【例题9】设“浅”表示不易褪色的浅色衣服，“深”表示易褪色的深色衣服，集合S=浅，深，定义S的一个二元运算“混洗”，记为“”，则 的运算表如下表所示。求S中关于 运算的幺元和零元。浅 深浅深 浅 深 深 深第27页，本讲稿共175页 282022/10/156.16.1代数结构代数结构u定理设*是定义在集合A上一个二元运算，且在A中有关于运算*的左零元l和右零元r,那么l=r=，且A中的零元是唯一的。第28页，本讲稿共175页 292022/10/156.16.1代数结构代数结构n逆元 逆元：设是一个代数系统，*是定义在集合A上的一个二

14、元运算，e是A中关于运算*的幺元。x,yA,如果x*y=e,那么关于运算*,x是y的左逆元，y是x的右逆元。如果x*y=y*x=e,那么关于运算*,x与y互为逆元。运算x的逆元记为x-1。第29页，本讲稿共175页 302022/10/156.16.1代数结构代数结构u定理设是一个代数系统，*是定义在集合A上的一个二元运算，e是A中关于运算*的幺元。若运算*是可结合的，且元素x有左逆元l和右逆元r，则l=r。证明：因为e是A中关于运算*的幺元且x有左逆元l和右逆元r,则有 l*x=x*r=e又运算是可结合的，所以 l=l*e=l*(x*r)=(l*x)*r=e*r=r第30页，本讲稿共175页

15、 312022/10/156.16.1本节小结本节小结u代数系统组成代数系统组成：载体、定义在载体上的运算、载体、定义在载体上的运算、代数常元。代数常元。u设设为代数系统，为代数系统，*是定义在是定义在A上的二上的二元运算，则运算元运算，则运算*的某些性质以及代数常元的某些性质以及代数常元可以直接从运算表中得到可以直接从运算表中得到：n运算*是封闭的，当且仅当运算表中的每个元素都属于A；n运算*满足交换律，当且仅当运算表关于主对角线对称；第31页，本讲稿共175页 322022/10/156.16.1本节小结本节小结n运算满足等幂律，当且仅当运算表中主对角线上的每一元素与它所对应的行(列)表头

16、元素相同;n运算满足消去律，当且仅当运算表中任意行、任意列没有相同的两个元素；n若A中有关于运算*的零元，则该元素所在的行和列中的所有元素都等于该元素；n若A中有关于运算*的幺元，则该元素所在的行(列)中的所有元素都依次与列(行)表头元素相同;第32页，本讲稿共175页 332022/10/156.16.1本节小结本节小结n设A 中有关于运算*的幺元e，元素a与b互逆，当且仅当运算表中a行、b列对应的元素与a列、b行对应的元素都是e。u代数常元代数常元：幺元、零元。幺元、零元。第33页，本讲稿共175页 342022/10/156.16.1习题习题u习题一习题一 设为代数系统，其中A=1,2,

17、3,4,“*”定义如下表所示：(a)运算*是可交换的吗？为什么？(b)运算*是可结合的吗？为什么？(c)求A中关于运算*的幺元，并给出每个元素的逆元。(d)A中有关于运算*的零元吗？*1 2 3 412341 2 3 42 3 4 13 4 1 24 1 2 3 第34页，本讲稿共175页 352022/10/156.16.1习题习题u习题二习题二设I是整数集合，函数g:III，定义为：g(x,y)=x*y=xyxy，其中+和 是普通的加法和乘法运算。(a)试证明二元运算*是可交换的和可结合的。(b)求运算*的幺元，并指出每个元素的逆元。第35页，本讲稿共175页 362022/10/156.

18、26.2子代数子代数u子代数定义子代数定义 设是一个代数系统，*和分别是载体A上的二元运算和一元运算，k是代数常元，如果满足 (1)A A,(2)*和运算在A上封闭，(3)kA,那么称是的子代数。第36页，本讲稿共175页 372022/10/156.26.2子代数子代数u平凡子代数定义平凡子代数定义 设是一代数系统，T是由A中的代数常元构成的集合，且运算*和在T上封闭。称和是的平凡子代数，非平凡子代数亦称为真子代数。第37页，本讲稿共175页 382022/10/156.26.2习题习题u习题一习题一 I是整数集合，Ie和Io分别是偶数集合和奇数集合，+是I上的普通加法运算，则是一代数系统。

19、和是的子代数吗？解答：是的子代数。而不是的子代数，因为Io在+上不封闭。第38页，本讲稿共175页 392022/10/156.26.2习题习题u习题二习题二 I是整数集合，I+是正整数集合，+是I上的普通加法运算，则是一代数系统。是的子代数吗？解答：不是的子代数，因为 0 I+。第39页，本讲稿共175页 402022/10/156.36.3同态同态u同态的定义同态的定义 设A=和A=是两个具有相同构成的代数系统，f是从S到S的一个映射，且对任意a,bS满足：f(a*b)=f(a)*f(b)f(a)=f(a)f(k)=k 则称f为由A到A的一个同态映射，简称同态。A同态于A,记作AA。第40

20、页，本讲稿共175页 412022/10/156.36.3同态同态u同态象同态象 设f是从A=到A=的一个同态映射，称为A在映射f下的同态象。其中 下图反映了两个代数系统间的同态关系。第41页，本讲稿共175页 422022/10/156.36.3同态同态kSSfkaf(a)bf(b)cf(c)a*bf(a)*f(b)(c)f(c)*同态象同态象第42页，本讲稿共175页 432022/10/156.36.3同态同态u【例题【例题1】设代数系统,I是整数集,是普通乘法运算。如果我们只对运算结果是正数、负数还是零关心,那么代数系统中的运算结果的特征就可以用另一个代数系统的运算结果来表示,其中B+

21、,-,0,是B上的二元运算，运算表如下所示，构造从到的同态映射。第43页，本讲稿共175页 442022/10/156.36.3同态同态解答：解答：构造函数f:IB,f(x)显然，任取a,bI,f(ab)=f(a)f(b)。所以，f是由到的一个同态。+-0+-0+-0-+0 0 0 0+x0-x00 x=0第44页，本讲稿共175页 452022/10/156.36.3同态同态u同态的分类同态的分类 设f是由A=S,*,k到A=S,*,k的一个同态。n 满同态:若f是满射的，则称f为由A到A的一个满同态。A就是A在满同态f下一个同态象。n单一同态：若f是单射的，则称f为由A到A的一个单一同态。

22、显然，A在单一同态f下的同态象与A同构。第45页，本讲稿共175页 462022/10/156.36.3同态同态u同态的分类同态的分类n同构：若f是双射的，则称f为由A到A的一个同构映射，简称同构。A同构于A，记作A A。n自同态：若A=A，则称f为A上的自同态。n自同构：若A=A且f是双射的，则称f为A上的自同构。第46页，本讲稿共175页 472022/10/156.36.3同态同态u【例题【例题2】N是自然数集合，+是N上的普通加法运算，设Nk=0,1,2,k-1,+k是定义在N上的模k加法运算。设函数f:NNk定义为 f(x)=x(mod k)证明：f是从到Nk,+k,0)的一个满同态

23、 映射。第47页，本讲稿共175页 482022/10/156.36.3同态同态证明：证明：(a)显然，f是从N到Nk的满射。(b)任取x,yN,有 f(x+y)=(x+y)(mod k)=(x(mod k)+y(mod k)(mod k)=(x(mod k)+k(y(mod k)=f(x)+kf(y)(c)f(0)=0。所以，f是从到的一个满同态。第48页，本讲稿共175页 492022/10/156.36.3同态同态u【例题【例题3】设A=a,b,c,d,在A上定义一个二元运算如表a所示，又设B=0,1,2,3,在B上定义一个二元运算*如表b所示。构造从代数系统到的一个同构映射。a b c

24、 dabcda a a aa b c da c a ca d c b*0 1 2 301232 0 2 00 1 2 32 2 2 20 3 2 1(a)(b)第49页，本讲稿共175页 502022/10/156.36.3同态同态解答：解答：设函数h:AB,h(a)=2,h(b)=1,h(c)=0,h(d)=3。容易验证：(a)h是双射的；(b)任取x,yA,h(xy)=h(x)*h(y);(c)中的幺元b,h(b)=1也是中的幺元；中的零元a,h(a)=2也是的零元。所以h是从代数系统到的一个同构映射。第50页，本讲稿共175页 512022/10/156.36.3同态的性质同态的性质u定

25、理定理设设f是从是从A=到到A=的一个同态映射，那么的一个同态映射，那么A的同态象的同态象是是A的子代数。的子代数。证明：(i)因为f是从S到S的一个映射,所以f(S)S。(ii)因为kS,f(k)=k,所以kf(S).(iii)任取a,bf(S)，存在x,yS,使得f(x)=a,f(y)=b。因为x*y=zS,所以 a*b=f(x)*f(y)=f(x*y)=f(z)f(S)故f(S)在运算*下是封闭的。第51页，本讲稿共175页 522022/10/156.36.3同态的性质同态的性质(iv)任取af(S),存在xS使得f(x)=a。因为xS,所以a=f(x)=f(x)f(S),故f(S)在

26、运算下是封闭的。由(i)(ii)(iii)(iv)可知，是A的子代数。fA=同态象A=第52页，本讲稿共175页 532022/10/156.36.3同态的性质同态的性质u定理定理设设f是从是从A=到到A=的一个同态映射，的一个同态映射，A=是是A在同在同态映射态映射f下的同态象，则有下的同态象，则有(1)若*在A中可交换,则*在A中也是可交换的;(2)若*在A中可结合,则*在A中也是可结合的;(3)若在A中*对可分配,则在A中*对也可分配;第53页，本讲稿共175页 542022/10/156.36.3同态的性质同态的性质(4)若e是A中关于运算*的幺元，则f(e)是A中关于运算*的幺元；(

27、5)若是A中关于运算*的零元，则f()是A中关于运算*的零元；(6)任取xS,x对运算*有逆元x-1,在f(S)中，f(x)也有关于运算*的逆元f(x-1)。第54页，本讲稿共175页 552022/10/156.36.3小结小结u子代数概念：子代数概念：一个代数系统载体一个代数系统载体A的一个子集的一个子集A，如果在该代数系统的所有运算下都封闭，则称以如果在该代数系统的所有运算下都封闭，则称以A为载体为载体的代数系统是原代数系统的子代数。的代数系统是原代数系统的子代数。u同态概念：同态概念：同态映射不仅建立了两个代数系统载体同态映射不仅建立了两个代数系统载体间的映射关系，更重要的是同时还建立

28、了两个代数系间的映射关系，更重要的是同时还建立了两个代数系统对应运算间的映射关系。统对应运算间的映射关系。第55页，本讲稿共175页 562022/10/156.36.3小结小结u同态象概念：同态象概念：一个代数系统与其同态象之间有许一个代数系统与其同态象之间有许多相似的地方。多相似的地方。u同态的分类：同态的分类：根据同态映射的性质可以将同态分为：根据同态映射的性质可以将同态分为：满同态、单一同态和同构。满同态、单一同态和同构。u同态性质：同态性质：在同态映射下，同态象的运算能够保持原在同态映射下，同态象的运算能够保持原代数系统中对应运算的交换性、结合性和分配性，并且幺代数系统中对应运算的交

29、换性、结合性和分配性，并且幺元、零元和逆元也满足映射对应关系。元、零元和逆元也满足映射对应关系。第56页，本讲稿共175页 572022/10/156.36.3本节习题本节习题u习题一习题一 设h是从A=到A=的同态，证明如果是A的子代数，那么是A的子代数。h-1(T)Thh-1hA=A=第57页，本讲稿共175页 582022/10/156.36.3本节习题本节习题证明：(i)因为是的子代数，所以T S。故有h-1(T)h-1(S)S。(ii)任取x,yh-1(T),存在x,yT使得h(x)=x,h(y)=y因为x,yS且h是从A到A的同态，所以有 h(x*y)=h(x)*h(y)=x*y

30、T 故x*yh-1(T),即h-1(T)对*运算是封闭的。(iii)因为h(k)=k T,所以k h-1(T)。由(i)(ii)(iii)可知，是的子代数。第58页，本讲稿共175页 592022/10/156.46.4同余关系同余关系u同余的定义同余的定义n运算上的同余关系：设A=是一个代数系统，是载体S上的等价关系，任取a,b,cS。(1)当ab时，若ab,则等价关系在一元运算下是可保持的，称是关于运算同余关系。(2)当ab和cd时，若有a*cb*d，则等价关系在二元运算*下是可保持的，称是关于运算*同余关系。第59页，本讲稿共175页 602022/10/156.46.4同余关系同余关系

31、ababcdcda=ac=caba*cb*dcda*c=a*c第60页，本讲稿共175页 612022/10/156.46.4同余关系同余关系u【例题【例题1】设+是整数集合I上的普通加法运算，是I上的模k(kI+)相等关系，问在运算+上是否是I上的同余关系？分析：任意a,b和c,d有：ab(mod k)其实就是a-b=n*k cd(mod k)其实就是c-d=m*k那么(a+c)-(b+d)=(m+n)*k，即(a+c)(b+d)(mod k)第61页，本讲稿共175页 622022/10/156.46.4同余关系同余关系u【例题【例题2】设是集合I上的一元运算，任取aI,a=a2,是I上的

32、模k(kI)相等关系，问在运算是否是I上的同余关系？是否是代数系统A上A的同余关系？分析：ab(mod k)就相当于(a-b)=n*k a-b=(a+b)(a-b)=(a+b)*n*k，即a b整数m第62页，本讲稿共175页 632022/10/156.46.4同余关系同余关系u代数系统上的同余关系：代数系统上的同余关系：设A=是一个代数系统，是载体S上的等价关系，若在A上的所有运算下都是可保持的，则称为代数系统A上的同余关系。第63页，本讲稿共175页 642022/10/156.46.4同余关系同余关系u定理定理 设g是从代数系统A=到A=的一个同态映射，那么由g诱导的S上的等价关系是代

33、数系统A上同余关系。证明：由函数g诱导的S上的等价关系为：任取a,bS,ab当且仅当g(a)=g(b)。(i)若ab,则g(a)=g(b),g(a)=g(b)。第64页，本讲稿共175页 652022/10/156.46.4同余关系同余关系又g是从A到A的同态映射，所以有 g(a)=g(a)=g(b)=g(b)故a b，这说明在运算下是可保持的。(ii)若ab且cd,且有g(a)=g(b),g(c)=g(d),所以g(a)*g(c)=g(b)*g(d),又因g是从A到A的同态映射，所以有g(a)*g(c)=g(a*c)=g(b)*g(d)=g(b*d)故a*cb*d,这说明等价关系在运算*下是

34、可保持的。由(i)(ii)可得，是代数系统A上的同余关系。第65页，本讲稿共175页 662022/10/156.46.4同余关系同余关系u运算上的同余关系：运算上的同余关系：等价关系在运算下的可保持性是等价关系在运算下的可保持性是指参与运算的对应元素，如果在同一个等价类中，则运算后指参与运算的对应元素，如果在同一个等价类中，则运算后所得的结果也必在同一个等价类中。所得的结果也必在同一个等价类中。u代数系统上的同余关系：代数系统上的同余关系：等价关系等价关系R如果在一个代如果在一个代数系统中的所有运算下都是可保持的，则数系统中的所有运算下都是可保持的，则R是是A上的同余上的同余关系。同余关系使

35、得元素所在的等价类在运算上可以作为关系。同余关系使得元素所在的等价类在运算上可以作为一个整体来看待。一个整体来看待。第66页，本讲稿共175页 672022/10/156.56.5商代数商代数u商代数定义商代数定义:设设A=是一个代数系是一个代数系统，统，是是A上的同余关系，上的同余关系，A关于关于的商代数的商代数A/=。其中。其中 a=a a*b=a*b注意：注意：S/是集合的集合，即等价类的集合，是集合的集合，即等价类的集合，形如：形如：a,b,*,是集合之间的运算是集合之间的运算 k是代数常元的集合是代数常元的集合 第67页，本讲稿共175页 682022/10/156.56.5商代数商

36、代数u【例题】【例题】代数系统A=，其中S=a1,a2,a3,a4,a5,一元运算和由下表所示的运算表定义。又S上的等价关系R产生的S上的划分 =a1,a3,a2,a5,a4 (a)证明：R是A上的同余关系。(b)给出A/R。a1 a2 a3 a4 a5 a4 a3 a4 a2 a1a3 a2 a1 a3 a5第68页，本讲稿共175页 692022/10/156.56.5小结小结u商代数：商代数：由等价关系由等价关系R可以得到代数系统可以得到代数系统A的载体的一的载体的一个划分，以这个划分为新的载体，按照原运算的规则个划分，以这个划分为新的载体，按照原运算的规则建立等价类之间新的运算，这样得

37、到的代数系统是原建立等价类之间新的运算，这样得到的代数系统是原代数系统的商代数。代数系统的商代数。第69页，本讲稿共175页 702022/10/156.66.6半群和独异点半群和独异点u半群：半群：一个代数系统一个代数系统，其中，其中S是非空集是非空集合，合，*是是S上一个二元运算，如果满足：上一个二元运算，如果满足：n运算*是封闭的；n运算*是可结合的，即任取x,y,zS,有 (x*y)*z=x*(y*z)则称为半群。第70页，本讲稿共175页 712022/10/156.66.6半群与独异点半群与独异点u【例题【例题1】设集合Sk=x|xI,xk,其中I是整数集合，kI,且k 1,+是普

38、通加法运算。证明是一个半群。证明：因为+运算在Sk上封闭的和可结合的，所以是半群。考虑：如果k 0呢？如果k -1呢？第71页，本讲稿共175页 722022/10/156.66.6半群与独异点半群与独异点u【例题【例题2】设I+是正整数集合，R是实数集合，R+和R-分别表示正实数和负实数集合。问、和都是半群吗？为什么？解答：满足半群的定义，它是半群。、的运算不封闭，因此均不是半群。第72页，本讲稿共175页 732022/10/156.66.6半群与独异点半群与独异点u定理定理设设是一个半群，是一个半群，T S且且*在在T上是封闭的，那么上是封闭的，那么是是的子代数，的子代数，也是一个半群，

39、称为也是一个半群，称为的子半群。的子半群。u独异点：独异点：含有含有幺元幺元的的半群半群。由于结合律在子代数上是可继承的，因此半群的子代数也是半群。第73页，本讲稿共175页 742022/10/156.66.6半群与独异点半群与独异点u【例题【例题3】判断以下代数系统是否是独异点。(a);(b)。解答：(a)是半群，但不是独异点，因为不含有幺元0。(b)是半群，因为含有幺元0，所以它也是独异点。第74页，本讲稿共175页 752022/10/156.66.6半群与独异点半群与独异点u【例题【例题4】设A=0,1,2,3,+4和4分别是模4加法和模4乘法，其运算表分别如下页(a)、(b)所示，

40、即任意a,bA有 a+4 b=(a+b)(mod 4)a4 b=(ab)(mod 4)(a)和是独异点吗?为什么?(b)A中的元素在运算+4 和4上有逆元吗?第75页，本讲稿共175页 762022/10/156.66.6半群与独异点半群与独异点+40 1 2 3 01230 1 2 31 2 3 02 3 0 13 0 1 240 1 2 3 01230 0 0 00 1 2 30 2 0 20 3 2 1(a)(b)第76页，本讲稿共175页 772022/10/156.66.6半群与独异点半群与独异点u子独异点子独异点：设：设是一个独异点，是一个独异点，T S且且*在在T上是封闭的，那么

41、上是封闭的，那么是是的子代数的子代数,也是一个独异点，称为也是一个独异点，称为的子独异点。的子独异点。n原代数系统的子代数n本身是独异点n在相同运算下，幺元相同第77页，本讲稿共175页 782022/10/156.66.6半群与独异点半群与独异点u【例题【例题5】设N10=0,1,2,3,9,10是模10乘法运算，则是一个独异点，(a)写出10的运算表；(b)取N10的一个子集A=0,2,4,6,8,证明是一个独异点，但不是的子独异点；(c)构造的一个含有5个元素的子独异点。第78页，本讲稿共175页 792022/10/156.66.6半群与独异点半群与独异点u交换半群（独异点）交换半群（

42、独异点）：在半群（独异点）中，：在半群（独异点）中，若二元运算是可交换的，则称该半群（独异若二元运算是可交换的，则称该半群（独异点）为交换半群（独异点）。点）为交换半群（独异点）。注：概念只作了解。注：概念只作了解。第79页，本讲稿共175页 802022/10/156.66.6半群和独异点的性质半群和独异点的性质u定理定理设设是一个半群，如果是一个半群，如果S是一个是一个有限集，则必存在有限集，则必存在aS,使得使得a*a=a。证明：设|S|=n,因为是半群，任取bS,由运算*的封闭性以及S为有限集知 b,b*b=b2,b*b*b=b3,bn,bn+1S根据抽屉原理，必有两个元素相等,不妨设

43、为bi=bj(其中ji)。n+1第80页，本讲稿共175页 812022/10/156.66.6半群与独异点的性质半群与独异点的性质令p=j-i,显然有p1。由此可得bi=bj=bp+i=bp*bi。bi=bp*bi bi+1=bp*bi+1 bkp=bp*bkp又由bkp=bp*bkp知 bkp=b(k+1)p b(k+1)p=b(k+2)p .b(2k-1)p=b2kp因此有 bkp b2kp bkp*bkp令a=bkp，则有a=a*a，证毕。第81页，本讲稿共175页 822022/10/156.66.6半群与独异点半群与独异点u【思考题】【思考题】设是一个独异点，*的运算表中可能出现两

44、行或两列完全相同吗？解答：不可能。设S中关于运算*的幺元是e。任取a,bS,若ab,则有 e*a e*b (任何两列不同)a*e b*e (任何两行不同)所以运算*的运算表中任何两行和两列都是不同的。第82页，本讲稿共175页 832022/10/156.66.6半群与独异点半群与独异点u循环独异点：循环独异点：设设是一个独异点，若是一个独异点，若存在一个元素存在一个元素gS,对于对于S中的每一个元素中的每一个元素a,都有一个对应的都有一个对应的kN使得使得a=gk，则称此独，则称此独异点为循环独异点。异点为循环独异点。g称为此循环独异点的称为此循环独异点的生成元。生成元。第83页，本讲稿共1

45、75页 842022/10/156.66.6半群与独异点半群与独异点u【例题【例题6】判断以下代数系统是否是循环独异点，若是，指出生成元。(a);(b),*的运算表如下表所示。*a b c dabcda b c db a d cc d b ad c a b第84页，本讲稿共175页 852022/10/156.66.6本节小结本节小结u半群半群n半群定义：封闭、可结合n子半群：子集、封闭，子代数，子半群n半群性质：有限半群中必有等幂元n交换半群：可交换第85页，本讲稿共175页 862022/10/156.66.6本节小结本节小结u独异点独异点n独异点定义：含幺元半群n子独异点：子集、封闭、含

46、有幺元e，子代数n交换独异点：可交换n循环独异点：有一个生成元g,每个元素都可以用gk表示第86页，本讲稿共175页 872022/10/156.76.7群群u群群：设：设是一个代数系统，其中是一个代数系统，其中G是非是非空集合，空集合，*是是G上一个二元运算。如果满足上一个二元运算。如果满足n运算*是封闭的，n运算*是可结合的，n存在幺元e，n对于每一个元素xG,都存在逆元x-1G，则称则称是一个群。是一个群。半群独异点群半群半群独异点独异点群群第87页，本讲稿共175页 882022/10/156.76.7群群u【例题【例题1】判断以下代数系统是否是群？】判断以下代数系统是否是群？(a),

47、I是整数集合，+是普通加法运算。(b),Q是有理数集合，是普通乘法运算。(c)，I是整数集合，是普通乘法运算。(d),运算*如下表所示。*a b cabc a b c b c a c a b第88页，本讲稿共175页 892022/10/156.76.7群群u【例题【例题2】设有代数系统，其中I是整数集合，运算的定义为，对任意a,bI,有 a b=a+b-2试问是否是群？解答：(i)对任意a,b I,a b I,所以运算在I上是封闭的。第89页，本讲稿共175页 902022/10/156.76.7群群(ii)对任意的a,b,c I,有 (a b)c=(a+b-2)c=(a+b-2)+c-2=

48、a+b+c-4 a(b c)=a+(b c)-2=a+(b+c-2)-2=a+b+c-4所以运算满足结合律。(iii)任取aI,ae=a+e-2=a,得到e=2,所以2是幺元。(iv)任取aI,aa-1=a+a-1-2=2,得到a-1=4-aI,因此I中每个元素都有逆元。由以上可知是一个群。第90页，本讲稿共175页 912022/10/156.76.7群群u有限群：有限群：设设是一个群，如果是一个群，如果G是有限是有限集，则称集，则称为有限群。为有限群。u无限群：无限群：设设是一个群，如果是一个群，如果G是无限是无限集，则称集，则称为无限群。为无限群。u群的阶数：群的阶数：有限群有限群的载体

49、的载体G的基数的基数|G|，称为群的阶。，称为群的阶。第91页，本讲稿共175页 922022/10/156.76.7群的性质群的性质u性质一：性质一：群中无零元。群中无零元。说明：当群中只有一个元素的时候，一般的把它看作幺元，如果它是零元的话，它就不符合群的定义了。因为零元没有逆元，零元与任何元素进行操作结果都是零元。如果群中有零元，则不符合群的定义了(任何一个元素都有逆元)。第92页，本讲稿共175页 932022/10/156.76.7群的性质群的性质u性质二：性质二：群中每个元素的逆元都是唯一的。群中每个元素的逆元都是唯一的。说明：前面我们学过一个定理6.1-3，对于可结合运算，如果一

50、个元素x有左逆元l和右逆元r,那么l=r（即逆元是唯一的）。假设群中的元素a有两个逆元c,d，c=c*e=c*(a*d)=(c*a)*d=e*d=d第93页，本讲稿共175页 942022/10/156.76.7群的性质群的性质u性质三：性质三：设设是一个群，对于是一个群，对于a,bG,必必存在唯一的存在唯一的xG,使得使得a*x=b。证明：设a的逆元是a-1,令 x=a-1*b 则 a*x=a*(a-1*b)=(a*a-1)*b =e*b=b 第94页，本讲稿共175页 952022/10/156.76.7群的性质群的性质若另一解x1,满足a*x1=b，则 a-1*(a*x1)=a-1*b