代数系统基础

代数系统基础第1页，课件共173页，创作于2023年2月近世代数这部分内容属于近世代数的范畴，近世代数是研究具有运算的集合，它第一次揭示了数学系统的多变性与丰富性。代数结构理论可用于计算机算法的复杂性分析，研究抽象数据结构的性质及操作，同时也是程序设计语言的理论基础。第2页，课件共173页，创作于2023年2月本篇内容我们将介绍代数系统的最基本概念和最基本理论，以及几类常用的代数系统，它们是：半群，群，环，域，格和布尔代数。本课程在第五、六、七章中介绍代数系统的内容。第3页，课件共173页，创作于2023年2月第五章代数系统基础代数系统是用代数运算构造数学模型的方法。这是一种抽象的方法，故又称抽象代数，又由于此种方法是在集合上通过构造手段生成，也可称为代数系统。第4页，课件共173页，创作于2023年2月§5.1代数系统的一般概念一个代数系统需要满足三个条件：（1）一个非空集合S；（2）一些建立在集合S上的运算；（3）这些运算在S上是封闭的；

第5页，课件共173页，创作于2023年2月封闭的含义其运算的结果都是在原来的集合中，我们称具有这种特征的运算是封闭的。如：数集上加法、绝对值、相反数运算；幂集上交、并运算等。不封闭运算的例子也有很多，如设N是自然数集，Z是整数集，普通的减法定义为N×N到Z的运算，是不封闭的。第6页，课件共173页，创作于2023年2月运算符通常用等△，﹡，·，……等表示二元运算，称为运算符。若f：s×s→s是集合S上的二元运算，对任意x,y,如果x与y运算的结果是z,即f(x，y)=z,可利用运算·简记为x·y=z。类似于二元运算，也可以使用运算符来表示n元运算。如f（a1，a2，…，an）=b

可简记为﹡（a1，a2，…，an）=b

第7页，课件共173页，创作于2023年2月

n=1时﹡（a1）=b是一元运算；

n=2时﹡（a1，a2）=b是二元运算；

n=3时﹡（a1，a2，a3）=b是三元运算；这些相当于前缀表示法，但对于二元运算用得较多的还是a1﹡a2=b，以下所涉及的n元运算主要是一元运算和二元运算。第8页，课件共173页，创作于2023年2月代数系统的例子（1）求一个数的倒数是非零实数集R*上的一元运算。（2）非零实数集R*上的乘法和除法都是R*上的二元运算，而加法和减法不是。（3）S是一非空集合，SS是S到S上的所有函数的集合，则复合运算○是SS上的二元运算。（4）空间直角坐标系中求点（x，y，z）的坐标在x轴上的投影，可以看作实数集R上的三元运算：f(x，y，z)=x，因为参加运算的是有序的3个实数，而结果也是实数。第9页，课件共173页，创作于2023年2月运算规律考察代数系统＜Z，+＞。很明显，在这个代数系统中，关于加法运算，具有以下二个运算规律，即对于任意的x，ｙ，ｚ∈Ｚ，有

(1)x+y=y+x(交换律)(2)(x+y)+z=x+(y+z)（结合律）又如，设S是集合，P（S）是S的幂集，则代数系统＜P（S），U＞和＜P（S），∩＞中的∪、∩都适合交换律，结合律，即他们与＜Z，+＞有类似的运算性质。这些就是代数系统研究的一部分内容。第10页，课件共173页，创作于2023年2月同类型的代数系统定义：如果两个代数系统有相同个数的运算符，每个对应的运算符有相同的元数，则称这两个代数系统有相同的类型。例：整数集上加法与实数集上乘法；

N阶矩阵集上加法、乘法运算。第11页，课件共173页，创作于2023年2月子代数定义：两个代数系统（S，×），（S’，+），若满足下列条件：（1）S’是S的子集（2）则称（S’，+）是（S，×）的子代数或子系统。例：偶数集上加法是整数集上加法的子代数。第12页，课件共173页，创作于2023年2月§5.2代数系统常见的性质对给定的集合，我们可以任意地在这个集合上规定运算使它成为代数系统。但我们所研究的是其运算有某些性质的代数系统。在前面考察几个具体的代数系统时，已经涉及到我们所熟悉的运算的某些性质。这一节，主要讨论一般二元运算的一些性质。第13页，课件共173页，创作于2023年2月代数系统（S，*）上性质1.结合律2.交换律例：常用的代数系统：数集上加法、乘法，幂集上交、并运算。第14页，课件共173页，创作于2023年2月3.分配律以上是第一分配律、第二分配律。例：数集上乘法对加法满足分配律，但加法对乘法不满足。幂集上交对并、并对交满足分配律。第15页，课件共173页，创作于2023年2月单位元定义：若存在一个元素e∈S,对任一x∈S，均有x*e=x，则称e为右单位元，记1r；若e*x=x，则称e为左单位元,记1l。常用1来表示单位元。注：1只是一个符号，用来表示S中单位元素。第16页，课件共173页，创作于2023年2月单位元定理定理1：若左单位元、右单位元都存在，则两者相等。定理2：若单位元存在，则必唯一。第17页，课件共173页，创作于2023年2月证明定理1：若1r、1l存在，1l*1r=1r=1l。定理2：设有两个单位元e1、e2，任一x∈S，e1*x=x，取x=e2，有e1*e2=e2，又e2也是单位元，e1*e2=e1。因此e1=e2，单位元是唯一的。第18页，课件共173页，创作于2023年2月零元素定义：若存在一个元素a∈S,对任一x∈S，均有x*a=a，则称a为右零元，记0r；若a*x=a，则称a为左零元,记0l。常用0来表示零元素。注：0只是一个符号，表示S中零元素。定理：若左零元、右零元都存在，则两者相等。定理：若零元存在，则必唯一。

第19页，课件共173页，创作于2023年2月例子数集上加法，单位元1=0；数集上乘法，单位元1=1。集合A的幂集上交运算。单位元1是A，零元0是空集；并运算的单位元是空集，零元是A。正整数集I上的运算min,max。其中min为取最小值运算，max是取最大值运算。(I,min)上零元是1，单位元不存在；(I,max)上零元不存在，单位元是1；第20页，课件共173页，创作于2023年2月逆元素：设（S，*）上单位元存在定义：若对S内元素a，存在a-1r∈S,有

