离散数学群与环

第七章群与环离散数学陈志奎主编人民邮电出版社第1页本章将讨论特殊代数系统——群与环。群是含有一个二元运算抽象代数。半群与群在形式语言、快速加法器设计、纠错码定制和自动机理论中都有卓有成效应用。环是含有两个二元运算代数系统，它和群以及半群有亲密联络。群最初是由EvaristeGalois在1830年所提出，它应用于满足一些性质一个有限集一系列置换中。Galois于1811年生于法国巴黎，直到12岁才进入巴黎一所公立中学学习，在此之前，他在家中有母亲进行教育。16岁时，完全沉醉在数学学习之中，以至于忽略了其它课程学习。两次参加EcolePolytechnique入学考试，但均未经过，最终进入EcoleNormale研究所进修。1830年法国革命期间，Galois因为指责其学校领导而被学校开除。另外Galois还曾因为政治活动二被捕入狱。在1832年5月30日，他在一场决斗中受伤，并在第二天逝世，年仅20岁。在决斗前，Galois留了一封信给他一位朋友，信中详细描述了他研究结果。他结果对于当初人来书实在太超前了，所以直到1870年他全部研究结果才完全展现在世人面前。概述第2页PART01PART02PART03半群群子群与群陪集分解PART04环与域PART05循环群与置换群内容安排第3页定义7.1给定<S，⊙>，若⊙满足结合律，则称<S，⊙>为半群。可见，半群就是由集合及在此集合上一个含有集合率二元运算组成代数系统。半群就是非空集合S以及一个定义在S上可结合二元运算⊙，将用<S，⊙>表示半群，或者当运算⊙很清楚时能够简记为S。另外还能够把a⊙b看成是a和b积。假如⊙是一个可交换二元运算，则称半群<S，⊙>是一个可交换半群。7.1半群第4页例7.1<Z,+>是一个可交换半群。因为加法满足结合率，同时加法是可交换，所以<Z,+>是一个可交换半群。例7.2集合Z以及普通意义下除法运算就不组成一个半群，因为除法运算不是可结合。例7.3集合P（S），其中S是一个集合，加上并运算，它就组成一个交换半群。因为并运算满足结合律和交换律。7.1半群第5页定义7.2：给定<M，⊙>，若<M，⊙>是半群且⊙有幺元或⊙满足结合律且拥有幺元，则称<M，⊙>为独异点或含幺半群或拟群。例7.4给定<N，+>和<N，*>，其中N是自然数集合，+和*为普通意义下加法和乘法。易知<N，+>和<N，*>都是半群，而且还是独异点。因为0是+幺元，1是*幺元。例7.5<，+>，<N，+>，<Q，+>，<R，+>，<C，+>都是半群，+是普通意义下加法，在这些半群中，除<，+>外都是独异点。其余几个中含有幺元0，而<，+>中无幺元存在。7.1半群第6页定义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页例7.6：给定<N，+>，其中N是自然数集合，+为普通意义下加法，则<N，+>是无穷循环独异点，0是幺元，1是生成元。例7.7令半群<S，*>，其中S={a，b，c，d}，*定义如表7.1，试证实生成集G={a，b}。7.1半群*AbcdaDcbabBbbbcCcccdAbcd第8页定义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半群第9页例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半群第10页定理7.1：若半群<S，⊙>和半群<T，

>是可交换，则<S×T，

>也是可交换。定理7.2：给定半群<S，⊙>和半群<T，

>，且e1和e2分别是他们幺元，则积半群<S×T>含有幺元<e1,e2>。7.1半群第11页定理7.3：给定半群<S，⊙>和半群<T，

>，且和分别是他们零元，则积半群<S×T>含有零元定理7.4：给定半群<S，⊙>和半群<T，

