离散数学 Algebraic structure

,离散数学,2,数理逻辑：人工智能、程序正确性证明、程序验证等集合论：关系数据库模型图论：数据结构、数据库模型、网络模型等代数结构：软件规范、形式语义、编译系统、编码理论、密码学、数据仓库组合数学：算法分析与设计、编码理论、容错,3,代数结构,5.1代数系统的引入5.2运算及其性质5.3半群5.4群与子群5.5阿贝尔群和循环群5.6置换群和伯恩赛德定理5.7陪集与拉格朗日定理5.8同态与同构5.9环与域,4,代数结构,5.1代数系统的引入5.2运算及其性质5.3半群5.4群与子群5.5阿贝尔群和循环群5.6置换群和伯恩赛德定理5.7陪集与拉格朗日定理5.8同态与同构5.9环与域,5,数学结构的重要作用和意义,自然科学社会科学计算机科学,6,什么是代数系统？,运算：对于集合A，一个从An到B的映射，称为集合A上的一个n元运算。代数系统：集合上定义若干运算而组成的系统称为代数系统。N种运算f1,f2,fn可记为A,f1,f2,fn。问题：请举出几个代数系统的实例。,7,代数结构,5.1代数系统的引入5.2运算及其性质5.3半群5.4群与子群5.5阿贝尔群和循环群5.6置换群和伯恩赛德定理5.7陪集与拉格朗日定理5.8同态与同构5.9环与域,8,封闭性,运算的封闭性：若x，yA，有x*yA，称*在A上是封闭的。说明：*代表任意二元运算符号，以同样的方式可以定义n元运算的封闭性。例如：A=xx=2n，nN，问运算封闭否，呢？,9,结合律,结合律：已知，若x，y，zA，有x*（y*z）=（x*y）*z，称*满足结合律。说明：结合律只定义于二元运算例如：，若a，bA，有a*b=b。证明：*满足结合律,10,交换律,交换律：已知，若x，yA，x*y=y*x，称*满足交换律。例如：设,*定义如下：a*b=a+b-ab，问*满足交换律否？,11,分配律,分配律：设，若x，y，zA有:x*(yz)=（x*y）（x*z）(yz)*x=(y*x)(z*x)，称运算*在上可分配。,例：设A=，二元运算*，定义如左表:,问：分配律成立否？,12,吸收律,吸收律：设，若x，yA有:x*(xy)=x，x(x*y)=x，称运算*和运算满足吸收律。例如:N为自然数集,x,yN，x*y=maxx，y,xy=minx，y试证：*和满足吸收律。,13,等幂律,等幂律：已知A，*，若xA，x*x=x则称*满足等幂律。例如：已知集合s,（s）,。,14,幺元（单位元）和零元,定义5-2.7，5-2.8设*是s上二元运算，er，el，r，e，s，有.若xs，有el*x=x，称el为运算*的左幺元。若xs，有x*er=x，称er为运算*的右幺元。.若xs，有l*x=l，称l为运算*的左零元。若xs，有x*r=r，称r为运算*的右零元。.若xs，有e*x=x，x*e=x称e为运算*的幺元。若xs，有*x=x*=，称为运算*的零元。,15,实例,例：代数系统A=a，b，c，,用下表定义：,则b是左幺元，无右幺元,a是右零元，b是右零元，无左零元;,运算既不满足结合律，也不满足交换律。,16,a）I，xb）（s）,c）N，+问题：以上系统中各运算的幺元和零元分别是什么？,17,幺元和零元的性质,定理5-2.1:设*是s上的二元运算，满足结合律，具有左么元el，右么元er，则el=er=e。证明：推论：二元运算的么元若存在则唯一。证明：,18,幺元和零元的性质（续）,定理5-2.2:设*是s上的二元运算，具有左零元ol，右零元or，则ol=or=o。(证明方法与定理5-2.1类似）推论：二元运算的零元若存在则唯一。定理5-2.2:设A，*是一个代数系统，且集合A中元素的个数大于1。如果该代数系统中存在么元e和零元o,则oe。,19,逆元,定义5-2.9设*是s上的二元运算，e是运算*的么元。、若x*y=e那对于运算*，x是y的左逆元，y是x的右逆元、若x*y=e，y*x=e，则称x是y的逆元，y的逆元通常记为y-1，存在逆元(或左逆无或右逆元）的元素称为可逆的（或左可逆的或右可逆的）,20,实例,a)、代数系统N，+中仅有幺元0有逆元0。在R，中，除零元0外所有元素均有逆元。b)、A=a，b，c，*由下表定义：b是幺元,a的右逆元为c，无左逆元，b的逆元为b，c无右逆元，左逆元为a。,21,逆元的性质,定理5-2.4:对于可结合运算，如果元素X有左逆元，右逆元r，则l=r=x推论：逆元若存在，则唯一。,22,二元运算表与运算性质的关系,1）运算具有封闭性，当且仅当运算表中的每个元素都属于A。2）运算具有可交换性，当且仅当运算表关于主对角线是对称的。3）运算具有等幂性，当且仅当运算表的主对角线上的每一个元素与它所在的行（列）的表头元素相同。4）A关于运算有零元，当且仅当该元素所对应的行和列中的元素都与该元素相同。5)A关于运算有幺元，当且仅当该元素所对应的行和列依次与运算表的行和列相一致。6）设A中有幺元，a和b互逆，当且仅当位于a所在行，b所在列的元素以及b所在行，a所在列的元素都是幺元。,23,代数结构,5.1代数系统的引入5.2运算及其性质5.3半群5.4群与子群5.5阿贝尔群和循环群5.6置换群和伯恩赛德定理5.7陪集与拉格朗日定理5.8同态与同构5.9环与域,24,群论是代数系统中研究得比较成熟的一个分支，在计算机形式语言，自动机理论，编码理论等得到广泛应用。,25,广群、半群和独异点,广群：具有运算封闭性的代数系统A=s，*称为广群。半群：满足运算封闭、结合律的代数系统A=s，*，称为半群，这里*是二元运算。独异点：存在么元的半群称为独异点，也称含么半群(或单位半群或单元半群)。子半群：,26,实例,a)N，x0，1，x是半群，是独异点,且是R，x的子半群,子独异点,R，-不是半群。b)设s=a，b，*定义如右表：即a，b都是右零元。x,y,zsx*ys运算封闭x*（y*z）=x*z=z（x*y）*z=z结合律成立。s，*是一半群，该半群称为二元素右零半群。,27,半群的性质,定理5-3.1设S，*是半群，BS且*在B上是封闭的，那么B，*也是一个半群。通常称B，*是半群S，*的子半群。定理5-3.2有限半群必有等幂元。定理5-3.3独异点运算表中任何两行两列均不相同。定理5-3.4若s，*的么元为e,a，bs，若a，b均有逆元，则a)（a-1）-1=a;b)（a*b）-1=b-1*a-1,28,代数结构,5.1代数系统的引入5.2运算及其性质5.3半群5.4群与子群5.5阿贝尔群和循环群5.6置换群和伯恩赛德定理5.7陪集与拉格朗日定理5.8同态与同构5.9环与域,29,群的定义,定义5-4.1：对二元运算*满足下列四条性质的代数系统A=G，*，称为群。1)运算封闭，即a,b,G，a*bG。2)结合律，即a,b,cG，a*（b*c）=（a*b）*c。3)存在么元e，即aG，e*a=a*e=a。4)G中每个元素存在逆元，即aG，a-1G,使a*a-1=a-1*a=e。,30,有限群和有限群的阶数,定义5-4.2：设G，*为群，若G是有限集，称G，*为有限群，G称为群的阶数，若G是无限集，称G，*为无限群。,31,阿贝尔群,定义5-5.1：设G，*为群，若*满足交换律，称G，*为阿贝尔群(或可交换群或加法群)。（此时，*符号可用+代替，a-1可写为-a，么元e可写为0。）,32,实例,a)I，+是一个群，且为阿贝尔群，证明：I，+运算封闭。普通加法+满足结合律。其中0为么元。aI，-a是a的逆元。,33,b)Q+，x是阿贝尔群,Nk，+k是阿贝尔群,Nk，xk不是群（0没有逆元）。c)设P是集合A的双射函数集合，则P，复合运算是一个群，但不是阿贝尔群。d）运算max，min一般不能用作群的二元运算因为对应运算max，min，逆元不存在。,34,广群、半群、独异点和群,35,群的性质,有关半群和独异点的性质在群中全部成立,如（a*b）-1=b-1*a-1定理5-4.2：若G，*是一个群，则a，bGa）存在唯一的x，使得a*x=b，b）存在唯一的y，使得y*a=b。定理5-4.3（群满足消去律）若G，*是一个群，则a，b，cG，有（a）a*b=a*c=b=c（b）b*a=c*a=b=c,36,群的性质（续）,幺元是唯一的等幂元,37,群的性质（续）,定义5-4.3：有限集合s到s的一个双射，称为s的一个置换。定理5-4.4：群G，*的运算表中的每一行或每一列是G中元素的置换。证：先证运算表中每一行(列)中的元素不能出现二次(单射)。若a*b1=a*b2=k，且b1b2，与可约性矛盾。再证G中任一元素在任一行（列）中均出现（满射）。考察对应于a的那一行，bG，则b=a*（a-1*b），b出现在a那一行，由，任意性得证因G，*中有么元，任二行（列）均不相同（即各个置换均不相同）。,38,群的性质（续）,一阶群、二阶群和三阶群只有一种，四阶群只有两种。问题：为什么？,39,群的性质（续）,定理5-4.1群中不可能有零元。,40,群的性质（续）,定理5-5.1设G，x是一个群，则G，*是阿贝尔群的充要条件是:a，bG，有（a*b）*（a*b）=（a*a）*（b*b）。证：充分性：若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-1b*a=a*b，G，*是阿贝尔群。必要性：若G，*是阿贝尔群，则a，bG，*b=b*a。a*（a*b）*b=a*（b*a）*b，（a*a）*（b*b）=（a*b）*（a*b）。,41,子群,定义5-4.5设(G,*,e,-1)为群，HG，若(1)x,yH则有x*yH，(2)*在H上满足可结合，(3)eH,(4)xH则有x-1H)。则称(H,*)为(G,*)的子群(Subgroup)，记为(H,*)(G,*)，当HG时，称(H,*)为(G,*)的真子群，记为(H,*)(G,*)。,42,有限子群的判定性定理,设是一个群,TG,T是个有限集,若a,bT,有a*bT。则是的子群。证明：,43,子群的判定性定理,是群,TG,若a,bT,有a*bT,a-1T,则是的子群。定理5-4.8是群,TG,若a,bT,有a*b-1T,则是的子群。,44,实例,a)是的子群,I为整数集。b)不是的子群,N是自然数集。c)是的子群。,45,例若，是群的子群，则是的子群。证明:设a,bHK，则a,bH,a,bK,又因为，是群的子群。a*b-1H，a*b-1K。即a*b-1HK。由子群判别法知：是的子群。,46,元素的阶,元素a的幂：给定群,aG,若nN,则定义:a0=e,an+1=ana,a-n=a-1a-1a-1=(a-1)n对m用归纳法可证：aman=am+n(m,nI),对k用归纳法可证：(am)k=amk(m,kI)。,47,元素的阶（续）,元素的阶：设是一个群,aG,若存在正整数n,使an=e,满足该等式的最小正整数n称为元素a的阶,并称元素a具有有限阶n,若不存在这样的正整数n,则称元素a具有无限阶。例.群的幺元e的阶为群中除以0外,其余元素的阶为无限阶。,48,元素的阶一些性质,定理：若群,aG具有有限阶n,则若ak=e,当且仅当k是n的倍数。证明:若k是n的倍数,即k=mn,mI则ak=amn=(an)m=em=e反之,若ek=e则k=mn+t,0tn,mIat=ak-mn=ak*(an)-m=e*(e)-m=e由定义知:n是使an=e的最小正整数因0t1，2),均是阿贝尔群，3)乘法对加法可分配，则称它是域。例如：1)I为整数集，不是域，2)是一个域,其中Q为有理数集合。是一个域，其中R为实数集合。是一个域，其中C为复数集合。,99,实例,证明：Nk=0,1,k-1,是个域,当且仅当k是质数.证明:必要性:（反证法）设是个域,若k不是质数i)k=1,则|N1|=1不是域ii)k=ab,则akb=0,a,b是零因子,故不是域矛盾。充分性:若k为质数,须证是个域。i)是个阿贝尔群，ii)证明是阿贝尔群，a)a,bNk-0akbNk-0，Nk-0对k封闭。b)结合律满足。c)么元为1。d)aNk-0，证明a存在逆元，,100,续:首先证明:若b,cNk-0,bc则akbakc。（反证法:）若akb=akc,不妨设bc，则:ab=nk+r,ac=mk+ra(b-c)=(n-m)k。k为质数,不能被分解成两个数的乘积,故等式左边至少有一个数是k的倍数,而这是不可能的，因此，ak1,ak(k-1)此k-1个数均不相同,其中必有一个为1。所以aNk-0,bNk-0使akb=1，aNk-0，a存在逆元。是阿贝尔群，是个域，证毕。说明：称为模k整数域。,101,域与整环,定理5-9.3：域一定是整环。证明：设是任一域。对于a,b,cA且a,如果有ab=ac,（1是乘法幺元）则b=1b=(a-1a)b=a-1(ab)=a-1(ac)=(a-1a)c=1c=c因此，是一个整环。定理5-9.4：有限整环必是域证明:设是有限整环,a,b,cA且c(证明c逆存在).若ab，由无零因子推出的可约律,则acbc，因为A为有限集,由运算封闭性设A-=a1,an，则A-=ca1,can=c(A-)。cA,d有ad=ec逆元存在为d。是阿贝尔群。因为有限整环满足分配律，是域。,102,环、整环、域的关系,无零因子环,环,含么环,域,有限整环,整环,交换环,103,环的同态,定义5-9.5:设，是环,若h:RS,a,bR有h(a+b)=h(a)h(b),h(ab)=h(a)h(b),称h是到的环同态。,104,环的同态象,定理5-9.5：给定环的同态映射h,则也是一个环。证明：1）从前面的定理可知、分别阿贝尔群、半群。2)对的可分配性。,105,实例,设是一个关于，分别有么元e1和e2的代数系统,且和彼此可分配,试证:xA,xx=xx=x证明:e2e2=e2(e2e2)=(e1e2)(e2e2)=(e1e2)e2=e1e2=e2xx=(xe2)(xe2)=x(e2e2)=xe2=xe1e1=e1(e1e1)=(e1e2)(e1e1)=e1(e2e1)=e1e2=e1xx=(xe1)(xe1)=x(e1e1)=xe1=x.,106,习题,P200,5.试证:循环群的子群是循环群证明：设是的子群,因是循环群,设g是它的生成元,T=gi1,gi2,gin,i是整数,设m是i1,i2,in,中最小的正整数(若i1,i2,in,均为负数,可取m是其中绝对数最小的)gijT,ij=lm+r(lI,0r是循环群。,107,试证:HK=KH当且仅当是的子群。证:1)h1k1,h2k2HK因为HK=KH,h3k3,k1h2=h3k3h1k1h2k2=h1h3k3k2HK2)(h1k1)-1=k1-1h1-1KH=HK(h1k1)-1HK所以是的子群。(1)HKKHxHK,则x-1HK设x-1=hkx=(x-1)-1=(hk)-1=k-1h-1KH(2)KHHKkhKHkh=(h-1k-1)-1HK(是子群)KHHK由(1),(2):KH=HK,108,P200,4)设是一个群,a,bG,a3*b3=(a*b)3,a4*b4=(a*b)4,a5*b5=(a*b)5,则为阿贝尔群。证:a3*b3=(a*b)3a*(a2*b2)*b=a*(b*a)*(b*a)*ba2*b2=(b*a)2因为a3*b3=(b*a)3,a4*b4=(b*a)4(a3*b3)*(b*a)=(b*a)3*(b*a)=(b*a)4=a4*b4,即b4*a=a*b4(1)(a2*b2)*(b*a)=(b*a)2*(b*a)=(b*a)3=a3*b3,即b3*a=a*b3(2)(a*b)*b3=a*b4=b4*a=b*(b3*a)=b*(a*b3)=b*a*b3a*b=b*a,由a,b的任意性,所以为阿贝尔群。,109,(一)设是半群,e是左么元,即xA,x有x*x=e试证明:a)a,b,cA若a*b=a*c则b=cb)e也是的么元,并且是群。证明:a)a*b=a*ca*a*b=a*a*ce*b=e*cb=cb)必须证:xA,x*e=xi)x*(x*e)=(x*x)*e=e*e=e=x*x,由a)得x*e=xe也是的右么元,即e是的么元ii)须证:xA,x*