近世代数.ppt

《近世代数.ppt》由会员分享，可在线阅读，更多相关《近世代数.ppt（36页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、离散数学离散数学Discrete Mathematics主主 讲讲 教教 师师:王王 涛涛Email:第第5章章 代数结构代数结构关于代数结构关于代数结构“时至今日，数学家们还在忙于发展简单的计算方法，时至今日，数学家们还在忙于发展简单的计算方法，也就是在一切数学领域中的所谓算法。一旦我们有了算法，也就是在一切数学领域中的所谓算法。一旦我们有了算法，所有的其他事都留给了计算机。计算机所作的不再是数学所有的其他事都留给了计算机。计算机所作的不再是数学了，但为了使用计算机，需要数学和数学家。了，但为了使用计算机，需要数学和数学家。”H.Freudenthal“模型化是数学中的一个基本概念，它处于所

2、有的数学模型化是数学中的一个基本概念，它处于所有的数学应用之心脏，也处于某些最抽象的纯数学核心之中。应用之心脏，也处于某些最抽象的纯数学核心之中。”R.C.Buck数学之所以重要，其中心原因就在于它提供的数学系统数学之所以重要，其中心原因就在于它提供的数学系统丰富多彩；此外的原因是，数学给出了一个系统，以便于丰富多彩；此外的原因是，数学给出了一个系统，以便于使用这些模型对物理现实和技术领域提出问题、回答问题，使用这些模型对物理现实和技术领域提出问题、回答问题，并且也就探索了模型的行为。并且也就探索了模型的行为。R.C.Buck&.E.F.Buck近世代数近世代数绪绪 论论初等代数、线性代数、高

3、等代数都称初等代数、线性代数、高等代数都称为经典代数，研究的对象是代数方程为经典代数，研究的对象是代数方程和线性方程组。近世代数也称为抽象和线性方程组。近世代数也称为抽象代数，研究的对象是代数系统代数，研究的对象是代数系统（带有（带有封闭运算的集合）。封闭运算的集合）。由于近世代数在数学的其他分支、近代由于近世代数在数学的其他分支、近代物理、近代化学、计算机科学、数字通物理、近代化学、计算机科学、数字通信、系统工程等许多领域都有重要应用，信、系统工程等许多领域都有重要应用，因而它是现代科学技术的数学基础之一，因而它是现代科学技术的数学基础之一，是许多科技人员需要掌握的基本内容和是许多科技人员需

4、要掌握的基本内容和方法，因此近世代数也是数学专业的专方法，因此近世代数也是数学专业的专业基础课之一。业基础课之一。古典代数古典代数 代数系统代数系统(系统化：模型及其性质系统化：模型及其性质)；纯数学；纯数学 结合计算机应用。结合计算机应用。计算机科学：计算？计算机科学：计算？计算过程？计算过程？能行性计算模型：抽象与具体化。能行性计算模型：抽象与具体化。计算机科学中的代数方法：计算机科学中的代数方法：形式语言与自动机理论、可计算理论、语义学（模型论）形式语言与自动机理论、可计算理论、语义学（模型论）模型模型/语言。语言。集合代数、逻辑代数集合代数、逻辑代数密码学、数据表示理论、数字逻辑密码学

5、、数据表示理论、数字逻辑未来的计算机未来的计算机 其他：代数方程求解、物理、化学其他：代数方程求解、物理、化学 思维训练思维训练 有关科学家：有关科学家：Von Neumann、Abel、Galois、Hawking、吴文俊、吴文俊18281828年，他写的论文送交法国科年，他写的论文送交法国科年，他写的论文送交法国科年，他写的论文送交法国科学院审查，原稿被柯西弄丢了。学院审查，原稿被柯西弄丢了。学院审查，原稿被柯西弄丢了。学院审查，原稿被柯西弄丢了。18291829年年年年7 7月，他在巴黎高等工科月，他在巴黎高等工科月，他在巴黎高等工科月，他在巴黎高等工科大学的入学考试中再次失败。大学的入

6、学考试中再次失败。大学的入学考试中再次失败。大学的入学考试中再次失败。18301830年初，他向科学院提交了的年初，他向科学院提交了的年初，他向科学院提交了的年初，他向科学院提交了的论文论文论文论文,因科学院秘书傅立叶将其手因科学院秘书傅立叶将其手因科学院秘书傅立叶将其手因科学院秘书傅立叶将其手稿拿回家去审读稿拿回家去审读稿拿回家去审读稿拿回家去审读,不料在写出评不料在写出评不料在写出评不料在写出评审报告前去世了审报告前去世了审报告前去世了审报告前去世了,此文再也没有此文再也没有此文再也没有此文再也没有找到找到找到找到.18271827年阿贝尔回到挪年阿贝尔回到挪威。次年患结核病不幸威。次年患

