离散数学第五章代数结构

离散数学课件第五章代数结构第一页，共五十八页，编辑于2023年，星期一证明:1）充分性

a,bG，有(ab)(ab)=(aa)(bb)左端=a(ba)b右端=a*(a*b)*b即a(ba)b=a(ab)b由可约性得，用a-1左上式，再用b-1右上式，得(ab)=(ba)

2）必要性从“<G,>是阿贝尔群”的结论出发，推出“(ab)(ab)=(aa)(bb)”。（证略）第二页，共五十八页，编辑于2023年，星期一补充：元素的阶（a的阶，记为|a|）1．元素a的幂的定义定义：给定群<G,*>,aG,若nN,则定义:a0=e,an+1=an*a,a-n=a-1*a-1**a-1=(a-1)n=(an)-1对m用归纳法可证：am*an=am+n(m,nI),对k用归纳法可证：(am)k=amk(m,kI)第三页，共五十八页，编辑于2023年，星期一补充：元素的阶（a的阶，记为|a|）2．元素a的阶的定义设<G，*>是群，aG能够使am=e的最小正整数m，称为a的阶。若m不存在，则说a是无阶的。例1：在整数加群<z,+>中，0的阶是1，其余元素均无阶。例2：在群<{1,-1},*>中，-1的阶是2，1的阶是1。例3：在整数加群<z6,+6>中，求各元素的阶：123450632361第四页，共五十八页，编辑于2023年，星期一循环群与生成元定义5-5.2设<G,>为群，如果在G中存在元素a,使得G中的任何元素都可表示为a的幂（约定a0=e,ak=a*a*…*a(k个)）,称<G,>为循环群，这时a称为循环群G的生成元。例1：整数加群<I,+>是循环群，其生成元为。计算群的生成元是判别一个群是否为循环群的关键。1和-1第五页，共五十八页，编辑于2023年，星期一循环群举例例：循环群<{0°,60°,120°,180°,240°,300°}，★>，0o是该循环群的幺元。60o是该循环群的生成元。(60o)1=60o,(60o)2=60o★60o=120o,(60o)3=60o★60o★60o=180o,(60o)4=240o,(60o)5=300o(60o)6=0o=e,(60o)7=60o,(60o)8=120o,……a★b表示平面图形连续旋转a和b得到的总旋转角度，并规定旋转360°等于原来的状态。300°也是生成元：300°,240°,180°,120°,60°,0°第六页，共五十八页，编辑于2023年，星期一循环群的性质定理5-5.2任何一个循环群必定是阿贝尔群。证设<G,>是一个循环群，a是该群的生成元，则对于任意的x,yG，必有r,sI，使得

x=ar和y=as

而且xy=aras=ar+s=as+r=asar=yx因此，运算可交换，是阿贝尔群。第七页，共五十八页，编辑于2023年，星期一循环群中生成元的阶（周期）定理5-5.3

设<G,>为循环群，aG是该群的生成元，如果G的阶数是n，即|G|=n，则an=e,且

G={a,a2,a3,...,an-2,an-1,an=e}其中，e是群<G,>的幺元。n是使得an=e成立的最小正整数，称为元素a的阶或周期。第八页，共五十八页，编辑于2023年，星期一定理5-5.3的证明证明思路:先证a的阶为n。设对于某个正整数m,m<n,有am=e。那么，由于<G,>是一个循环群，所以对于G中任意的元素都能写为ak(kI),而且k=mq+r,其中q是某个整数,0≤r<m,则有ak=amq+r=(am)qar=(e)qar=ar因此，G中每一元素都可写成ar，G中最多有m个元素。与|G|=n矛盾。所以am=e是不可能的。

再用反证法证明a，a2，...，an互不相同。设ai=aj，其中1≤i<j≤n，就有aj-i=e，而且1≤j-i<n，这已经有上面证明是不可能的。第九页，共五十八页，编辑于2023年，星期一循环群中生成元的阶例1：循环群<{0°,60°,120°,180°,240°,300°}，★>，60o是生成元；e=0o；6是使(60o)n=e的最小正整数，故60o的周期(阶)为6。例2：<{5j|jI},+>是无限循环群,其中-5,5是均生成元。同理，300°的阶也是6。第十页，共五十八页，编辑于2023年，星期一例3：循环群<Nk，+k>，其中Nk={[0],,[k-1]}，[x]表示N中的模k等价类，[x]+k[y]=[(x+y)modk]。求<N4，+4>的幺元、生成元，并求生成元的周期。解：任意[x]N4，必有[x]+4[0]=[x]，故[0]为该群的幺元；[1]和[3]都是生成元，周期都是4。([1])1=[1],([1])2=[2],([1])3=[3],([1])4=[0]([3])1=[3],([3])2=[2],([3])3=[1],([3])4=[0]思考：为什么[2]不是生成元？<N5，+5>的生成元？第十一页，共五十八页，编辑于2023年，星期一例4：设G={α,β,γ,δ}，*的运算表如下，证<G,*>是循环群。*αβγδααβγδββαδγγγδβαδδγαβ

