离散数学第5章

1、1第第3篇篇 代数系统代数系统（Algebraic System）2第第5章章 代数结构（代数结构（algebraic structure ）1 代数系统的引入代数系统的引入2 运算及其性质运算及其性质3 半群半群4 群与子群群与子群5 阿贝尔群和循环群阿贝尔群和循环群6 陪集与拉格朗日定理陪集与拉格朗日定理7 同态与同构同态与同构8 环和域环和域 31代数系统的引入如果如果 为为An到到B的一个函数，的一个函数，则称则称 为集合为集合A上的上的n元运算元运算（operater）。）。 如果如果 B A，则称该，则称该n元运算元运算在在A上上封封闭。闭。41代数系统的引入代数系统的引入 本章主

2、要讨论一元运算和二元运算。本章主要讨论一元运算和二元运算。例：（例：（1）在整数）在整数I和实数和实数R中中,+,-,均为均为二元运算。二元运算。 （2）在集合）在集合Z的幂集的幂集 (z)中中, , 均为二元均为二元运算运算,而而“”是一元运算；是一元运算；51代数系统的引入代数系统的引入（3 3） 命题公式命题公式 中中,均为二元运算均为二元运算, ,而而“ ”为一元运算为一元运算（4 4） 双射函数双射函数 中中, ,函数的合成运算是函数的合成运算是二元运算；二元运算； 二元运算常用符号：二元运算常用符号：+,+, , , , , , , , , , , , , 等等。等等。61代数系统

3、的引入 定义定义: :一个非空集合一个非空集合A A连同若干个定义连同若干个定义在该集合上的运算在该集合上的运算f f1 1,f,f2 2,.,f,.,fk k所组成所组成的系统就称为一个代数系统，的系统就称为一个代数系统， 记作记作A, f 。72运算及其性质 定义定义: :设设*是集合是集合S上的二元运算上的二元运算,对任一对任一x,y S有有x yS则称则称 运算在运算在S上是封闭上是封闭的。的。 81代数系统的引入 例：（例：（1 1）在正整偶数的集合）在正整偶数的集合E E中中, ,对对,+,+运算是封闭的；在正整奇数的集合中运算是封闭的；在正整奇数的集合中, ,对对运算是封闭的运算

4、是封闭的, ,而对而对+ +运算不是封闭的。运算不是封闭的。 （2）在前例中）在前例中,R,I集合中集合中+,-,运算；运算； (z) 的元素中的元素中 , ,运算等均为封闭的。运算等均为封闭的。92运算及其性质 例题例题: 设设A=x|x=2n,n N,问乘法运算是问乘法运算是否封闭？对加法运算呢？否封闭？对加法运算呢？ 解解 对于任意的对于任意的2r,2s A，r，s N，因，因为为2r2s=2r+s A,所以乘法运算是封闭。所以乘法运算是封闭。对于加法运算是不封闭的，因为至少对于加法运算是不封闭的，因为至少有有2+22=6 A102运算及其性质 定义定义:设设* *是集合是集合S S上的

5、二元运算上的二元运算, ,对任一对任一x,yx,y S S有有x x y=yy=y x,x,则称则称 运算在运算在S S上是可交上是可交换的（换的（commutative ）或者说）或者说 在在S S上满足上满足交换律。交换律。112运算及其性质 例题例题:设设Q是有理数集合，是有理数集合，是是Q上的二元上的二元运算，对任意的运算，对任意的a,b R， ab=a+b-ab，问运算，问运算是否可交换。是否可交换。解解 因为因为 ab=a+b-ab=b+a-ba=ba所以运算所以运算 是可交换的。是可交换的。122运算及其性质 定义定义: :设设* *是集合是集合S S上的二元运算上的二元运算,

6、,对任对任一一x,y,z x,y,z S S都有都有 （x x y y） z=x z=x （y y z z）, ,则称则称 运算在运算在S S上是可结合的（上是可结合的（associative ）或者说或者说* *在在S S上满足结合律。上满足结合律。132运算及其性质 例题例题:设设A是一个非空集合，是一个非空集合， 是是A上上的二元运算，对于任意的二元运算，对于任意a,b A,有有ab=b，证明是可结合运算。，证明是可结合运算。证明证明 因为对于任意的因为对于任意的a,b,c A (ab)c=bc=c而而 a(bc)=ac=c所以所以(ab)c=a(bc) 142运算及其性质 定义定义:

7、:设设 和和 是集合是集合S S上的二个二元运算上的二个二元运算, ,对任一对任一x,y,z x,y,z S S有有 x x （y y z z）= =（x x y y） （x x z z）；）； （y y z z） x=x=（y y x x） （z z x x）, , 则称运算则称运算 对对 是可分配的（是可分配的（distributive ）或称或称 对对 满足分配律。满足分配律。 152运算及其性质 例题：设集合例题：设集合A A， ，定义，定义A A上的二元运算上的二元运算 ， ，运算表如下：问：运算表如下：问： 对对 可分配吗？可分配吗？ 16从从*和的运算表中可以看出和的运算表中可以

8、看出*和两种运算都是可交换的。和两种运算都是可交换的。故只须验证故只须验证 (*)=()*() (*)=()*() (*)=()*() (*)=()*() (*)=()*() (*)=()*()(*)= ()*()=*= (*)= ()*()=*=(*)= ()*()=*=(*)= ()*()=*=(*)= ()*()=*=(*)= ()*()=*=验证运算对于运算验证运算对于运算*是可分配的。是可分配的。17 * ( )(*) (*) * ( ) (*) (*) 运算运算* 对于运算是不可分配的。对于运算是不可分配的。182运算及其性质 定义定义: :设设 ， 是定义在集合是定义在集合S S