a*a-1r=1，则称a-1r为a的右逆元素；若存在a-1l∈S,有a-1l*a=1，则称a-1l为a的左逆元素。第21页，课件共173页，创作于2023年2月定理定理1：一个代数系统（S，*）,如果其运算满足结合律，则左、右逆元相等。定理2：一个代数系统（S，*）,如果运算满足结合律且逆元存在，则S内每一个元素的逆元是唯一的。第22页，课件共173页，创作于2023年2月例子整数集上加法。单位元是0，a的逆元是-a；整数集上乘法，单位元是1，只有1、-1有逆元；实数集上乘法，0没有逆元。自然数集上加法。单位元是0，0的逆元是0，其他元素没有逆元。在非零的实数集R*上定义运算﹡，使对于任意的元素a,b∈R*，有a﹡b=a。那么，R*的任何元素都是运算﹡的左零元，而R*中运算﹡没有右零元，因此没有零元。第23页，课件共173页，创作于2023年2月练习题题1设Z是整数集，，☆分别是Z上的二元运算，其定义为，对任意的a，ｂ∈Ｚ，a△ｂ＝ab－a－b，a☆ｂ＝ab—a＋b，问Ｚ上的运算△，☆分别是否可交换？第24页，课件共173页，创作于2023年2月解因为a△b＝ab－a－ｂ=ba－ｂ－a＝ｂ△a，对Z中任意元素a，b成立，所以运算△是可以交换的。又因为对Z中的数0，1，0☆1=0×1－0+1=1，1☆0=1×0—1+0=－1，所以，0☆1≠1☆0，从而运算☆是不可交换的第25页，课件共173页，创作于2023年2月练习题2设Ｑ是有理数集合，⊙，﹡分别是Ｑ上的二元运算，其定义为，对于任意的a，b∈Ｑ，a⊙ｂ＝a，a*b＝a-2b，证明运算⊙是可结合的，并说明运算﹡不满足结合律。第26页，课件共173页，创作于2023年2月证明因为对任意的a，b，c∈Q，（a⊙b⊙c=a○c=a;a⊙(b⊙c)=a⊙b=a，所以（a⊙b）⊙c=a⊙(b⊙c)，即得运算⊙是可以结合的。又因为对Q中的元素0，1

（0﹡0）﹡1=0﹡1=0-2=20﹡（0﹡1）=0﹡（-2）=0-2×（-2）=4

所以（0﹡0）﹡1≠0﹡（0﹡1），从而运算﹡不满足结合律。第27页，课件共173页，创作于2023年2月练习题3设A={a,b,c,d}，运算表如下。问题：是否满足交换律，是否有单位元，是否有零元，哪些元素有逆元？第28页，课件共173页，创作于2023年2月运算表解(2)(1)第29页，课件共173页，创作于2023年2月解（1）运算可交换，没有零元，a是单位元，a-1=a,c-1=c,b-1=d,d-1=b（2）运算不可交换，a是左零元，b是单位元，b-1=b；由于c*d=b，所以c是d的右逆元，d是c的左逆元。第30页，课件共173页，创作于2023年2月运算表若＜S,○＞是代数系统，其中○是有限非空集合S上的二元运算，那么该运算的部分性质可以从运算表直接看出，例如1.当且仅当运算表中每个元素都属于S，运算○具有封闭性。2.当且仅当运算表关于主对角线对称时，运算○具有可交换性。3.S关于运算○有单位元e，当且仅当表头e所在的列与左边一列相同且表左一列e所在的行与表头一行相同。第31页，课件共173页，创作于2023年2月4.S关于运算○有零元0，当且仅当表头0所在的列和表中左边一列0所在的行都是0。5.设S关于运算○有单位元，当且仅当位于a所在的行与b所在的列交叉点上的元素以及b所在的行与a所在的列交叉点上的元素都是单位元时，a与b互为逆元。6.代数系统＜S，○＞中一个元素是否有左逆元或右逆元也可从运算表中观察出来，但运算是否满足结合律在运算表上一般不易直接观察出来。第32页，课件共173页，创作于2023年2月§5.3同构与同态代数系统的同构与同态就是在两个代数系统间存在着一种特殊的映射----保持运算的映射，它是研究两个代数系统间强有力的工具。后面会分析，同构不仅使两个代数系统具有相同的基数，而且使运算保持相同的性质。第33页，课件共173页，创作于2023年2月为什么需要研究代数系统间的关系？在研究代数系统的过程中，所关心的常常是代数系统中运算所满足的性质，而不关心具体的运算，而对于遵循相同运算规律的系统，只需研究其中一个就可以了解其他的系统。第34页，课件共173页，创作于2023年2月同构与同态定义：设（X，△）、（Y，*）是同类型的代数系统，均是二元运算，若存在一个函数：g：X→Y，使得若x1,x2∈X，则有g(x1△x2)=g(x1)*g(x2)则称g是从（X，△）到（Y，*）的同态函数。第35页，课件共173页，创作于2023年2月特别的若g是一一对应，则称g是（X，△）到（Y，*）的同构函数，记（X，△）≌（Y，*）；若g是单射，则称g是（X，△）到（Y，*）的单同态；若g是满射，则称g是（X，△）到（Y，*）的满同态。一个系统与自身的同态称为自同态；一个系统与自身的同构称为自同构。第36页，课件共173页，创作于2023年2月例子例1.

定义g:Z→Zm,g(k)=k（modm）=[k]，则V1与V2同态，易知g是满同态。第37页，课件共173页，创作于2023年2月例子例2.f：Q→R，定义f(x)=2x,则f是单同态。例3.教材65页例5.15，例5.16，例5.17

