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

第七章第七章 群与环群与环离散数学离散数学 陈志奎主编陈志奎主编人民邮电出版社人民邮电出版社n本章将讨论特殊的代数系统——群与环群是具有一个二元运算的抽象代数半群与群在形式语言、快速加法器设计、纠错码定制和自动机理论中都有卓有成效的应用环是具有两个二元运算的代数系统，它和群以及半群有密切的联系n群最初是由Evariste Galois在1830年所提出的，它应用于满足某些性质的一个有限集的一系列置换中Galois于1811年生于法国巴黎，直到12岁才进入巴黎一所公立中学学习，在此之前，他在家中有母亲进行教育16岁时，完全沉浸在数学的学习之中，以至于忽略了其他课程的学习两次参加Ecole Polytechnique的入学考试，但均未通过，最后进入Ecole Normale研究所进修n1830年法国革命期间，Galois因为指责其学校领导而被学校开除此外Galois还曾因为政治活动二被捕入狱在1832年5月30日，他在一场决斗中受伤，并在第二天去世，年仅20岁在决斗前，Galois留了一封信给他的一位朋友，信中详细描述了他的研究成果他的成果对于当时的人来书实在太超前了，因此直到1870年他的所有研究成果才完全展现在世人面前。

概述PART PART 0101PART PART 0202PART PART 0303半群群子群与群的陪集分解PART PART 0404环与域PART PART 0505循环群与置换群内容安排n定义定义7.1 给定，若⊙满足结合律，则称为半群半群可见，半群就是由集合及在此集合上的一个具有集合率的二元运算组成的代数系统半群就是非空集合S以及一个定义在S上的可结合的二元运算⊙，将用表示半群，或者当运算⊙很清楚时可以简记为S此外还可以把a⊙b看成是a和b的积如果⊙是一个可交换的二元运算，则称半群是一个可交换半群7.1￿半群n例例 7.1 是一个可交换半群因为加法满足结合率，同时加法是可交换的，所以是一个可交换半群n例例 7.2 集合Z以及一般意义下的除法运算就不构成一个半群，因为除法运算不是可结合的n例例 7.3 集合P（S），其中S是一个集合，加上并运算，它就构成一个交换半群因为并运算满足结合律和交换律7.1￿半群n定义定义7.2 ：给定，若是半群且⊙有幺元或⊙满足结合律且拥有幺元，则称为独异点独异点或含幺半群含幺半群或拟群拟群。

n例例7.4 给定和，其中N是自然数集合，+和*为一般意义下的加法和乘法易知和都是半群，而且还是独异点因为0是+的幺元，1是*的幺元n例例7.5 < ，+>，，，，都是半群，+是一般意义下的加法，在这些半群中，除< ，+>外都是独异点其余几个中含有幺元0，而< ，+>中无幺元存在7.1￿半群n定义定义7.3 给定半群和g∈S，以及自然数集合N，则g为的生成元有：(∀x)(x∈S→(∃n)(n∈N∧x = ))此时也说，元素g生成半群，而且称该半群为循环半群循环半群，，g为生成元n定义定义7.4 给定半群及G⊆S，则G为的生成集：(∀a)(a∈S→a=⊙(G))∧min|G|这里⊙(G)表示用G中的元素经⊙的复合而生成的元素类似地定义独异点的生成集生成集7.1￿半群n例例7.6：： 给定，其中N是自然数集合，+为一般意义下的加法，则是无穷循环独异点，0是幺元，1是生成元n例例7.7 令半群，其中S={a，b，c，d}，*定义如表7.1，试证明生成集G={a，b}。

7.1￿半群*AbcdaDcbabBbbbcCcccdAbcdn定义定义7.5 ：：给定半群及非空集合T⊆S，若T对⊙封闭，则称为的子半群子半群n定义定义7.6 ：给定半群以及任意的a∈S，则有<{a，a2，a3，…}，⊙>是的循环子半群循环子半群n例例7.8 ：：给定半群以及任意的a∈S，证明<{a， ，},⊙>是循环子半群7.1￿半群n例例7.9 给定两个半群和称为和的积积半群半群，其中S×T为集合S与T的笛卡儿积，运算⊗定义如下：⊗ =，其中s1，s2∈S，t1，t2∈T由于⊗是由⊙和*定义的，易知积半群是个半群7.1￿半群n定理定理7.1 ：：若半群和半群是可交换的，则也是可交换的n定理定理7.2 ：给定半群和半群，且e1 和 e2分别是他们的幺元，则积半群含有幺元 7.1￿半群n定理定理7.3：：给定半群和半群，且 和 分别是他们的零元，则积半群含有零元n定理定理7.4：：给定半群和半群，且s∈S的逆元 ，t∈T的逆元 ，则积半群中的逆元为7.1￿半群PART PART 0101PART PART 0202PART PART 0303半群群子群与群的陪集分解PART PART 0404环与域PART PART 0505循环群与置换群n定义定义7.7 给定代数系统Ｖ＝，若是独异点并且每个元素均存在逆元，或满足⊙是可结合的并且关于⊙存在幺元并且G中每个元素关于⊙是可逆的，则称是群群。