证：从运算表可验证<G,*>是群。从表中可看出α是幺元。γ：γ2=β,γ3=δ,γ4=αδ：δ2=β,δ3=γ,δ4=αβ：β2=α,β3=β，β4=α故生成元为：γ，δ故<G,*>是循环群。第十二页，共五十八页，编辑于2023年，星期一练习1证明：循环群的任何子群必定也是循环群。证设<G,*>是循环群，其生成元是a。设<S,*>是<G,*>的子群，且S≠{e}。那么，存在最小正整数m，使得amS，对于任意的aiS，必有i=tm+r

(tI+，0≤r<m)，故ar=ai-tm=ai*(amt)-1S。又因为m是使amS的最小正整数，所以r只能取值为0，所以i=tm，即ai=(am)t。这说明，S中任一元素都是am的乘幂。因此，<S,*>是以am为生成元的循环群。第十三页，共五十八页，编辑于2023年，星期一练习2设<G,*>是一个独异点，并且对于G中的每一个元素x都有x*x=e，其中e是幺元，证明<G,*>是一个阿贝尔群。证

1)证G中每个元素均有逆元。∵任意xG都有x*x=e，故x-1=x。

2)证运算满足交换律。∵任意a,bG都有(a*b)-1=a*b∴a*b=(a*b)-1=b-1*a-1=b*a∴运算满足交换律。综上所述，<G,*>是一个阿贝尔群。第十四页，共五十八页，编辑于2023年，星期一练习3设G={[1],[2],[3],[4],[5],[6]}，G上的二元运算×7如表所示。问<G,×7>是循环群吗？若是，求其生成元。×7[1][2][3][4][5][6][1][1][2][3][4][5][6][2][2][4][6][1][3][5][3][3][6][2][5][1][4][4][4][1][5][2][6][3][5][5][3][1][6][4][2][6][6][5][4][3][2][1]生成元为：[3],[5]第十五页，共五十八页，编辑于2023年，星期一5-7陪集与拉格朗日定理(群的分解)定义5-7.1设<G,>为群,A,Bρ(G),且A≠Φ，B≠Φ，记AB={ab

aA,bB}和A-1={a-1

aA}

分别称为A，B的积和A的逆。定义5-7.2设<H，>为<G，>的子群，那么对任一aG，称aH={a*h｜h∈H}为H的左陪集(leftcoset),记为aH;称Ha={h*a｜h∈H}为H的右陪集(rightcoset),记为Ha。第十六页，共五十八页，编辑于2023年，星期一陪集举例例1.求出<N6,+6>关于子群<{[0],[3]},+6>的所有左陪集,右陪集。解:令H={[0],[3]},则左陪集:右陪集:[0]H={[0],[3]}=[3]HH[0]={[0],[3]}=H[3][1]H={[1],[4]}=[4]HH[1]={[1],[4]}=H[4][2]H={[2],[5]}=[5]HH[2]={[2],[5]}=H[5]从中可以看出：{[0]H,[1]H,[2]H}是G的一个划分。第十七页，共五十八页，编辑于2023年，星期一陪集的性质设<H,*>是<G,*>的子群,a,bG则aH=bH或aH∩bH=Ф。证:对于aH和bH，只有两种情况：

①

aH∩bH=Ф②aH∩bH≠Ф对于第二种情况，设faH∩bHh1，h2H，使f=a*h1=b*h2a=b*h2*h1-1bHxaH则h3H,x=a*h3=b*h2*h1-1*h3bHaHbH，同理bHaHaH=bH第十八页，共五十八页，编辑于2023年，星期一拉格朗日定理定理5-7.1(拉格朗日定理)

设<H，>为有限群<G，>的子群，|G|=n,|H|=m,那么|G|/|H|=n/m是整数，即m|n。

第十九页，共五十八页，编辑于2023年，星期一拉格朗日定理的推论推论1任何质数阶的群不可能有非平凡子群。推论2

设<G,>为n阶有限群，那么对于任意aG,a的阶必是n的因子且必有an=e,这里e是群<G,>的幺元。如果n为质数，则<G,>必是循环群。第二十页，共五十八页，编辑于2023年，星期一拉格朗日定理推论2的证明证:若aG的阶是r,则{e,aa2,a3,…,ar-1}是G的子群且该子群的阶为r，由拉格朗日定理可知r整除n，所以a的阶必是n的因子。故n=rt(tI+),故an=e。设<G,*>为质数阶群，则aG且ae，∵a的阶数可整除|G|,但是|G|为质数,所以a的阶数等于群的阶数。∴{a,a2,,ar}=G

∴

<G,*>是循环群第二十一页，共五十八页，编辑于2023年，星期一拉格朗日定理练习例1.试证奇数阶群所有元素之积等于幺元。证:设<G,*>是一个群,e为幺元,则在G中不存在这样的元素a：ae，a=a-1∵若a=a-1则a2=e<{a,e},*>是<G,*>的子群又因为|{a,e}|=2，所以由拉格朗日定理可得：2整除|G|，这与G是奇数阶群矛盾。

所以，∀a∈G，若a≠e,a、a-1总是成对出现

G={e,a1,a1-1,a2,a2-1,,an,an-1}，其中aiai-1

e*a*a1-1**an*an-1=e第二十二页，共五十八页，编辑于2023年，星期一拉格朗日定理练习例2.任何一个四阶群只可能是循环群或者Klein四元群。（P211）证设四阶群为<{e,a,b,c},*>。其中e是幺元。当四阶群含有一个四阶元素时，这个群就是循环群。当四阶群不含有四阶元素时，则由推论2可知，除幺元e外，a,b,c的阶一定都是2（幺元是唯一的一阶元）。a*b不可能等于a,b或e，否则根据消去律，将导致b=e,a=e或a=b的矛盾。所以a*b只能等于c。同样地有b*a=c以及a*c=c*a=b,b*c=c*b=a。因此，这个群是Klein四元群。第二十三页，共五十八页，编辑于2023年，星期一四阶群（只有两个）Klein四元群：eeabceeabcaaecbbbceaccbae四阶循环群：eeabceeabcaabcebbceacceab第二十四页，共五十八页，编辑于2023年，星期一练习：P211-(5)1、证A非空设<G,*>的幺元为e，则有e*H*e-1=H故e∈A.2、证∀a,b∈A，a*b-1∈A

=H,故a*b-1∈A第二十五页，共五十八页，编辑于2023年，星期一练习：P211-(8)apt-1(apt-1)p第二十六页，共五十八页，编辑于2023年，星期一5-8同态与同构定义5-8.1设<A,★>和<B,>是两个代数系统，f是从A到B的一个映射，a1,a2A，有

f(a1★a2)=f(a1)f(a2)（先算后映=先映后算）则称f为由代数结构<A,★>到<B,>的同态映射，称<A,★>同态于<B,>，记为A~B。称<f(A),>为<A,★>的一个同态象。其中

f(A)={x|x=f(a),aA}B第二十七页，共五十八页，编辑于2023年，星期一（G，*)(S，o)a●b●a*b●f(a)●f(b)●f(a)of(b)●同态象f通过映射建立了两个代数系统之间的联系。第二十八页，共五十八页，编辑于2023年，星期一同构(同态双射)定义5-8.2当同态映射f分别是入射（单射）、满射、双射时，分别称f是单一同态、满同态、同构映射。如果存在一个从<A,★>到<B,*>的同构映射,则称代数系统<A,★>与<B,*>同构,记作A≌B。定义5-8.3设<A,★>是一个代数系统，如果f是<A,★>到<A,★>的同态,称f为A的自同态。如果ｇ是<A,★>到<A,★>的同构,称f为A的自同构。第二十九页，共五十八页，编辑于2023年，星期一同构举例例１：设H={x|x=dn,dI+,nI},定义映射f:I->H

为对任意I，有f(n)=dn，那么，f是<I,+>到<H,+>的一个同构，即I≌H。例２：设fk:I

I,fk(x)=kx，其中I为整数集合。∵fk(x1+x2)=k(x1+x2)=k*x1+k*x2=fk(x1)+fk(x2)fk是从<I,+>到<I,+>的自同态,若k0,则fk是单一同态,若k=1,则fk是<I,+>到<I,+>的自同构。第三十页，共五十八页，编辑于2023年，星期一同构举例证明：设f:NNk(k>0)，f(x)=xmodk。证明f是<N,+>到<Nk,+k>的满同态。证：设x1=lk+h1,x2=mk+h2(h1,h2<k)则∵f(x1+x2)=(x1+x2)modk=(h1+h2)modk=h1+kh2=