7、结核病不幸去世，年仅去世，年仅2727岁。就在岁。就在他去世后两天后，克雷他去世后两天后，克雷尔来信通知他已被柏林尔来信通知他已被柏林大学任命为数学教授。大学任命为数学教授。但为时已晚，阿贝尔已但为时已晚，阿贝尔已无法前往接受这一职务无法前往接受这一职务了。了。知识点回顾知识点回顾【定义定义】运算：设运算：设A1,A2,An和和B是集合，若是集合，若 f：A1 A2 AnB则称则称f为为A1,A2,An到到B的的n元运算。元运算。【解释解释】1定义在集合之上的运算，要求集合必须是非空集合。定义在集合之上的运算，要求集合必须是非空集合。2若若f：A A AB，则称，则称f为为A上的上的n元运算；

8、元运算；3若对于任意若对于任意x1，x2，xn A，有，有f(x1，x2，xn)=y A，则称则称f为为A上的上的n元封闭运算元封闭运算(代数运算代数运算)。即。即f:A A AA4由定义知，运算结果是唯一的，其中由定义知，运算结果是唯一的，其中x1，x2，xn是参加运是参加运算的算的n个有顺序的对象，个有顺序的对象，y是运算结果，是运算结果，f 称为称为n元运算。元运算。封闭性：封闭性：A中任何元素都可参与运算，中任何元素都可参与运算，运算结果属于运算结果属于A。【例例1】设设 f:ZN，f(x)=|x|，则，则f是整数集是整数集合合Z上的取绝对值运算，上的取绝对值运算，f是是1元运算。运算

9、是封元运算。运算是封闭的。闭的。【例例2】设设 f:QQQ，f(x1，x2)=x1+x2，则则f是集合是集合Q上的加法运算，上的加法运算，f是是2元运算。运算元运算。运算是封闭的。是封闭的。【例例3】设设 f:QQQQ，f(x1，x2，x3)=x1+x2+x3，则，则f是集合是集合Q上的上的3元封闭运算。元封闭运算。n元运算的表示元运算的表示u运算符号的选取运算符号的选取1）在不同场称呼不同；）在不同场称呼不同；2）未加说明人们习惯的运算符号含义最好不改变；）未加说明人们习惯的运算符号含义最好不改变；3）运算符号可以自己规定。）运算符号可以自己规定。4）在本系统中运算符号含义明确。）在本系统中

10、运算符号含义明确。u运算符号的位置运算符号的位置1）放在最前面（或顶置、肩置）放在最前面（或顶置、肩置）2）放在中间）放在中间3）放在最后面）放在最后面u运算表运算表运算的性质运算的性质对合性对合性 设设*是是A上的上的1元代数运算，元代数运算，若对于任意的若对于任意的x A,均有均有*(*x)=x,则称则称*具有对合性，或称具有对合性，或称*满足对合律。满足对合律。集合的非运算；数集的取反运算，矩阵的逆运算集合的非运算；数集的取反运算，矩阵的逆运算及转置运算均具有对合性。及转置运算均具有对合性。实数集上的取相反数运算？实数集上的取相反数运算？幂等性（幂等律）幂等性（幂等律）设设*是是A上的上

11、的2元代数运算，元代数运算，若对于若对于x A，有，有x*x=x则称则称x为关于为关于*运算的幂等元；若对于运算的幂等元；若对于A中每个元素中每个元素x对对于于*都是幂等元，则称都是幂等元，则称*运算具有幂等性或称运算具有幂等性或称*满足幂满足幂等律（等幂律）。等律（等幂律）。集合上的交、并运算具有幂等性集合上的交、并运算具有幂等性.交换性（交换律）交换性（交换律）设设*是是A上的上的2元代数运算，元代数运算，若对于任意的若对于任意的x,y A，均均有有 x*y=y*x，则称，则称*满足交换律。满足交换律。结合性（结合律）结合性（结合律）设设*是是A 上的上的2元代数运算，若对于任意的元代数运

12、算，若对于任意的x，y，z A,均有均有(x*y)*z=x*(y*z)，则称，则称*运算具有结合性，或称运算具有结合性，或称*运算满足结合律。运算满足结合律。哪些运算符合上述性质？哪些运算符合上述性质？消去性消去性.设设*是是A上的上的2元代数运算，元代数运算，若若A关于关于*运算有零元则记运算有零元则记为为 ,如果对于任意的如果对于任意的x,y,z A，只要只要x,那么下列那么下列条件均成立：条件均成立：x*y=x*z y=z；y*x=z*x y=z；则称则称*具有消去性，具有消去性，或称或称*满足消去律。满足消去律。分配性（分配律）分配性（分配律）设设*和和是集合是集合A上的两个上的两个2

