离散数学课件第六章(第3讲).ppt

《离散数学课件第六章(第3讲).ppt》由会员分享，可在线阅读，更多相关《离散数学课件第六章(第3讲).ppt（17页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、 定义定义设设是一个群，且是一个群，且S G是一个非空集合。若是一个非空集合。若满足下列三个条件，则称满足下列三个条件，则称是是的子群：的子群：（1）e是是的幺元，且的幺元，且e S；（保持幺元）（保持幺元）（2）对任一）对任一 a S一定有一定有a-1 S；（保持逆元）（保持逆元）（3）对任一）对任一a,b S一定有一定有a*b S。（运算的封闭性）（运算的封闭性）注：注：任一群任一群至少可找到两个子群，即至少可找到两个子群，即和和，这两个子群称为平凡子群。，这两个子群称为平凡子群。4 群与子群群与子群例：例：设设是一个群，是一个群，mG，N=gG|m*g=g*m,证明：证明：是是的子群。的

2、子群。定理定理设设是一个群，是一个群，B是是G的非空子集，如果的非空子集，如果B是一个有限集，那么，只要运算是一个有限集，那么，只要运算*在在B上是封闭的，则上是封闭的，则必定是必定是的子群。的子群。证明：设证明：设 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-i=bj-i*bi由此可说明由此可说明bj-i是是中的幺元，且这个幺元也中的幺元，且这个幺元也 在子集在子集B中。中

3、。如果如果j-i1，那么由，那么由bj-i=b*bj-i-1=bj-i-1*b可知可知bj-i-1是是b的逆元，的逆元，且且 bj-i-1 B；如果；如果j-i=1，那么由，那么由bi=bi*b=b*bi可知可知b就是幺元就是幺元,且且 以自身为逆元。以自身为逆元。因此，因此，是是的一个子群。的一个子群。例：设例：设G4=p=|pi 0,1，是上的二元是上的二元 运算，运算，定义为：定义为：对任意对任意X=，Y=G4，X Y=，其中其中 的运算表如图所示：的运算表如图所示：证明证明,是群是群的子群。的子群。01001110定理定理:设设是一个群，是一个群，S是是G的非空子集，如果对于的非空子集

4、，如果对于S中中的任意元素的任意元素a和和b有有a*b-1 S，则，则是是的子群。的子群。证明：证明：先证，先证，G中的幺元中的幺元e也是也是S中的幺元。中的幺元。任取任取 a S，a*a-1 S，而，而a*a-1e，e e S 再证，每个元素都有逆元。再证，每个元素都有逆元。又又e*a-1 S，即，即a-1 S。最后证明，最后证明，*对对S是封闭的。是封闭的。a,b S，因，因b-1 S，(b-1)-1 S a*b=a*(b-1)-1 S，而，而(b-1)-1 b a*b S 是是的子群。的子群。例：设例：设和和都是群都是群的子群，试证明的子群，试证明也是也是的子群。的子群。5 阿贝尔群和循

5、环群阿贝尔群和循环群定义定义如果群如果群中运算中运算*是可交换的，则称该群是可交换的，则称该群为阿贝尔群（或称为交换群）。为阿贝尔群（或称为交换群）。例：例：为阿贝尔群。为阿贝尔群。由运算表可知：由运算表可知：（1）运算是封闭的；）运算是封闭的；（2）“”可结合；可结合；（3）幺元）幺元 为为f0；（4）每一个元素均可逆）每一个元素均可逆;（5）以主对角线为对称。）以主对角线为对称。为阿贝尔群。为阿贝尔群。f0f1 f2 f3f0f0f1 f2 f3f1f1 f2 f3f0f2 f2 f3f0f1f3f3f0f1f2 例：离散函数代数系统例：离散函数代数系统是阿贝尔群。是阿贝尔群。F=f0 ,