9、上的两个可上的两个可交换二元运算，如果对于任意的交换二元运算，如果对于任意的x,yx,y S S，都有：都有：x x (x (x y)=xy)=x；x x (x(x y)=xy)=x 则称运算则称运算 和运算和运算 满足吸收律满足吸收律（assimilate）。）。192运算及其性质n例题：设集合例题：设集合N为自然数全体，在为自然数全体，在N上定上定义两个二元运算义两个二元运算*和，对于任意和，对于任意x,y N，有有n x*y=max(x,y)n xy=min(x,y)n验证运算验证运算*和的吸收律。和的吸收律。202运算及其性质n解解 对于任意对于任意a,b Nn a*(ab)=max(

10、a,min(a,b)=an a(a*b)=min(a,max(a,b)=an因此，因此，*和满足吸收律。和满足吸收律。212运算及其性质 定义定义: :设设* *是是S S上的二元运算上的二元运算, ,若对任一若对任一x x S S有有x x x=x, x=x,则称则称 满足等幂律满足等幂律（idempotent ）。）。222运算及其性质 例题：设例题：设(S)是集合是集合S的幂集，在的幂集，在(S)上定义的两个二元运算，集合的上定义的两个二元运算，集合的“并并”运算运算和集合的和集合的“交交”运算运算 ，验证是，验证是、等幂的。等幂的。232运算及其性质讨论定义：讨论定义：1)S1)S上每

11、一个元素均满足上每一个元素均满足x x x=x,x=x,才称才称 在在S S上上满足幂等律；满足幂等律；2)2)若在若在S S上存在元素上存在元素x x S S有有x x x=x, x=x,则称则称x x为为S S上的等幂元；上的等幂元；3)3)由此定义由此定义, ,若若x x是幂等元素是幂等元素, ,则有则有x x x=xx=x和和x xn n=x=x成立。成立。242运算及其性质 例：（例：（1 1）在实数集合）在实数集合R R中中,+,+,是可是可交换交换, ,可结合的可结合的, ,对对+ +是满足分配律是满足分配律的的,“0”,“0”对对+ +是等幂元素是等幂元素, ,而其它不而其它不

12、为等幂元素为等幂元素, ,对对“-”-”法是不可交换法是不可交换, ,不可结合的不可结合的；252运算及其性质（2 2）在）在 (z)(z)中中, , , , 均是可交换均是可交换, ,可结可结合的合的, , 对对 , , 对对 均是可分配的；均是可分配的； (z)(z)中任一元素中任一元素, ,对对 , , 均是等幂元素。均是等幂元素。满足等幂律；满足等幂律；而而 (z)(z)中中, ,对称差分对称差分 是可交换是可交换, ,可结合可结合的。的。262运算及其性质 除除 (s)(s) = = 以外不满足等幂律。以外不满足等幂律。 = = , ,而除而除 以外的以外的A A (z)(z)有有A

13、 A AA AA。272运算及其性质 下面定义特异元素幺元下面定义特异元素幺元, ,零元和逆元。零元和逆元。定义：设定义：设* *是集合是集合Z Z中的二元运算中的二元运算, ,(1)(1)若有一元素若有一元素el el Z Z, ,对任一对任一x x Z Z有有elel* *x=xx=x；则称；则称elel为为Z Z中对于中对于* *的左幺元的左幺元( (左单位元素左单位元素) )；282运算及其性质 (2)(2)若有一元素若有一元素er er Z Z, ,对任一对任一x x Z Z有有x x* * er=xer=x；则称则称erer为为Z Z中对于中对于* *的右幺元的右幺元（右单元元素）

14、。（右单元元素）。292运算及其性质 定理：若定理：若e el l和和e er r分别是分别是Z Z中对于中对于* *的左的左幺元和右幺元幺元和右幺元, ,则对于每一个则对于每一个x x Z Z，可有可有e el l= = e er r = = e e和和e e* *x=xx=x* * e=x e=x，则称，则称e e为为Z Z中关于运算中关于运算* * 的幺元，且的幺元，且e e Z Z是是唯一的。唯一的。302运算及其性质 elel和和erer分别是对分别是对* *的左的左, ,右左元，右左元， 则有则有el el * * erer = = erer = = elel有有elel = =

15、er = eer = e成立。成立。312运算及其性质（2 2）幺元）幺元e e是唯一的。是唯一的。 用反证法：假设有二个不同的幺元用反证法：假设有二个不同的幺元e1e1和和e2e2, ,则有则有e1e1* * e2= e2= e1 e2= e2= e1, ,这和这和假设相矛盾。假设相矛盾。若存在幺元的话一定是唯一的。若存在幺元的话一定是唯一的。322运算及其性质例：例：（1 1）在实数集合）在实数集合R R中中, ,对对+ +而言而言, , e e+=0+=0；对对而言而言, , e e* *=1 =1 ；（2 2）在）在 (E)(E)中中, ,对对 而言而言, , e e =E=E（全集合