f(x1)+kf(x2)∴f(x1+x2)=f(x1)+kf(x2)

∴f是同态。又因为f是满射

∴f是<N,+>到<Nk,+k>的满同态。第三十一页，共五十八页，编辑于2023年，星期一同态象的性质定理5-8.2设f是由<A,★>到<B,>的一个同态映射。（a）如果<A,★>是半群，那么在f作用下，同态象<f(A),>也是半群。（b）如果<A,★>是独异点，那么在f作用下，同态象<f(A),>也是独异点。（c）如果<A,★>是群，那么在f作用下，同态象<f(A),>也是群。第三十二页，共五十八页，编辑于2023年，星期一定理5-8.2的证明证明思路:先证（a）：<f(A),>是半群证运算在f(A)上封闭

设<A,★>是半群，<B,>是一个代数结构，如果f是由<A,★>到<B,>的一个同态。则f(A)

B。对于任意的a，bf(A)，必有x,yA，使得

f(x)=a,f(y)=b。在A中必有z=x★y,所以ab=f(x)f(y)=f(x★y)=f(z)f(A)第三十三页，共五十八页，编辑于2023年，星期一证在f(A)上满足结合律对于任意的a,b,cf(A),必有x,y,zA,使得f(x)=a,f(y)=b,f(z)=c因为在A上是可结合的，所以a(bc)=f(x)(f(y)f(z))=f(x)f(y★z)=f(x★(y★z))=f((x★y)★z)

=f(x★y)f(z)

=(f(x)f(y))f(z)=(ab)c故<f(A),>是半群。

第三十四页，共五十八页，编辑于2023年，星期一再证（b）：<f(A),>是独异点设<A,★>是独异点,e是A中的幺元,那么f(e)是f(A)中的幺元。因对于任意的af(A),必有xA,使得f(x)=a所以af(e)=f(x)f(e)=f(x★e)=f(x)=a=f(e★x)=f(e)f(x)=f(e)a因此f(e)是<f(A),>中的幺元，<f(A),>是独异点。第三十五页，共五十八页，编辑于2023年，星期一最后证（c）：<f(A),>是群设<A,★>是群,对于任意的af(A),必有xA,使得f(x)=a因为<A,★>是群,所以对于任意的xA,都有逆元x-1A，且f(x-1)f(A),而

f(x)f(x-1)=f(x★x-1)=f(e)=f(x-1★x)=f(x-1)f(x)所以，f(x-1)是f(x)的逆元。即f(x-1)=（f(x)）-1因此<f(A),>中的任意元素都有逆元,<f(A),>是群。综合上述(a)、(b)、(c)三步，定理证毕第三十六页，共五十八页，编辑于2023年，星期一同态核定义5-8.4如果f为代数结构<G,★>到<G’,>的一个同态映射，G’中有么元e’，那么称下列集合为f的同态核，记为K(f)。

K(f)={xxG∧f(x)＝e’}第三十七页，共五十八页，编辑于2023年，星期一同态核的性质定理5-8.3设f为群<G,★>到群<G’,>的同态映射，那么f的同态核K是G的子群。证明思路:设e是<G,★>的幺元，e’=f(e),故eK。证★运算在K上封闭。设k1,k2K,则f(k1★k2)=f(k1)f(k2)=e’e’=e’故k1★k2K，★运算在K上封闭。

证K中的元素有逆元。对任意的kK,f(k-1)=[f(k)]-1=e’-1=e’故k-1K。结论得证。第三十八页，共五十八页，编辑于2023年，星期一同态核举例例:f:<I,+><N5,+5>,xN,f(x)=xmod5则x,yI,f(x+y)=(x+y)mod5=xmod5+5ymod5=f(x)+5f(y)f是从<I,+>到<N5,+5>的同态ker(f)={x|xIf(x)=0}={0,5,-5,10,-10,}第三十九页，共五十八页，编辑于2023年，星期一代数结构的划分——同余关系显然整数集合I上的模k余数相等关系R是等价关系。容易证明，对于a,b,c,dI，R对整数上的加运算满足性质：若x≡y(modk)且z≡w(modk),则(x+z)≡(y+w)(modk),称这种特殊的等价关系为同余关系。

将上述同余关系推广，则得到代数结构上一般意义的同余关系。第四十页，共五十八页，编辑于2023年，星期一同余关系与同余类定义5-8.5

