離散數(shù)學(xué)代數(shù)系統(tǒng)

離散數(shù)學(xué)代數(shù)系統(tǒng)第一頁，共七十三頁，編輯于2023年，星期日§6.1代數(shù)運算及代數(shù)系統(tǒng)二元代數(shù)運算：設(shè)A是非空集合,如R*=R–{0}上的乘法,除法運算:f:AnA稱為A上的n元運算,n為運算階.函數(shù)f:AA是集合A上的一元代數(shù)運算,簡稱一元運算;如集合R－{0}上的求倒數(shù)運算；函數(shù)f:A2A稱為A上二元代數(shù)運算.一、代數(shù)運算的概念第二頁，共七十三頁，編輯于2023年，星期日集合的封閉性：給定集A,如Z對加、減、乘法封閉,對除法不封閉.如果對A上的元素進行某種運算后,運算結(jié)果仍在A中,則稱集A對該種運算封閉。第三頁，共七十三頁，編輯于2023年，星期日二、常見二元運算：(1)設(shè)Mn(R)表示所有n階實矩陣的集合,則矩陣加法和乘法運算是Mn(R)上的二元運算,且封閉;(2)S為任意集合,P(S)為其冪集,則∪,∩,–,都是P(S)上的二元運算,且封閉；(3)S為集合,Ss是S上的所有函數(shù)的集合,則合成運算o是Ss上的二元運算.第四頁，共七十三頁，編輯于2023年，星期日三、二元運算的性質(zhì)：(1)設(shè)是定義在集A上的二元運算,若對任意的x,yA都有yx=xy,則說具有可交換性；(2)如果對任意的x,y,zA,都有(xy)z=x(yz),則說具有可結(jié)合性；第五頁，共七十三頁，編輯于2023年，星期日(3)設(shè),是A上的兩個二元運算,如果對任意的x,y,zAx(yz)=(xy)(xz)(yz)x=(yx)(zx)則說對具有可分配性.第六頁，共七十三頁，編輯于2023年，星期日(4)設(shè),是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關(guān)于運算

的零元，有y=z,

(ⅱ)yx=zx

且x,有y

=z則是滿足消去律.第八頁，共七十三頁，編輯于2023年，星期日四、集A的特殊元：(1)幺元：是集A上的二元運算,如果elA且xA,有elx=x,則el為A中關(guān)于的左幺元；如何定義右幺元er(自己敘述一遍！)第九頁，共七十三頁，編輯于2023年，星期日如果A中的一個元素e,既是左幺元又是右幺元,則e為A中關(guān)于的幺元.可以證明：幺元是唯一的.證明：反證,若有兩個幺元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)可證：逆元存在則唯一(要求可結(jié)合)證明：設(shè)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年，星期日五、代數(shù)系統(tǒng)：非空集合S與S上的k個運算f1,f2,…,fk組成的系統(tǒng),稱為代數(shù)系統(tǒng),記作：

<S,f1,f2,…,fk>如<N,+>,<Z,+>,<R,+,?>,<Mn(R),+,?>,<P(S),∪,∩,–>第十四頁，共七十三頁，編輯于2023年，星期日§6.2同態(tài)與同構(gòu)同態(tài)：V1=<A,f1,…,fn>,V2=<B,1,…,n>是兩個代數(shù)系統(tǒng),其中fi

,i(i=1,2,…,n)都是二元運算。x,yA,f(xfiy)=f(x)if(y)(i=1,…,n)則稱f是V1到V2的一個同態(tài)映射,也說V1與V2同態(tài),記作V1f

V2或V1～V2.

f

如果存在映射f:AB

滿足：第十五頁，共七十三頁，編輯于2023年，星期日如：<R+,×>~<R,+>(只要定義f:R+R,f(ab)=lgab=lga+lgb=f(a)+f(b))當n=1時，設(shè)V1=<A,>，V2=<B,>是兩個代數(shù)系統(tǒng)。如果存在f:AB.使x,yA，f(xy)=f(x)f(y)則稱f

是V1到V2的一個同態(tài)映射。第十六頁，共七十三頁，編輯于2023年，星期日同態(tài)象：設(shè)V1=<A,>～V2=<B,>,則稱<f(A),>是V1在f下的同態(tài)象.f同態(tài)的性質(zhì)：設(shè)V1=<A,>～V2=<B,>,f(1)如果f:AB是滿射,則說f為V1到V2滿同態(tài)的(2)如果f是單射,則說f為V1到V2單同態(tài)的(3)如果f是雙射,則說f為V1與V2同構(gòu),記作(4)當V1=V2時,則說f是V1的自同態(tài)(自同構(gòu))第十七頁，共七十三頁，編輯于2023年，星期日例6.1<R,+>,<R,>是兩個代數(shù)系統(tǒng),f:RR,且xR,f(x)=2x,驗證f是<R,+>到<R,>的同態(tài),并且是單同態(tài).驗證：任取x,yR由于f(x+y)=2x+y=2x2y=f(x)