16、）；对（全集合）；对 而言而言, , e e = = （空集）；（空集）；332运算及其性质（3 3） 双射函数双射函数 中中, ,对对“ ”而言，而言， e e =Ix=Ix（恒等函数）；（恒等函数）；（4 4） 命题逻辑命题逻辑 中，中， 对对而言，而言，e e =F=F（永假式）；（永假式）； 对对而言，而言， e e =T=T（永真式）（永真式）。342运算及其性质 例例: :设集合设集合S=,S=,，在，在S S上定义上定义的两个二元运算的两个二元运算* *和和 如表所示。试指如表所示。试指出左幺元或右幺元。出左幺元或右幺元。* 352运算及其性质 定义：设定义：设* *是对集合是对

17、集合Z Z中的二元运算，中的二元运算， （1 1）若有一元素）若有一元素l l Z Z，且对每一个且对每一个x x Z Z有有l l * *x= l x= l ，则称，则称l l 为为Z Z中对于中对于* *的左零元；的左零元；（2 2）若有一元素）若有一元素r r Z Z，且对每一个且对每一个x x Z Z有有 x x* * r r= = r r ，则称则称r r为为Z Z中对于中对于* *的右零元。的右零元。362运算及其性质 定理：若定理：若l l和和r r分别是分别是Z Z中对于中对于* *的的左零元和右零元，于是对所有的左零元和右零元，于是对所有的x x Z Z，可有可有l l =

18、= r r = =，能使，能使* *x=xx=x* *=。在此情况下，。在此情况下， Z Z是唯一的，并称是唯一的，并称是是Z Z中对中对* *的零元。的零元。372运算及其性质例：例：（1 1）在实数集合）在实数集合R R中，对中，对而言而言, ,， L L = = r r =0 =0 （2 2）在）在 (E)(E)中，对中，对 而言，而言， = = ； 对对 而言，而言， = E = E ；（3 3） 命题逻辑命题逻辑 中，中， 对对而言，而言， =T =T ； 对对而言，而言， = F= F。382运算及其性质 例题例题8 8 设集合设集合S=S=浅色，深色浅色，深色 ，定义在，定义在S

19、 S上的一个二元运算上的一个二元运算* *如表所示。试指出零如表所示。试指出零元和幺元。元和幺元。*浅色浅色 深色深色浅色浅色深色深色浅色浅色 深色深色深色深色 深色深色392运算及其性质 1）运算）运算 具有封闭性，当且仅当运算具有封闭性，当且仅当运算表中的每个元素都属于表中的每个元素都属于A。 2）运算）运算 具有可交换性，当且仅当运具有可交换性，当且仅当运算表关于主对角线是对称的。算表关于主对角线是对称的。 3）运算）运算 具有等幂性，当且仅当运算具有等幂性，当且仅当运算表的主对角线上的每一元素与它所在行表的主对角线上的每一元素与它所在行（列）的表头元素相同。（列）的表头元素相同。 40

20、2运算及其性质 定义定义: :设代数结构设代数结构Ae 中中 为二元运为二元运算，算，e e为么元，为么元，a,b a,b 为为A A中元素中元素, ,若若b b a ae e，那么称那么称b b为为a a的左逆元，的左逆元，a a为为b b的右逆元。若的右逆元。若a a b bb b a ae e，那么称，那么称a(b)a(b)为为b(a)b(a)的逆元。的逆元。 x x的逆元通常记为的逆元通常记为x x-1-1; ;但当运算被称为但当运算被称为“加法运算加法运算”（记为（记为+ +）时，）时，x x的逆元可记的逆元可记为为-x -x 。412运算及其性质 1） A中关于运算中关于运算 具有

21、幺元，当且仅当该具有幺元，当且仅当该元素所对应的行和列依次与运算表的行和列相元素所对应的行和列依次与运算表的行和列相一致。一致。 2） A中关于运算中关于运算 具有零元，当且仅当该元具有零元，当且仅当该元素所对应的行和列中的元素都与该元素相同。素所对应的行和列中的元素都与该元素相同。 3） 设设A中关于运算中关于运算 具有幺元，具有幺元，a和和b互逆，互逆，当且仅当位于当且仅当位于a所在行和所在行和b所在列的元素及所在列的元素及b所所在行和在行和a 所在列的元素都是幺元。所在列的元素都是幺元。422运算及其性质 例例: : 设集合设集合S=, ,S=, ,定义在定义在S S上的一个二元运算上的

22、一个二元运算* *如表所示。试指出代数如表所示。试指出代数系统系统S, 中各个元素的左、右逆元情况。中各个元素的左、右逆元情况。432运算及其性质* *442运算及其性质 一般地，一个元素的一般地，一个元素的左逆元左逆元不一定等于不一定等于它的它的右逆元右逆元。一个元素可以有。一个元素可以有左逆元左逆元不不一定有一定有右逆元右逆元。甚至一个元素的。甚至一个元素的左（右）左（右）逆元逆元不一定是唯一的。不一定是唯一的。452运算及其性质 定理：设定理：设Z, 是代数系统，是代数系统， * *是定义是定义在在Z Z上的一个二元运算，上的一个二元运算，Z Z中含有幺元中含有幺元e e。且每一个元素都