设R为<A,★>中A上的等价关系，若<a1,a2>R,<b1,b2>R<a1★b1,a2★b2>R则称R为A上关于二元运算★的同余关系。由这个等价关系将集合划分成的等价类就称为同余类。例：1、前例<I,+>上的模k余数相等关系就是同余关系。2、<I,*>上的恒等关系R是同余关系；第四十一页，共五十八页，编辑于2023年，星期一例：<I,+>，在I上定义R:<x,y>R|x|=|y|,R是<I,+>的同余关系吗?解:1)自反性：xI,|x|=|x|<x,x>R2)对称性：x,yI,若<x,y>R则|x|=|y|

<y,x>R3)传递性：x,y,zI，若<x,y>R,<y,z>R则|x|=|y|=|z|<x,z>R

R是一等价关系

x1,y1,x2,y2I，若<x1,y1>R,<x2,y2>R，但<x1+x2,y1+y2>R不一定成立。例<1,-1>,<2,2>R，但<1+2,-1+2>R,

R不是同余关系第四十二页，共五十八页，编辑于2023年，星期一同余关系与划分类似于集合论中等价关系及其相应的划分，同余关系所得到的等价类称为同余类，同余类的集合是同余关系所诱导的一个划分。例：课本P218例6。代数系统<A,★>,A上的★运算见表5-8.5，在A上定义的等价关系R见表5-8.6。（1）R是A上关于★的同余关系。如何验证？

<a1,a2>R,<b1,b2>R<a1★b1,a2★b2>R（2）R将A划分为同余类：{a,b}、{c,d}（3）R诱导的一个划分为：{{{a,b},{c,d}}

第四十三页，共五十八页，编辑于2023年，星期一★abcdaaadcbbacdccdabdddbaabcda√√b√√c√√d√√第四十四页，共五十八页，编辑于2023年，星期一练习P222(11):设f和g都是群<G1,★>到群<G2,*>的同态，证明<G,★>是<G1,★>的一个子群，其中G={x|xG1且f(x)=g(x)}第四十五页，共五十八页，编辑于2023年，星期一证：(1)证G是G1的非空子集设群<G1,★>的幺元为e，则f(e)是群<G2,*>的幺元，同时g(e)也是群<G2,*>的幺元，故f(e)=g(e)，故eG。

(2)证任意a,bG,有a★b-1G

任意a,bG,有a★b-1G1，f(a★b-1)=f(a)*f(b-1)=g(a)*g(b-1)=g(a★b-1)故a★b-1G。综上所述，<G,★>是<G1,★>的一个子群。第四十六页，共五十八页，编辑于2023年，星期一5-9环与域定义5-9.1设<A,★,>是一个代数系统，如果满足（1）<A,★>是阿贝尔群．（2）<A,>是半群．（3）乘运算对加运算★可分配，即对任意元素a,b,cA，a(b★c)=(ab)★(ac)(b★c)a=(ba)★(ca)称代数结构<A,★,>为环（ring）。一般将★称为加运算，记为“+”，将称为乘运算，记为“”。第四十七页，共五十八页，编辑于2023年，星期一例1.1)整数集、有理数集、实数集和复数集关于普通的加法和乘法构成环。2)实系数多项式对于多项式加法,乘法是个环。第四十八页，共五十八页，编辑于2023年，星期一环的性质定理5-9.1设<A,+,>为环，那么对任意a,b,cA，有（1）a=a=(加法幺元必为乘法零元)（2）a(-b)=(-a)b=-(ab)（3）(-a)(-b)=ab（4）a(b-c)=(ab)-(ac)

（5）(b-c)

a=(ba)-(ca)其中是加法幺元,-a表示a的加法逆元,并将a+(-b)记为a-b。第四十九页，共五十八页，编辑于2023年，星期一特殊的环定义5-9.2当环<A,+,>中运算满足交换律时,称<A,+,>为交换环；当运算有幺元时,称A为含幺环。两者都含有时，称A为含幺交换环。第五十页，共五十八页，编辑于2023年，星期一特殊的环（续）定义5-9.3设<A,+,>是一个代数系统，如果满足：(1)<A,+>是阿贝尔群(2)<A,>是可交换独异点，且无零因子，即对任意的a,bA,a≠,b≠,必有ab≠。(3)运算对于运算+是可分配的。则称<A,+,>为整环。

若<A,+,>既是交换环、含幺环,也是无零因子环,则称R是整环。例：1)<I,+,