离散数学第五版第九章(耿素云、屈婉玲、张立昂编著)省名师优质课赛课获奖课件市赛课一等奖课件

离散数学第1页第9章

代数系统介绍9.1二元运算及其性质9.2代数系统9.3几个经典代数系统第2页9.1二元运算及其性质一、二元运算定义(定义9.1)设S为集合，函数f:S×SS称为S上二元运算，简称为二元运算。

怎样判断一个运算是否为集合S上二元运算？S中任意两个元素均能够进行这种运算，且运算结果是唯一。S中任意两个元素运算结果都属于S，即S对该运算是封闭。第3页9.1二元运算及其性质例1：第4页9.1二元运算及其性质例2：例3：S为任意集合，则在f:P(A)×P(A)P(A)上，、、、是否为二元运算？第5页9.1二元运算及其性质二、n元运算定义(定义9.2)设S为集合，n为正整数，则函数

f：S×S×……×SS称为S上一个n元运算，简称为n元运算。（1）当n=1时，则函数f:SS为S上一元运算，如(x)=y（2）当n=2时，则函数f:S×SS为S上二元运算。

(x，y)=z（3）当n=3时，则函数f:S×S×SS为S上三元运算。

(x，y，z)=t第6页9.1二元运算及其性质例4：在整数集合Z、有理数集合Q、实数集合R上，一个数相反数、倒数是否为这些集合上一元运算？例5：在幂集P(S)上，假如要求全集为S，则求集合绝对补运算～是否为P(S)上一元运算？第7页9.1二元运算及其性质例6：设S={1,2},给出P(S)上运算～和运算表，其中全集为S。ai~ai

{1,2}{1}{1}{2}{2}{1,2}

P(S)={,{1},{2},{1,2}}

{1}{2}{1,2}

{1}{2}{1,2}{1}{1}

{1,2}{2}{2}{2}{1,2}

{1}{1,2}{1,2}{2}{1}

第8页9.1二元运算及其性质例7：设S={1,2,3,4},定义S上二元关系以下：

x

y=(x*y)mod5x,yS。 求运算列表。

123411234224133314244321第9页9.1二元运算及其性质三、二元运算主要性质设为S上二元运算.假如对于任意x,yS都有

xy=yx则称运算在S上是可交换,或者说运算在S上适合交换律.（1）交换律（定义9.3）注:对于二元运算矩阵来说,二元运算满足交换律,则二元运算矩阵关于主对角线对称。第10页9.1二元运算及其性质设为S上二元运算.假如对于任意x,y,zS都有

(xy)z=x(yz)则称运算在S上是可结合,或者说运算在S上适合结合律.（2）结合律（定义9.3）注:整数集Z、自然数集N、有理数集Q、实数集R上加法和乘法都是可结合；矩阵加法和乘法也是可结合；集合、、也是可结合；函数复合运算也是可结合。第11页9.1二元运算及其性质设为S上二元运算,假如对于任意xS都有

xx=x则称运算在S上适合等幂律.（3）幂等律（定义9.3）集合、是复合等幂律。第12页9.1二元运算及其性质设和*是S上两个二元运算,假如对于任意x，y，zS有

x*(yz)=(x*y)(x*z)(左分配律) (yz)*x=(y*x)(z*x)(右分配律)则称运算*对是可分配，也称*对适合分配律。（4）分配律（定义9.4）第13页9.1二元运算及其性质设和*是S上两个可交换二元运算,假如对于任意x，yS有

x*(xy)=x x(x*y)=x则称运算*和满足吸收律。（5）吸收律（定义9.5）比如：幂集P(S)上和运算满足吸收律。即A,BP(S)

有 A(AB)=A A(AB)=A第14页9.1二元运算及其性质四、单位元和幺元设为S上二元运算,假如存在(或)S使得对于任何xS都有

x=x(或x=x)则称(或)是S中关于运算一个左幺元(或右幺元)。若eS关于运算既是左幺元又是右幺元，则称e为S上关于运算幺元。幺元定义（定义9.6）第15页9.1二元运算及其性质例8：自然数集N上加法

幺元，幺元是

。自然数集N上乘法

幺元，幺元是

。自然数集N上除法

幺元，幺元是

。幂集P(S)上运算

幺元，幺元是

。幂集P(S)上运算

幺元，幺元是

。第16页9.1二元运算及其性质设为S上二元运算,，分别为运算左幺元和右幺元，则有

==e且e为S上关于运算唯一幺元。单位元和幺元唯一定理（定理9.1）第17页9.1二元运算及其性质四、零元设为S上二元运算,假如存在(或)S使得对于任何xS都有

x=(或x=)则称(或)是S中关于运算一个左零元(或右零元)。若S关于运算既是左零元又是右零元，则称为S上关于运算零元。零元定义（定义9.6）第18页9.1二元运算及其性质例9：自然数集N上加法