f(y)所以f是<R,+>到<R,>的自同態(tài)；

其次,對任取的x,yR,當xy時,2x

2y,即f(x)f(y),f為單射,從而f是單自同態(tài)第十八頁，共七十三頁，編輯于2023年，星期日例6.2

設(shè)A={a,b,c,d},B={[0],[1],[2],[3]}且f:AB,f(a)=[0],f(b)=[1],f(c)=[2],f(d)=[3]代數(shù)系統(tǒng)<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>的同構(gòu).第二十頁，共七十三頁，編輯于2023年，星期日同態(tài)與同構(gòu)的意義(1)V1=<A,>與V2=<B,+4>

同態(tài),則V1中所具有的運算性質(zhì),可以保持在同態(tài)象中；(2)對于滿同態(tài),V1的運算在V2中仍保持；(3)如果V1V2,則它們的性質(zhì)完全相同,可以看成一個東西不加區(qū)別(代數(shù)角度).第二十一頁，共七十三頁，編輯于2023年，星期日§6.3同余關(guān)系與商代數(shù)模n同余關(guān)系：Z是整數(shù)集,在Z中定義關(guān)系R={<x,y>|x,yZ

xy(modn)}其中,xy(modn)的含義是x–y可以被n整除.不難驗證:R是Z上的等價關(guān)系(自反、對稱、傳遞),我們稱該等價關(guān)系為模n同余關(guān)系.由同余關(guān)系R可得商集：Z/R={[0],[1],…,[n–1]},記作：Zn.一、模n同余關(guān)系的概念第二十二頁，共七十三頁，編輯于2023年，星期日同余關(guān)系與剩余類：設(shè)代數(shù)系統(tǒng)V=<A,>,是集A上的二元運算,(1)R是A上的等價關(guān)系；(2)a1,a2,b1,b2A,(a1Ra2)(b1Rb2)(a1b1)R(a2b2)則稱R是A上對運算的同余關(guān)系,或稱V上的同余關(guān)系。如果集A上存在關(guān)系R滿足：由同余關(guān)系將A劃分的等價類稱為剩余類.二、一般同余關(guān)系的定義第二十三頁，共七十三頁，編輯于2023年，星期日例6.3

設(shè)代數(shù)系統(tǒng)<A,>,A={a,b,c,d},見下列運算表：abcdaadcbacdcdabddbaabcd第二十四頁，共七十三頁，編輯于2023年，星期日再規(guī)定A上的一個關(guān)系：R={<a,a>,<a,b>,<b,a>,<b,b>,<c,c>,<c,d>,<d,c>,<d,d>}則可驗證：(1)R是等價關(guān)系(2)x,y,u,vA如果(xRy)(uRv),則(xu)R(yv)(驗證方法：在R中任取2個元素，如<a,b>,<d,d>;<a,a>,<c,c>……等加以驗證)第二十五頁，共七十三頁，編輯于2023年，星期日例6.4

代數(shù)系統(tǒng)<Z,>中,Z是整數(shù)集,是一元運算,且zZ,zz=z2(modm),m為一自然數(shù).設(shè)R是Z上的模m同余關(guān)系可以證明：R是Z上的同余關(guān)系(2)對任意的z1,z2Z,如果z1Rz2即z1z2(modm)(1)R顯然是等價關(guān)系證明：第二十六頁，共七十三頁，編輯于2023年，星期日往證：z1z1=z12(modm)與z2z2=z22(modm)具有R關(guān)系,即z12(modm)Rz22(modm),這是因為：z1z2(modm)z1=a1m+ro,z2=a2m+ro,其中0rom–1第二十七頁，共七十三頁，編輯于2023年，星期日三、同余關(guān)系的判定：<A,>與<B,>是兩個代數(shù)系統(tǒng)。證明：(1)R是等價關(guān)系f：AB是同態(tài)映射。利用f規(guī)定A上的二元關(guān)系R：aRb當且僅當f(a)=f(b)，則R是同余關(guān)系。第二十八頁，共七十三頁，編輯于2023年，星期日由同態(tài)映射的定義知：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年，星期日商代數(shù)：V=<A,>是一個代數(shù)系統(tǒng),是二元運算。A/R={[x]R|xA}在A/R中規(guī)定二元運算：[x]R,[y]RA/R,[x]R