23、有左逆元。如果且每一个元素都有左逆元。如果* *是可结是可结合的运算。那么，这个代数系统中的任合的运算。那么，这个代数系统中的任何一个元素的左逆元必定是该元素的右何一个元素的左逆元必定是该元素的右逆元，且每个元素的逆元是唯一的。逆元，且每个元素的逆元是唯一的。462运算及其性质证明：（证明：（1 1）先证左逆元）先证左逆元= =右逆元：右逆元：设设a,b,c，且，且b是是a的左逆元，的左逆元， c是是b的左逆元。的左逆元。因为：因为： （b a） b =e b = b所以：所以： e=c b = c (（b a） b ) = (c （b a） ) b = (（c b ） a ) b = (（e

24、 ） a ) b =a b (即即b也是也是a的的右逆元右逆元)472运算及其性质（2 2）证明逆元是唯一的。）证明逆元是唯一的。ab1和和b2，则有则有 b1 = b1 e = b1 a b2 =b1 a b2 = e b2b2482运算及其性质 例：试构造一个代数系统，使得其中只例：试构造一个代数系统，使得其中只有一个元素具有逆元。有一个元素具有逆元。解解 ：设：设m,n I,T=x|x I,mxn,那么，那么，代数系统代数系统中有一个幺元是中有一个幺元是m,且只且只有有m有逆元，因为有逆元，因为m=max(m,m)。492运算及其性质 例：例： 对于代数系统对于代数系统，这里，这里R是实

25、数的全体，是普通的乘法运算，是实数的全体，是普通的乘法运算，是否每个元素都有逆元。是否每个元素都有逆元。解解 ：该代数系统中的幺元是：该代数系统中的幺元是1，除了零，除了零元素元素0外，所有的元素都有逆元。外，所有的元素都有逆元。502运算及其性质例：例： 对于代数系统对于代数系统，这里，这里Nk=0,1,2,k-1, +k是定义在是定义在Nk上上的模的模k加法运算，定义如下：加法运算，定义如下： 对于任意对于任意x,y Nk x+y 若若x+yk x +ky= x+y-k 若若x+y k试问是否每个元素都有逆元。试问是否每个元素都有逆元。512运算及其性质 解解: 可以验证，可以验证，+k是

26、一个可结合的二元运是一个可结合的二元运算，算，Nk中关于运算中关于运算+k的幺元是的幺元是0， Nk中中的每一个元素都有唯一的逆元，即的每一个元素都有唯一的逆元，即0的逆的逆元是元是0，每个非零元素，每个非零元素x的逆元是的逆元是k-x。522运算及其性质推论：推论：(x(x-1-1) )-1-1 =x , =x , e e-1-1= = e e证明：证明： x x-1-1 * *x= (xx= (x-1-1) )-1-1 * *（ x x-1-1 ）=x=x* * x x-1 -1 = = e e 有有(x(x-1-1) )-1-1 =x =x e e-1-1 * * e e= = e e=

27、 = e e* * e e 有有e e-1-1= = e e 532运算及其性质例：（例：（1 1）在实数集合）在实数集合R R中，对中，对“+”+”运算，任一运算，任一x x R R有有 x x-1-1 =-x =-x，x+x+（-x-x）=0=0，加法幺元，加法幺元 对对“”运算，对任一运算，对任一x x R R有有x x-1-1 =1=1 x x（x x 0 0） x x 1 1 x x =1 =1，乘法幺元；，乘法幺元；542运算及其性质（2 2）在函数的合成运算中）在函数的合成运算中, ,每一个双每一个双射函数都是可逆的，射函数都是可逆的， f f-1-1（f f的逆关系）；的逆关系

28、）；（3 3）在所有的二元运算中）在所有的二元运算中, ,零元一定零元一定不存在逆元，不存在逆元，* *x=xx=x* *=。 553 半群（半群（semigroup ） 半群是一种特殊的代数系统，它在形式语言、半群是一种特殊的代数系统，它在形式语言、自动机等领域中，都有具体的应用。自动机等领域中，都有具体的应用。学习本节要掌握如下概念：学习本节要掌握如下概念：广群、半群、子半群、独异点广群、半群、子半群、独异点563 半群半群 定义：一个代数系统定义：一个代数系统，其中，其中S是是非空集合，非空集合，*是是S上的一个二元运算，如上的一个二元运算，如果运算果运算 是封闭的，则称代数系统是封闭的

29、，则称代数系统为广群。为广群。573 半群半群S， 如如果：果：n（1）运算）运算 是封闭的；是封闭的；n（2）运算）运算*是可结合的，即对任意的是可结合的，即对任意的x,y,z S，满足，满足 (x*y)*z=x*(y*z)n则称代数系统则称代数系统为半群。为半群。583 半群半群例：对于正整数例：对于正整数k，Nk=0,1,2,k-1，设，设*k是是Nk上的一个二元运算，使得上的一个二元运算，使得a*kb=用用k除除ab所所得的余数，这里得的余数，这里a，bNk。na)当当k=4时，试造出时，试造出*k的运算表。的运算表。nb)对于任意正整数对于任意正整数k，证明，证明是一个半是一个半群。

30、群。593 半群半群*k 0 1 2 3 0 0 0 0 0 1 0 1 2 3 2 0 2 0 2 3 0 3 2 1603 半群半群nb)对于任意的对于任意的a，bNk ，a*kb= ab-nk= r，0rk-1，n所以运算所以运算*k在在Nk上是封闭的。上是封闭的。n对于任意的对于任意的a，b，cNk ，有，有n (a*kb) *kc=(ab-n1k) c- n2k=r1 0r1k-1n = ab c-k(n1c+n2)n a*k ( b *kc)=a(b c -n3k) - n4k=r2 0r2k-1n = ab c-k(n3a+n4)n可见可见r1和和r2都是都是ab c用用k除所得