>，且s∈S逆元，t∈T逆元，则积半群<S×T>中逆元为7.1半群第12页PART01PART02PART03半群群子群与群陪集分解PART04环与域PART05循环群与置换群第13页定义7.7给定代数系统Ｖ＝<G，⊙>，若<G，⊙>是独异点而且每个元素均存在逆元，或满足⊙是可结合而且关于⊙存在幺元而且G中每个元素关于⊙是可逆，则称<G，⊙>是群。记为G。群比独异点含有更强条件。例7.11给定<Z，+>和<Q，*>，其中Z和Q分别为整数集和有理数集，+和*分别是普通意义下加法和乘法。可知<Z，+>是群，0是幺元，每个元素i∈Z逆元为-1；<Q，*>不是群，1是幺元，0无逆元。但<Q-{0}，*>是群。在半群、独异点、群这些概念中，因为只含有一个二元运算，所以在不发生混同情况下，能够将算符省去。比如将x*y写成xy。在下面讨论中，我们将常使用这种简略表示方法。7.2群第14页例7.12设G={e，a，b，c}，G上运算由表7.2表示，不难验证G是一个群。由表中能够看出G运算含有以下特点：e为G中单位元；G中运算是可交换；每个元素逆元就是它自己；在a，b，c三个元素中，任意两个元素运算结果都等于另一个元素。这个群为Klein四元群，简称四元群。7.2群eabceeabcaaecbbbceaccbae第15页定义7.8给定群G，若⊙是可交换，则称G是可交换群或G是Abel群。例7.14含有普通意义下加法运算全部整数集合Z是一个Abel群，假如a∈Z，那么a逆是他负数-a。例7.15在普通意义下乘法运算不是一个群，因为中元素2没有你元素。然而，在给出运算下该集合是一个幺半群。例7.16在普通意义下乘法运算下，全部非零实数组成集合组成一个群。a≠0逆是1/a。7.2群第16页定义7.9若群G是有穷集，则称G是有限群，不然称为无限群。群G基数称为群G阶。含有单位元群称为平凡群。7.2群第17页例7.17<Z，+>是无穷群，<S，⊙>，其中S={a，b，c}，⊙运算表如表7.3能够验证，<S，⊙>是群，a为幺元，b和c互为逆元；又因为|G|=3，故<S，⊙>是3阶群。7.2群⊙abcaabcbbcaccab第18页例7.18<Z，+>和<R，+>是无限群，<Zn，

>是有限群也是n阶群。klein四元群是四阶群。<{0}，+>是平凡群。上述全部群都是交换群，不过n阶（n≥2）实可逆矩阵集合关于矩阵乘法组成群是非交换群，因为矩阵乘法不满足交换律。定理7.5给定群<G，

>，则7.2群第19页定义7.10：集合置换：令X是非空有限集合，从X到X双射函数，称为集合X中置换，并称|X|为置换阶。集合上全部置换（双射）与复合运算，组成代数系统是一个群，称为对称群。由n个元素集合而组成全部n!个n阶置换集合与复合置换运算

组成群<，

>，它便是n次n!阶对称群。

若

，则称由Q和

组成群<Q，

>为置换群。7.2群第20页定义7.11集合X是无限，令TX表示全部从集合X到X变换集合，具有以下性质：––––<TX，º>组成群，在代数中称为变换群。置换群是变换群特例。7.2群第21页定义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阶轮换（124）。7.2群第22页PART01PART02PART03半群群子群与群陪集分解PART04环与域PART05循环群与置换群第23页子群就是群子代数。定义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子群概念第24页定义7.14给定群<G，⊙>及非空集合H

G，则<H,⊙>是<G，⊙>子群

（

a）（

b）（a，b∈H

a⊙b∈H）

（

a）（a∈H

∈H）。本定理表明<H，⊙>是<G，⊙>子群充要条件是H对于⊙封闭及H中每个元素存在逆元。定理7.6设G为群，H是G非空子集。则H是G子群当且仅当

a，b属于H有a∈H。7.3.1子群概念第25页给定一子群H和G内某一元素a，则可定义出一个左陪集aH={ah;h∈H}。因为a为可逆，由φ(h)=ah给出之映射φ:H→aH为一个双射。更甚地，每一个G内元素都包含在恰好一个H左陪集中；其左陪集为对应于一等价关系等价类，其等价关系a1~a2当且仅当a1−1a2会在H内。H左陪集之数目称之为H在G内“指数”，并标识为[G:H]。拉格朗日定理叙述著对一个有限群G和一个子群H而言，其中o(G)和o(H)分别为G和H目。尤其地是，每一个G子群目(和每一个G内元素目)都必须为o(G)因子。右陪集为相类比之定义：Ha={ha:h∈H}。其亦有对应于一适当之等价关系等价类，且其个数亦会相等于[G:H]。若对于每个在G内a，aH=Ha，则H称之为正规子群。每一个指数2子群皆为正规：左陪集和右陪集都简单地为此一子群和其补集。7.3.2群陪集与拉格朗日定理第26页例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群陪集与拉格朗日定理第27页PART01PART02PART03半群群子群与群陪集分解PART04环与域PART05循环群与置换群第28页定义7.15设<G，

>是群，若

a∈G，对

x∈G，

k∈Z，有x=，则称<G，

>是循环群，记作G=<a>，称a是群<G，

