《离散数学PPT教学 群论》由会员分享，可在线阅读，更多相关《离散数学PPT教学 群论（34页珍藏版）》请在金锄头文库上搜索。
1、 欢迎进入离 散 数 学 第 八章 群 论近世代数 第八章 群 论8.1 半群和独异点8.2 群、阿贝尔群及性质结束8.3 循环群和置换群8.4 群的同态和同构例1a)N，x0，1，x是半群，是独异点,且是R，x的子半群,子独异点,R，-不是半群* a b a a b b a b8.1 半群和独异点b) 设s=a，b，*定义如右表： 即a，b都是右零元x,y,zs x*ys 运算封闭 x*（y*z）=x*z=z（x*y）*z=z结合律成立s，*是一半群，该半群称为二元素右零半群 1、有限半群必有等幂元 证明：设s，*是半群有限集，需证 as，有a*a=abs ，因为运算封闭， b2=b*bs
2、b3，b4ss有限 ，j，j 有bi=bj bi =bj =bj- i * bi令p=ji 当qi ,bq=bpbq （）又p1 k 有k p i 由（） bkp=bp*bkp=bP*(bP*bkp)=bkpbkp令a=bkps 则a*a=a bkp是等幂元二、半群的性质二、半群的性质2、独异点运算表中任何两行两列均不相同证明：设独异点的么元为e，a，bs，aba*eb*e ，运算表中，两行不同，由，任意性，运算表中任两行不同 e*ae*b ，运算表中，二列 不同由，任意性，运算表中任两列不同二、半群的性质二、半群的性质3、若s，*的么元为e,a，bs，若a，b均有逆元，则 a)（a-1）-1
3、=a ; b)（a*b）-1=b-1*a-1 证明：a) a*a-1=e a是a-1的左逆元a-1*a=e a是a-1的右逆元(a-1)-1=ab) (a*b)*(b-1*a-1)=a*(b*b-1)*a-1=a*e*a-1=eb-1*a-1是a*b的右逆元又（b-1*a-1）*（a*b）=b-1*（a-1*a）*beb-1*a-1是a*b的左逆元（a*b）-1=b-1*a-1返回目录群论是抽象代数发展充分的一个分支，广泛应用 于计算，通讯，计算机科学，是我们这一章的重点 。8.2 群、阿贝尔群及性质一、 群的定义1、定义：对二元运算*满足下列四条性质的代数系统A=G，*，称为群1) 运算封闭
4、，即a,b,G， a*b G2) 结合律，即a,b,cG，a*（b*c ）= （a*b）*c3) 存在么元e，即aG，e*a=a*e=a4) G中每个元素存在逆元即aG，a-1 G,使a*a-1=a-1*a=e若G是有限集，称G，*为有限群，G 称为群的阶数，若G是无限集，称G，*为 无限群一、 群的定义2、有限群3、阿贝尔群若*满足交换律，称G，*为阿贝尔群， 或可交换群或加法群，（此时，*符号可用 +代替，a-1可写为-a，么元e可写为0）例1I，+是一个群。考虑是否为阿贝尔群 ？证明：I，+运算封闭 普通加法+满足结合律 其中0为么元 aI，-a是a的逆元一、 群的定义b)Q+，x是阿贝
5、尔群,Nk，+k是阿贝尔群,Nk，xk 不是群（0没有逆元）一、 群的定义c) 设P是集合A的双射函数集合，则P，复合运算是一个群，但不是阿贝尔群d）运算max，min一般不能用作群的二元运算 因为对应运算max，min，逆元不存在 二、 群的性质二、 群的性质1、有关半群和独异点的性质在群中全部成立,（a*b）-1=b-1*a-1 阿贝尔群半群 独异点群若G，*是一个群，则a，bGa）存在唯一的x，使得a*x=bb）存在唯一的y，使得y*a=b 证：a）存在性:令x=a-1*b，则a*(a-1*b)=a*a-1*b=e*b=b唯一性:若a*x=b，则a-1*a*x=a-1*b x=a-1*b
6、b）略 二、 群的性质2、Th2:3、 可逆必可约，反之不成立Th3:（a） a*b=a*c = b=c（b） b*a= c *a = b=c证： a*b=a*c = a-1*（a*b）=a-1*（a*c） = b=c二、 群的性质4、Th5: 么元是群中唯一的等幂元证：若x是等幂元素，则：x=e*x=（x-1*x）*x= x-1*（x*x）x-1*x=e二、 群的性质5、Th4:群G，*的运算表中的每一行或每一列是G中元素的置换定义：有限集合s到s的一个双射，称为s的一个 置换 定理：群G，*的运算表中的每一行或每一列是G中元素的置换证： 先证运算表中每一行（列）中的元素不能出现二次（单射）
7、二、 群的性质若a*b1=a*b2=k，且b1b2，与可约性矛盾 再证G中任一元素在任一行（列）中均出现（满 射）考察对应于a的那一行，bG，则b=a*（a-1*b） b出现在a那一行，由，任意性得证因G，*中有么元，任二行（列）均不相同 （即各个置换均不相同） 证毕6、 有限群举例 一阶群仅有1个 二阶群仅有1个 三阶群仅有1个 四阶群仅有2个（证略） * e e e* e a e e a a a e *e a b e e a b a a b e b b e a二、 群的性质7、Th1:群中不可能有零元证：当G=1，它的唯一元素视为么元当G1且G，*有零元，则xG，都有x*=*x=e无逆元，
8、这与G是群矛盾二、 群的性质8、 设G，x是一个群，则G，*是阿贝尔 群的充要条件是证：充分性：若a，bG，因为满足交换律有(a*b)*(a*b)=(a*a)*(b*b)反之，a-1*(a*b)*(a*b)*b-1=a-1*(a*a)*(b*b)*b-1 b*a=a*bG，*是阿贝尔群二、 群的性质a，bG，有（a*b）*（a*b）=（a*a）*（b*b）必要性：若G，*是阿贝尔群，则a，bG，*b=b*aa*（a*b）*b=a*（b*a）*a（a*a）*（b*b）=（a*b）*（a*a） 二、 群的性质8.3 循环群和置换群一.循环群定义定义:设是一个群,若存在gG,使得 aG,iI（I为整
9、数集），有a=gi,则称 是一个循环群, g是的生成元。可 称是由g生成的, 。二.性质1. 每个循环群是阿贝尔群证:设g是的生成元则a,bG, a=gr, b=gsa*b=gr*gs=gr+s=gs*gr=b*a下一页2.是由g生成的有限循环群,若 |G|=n,即g的阶为n,则G=g1,g2,gn证:a) 证g的阶为n。先证：若m是一个群,故必有么元， gn=eG=g0 ,g1 , g2 , ,gn-1下一页例1例1.a)是无限循环群,其中-1,1均是生成元b)是无限循环群,其中-5,5是均生成元c)Nk=0,k-1，是有限循环群,其中1是 生成元,与k互质的任一数也是生成元，这里Nk=0,
10、k -1,x是I中的模k等价类+k定义为:x+ky=x+y+4 0 1 2 3 30 0 1 2 3 32=6=2 1 1 2 3 0 33=5=1 2 2 3 0 1 34=4=0 3 3 0 1 2下一页二.循环群性质例2.设G=,，证是循环群 * 证: 2=, 3=,4=运算表可改写如下:* 2 3 2 3 2 3 2 2 2 3 3 2由上表看出G=,是一个循环群下一页置换群三、置换群一.复合运算1.定义:一个具有n个元素的集合S,将S上所有n!个 不同的置换所生成的集合记作Sn例:A=1,2有二个置换1= 1 2 2= 1 21 2 2 1A=1,2,3有6个置换P0 p1 p2 p
11、3 p4 p5 123 123 123 123 123 123 123 213 321 132 231 312下一页二元运算二元运算pipj表示先进行置换pj,再进行置换pi,称左复合pipj表示先进行置换pi,再进行置换pj,称右复合例:左复合123 123 123 =321 213 231右复合123 123 123 =321 213 312下一页是一个群 证:(1)封闭性p1,p2Sn，须证p1p2Sn若a,bS且ab则当a,b被p2置换为c,d时,必有cd当c,d被p1置换为e,f时,必有efp1p2将S中任二个不同元素映射到S中的二个不同元素p1p2Sn(有限集A上的单射必为满射)(
12、2)运算满足结合律p1，p2，p3Sn,xS有p3(x)=y ，p2(y)=z, p1(z)=u,则(p1p2)p3(x)=u,p1(p2p3)(x)=p1(z)=up1(p2p3)=(p1p2)p3(3)恒等置换为么元(4)pSn,xS,存在逆元p-1,其中若p(x)=y则p-1(y)=x. 所以，是一个群下一页例:p1= 123 p1-1= 123 p1p1-1= 123312 231 123 四、置换群与对称群定义:的任何子群称为集合S上的一个置换群称为S上的对称群。 例:设S=1,2,3，试写出S的所有的置换群及对称群 解: S上对称群Sn=p0,p1,p2,p3,p4,p5置换群以p
13、1为生成元的对称群,以p2为生成元对称群以p3为生成元对称群,以p4为生成元对称群。下一页同态与同构8.4 群的同态与同构一.同构与同态1.同构定义代数A=和A=若1)存在从S到S的双射函数h2)a,bS有h(a*b)=h(a)*h(b)则称代数A与代数A是同构 的,记为注:1)A与A同构,则调换符号能从A得到A,可以认为它们 是相同的代数;2)若e是A的么元,则h(e)是A的么元 yS,xS,y=h(x)y* h( e)=h(x) * h(e)=h(x*e)=y若o是A的零元,则h(o)是A的零元下一页一.同构与同态例1.证同构于证:i)令h:R+R,h(x)=x则因对数函数单调增h是单射yR,x=2y使y=2y =h(x) h是满射h是从R+到R的双射ii)h(ab)=（ab）=a+b=h(a)+h(b)同构于下一页一.同构与同态例2.证明和不同构 证:反证法设h是到的一个同构映射,x2则: p=h(x)=h(x+0)=h(x)h(0)1)7=h(7)=h(7+0)=h(7)h(0)h(7)=1或h(0)=12)7=h(7)=h(6+1)=h(6)h(1) h(6)=1或h(1)=11至少是两个元素的象, 这与h是双射矛盾 和不同构下一页证:G=g0,g1,g2,g3, f:
