离散数学代数系统

离散数学代数系统第一页，共七十三页，编辑于2023年，星期日§6.1代数运算及代数系统二元代数运算：设A是非空集合,如R*=R–{0}上的乘法,除法运算:f:AnA称为A上的n元运算,n为运算阶.函数f:AA是集合A上的一元代数运算,简称一元运算;如集合R－{0}上的求倒数运算；函数f:A2A称为A上二元代数运算.一、代数运算的概念第二页，共七十三页，编辑于2023年，星期日集合的封闭性：给定集A,如Z对加、减、乘法封闭,对除法不封闭.如果对A上的元素进行某种运算后,运算结果仍在A中,则称集A对该种运算封闭。第三页，共七十三页，编辑于2023年，星期日二、常见二元运算：(1)设Mn(R)表示所有n阶实矩阵的集合,则矩阵加法和乘法运算是Mn(R)上的二元运算,且封闭;(2)S为任意集合,P(S)为其幂集,则∪,∩,–,都是P(S)上的二元运算,且封闭；(3)S为集合,Ss是S上的所有函数的集合,则合成运算o是Ss上的二元运算.第四页，共七十三页，编辑于2023年，星期日三、二元运算的性质：(1)设是定义在集A上的二元运算,若对任意的x,yA都有yx=xy,则说具有可交换性；(2)如果对任意的x,y,zA,都有(xy)z=x(yz),则说具有可结合性；第五页，共七十三页，编辑于2023年，星期日(3)设,是A上的两个二元运算,如果对任意的x,y,zAx(yz)=(xy)(xz)(yz)x=(yx)(zx)则说对具有可分配性.第六页，共七十三页，编辑于2023年，星期日(4)设,是A上的两个可交换二元运算,如果对于任意的x,y,zA,都有x(xy)=xx(xy)=x则称运算对满足吸收律.如：N上定义两个二元运算,如下xy=max(x,y)xy=min(x,y)则对满足吸收律.第七页，共七十三页，编辑于2023年，星期日(5)是A上的一个二元运算,如果x,xx=x,则说是等幂的(6)如果(ⅰ)xy=xz

且x,是指集A关于运算

的零元，有y=z,

(ⅱ)yx=zx

且x,有y

=z则是满足消去律.第八页，共七十三页，编辑于2023年，星期日四、集A的特殊元：(1)幺元：是集A上的二元运算,如果elA且xA,有elx=x,则el为A中关于的左幺元；如何定义右幺元er(自己叙述一遍！)第九页，共七十三页，编辑于2023年，星期日如果A中的一个元素e,既是左幺元又是右幺元,则e为A中关于的幺元.可以证明：幺元是唯一的.证明：反证,若有两个幺元e,e',则由幺元的定义知e=e'e=e'矛盾.第十页，共七十三页，编辑于2023年，星期日(2)零元：如果有一个元素lA,使得xA,lx=l,则l称为左零元；右零元呢？(r)零元呢？()类似于幺元,可证A中零元唯一.第十一页，共七十三页，编辑于2023年，星期日(3)逆元：是A上的一个运算,e是幺元,如果对于A中元素a,存在bA,使得ba=e,则称b为a的左逆元；右逆元呢？逆元呢？(a–1)可证：逆元存在则唯一(要求可结合)证明：设b,c为a的两个不同逆元,则ba

=ab=e

ca=ac=e从而

b=be=b(ac)=(ba)c=ec=c矛盾.第十二页，共七十三页，编辑于2023年，星期日(4)幂等元：

是A上的二元运算,对于xA,如果有xx=x,则x是A中的幂等元,如幺元和零元.第十三页，共七十三页，编辑于2023年，星期日五、代数系统：非空集合S与S上的k个运算f1,f2,…,fk组成的系统,称为代数系统,记作：

<S,f1,f2,…,fk>如<N,+>,<Z,+>,<R,+,•>,<Mn(R),+,•>,<P(S),∪,∩,–>第十四页，共七十三页，编辑于2023年，星期日§6.2同态与同构同态：V1=<A,f1,…,fn>,V2=<B,1,…,n>是两个代数系统,其中fi

,i(i=1,2,…,n)都是二元运算。x,yA,f(xfiy)=f(x)if(y)(i=1,…,n)则称f是V1到V2的一个同态映射,也说V1与V2同态,记作V1f

V2或V1～V2.

f

如果存在映射f:AB