13、元代数运算，若对于任意元代数运算，若对于任意x,y,z A,有有 x*(yz)=x*yx*z；(yz)*x=y*xz*x成立，则称成立，则称*对于对于是可分配的（分配律）。是可分配的（分配律）。吸收性吸收性 设设*和和是集合是集合A上的两个上的两个2元代数运算元代数运算,若对于任意若对于任意x,y A,有有 x*(xy)=x；(yx)*x=x成立，则称成立，则称*对于对于是可吸收的（吸收律）。是可吸收的（吸收律）。德摩根律德摩根律 设设是集合是集合A上的上的1元代数运算元代数运算,*和和是是A上的两个上的两个2元元代数运算代数运算,若对于任意若对于任意x,y A，均有下面两个等式成均有下面两个

14、等式成立立:（x*y）=(x)(y)和和（xy）=(x)*(y)则称这三种运算满足德摩根律。则称这三种运算满足德摩根律。特异元素特异元素单位元素单位元素设设*是是A上的上的2元代数运算元代数运算,若存在若存在e A,对于任意的对于任意的x A,下列条件均成立：下列条件均成立：e*x=x；x*e=x.则称则称e为集为集合合A关于关于*运算的单位元素或幺元素。运算的单位元素或幺元素。零元素零元素 设设*是是A上的上的2元代数运算元代数运算,若存在若存在A,对于任意的对于任意的x A,下列条件均成立：下列条件均成立：*x=；x*=.则称则称 为为集合集合A关于关于*运算的零元素。运算的零元素。逆元素

15、逆元素设设*是是A上的上的2元代数运算且有单位元素元代数运算且有单位元素e，若对于，若对于x A,存在存在y A，使得下列条件均成立，使得下列条件均成立:x*y=e;y*x=e.则称则称y为为x的关于的关于*的逆元素。的逆元素。举例说明哪些运算具有幂等元、单位元、零元素举例说明哪些运算具有幂等元、单位元、零元素和逆元素。和逆元素。5.1 代数结构简介代数结构简介1.代数结构的定义代数结构的定义Def 设设A是非空集合是非空集合,f1,f2,fk(k 1)是是A上上的代数的代数(封闭封闭)运算运算,则集合则集合A连同其上的代数连同其上的代数运算称为代数结构运算称为代数结构(algebra str

16、ucture)或代数或代数系统系统(algebra system)或简称代数或简称代数(algebra),记为记为(A,f1,f2,fk),在已知运算的情况下可在已知运算的情况下可简记为简记为A.对于代数结构的理解对于代数结构的理解,需注意以下几点：需注意以下几点：(1)A非空非空;(2)代数运算代数运算;(3)(k+1)-元组元组(A,f1,f2,fk);(4)运算的元数可以相同运算的元数可以相同.例例5-1:(1)(R,+).(2)(R,+,).(3)有限代数与无限代数有限代数与无限代数?2.两种最简单的代数结构两种最简单的代数结构:半群及独异点半群及独异点Def 设设*是非空集合是非空集

17、合S上的上的2元代数运算元代数运算,若若*满足结合律满足结合律,即对于任意即对于任意x,y,z S,有有(x*y)*z=x*(y*z),则则(S,*)称是半群称是半群(semigroup).例例 实数集合实数集合R关于其上的乘法运算关于其上的乘法运算“”作作成一个半群成一个半群(R,.).例例 设设 是若干个字母组成的集合是若干个字母组成的集合,称为字母表称为字母表,由由 中有限个字母组成的序列称为中有限个字母组成的序列称为 上的串上的串,不不含任何字母的串称为空串含任何字母的串称为空串,记为记为.令令*是所有是所有 上的串组成的集合上的串组成的集合,其上的运算其上的运算为为 *上的上的连接运

18、算连接运算:很容易验证很容易验证:(*,)是半群是半群.实际上实际上,上的所有非空串组成的集合上的所有非空串组成的集合+,关于关于其上的串的连接运算也构成一个半群其上的串的连接运算也构成一个半群(+,).Def 设设*是非空集合是非空集合M上的上的2元代数运算元代数运算,若若*满满足结合律且足结合律且M关于关于*有幺元有幺元e,即对于任意即对于任意x M,有有e*x=x*e=x,则称则称(M,*,e)为独异为独异点点.例例5-4 在例在例5-3中中,(*,)是独异点是独异点,而而(+,)不是不是.lRemarks(1)在在(*,)中的中的 称为代数常数称为代数常数.代数结构代数结构中的代数常数

19、可以不止一个中的代数常数可以不止一个,例如在后面将学例如在后面将学习的布尔代数就有习的布尔代数就有2个代数常数个代数常数.当然也可以当然也可以没有代数常数没有代数常数.(2)(*,)是半群是半群,(*,)是独异点是独异点,它们它们是两个不同的代数结构是两个不同的代数结构.正因为这样正因为这样,一个最一个最好的处理方式是将代数常数看作是好的处理方式是将代数常数看作是0元运算元运算,(*,)有有1个个0元运算元运算(及及1个二元运算个二元运算),布布尔代数有尔代数有2个个0元运算元运算.lTheorem 设设(S,*)是有限半群是有限半群,则则(S,*)中存中存在幂等元素在幂等元素.5.2 群的定

