离散数学第五章代数结构

离散数学课件第五章代数结构第1页，课件共58页，创作于2023年2月证明:1）充分性

a,b

G，有(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)”。（证略）第2页，课件共58页，创作于2023年2月补充：元素的阶（a的阶，记为|a|）1．元素a的幂的定义定义：给定群<G,*>,

a

G,若n

N,则定义: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,n

I),对k用归纳法可证：(am)k=amk(m,k

I)第3页，课件共58页，创作于2023年2月补充：元素的阶（a的阶，记为|a|）2．元素a的阶的定义设<G，*>是群，

a

G能够使am=e的最小正整数m，称为a的阶。若m不存在，则说a是无阶的。例1：在整数加群<z,+>中，0的阶是1，其余元素均无阶。例2：在群<{1,-1},*>中，-1的阶是2，1的阶是1。例3：在整数加群<z6,+6>中，求各元素的阶：123450632361第4页，课件共58页，创作于2023年2月循环群与生成元定义5-5.2设<G,

>为群，如果在G中存在元素a,使得G中的任何元素都可表示为a的幂（约定a0=e,ak=a*a*…*a(k个)）,称<G,

>为循环群，这时a称为循环群G的生成元。例1：整数加群<I,+>是循环群，其生成元为。计算群的生成元是判别一个群是否为循环群的关键。1和-1第5页，课件共58页，创作于2023年2月循环群举例例：循环群<{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°第6页，课件共58页，创作于2023年2月循环群的性质定理5-5.2任何一个循环群必定是阿贝尔群。证设<G,

>是一个循环群，a是该群的生成元，则对于任意的x,y

G，必有r,s

I，使得

x=ar和y=as

而且x

y=ar

as=ar+s=as+r=as

ar=y

x因此，运算可交换，是阿贝尔群。第7页，课件共58页，创作于2023年2月循环群中生成元的阶（周期）定理5-5.3

设<G,

>为循环群，a

G是该群的生成元，如果G的阶数是n，即|G|=n，则an=e,且

G={a,a2,a3,...,an-2,an-1,an=e}其中，e是群<G,

>的幺元。n是使得an=e成立的最小正整数，称为元素a的阶或周期。第8页，课件共58页，创作于2023年2月定理5-5.3的证明证明思路:先证a的阶为n。设对于某个正整数m,m<n,有am=e。那么，由于<G,

>是一个循环群，所以对于G中任意的元素都能写为ak(k

I),而且k=mq+r,其中q是某个整数,0≤r<m,则有ak=amq+r=(am)q

ar=(e)q

ar=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，这已经有上面证明是不可能的。第9页，课件共58页，创作于2023年2月循环群中生成元的阶例1：循环群<{0°,60°,120°,180°,240°,300°}，★>，60o是生成元；e=0o；6是使(60o)n=e的最小正整数，故60o的周期(阶)为6。例2：<{5j|j

I},+>是无限循环群,其中-5,5是均生成元。同理，300°的阶也是6。第10页，课件共58页，创作于2023年2月例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>的生成元？第11页，课件共58页，创作于2023年2月例4：设G={α,β,γ,δ}，*的运算表如下，证<G,*>是循环群。*αβγδααβγδββαδγγγδβαδδγαβ

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

(t

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

1)证G中每个元素均有逆元。∵任意x

G都有x*x=e，故x-1=x。

2)证运算满足交换律。∵任意a,b

G都有(a*b)-1=a*b∴a*b=(a*b)-1=b-1*a-1=b*a∴运算满足交换律。综上所述，<G,*>是一个阿贝尔群。第14页，课件共58页，创作于2023年2月练习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]第15页，课件共58页，创作于2023年2月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，

>的子群，那么对任一a

G，称aH={a*h｜h∈H}为H的左陪集(leftcoset),记为aH;称Ha={h*a｜h∈H}为H的右陪集(rightcoset),记为Ha。第16页，课件共58页，创作于2023年2月陪集举例例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的一个划分。第17页，课件共58页，创作于2023年2月陪集的性质设<H,*>是<G,*>的子群,

a,b

G则aH=bH或aH∩bH=Ф。证:对于aH和bH，只有两种情况：

①

aH∩bH=Ф②aH∩bH≠Ф对于第二种情况，设

f

aH∩bH

h1，h2

H，使f=a*h1=b*h2

a=b*h2*h1-1

bH

x

aH则

h3

H,x=a*h3=b*h2*h1-1*h3

bH

aH

bH，同理bH

aH

aH=bH第18页，课件共58页，创作于2023年2月拉格朗日定理定理5-7.1(拉格朗日定理)

设<H，

>为有限群<G，

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