构造g(a)=a-3，证明g是一一对应，且g(a^b)=g(a)*g(b)第38页，课件共173页，创作于2023年2月例子例4.(R,+)与(R+，×)是同构的；(R+，×)与(R,+)是满同态的。（1）设f:R→R+,f(x)=ex；验证f是单射，满射，满足同态方程。（2）定义f:R+→R,f(x)=lnx,同理可以验证函数是满射，满足同态方程。第39页，课件共173页，创作于2023年2月设代数系统（X，^）与（Y,*）同构，g是同构函数，则两个同构的代数系统对运算保持许多相同的性质。第40页，课件共173页，创作于2023年2月性质结合律交换律单位元存在性，且g(1x)=1Y零元存在性，且g(0x)=0Y逆元若（X，^）对每个x均有逆元x-1,则（Y，*）对每个y也有逆元y-1，且g(x-1)=g(y-1)分配律第41页，课件共173页，创作于2023年2月定理定理：设G是一些只有一个二元运算的代数系统的非空集合，则G中代数系统间的同构关系是等价关系。证明：设（X,^）≌（Y,*）≌（Z,+）,g、f是同构映射。（1）（X,^）≌（X,^）,s(x)=x；自反的（2）（X,^）≌（Y,*）；对称的

(3)（X,^）≌（Y,*）,（Y,*）≌（Z,+）传递的

第42页，课件共173页，创作于2023年2月有

第43页，课件共173页，创作于2023年2月同构是代数系统间的等价关系，所有同构的代数系统，只需研究一个即可。设代数系统（X，●）与（Y,*）满同态，代数系统的性质是单向保持，即（X，●）的性质（Y,*）具有，反之不一定。第44页，课件共173页，创作于2023年2月自然同态同余关系：整数集上除以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页，创作于2023年2月（Z,+）上讨论R的性质任取两个类中的元素，通过+运算得到的元素均属同一个等价类。如：-5+（-4）∈[0]，1+11∈[0]…,即[1]+[2]=[0],[1]+[1]=[2],[2]+[2]=[1],[1]+[0]=[0]…这是同余关系特有的性质，一般等价关系没有。第46页，课件共173页，创作于2023年2月同余关系推广上述同余关系。设（X，*）上等价关系E，任意x1、x2、

x1’、x2’∈X，若x1Ex1’,x2Ex2’,则有（x1*x2）E（x1’*x2),称E为同余关系。同余关系不仅要考虑在哪个集合上的关系是等价关系，还用考虑运算后的结果是否保持等价关系。即（X，*）的运算*按等价类保持。第47页，课件共173页，创作于2023年2月例（Z，×）上，R1定义为x≡y(modm)；

R2定义为R={(x,y)|x/y=2m,m∈Z}.

解：前面已经验证R1是同余关系；

R2首先是等价关系。其次，x1/x1’=2k,x2/x2’=2j,则

(x1×x2)/(y1×y2)=2(k+j),

故R2是同余关系。第48页，课件共173页，创作于2023年2月练习题设整数集（A，+）上定义R：(x,y)∈R等价于|x|=|y|。问R是否是A上等价关系？是否是同余关系？第49页，课件共173页，创作于2023年2月解

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页，创作于2023年2月商代数定义：设（X，△）上同余关系E，因E是等价关系，可按E对X分类，得一个商集X/E，在商集上定义运算*，对任一[x1]E、[x2]E∈X/E,有

[x1]E*[x2]E=[x1△x2]E，这样（X/E，*）构成一个代数系统，称为（X，△）的商代数。第51页，课件共173页，创作于2023年2月定理：（X，△）与其上的商代数（X/E，*）同态。证明：构造函数g:X→X/E，g(x)=[x]E,，易证g是满射。且有

g(x1△x2)=[x1△x2]E=[x1]E*[x2]E

=g(x1)*g(x2)第52页，课件共173页，创作于2023年2月称代数系统与商代数的同态是自然同态。由此任何一个代数系统总能找到与其同态的代数系统，这个同态的代数系统就是他的商代数。下面的工作就是如何得到商代数，也就是找到代数系统上的同余关系。第53页，课件共173页，创作于2023年2月一种同余关系定义：设（X，▽）与（Y，*）同态，f：X→Y是同态映射。在X上定义一个关系Ef：即如果X上元素通过映射f，在Y上有相同的像，则由这样的元素所构成的关系。第54页，课件共173页，创作于2023年2月定理验证上面定义的关系Ef是同余关系。证明：首先证明Ef是等价关系。其次证Ef是同余关系。若x1Efx1’,x2Efx2’,即f(x1)=f(x1’),f(x2)=f(x2’),f(x1▽x2)=f(x1)*f(x2)=f(x1’)*f(x2’)=f(x1’▽x2’),

因此x1▽x2Efx1’▽x2’，即Ef是同余关系。第55页，课件共173页，创作于2023年2月定理：设f是（X，⊙）与（Y，*）的满同态，必有（X/Ef，*）与（Y，*）同构。证明:只要证明存在一一对应h：

X/Ef→Y,h([x])=f(x),s.t.h([x1]*[x2])=h([x1])*h([x2])

第56页，课件共173页，创作于2023年2月(1)定义h：X/Ef→Y,h([x])=f(x),由f是X到Y的满同态，任意x1,x2∈X，有

f(x1⊙x2)=f(x1)*f(x2)有

所以h是同态函数。第57页，课件共173页，创作于2023年2月（2）如果[x1]≠[x2]，则h([x1])=f(x1)≠h([x2])=f(x2)，所以h是单射。由f是满射，对Y中任一元素y必有X中元素x，s.t.f(x)=y。由X/Ef定义，x∈[x]Ef，即任一y，必有[x]Ef与之对应，

s.t.h([x])=y，所以h是满射。第58页，课件共173页，创作于2023年2月结论这个定理说明对一个代数系统(X，⊙)而言，任一个与它同态的代数系统(Y,*)总可以找到X的商代数（X/E，*）与它同构。即从抽象观念看，一个代数系统仅与其商代数满同态。也说明若(X，⊙)与(Y,*)满同态，必能找到一个代数系统与Y同构。第59页，课件共173页，创作于2023年2月第60页，课件共173页，创作于2023年2月第六章群论群是代数系统中最基本最重要的系统。在编码理论,密码安全中也有广泛的应用.