31、的余数，所以除所得的余数，所以r1 = r2 。n所以所以(a*kb) *kc= a*k ( b *kc)，即，即*k满足结合律。满足结合律。n因此，因此，是半群。是半群。613 半群半群 例题：设例题：设S=a,b,c，在，在S上的一个二元运算上的一个二元运算 定义如表所示。验证定义如表所示。验证是一个半群。是一个半群。 a b cabca b ca b ca b c623 半群半群n解解 从运算表中可知运算从运算表中可知运算是封闭的，同是封闭的，同时时a,b和和c都是左幺元。所以，对于任意都是左幺元。所以，对于任意的的x,y,z S，都有，都有n x(yz)=xz=z=yz=(xy)zn因

32、此，因此，是半群。是半群。633 半群半群n例：设例：设*是实数集是实数集R上的运算，其定义如下：上的运算，其定义如下：n a*b=a+b+2abn1)求求2*3，3*（-5）和）和7*1/2。n2)是半群吗？是半群吗？*可交换吗？可交换吗？n3)求求R中关于中关于*的幺元（单位元）。的幺元（单位元）。n4)R中哪些元素有逆元，逆元素是什么？中哪些元素有逆元，逆元素是什么？643 半群半群解：解：1) 2*3=17，3*（-5）=-32，7*1/2=14.5653 半群半群n2)运算运算*在在R上是封闭的。对任意上是封闭的。对任意a，b，cR，n(a*b)*c=(a+b+2ab)*c=a+b+

33、2ab+c+2(a+b+2ab )c=a+b+c+2ab+2ac+2bc+4abcna*(b*c)=a*(b+c+2bc)=a+b+c+2bc+2a(b+c+2bc)=a+b+c+2ab+2ac+2bc+4abcn所以所以(a*b)*c= a*(b*c)。因此。因此是半群。是半群。*可交换。可交换。663 半群半群n3)R中关于中关于*的幺元是的幺元是0。n4)R中除中除-1/2外所有元素都有逆元，外所有元素都有逆元，a的的逆元素是逆元素是-a/（1+2a）。）。673 半群半群设设为一半群为一半群, B S且且 在在B上封上封闭，那么闭，那么也是也是一个半群，称为一个半群，称为的的子半群子半

34、群。例：设例：设 表示普通的乘法运算，那么表示普通的乘法运算，那么、和和都是都是的子半群。的子半群。683 半群半群 讨论定义：讨论定义：（1 1）因为）因为* *在在S S上是可结合的，而上是可结合的，而T T S S且且* *在在T T上上是封闭的，所以是封闭的，所以* *在在T T上也是可结合的。上也是可结合的。 （2 2）由定义可知，）由定义可知， S S S S ， S , 也是也是 S , 的子半群。为了和其它子半群相的子半群。为了和其它子半群相互区别，称互区别，称 S , 是是 S , 的的“平凡子半平凡子半群群”; ;693 半群半群 练习：若练习：若S 是半群，是半群，aSa

35、S， M=aM=an n|n N|n N，证明，证明M 是是S 的的子半群。子半群。703 半群半群证明证明 只须证明运算只须证明运算*在在M上是封闭的。上是封闭的。任取任取an ， am M， an * am =（ an * a）* am -1 = an +1 * am -1 =（ an+1 * a）* am -2 = an +2 * am -2 = = an +m M所以所以是是的子半群的子半群。713 半群半群 设代数结构设代数结构为一个半群，为一个半群，如果如果S是一个有限集合，则必有是一个有限集合，则必有a S ，使得使得a a=a723 半群半群 证明证明: 因因是半群是半群,对于

36、任意对于任意b S，由，由于于 的封闭性可知的封闭性可知 b b S 记记b2 =b b b2 b =b b2 S 记记b3 = b2 b =b b2 b, b2, b3, , bi, , bq, , bj(最多有最多有|S|个不同元素个不同元素)733 半群半群 因因S是一个有限集合，所以必存在是一个有限集合，所以必存在 ji，使得，使得 bi = bj 令令 p=j-i 即即 j =p+i 代入上式：代入上式： bi = bp bi 所以，所以， bq = bp bq iqq 因为因为p1所以总可以找到所以总可以找到k1，使得，使得 kpi 对于对于bkp S，就有，就有 bkp = bp

37、 bkp = bp (bp bkp ) = b2p bkp = b2p (bp bkp ) =.= bkp bkp743 半群半群设代数结构设代数结构为半群，若为半群，若含有关于含有关于 运算的运算的么元么元,则称它为则称它为独异点独异点(monoidmonoid)，或，或含么半群含么半群。753 半群半群 例如：代数系统例如：代数系统是一个独异点，因是一个独异点，因为为是一个半群，且是一个半群，且0是是R中关于运算中关于运算+的幺元。的幺元。 另外，代数系统另外，代数系统,都是都是具有幺元具有幺元1的半群，因此它们都是独异点。的半群，因此它们都是独异点。763 半群半群 例：设例：设S S为

38、非空集合，为非空集合， (S)(S)是是S S的幂集，的幂集， 则则 , , ,S均为含幺半群。而均为含幺半群。而，其中，其中max(x1,x2)max(x1,x2)取二者之大值；取二者之大值；，其，其中中min(x1,x2)min(x1,x2)取二者之小值，均不为幺半取二者之小值，均不为幺半群（不存在幺元）。群（不存在幺元）。则为含幺半则为含幺半群，其中群，其中 e =0e =0773 半群半群 代数系统代数系统虽是一个半群，但关虽是一个半群，但关于运算于运算+不存在幺元，所以，这个代数系统不存在幺元，所以，这个代数系统不是独异点。不是独异点。783 半群半群 有代数系统有代数系统，其中，其

39、中S=a，0，1，运，运算算*由下表定义，证明由下表定义，证明是独异点。是独异点。*a 01aa 0100 0111 01793 半群半群证明：证明： 1）运算）运算*是封闭的。是封闭的。2）对于任意）对于任意x，yS，(x*y)*a=x*y x*(y*a)=x*y(x*y)*0=0 x*(y*0)=x*0=0(x*y)*1=1 x*(y*1)=x*1=1所以运算所以运算*是可结合的。是可结合的。803 半群半群证明：证明： 3）a是是S中关于运算中关于运算*的幺元。的幺元。因此因此是独异点。是独异点。813 半群半群设设是一个独异点是一个独异点,则在关于则在关于运算运算 的运算表中任何两行或

40、两列都是不相的运算表中任何两行或两列都是不相同的。同的。823 半群半群证明证明: 因因S 中关于中关于 运算的幺元是运算的幺元是e，因为因为对对于任意的元素于任意的元素a,b S，且，且ab时，总有时，总有 e a = a b= e b 和和 a e = a b= b e 所以：在的运算表中不可能有两行或两列是所以：在的运算表中不可能有两行或两列是相同的。相同的。833 半群半群例题：例题：设设I I是整数集合，是整数集合，m m是任意正整数，是任意正整数，Z Zm m是由模是由模m m的同余类组成的同余类集，在的同余类组成的同余类集，在Z Zm m上定义两个二元上定义两个二元运算运算+ +

41、m m和和m m分别如下：对于任意的分别如下：对于任意的ii，jj Z Zm m i + i +m mj=(i+j)(mod m)j=(i+j)(mod m) i im mj=(ij=(ij)(mod m)j)(mod m)试证明在这两个二元运算的运算表中任何两行或两试证明在这两个二元运算的运算表中任何两行或两列都是不相同的。列都是不相同的。 843 半群半群证明：考察代数结构证明：考察代数结构和和 ，只须证明只须证明和和都是独异点。都是独异点。先分三步证明先分三步证明是独异点，是独异点， 1）根据运算定义，证明两个运算在）根据运算定义，证明两个运算在Z Zm m上封闭；上封闭； 2）根据运算

42、定义，证明两个运算满足结合律；）根据运算定义，证明两个运算满足结合律； 3）根据运算定义，证明）根据运算定义，证明00是是的幺元，的幺元，11是是的幺元。的幺元。 853 半群半群(1)由运算由运算+ +m m和和m m的定义，可知它们在的定义，可知它们在Z Zm m上都上都是封闭的。是封闭的。 (2)对于任意对于任意i，j，k Z Zm m(i+(i+m mj)+j)+m mk=i+k=i+m m(j+(j+m mk)k) =(i+j+k)(mod m) =(i+j+k)(mod m)(i(im mj)j)m mk=ik=im m(j(jm mk)k) =(i =(ij jk)(mod m)

43、k)(mod m)即即运算运算+ +m m和和m m都是可结合的。都是可结合的。863 半群半群(3)因为因为0+0+m mi=i+i=i+m m0=i0=i，所以，所以，00是是中的幺元。因为中的幺元。因为11m mi=ii=im m1=i1=i，所以，所以11是是中的幺元。中的幺元。 因此，代数系统因此，代数系统， 都都是独异点。由定理可知，这两个运算的运算是独异点。由定理可知，这两个运算的运算表中任何两行或两列都不相同。表中任何两行或两列都不相同。 873 半群半群 定理：设定理：设是独异点，对于任是独异点，对于任意意a，b S，且，且a， b均有逆元，则均有逆元，则 a)(a-1)-1

44、=a b)a*b有逆元，且有逆元，且(a*b)-1=b-1*a-1883 半群半群证明：证明：a)因为因为a-1是是a的逆元，即的逆元，即a* a-1= a-1*a=e 所以所以 (a-1)-1=a b)因为因为(a*b)*(b-1*a-1) = a*(b*b-1)*a-1=a*e*a-1=e 同理可证：同理可证： (b-1*a-1) * (a*b)=e 所以所以 (a*b)-1=b-1*a-1894 群与子群群与子群 定义：设定义：设是一代数系统，是一代数系统，S是非空集是非空集合，合，*为为S上的二元运算，它满足以下四个上的二元运算，它满足以下四个条件时，则称条件时，则称为群。为群。（1）

45、*运算是封闭的；运算是封闭的；（2） *运算是可结合的；运算是可结合的；（3）存在幺元）存在幺元e；（4）S中每一个元素均有逆元。中每一个元素均有逆元。904 群与子群群与子群 例：例：, , （其中（其中Z2 =0,1, Z3 =0,1,2 ），）， 等均为群等均为群 , 只是含幺半群而不是群。只是含幺半群而不是群。914 群与子群群与子群 例：设例：设M= 0,60,120,240,300,180表示表示平面上几何图形顺时针旋转的六种位置，定平面上几何图形顺时针旋转的六种位置，定义一个二元运算义一个二元运算*，对，对M中任一元素中任一元素a,b有有a*b=图形旋转图形旋转(a+b)的角度，