满足：第十五页，共七十三页，编辑于2023年，星期日如：<R+,×>~<R,+>(只要定义f:R+R,f(ab)=lgab=lga+lgb=f(a)+f(b))当n=1时，设V1=<A,>，V2=<B,>是两个代数系统。如果存在f:AB.使x,yA，f(xy)=f(x)f(y)则称f

是V1到V2的一个同态映射。第十六页，共七十三页，编辑于2023年，星期日同态象：设V1=<A,>～V2=<B,>,则称<f(A),>是V1在f下的同态象.f同态的性质：设V1=<A,>～V2=<B,>,f(1)如果f:AB是满射,则说f为V1到V2满同态的(2)如果f是单射,则说f为V1到V2单同态的(3)如果f是双射,则说f为V1与V2同构,记作(4)当V1=V2时,则说f是V1的自同态(自同构)第十七页，共七十三页，编辑于2023年，星期日例6.1<R,+>,<R,>是两个代数系统,f:RR,且xR,f(x)=2x,验证f是<R,+>到<R,>的同态,并且是单同态.验证：任取x,yR由于f(x+y)=2x+y=2x2y=f(x)

f(y)所以f是<R,+>到<R,>的自同态；

其次,对任取的x,yR,当xy时,2x

2y,即f(x)f(y),f为单射,从而f是单自同态第十八页，共七十三页，编辑于2023年，星期日例6.2

设A={a,b,c,d},B={[0],[1],[2],[3]}且f:AB,f(a)=[0],f(b)=[1],f(c)=[2],f(d)=[3]代数系统<A,>,<B,+4>中运算

,+4定义如下：abcdabcdbcdacdabdabcabcd+4[0][1][2][3][0][1][2][3][0][1][2][3][1][2][3][0][2][3][1][0][3][0][1][2]第十九页，共七十三页，编辑于2023年，星期日验证：<A,><B,+4>f验证：首先由f定义知f既是单射又是满射,从而双射,其次通过研究运算表知：x,yA,f(xy)=f(x)+4f(y)从而f是从<A,>到<B,+4>的同构.第二十页，共七十三页，编辑于2023年，星期日同态与同构的意义(1)V1=<A,>与V2=<B,+4>

同态,则V1中所具有的运算性质,可以保持在同态象中；(2)对于满同态,V1的运算在V2中仍保持；(3)如果V1V2,则它们的性质完全相同,可以看成一个东西不加区别(代数角度).第二十一页，共七十三页，编辑于2023年，星期日§6.3同余关系与商代数模n同余关系：Z是整数集,在Z中定义关系R={<x,y>|x,yZ

xy(modn)}其中,xy(modn)的含义是x–y可以被n整除.不难验证:R是Z上的等价关系(自反、对称、传递),我们称该等价关系为模n同余关系.由同余关系R可得商集：Z/R={[0],[1],…,[n–1]},记作：Zn.一、模n同余关系的概念第二十二页，共七十三页，编辑于2023年，星期日同余关系与剩余类：设代数系统V=<A,>,是集A上的二元运算,(1)R是A上的等价关系；(2)a1,a2,b1,b2A,(a1Ra2)(b1Rb2)(a1b1)R(a2b2)则称R是A上对运算的同余关系,或称V上的同余关系。如果集A上存在关系R满足：由同余关系将A划分的等价类称为剩余类.二、一般同余关系的定义第二十三页，共七十三页，编辑于2023年，星期日例6.3

设代数系统<A,>,A={a,b,c,d},见下列运算表：abcdaadcbacdcdabddbaabcd第二十四页，共七十三页，编辑于2023年，星期日再规定A上的一个关系：R={<a,a>,<a,b>,<b,a>,<b,b>,<c,c>,<c,d>,<d,c>,<d,d>}则可验证：(1)R是等价关系(2)x,y,u,vA如果(xRy)(uRv),则(xu)R(yv)(验证方法：在R中任取2个元素，如<a,b>,<d,d>;<a,a>,<c,c>……等加以验证)第二十五页，共七十三页，编辑于2023年，星期日例6.4