第19页，课件共58页，创作于2023年2月拉格朗日定理的推论推论1任何质数阶的群不可能有非平凡子群。推论2

设<G,

>为n阶有限群，那么对于任意a

G,a的阶必是n的因子且必有an=e,这里e是群<G,

>的幺元。如果n为质数，则<G,

>必是循环群。第20页，课件共58页，创作于2023年2月拉格朗日定理推论2的证明证:若a

G的阶是r,则{e,aa2,a3,…,ar-1}是G的子群且该子群的阶为r，由拉格朗日定理可知r整除n，所以a的阶必是n的因子。故n=rt(t

I+),故an=e。设<G,*>为质数阶群，则

a

G且a

e，∵a的阶数可整除|G|,但是|G|为质数,所以a的阶数等于群的阶数。∴{a,a2,

,ar}=G

∴

<G,*>是循环群第21页，课件共58页，创作于2023年2月拉格朗日定理练习例1.试证奇数阶群所有元素之积等于幺元。证:设<G,*>是一个群,e为幺元,则在G中不存在这样的元素a：a

e，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}，其中ai

ai-1

e*a*a1-1*

*an*an-1=e第22页，课件共58页，创作于2023年2月拉格朗日定理练习例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四元群。第23页，课件共58页，创作于2023年2月四阶群（只有两个）Klein四元群：eeabceeabcaaecbbbceaccbae四阶循环群：eeabceeabcaabcebbceacceab第24页，课件共58页，创作于2023年2月练习：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第25页，课件共58页，创作于2023年2月练习：P211-(8)apt-1(apt-1)p第26页，课件共58页，创作于2023年2月5-8同态与同构定义5-8.1设<A,★>和<B,

>是两个代数系统，f是从A到B的一个映射，

a1,a2

A，有

f(a1★a2)=f(a1)

f(a2)（先算后映=先映后算）则称f为由代数结构<A,★>到<B,

>的同态映射，称<A,★>同态于<B,

>，记为A~B。称<f(A),

>为<A,★>的一个同态象。其中

f(A)={x|x=f(a),a

A}

B第27页，课件共58页，创作于2023年2月（G，*)(S，o)a●b●a*b●f(a)●f(b)●f(a)of(b)●同态象f通过映射建立了两个代数系统之间的联系。第28页，课件共58页，创作于2023年2月同构(同态双射)定义5-8.2当同态映射f分别是入射（单射）、满射、双射时，分别称f是单一同态、满同态、同构映射。如果存在一个从<A,★>到<B,*>的同构映射,则称代数系统<A,★>与<B,*>同构,记作A≌B。定义5-8.3设<A,★>是一个代数系统，如果f是<A,★>到<A,★>的同态,称f为A的自同态。如果ｇ是<A,★>到<A,★>的同构,称f为A的自同构。第29页，课件共58页，创作于2023年2月同构举例例１：设H={x|x=dn,d

I+,n

I},定义映射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,+>的自同态,若k

0,则fk是单一同态,若k=

1,则fk是<I,+>到<I,+>的自同构。第30页，课件共58页，创作于2023年2月同构举例证明：设f:N

Nk(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>的满同态。第31页，课件共58页，创作于2023年2月同态象的性质定理5-8.2设f是由<A,★>到<B,

>的一个同态映射。（a）如果<A,★>是半群，那么在f作用下，同态象<f(A),

>也是半群。（b）如果<A,★>是独异点，那么在f作用下，同态象<f(A),

>也是独异点。（c）如果<A,★>是群，那么在f作用下，同态象<f(A),

>也是群。第32页，课件共58页，创作于2023年2月定理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)第33页，课件共58页，创作于2023年2月证

在f(A)上满足结合律对于任意的a,b,c

f(A),必有x,y,z

A,使得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),

>是半群。

第34页，课件共58页，创作于2023年2月再证（b）：<f(A),

>是独异点设<A,★>是独异点,e是A中的幺元,那么f(e)是f(A)中的幺元。因对于任意的a

f(A),必有xA,使得f(x)=a所以a

f(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),

>是独异点。第35页，课件共58页，创作于2023年2月最后证（c）：<f(A),

>是群设<A,★>是群,对于任意的a

f(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)三步，定理证毕第36页，课件共58页，创作于2023年2月同态核定义5-8.4如果f为代数结构<G,★>到<G’,

>的一个同态映射，G’中有么元e’，那么称下列集合为f的同态核，记为K(f)。

K(f)={x

x

G∧f(x)＝e’}第37页，课件共58页，创作于2023年2月同态核的性质定理5-8.3设f为群<G,★>到群<G’,