46、并规定当旋转的角度，并规定当旋转到到360时即为时即为0， 试验证试验证是一个群。是一个群。924 群与子群群与子群*060120180240300006012018024030060601201802403000120120180240300060180180240300060120240240300060120180300300060120180240934 群与子群群与子群（1）运算是封闭的）运算是封闭的（2）*是可结合的是可结合的（3）幺元为）幺元为0 ；（4）每一个元素均有逆元：）每一个元素均有逆元：(0 )-1= 0 , (60 )-1=300 ,(120 )-1=240 , (1

47、80 )-1= 180 , (240 )-1=12 0 ,(300 )-1= 60 是一个群。是一个群。 944 群与子群群与子群 定义：设定义：设是一个群，如果是一个群，如果G是有限集是有限集合，则称合，则称为有限群，并把为有限群，并把|G|称为群称为群的阶数，如果的阶数，如果G为无限集合，则称为无限集合，则称为为无限群。无限群。 例：例：为无限群，上例中为无限群，上例中为有限为有限群，群的阶为群，群的阶为|M| =6。954 群与子群群与子群 至此，可以概括地说：广群仅仅是具有一至此，可以概括地说：广群仅仅是具有一个封闭的二元运算的非空集合；半群是一个封闭的二元运算的非空集合；半群是一个具

48、有结合运算的广群；独异点是具有幺个具有结合运算的广群；独异点是具有幺元的半群；群是每个元素都有逆元的独异元的半群；群是每个元素都有逆元的独异点。点。964 群与子群群与子群（1）群具有半群和含幺半群所具有的所有性）群具有半群和含幺半群所具有的所有性质；质；（2）由于群中存在幺元，所以在群的运算表）由于群中存在幺元，所以在群的运算表中一定没有相同的行（和列）中一定没有相同的行（和列）（3）在群中，每一个元素均存在逆元，所以）在群中，每一个元素均存在逆元，所以群相对半群和含幺半群来说有一些特殊的群相对半群和含幺半群来说有一些特殊的性质。性质。974 群与子群群与子群定理定理1：一个群：一个群中一定

49、不存在零元。中一定不存在零元。 984 群与子群群与子群 证明证明: 因当群的阶为因当群的阶为1时，它的唯一元素时，它的唯一元素是视作幺元是视作幺元e 。 设设|G|1 且群有零元。那么群中任何元素且群有零元。那么群中任何元素x G，都有，都有 x = x = e，所，所以，零元以，零元 就不存在，与就不存在，与是群的是群的假设矛盾。假设矛盾。994 群与子群群与子群 定理定理2：若：若是一个群，则对任一是一个群，则对任一a,b G必必存在唯一的元素存在唯一的元素x G ， 使使a * x= b。1004 群与子群群与子群n证明证明: 1）先证解存在性）先证解存在性 n 设设a的逆元的逆元a-

50、1，令，令n x = a-1 b （构造一个解）（构造一个解）n a x a （ a-1 b ）n （ a a-1 ） bn e b bn 2）再证解唯一性）再证解唯一性n 若另有解若另有解x1满足满足a x1 b ，则，则n a-1 （a x1） a-1 b n x1 a-1 b1014 群与子群群与子群 定理定理3：若：若是一个群，则对任一是一个群，则对任一a,b,c G，如果，如果有有 a * b = a * c 或或b * a = c * a ， 则必则必 有有 b = c。1024 群与子群群与子群 定理定理4：群：群的运算表中的每一行或的运算表中的每一行或每一列都是每一列都是G的元

51、素的一个置换。的元素的一个置换。定义：设定义：设S是一个非空集合，从集合是一个非空集合，从集合S到到S的的一个双射称为一个双射称为S的一个置换。的一个置换。1034 群与子群群与子群n如：对于集合如：对于集合S=a,b,c,d，一个置换如下：，一个置换如下： n a b c dn b d a cn a b c d n c a d b1044 群与子群群与子群 证明证明: 先证先证G中每一个元素只出现一次中每一个元素只出现一次 用反证法：设用反证法：设a对应行有两个元素对应行有两个元素b1、 b2对应的都是对应的都是c, 即即a b1a b2c,且且b1b2 由可约性得由可约性得b1b2 与假设

52、矛盾。与假设矛盾。 1054 群与子群群与子群 再证再证G中每一个元素必出现一次中每一个元素必出现一次 对于元素对于元素a G的那一行，设的那一行，设b是是G中的任中的任意一个元素，由于意一个元素，由于b=a （a-1 b），所以），所以b必定出现在对应于必定出现在对应于a的那一行。的那一行。 再由运算表中任何两行或两列都是不相再由运算表中任何两行或两列都是不相同的。同的。 得出要证的结论。得出要证的结论。1064 群与子群群与子群 定理定理5：群：群中，除幺元中，除幺元e外，不可外，不可能有别的等幂元。能有别的等幂元。定义：代数系统定义：代数系统中，如果存在中，如果存在a G,有有a*a=a

53、，则称，则称a为等幂元。为等幂元。1074 群与子群群与子群证明证明: 因为因为e e = e ，所以，所以e是等幂元。是等幂元。现设现设 a G， ae 且且 a a= a 则有则有a=e a=(a-1 a) a =a-1 (a a)=a-1 a=e与假与假设设 ae 矛矛盾。盾。1084 群与子群群与子群设设为群。为群。S是是G的非空的非空子集子集 ，如果，如果也构成群，则称也构成群，则称 为为G的子群的子群(subgroups)。1094 群与子群群与子群设设为群，为群，为为G的的子群，那么，子群，那么， 中的幺元中的幺元e必定必定也是也是中的幺元。中的幺元。1104 群与子群群与子群