第61页，课件共173页，创作于2023年2月§6.1半群与单元半群定义：设<S,*>是一个二元代数系统：半群：运算“*”满足结合律；可换半群：半群中运算“*”满足交换律；单元半群：半群中存在单位元e可换单元半群：半群满足交换律，e存在有限半群：S是有限集；无限半群：S是无限集；第62页，课件共173页，创作于2023年2月例指出下列代数系统中那些是半群，那些是可交换半群，那些不是半群：〈Z,+〉,〈N,+〉,〈R,+〉，〈Z,×〉,〈N,×〉,〈R,×〉，〈R-{0},〉；（P(A),∪）,（P(A),∩）；（Z,max）,(Z,min),(Mn,×)；（Z4，+4）第63页，课件共173页，创作于2023年2月例1、设n＝｛0,1,…,n－1｝定义n上的运算＋n

如下：

x,y∈n,x＋ny＝x＋y(modn)，证明<n,＋n>是含么半群2、设有集合Sk={x|xZ且xk},“+”是一个普通的加法运算,试判断<Sk,+>是否是一个半群？第64页，课件共173页，创作于2023年2月定义定义：子半群一个半群（S,*），如果它有子代数（M,*），则M也是半群，称为S的子半群。定义：等幂元定义a的幂

a1=a,a2=a*a,……,an+1=an*a

若a2=a,则称a为等幂元。第65页，课件共173页，创作于2023年2月如果<S,*>有单位元e,可以定义：x0=e。如同一般的幂运算一样,由于结合律满足,有如下的公式：

akaj=ak+j

(ak)j=ak×j第66页，课件共173页，创作于2023年2月例例1.半群<R,×>的子代数<{0,1},×>,<Z,×>,<R+,×>都是<R,×>的子半群。例2.设〈S,*〉是一个可交换的单元半群,M是它的所有的幂等元构成的集合,则<M,*>是〈S,*〉的一个子单元半群。第67页，课件共173页，创作于2023年2月循环半群定义：设<S,*>是一个半群,若aS,使得对xS，都有

x=an

其中nZ+,特别地e=a0.

则称此半群为由a所生成的循环半群,而a称为该循环半群的生成元；第68页，课件共173页，创作于2023年2月若<S,*>的生成元素是有限个元素，则称M={a|aS且a是S的生成元}为该循环半群的生成集。若满足交换律，则称S为可换循环半群。第69页，课件共173页，创作于2023年2月例可换循环半群（N，+）。判断代数系统<4,+4>是否是循环含幺半群？若是,请求出其所有的生成元。代数系统<Zn,+n>是一个可换循环单元半群；

对aZn,若(a,n)=1,则a是<Zn,+n>的生成元；当n是素数时,Zn中除单位元“0”以外,其它一切元素都是生成元。第70页，课件共173页，创作于2023年2月定理：一个循环半群一定是一个可换半群。推论：每个循环单元半群是可换单元半群。定理：一个半群内的任一元素和它所有的幂组成一个由a生成的循环子半群。证明：（S，*）是半群，任意a∈S，构造M={a,a2,a3,……},M上运算封闭，M是S的子集，故M是S的子代数；M是子半群，a是生成元，所以(M,*)是循环子半群。第71页，课件共173页，创作于2023年2月单元半群单元半群是有单位元的半群。例：教材P77例6.5。整数集上模m同余关系R所划分的类Zm={[0],[1],[2],……[m-1]}，定义+m,×m如下：（Zm,+m)，（Zm,×m)是单元半群，单位元分别是[0],[1],满足交换律。第72页，课件共173页，创作于2023年2月单元半群是半群的扩充，比半群具有更多的性质。设半群（S,*），若存在1∈S，有性质：1*1=1，任意x∈S，均有1*x=x*1=x，则{(S,*)}构成单元半群。定理：设S是有可列个元素的集合，（S，*）是单元半群，则在关于*的运算表中任何两行或两列均不相同。具体参见教材表6.2。第73页，课件共173页，创作于2023年2月定理：单元半群（S，×），若存在子系统（M,×），且单位元在M中，则（M，×）也是单元半群，称为子单元半群。定义：循环单元半群：有单位元的循环半群，同时也是可换单元半群。第74页，课件共173页，创作于2023年2月定理：一个可换单元半群，它的所有等幂元构成一个子单元半群。（67页例2）证明：设可换单元半群（M，×），M’={等幂元}（1）设a、b∈M,a2=a,b2=b，有(a×b)×(a×b)=a×b×a×b=a×a×b×b=a×b，故(M’,×)构成代数系统。（2）单位元是等幂元，故(M’,×)中有单位元。（3）M’是M的子集。故(M’,×)是子单元半群。第75页，课件共173页，创作于2023年2月§6.2群定义：群。一个二元代数系统<G,*>若满足：

1)G中运算“*”满足结合律；

2)G中存在关于运算“*”的单位元；

3)G中每个元素都有逆元。则称该代数系统<G,*>为一个群。或者定义：单元半群，每一个元素都有逆元。第76页，课件共173页，创作于2023年2月群的相关定义定义：如果<G,*>为一个群，运算“*”满足交换律，则称此群为可换群或Abel群；若|G|是有限的,则称此群为有限群；若|G|是无限的,则称此群为无限群；群的阶，|G|，G的基数。若G的子代数（H，*）也是群，则称为子群。第77页，课件共173页，创作于2023年2月例1（Z,+），（Q,+），（R,+）都是群，（Z+,+）,（N,+）不是群。设n是大于1的正整数，（Mn(R),+）是群,而（Mn(R),×）不是群。（P(B),）是群，其中为集合的对称差运算。（Zn,）是群,其中Zn={1,2,…,n-1},为模n运算。（R*,）不是群，是半群。其中R*为非零实数集合，运算定义为：任意x,yR*,x

y=y。

第78页，课件共173页，创作于2023年2月例2（Z,+）,（R,+）都是无限群;（Zn,）是n阶有限群；（{0},+）是平凡群，只有一个元素，既是单位元又是零元素。它们均为交换群.n(n>1)阶实可逆矩阵的集合关于矩阵乘法构成的群是非交换群，但对于加法构成交换群。第79页，课件共173页，创作于2023年2月练习题判断下列代数系统是否是群或Abel群：<Z,+>,<Q,+>,<R,+>,<C,+>，<Z,×>,<Q,×>,<R,×>,<C,×>，