代数系统<Z,>中,Z是整数集,是一元运算,且zZ,zz=z2(modm),m为一自然数.设R是Z上的模m同余关系可以证明：R是Z上的同余关系(2)对任意的z1,z2Z,如果z1Rz2即z1z2(modm)(1)R显然是等价关系证明：第二十六页，共七十三页，编辑于2023年，星期日往证：z1z1=z12(modm)与z2z2=z22(modm)具有R关系,即z12(modm)Rz22(modm),这是因为：z1z2(modm)z1=a1m+ro,z2=a2m+ro,其中0rom–1第二十七页，共七十三页，编辑于2023年，星期日三、同余关系的判定：<A,>与<B,>是两个代数系统。证明：(1)R是等价关系f：AB是同态映射。利用f规定A上的二元关系R：aRb当且仅当f(a)=f(b)，则R是同余关系。第二十八页，共七十三页，编辑于2023年，星期日由同态映射的定义知：f(xu)=f(x)f(u)f(yv)=f(y)f(v)所以f(xu)=f(yv),即(xu)R(yv)(2)x,y,u,vA，如果xRy,uRv，则(xu)R(yv)。这是因为：xRy即f(x)=f(y);uRv即f(u)=f(v).第二十九页，共七十三页，编辑于2023年，星期日商代数：V=<A,>是一个代数系统,是二元运算。A/R={[x]R|xA}在A/R中规定二元运算：[x]R,[y]RA/R,[x]R

[y]R

=[xy]R则称<A/R,>为V关于R的商代数,记作V/R.R是V中的同余关系,A/R是A关于R的商集。四、同余关系的应用第三十页，共七十三页，编辑于2023年，星期日§6.4群半群：代数系统V=<A,>中,是非空集合A上的二元运算,且在A中是可结合的,即x,y,zA(xy)

z=x

(yz)一、几个基本概念第三十一页，共七十三页，编辑于2023年，星期日常见半群：(1)<Z+,+>(2)<N,+>(3)<Z,+>但<Z,–>,<R+,÷>不是半群.只要验证运算是否可结合！(4)<Q,+>(5)<R,+>(6)<Mn(R),•>第三十二页，共七十三页，编辑于2023年，星期日含幺半群：V=<A,>是半群且含有幺元,即存在元eA,使得aA,ae=ea=a。如：<Mn(R),•>,幺元为n阶单位阵<Zn,+n>,幺元为[0]<Z,+>,幺元为0<R,+>,幺元为0含幺半群又称独异点.第三十三页，共七十三页，编辑于2023年，星期日子半群：<A,>是半群,B

A,且运算在B上仍封闭,则<B,

>是<A,>的子半群.子独异点：含幺元e的子半群,如：<N,+>是<Z,+>的子独异点平凡子独异点：V=<A,>是独异点,<{e},

>,V称为平凡子独异点.可交换半群：V=<A,

>是半群,且是可交换的.如<z,+>,<z+,+>等第三十四页，共七十三页，编辑于2023年，星期日半群中的幂：在含幺元半群V=<A,>中,规定：xA,x0=e,x1=xx0,x2=xx1,xn+1=xxn,则有xm+n=xm

xn,(xm)n

=xmn第三十五页，共七十三页，编辑于2023年，星期日独异点的性质：<A,>是独异点,则的运算表中没有任何两行或两列相同.证明：任取a,b(ab)所在行,由于A中含有幺元e,我们比较a行,b行中e列的元素ae=ab

e=b因为：ab,所以aebe,从而a行与b行不同,同理可证任两列不同.第三十六页，共七十三页，编辑于2023年，星期日群：设<G,>含幺元半群且对任何元素xG都有逆元x–1G(即逆元运算封闭).如：(1)<Q,•>Q=Q–{0},“•”普通乘法(2)<R,•>幺元为1但<Mn(R),•>是独异点,不是群.有限群：

G是有限集的群<G,>。|G|为有限群的阶数二、群的定义有典型群第三十七页，共七十三页，编辑于2023年，星期日交换群：群<G,>中,满足交换律,又称阿贝尔群.如：<Z,+>,<Q,+>,<R,+>,<P(A),>子群：设群<G,>,H是G的非空子集,如：<2Z,+>是<Z,+>的子群.如果H关于G中的运算构成群,则称<H,>为<G,>的子群,记作：HG.稍后还要专门介绍循环群，置换群，对称群。第三十八页，共七十三页，编辑于2023年，星期日子群的判定方法：设<G,>为群,H是G的非空子集,如果对任意的x,yH都有xy–1H,则H是G的子群,即HG.第三十九页，共七十三页，编辑于2023年，星期日三、群的性质：设<G,>是一个群,则(1)G中幺元唯一(2)逆元唯一(3)满足消去律,即a,b,cG,如果ab=ac,或者ba=ca,则有b=c.(4)G中一定没有零元(5)对任意的a,bG,必存在唯一的xG,使ax=b(或者xa=b)(6)对任意a,bG,(ab)–1

