《离散数学第七章群与环.ppt》由会员分享，可在线阅读，更多相关《离散数学第七章群与环.ppt（45页珍藏版）》请在三一办公上搜索。
1、,第七章 群与环,离散数学 陈志奎主编人民邮电出版社,本章将讨论特殊的代数系统群与环。群是具有一个二元运算的抽象代数。半群与群在形式语言、快速加法器设计、纠错码定制和自动机理论中都有卓有成效的应用。环是具有两个二元运算的代数系统，它和群以及半群有密切的联系。群最初是由Evariste Galois在1830年所提出的，它应用于满足某些性质的一个有限集的一系列置换中。Galois于1811年生于法国巴黎，直到12岁才进入巴黎一所公立中学学习，在此之前，他在家中有母亲进行教育。16岁时，完全沉浸在数学的学习之中，以至于忽略了其他课程的学习。两次参加Ecole Polytechnique的入学考试，
2、但均未通过，最后进入Ecole Normale研究所进修。1830年法国革命期间，Galois因为指责其学校领导而被学校开除。此外Galois还曾因为政治活动二被捕入狱。在1832年5月30日，他在一场决斗中受伤，并在第二天去世，年仅20岁。在决斗前，Galois留了一封信给他的一位朋友，信中详细描述了他的研究成果。他的成果对于当时的人来书实在太超前了，因此直到1870年他的所有研究成果才完全展现在世人面前。,概述,半群,群,子群与群的陪集分解,环与域,循环群与置换群,内容安排,定义7.1 给定，若满足结合律，则称为半群。可见，半群就是由集合及在此集合上的一个具有集合率的二元运算组成的代数系统
3、。半群就是非空集合S以及一个定义在S上的可结合的二元运算，将用表示半群，或者当运算很清楚时可以简记为S。此外还可以把ab看成是a和b的积。如果是一个可交换的二元运算，则称半群是一个可交换半群。,7.1 半群,例 7.1 是一个可交换半群。因为加法满足结合率，同时加法是可交换的，所以是一个可交换半群。例 7.2 集合Z以及一般意义下的除法运算就不构成一个半群，因为除法运算不是可结合的。例 7.3 集合P（S），其中S是一个集合，加上并运算，它就构成一个交换半群。因为并运算满足结合律和交换律。,7.1 半群,定义7.2：给定，若是半群且有幺元或满足结合律且拥有幺元，则称为独异点或含幺半群或拟群。例
4、7.4 给定和，其中N是自然数集合，+和*为一般意义下的加法和乘法。易知和都是半群，而且还是独异点。因为0是+的幺元，1是*的幺元。例7.5，都是半群，+是一般意义下的加法，在这些半群中，除外都是独异点。其余几个中含有幺元0，而中无幺元存在。,7.1 半群,定义7.3 给定半群和gS，以及自然数集合N，则g为的生成元有：(x)(xS(n)(nNx=)。此时也说，元素g生成半群，而且称该半群为循环半群，g为生成元。定义7.4 给定半群及GS，则G为的生成集：(a)(aSa=(G)min|G|这里(G)表示用G中的元素经的复合而生成的元素。类似地定义独异点的生成集。,7.1 半群,例7.6：给定，
5、其中N是自然数集合，+为一般意义下的加法，则是无穷循环独异点，0是幺元，1是生成元。例7.7 令半群，其中S=a，b，c，d，*定义如表7.1，试证明生成集G=a，b。,7.1 半群,定义7.5：给定半群及非空集合TS，若T对封闭，则称为的子半群。定义7.6：给定半群以及任意的aS，则有是的循环子半群。例7.8：给定半群以及任意的aS，证明是循环子半群。,7.1 半群,例7.9 给定两个半群和。称为和的积半群，其中ST为集合S与T的笛卡儿积，运算定义如下：=，其中s1，s2S，t1，t2T。由于是由和*定义的，易知积半群是个半群。,7.1 半群,定理7.1：若半群和半群是可交换的，则也是可交换
6、的。定理7.2：给定半群和半群，且e1 和 e2分别是他们的幺元，则积半群含有幺元。,7.1 半群,定理7.3：给定半群和半群，且 和 分别是他们的零元，则积半群含有零元定理7.4：给定半群和半群，且sS的逆元，tT的逆元，则积半群中的逆元为,7.1 半群,半群,群,子群与群的陪集分解,环与域,循环群与置换群,定义7.7 给定代数系统，若是独异点并且每个元素均存在逆元，或满足是可结合的并且关于存在幺元并且G中每个元素关于是可逆的，则称是群。记为G。群比独异点具有更强的条件。例 7.11 给定和，其中Z和Q分别为整数集和有理数集，+和*分别是一般意义下的加法和乘法。可知是群，0是幺元，每个元素i
7、Z的逆元为-1；不是群，1是幺元，0无逆元。但是群。在半群、独异点、群这些概念中，由于只含有一个二元运算，所以在不发生混淆的情况下，可以将算符省去。例如将x*y写成xy。在下面的讨论中，我们将常使用这种简略表示方法。,7.2 群,例 7.12 设G=e，a，b，c，G上的运算由表7.2表示，不难验证G是一个群。由表中可以看出G的运算具有以下特点：e为G中的单位元；G中的运算是可交换的；每个元素的逆元就是它自己；在a，b，c三个元素中，任意两个元素运算的结果都等于另一个元素。这个群为Klein四元群，简称四元群。,7.2 群,定义7.8 给定群G，若是可交换的，则称G是可交换群或G是Abel群。
8、例7.14 具有一般意义下的加法运算的所有整数的集合Z是一个Abel群，如果aZ，那么a的逆是他的负数-a。例7.15 在一般意义下的乘法运算 不是一个群，因为 中的元素2没有你元素。然而，在给出的运算下该集合是一个幺半群。例7.16 在一般意义下的乘法运算下，所有非零实数组成的集合构成一个群。a0的逆是1/a。,7.2 群,定义 7.9 若群G是有穷集，则称G是有限群，否则称为无限群。群G的基数称为群G的阶。含有单位元的群称为平凡群。,7.2 群,例7.17 是无穷群，其中S=a，b，c，的运算表如表7.3可以验证，是群，a为幺元，b和c互为逆元；又因为|G|=3，故是3阶群。,7.2 群,
9、例7.18 和是无限群，是有限群也是n阶群。klein四元群是四阶群。是平凡群。上述的所有群都是交换群，但是n阶（n2）实可逆矩阵的集合关于矩阵乘法构成的群是非交换群，因为矩阵乘法不满足交换律。定理 7.5 给定群，则,7.2 群,定义 7.10：集合的置换：令X是非空有限集合，从X到X的双射函数，称为集合X中的置换，并称|X|为置换的阶。集合上的所有置换（双射）与复合运算，构成的代数系统是一个群，称为对称群。由n个元素的集合而构成的所有n!个n阶置换的集合 与复合置换运算构成群，它便是n次n!阶对称群。若，则称由Q和构成的群为置换群。,7.2 群,定义 7.11 集合X是无限的，令TX表示所
10、有从集合X到X的变换的集合，具有下列性质：构成群，在代数中称为变换群。置换群是变换群的特例。,7.2 群,定义7.12 设p是集合X=，上的n阶置换，若p（）=，p（）=，p（）=，并且X中其余元素保持不变，则称p为X上的n阶轮换，记为（）若n=2，称p为X上的对换。由轮换的定义可知，轮换中任何元素均可排在首位，他们表示是同一个轮换，如（）=（）。例7.20 令S=1，2，3，4，5，S上的5阶置换p=是S上的3阶轮换（1 2 4）。,7.2 群,半群,群,子群与群的陪集分解,环与域,循环群与置换群,子群就是群的子代数。定义 7.13 给定群G，H是G的子集，使得（1）G的单位元eH，（2）如
11、果a和bH，那么abH，（3）如果aH，那么 H。则称H为G的一个子群，（1）和（3）说明H是G的子幺半群。如果G是一个群，H是G的一个子群，那么H也是关于G中运算的一个群，因为G中的结合性质在H中也成立。,7.3.1 子群的概念,定义7.14 给定群及非空集合HG，则是的子群（a）（b）（a，bHabH）（a）（aH H）。本定理表明是的子群的充要条件是H对于封闭及H中每个元素存在逆元。定理7.6 设G为群，H是G的非空子集。则H是G的子群当且仅当a，b属于H有a H。,7.3.1 子群的概念,给定一子群H和G内的某一元素a，则可定义出一个左陪集 aH=ah;hH。因为a为可逆的，由(h)=
12、ah给出之映射:H aH为一个双射。更甚地，每一个G内的元素都包含在恰好一个H的左陪集中；其左陪集为对应于一等价关系的等价类，其等价关系a1 a2当且仅当a11a2会在H内。H的左陪集之数目称之为H在G内的“指数”，并标记为G:H。拉格朗日定理叙述著对一个有限群G和一个子群H而言，其中o(G)和o(H)分别为G和H的目。特别地是，每一个G的子群的目(和每一个G内元素的目)都必须为o(G)的因子。右陪集为相类比之定义：Ha=ha:hH。其亦有对应于一适当之等价关系的等价类，且其个数亦会相等于G:H。若对于每个在G内的a，aH=Ha，则H称之为正规子群。每一个指数2的子群皆为正规的：左陪集和右陪集
13、都简单地为此一子群和其补集。,7.3.2 群的陪集与拉格朗日定理,例7.23 证明6阶群中必含有3阶元。证明：设G是6阶群，由拉格朗日定理可知G中的元素只能是1阶，2阶3阶或6阶元。若G中含有6阶元，设这6阶元为a，则 是3阶元。若G中不含6阶元，下满证明G中必含有3阶元。若不然，G中只含有1阶和2阶元，即aG，有=e，可知G是Abel群，取G中的两个不同的2阶元a和b，令H=e，a，b，ab易知H是G的子群，但|H|=4，|G|=6，与拉格朗日定理矛盾。综上所述，6阶群中必含有3阶元。,7.3.2 群的陪集与拉格朗日定理,半群,群,子群与群的陪集分解,环与域,循环群与置换群,定义7.15 设
14、是群，若aG，对xG，kZ，有x=，则称是循环群，记作G=，称a是群的生成元。定义7.16 若存在aG使得G=，则称G是循环群，称a为G的生成元。循环群G=根据生成元a的阶可以分为两类：n阶循环群和无限循环群。设G=是循环群，若a是n阶元，则那么|G|=n，称G为n阶循环群。若a是无限阶元，则这时称G为无限循环群。,7.4 循环群与置换群,定理 7.7 设G=是循环群若G是无限循环群，则G只有两个生成元，即a和。若G是n阶循环群，则G含有 个生成元，对于任何小于n且与n互素的自然数r，是G的生成元。定理7.8 设G=是循环群，则G的子群仍是循环群。若G=是无限循环群，则G的子群除e以外都是无限
15、循环群。若G=是n阶循环群，则对于n的每个正因子d，G恰好含有一个d阶子群。,7.4 循环群与置换群,例7.24 设 是整数加群，是模12加群，求出 和 的所有子群。,7.4 循环群与置换群,定义7.17：设S=1,2，n，S上的任何双射函数 称为S上的n元置换。定义7.18：设 是n元置换，的复合 也是n元置换，称为 与 的乘机，记作。,7.4 循环群与置换群,定义7.19 一个置换群是一个群G，其元素是一个给定集M的置换，而其群作用是G中的置换（可以看作是从M到自身的双射）的复合；其关系经常写作(G,M)。注意所有置换的群是对称群；置换群通常是指对称群的一个子群。n个元素的置换群记为；若M
16、 是任意有限或无限集合，则所有M的置换组成的对称群通常写作Sym(M)。设S，|S|+，S上的一个一一变换被称为置换。当S上的某些置换关于乘法运算构成群是，就成它为置换群。若|S|=n，设1,2，n，其置换全体组成的集合一般表示为Sn；经过n次恒等变换的群称为n次对称群。,7.4 循环群与置换群,置换群到被置换的元素的应用称为群作用；它在对称性和组合论以及数学的其他很多分支中有应用。,半群,群,子群与群的陪集分解,环与域,循环群与置换群,内容安排,在本章前面的内容中介绍了半群、独异点和群，他们都是具有一个运算的代数结构，这对于研究简单的整数和实数系统来说都是不够的。因此，必须研究具有两个运算的
17、代数结构环和域。环和域均建立在Abel群的基础之上，在上一节中已经有过介绍。,7.5 环与域,定义7.21 设是代数系统，+和是二元运算，如果满足下列条件：（1）构成交换群；（2）构成半群；（3）运算关于+运算适合分配律，则称是一个环。为了区分环中的两个运算，通常称+为环中的加法，为环中的乘法，把称为加法群，称为乘法半群。而且还规定，运算的顺序是先计算乘法再算加法。常常又因为环中的乘法半群满足于不同的乘法的各种性质，将环冠以不同的名称。,7.5 环与域,定义7.22 给定环，若是可交换半群，则称是可交换环；若是独异点，则称是含幺环；若a，bR，ab=0a=0b=0，则称R是无零因子环；若满足等
18、幂律，则称是布尔环；若R既是交换环、含幺环，又是无零因子环，则称R是整环。,7.5 环与域,例7.25，和等都是环。而且除了之外都是拥有加法零元（数0）和乘法幺元（数1）的和交换含幺环。这里Z，R，Q，E，C分别为整数集合，实数集合，有理数集合，偶数集合和复数集合。而+和*分别为普通意义下的加法和乘法。例7.26 给定，其中P（S）是结合S的幂集，+和*分别为普通意义下的加法和乘法：A+B=（A-B）（B-A）A*B=AB 这里A,BP（S），和是集合的交与并运算。不难验证，是环，并且拥有加法幺元和乘法幺元S的可交换幺换。通常称该环为子集环。,7.5 环与域,定理7.9 设是环，则（1）aR，
19、a0=0a=0（2）a，bR，（-a）b=a（-b）=-ab（3）a，b，cR，a（b-c）=ab-ac，（b-c）a=ab-ca,7.5 环与域,例7.28 在环中计算(a+b)3,(ab)2 解(a+b)3=(a+b)(a+b)(a+b)=(a2+ba+ab+b2)(a+b)=a3+ba2+aba+b2a+a2b+bab+ab2+b3(ab)2=(ab)(ab)=a2baab+b2,7.5 环与域,域的概念是在环的概念之上的延伸。定义7.23 设R是整环，且R中至少含有两个元素。若a=R-0，都有 R，则称R是域。定理7.10 给定可交换环，若为群，此时称为域。,7.5 环与域,例7.29
20、 和都是域，而不是域，其中R，Q和Z分别为实数集合，有理数集合和整数集合，+和*为一般意义下的加法运算和乘法运算。定理7.11 为域（a）（b）（a，bSa*b=0（a=0b=0）,7.5 环与域,定理7.12 给定环，则是域n为素数。例7.30 整数环Z，有理数环Q，实数环R,复数环C都是交换环、含幺环、无零因子环和整环，其中有理数环Q、实数环R、复数环C是域。包含有限个元素的域被称为有限域。它在密码学中有着重要的应用。,7.5 环与域,实例：整数环Z、有理数环Q、实数环R、复数环C都是交换 环,含幺环,无零因子环和整环.除了整数环以外都是域.令2Z=2z|zZ，则构成交换环和无零因子环.但不是含幺环和整环.设nZ,n2,则n阶实矩阵的集合Mn(R)关于矩阵加法和乘法构成环，它是含幺环，但不是交换环和无零因子环，也不是整环.构成环，它是交换环,含幺环,但不是无零因子 环和整环.23=32=0，2和3是零因子.注意：对于一般的n,Zn是整环当且仅当n是素数.,7.5 环与域,END,
