《代数系统基础精选PPT.ppt》由会员分享，可在线阅读，更多相关《代数系统基础精选PPT.ppt（173页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、代数系统基础第1页，此课件共173页哦近世代数l这部分内容属于近世代数的范畴，近世代数是研究具有运算的集合，它第一次揭示了数学系统的多变性与丰富性。l代数结构理论可用于计算机算法的复杂性分析，研究抽象数据结构的性质及操作，同时也是程序设计语言的理论基础。第2页，此课件共173页哦本篇内容l我们将介绍代数系统的最基本概念和最基本理论，以及几类常用的代数系统，它们是：半群，群，环，域，格和布尔代数。l本课程在第五、六、七章中介绍代数系统的内容。第3页，此课件共173页哦第五章 代数系统基础l代数系统是用代数运算构造数学模型的方法。这是一种抽象的方法，故又称抽象代数，又由于此种方法是在集合上通过构造
2、手段生成，也可称为代数系统。第4页，此课件共173页哦5.1代数系统的一般概念l一个代数系统需要满足三个条件：（1）一个非空集合S；（2）一些建立在集合S上的运算；（3）这些运算在S上是封闭的；第5页，此课件共173页哦封闭的含义l其运算的结果都是在原来的集合中，我们称具有这种特征的运算是封闭的。如：数集上加法、绝对值、相反数运算；幂集上交、并运算等。l不封闭运算的例子也有很多，如设N是自然数集，Z是整数集，普通的减法定义为NN到Z的运算，是不封闭的。第6页，此课件共173页哦运算符l通常用等，等表示二元运算，称为运算符。l若f：sss是集合S上的二元运算，对任意x,y,如果x与y运算的结果是
3、z,即f(x，y)=z,可利用运算简记为xy=z。l类似于二元运算，也可以使用运算符来表示n元运算。如 f（a1，a2，an）=b 可简记为 （a1，a2，an）=b 第7页，此课件共173页哦 n=1时（a1）=b是一元运算；n=2时（a1，a2）=b是二元运算；n=3时（a1，a2，a3）=b是三元运算；这些相当于前缀表示法，但对于二元运算用得较多的还是a1 a2=b，以下所涉及的n元运算主要是一元运算和二元运算。第8页，此课件共173页哦代数系统的例子l（1）求一个数的倒数是非零实数集R*上的一元运算。l（2）非零实数集R*上的乘法和除法都是R*上的二元运算，而加法和减法不是。l（3）S
4、是一非空集合，SS是S到S上的所有函数的集合，则复合运算是SS上的二元运算。l（4）空间直角坐标系中求点（x，y，z）的坐标在 x 轴上的投影，可以看作实数集R上的三元运算：f(x，y，z)=x，因为参加运算的是有序的3个实数，而结果也是实数。第9页，此课件共173页哦运算规律l考察代数系统Z，+。很明显，在这个代数系统中，关于加法运算，具有以下二个运算规律，即对于任意的x，有 (1)x+y=y+x (交换律)(2)(x+y)+z=x+(y+z)（结合律）l又如，设S是集合，P（S）是S的幂集，则代数系统P（S），U和P（S），中的、都适合交换律，结合律，即他们与Z，+有类似的运算性质。这些就
5、是代数系统研究的一部分内容。第10页，此课件共173页哦同类型的代数系统l定义：如果两个代数系统有相同个数的运算符，每个对应的运算符有相同的元数，则称这两个代数系统有相同的类型。l例：整数集上加法与实数集上乘法；N阶矩阵集上加法、乘法运算。第11页，此课件共173页哦子代数l定义：两个代数系统（S，），（S，+），若满足下列条件：（1）S是S的子集 （2）则称（S，+）是（S，）的子代数或子系统。例：偶数集上加法是整数集上加法的子代数。第12页，此课件共173页哦5.2代数系统常见的性质l对给定的集合，我们可以任意地在这个集合上规定运算使它成为代数系统。但我们所研究的是其运算有某些性质的代数系
6、统。l在前面考察几个具体的代数系统时，已经涉及到我们所熟悉的运算的某些性质。这一节，主要讨论一般二元运算的一些性质。第13页，此课件共173页哦代数系统（S，*）上性质l1.结合律l2.交换律l例：常用的代数系统：数集上加法、乘法，幂集上交、并运算。第14页，此课件共173页哦l3.分配律l以上是第一分配律、第二分配律。l例：数集上乘法对加法满足分配律，但加法对乘法不满足。幂集上交对并、并对交满足分配律。第15页，此课件共173页哦单位元l定义：若存在一个元素eS,对任一x S，均有x*e=x，则称e为右单位元，记1r；l若e*x=x，则称e为左单位元,记1l。l常用1来表示单位元。l注：1只
7、是一个符号，用来表示S中单位元素。第16页，此课件共173页哦单位元定理l定理1：若左单位元、右单位元都存在，则两者相等。l定理2：若单位元存在，则必唯一。第17页，此课件共173页哦证明l定理1：若1r、1l存在，1l*1r=1r=1l。l定理2：设有两个单位元e1、e2，任一xS，e1*x=x，取x=e2，有e1*e2=e2，又e2也是单位元，e1*e2=e1。因此e1=e2，单位元是唯一的。第18页，此课件共173页哦零元素l定义：若存在一个元素aS,对任一xS，均有x*a=a，则称a为右零元，记0r；若a*x=a，则称a为左零元,记0l。l常用0来表示零元素。注：0只是一个符号，表示S
8、中零元素。l定理：若左零元、右零元都存在，则两者相等。l定理：若零元存在，则必唯一。第19页，此课件共173页哦例子l数集上加法，单位元1=0；数集上乘法，单位元1=1。l集合A的幂集上交运算。单位元1是A，零元0是空集；并运算的单位元是空集，零元是A。l正整数集I上的运算min,max。其中min为取最小值运算，max是取最大值运算。(I,min)上零元是1，单位元不存在；(I,max)上零元不存在，单位元是1；第20页，此课件共173页哦逆元素：设（S，*）上单位元存在l定义：若对S内元素a，存在a-1rS,有 a*a-1r=1，则称a-1r为a的右逆元素；l 若存在a-1lS,有a-1l
9、*a=1，则称a-1l为a的左逆元素。第21页，此课件共173页哦定理l定理1：一个代数系统（S，*）,如果其运算满足结合律，则左、右逆元相等。l定理2：一个代数系统（S，*）,如果运算满足结合律且逆元存在，则S内每一个元素的逆元是唯一的。第22页，此课件共173页哦例子l整数集上加法。单位元是0，a的逆元是-a；整数集上乘法，单位元是1，只有1、-1有逆元；实数集上乘法，0没有逆元。l自然数集上加法。单位元是0，0的逆元是0，其他元素没有逆元。l在非零的实数集R*上定义运算，使对于任意的元素a,bR*，有ab=a。那么，R*的任何元素都是运算的左零元，而R*中运算没有右零元，因此没有零元。第
10、23页，此课件共173页哦练习题l题1 设Z是整数集，分别是Z上的二元运算，其定义为，对任意的a，aabab，aabab，问上的运算，分别是否可交换？第24页，此课件共173页哦解l 因为ababa=baa a，对Z中任意元素a，b成立，所以运算是可以交换的。又因为对Z中的数0，1，01=010+1=1，10=101+0=1，所以，0110，从而运算是不可交换的第25页，此课件共173页哦练习题2l设是有理数集合，分别是上的二元运算，其定义为，对于任意的a，b，aa，a*ba-2b，证明运算是可结合的，并说明运算不满足结合律。第26页，此课件共173页哦证明l因为对任意的a，b，cQ，（abc
11、=ac=a;a(bc)=a b=a，所以（ab）c=a(bc)，即得运算是可以结合的。又因为对Q中的元素0，1 （00）1=01=0-2=2 0（01）=0（-2）=0-2（-2）=4 所以（00）10（01），从而运算不满足结合律。第27页，此课件共173页哦练习题3l设A=a,b,c,d，运算表如下。l问题：是否满足交换律，是否有单位元，是否有零元，哪些元素有逆元？第28页，此课件共173页哦运算表解(2)(1)第29页，此课件共173页哦解l（1）运算可交换，没有零元，a是单位元，a-1=a,c-1=c,b-1=d,d-1=bl（2）运算不可交换，a是左零元，b是单位元，b-1=b；由于
12、c*d=b，所以c是d的右逆元，d是c的左逆元。第30页，此课件共173页哦运算表l若S,是代数系统，其中是有限非空集合S上的二元运算，那么该运算的部分性质可以从运算表直接看出，例如l1.当且仅当运算表中每个元素都属于S，运算具有封闭性。l2.当且仅当运算表关于主对角线对称时，运算具有可交换性。l3.S关于运算有单位元e，当且仅当表头e所在的列与左边一列相同且表左一列e所在的行与表头一行相同。第31页，此课件共173页哦l4.S关于运算有零元0，当且仅当表头0所在的列和表中左边一列0所在的行都是0。l5.设S关于运算有单位元，当且仅当位于a所在的行与b所在的列交叉点上的元素以及b所在的行与a所
13、在的列交叉点上的元素都是单位元时，a与b互为逆元。l6.代数系统S，中一个元素是否有左逆元或右逆元也可从运算表中观察出来，但运算是否满足结合律在运算表上一般不易直接观察出来。第32页，此课件共173页哦5.3同构与同态l代数系统的同构与同态就是在两个代数系统间存在着一种特殊的映射-保持运算的映射，它是研究两个代数系统间强有力的工具。l后面会分析，同构不仅使两个代数系统具有相同的基数，而且使运算保持相同的性质。第33页，此课件共173页哦l为什么需要研究代数系统间的关系？l在研究代数系统的过程中，所关心的常常是代数系统中运算所满足的性质，而不关心具体的运算，而对于遵循相同运算规律的系统，只需研究
14、其中一个就可以了解其他的系统。第34页，此课件共173页哦同构与同态l定义：设（X，）、（Y，*）是同类型的代数系统，均是二元运算，若存在一个函数：g：XY，使得若x1,x2X，则有 g(x1x2)=g(x1)*g(x2)则称g是从（X，）到（Y，*）的同态函数。第35页，此课件共173页哦特别的l若g是一一对应，则称g是（X，）到（Y，*）的同构函数，记（X，）（Y，*）；l若g是单射，则称g是（X，）到（Y，*）的单同态；l若g是满射，则称g是（X，）到（Y，*）的满同态。l一个系统与自身的同态称为自同态；l一个系统与自身的同构称为自同构。第36页，此课件共173页哦例子l例1.定义g:Z
15、Zm,g(k)=k（modm）=k，则V1与V2同态，易知g是满同态。第37页，此课件共173页哦例子l例2.f：QR，定义f(x)=2x,则f是单同态。l例3.教材65页例5.15，例5.16，例5.17 构造g(a)=a-3，证明g 是一一对应，且g(ab)=g(a)*g(b)第38页，此课件共173页哦例子l例4.(R,+)与(R+，)是同构的；(R+，)与(R,+)是满同态的。（1）设f:RR+,f(x)=ex；验证f是单射，满射，满足同态方程。（2）定义f:R+R,f(x)=lnx,同理可以验证函数是满射，满足同态方程。第39页，此课件共173页哦l设代数系统（X，）与（Y,*）同构
16、，g是同构函数，则两个同构的代数系统对运算保持许多相同的性质。第40页，此课件共173页哦性质l结合律l交换律l单位元存在性，且g(1x)=1Yl零元存在性，且g(0 x)=0Yl逆元 若（X，）对每个x均有逆元x-1,则（Y，*）对每个y也有逆元y-1，且g(x-1)=g(y-1)l分配律第41页，此课件共173页哦定理l定理：设G是一些只有一个二元运算的代数系统的非空集合，则G中代数系统间的同构关系是等价关系。l证明：设（X,）（Y,*）（Z,+）,g、f是同构映射。（1）（X,）（X,）,s(x)=x；自反的 （2）（X,）（Y,*）；对称的 (3)（X,）（Y,*）,（Y,*）（Z,+
17、）传递的 第42页，此课件共173页哦有 第43页，此课件共173页哦l同构是代数系统间的等价关系，所有同构的代数系统，只需研究一个即可。l设代数系统（X，）与（Y,*）满同态，代数系统的性质是单向保持，即（X，）的性质（Y,*）具有，反之不一定。第44页，此课件共173页哦自然同态l同余关系：整数集上除以m后余数相同的关系。例R=(x,y)|x-y能被3整除，以3为模的同余关系是等价关系，将Z分为3个划分块0、1、2，这是三个等价类：0=-3,-6,0,3,6,9 1=-5,-2,1,4,7,10 2=-4,-1,2,5,8,11第45页，此课件共173页哦（Z,+）上讨论R的性质l任取两个
18、类中的元素，通过+运算得到的元素均属同一个等价类。如：-5+（-4）0，1+11 0,即 1+2=0,1+1=2,2+2=1,1+0=0这是同余关系特有的性质，一般等价关系没有。第46页，此课件共173页哦同余关系l推广上述同余关系。设（X，*）上等价关系E，任意x1、x2、x1、x2X，若x1Ex1,x2Ex2,则有（x1*x2）E（x1*x2),称E为同余关系。l同余关系不仅要考虑在哪个集合上的关系是等价关系，还用考虑运算后的结果是否保持等价关系。l即（X，*）的运算*按等价类保持。第47页，此课件共173页哦例l（Z，）上，R1定义为xy(modm)；R2定义为R=(x,y)|x/y=2
19、m,mZ.解：前面已经验证R1是同余关系；R2首先是等价关系。其次，x1/x1=2k,x2/x2=2j,则 (x1x2)/(y1y2)=2(k+j),故R2是同余关系。第48页，此课件共173页哦练习题l设整数集（A，+）上定义R：(x,y)R等价于|x|=|y|。l问R是否是A上等价关系？是否是同余关系？第49页，此课件共173页哦解l R是A上等价关系。但R不是同余关系。若(x1,y1)R,(x2,y2)R，但是(x1+x2,y1+y2)R不一定成立。例(1,1)R,(2,-2)R，但|1+2|1-2|第50页，此课件共173页哦商代数l定义：设（X，）上同余关系E，因E是等价关系，可按E
20、对X分类，得一个商集X/E，在商集上定义运算*，对任一x1E、x2EX/E,有 x1E*x2E=x1x2E，这样（X/E，*）构成一个代数系统，称为（X，）的商代数。第51页，此课件共173页哦l定理：（X，）与其上的商代数（X/E，*）同态。l证明：构造函数g:XX/E，g(x)=xE,，易证g是满射。且有 g(x1x2)=x1x2E =x1E*x2E =g(x1)*g(x2)第52页，此课件共173页哦l称代数系统与商代数的同态是自然同态。由此任何一个代数系统总能找到与其同态的代数系统，这个同态的代数系统就是他的商代数。l下面的工作就是如何得到商代数，也就是找到代数系统上的同余关系。第53
21、页，此课件共173页哦一种同余关系l定义：设（X，）与（Y，*）同态，f：XY是同态映射。l在X上定义一个关系Ef：即如果X上元素通过映射f，在Y上有相同的像，则由这样的元素所构成的关系。第54页，此课件共173页哦定理l验证上面定义的关系Ef是同余关系。l证明：首先证明Ef是等价关系。其次证Ef是同余关系。若x1Efx1,x2Efx2,即 f(x1)=f(x1),f(x2)=f(x2),f(x1x2)=f(x1)*f(x2)=f(x1)*f(x2)=f(x1x2),因此x1x2Efx1x2，即Ef是同余关系。第55页，此课件共173页哦l定理：设f是（X，）与（Y，*）的满同态，必有（X/E
22、f，*）与（Y，*）同构。l证明:只要证明存在一一对应h：X/EfY,h(x)=f(x),s.t.h(x1*x2)=h(x1)*h(x2)第56页，此课件共173页哦(1)定义h：X/EfY,h(x)=f(x),由f是X到Y的满同态，任意x1,x2X，有 f(x1x2)=f(x1)*f(x2)有 所以h是同态函数。第57页，此课件共173页哦（2）如果x1 x2，则h(x1)=f(x1)h(x2)=f(x2)，所以h是单射。由f是满射，对Y中任一元素y必有X中元素x，s.t.f(x)=y。由X/Ef定义，xxEf，即任一y，必有xEf与之对应，s.t.h(x)=y，所以h是满射。第58页，此课
23、件共173页哦结论l这个定理说明对一个代数系统(X，)而言，任一个与它同态的代数系统(Y,*)总可以找到X的商代数（X/E，*）与它同构。l即从抽象观念看，一个代数系统仅与其商代数满同态。l也说明若(X，)与(Y,*)满同态，必能找到一个代数系统与Y同构。第59页，此课件共173页哦第60页，此课件共173页哦第六章 群论l 群是代数系统中最基本最重要的系统。在编码理论,密码安全中也有广泛的应用.第61页，此课件共173页哦6.1半群与单元半群l定义：设是一个二元代数系统：l半群：运算“*”满足结合律；l可换半群：半群中运算“*”满足交换律；l单元半群：半群中存在单位元el可换单元半群：半群满
24、足交换律，e存在l有限半群：S是有限集；无限半群：S是无限集；第62页，此课件共173页哦例例l指出下列代数系统中那些是半群，那些是可交换半群，那些不是半群：lZ,+,N,+,R,+，Z,N,R,，R-0,；l（P(A),）,（P(A),）；l（Z,max）,(Z,min),(Mn,)；l（Z4，+4）第63页，此课件共173页哦例1、设n n0,1,n1定义n n上的运算n 如下：x,yn n,xnyxy(mod n)，证明是含么半群2、设有集合Sk=x|xZ且xk,“+”是 一个普通的加法运算,试判断是否是一个半群？第64页，此课件共173页哦定义l定义：子半群 一个半群（S,*），如果它
25、有子代数（M,*），则M也是半群，称为S的子半群。l定义：等幂元 定义 a的幂 a1=a,a2=a*a,an+1=an*a 若a2=a,则称a为等幂元。第65页，此课件共173页哦l如果有单位元e,可以定义：x0=e。l如同一般的幂运算一样,由于结合律满足,有如下的公式：akaj=ak+j (ak)j=akj第66页，此课件共173页哦例l例1.半群的子代数,都是的子半群。l例2.设S,*是一个可交换的单元半群,M是它的所有的幂等元构成的集合,则是S,*的一个子单元半群。第67页，此课件共173页哦循环半群l定义：设是一个半群,若aS,使得对xS，都有 x=an 其中nZ+,特别地 e=a0.
26、则称此半群为由a所生成的循环半群,而a称为该循环半群的生成元；第68页，此课件共173页哦l若的生成元素是有限个元素，则称M=a|aS且a是S的生成元为该循环半群的生成集。l若满足交换律，则称S为可换循环半群。第69页，此课件共173页哦例l可换循环半群（N，+）。l判断代数系统是否是循环含幺半群？若是,请求出其所有的生成元。l代数系统是一个可换循环单元半群；对aZn,若(a,n)=1,则a是的生成元；当n是素数时,Zn中除单位元“0”以外,其它一切元素都是生成元。第70页，此课件共173页哦l定理：一个循环半群一定是一个可换半群。l推论：每个循环单元半群是可换单元半群。l定理：一个半群内的任
27、一元素和它所有的幂组成一个由a生成的循环子半群。证明：（S，*）是半群，任意aS，构造M=a,a2,a3,M上运算封闭，M是S的子集，故M是S的子代数；M是子半群，a是生成元，所以(M,*)是循环子半群。第71页，此课件共173页哦单元半群l单元半群是有单位元的半群。l例：教材P77例6.5。整数集上模m同余关系R所划分的类Zm=0,1,2,m-1，定义+m,m如下：l（Zm,+m)，（Zm,m)是单元半群，单位元分别是0,1,满足交换律。第72页，此课件共173页哦l单元半群是半群的扩充，比半群具有更多的性质。l设半群（S,*），若存在1S，有性质：1*1=1，任意xS，均有1*x=x*1=
28、x，则(S,*)构成单元半群。l定理：设S是有可列个元素的集合，（S，*）是单元半群，则在关于*的运算表中任何两行或两列均不相同。具体参见教材表6.2。第73页，此课件共173页哦l定理：单元半群（S，），若存在子系统（M,），且单位元在M中，则（M，）也是单元半群，称为子单元半群。l定义：循环单元半群：有单位元的循环半群，同时也是可换单元半群。第74页，此课件共173页哦l定理：一个可换单元半群，它的所有等幂元构成一个子单元半群。（67页例2）l证明：设可换单元半群（M，），M=等幂元（1）设a、bM,a2=a,b2=b，有(ab)(ab)=abab=aabb=ab，故(M,)构成代数系统。
29、（2）单位元是等幂元，故(M,)中有单位元。（3）M是M的子集。故(M,)是子单元半群。第75页，此课件共173页哦6.2群l定义：群。一个二元代数系统若满足：1)G中运算“*”满足结合律；2)G中存在关于运算“*”的单位元；3)G中每个元素都有逆元。则称该代数系统为一个群。或者定义：单元半群，每一个元素都有逆元。第76页，此课件共173页哦群的相关定义l定义：如果为一个群，运算“*”满足交换律，则称此群为可换群或Abel群；l若|G|是有限的,则称此群为有限群；l若|G|是无限的,则称此群为无限群；l群的阶，|G|，G的基数。l若G的子代数（H，*）也是群，则称为子群。第77页，此课件共17
30、3页哦例1l（Z,+），（Q,+），（R,+）都是群，（Z+,+）,（N,+）不是群。l设n是大于1的正整数，（Mn(R),+）是群,而（Mn(R),）不是群。l（P(B),）是群，其中为集合的对称差运算。l（Zn,）是群,其中Zn=1,2,n-1,为模n运算。l（R*,）不是群，是半群。其中R*为非零实数集合，运算定义为：任意x,y R*,x y=y。第78页，此课件共173页哦例2l（Z,+）,（R,+）都是无限群;（Zn,）是n阶有限群；（0,+）是平凡群，只有一个元素，既是单位元又是零元素。它们均为交换群.ln(n1)阶实可逆矩阵的集合关于矩阵乘法构成的群是非交换群，但对于加法构成交换
31、群。第79页，此课件共173页哦练习题l判断下列代数系统是否是群或Abel群：,，,，,，,l解：Abel群有,？第80页，此课件共173页哦练习题l证明是群。l证明：前面已证是单元半群，0为单位元，下面证明每个元素均有逆元。如果x0，显然010，如果x0，则有n-xn，显然xn(n-x)=(n-x)+nx=0 所以x的逆元是n-x，因此xn，x有逆元。即是群。第81页，此课件共173页哦群的性质l群G中每个元素都是可消去的，即运算满足消去律；l群G中除e外无其它幂等元；为什么？l阶大于1的群G不可能有零元；为什么？l群G中的任意两个元素a,b，都有 (a*b)-1b-1*a-1l群G的运算表
32、中任意一行(列)都没有两个相同的元素；第82页，此课件共173页哦群的性质l一个群的方程a*x=b和y*a=b中，在群内有唯一解。l证明：首先方程a*x=b解是存在的，x=a-1*b;其次解是唯一的。若x1也是方程的解，有a*x=a*x1=b，由群的消去律知x=x1。第83页，此课件共173页哦群的第二定义l定义：若代数系统(G,*)满足下列条件，则称为群。（1）结合律。（2）方程a*x=b和y*a=b在G内有唯一解。第84页，此课件共173页哦证明：只要推出G有单位元和逆元即可。（1）a*x=a的解为右单位元1r,同理y*a=a的解为左单位元1l，由解的唯一性，1r=1l（2）由a*x=1和
33、y*a=1分别得a的右、左逆元，又因满足结合律，左右逆元相等。第85页，此课件共173页哦群的同态、同构l定义：设群(G，)、(H，*)，若存在函数g：GH，s.t.对每个a、bG，有g(ab)=g(a)*g(b)，则称g是从(G，)到(H，*)的群同态。若g是一一对应，则称为群同构。l定理：设(G，)与(H，*)群同态，函数g：GH是同态函数，则有g(1G)=1H,g(a-1)=g(a)-1l定理：设(G，)是群，若(G，)与(H，*)满同态或同构，则(H，*)也构成群。第86页，此课件共173页哦变换群l变换的定义：集合上的变换是从S到S的一个一一对应函数，记为t：SS。l例：S=1,2，
34、则t1(1)=1,t1(2)=2是变换；t2(1)=2,t2(2)=1是变换；但t3(1)=1,t3(2)=1不是变换。S=t1,t2是变换的集合，称为变换集。第87页，此课件共173页哦lS中元素是变换，是一种函数，这是一种关系，而关系存在复合运算，故变换也存在复合运算，可称为复合变换。l在变换集上定义一个变换的二元运算，可构成一个代数系统。这个二元运算可以取变换的复合运算。第88页，此课件共173页哦验证变换群（1）S上的变换是封闭的。（2）S上有恒等变换，故S中单位元即是恒等变换：t1(x)=x。对任意tS,t1*t=t*t1=t（3）S上任意变换t均为一一对应，故其逆变换t-1也是S上
35、的，t*t-1=t1。（4）复合变换满足结合律。因此（S,*）构成群，称之为变换群。l若S上的一些变换和复合运算构成一个群，也称为变换群。第89页，此课件共173页哦l定义：集合S上的若干变换与复合运算若构成群，则称为变换群。l定理：任一个群(G,*)均与一个变换群同构。l证明：取aG,存在变换ta，对G中每个元素，ta(x)=x*a，这样G中每个元素都有一个变换与之对应，设G=a,b,c,d,，有ta,tb,tc,td,记为集合G=ta,tb,tc,td,。第90页，此课件共173页哦 定义为变换的复合运算。下面证明存在一一对应函数g:GG，满足同构方程。令g(a)=ta,可证g是函数，是单
36、射，是满射，且有 g(a*b)=ta*b=x*a*b=tb(x*a)=tb(ta(x)=tatb=g(a)g(b)第91页，此课件共173页哦l任意一个群均可在变换群中找到一个同构群，故对群的研究可归结为对变换群的研究。第92页，此课件共173页哦有限群l 设S为有限集，以|S|=3为例，有6个不同的变换，设S=1,2,3，有 可证这些变换对运算*构成一个群，称为对称群。记为S3=p1,p2,p3,p4,p5,p6,其中p1是单位元。p2、p3、p6的逆元还是她们自身。p5、p4互为逆元。第93页，此课件共173页哦l定理：一个有限集上所有变换及复合运算构成一个群。l例：S=p1,p4,p5构
37、成一个群，也称变换群。l定义：对称群、置换群|S|=n,S上所有变换构成一个集合Sn,Sn及复合运算构成的群称为S的对称群。若S上有若干变换，所组成的集合P及*构成的群（P，*）称为S的置换群。第94页，此课件共173页哦l定理：S的对称群（Sn,*）的阶为n!。l证明：由排列组合的理论知识很容易可知。第95页，此课件共173页哦有限群的另一个定义l定理：一个代数系统（G，*），若G为有限且满足结合律及消去律，则构成一个群。l证明：用群的第二定义：结合律以及 a*x=b,y*a=b方程存在唯一解。设G=a1,a2,an，取aG，作 G=a*a1,a*a2,a*an。第96页，此课件共173页哦
38、 由G代数系统的封闭性，G是G的子集，且由消去律，若ij，a*aia*aj。故|G|=n,因此G=G。所以对bG或G，必有 akG,s.t.b=a*ak，且ak唯一。同理y*a=b也存在唯一解。第97页，此课件共173页哦群表l对有限群，可用一组合表将运算表示出来，称为群表。l设|G|=1，群表是唯一的。l设|G|=2，群表是唯一的。l设|G|=3，群表是唯一的，且是对称的，因此3阶群是可换群。l设|G|=4，群表不是唯一的，且均是对称的。第98页，此课件共173页哦群表|G|4l|G|=1l|G|=2l|G|=3l|G|=4l这几个群表参见教材87页。第99页，此课件共173页哦从以上群表可
39、看出一些特性：l由于单位元1存在，群表中总有一行（一列）与表头元素一样。l由于消去律，群表中每行（每列）各不相同，且任两行（两列）对应元也不同。因此，群表每一行（列）是群中元素的一个排列，是G中元素的一个置换。l若G是可换群，其可换性与群表的对称性是一致的。第100页，此课件共173页哦l定理：每个有限群均与一个置换群同构。l证明：由教材83页定理6.11，置换群中的每个置换是变换的特例，与复合运算构成一个群，且与对应的有限群同构。第101页，此课件共173页哦循环群l定义：方幂 设G是群，令a0=1,aj+1=aj*a,a-j=(a-1)j,有性质akaj=ak+j，(ak)j=akj l定
40、义：循环群 若群G的每个元素均是它的某一个固定元素a的某次方幂，则称G是由a生成的循环群，a称为G的生成元素。第102页，此课件共173页哦l定义：周期 一个由a生成的循环群（G，*），若存在m，使得am=1的最小正整数m称为a的周期；若不存在这样的m，则称a的周期无限。第103页，此课件共173页哦循环群的构造l对于任何群G，由G中元素a生成的子群是循环群。l 任何素数阶的群都是循环群。l设G是循环群，若a是n阶元，则 G=a0,a1,a2,an-1，那么|G|=n 称G为n阶循环群;若a是无限阶元，则 G=a0,a1,a2,a3 称G为无限阶循环群。第104页，此课件共173页哦l例：（Z
41、，+）无限循环群，生成元：1，-1l例：（4，+4）周期为4的循环群，生成元：1、3l例：模为m 的剩余类加群（Zm,+m）周期为m的循环群，生成元：1、k，其中k是与m互质的数。第105页，此课件共173页哦循环群定理l定理：设由a生成的循环群G，则有（1）若a的周期无限，则G与整数加群（I，+）同构。（2）若a的周期有限，则G与剩余类加群（Zm，+m）同构。l证明:(1)定义f:GI，f(ak)=k (2)定义g:GZm，g(ak)=k 验证f、g函数均是一一对应，且满足同态方程。第106页，此课件共173页哦l由上面定理说明，任何循环群都可以找到与之同构的群。无论是整数加群还是剩余类加群
42、的性质特性都有深刻的研究。故循环群的问题已基本解决。第107页，此课件共173页哦G=循环群的生成元l定理：(1)若G是无限循环群，则G的生成元是a和a1。(2)若G是n阶循环群，则 G有(n)个生成元，当n=1时G=的生成元为e；当 n1时,对于任何小于等于n且与n互质的正整数r，ar是G的生成元。即G的生成元ar(n,r)=1.第108页，此课件共173页哦证明思路：l (1)证明 a1是生成元。证明若存在生成元b，则b=a或a1。l (2)只需证明(r,n)=1,则ar是生成元 反之，若ar是生成元，则(r,n)=1.第109页，此课件共173页哦证明（1）l(1)a是生成元，G,任取
43、aiG,ai=(a1)i G。假设 b 为生成元，b=aj,a=bt,a=bt=(aj)t=ajt ajt1=e 若 jt10与 a为无限阶元矛盾,因此 j=t=1 或 j=t=1。第110页，此课件共173页哦证明（2）l详细的证明可以参加其它资料。如果同学有兴趣，查阅北京大学离散数学精品课程。第111页，此课件共173页哦例题l例1.设G是12阶循环群，则小于或等于12且与12互质的数是1，5，7，11。设G=,则a1,a5,a7,a11是生成元。l例2.设Z9是模9的整数加法群，则G的生成元是1，2，4，5，7，8。l例3.设G=3Z=3k|kZ,G上的运算是普通加法，那么G只有两个生成
44、元：3和-3。第112页，此课件共173页哦子群l定义：一个群G如果它的子代数（H，*）也是一个群，则称H是G的一个子群。lH是群则必须满足一些条件，下面给出充要条件。l定理：一个群G，由它的一个子集H组成一个系统，该系统构成G的子群的充要条件是 a,bH,则a*bH；aH,则a-1H 证明：略第113页，此课件共173页哦有关子群的定理l定理：设H是G的一个子群，则 1H=1G，aH-1=aG-1l定理：设G是群，G的子集H所构成的子代数（H，*）是子群的充要条件是：若a,bH，则a*b-1 H。第114页，此课件共173页哦有限子群的定理l定理：设G是群，G的一个有限子集H所构成的（H，*
45、）是一个群的充要条件是：若a,bH，则a*bH。l证明：结合律满足说明构成代数系统；第115页，此课件共173页哦平凡子群及例子l例1：任一个群（G，*）都有两个子群，群（G，*）和（1，*），这两个是任意群都有的子群，称之为平凡子群。l例2：群（Z4，+4）中，(2,+4)不是子群；(1,3,+4)不是子群；(0,2,+4)是子群。第116页，此课件共173页哦子群的例子l例3：设群（G，*），任意aG,定义H=an,则H是G的子群。l例4：定义Z2=2n|n是整数，（Z2，+）是（Z，+）的子群。第117页，此课件共173页哦子群的陪集及Lagrange定理l 群的子群反映了群的结构和性质
46、；陪集和拉格朗日定理反映了群与子群之间的关系。l例：整数加群利用模3同余关系，将I划分成3个剩余类，分别是0,1,2。对于以上的同余关系R，也可表示成另一种方式。记H=3*i|iI，由定理知，H是整数加群的子群。第118页，此课件共173页哦模3同余关系lG上的模3同余关系，a,bG,a=b(mod3)等价于（a-b）/3余数为0。即l故可由a-bH或a+b-1H来确定等价关系，进而对G进行分类。l也就是说，G的剩余类是利用H来分类的。第119页，此课件共173页哦把上例推广至一般情况l设H是G 的一个子群，确定G上的一个关系R，（a,b）R当且仅当a*b-1 H，这个关系称为G上的右陪集关系
47、，可写为 ab(modH)l定理：设G有一个子群H，则在G上的一个右陪集关系R，ab(modH)是等价关系。证明：略第120页，此课件共173页哦l例：H=3i,验证I上m=3同余关系是右陪集关系。第121页，此课件共173页哦右陪集l定义：右陪集 a.群G的子集H所确定的右陪集关系对G所划分的类称为子群H的右陪集，包含a的右陪集记以Ha。b.H是群G的子群，称Ha=h*a|hH为由aG确定的子群H的右集，a称为Ha的代表元素。第122页，此课件共173页哦分析右陪集的定义l由定义知，右陪集是由一个等价关系（右陪集关系）所划分成的等价类。l右陪集的元素构成。Ha=x|xG,xa(modH)，(
48、x,a)R,x与a有右陪集关系：x*a-1H，记h=x*a-1，得x=h*a，故Ha=h*a|hH。l因此包含a的右陪集是H内所有元素与a运算后所得结果组成的集合。第123页，此课件共173页哦左陪集l定义：左陪集 由G的一个子群可确定群G上的左陪集关系R，（a,b）R当且仅当b-1*a H，这个R是等价关系,称为左陪集关系。由R所划分的等价类称为左陪集。包含a的左陪集记以aH=ah|hH。l左陪集与右陪集是类似的，都是由陪集关系确定的等价类。第124页，此课件共173页哦等势l定理：群G的一个子群H与其每个右陪集Ha等势。l证明：定义f：HHa，f(h)=h*a。可以证明f是一一对应。因此H
49、与Ha等势。第125页，此课件共173页哦相同的基数l定理1：设H是群G的一个子群，Ha、Hb是任意两个右陪集（或左陪集），则或者Ha=Hb，或者Ha与Hb是分离的。l证明：略。因为右陪集是等价类，那么按照等价关系的理论，由等价关系划分的等价类要么相等要么相互分离。第126页，此课件共173页哦分析l 设Ha与Hb相互分离，即是不同的等价类，那么它们均与H是等势的，因此Ha与Hb这两个不同的右陪集具有相同的基数。l 得出结论:(H,*)的所有右陪集具有相同的基数。第127页，此课件共173页哦拉格朗日定理l定理：一个有限群G的阶一定被它的子群的阶所等分。l分析：阶为n有限群的子群H阶为m,也是
50、有限群，H的所有右陪集构成了G上的所有等价类，也就是构成了G上的一个划分。l每个划分块即每个右陪集的基数是相同的，并且必为整数，与H的基数相同。即|aH|=|H|=m，这样由H确定的等价关系产生的划分块个数为n/m。第128页，此课件共173页哦拉格朗日定理推论l设G的子群H的右陪集个数为k(称之为G内H的指数)，则有k=|G|/|H|l推论1：任一个阶为素数的有限群没有真子群。l推论2：任一个阶为n的有限群的循环子群，它的周期均能除尽n。l推论3：任一个阶为n的有限群，可得到 an=1第129页，此课件共173页哦l证明1：若有真子群H阶为q，设G的阶为p,则p/q为整数，即q是p的真因子，