[y]R

=[xy]R則稱<A/R,>為V關(guān)于R的商代數(shù),記作V/R.R是V中的同余關(guān)系,A/R是A關(guān)于R的商集。四、同余關(guān)系的應(yīng)用第三十頁，共七十三頁，編輯于2023年，星期日§6.4群半群：代數(shù)系統(tǒng)V=<A,>中,是非空集合A上的二元運算,且在A中是可結(jié)合的,即x,y,zA(xy)

z=x

(yz)一、幾個基本概念第三十一頁，共七十三頁，編輯于2023年，星期日常見半群：(1)<Z+,+>(2)<N,+>(3)<Z,+>但<Z,–>,<R+,÷>不是半群.只要驗證運算是否可結(jié)合！(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,>中,規(guī)定：xA,x0=e,x1=xx0,x2=xx1,xn+1=xxn,則有xm+n=xm

xn,(xm)n

=xmn第三十五頁，共七十三頁，編輯于2023年，星期日獨異點的性質(zhì)：<A,>是獨異點,則的運算表中沒有任何兩行或兩列相同.證明：任取a,b(ab)所在行,由于A中含有幺元e,我們比較a行,b行中e列的元素ae=ab

e=b因為：ab,所以aebe,從而a行與b行不同,同理可證任兩列不同.第三十六頁，共七十三頁，編輯于2023年，星期日群：設(shè)<G,>含幺元半群且對任何元素xG都有逆元x–1G(即逆元運算封閉).如：(1)<Q,?>Q=Q–{0},“?”普通乘法(2)<R,?>幺元為1但<Mn(R),?>是獨異點,不是群.有限群：

G是有限集的群<G,>。|G|為有限群的階數(shù)二、群的定義有典型群第三十七頁，共七十三頁，編輯于2023年，星期日交換群：群<G,>中,滿足交換律,又稱阿貝爾群.如：<Z,+>,<Q,+>,<R,+>,<P(A),>子群：設(shè)群<G,>,H是G的非空子集,如：<2Z,+>是<Z,+>的子群.如果H關(guān)于G中的運算構(gòu)成群,則稱<H,>為<G,>的子群,記作：HG.稍后還要專門介紹循環(huán)群，置換群，對稱群。第三十八頁，共七十三頁，編輯于2023年，星期日子群的判定方法：設(shè)<G,>為群,H是G的非空子集,如果對任意的x,yH都有xy–1H,則H是G的子群,即HG.第三十九頁，共七十三頁，編輯于2023年，星期日三、群的性質(zhì)：設(shè)<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年，星期日證明：設(shè)有兩個幺元e,e',則e=ee'=e'證明：設(shè)元素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,假設(shè)<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成立的最小正整數(shù)n稱為a的周期(或階).如：幺元e的周期為1,<Z,+>中,非零整數(shù)的周期是無限的.周期的性質(zhì)：設(shè)<G,>是群,若aG有有限周期r,則(1)ak=e

當且僅當k是r的倍數(shù)(2)a–1的周期亦為r(3)r

|G|四、循環(huán)群第四十六頁，共七十三頁，編輯于2023年，星期日證明：(充分性)設(shè)k=nr,則ak=anr=(ar)n=en=e(必要性)如果ak

=e,反設(shè)k不是r的倍數(shù),則(1)ak=e

當且僅當k是r的倍數(shù)第四十七頁，共七十三頁，編輯于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年，星期日循環(huán)群：在群<G,

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

Z}記作G=(a)a為(G,)的生成元例如：在N4={[0],[1],[2],[3]}中引入運算+4：[x],[y]N4,[x]+4[y]=[x+y]則得一循環(huán)群<

N4,+4>,生成元為[1].第四十九頁，共七十三頁，編輯于2023年，星期日循環(huán)群的性質(zhì)(1)每個循環(huán)群必是阿貝爾群(即可交換群)(2)有限循環(huán)群<G,>,若|G|=n,則存在aG,使：G={a,a2,a3,…,an–1,an=e}證明(2)：假設(shè)存在某個正整數(shù)m,m<n使am=e,那么,由于<G,>是一個循環(huán)群,所以G中的任何元素都能寫成ak(kZ),而且k=mq+r,q是某個整數(shù),0rm,這就有：ak