>生成元。定义7.16若存在a

G使得G=<a>，则称G是循环群，称a为G生成元。循环群G=<a>依据生成元a阶能够分为两类：n阶循环群和无限循环群。设G=<a>是循环群，若a是n阶元，则那么|G|=n，称G为n阶循环群。若a是无限阶元，则这时称G为无限循环群。7.4循环群与置换群第29页定理7.7设G=<a>是循环群若G是无限循环群，则G只有两个生成元，即a和。若G是n阶循环群，则G含有个生成元，对于任何小于n且与n互素自然数r，是G生成元。定理7.8设G=<a>是循环群，则G子群仍是循环群。若G=<a>是无限循环群，则G子群除{e}以外都是无限循环群。若G=<a>是n阶循环群，则对于n每个正因子d，G恰好含有一个d阶子群。7.4循环群与置换群第30页例7.24设是整数加群，是模12加群，求出和全部子群。7.4循环群与置换群第31页定义7.17：设S={1,2，

，n}，S上任何双射函数称为S上n元置换。定义7.18：设是n元置换，复合º也是n元置换，称为与乘机，记作。7.4循环群与置换群第32页定义7.19一个置换群是一个群G，其元素是一个给定集M置换，而其群作用是G中置换（能够看作是从M到本身双射）复合；其关系经常写作(G,M)。注意全部置换群是对称群；置换群通常是指对称群一个子群。n个元素置换群记为；若M是任意有限或无限集合，则全部M置换组成对称群通常写作Sym(M)。设S≠Ф，|S|＜+，S上一个一一变换被称为置换。当S上一些置换关于乘法运算组成群是，就成它为置换群。若|S|=n，设{1,2，

，n}，其置换全体组成集合普通表示为Sn；经过n次恒等变换群称为n次对称群。7.4循环群与置换群置换群到被置换元素应用称为群作用；它在对称性和组合论以及数学其它很多分支中有应用。第33页PART01PART02PART03半群群子群与群陪集分解PART04环与域PART05循环群与置换群内容安排第34页在本章前面内容中介绍了半群、独异点和群，他们都是含有一个运算代数结构，这对于研究简单整数和实数系统来说都是不够。所以，必须研究含有两个运算代数结构——环和域。环和域均建立在Abel群基础之上，在上一节中已经有过介绍。7.5环与域第35页定义7.21设<R，+，

>是代数系统，+和

是二元运算，假如满足以下条件：（1）<R，+>组成交换群；（2）<R，

>组成半群；（3）

运算关于+运算适合分配律，则称<R，+，

>是一个环。为了区分环中两个运算，通常称+为环中加法，

为环中乘法，把<S，+>称为加法群，<S，

>称为乘法半群。而且还要求，运算次序是先计算乘法再算加法。经常又因为环中乘法半群满足于不一样乘法各种性质，将环冠以不一样名称。7.5环与域第36页定义7.22给定环<R，+，

>，若<R，

>是可交换半群，则称<R，+，

>是可交换环；若<R，

>是独异点，则称<R，+，

>是含幺环；若

a，b

R，ab=0

a=0

b=0，则称R是无零因子环；若<R，

>满足等幂律，则称<R，+，

>是布尔环；若R既是交换环、含幺环，又是无零因子环，则称R是整环。7.5环与域第37页例7.25

<Z，+，*>，<R，+，*>，<Q，+，*>，<E，+，*>，和<C，+，*>等都是环。而且除了<E，+，*>之外都是拥有加法零元（数0）和乘法幺元（数1）和交换含幺环。这里Z，R，Q，E，C分别为整数集合，实数集合，有理数集合，偶数集合和复数集合。而+和*分别为普通意义下加法和乘法。例7.26

给定<P（S），+，*>，其中P（S）是结合S幂集，+和*分别为普通意义下加法和乘法：A+B=（A-B）∪（B-A）A*B=A∩B这里A,B∈P（S），∩和∪是集合交与并运算。

不难验证，<P（S），+，*>是环，而且拥有加法幺元∅和乘法幺元S可交换幺换。通常称该环为子集环。7.5环与域第38页定理7.9设<R，+，

>是环，则（1）

a

R，a0=0a=0（2）

a，b

R，（-a）b=a（-b）=-ab（3）

a，b，c

R，a（b-c）=ab-ac，（b-c）a=ab-ca7.5环与域第39页例7.28在环中计算(a+b)3,(a

b)2解

(a+b)3=(a+b)(a+b)(a+b)

=(a2+ba+ab+b2)(a+b)

=a3+ba2+aba+b2