离散数学第七章群与环.pptxVIP

第七章 群与环离散数学 陈志奎主编人民邮电出版社第一页，共四十五页。概述本章将讨论特殊的代数系统——群与环。群是具有一个二元运算的抽象代数。半群与群在形式语言、快速加法器设计、纠错码定制和自动机理论中都有卓有成效的应用。环是具有两个二元运算的代数系统，它和群以及半群有密切的联系。群最初是由Evariste Galois在1830年所提出的，它应用于满足某些性质的一个有限集的一系列置换中。Galois于1811年生于法国巴黎，直到12岁才进入巴黎一所公立中学学习，在此之前，他在家中有母亲进行教育。16岁时，完全沉浸在数学的学习之中，以至于忽略了其他课程的学习。两次参加Ecole Polytechnique的入学考试，但均未通过，最后进入Ecole Normale研究所进修。1830年法国革命期间，Galois因为指责其学校领导而被学校开除。此外Galois还曾因为政治活动二被捕入狱。在1832年5月30日，他在一场决斗中受伤，并在第二天去世，年仅20岁。在决斗前，Galois留了一封信给他的一位朋友，信中详细描述了他的研究成果。他的成果对于当时的人来书实在太超前了，因此直到1870年他的所有研究成果才完全展现在世人面前。第二页，共四十五页。PART 01PART 02PART 03PART 04PART 05内容安排半群群子群与群的陪集分解循环群与置换群环与域第三页，共四十五页。7.1 半群定义7.1 给定<S，⊙>，若⊙满足结合律，则称<S，⊙>为半群。可见，半群就是由集合及在此集合上的一个具有集合率的二元运算组成的代数系统。半群就是非空集合S以及一个定义在S上的可结合的二元运算⊙，将用<S，⊙>表示半群，或者当运算⊙很清楚时可以简记为S。此外还可以把a⊙b看成是a和b的积。如果⊙是一个可交换的二元运算，则称半群<S，⊙>是一个可交换半群。第四页，共四十五页。7.1 半群例 7.1 <Z,+>是一个可交换半群。因为加法满足结合率，同时加法是可交换的，所以<Z,+>是一个可交换半群。例 7.2 集合Z以及一般意义下的除法运算就不构成一个半群，因为除法运算不是可结合的。例 7.3 集合P（S），其中S是一个集合，加上并运算，它就构成一个交换半群。因为并运算满足结合律和交换律。第五页，共四十五页。7.1 半群定义7.2 ：给定<M，⊙>，若<M，⊙>是半群且⊙有幺元或⊙满足结合律且拥有幺元，则称<M，⊙>为独异点或含幺半群或拟群。例7.4 给定<N，+>和<N，*>，其中N是自然数集合，+和*为一般意义下的加法和乘法。易知<N，+>和<N，*>都是半群，而且还是独异点。因为0是+的幺元，1是*的幺元。例7.5 < ，+>，<N，+>，<Q，+>，<R，+>，<C，+>都是半群，+是一般意义下的加法，在这些半群中，除< ，+>外都是独异点。其余几个中含有幺元0，而< ，+>中无幺元存在。第六页，共四十五页。7.1 半群定义7.3 给定半群<S，⊙>和g∈S，以及自然数集合N，则g为<S，⊙>的生成元有：(?x)(x∈S→(?n)(n∈N∧x = ))。此时也说，元素g生成半群<S，⊙>，而且称该半群为循环半群，g为生成元。定义7.4 给定半群<S，⊙>及G?S，则G为<S，⊙>的生成集：(?a)(a∈S→a=⊙(G))∧min|G|这里⊙(G)表示用G中的元素经⊙的复合而生成的元素。类似地定义独异点<M，⊙，e>的生成集。第七页，共四十五页。7.1 半群例7.6： 给定<N，+>，其中N是自然数集合，+为一般意义下的加法，则<N，+>是无穷循环独异点，0是幺元，1是生成元。例7.7 令半群<S，*>，其中S={a，b，c，d}，*定义如表7.1，试证明生成集G={a，b}。*AbcdaDcbabBbbbcCcccdAbcd第八页，共四十五页。7.1 半群定义7.5 ：给定半群<S，⊙>及非空集合T?S，若T对⊙封闭，则称<T，⊙>为<S，⊙>的子半群。定义7.6 ：给定半群<S，⊙>以及任意的a∈S，则有<{a，a2，a3，…}，⊙>是<S，⊙>的循环子半群。例7.8 ：给定半群<S，⊙>以及任意的a∈S，证明<{a， ，?},⊙>是循环子半群。第九页，共四十五页。7.1 半群例7.9 给定两个半群<S，⊙>和<T，*>。称<S×T，?>为<S，⊙>和<T，*>的积半群，其中S×T为集合S与T的笛卡儿积，运算?定义如下：<s1，t1>?<s2，t2> =<s1⊙s2，t1*t2>，其中s1，s2∈S，t1，t2∈T。由于?是由⊙和*定义的，易知积半群是个半群。第十页，共四十五页。7.1 半群定理7.1 ：若半群<S，⊙>和半群<T，?>是可交换的，则<S×T，?>也是可交换的。定理7.2 ：给定半群<S，⊙>和半群<T，?>，且e1