<Q-{0},×>,<R-{0},×>,<C-{0},×>，<P(S),∪>,<P(S),∩>解：Abel群有<Z,+>,<Q,+>,<R,+>,<C,+>,<Q-{0},×>,<R-{0},×>,<C-{0},×>？第80页，课件共173页，创作于2023年2月练习题证明<n，＋n>是群。证明：前面已证<n，＋n>是单元半群，0为单位元，下面证明每个元素均有逆元。如果x＝0，显然0－1＝0，如果x≠0，则有n-x∈n，显然x＋n(n-x)=(n-x)+nx=0

所以x的逆元是n-x，因此x∈n，x有逆元。即<n，＋n>是群。第81页，课件共173页，创作于2023年2月群的性质群G中每个元素都是可消去的，即运算满足消去律；群G中除e外无其它幂等元；为什么？阶大于1的群G不可能有零元；为什么？群G中的任意两个元素a,b，都有

(a*b)-1＝b-1*a-1群G的运算表中任意一行(列)都没有两个相同的元素；第82页，课件共173页，创作于2023年2月群的性质一个群<G,*>的方程a*x=b和y*a=b中，在群内有唯一解。证明：首先方程a*x=b解是存在的，

x=a-1*b;

其次解是唯一的。若x1也是方程的解，有a*x=a*x1=b，由群的消去律知x=x1。

第83页，课件共173页，创作于2023年2月群的第二定义定义：若代数系统(G,*)满足下列条件，则称为群。（1）结合律。（2）方程a*x=b和y*a=b在G内有唯一解。第84页，课件共173页，创作于2023年2月证明：只要推出G有单位元和逆元即可。（1）a*x=a的解为右单位元1r,同理y*a=a的解为左单位元1l，由解的唯一性，1r=1l（2）由a*x=1和y*a=1分别得a的右、左逆元，又因满足结合律，左右逆元相等。第85页，课件共173页，创作于2023年2月群的同态、同构定义：设群(G，⊙)、(H，*)，若存在函数g：G→H，s.t.对每个a、b∈G，有g(a⊙b)=g(a)*g(b)，则称g是从(G，⊙)到(H，*)的群同态。若g是一一对应，则称为群同构。定理：设(G，⊙)与(H，*)群同态，函数g：G→H是同态函数，则有g(1G)=1H,g(a-1)=g(a)-1定理：设(G，⊙)是群，若(G，⊙)与(H，*)满同态或同构，则(H，*)也构成群。第86页，课件共173页，创作于2023年2月变换群变换的定义：集合上的变换是从S到S的一个一一对应函数，记为t：S→S。例：S={1,2}，则t1(1)=1,t1(2)=2是变换；t2(1)=2,t2(2)=1是变换；但t3(1)=1,t3(2)=1不是变换。S’={t1,t2}是变换的集合，称为变换集。第87页，课件共173页，创作于2023年2月S’中元素是变换，是一种函数，这是一种关系，而关系存在复合运算，故变换也存在复合运算，可称为复合变换。在变换集上定义一个变换的二元运算，可构成一个代数系统。这个二元运算可以取变换的复合运算。第88页，课件共173页，创作于2023年2月验证变换群（1）S上的变换是封闭的。（2）S上有恒等变换，故S’中单位元即是恒等变换：t1(x)=x。对任意t∈S’,t1*t=t*t1=t

（3）S上任意变换t均为一一对应，故其逆变换t-1也是S上的，t*t-1=t1。（4）复合变换满足结合律。因此（S’,*）构成群，称之为变换群。若S上的一些变换和复合运算构成一个群，也称为变换群。第89页，课件共173页，创作于2023年2月定义：集合S上的若干变换与复合运算若构成群，则称为变换群。定理：任一个群(G,*)均与一个变换群同构。证明：取a∈G,存在变换ta，对G中每个元素，ta(x)=x*a，这样G中每个元素都有一个变换与之对应，设G={a,b,c,d,…}，有ta,tb,tc,td,…,记为集合G’={ta,tb,tc,td,…}。

第90页，课件共173页，创作于2023年2月定义△为变换的复合运算。下面证明存在一一对应函数g:G→G’，满足同构方程。令g(a)=ta,可证g是函数，是单射，是满射，且有g(a*b)=ta*b=x*a*b=tb(x*a)=tb(ta(x))=ta△tb=g(a)△g(b)第91页，课件共173页，创作于2023年2月任意一个群均可在变换群中找到一个同构群，故对群的研究可归结为对变换群的研究。第92页，课件共173页，创作于2023年2月有限群设S为有限集，以|S|=3为例，有6个不同的变换，设S={1,2,3}，有可证这些变换对运算*构成一个群，称为对称群。记为S3={p1,p2,p3,p4,p5,p6},其中p1是单位元。p2、p3、p6的逆元还是她们自身。p5、p4互为逆元。第93页，课件共173页，创作于2023年2月定理：一个有限集上所有变换及复合运算构成一个群。例：S’={p1,p4,p5}构成一个群，也称变换群。定义：对称群、置换群

|S|=n,S上所有变换构成一个集合Sn,Sn及复合运算构成的群称为S的对称群。若S上有若干变换，所组成的集合P及*构成的群（P，*）称为S的置换群。第94页，课件共173页，创作于2023年2月定理：S的对称群（Sn,*）的阶为n!。证明：由排列组合的理论知识很容易可知。第95页，课件共173页，创作于2023年2月有限群的另一个定义定理：一个代数系统（G，*），若G为有限且满足结合律及消去律，则构成一个群。证明：用群的第二定义：结合律以及

a*x=b,y*a=b方程存在唯一解。设G={a1,a2,…,an}，取a∈G，作

G’={a*a1,a*a2,…,a*an}。第96页，课件共173页，创作于2023年2月