6、f1 ,f2 ,f3 定理定理设设是一个群，是一个群，是阿贝尔群的充分是阿贝尔群的充分必要条件是对任一必要条件是对任一a,b G有有：(a*b)*(a*b)=(a*a)*(b*b)。证明：证明：（1）充分性：）充分性：(a*b)*(a*b)=(a*a)*(b*b)是阿贝尔群。是阿贝尔群。对任意对任意a,b G有有(a*b)*(a*b)=(a*a)*(b*b)成立，成立，*是可结合的，且是可消去的，是可结合的，且是可消去的，a*(a*b)*b=a*(b*a)*b 则则 a*b=b*a 是阿贝尔群。是阿贝尔群。（2）必要性：）必要性：是阿贝尔群是阿贝尔群(a*b)*(a*b)=(a*a)*(b*b

7、)。阿贝尔群满足交换律，对任一阿贝尔群满足交换律，对任一a,b G有有a*b=b*a，(a*a)*(b*b)=a*(a*b)*b=a*(b*a)*b=(a*b)*(a*b)推论推论在阿贝尔群中，对任一在阿贝尔群中，对任一a,b G有有 (a*b)1 =b-1*a-1=a-1*b-1定义定义设设是一个群，是一个群，I 是整数集合，若存在一个元是整数集合，若存在一个元素素g S，对于，对于S中每一个元素中每一个元素a都能表示成都能表示成gn的形式（的形式（n I），则称），则称是一个循环群，是一个循环群，g称为群称为群的生的生成元。成元。例：设例：设M=0,60,120,240,300,180表示

8、平面上几何图形表示平面上几何图形顺时针旋转的六种位置，定义一个二元运算顺时针旋转的六种位置，定义一个二元运算*，对，对M中任一中任一元素元素a,b有有a*b=图形旋转图形旋转(a+b)的角度，并规定当旋转到的角度，并规定当旋转到360时即为时即为0，试验证群，试验证群是一个循环群。是一个循环群。*060120180240300006012018024030060601201802403000120120180240300060180180240300060120240240300060120180300300060120180240证明：证明：60=601 120=60*60=602180=1

9、20*60=603 240=180*60=604300=240*60=605 0=300*60=606存在一个元素存在一个元素60 M，对于，对于M中每一个元素中每一个元素 都能表示成都能表示成60n的形式（的形式（n I），所以），所以是一个循环群，是一个循环群，60是是循环群循环群的生成元。的生成元。定理定理每一个循环群必然是阿贝尔群。每一个循环群必然是阿贝尔群。证明：设证明：设是一循环群，是一循环群，g为生成元，为生成元，对任意对任意p,q S，一定存在一定存在 i,j I（整数集）使得（整数集）使得p=gi,q=gj，则则p*q=gi *gj=gi+j =gj *gi=q*p。循环群一

10、定是阿贝尔群。循环群一定是阿贝尔群。定理定理设设是由元素是由元素g S生成的循环群，若生成的循环群，若是是n阶的（即阶的（即|S|=n），则），则gn=e，且，且S=g1,g2,gn =e，而且，而且n是能使是能使gn =e的最小正整数。的最小正整数。在上例中，设在上例中，设是循环群，是循环群，60 是循环群是循环群的生成元。的生成元。是是6阶的循环群（即阶的循环群（即|M|=6），则），则606=0（幺元），且（幺元），且M=601,602,606 =e，使使gn =e成立成立的最小正整数的最小正整数n为为6。例：例：为一循环群为一循环群,S中元素中元素和和*运算见运算表：运算见运算表：c1=c,c2=b,c3=d,c4=a(幺元幺元)d1=d,d2=b,d3=c,d4=a(幺元幺元)a1=a,a2=a,a3=a,a4=a b1=b,b2=a,b3=b,b4=a 由上可知：生成元为由上可知：生成元为c,d，而，而a,b不是生成元。生成元不是生成元。生成元 c,d的阶为的阶为4，等于循环群，等于循环群的阶。的阶。*abcdaabcdbbadcccdbaddcab