54、证明证明: 设设中的幺元为中的幺元为e1 ，对，对于任意一个元素于任意一个元素 x S G, 必有必有 e1 x = x = e x 则有则有 e1 = e1114 群与子群群与子群设设为群，为群，为为G的的子群，如果，子群，如果，S =e或或S =G，那么，那么称称为为 的平凡子群。的平凡子群。1124 群与子群群与子群 例：例： 是一个群，设是一个群，设IE=x|x=2n,n I，证明证明是是的一个子群。的一个子群。1134 群与子群群与子群 证明：证明： (1)对于任意的对于任意的x,y IE，不妨设，不妨设x=2n1,y=2n2,n1,n2 I,则则 x+y=2n1+2n2=2(n1+

55、n2) n1+n2 I 所以所以 x+y I 即即+在在IE上封闭。上封闭。1144 群与子群群与子群 (2)运算运算+在在IE上保持可结合性。上保持可结合性。(3)中的幺元中的幺元0也在也在IE中。中。(4)对于任意的对于任意的x IE，必有，必有n使得使得x=2n，而，而 -x=-2n=2(-n)，n I所以所以-x IE，而，而x+(-x)=0，因此，因此，是是的一个子群。的一个子群。1154 群与子群群与子群 定理：设定理：设是一个群，是一个群，B是是G的非的非空子集，如果空子集，如果B是一个有限集，那么，是一个有限集，那么，只要运算只要运算*在在B上是封闭的，则上是封闭的，则必定是必

56、定是的子群。的子群。1164 群与子群群与子群证明：设证明：设b B，已知，已知*在在B上封闭，上封闭， 则则b*b B，即，即 b2 B， b2 *b B， 即：即： b3 B， 于是于是b ， b2 ， b3均在均在B中。中。由于由于B是有限集，是有限集，必存在正整数必存在正整数i和和j，ij,使得：使得：bi=bj即：即： bi=bi*bj-i1174 群与子群群与子群由此可说明由此可说明bj-i是是中的幺元，且这个中的幺元，且这个幺元也在子集幺元也在子集B中。中。 如果如果j-i1，那么由，那么由bj-i=b*bj-i-1 可知可知bj-i-1是是b的逆元，的逆元， 且且bj-i-1

57、B；n如果如果j-i=1，则由，则由bi=bi b可知可知b是幺元，是幺元，n 而幺元是以自身为逆元的。而幺元是以自身为逆元的。因此，因此， 是是的一个子群。的一个子群。1184 群与子群群与子群 定理定理:设设是一个群，是一个群，S是是G的非空的非空子集，如果对于子集，如果对于S中的任意元素中的任意元素a和和b有有a*b-1 S，则，则是是的子群。的子群。1194 群与子群群与子群 证明：先证，证明：先证，G中的幺元中的幺元e也是也是S中的幺元。中的幺元。任取任取 a S， a*a-1 S，而，而a*a-1e，e S 再证，每个元素都有逆元。再证，每个元素都有逆元。 又又e*a-1 S，即，

58、即a-1 S。 最后说明，最后说明，*对对S是封闭的。是封闭的。 a,b S，因，因b-1 S， (b-1)-1 S1204 群与子群群与子群 a*b=a*(b-1)-1 S，而，而(b-1)-1 b a*b S 是是的子群。的子群。结合律是保持的，证毕。结合律是保持的，证毕。1214 群与子群群与子群 例：设例：设G4=p=|pi 0,1， 是上是上的二元运算，定义为，对任意的二元运算，定义为，对任意X=，Y= G4， X Y=， 其中其中 的运算表如图所示：的运算表如图所示： 证明证明, 是群是群 的子群。的子群。 010011101224 群与子群群与子群 例：例： 设设和和都是群都是群

59、的子群，的子群，试证明试证明也是也是的子群。的子群。证明：设任意的证明：设任意的a,b HK，因为，因为和和都是子群，所以都是子群，所以b-1 HK，由于，由于*在在H和和K中的封闭性，中的封闭性，所以所以a*b-1 HK，由定理即得，由定理即得也也是是的子群。的子群。1235 阿贝尔群（阿贝尔群（ Abel group ）和）和循环群（循环群（cyclic group ） 定义：如果群定义：如果群中运算中运算*是可交换是可交换的，则称该群为阿贝尔群（或称为交的，则称该群为阿贝尔群（或称为交换群）。换群）。 例：例： 为阿贝尔群。为阿贝尔群。 1245 阿贝尔群（阿贝尔群（ Abel grou

60、p ）和循）和循环群（环群（cyclic group ）例：离散函数代数系统例：离散函数代数系统是阿贝尔群。是阿贝尔群。Z=1,2,3,4， F=f0 , f1 , f2 , f3 1 2 3 42 3 4 1f2 =1 2 3 43 4 1 2f3 =1 2 3 44 1 2 3f0 =1 2 3 41 2 3 4 f =1255 阿贝尔群和循环群阿贝尔群和循环群由运算表可见：由运算表可见：（1）运算是封闭的；）运算是封闭的；（2）“ ”可结合；可结合； （3）幺元）幺元f0 ；（4）每一个元素均可逆）每一个元素均可逆; （5）以主对角线为对称。）以主对角线为对称。 为阿贝尔群。为阿贝尔群。