由G代数系统的封闭性，G’是G的子集，且由消去律，若i≠j，a*ai≠a*aj。故|G’|=n,因此G=G’。所以对b∈G或∈G’，必有ak∈G,s.t.b=a*ak，且ak唯一。同理y*a=b也存在唯一解。第97页，课件共173页，创作于2023年2月群表对有限群，可用一组合表将运算表示出来，称为群表。设|G|=1，群表是唯一的。设|G|=2，群表是唯一的。设|G|=3，群表是唯一的，且是对称的，因此3阶群是可换群。设|G|=4，群表不是唯一的，且均是对称的。第98页，课件共173页，创作于2023年2月群表|G|≤4|G|=1|G|=2|G|=3|G|=4这几个群表参见教材87页。第99页，课件共173页，创作于2023年2月从以上群表可看出一些特性：

由于单位元1存在，群表中总有一行（一列）与表头元素一样。由于消去律，群表中每行（每列）各不相同，且任两行（两列）对应元也不同。因此，群表每一行（列）是群中元素的一个排列，是G中元素的一个置换。若G是可换群，其可换性与群表的对称性是一致的。第100页，课件共173页，创作于2023年2月定理：每个有限群均与一个置换群同构。证明：由教材83页定理6.11，置换群中的每个置换是变换的特例，与复合运算构成一个群，且与对应的有限群同构。第101页，课件共173页，创作于2023年2月循环群定义：方幂设G是群，令a0=1,aj+1=aj*a,a-j=(a-1)j,

有性质akaj=ak+j，(ak)j=ak×j

定义：循环群若群G的每个元素均是它的某一个固定元素a的某次方幂，则称G是由a生成的循环群，a称为G的生成元素。第102页，课件共173页，创作于2023年2月定义：周期一个由a生成的循环群（G，*），若存在m，使得am=1的最小正整数m称为a的周期；若不存在这样的m，则称a的周期无限。第103页，课件共173页，创作于2023年2月循环群的构造对于任何群G，由G中元素a生成的子群是循环群。任何素数阶的群都是循环群。设G是循环群，若a是n阶元，则G={a0,a1,a2,…,an-1}，那么|G|=n称G为n阶循环群;若a是无限阶元，则G={a0,a±1,a±2,a±3…}称G为无限阶循环群。第104页，课件共173页，创作于2023年2月例：（Z，+）无限循环群，生成元：1，-1例：（4，+4）周期为4的循环群，生成元：[1]、[3]例：模为m的剩余类加群（Zm,+m）周期为m的循环群，生成元：[1]、[k]，其中k是与m互质的数。第105页，课件共173页，创作于2023年2月循环群定理定理：设由a生成的循环群G，则有（1）若a的周期无限，则G与整数加群（I，+）同构。（2）若a的周期有限，则G与剩余类加群（Zm，+m）同构。证明:(1)定义f:G→I，f(ak)=k(2)定义g:G→Zm，g(ak)=[k]

验证f、g函数均是一一对应，且满足同态方程。第106页，课件共173页，创作于2023年2月由上面定理说明，任何循环群都可以找到与之同构的群。无论是整数加群还是剩余类加群的性质特性都有深刻的研究。故循环群的问题已基本解决。第107页，课件共173页，创作于2023年2月G=<a>循环群的生成元定理：

(1)若G是无限循环群，则G的生成元是a和a−1

。(2)若G是n阶循环群，则G有ϕ(n)个生成元，当n=1时G=<e>的生成元为e；当n>1时,对于任何小于等于n且与n互质的正整数r，ar是G的生成元。

即G的生成元ar⇔(n,r)=1.第108页，课件共173页，创作于2023年2月证明思路：

(1)证明a−1是生成元。证明若存在生成元b，则b=a或a−1。

(2)只需证明(r,n)=1,则ar是生成元反之，若ar是生成元，则(r,n)=1.

第109页，课件共173页，创作于2023年2月证明（1）

(1)a是生成元，<a−1>⊆G,任取ai∈G,ai=(a−1)−i∈<a−1>⇒G⊆<a−1>。假设b为生成元，b=aj,a=bt,a=bt=(aj)t=ajt⇒ajt−1=e若jt−1≠0与a为无限阶元矛盾,因此j=t=1或j=t=−1。第110页，课件共173页，创作于2023年2月证明（2）详细的证明可以参加其它资料。如果同学有兴趣，查阅北京大学离散数学精品课程。第111页，课件共173页，创作于2023年2月例题例1.设G是12阶循环群，则小于或等于12且与12互质的数是1，5，7，11。设G=<a0(e),a1,…,a11>,则a1,a5,a7,a11是生成元。例2.设Z9是模9的整数加法群，则G的生成元是[1]，[2]，[4]，[5]，[7]，[8]。例3.设G=3Z={3k|k∈Z},G上的运算是普通加法，那么G只有两个生成元：3和-3。第112页，课件共173页，创作于2023年2月子群定义：一个群G如果它的子代数（H，*）也是一个群，则称H是G的一个子群。H是群则必须满足一些条件，下面给出充要条件。定理：一个群G，由它的一个子集H组成一个系统，该系统构成G的子群的充要条件是

a,b∈H,则a*b∈H；a∈H,则a-1∈H

证明：略第113页，课件共173页，创作于2023年2月有关子群的定理定理：设H是G的一个子群，则

1H=1G，aH-1=aG-1定理：设G是群，G的子集H所构成的子代数（H，*）是子群的充要条件是：若a,b∈H，则a*b-1∈H。第114页，课件共173页，创作于2023年2月有限子群的定理定理：设G是群，G的一个有限子集H所构成的（H，*）是一个群的充要条件是：若a,b∈H，则a*b∈H。证明：结合律满足说明构成代数系统；第115页，课件共173页，创作于2023年2月平凡子群及例子例1：任一个群（G，*）都有两个子群，群（G，*）和（{1}，*），这两个是任意群都有的子群，称之为平凡子群。例2：群（Z4，+4）中，