记为G群比独异点具有更强的条件n例例 7.11 给定和，其中Z和Q分别为整数集和有理数集，+和*分别是一般意义下的加法和乘法可知是群，0是幺元，每个元素i∈Z的逆元为-1；不是群，1是幺元，0无逆元但是群n在半群、独异点、群这些概念中，由于只含有一个二元运算，所以在不发生混淆的情况下，可以将算符省去例如将x*y写成xy在下面的讨论中，我们将常使用这种简略表示方法7.2￿群n例例 7.12 设G={e，a，b，c}，G上的运算由表7.2表示，不难验证G是一个群由表中可以看出G的运算具有以下特点：e为G中的单位元；G中的运算是可交换的；每个元素的逆元就是它自己；在a，b，c三个元素中，任意两个元素运算的结果都等于另一个元素这个群为Klein四元群，简称四元群四元群7.2￿群eabceeabcaaecbbbceaccbaen定义定义7.8 给定群G，若⊙是可交换的，则称G是可交换群可交换群或G是Abel群群n例例7.14 具有一般意义下的加法运算的所有整数的集合Z是一个Abel群，如果a∈Z，那么a的逆是他的负数-an例例7.15 在一般意义下的乘法运算 不是一个群，因为 中的元素2没有你元素。

然而，在给出的运算下该集合是一个幺半群n例例7.16 在一般意义下的乘法运算下，所有非零实数组成的集合构成一个群a≠0的逆是1/a7.2￿群n定义定义 7.9 若群G是有穷集，则称G是有限群有限群，否则称为无限群无限群群G的基数称为群G的阶含有单位元的群称为平凡群平凡群7.2￿群n例例7.17 是无穷群，，其中S={a，b，c}，⊙的运算表如表7.3可以验证，是群，a为幺元，b和c互为逆元；又因为|G|=3，故是3阶群7.2￿群⊙abcaabcbbcaccabn例例7.18 和是无限群，是有限群也是n阶群klein四元群是四阶群<{0}，+>是平凡群上述的所有群都是交换群，但是n阶（n≥2）实可逆矩阵的集合关于矩阵乘法构成的群是非交换群，因为矩阵乘法不满足交换律n定理定理 7.5 给定群，则7.2￿群n定义定义 7.10：： 集合的置换：令X是非空有限集合，从X到X的双射函数，称为集合X中的置换置换，并称|X|为置换的阶 集合上的所有置换（双射）与复合运算，构成的代数系统是一个群，称为对称群对称群。

由n个元素的集合而构成的所有n!个n阶置换的集合 与复合置换运算◇构成群< ，◇>，它便是n次n!阶对称群阶对称群 若 ，则称由Q和◇构成的群为置换群置换群7.2￿群n定义定义 7.11 集合X是无限的，令TX表示所有从集合X到X的变换的集合，具有下列性质：– – – – 构成群，在代数中称为变换群变换群置换群是变换群的特例7.2￿群n定义定义7.12 设p是集合X={ ， ，， }上的n阶置换，若p（ ）= ，p（ ）= ，，p（ ）= ，并且X中其余元素保持不变，则称p为X上的n阶轮换，记为（ ）若n=2，称p为X上的对换对换 由轮换的定义可知，轮换中任何元素均可排在首位，他们表示是同一个轮换，如（ ）=（ ）n例例7.20 令S={1，2，3，4，5}，S上的5阶置换p= 是S上的3阶轮换（1 2 4）。