>的同态映射，那么f的同态核K是G的子群。证明思路:设e是<G,★>的幺元，e’=f(e),故e

K。证★运算在K上封闭。设k1,k2

K,则f(k1★k2)=f(k1)

f(k2)=e’

e’=e’故k1★k2

K，★运算在K上封闭。

证K中的元素有逆元。对任意的k

K,f(k-1)=[f(k)]-1=e’-1=e’故k-1

K。结论得证。第38页，课件共58页，创作于2023年2月同态核举例例:f:<I,+>

<N5,+5>,

x

N,f(x)=xmod5则

x,y

I,f(x+y)=(x+y)mod5=xmod5+5ymod5=f(x)+5f(y)

f是从<I,+>到<N5,+5>的同态

ker(f)={x|x

I

f(x)=0}={0,5,-5,10,-10,

}第39页，课件共58页，创作于2023年2月代数结构的划分——同余关系显然整数集合I上的模k余数相等关系R是等价关系。容易证明，对于

a,b,c,d

I，R对整数上的加运算满足性质：若x≡y(modk)且z≡w(modk),则(x+z)≡(y+w)(modk),称这种特殊的等价关系为同余关系。

将上述同余关系推广，则得到代数结构上一般意义的同余关系。第40页，课件共58页，创作于2023年2月同余关系与同余类定义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是同余关系；第41页，课件共58页，创作于2023年2月例：<I,+>，在I上定义R:<x,y>

R

|x|=|y|,R是<I,+>的同余关系吗?解:1)自反性：

x

I,|x|=|x|

<x,x>

R2)对称性：

x,y

I,若<x,y>

R则|x|=|y|

<y,x>

R3)传递性：

x,y,z

I，若<x,y>

R,<y,z>

R则|x|=|y|=|z|

<x,z>

R

R是一等价关系

x1,y1,x2,y2

I，若<x1,y1>

R,<x2,y2>

R，但<x1+x2,y1+y2>

R不一定成立。例<1,-1>,<2,2>

R，但<1+2,-1+2>

R,

R不是同余关系第42页，课件共58页，创作于2023年2月同余关系与划分类似于集合论中等价关系及其相应的划分，同余关系所得到的等价类称为同余类，同余类的集合是同余关系所诱导的一个划分。例：课本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}}

第43页，课件共58页，创作于2023年2月★abcdaaadcbbacdccdabdddbaabcda√√b√√c√√d√√第44页，课件共58页，创作于2023年2月练习P222(11):设f和g都是群<G1,★>到群<G2,*>的同态，证明<G,★>是<G1,★>的一个子群，其中G={x|xG1且f(x)=g(x)}第45页，课件共58页，创作于2023年2月证：(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-1

G1，f(a★b-1)=f(a)*f(b-1)=g(a)*g(b-1)=g(a★b-1)故a★b-1G。综上所述，<G,★>是<G1,★>的一个子群。第46页，课件共58页，创作于2023年2月5-9环与域定义5-9.1设<A,★,

>是一个代数系统，如果满足（1）<A,★>是阿贝尔群．（2）<A,

>是半群．（3）乘运算

对加运算★可分配，即对任意元素a,b,c

A，a(b★c)=(a

b)★(a

c)(b★c)

a=(b

a)★(c

a)称代数结构<A,★,

>为环（ring）。一般将★称为加运算，记为“+”，将

称为乘运算，记为“

”。第47页，课件共58页，创作于2023年2月例1.1)整数集、有理数集、实数集和复数集关于普通的加法和乘法构成环。2)实系数多项式对于多项式加法,乘法是个环。第48页，课件共58页，创作于2023年2月环的性质定理5-9.1设<A,+,

>为环，那么对任意a,b,cA，有（1）

a=a

=

(加法幺元必为乘法零元)（2）a(-b)=(-a)

b=-(a

b)（3）(-a)(-b)=a

b（4）a

(b-c)=(a

b)-(a

c)

（5）(b-c)

a=(b

a)-(c

a)其中

是加法幺元,-a表示a的加法逆元,并将a+(-b)记为a-b。第49页，课件共58页，创作于2023年2月特殊的环定义5-9.2当环<A,+,

>中

运算满足交换律时,称<A,+,

>为交换环；当

运算有幺元时,称A为含幺环。两者都含有时，称A为含幺交换环。第50页，课件共58页，创作于2023年2月特殊的环（续）定义5-9.3设<A,+,

>是一个代数系统，如果满足：(1)<A,+>是阿贝尔群(2)<A,>是可交换独异点，且无零因子，即对任意的a,bA,a≠,b≠,必有a

b≠。(3)运算对于运算+是可分配的。则称<A,+,

>为整环。

若<A,+,

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