=amq+r

=(am)qar

=ear

=ar第五十頁，共七十三頁，編輯于2023年，星期日這就有，ak

=ar從而G中每個元素都可以表示成ar(0rm),再證a,a2,…,an互不相同.反設(shè)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元置換：設(shè)S={x1,x2,…,xn},S上的任何雙射函數(shù)：SS構(gòu)成S上n個元素的置換,稱為n元置換.記作：五、置換群與對稱群第五十二頁，共七十三頁，編輯于2023年，星期日如：(1)S={1,2,3},令：SS且(1)=2,(2)=3,(3)=1,則有一個置換：123231(2)稱為恒等置換,記作Is注：當|s|=n時,S上有n!個置換,把它們構(gòu)成的集合記作：Sn第五十三頁，共七十三頁，編輯于2023年，星期日置換的運算(1)設(shè)S={x1,x2,…,xn}上有置換：P=則稱為P的逆置換,記作:P–1.第五十四頁，共七十三頁，編輯于2023年，星期日(2)設(shè)S={x1,x2,…,xn}上有兩個置換：P1=則稱P=為P1與P2的合成,P2=顯然:

Is=Is

=,這說明:Is是<Sn,

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

P1.第五十五頁，共七十三頁，編輯于2023年，星期日置換群：可以證明Sn關(guān)于合成運算和上述逆運算構(gòu)成一個群<Sn,>,稱之為置換群。<Sn,>的任何一個子群也稱為置換群,統(tǒng)稱為S上的置換群.第五十六頁，共七十三頁，編輯于2023年，星期日解：

(1)先寫出所有的置換,共3!=6個,例6.5

設(shè)S={1,2,3},寫出S上所有的置換群P3=321123P4=213123P5=132123Pe=123123P1=231123P2=312123按順序?qū)懀?23第五十七頁，共七十三頁，編輯于2023年，星期日(2)再列出S3={pe,p1,p2,p4,p5}上關(guān)于合成運算的運算表pep1p2p3p4p5pep1p2p3p4p5pep1p2p3p4p5p1p2pep5p3p4p2pep1p5p3p4p3p4p5pep1p2p4p5p3p2pep1p5p3p4p1p2pe第五十八頁，共七十三頁，編輯于2023年，星期日(3)最后寫S上的置換群(檢驗封閉性)<S3,><{p3,p4},><{pe,p1,p2},>都是S上的置換群.<{pe,p3},><{pe,p5},>對稱群：稱<Sn,>為n元對稱群.第五十九頁，共七十三頁，編輯于2023年，星期日例6.6

設(shè)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環(huán)與域環(huán)：設(shè)<A,,>是具有兩個二元運算和的代數(shù)系統(tǒng),(1)<A,>是交換群(或阿貝爾群

)；(2)<A,>是半群；(3)運算對運算是可分配的；則稱<A,,>是環(huán).如果：一、環(huán)的概念第六十一頁，共七十三頁，編輯于2023年，星期日例如：(1)R[x]={實系數(shù)多項式}關(guān)于通常意義下多項式的加法和乘法構(gòu)成一個環(huán),當然<R,+,x>是環(huán).(2)<Mn(R),+,?>是環(huán)(3)<Z,+,?

>–––整數(shù)環(huán)<Q,+,?>–––有理數(shù)環(huán)<R,+,?>–––實數(shù)環(huán)<C,+,?>–––復(fù)數(shù)環(huán)第六十二頁，共七十三頁，編輯于2023年，星期日(4)<P(s),∪,∩>–––S的子集環(huán)(5)<Zn,,>–––模n的整數(shù)環(huán)其中：Zn

={[0],[1],…,[n–1]}[x],[y]Zn[x][y]=[x+y](modn)[x][y]=[xy](modn)第六十三頁，共七十三頁，編輯于2023年，星期日交換環(huán)：在環(huán)<A,,>中,運算是可交換的.含幺環(huán)：在環(huán)<A,,>中,運算有幺元.注：為了區(qū)別運算的幺元與的幺元,通常記的幺元為,記的幺元為e。第六十四頁，共七十三頁，編輯于2023年，星期日所以a,b,cA,a(bc)=(ab)(ac)a

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

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

=,即對是零元.證明：由環(huán)的意義,對是可分配的,如果為運算的幺元,取b=,則有：可以證明：的幺元恰好是的零元.第六十五頁，共七十三頁，編輯于2023年，星期日左(右)零因子：在環(huán)<A,

,>中,如果存在a