零元，零元是

。自然数集N上乘法

零元，零元是

。自然数集N上除法

零元，零元是

。幂集P(S)上运算

零元，零元是

。幂集P(S)上运算

零元，零元是

。第19页9.1二元运算及其性质设为S上二元运算,，分别为运算左零元和右零元，则有

==且为S上关于运算唯一零元。零元唯一定理（定理9.2）第20页9.1二元运算及其性质设为S上二元运算,e，分别为运算幺元和零元，假如S最少有两个元素，则e。幺元与零元定理证实：假设e=,则xS有

x=ex=x=

则x==e,S中只有一个元素 又因为S中最少有两个元素，矛盾 所以：e 第21页9.1二元运算及其性质五、逆元逆元定义（定义9.6）设为S上二元运算,eS为运算幺元，对于xS，假如存在使得

则称是x左逆元（或右逆元）。若yS既是x左逆元又是x右逆元，则称y是x逆元。假如x逆元存在，则称x是可逆。第22页9.1二元运算及其性质逆元唯一定理（定理9.3）设为S上可结合二元运算,eS为运算单位元，对于xS，假如存在左逆元和右逆元则有

则y是x唯一逆元。第23页9.1二元运算及其性质六、消去律（定义9.7）设为S上二元运算,假如对于任意x,y,zS满足以下条件：

(1)若xy=xz且x，则y=z。

(2)若yx=zx且x，则y=z。那么称运算满足消去律，其中(1)称作左消去律，(2)称作右消去律。第24页9.1二元运算及其性质例10：设是字母有穷集，称为字母表，中有限个字母组成序列称为上串，对任何串，串中字母个数叫做串长度，记作||，长度是0串叫空串，记作，对任给自然数k，令它是上全部长度为k串集合，尤其：串连接运算：第25页第九章

代数系统普通性质9.1二元运算及其性质9.2代数系统9.3几个经典代数系统第26页9.2代数系统一、代数系统定义(定义9.8)非空集合S和S上k个运算f1,f2……fk(其中fi为ni元运算，i=1，2,…，k)组成系统称为一个代数系统，简称代数，记作<S,f1,f2……fk>。判断代数系统方法： 判断该系统中每个运算是否为n元运算。第27页9.2代数系统例11：<N,+>、<N,+,->、<Z,+,->、<Z,+,,×>是否为代数系统？<P(S),,>,<P(S),,->是否为代数系统？第28页9.2代数系统二、特异元素、代数常数定义代数系统中对于给定二元运算存在幺元或零元，而且它们对该系统性质起着主要作用，称之为该系统特异元素或代数常数。比如：

<Z,+,0>、<Z,*,1>、<P(S),,,,S,>第29页9.2代数系统三、子代数系统、子代数定义(定义9.13)设V={S,f1,f2,……,fk}是代数系统，BS且B，假如B对f1,f2,……,fk都是封闭，且B和S含有相同代数常数，则称<B,f1,f2,……,fk>是V子代数系统，简称子代数。比如：

v1=<N,+,0> v2=<Z,+,0>第30页9.2代数系统例12：设V=<Z,+,0>，令

nZ={nz|zZ}.n为自然数，那么，<nZ,+,0>是否为V子代数？第31页9.2代数系统四、平凡子代数与真子代数定义对任何代数系统V={S,f1,f2,……,fk}，最大子代数就是V本身。假如令V中全部代数常数组成集合是B，且B对V中全部运算都是封闭，则，B就组成了V最小子代数。这种最小和最大子代数称为V平凡子代数。假如代数系统V子代数V’={B,f1,f2,……,fk}，满足

BS，则称V’为V真子代数。第32页9.2代数系统五、积代数定义（定义9.14）设V1=<S1,

>,V2=<S2,*>是代数系统，和*为二元运算。V1和V2积代数V1×V2是含有一个二元运算代书系统，即V1×V2=<S,>,其中S=S1×S2,对任意<x1,y1>,<x2,y2>S1×S2有

<x1,y1><x2,y2>=<x1x2,y1*y2>第33页9.2代数系统例13：设V1=<Z,+,0>，V2=<Z,*,1>,求V1与V2积代数。V1×V2=<Z×Z,,<0,1>>,其中：

<x1,y1>

<x2,y2>=<x1+x2,y1*y2>第34页9.2代数系统六、同态定义(定义9.15)设V1=<S1,

>,V2=<S2,*>是代数系统，

和*是二元运算。假如存在映射：S1S2，若x，yS1都有

(x

b)=(x)*(y)则称是V1到V2同态映射，简称同态。第35页9.2代数系统例14：(1)G1=<Z,+>，G2=<Zn,

>,令

：ZZn，(x)=(x)modn