=b–1

a–1,(a–1)–1=a第四十页，共七十三页，编辑于2023年，星期日证明：设有两个幺元e,e',则e=ee'=e'证明：设元素x有两个逆元y,z,即xy=yx=e

zx=xz

=e

从而y=ye=y(xz)=(yx)z(1)G中幺元唯一(2)逆元唯一=ez=z第四十一页，共七十三页，编辑于2023年，星期日证明：如果ab=ac,由(2)知a存在唯一逆元a–1则a–1(ab)=a–1(ac)(a–1a)b=(a–1a)c所以eb=ecb=c(3)满足消去律,即a,b,cG,如果ab=ac,或者ba=ca,则有b=c.第四十二页，共七十三页，编辑于2023年，星期日证明：如果|G|=1,则它的唯一元素必是幺元；(4)G中一定没有零元与<G,>中每个元素可逆矛盾.如果|G|>1,假设<G,>有零元,则对于任何xG,有x=x=e,这说明G中任何元素x不可能成为的逆元。第四十三页，共七十三页，编辑于2023年，星期日证明：任取a,bG,由于G对逆元素封闭,故a有逆元a–1,且a–1G,因为a–1bG,令x=a–1b,则ax=a(a–1b)(5)对任意的a,bG,必存在唯一的xG,使ax=b(或者xa=b)=(aa–1)b=eb=b第四十四页，共七十三页，编辑于2023年，星期日证明：先证(ab)–1

=b–1

a–1,这是因为：(b–1a–1)(ab)=b–1(a–1(ab))=b–1((a–1a)b)所以(a

b)–1=b–1

a–1

=b–1(eb)=b–1b=e(ab)(b–1a–1)=a(b(b–1a–1))再证(a–1)–1

=a

这是因为：a–1a=e从而(a–1)–1=a

(6)对任意a,bG,(ab)–1

=b–1

a–1,(a–1)–1=aa

a–1=e=a((bb–1)a–1)=e第四十五页，共七十三页，编辑于2023年，星期日元素a的周期：<G,>是群,aG,使an=e成立的最小正整数n称为a的周期(或阶).如：幺元e的周期为1,<Z,+>中,非零整数的周期是无限的.周期的性质：设<G,>是群,若aG有有限周期r,则(1)ak=e

当且仅当k是r的倍数(2)a–1的周期亦为r(3)r

|G|四、循环群第四十六页，共七十三页，编辑于2023年，星期日证明：(充分性)设k=nr,则ak=anr=(ar)n=en=e(必要性)如果ak

=e,反设k不是r的倍数,则(1)ak=e

当且仅当k是r的倍数第四十七页，共七十三页，编辑于2023年，星期日=(ar)–1=e–1=e证明：反证,如果r>|G|,则a,a2,…,ar均为G中不同元素与|G|<r矛盾.证明：(a–1)r=a–1a–1…a–1r个(2)a–1的周期亦为r(3)r

|G|r个=(aa…a)–1第四十八页，共七十三页，编辑于2023年，星期日循环群：在群<G,

>中,如果存在元素aG,使得G={ak|k

Z}记作G=(a)a为(G,)的生成元例如：在N4={[0],[1],[2],[3]}中引入运算+4：[x],[y]N4,[x]+4[y]=[x+y]则得一循环群<

N4,+4>,生成元为[1].第四十九页，共七十三页，编辑于2023年，星期日循环群的性质(1)每个循环群必是阿贝尔群(即可交换群)(2)有限循环群<G,>,若|G|=n,则存在aG,使：G={a,a2,a3,…,an–1,an=e}证明(2)：假设存在某个正整数m,m<n使am=e,那么,由于<G,>是一个循环群,所以G中的任何元素都能写成ak(kZ),而且k=mq+r,q是某个整数,0rm,这就有：ak

=amq+r

=(am)qar

=ear

=ar第五十页，共七十三页，编辑于2023年，星期日这就有，ak