20、义及性质群的定义及性质 1.群的定义群的定义Def 设设G是非空集合是非空集合,是是G上的代数运算上的代数运算,若下列若下列3个条件成立个条件成立,则称为群则称为群(group).(1)满足结合律满足结合律;(2)G关于关于 有单位元有单位元,通常记为通常记为e;(3)G中每一个元素在中每一个元素在G中都有逆元中都有逆元.l下面是群的例子下面是群的例子.l例例 验证验证:整数集合整数集合Z关于数的加法运算关于数的加法运算+构构成群成群.lSolution 因为因为Z关于关于+是封闭的且满足是封闭的且满足l(1)+运算满足结合律运算满足结合律;l(2)Z关于关于+有单位元有单位元0:x+0=0+

21、x=x;l(3)Z中每一个元素中每一个元素x Z,都有逆元都有逆元-x Z:x+(-x)=(-x)+x=0.l所以所以,(Z,+)是群是群.l2.群的性质Theorem 设是(G,)群,则满足消去律.Theorem 设设(G,)是群是群,对于任意对于任意a,b G,方方程程a x=b(x a=b或或)在在G中中有有唯一唯一解解a-1 b(b a-1).(1)存在性存在性;(2)惟一性惟一性.利用利用“群中任意元素均存在逆元群中任意元素均存在逆元”.5.4 Abel群与循环群群与循环群Abel群与循环群是两类较简单的群群与循环群是两类较简单的群.l1.Abel群群Def 设设(G,)是群，若其运

22、算是群，若其运算 是可交换的，则称是可交换的，则称(G,)为交换群为交换群(commutative group)或或Abel群群(Abelian group).跟跟E.Galois一样，挪威数学家一样，挪威数学家N.H.Abel在群的在群的研究方面也做出过惊人的成就研究方面也做出过惊人的成就.例例设设证明证明:G关于矩阵的乘法运算关于矩阵的乘法运算 构成一个构成一个Abel群群.2.循环群循环群循环群是最简单的群循环群是最简单的群.(1)群中元素的整数方幂群中元素的整数方幂an(n Z)Def lRemark 方幂运算是对群中的运算来说的方幂运算是对群中的运算来说的.如在群如在群(Z,+)中中

23、,有有:lTheorem m,n Z.(1)(2)(3)(4)(5)l(2)群元素的阶群元素的阶lDef 设设(G,)是群是群,e是其单位元素是其单位元素,a G,使使ak=e成立的最小的正整数成立的最小的正整数k称为元素的阶或称为元素的阶或周期周期,记为记为|a|=k,这时元素这时元素a称为称为k阶元阶元.若对若对于任意正整数于任意正整数k,都有都有ak e,则称则称a为无限阶元为无限阶元.显然显然,|e|=1.例例 求求中各元素的阶中各元素的阶.lHint 除单位元外除单位元外,阶均为阶均为2.l(3)循环群循环群lDef 设设(G,)是群是群,a G,若若G中任意元素均中任意元素均为元素

24、为元素a的某整数方幂的某整数方幂,即即 则称则称(G,)为循环群为循环群,称称a为为G的生成元的生成元.例例 证明证明:(Zn,+n)是是n阶循环群阶循环群,并找出并找出6阶循环阶循环群群(Z6,+6)的所有生成元的所有生成元.l对于任意正整数对于任意正整数n,Euler函数函数(n)表示小于表示小于等于等于n且与且与n互素的正整数个数互素的正整数个数,例如例如(1)=1,(2)=1,(3)=2,(4)=2,(5)=4,(6)=2,(7)=6等等,可以证明可以证明:n阶循环群阶循环群的生成元个数为的生成元个数为(n).lTheorem 设设a是循环群是循环群(G,)的生成元的生成元,若若|a|=k,则则|G|=k且且lHint n Z,an?5.5 子群、群的陪集分解及正规子群子群、群的陪集分解及正规子群l1.子群子群l根据根据5.1节节,可以考虑群的子代数可以考虑群的子代数子群子群.lDef 设设(G,)是群是群,H G,若若H关于群关于群G的的运算构成群运算构成群(H,),则称则称(H,)是是(G,)的子群的子群(subgroup),记为记为(H,)(G,),可简记为可简记为H G.l根据定义容易验证根据定义容易验证(Z,+)(R,+).l对于任意群对于任意群(G,),设设e为其单位元为其单位元,则则e和和G都是都是G的子群的子群,称为称为G的平凡子群的平凡子群.