则是否为G1到G2同态？第36页9.2代数系统例15：(2)G1=<R,+>，G2=<R+,

>,令

：RR+

，(x)=ex

则是否为G1到G2同态？第37页9.2代数系统七、同态象定义(定义9.16)设

是V1=<S1,

>到V2=<S2,*>同态，则称<(S1),*>是V1在下象。第38页9.2代数系统八、满同态、单同态、同构和自同态(定义9.17)(1)若：G1G2是满射，则称为满同态，这时也称

G2是G1同态像，记作。(2)若：G1G2是单射，则称为单同态。(3)若：G1G2是双射，则称为同构，记作。(4)若G1=G2，则称是群G自同态。第39页9.2代数系统例16：设V=<R+,

>，其中为普通成法。对任意xR+令1(x)=|x|，2(x)=2x,3(x)=x2,4(x)=1/x,5(x)=-x,则分析他们是否为V到V同态，假如是，则分别为何同态。第40页第九章代数系统介绍9.1二元运算及其性质9.2代数系统9.3几个经典代数系统半群与群第41页(1)半群与群一、半群定义(定义9.13)（1）设V=<S,

>是代数系统，

为二元运算，假如

是可结合，则称V为半群。（2）设V=<S,

>是半群，若eS是关于运算单位 元，则称V是含幺半群，也叫独异点。有时也将独异点V记作<S,

,e>。第42页(1)半群与群例1：(1)<Z,+>,<N,+>,<Q,+>,<R,+>都是半群，其中+表示普通加法。(2)<,>是半群，其中是有穷字母表，表示连接运算。(3)<P(B),>是半群，也是独异点，其中为集合对称差运算。(4)<Zn,>是半群，其中Zn={0,1,……,n-1},表示模n加法。第43页(1)半群与群二、幂运算定义半群V=<S,

>，对于任意xS，要求：

普通乘法幂、关系幂等都遵照这个幂运算规则。幂运算运算规则：对独异点有：第44页(1)半群与群三、子半群定义半群子代数叫做子半群，独异点子代数叫做子独异点。若V=<S,

>是半群，TS，只要T对V中运算封闭，那么<T,>就是V子半群。而对独异点V=<S,,e>来说，TS，不但T对V中运算封闭，而且eT，这时<T,,e>才组成V子独异点。第45页(1)半群与群例2：设独异点V1=<Z,+,0>，V2=<nZ,+,0>,V2是否为V1子独异点？第46页(1)半群与群四、积半群设V1=<S1,

>，V2=<S2,*>是半群（或独异点），则V1×V2=<S1×S2,>也是半群，且：

<a,b>，<c,d>S1×S2，<a,b><c,d>=<ac,b*d>称V1×V2

为V1和V2积半群。若V1和V2是独异点，其单位元为e1和e2，则<e1,e2>是V1×V2中单位元。所以V1×V2也是独异点。第47页(1)半群与群五、半群同构(1)设V1=<S1,

>，V2=<S2,*>是半群，

:S1S2。若对任意

x，yS1有

(xy)=(x)*(y)

则称为半群V1到V2同态映射，简称为同态。(2)设V1=<S1,,e1>，V2=<S2,*,e2>是独异点，

:S1S2。若对任意x，yS1有

(xy)=(x)*(y)且(e1)=e2

则称为独异点V1到V2同态映射，简称为同态。第48页(1)半群与群例3：设半群V1=<S,

>，独异点V2=<S,,e>。其中为矩阵乘法，e为2阶单位矩阵。令则是半群V1=<S,

>到本身同态，称V1自同态。但不是独异点

V2=<S,

,e>自同态。第49页(1)半群与群六、群定义(定义9.14)设<G,

>是代数系统，

为二元运算。假如运算是可结合，存在单位元eG，而且对于G中任何元素x都有G，则称<G,>为群。第50页(1)半群与群例6：(1)<Z,+>,<N,+>,<Q,+>,<R,+>，其中+表示普通加法。(2)<,>其中是有穷字母表，表示连接运算。(3)<P(B),>，其中为集合对称差运算。(4)<Zn,>，其中Zn={0,1,……,n-1},表示模n加法。第51页(1)半群与群例7：设G={e,a,b,c},

为G上二元运算,它由一下运算表给出。判断<G,>是否为群?

eabceeabcaaecbbbceaccbae第52页(1)半群与群例8：设<G1,>,<G2,*>是群,在G1×G2上定义二元运算以下：

<a,b>,<c,d>G1G2,<a,b><c,d>=<ac,b*d>

称<G1×G2,>是G1与G2直积。则<G1×G2,>是否是群？第53页(1)半群与群七、群相关概念定义(1)若群G是有穷集，则称G是有限群，不然称为无限群。群G基数称为群G阶。(2)只含单位元群称为平凡群。(3)若群G中二元运算是可交换，则称G为交换群或