({[2]},+4)不是子群；({[1],[3]},+4)不是子群；({[0],[2]},+4)是子群。第116页，课件共173页，创作于2023年2月子群的例子例3：设群（G，*），任意a∈G,定义H={an},则H是G的子群。例4：定义Z2={2n|n是整数}，（Z2，+）是（Z，+）的子群。第117页，课件共173页，创作于2023年2月子群的陪集及Lagrange定理群的子群反映了群的结构和性质；陪集和拉格朗日定理反映了群与子群之间的关系。例：整数加群利用模3同余关系，将I划分成3个剩余类，分别是[0],[1],[2]。对于以上的同余关系R，也可表示成另一种方式。记H={3*i|i∈I}，由定理知，H是整数加群的子群。第118页，课件共173页，创作于2023年2月模3同余关系G上的模3同余关系，a,b∈G,a=b(mod3)等价于（a-b）/3余数为0。即故可由a-b∈H或a+b-1∈H来确定等价关系，进而对G进行分类。也就是说，G的剩余类是利用H来分类的。第119页，课件共173页，创作于2023年2月把上例推广至一般情况设H是G的一个子群，确定G上的一个关系R，（a,b）∈R当且仅当a*b-1∈H，这个关系称为G上的右陪集关系，可写为

a≡b(modH)定理：设G有一个子群H，则在G上的一个右陪集关系R，a≡b(modH)是等价关系。证明：略第120页，课件共173页，创作于2023年2月例：H={3i},验证I上m=3同余关系是右陪集关系。第121页，课件共173页，创作于2023年2月右陪集定义：右陪集

a.群G的子集H所确定的右陪集关系对G所划分的类称为子群H的右陪集，包含a的右陪集记以Ha。

b.H是群G的子群，称Ha={h*a|h∈H}为由a∈G确定的子群H的右集，a称为Ha的代表元素。第122页，课件共173页，创作于2023年2月分析右陪集的定义由定义知，右陪集是由一个等价关系（右陪集关系）所划分成的等价类。右陪集的元素构成。Ha={x|x∈G,x≡a(modH)}，(x,a)∈R,x与a有右陪集关系：x*a-1∈H，记h=x*a-1，得x=h*a，故Ha={h*a|h∈H}。因此包含a的右陪集是H内所有元素与a运算后所得结果组成的集合。第123页，课件共173页，创作于2023年2月左陪集定义：左陪集由G的一个子群可确定群G上的左陪集关系R，（a,b）∈R当且仅当b-1*a∈H，这个R是等价关系,称为左陪集关系。由R所划分的等价类称为左陪集。包含a的左陪集记以aH={ah|h∈H}。左陪集与右陪集是类似的，都是由陪集关系确定的等价类。第124页，课件共173页，创作于2023年2月等势定理：群G的一个子群H与其每个右陪集Ha等势。证明：定义f：H→Ha，f(h)=h*a。可以证明f是一一对应。因此H与Ha等势。第125页，课件共173页，创作于2023年2月相同的基数定理1：设H是群G的一个子群，Ha、Hb是任意两个右陪集（或左陪集），则或者Ha=Hb，或者Ha与Hb是分离的。证明：略。因为右陪集是等价类，那么按照等价关系的理论，由等价关系划分的等价类要么相等要么相互分离。第126页，课件共173页，创作于2023年2月分析设Ha与Hb相互分离，即是不同的等价类，那么它们均与H是等势的，因此Ha与Hb这两个不同的右陪集具有相同的基数。得出结论:(H,*)的所有右陪集具有相同的基数。第127页，课件共173页，创作于2023年2月拉格朗日定理定理：一个有限群G的阶一定被它的子群的阶所等分。分析：阶为n有限群的子群H阶为m,也是有限群，H的所有右陪集构成了G上的所有等价类，也就是构成了G上的一个划分。每个划分块即每个右陪集的基数是相同的，并且必为整数，与H的基数相同。即|aH|=|H|=m，这样由H确定的等价关系产生的划分块个数为n/m。第128页，课件共173页，创作于2023年2月拉格朗日定理推论设G的子群H的右陪集个数为k(称之为G内H的指数)，则有k=|G|/|H|推论1：任一个阶为素数的有限群没有真子群。推论2：任一个阶为n的有限群的循环子群，它的周期均能除尽n。推论3：任一个阶为n的有限群，可得到an=1第129页，课件共173页，创作于2023年2月证明1：若有真子群H阶为q，设G的阶为p,则p/q为整数，即q是p的真因子，与p为素数矛盾。证明2：设H为G的循环子群，|G|=n，设H={a0,a1,…,am-1}，|H|=m，则mk=n，即H的周期均能除尽n。证明3：任意G中元素a,有a0,a1,…,am,…∈G，由于G为有限群，故上述元素中必有相同元，设ai=aj(i≠j),有ai-j=1,记k=i-j，则ak=1,记S={a0,a1,…,ak-1}，则S为G的循环子群，由推论2，k能被n整除。n=mk，故an=1。第130页，课件共173页，创作于2023年2月循环子群定理2G=<a>是循环群，那么(1)G的子群也是循环群。(2)若G是无限阶，则G的子群除{e}外也是无限阶。(3)若G是n阶的，则G的子群的阶是n的因子，对于n的每个正因子d,在G中有且仅有一个d阶子群第131页，课件共173页，创作于2023年2月证明思路：(1)子群H中最小正方幂元am

为H的生成元。(2)若子群H=<am>有限，a≠e,则推出|a|有限。(3)H=<am>,|H|=|am|,(am)n=e.从而|am|是n的因子.(4)<an/d>是d阶子群，然后证明唯一性.第132页，课件共173页，创作于2023年2月证明

(1)设H是G=<a>的子群，不妨设H≠{e}.取H中最小正方幂元am,<am>⊆H.对于任意整数i,i=jm+r,r∈{0,1,…,m−1}ai∈H⇒ar=ai(am)−j∈H⇒r=0⇒ai∈<am>H⊆<am>第133页，课件共173页，创作于2023年2月(2)设H为G的子群，若H≠{e},H=<am>,m为H中最小正方幂元.假设|H|=t,则(am)t=e⇒amt=e，与a为无限阶元矛盾。(3)设G={e,a,…,an−1}，H={e}命题显然成立.若H≠{e},必有H=<am>,am为H中最小正方幂元.设|H|=|am|=d,(am)n=(an)m=e⇒|am||n⇒d|n。第134页，课件共173页，创作于2023年2月(4)设d|n，则,H是G的d阶子群.若H’=<am>也是G的d阶子群，其中am为最小正方幂元.则第135页，课件共173页，创作于2023年2月求下例的生成元和子群.例1。<Z12,⊕>,生成元为与12互质的数：1,5,7,11。12的正因子为1,2,3,4,6,12，子群：<0>,<1>,<2>,<3>,<4>,<6>