=ar从而G中每个元素都可以表示成ar(0rm),再证a,a2,…,an互不相同.反设ai=aj,其中1ijn,则有aj–i=e,而且1j–i<n,这与前面证明的矛盾,所以a,a2,…,an互不相同.由于|G|=n,所以an=e,从而G中元素为{a,a2,a3,…,an–1,an=e}这样,G中最多只有m个不同的元素,与|G|=n

相矛盾,所以am

=e(m<n)不可能.第五十一页，共七十三页，编辑于2023年，星期日n元置换：设S={x1,x2,…,xn},S上的任何双射函数：SS构成S上n个元素的置换,称为n元置换.记作：五、置换群与对称群第五十二页，共七十三页，编辑于2023年，星期日如：(1)S={1,2,3},令：SS且(1)=2,(2)=3,(3)=1,则有一个置换：123231(2)称为恒等置换,记作Is注：当|s|=n时,S上有n!个置换,把它们构成的集合记作：Sn第五十三页，共七十三页，编辑于2023年，星期日置换的运算(1)设S={x1,x2,…,xn}上有置换：P=则称为P的逆置换,记作:P–1.第五十四页，共七十三页，编辑于2023年，星期日(2)设S={x1,x2,…,xn}上有两个置换：P1=则称P=为P1与P2的合成,P2=显然:

Is=Is

=,这说明:Is是<Sn,

>中的幺元.记作：P=P2

P1.第五十五页，共七十三页，编辑于2023年，星期日置换群：可以证明Sn关于合成运算和上述逆运算构成一个群<Sn,>,称之为置换群。<Sn,>的任何一个子群也称为置换群,统称为S上的置换群.第五十六页，共七十三页，编辑于2023年，星期日解：

(1)先写出所有的置换,共3!=6个,例6.5

设S={1,2,3},写出S上所有的置换群P3=321123P4=213123P5=132123Pe=123123P1=231123P2=312123按顺序写：123第五十七页，共七十三页，编辑于2023年，星期日(2)再列出S3={pe,p1,p2,p4,p5}上关于合成运算的运算表pep1p2p3p4p5pep1p2p3p4p5pep1p2p3p4p5p1p2pep5p3p4p2pep1p5p3p4p3p4p5pep1p2p4p5p3p2pep1p5p3p4p1p2pe第五十八页，共七十三页，编辑于2023年，星期日(3)最后写S上的置换群(检验封闭性)<S3,><{p3,p4},><{pe,p1,p2},>都是S上的置换群.<{pe,p3},><{pe,p5},>对称群：称<Sn,>为n元对称群.第五十九页，共七十三页，编辑于2023年，星期日例6.6

设G为群,xG,问H={xk|kZ}是否为G的子群.解：首先HG其次任取H中的两个元素xm,xl,m,lZ则xm

(xl)–1=xm

(x

–1)l=xm–l

H注：称H为由x生成的子群,记作：<x>.第六十页，共七十三页，编辑于2023年，星期日6.5环与域环：设<A,,>是具有两个二元运算和的代数系统,(1)<A,>是交换群(或阿贝尔群

)；(2)<A,>是半群；(3)运算对运算是可分配的；则称<A,,>是环.如果：一、环的概念第六十一页，共七十三页，编辑于2023年，星期日例如：(1)R[x]={实系数多项式}关于通常意义下多项式的加法和乘法构成一个环,当然<R,+,x>是环.(2)<Mn(R),+,•>是环(3)<Z,+,•

>–––整数环<Q,+,•>–––有理数环<R,+,•>–––实数环<C,+,•>–––复数环第六十二页，共七十三页，编辑于2023年，星期日(4)<P(s),∪,∩>–––S的子集环(5)<Zn,,>–––模n的整数环其中：Zn

={[0],[1],…,[n–1]}[x],[y]Zn[x][y]=[x+y](modn)[x][y]=[xy](modn)第六十三页，共七十三页，编辑于2023年，星期日交换环：在环<A,,>中,运算是可交换的.含幺环：在环<A,,>中,运算有幺元.注：为了区别运算的幺元与的幺元,通常记的幺元为,记的幺元为e。第六十四页，共七十三页，编辑于2023年，星期日所以a,b,cA,a(bc)=(ab)(ac)a

(c)=(a)(ac)即a

c=(a)(ac)从而必有a

=,即对是零元.证明：由环的意义,对是可分配的,如果为运算的幺元,取b=,则有：可以证明：的幺元恰好是的零元.第六十五页，共七十三页，编辑于2023年，星期日左(右)零因子：在环<A,

,>中,如果存在a