阿贝尔群。第54页(1)半群与群八、群幂次定义注：半群和特异点不一样，群中元素能够定义负整数次幂。设G是群，aG，nZ，则an次幂第55页(1)半群与群九、元素阶、无限阶元设G是群，aG，使得等式成立最小正整数k称为a阶，记作|a|=k，这是也称a为k阶元。若不存在这么正整数k，则称a为无限阶元。第56页(1)半群与群十、群中元素阶性质<G,*>为群，aG，且|a|=r。设k是整数，则例：设G是群，a，bG是有限阶元。证实第57页(1)半群与群十一、群幂运算定理(定理9.4)设G是群，则G中幂运算满足：第58页(1)半群与群十二、方程唯一解定理(定理9.5)G为群，

a,bG，方程ax=b和ya=b在G中有解且有唯一解。例9：设群G=<P({a,b}),

>，其中

为集合对称差运算。解以下方程：

{a}X=，Y{a,b}={b}第59页(1)半群与群十三、群中二元运算消去律(定理9.6)G为群，则G中适合消去律，即对任意a,b,cG有(1)若ab=ac，则b=c。(2)若ba=ca，则b=c。例10：设G为群，a,bG，k，证实第60页(1)半群与群例11：设G为群，a，bG，且证实ab=ba。第61页(1)半群与群十四、子群定义(定义9.15)设群<G,*>，H是G非空子集，假如H关于G中运算*组成群，则称H是G子群，记作HG。若H是G子群，HG，则称H是G真子群，记作H<G。注：

G和｛e｝是G平凡子群。第62页(1)半群与群十五、子群判定定理一(定理9.8)设G是群，H是G非空子集。如对任意x,yH都有xy-1H则H是G子群。第63页(1)半群与群例：设G为群，ａＧ，令 Ｈ＝｛ａｋ｜ｋＺ｝即ａ全部幂组成集合，则求证Ｈ是Ｇ子群。第64页(1)半群与群十六、循环群定义(定义9.16)设G是群，若存在aG使得

G={|kZ}则称G是循环群，记作G=<a>，称a为G生成元。注：(1)任何素数阶群都是循环群。

(2)循环群生成元可能不止一个。第65页(1)半群与群例13：(1)G=<Z,+>是否为循环群？(2)G=<R,+>是否为循环群？(3)G=<R,×>是否为循环群？(4)G=<Zn,

>，是模n加法，则G是否为循环群？(5)G={P(A),

}是否为循环群？(6)G={nZ,+}是否为循环群？第66页(1)半群与群例14：设A={1,2,3,4,5},<P(A),

>组成群，其中为集合对称差。（1）求解群方程{1,3}X={3,4,5}

（2）令B={1,4,5}，求由B生成循环子群<B>第67页(1)半群与群十七、循环群生成元求法设G=<a>是循环群。（1）若G是无限循环群，则G只有两个生成元，即a和（2）若G是n阶循环群，则G含有(n)个生成元。对于任何小于等于n且与n互素正整数r，是G生成元。第68页(1)半群与群例15：(1)设G={e,a,……,a11}是12阶循环群，则它生成元有几个，分别是什么？(2)G=<Z9,

>是模9整数加群，则它生成原有几个，分别是什么？(3)G=<3Z,+>，则G上生成元有几个，分别是什么？第69页(1)半群与群十八、循环群子群求法（1）设G=<a>是循环群，则其全部子群均为循环群（2）设G=<a>是无限循环群，则G子群除｛e｝外都是无限循环群。（3）设G=<a>是n阶循环群，则对n每个正因子d，G恰好含有一个d阶子群。第70页(1)半群与群例16：G=<Z,+>是无限循环群，其生成元为1和－1，则列出G全部循环子群。<10>={0}=0Z<11>={……，-1,0,1,……}=Z<12>={……-4，-2,0,2,4,……}=2Z<1n>={……-2n，-n,0,n,2n,……}=nZ……第71页(1)半群与群例17：G=<Z12,

>是12阶循环群，列出G全部子群。<112/12>=Z12<112/6>={0,2,4,6,8,10}<112/4>={0,3,6,9}<112/3>={0,4,8}<112/2>={0,6}12正因子为：1,2,3,4,6,12<112/1>={0}第72页(1)半群与群例18：设G1=<a2>={e,a2,a-2,a4,a-4,……}是无限循环群，则G1子群是什么？<(a2)0>={e}<(a2)m>=<a2m>={e,a2m,a-2m,a4m,a-4m,……}m是正整数第73页(1)半群与群例19：设G2=<a2>是9阶循环群，则G2子群是什么？<(a2)9/9>=<a2>=G2<(a2)9/3>={e,a6,a12}9正因子有：1,3,9<(a2)9/1>={e}第74页(1)半群与群十九、置换定义(定义9.17)设S=