如<2>={0，2，4，6，8，10}，子群的阶为6.例2G=<a2>为12阶群，生成元为a2,a10,a14,a22

（对应1,5,7,11）

G的子群：<e>,<a2>,<a4>,<a6>,<a8>,<a12>第136页，课件共173页，创作于2023年2月例3<a>为无限循环群，生成元为a,a−1；子群为<ai>，i=0,1,2,…；例4G=<Z,+>，生成元：1,−1;

子群nZ,n=0,1,…,第137页，课件共173页，创作于2023年2月第138页，课件共173页，创作于2023年2月群、商群、同态群如同第五章的代数系统、商代数一样，我们将研究群与商群。要得到一个商群，必须构造一个同余关系，然后据这种同余关系建立群与商群，以及与它的一个同态群间的关系。（N，*）是（G，*）的正规子群，首先证明陪集关系是同余关系，其次定义商群（G/N，~）。最后构造一个正规子群—群的同态核。第139页，课件共173页，创作于2023年2月正规子群与同态定义：群G的一个子群N，若对任意a∈G，均有aN=Na，则称N是G的正规子群。此时N的左（右）陪集称为N的陪集。例1：可换群的任意子群都是正规子群。例2：对称群的子群。教材94页。只有当左右陪集相等时，才是正规子群。第140页，课件共173页，创作于2023年2月定理定理：群（G，·）的子群（N，·）是正规子群的充分必要条件是a·n·a-1∈N，a、a-1∈G，n∈N定理：群G的一个正规子群N所确定的左（右）陪集关系是一个同余关系。分析：右（左）陪集关系指的是群中两个元素满足a·b-1∈N（b-1·a∈N）,则a、b有关系，显然这是由群的子群来确定的。可验证这是同余关系。第141页，课件共173页，创作于2023年2月群与商群的关系由定理知群（G,·）的正规子群（N，·）所确定的陪集关系是同余关系；又由第五章自然同态理论，G/N是由同余关系定义的商集，定义运算*如下：任一aN、bN∈G/N,aN*bN=(a·b)N

称（G/N，*）为G关于正规子群N的商群。

第142页，课件共173页，创作于2023年2月分析上面定义出现的几个因素：（1）等价关系。G上有一个正规子群，由正规子群的陪集关系不仅是等价关系，还是同余关系。（2）根据同余关系，可以定义G的商集，因为同余关系与N有关，故记为G/N。（3）在商集上定义等价类（陪集）的运算，就得到了商代数，即商群。（4）由第五章最后一节内容知，群G与商群是满同态的。故存在g：GG/N，g是满同态映射。第143页，课件共173页，创作于2023年2月讨论一个特殊的正规子群上面已经定义了群的商群，但是等价关系（同余关系）如何定义？或者确定陪集关系的正规子群如何得到？这是目前需要考虑的问题。定义：设f是（G，·）到（G’，⊙）的群同态，则G的子集K={k|k∈G，f(k)=1G’}

叫同态f的核。第144页，课件共173页，创作于2023年2月验证K为正规子群定理：设K是从群（G，·）到（G’，⊙）的同态f的核，则（K，·）是（G，·）的正规子群。证明思路：（1）K是G的子群。若k1、k2∈K

，有k1·k2

-1∈K即可。（2）由定理6.24验证K是正规子群。若n∈K,a∈G’，有a·n·a-1∈K即可。第145页，课件共173页，创作于2023年2月定理：设f是群（G，·）到（G’，⊙）的满同态，K是f的核，则（G/K，*）与（G’，⊙）同构。证明思路:

（1）因为K是正规子群，由K所确定的陪集关系与第五章所确定的同余关系Ef一致。回顾Ef的定义。（2）根据第五章教材72页定理5.14，可以得到此定理。第146页，课件共173页，创作于2023年2月练习题1已知（G，*）是群，G={1，2，3，4，5，6}，*是对模7的乘法。（1）构造此群的运算表；（2）找出元素2的生成子群，并指出阶是多少。第147页，课件共173页，创作于2023年2月练习题2设G是群，非空集合H是G的子集，H中的元素都是有限阶的，运算在H中封闭，证明（H，*）是（G，*）的子群。第148页，课件共173页，创作于2023年2月第149页，课件共173页，创作于2023年2月第七章其他代数系统本章研究一些较复杂的代数系统：环，域，格，布尔代数等。我们关心的是代数系统中两个不同运算间的联系。这些代数系统在计算机科学的复杂领域中有重要应用。第150页，课件共173页，创作于2023年2月§7.1环、理想、整环和域定义：环设有代数系统（R，+，·），如满足下列条件：（1）（R，+）是可换群（2）（R，·）是半群（3）运算·对+满足分配律

a·（b+c)=a·b+a·c

（b+c)·a=b·a+c·a

则称（R，+，·）是环。第151页，课件共173页，创作于2023年2月定义：可换环；定义：含单位元的环；例：（Z，+，×）构成环；（Z4，+4，×4）构成环；第152页，课件共173页，创作于2023年2月有关环的说明在环中，（R，+）是群，有单位元，有逆元，有交换律，结合律，消去律；（R，·）只是半群，不一定有单位元。在环中，·对+满足分配律，反之不一定。环中有两种运算，一般称之为加、乘，+的单位元用0表示，·的单位元若存在，就用1表示。由环的定义条件3知，+的单位元必是对·的零元素，故（R，·）有零元素，若阶大于1，则不可能构成群。第153页，课件共173页，创作于2023年2月证明：设x,y,a∈R,e是（R，+）的单位元，有