7.2￿群PART PART 0101PART PART 0202PART PART 0303半群群子群与群的陪集分解PART PART 0404环与域PART PART 0505循环群与置换群子群就是群的子代数n定义定义 7.13 给定群G，H是G的子集，使得（1）G的单位元eH ，（2）如果a和bH ，那么abH ，（3）如果aH ，那么 H 则称H为G的一个子群，（1）和（3）说明H是G的子幺半群如果G是一个群，H是G的一个子群，那么H也是关于G中运算的一个群，因为G中的结合性质在H中也成立7.3.1￿子群的概念n定义定义7.14 给定群及非空集合HG，则是的子群（a）（b）（a，b∈Ha⊙b∈H）（a）（a∈H ∈H） 本定理表明是的子群的充要条件是H对于⊙封闭及H中每个元素存在逆元n定理定理7.6 设G为群，H是G的非空子集则H是G的子群当且仅当a，b属于H有a ∈H7.3.1￿子群的概念n给定一子群H和G内的某一元素a，则可定义出一个左陪集 aH={ah;h∈H}。

因为a为可逆的，由φ(h) = ah给出之映射φ : H → aH为一个双射更甚地，每一个G内的元素都包含在恰好一个H的左陪集中；其左陪集为对应于一等价关系的等价类，其等价关系a1 ~ a2当且仅当a1−1a2会在H内H的左陪集之数目称之为H在G内的“指数”，并标记为[G:H]n拉格朗日定理叙述著对一个有限群G和一个子群H而言，n其中o(G)和o(H)分别为G和H的目特别地是，每一个G的子群的目(和每一个G内元素的目)都必须为o(G)的因子 右陪集为相类比之定义：Ha = {ha : h∈H}其亦有对应于一适当之等价关系的等价类，且其个数亦会相等于[G:H]n若对于每个在G内的a，aH=Ha，则H称之为正规子群每一个指数2的子群皆为正规的：左陪集和右陪集都简单地为此一子群和其补集7.3.2￿群的陪集与拉格朗日定理n例例7.23 证明6阶群中必含有3阶元证明：设G是6阶群，由拉格朗日定理可知G中的元素只能是1阶，2阶3阶或6阶元 若G中含有6阶元，设这6阶元为a，则 是3阶元 若G中不含6阶元，下满证明G中必含有3阶元若不然，G中只含有1阶和2阶元，即a∈G，有 =e，可知G是Abel群，取G中的两个不同的2阶元a和b，令H={e，a，b，ab}易知H是G的子群，但|H|=4，|G|=6，与拉格朗日定理矛盾。

综上所述，6阶群中必含有3阶元7.3.2￿群的陪集与拉格朗日定理PART PART 0101PART PART 0202PART PART 0303半群群子群与群的陪集分解PART PART 0404环与域PART PART 0505循环群与置换群n定义定义7.15 设是群，若a∈G，对x∈G，k∈Z，有x= ，则称是循环群，记作G=，称a是群的生成元生成元n定义定义7.16 若存在aG使得G=，则称G是循环群循环群，称a为G的生成元循环群G=根据生成元a的阶可以分为两类：n阶循环群和无限循环群设G=是循环群，若a是n阶元，则那么|G|=n，称G为n阶循环群阶循环群若a是无限阶元，则这时称G为无限循环群无限循环群7.4￿循环群与置换群n定理定理 7.7 设G=是循环群若G是无限循环群，则G只有两个生成元，即a和 若G是n阶循环群，则G含有 个生成元，对于任何小于n且与n互素的自然数r， 是G的生成元n定理定理7.8 ①设G=是循环群，则G的子群仍是循环群②若G=是无限循环群，则G的子群除{e}以外都是无限循环群。

③若G=是n阶循环群，则对于n的每个正因子d，G恰好含有一个d阶子群7.4￿循环群与置换群n例例7.24 设 是整数加群， 是模12加群，求出 和 的所有子群7.4￿循环群与置换群n定义定义7.17：：设S={1,2，，n}，S上的任何双射函数 称为S上的n元置换n定义定义7.18：：设 是n元置换， 的复合 º 也是n元置换，称为 与 的乘机，记作 7.4￿循环群与置换群n定义定义7.19 一个置换群是一个群G，其元素是一个给定集M的置换，而其群作用是G中的置换（可以看作是从M到自身的双射）的复合；其关系经常写作(G,M)注意所有置换的群是对称群；置换群通常是指对称群的一个子群 n个元素的置换群记为 ；若M 是任意有限或无限集合，则所有M的置换组成的对称群通常写作Sym(M) 设S≠Ф，|S|＜+ ，S上的一个一一变换被称为置换当S上的某些置换关于乘法运算构成群是，就成它为置换群。