離散數(shù)學(xué)課后習(xí)題答案 （邱學(xué)紹） 圖9.證明方法1:設(shè)T結(jié)點(diǎn)數(shù)為n,分支點(diǎn)數(shù)?i。根據(jù)完全二元樹(shù)的定義，可知下面等式均成立:(1)2i由式⑴，⑵，⑶易知m2t2。方法2：在完全二元樹(shù)中，除樹(shù)葉外，每個(gè)結(jié)點(diǎn)的出度為定理知2。除樹(shù)根外，每個(gè)結(jié)點(diǎn)的入度為由握手n2md(V9.證明方法1:設(shè)T結(jié)點(diǎn)數(shù)為n,分支點(diǎn)數(shù)?i。根據(jù)完全二元樹(shù)的定義，可知下面等式均成立:(1)2i由式⑴，⑵，⑶易知m2t2。方法2：在完全二元樹(shù)中，除樹(shù)葉外，每個(gè)結(jié)點(diǎn)的出度為定理知2。除樹(shù)根外，每個(gè)結(jié)點(diǎn)的入度為由握手n2md(Vi)nd(Vi)12(n3(mt)1)2t3n2t解得：m2t2。.證明設(shè)完全二元樹(shù)又結(jié)點(diǎn)數(shù)nit,所以tT有i個(gè)分支點(diǎn)，t片樹(shù)葉，由T為完全二元樹(shù)，則由7.2節(jié)定理3有i(n1)/2為T(mén)的樹(shù)葉數(shù)。t1。.解對(duì)于圖7-21所示的二元樹(shù)，三種遍歷方法的結(jié)果如下:先根遍歷:中根遍歷:后根遍歷:V0V1V3V4V6V2V5V7V8V9V3V1V6V4V0V5V8V7V9V2V3V6V4V1V8V9V7V5V2V00(左)12.解設(shè)圖7-22⑴所示的樹(shù)為T(mén)i,Ti是完全二元樹(shù)。在每個(gè)分支結(jié)點(diǎn)引出的兩條邊上分別標(biāo)上和1(右)，則得如圖7-23⑴0(左)B{0000,0001,001,0100,01010,01011,011,1},則Bi,為前綴碼。設(shè)圖7-22⑵中所示的樹(shù)為T(mén)2,T2是二元樹(shù)，但不是完全二元樹(shù)。對(duì)于有一個(gè)兒子的分支結(jié)點(diǎn)引出的邊可隨便標(biāo)上0或1;有兩個(gè)兒子的分支點(diǎn)標(biāo)法同 T1,則得如圖7-23⑵的樹(shù)，所得前綴碼為B2。B2{00,0100,01010,011,11}

(1)(1)圖13.解：其實(shí)，W(T)等于T的各分支點(diǎn)的權(quán)之和，即W(T)510152555⑵由T形成的二元前綴碼為B{000,001,01,10,11}。14.解應(yīng)該用較短的符號(hào)串傳輸出現(xiàn)頻率高的數(shù)字，因而可用100乘各數(shù)字出現(xiàn)的頻率作為權(quán),求最14.解應(yīng)該用較短的符號(hào)串傳輸出現(xiàn)頻率高的數(shù)字，因而可用100乘各數(shù)字出現(xiàn)的頻率作為權(quán),求最100乘各頻率得權(quán)100乘各頻率得權(quán)w0 30,w120,w2 15,w3 10, w4 10, w5 6,w6 5,ww0 30,w1得到4,5,6,10,10,15,20,30。(1)所求最優(yōu)二元樹(shù)如圖7-25所示。

⑵用所求的最優(yōu)二元樹(shù)產(chǎn)生二元前綴碼如圖 7-25所示。帶權(quán)為wi的樹(shù)葉對(duì)應(yīng)的符號(hào)串就為傳輸 i的符號(hào)串。數(shù)字0,1,2,3,4,5,6,7對(duì)應(yīng)的符號(hào)串分別為01,11,001,100,101,0001,00000,00001.⑶用這樣的符號(hào)串傳輸按上述比例出現(xiàn)的數(shù)字最少。104_ _ 40.32104104_ _ 40.32104__ 4 4 40.221040.153104_ 4 -0.131040.134 _ 4 _ 410 0.14 _ 4 _ 410 0.1310 0.06410一一一 一4一一 一0.05510 0.04527400所以彳^輸10000所以彳^輸10000個(gè)上述比例出現(xiàn)的數(shù)字至少要用27400個(gè)二進(jìn)制數(shù)字。15.證明設(shè)二部圖G的互補(bǔ)結(jié)點(diǎn)子集為V1、V2,貝Um=V1V2且V1+V15.證明設(shè)二部圖G的互補(bǔ)結(jié)點(diǎn)子集為定，只有當(dāng)它們相等時(shí)積最大，即當(dāng)V1=V2=n/2時(shí)，積V1V2最大為n2/4,亦即mn2/4。.解 令V1= {P1, P2,…，P7} , V2={a1,嗎…，a10},以V1和V2的元素作結(jié)點(diǎn)，若Pi是a的合格工作崗位,則在Pi和句之間連一邊，因此，可得二部圖如圖 7-26o去掉圖7-26 邊(P1,a0, (Pi,%), (P3向),(Pi,&) ,(P2㈤,(P5,a1)代6忿),依㈤,則圖7-26的子圖如圖 7-27。而圖7-27滿足t(t=1)條件,所以，存在Vi到V2的匹配M={(P1,a9),修向),(P3,%),(P4,a3),(P5,ai0),(P6,a1),(P7,a2)},因此，圖7-26中也存在Vi到V2的匹配M={(P1,a9),(P2,a7),(P3,a6),(P4,a3),(P5,ai0),(P6,a1),(P7,a2)}。這樣安排使得所有的人都有工作。

P4 Pl P3 P2 P5 P6 P7圖.解以V1={L1,L2,L3,L4,L5,L6},V2={G1,G2,G3,G4,G5,G6}作為互補(bǔ)結(jié)點(diǎn)集, 若Li和Gj互相滿意對(duì)方，則在Li和Gj之間連一邊，這樣得到一個(gè)二部圖如圖 7-28,由圖7-28可以看出，此圖滿足滿足t(t=2)條件,所以，存在V1到V2的匹配，因此，可使得每一個(gè)青年男女都能夠找到自己滿意的對(duì)象，其中一個(gè)分配方法是M={(L1,G1),(L2G3),(L3G4),(L4,G2),(L5,G6),(L6,G5)}。第八章 代數(shù)系統(tǒng)習(xí)題8.1.解⑴是，⑵不是，⑶是，⑷不是,…一 ?*.解若*對(duì)0是可分配的，則有任意 a,b,cGI，均有a*(bOc)=(a*b)O(a*c)=aboac=(abac)=ab+c而a*(boc)=a*(bc)=abcwab+c故*對(duì)o是不可分配的。.解⑴對(duì)于任意AGP(S),因?yàn)锳S,所以，AS=S,因此，S是關(guān)于運(yùn)算的零元；⑵對(duì)于任意AGP(S),因?yàn)锳S,所以，AS=A,因此，S是關(guān)于運(yùn)算的零元單。.解⑴①因?yàn)閤*y=xy-2x-2y+6,貝Uy*x=yx-2y-2x+6=x*y,滿足交換律；②任意x,y,zGR有x*(y*z)=x*(yz-2y-2z+6)=x(yz-2y-2z+6)-2x-2(yz-2y-2z+6)+6=xyz-2xy-2xz+6x-2x-2yz+4y+4z-12+6=xyz-2xy-2xz-2yz+4x+4y+4z-6.(x*y)*z=(xy-2x-2y+6)*z=(xy-2x-2y+6)z-2(xy-2x-2y+6)-2z+6=xyz-2xz-2yz+6z-2xy+4x+4y-2z-6=x*(y*z).故滿足結(jié)合律。(2)①設(shè)任意aeR,存在eGR,要e*a=ea-2e-2a+6=a,由于a的任意性則e=3。因此e=3是其單位元；②設(shè)任意bGR,zGR,要有z*b=zb-2z-2b+6=z,由于b的任意性則z=2,因止匕z=2是其零元。1 ^111(3)因?yàn)?是滿足父換律，對(duì)于xGR,要存在xGR,須有x*x=xx-2x-2x+6=e=3,當(dāng)x2時(shí)，x12x31。即對(duì)于任意的x,當(dāng)x2時(shí)x都是可逆的，且x2x35.解f1,f2,f3都滿足交換律，f4滿足等募率，f2有單位元x2a,f3有零元bof1abf2abaaaaabbaabbaf3abf4ababaaabbaababa,fi有零元習(xí)題8.21.解構(gòu)成代數(shù)系統(tǒng)的運(yùn)算有(2),(3),(4)。2.解{0}，4,{0,2},4,{0,1,2,3},習(xí)題8.31.證明作函數(shù)的x,yA都有abcaabcbbbcccbc(a)(b)表8-2f:{a,b,c}-{,,},f(a)=,f(b)=,f(c)=.顯然此映射是雙射。由表8-2可知對(duì)于任意有f(xy)=f(x)of(y),故<慶，*>l<B,o>02.解代數(shù)系統(tǒng) R,R,不可能同構(gòu)。因?yàn)?，由同?gòu)的性質(zhì)，如果兩個(gè)代數(shù)系統(tǒng)同構(gòu),則兩個(gè)系統(tǒng)的單位元對(duì)應(yīng)，零元對(duì)應(yīng)，而這里，代數(shù)系統(tǒng) ＜R,＞的零元是0,而＜R,+＞沒(méi)有零元。故代數(shù)系統(tǒng)R,R,不可能同構(gòu)。復(fù)習(xí)題八1.解⑴有單位元e=<1,0>,因?yàn)?，?duì)于任意＜a,b＞eS,均有<1,0a,b1a,1a,b，且,a,b1,0a1,aa,b,故<1,0>單位元⑵對(duì)于<a,b>€S,要＜a,b＞有逆元,需要有<x,y>GS使得，<a,b><x,y>=<x,y><a,b>=<1,0>事實(shí)上,1一1一，ya1b一,aa(a,b)即<1,0>=<a,b><x,y>=<ax,ay+b>,因止匕，ax=1,ay+b=0,當(dāng)a0時(shí)可解得xa,b1,0。故當(dāng)a0時(shí)，形式的元素 a,b都可逆，且b——。,aa2.解因?yàn)閍*b=b*aa=b,則任意a€A,而*是可結(jié)合的，則有a*(a*a)=(a*a)*a,因此a*a=a2.解因?yàn)閍*b=b*a滿足等嘉律..證明假設(shè)f:Q-Q-{0}是從＜Q,+＞至iJ＜Q-{0},＞的同構(gòu)，則兩個(gè)系統(tǒng)的單位元對(duì)應(yīng)，即有f(0)=1因?yàn)閒是從Q到Q-{0}的滿射，所以，對(duì)于任意一個(gè)素?cái)?shù)pGQ-{0}必存在某個(gè)xGQ,使得f(x)=p,又由于f是一個(gè)同構(gòu)，因此有p=f(x)=f((x-1)+1)=f(x-1) f(1),而在Q-{0}中有無(wú)窮多個(gè)素?cái)?shù)，因此，總可以找到一個(gè)素?cái)?shù)p,使得x-10,則f(x-1)不是1,這與p是素?cái)?shù)矛盾。證畢。.證明因?yàn)?，aaa,(ab)(cd)(ac)(bd),所以，a(bc)(aa)(bc)(ab)(ac)。.證明對(duì)n用數(shù)學(xué)歸納法。當(dāng)n=1時(shí)，由嘉的定義則(a*b)1=a*b=(a1)*(b1),所以結(jié)論成立。假設(shè)n=k時(shí)結(jié)論成立，即(a*b)k=ak*bk,下面考察n=k+1時(shí)，(a*b)k+1=(a*b)k*(a*b)=(ak*bk)*(a*b)=(ak*a)*(bk*b)=ak+1*bk+1。即門(mén)=卜+1時(shí)，結(jié)論也成立。由歸納法原理，對(duì)于任意的正整數(shù) n,都有(a*b)n=an*bn。.證明任意m,n2GN,只有如下的三種情況：① m,n2都能表示成2的嘉的形式，②m,n2都不能表示成2的嘉的形式，③一個(gè)能表示成 2的嘉的形式，而另一個(gè)不能。下面就這三種情況分別考慮。①設(shè)存在k1,k2^N,使得n〔=2k1,n2=2k2,則n〔xn2=2k1x2k2=2k1+k2GN,且f(n1)=f(n2)=1,因此f(n1Xn2)=f(2k1+k2)=1=f(n1)xf(n2)=f(2k1)xf(2k2);②n1,n2都不能表示成2的寨的形式，則mxn2也不能表示成2的寨的形式，所以，f(n1)=f(n2)=0,因此f(n1xn2)=0=f(n1)xf(n2)。③不妨設(shè)存在kGN,使得m=2k,,而n2不能表示成2的嘉的形式，則n〔xn2也不能表示成2的嘉的形式，所以，f(n1)=1,f(n2)=0,因此，f(n1xn2)=0=f(n1)xf(n2)。綜上所述，代數(shù)結(jié)構(gòu) N,與{0,1},同態(tài)。第九章特殊的代數(shù)系統(tǒng)習(xí)題9.1.解⑴是半群。顯然，二元運(yùn)算“ ”在N上是封閉的，所以，N,是一個(gè)代數(shù)系統(tǒng),另一方面,a,b,cN,有abcmaxa,bcmaxa,b,c,另一方面,而abcamaxb,cmaxa,b,c,因此，abcabc,而abcamaxb,c滿足結(jié)合律的，故 N, 是半群;⑵是半群。顯然，二元運(yùn)算“”在N上是封閉的，所以，N,是一個(gè)代數(shù)系統(tǒng),c,而abcacc,則另一方面， a,b,cN,有c,而abcacc,則abcabc,所以，運(yùn)算“”滿足結(jié)合律，故 N,是半群;⑶是半群。顯然，二元運(yùn)算在n上是封閉的，所以，N, 是一個(gè)代數(shù)系統(tǒng),另一方面,a,b,cN,⑶是半群。顯然，二元運(yùn)算在n上是封閉的，所以，N, 是一個(gè)代數(shù)系統(tǒng),另一方面,a,b,cN,有abc(2ab)c2(2ab)c4abc,abca(2bc)2a2bc4abc，即abcabc,所以，運(yùn)算滿足結(jié)合律，故N,是半群⑷不是半群。雖然，二元運(yùn)算在⑷不是半群。雖然，二元運(yùn)算在N上是封閉的，即N, 是一個(gè)代數(shù)系統(tǒng)，但是對(duì)于5,3,6,對(duì)于5,3,6,因?yàn)椋?36 536怛64,而5(36)536 536|2,即5(36)536 536|2,即5365(36),所以，運(yùn)算不滿足結(jié)合律，故N, 不是半群。.解⑴正確。因?yàn)?，運(yùn)算顯然封閉。⑵正確。(ab)c(abab)cabcabacbcabc,a(bc)a(bcbc)abcabacbc,即是abcabc,所以滿足結(jié)合律。故R,是半群N,有0a0a0aa,又有a0a0aa,即存在單位元是0,故R, 是獨(dú)異點(diǎn)flab表f2abaaaaabbaabbaf3abf4ababaaabbaabab3.解fl,f3,f4都不能使＜{a,b},＞構(gòu)成獨(dú)異點(diǎn)，因?yàn)闆](méi)有一個(gè)函數(shù)存在單位元。而

f2的單位元是a,＜{a,b},f2＞能構(gòu)成獨(dú)異點(diǎn)4.解⑴是，因?yàn)镸={2,3}關(guān)于min是封閉的，故＜M02是＜$皿2的子代數(shù)；＜M,min＞是＜$四g＞的子半群；⑶不是，因?yàn)镾的單位元是4,而4M,故＜M,min＞不是＜§min＞的子獨(dú)異點(diǎn)。習(xí)題9.2.解⑴是，因?yàn)閷?shí)數(shù)乘法滿足結(jié)合律，存在單位元 a0=1,任意元素a存在逆元素a-1;⑵是，因?yàn)橛欣頂?shù)乘法滿足結(jié)合律，存在單位元 1,任意元素a存在逆元素sr1;(3)是，因?yàn)閺?fù)數(shù)乘法滿足結(jié)合律，存在單位元 1,任意元素z的逆元素是z共羯復(fù)數(shù)；(4)是，因?yàn)槎囗?xiàng)式的加法滿足結(jié)合律，多項(xiàng)式關(guān)于加法的單位元是 0多項(xiàng)式，任意元素P(x)的逆元素是-P(x).(5)是，因?yàn)橄蛄康募臃M足結(jié)合律， n維實(shí)向量關(guān)于向量的加法的單位元是 n維零向量，任意的n維實(shí)向量的逆元素是-。.解可以構(gòu)成群。⑴因?yàn)?，?duì)于任意的 x,y,zI,(xy)z(xy2)z2xy z 4 x (y z2)2x(yz),所以，運(yùn)算o蔭足結(jié)合律；，⑵關(guān)于運(yùn)算。有單位元2,這是因?yàn)閷?duì)于任意的aI,都有a2a22a,且2a 2 a 2 a;⑶對(duì)于任意的aI,若要a有逆元b,需要有ab=ba=2,即需要a+b-2=b+a-2=2,事實(shí)上只要b=a-4即可。因此，對(duì)于任意的aI,a都可逆，且a的逆元是a-4。綜上所述，由⑴，(2，⑶得出結(jié)論 I與運(yùn)算。能構(gòu)成群。_ 1.證明因?yàn)閷?duì)于任意的aG,aa1,所以a可逆，且aa,因此，＜g,*＞是群。要證明＜g,*＞是Abel群，只需證明運(yùn)算滿足交換律， 事實(shí)上，因?yàn)?，?duì)于任意的x,yG,xx1,yy1,所以(xx) (yy)1(xy)(xy),因止匕，由結(jié)合律則有x(y x)y x(xy) y,再由消去律得：y xxy。故＜g,*＞是Abel群。TOC\o"1-5"\h\z\o"CurrentDocument"1 1 1- .4.證明當(dāng)x0 abcab時(shí)，因?yàn)椋? 1 1axobaa(abcab)ba=bc,1 1 1所以，x0 abca b 是萬(wàn)程axb a b c的解。下面萬(wàn)程的解是唯一的。對(duì)于a,b,c G,若axb a bc解y,即a y b ab c,由于群中的任何元素都可逆，則對(duì)上式兩邊同時(shí)左乘a-1,并兩邊同時(shí)右乘a-1b-1則得，a1(ayb a) (a1b1)a 1 (b c)(a 1b1)由結(jié)合律則有，ya1bca1b1。證畢。

5.證明設(shè)1是群G的單位元，若G中存在嘉等元a,即aaa因?yàn)槿褐械娜魏卧囟伎赡?，因此，a也可逆，則有1 1,1、aa(aa)aa(aa)a1a故單位元為G中惟一的嘉等元。6.解答案是A,因?yàn)榇嬖谕瑧B(tài)映射f:RR-{0},f(x)=ex,但不存在同構(gòu)映射。習(xí)題9.3.解1,5,7,11為其生成元，任何與12互素的正整數(shù)都可作＜N12,+12＞的生成元。.證明設(shè)H是循環(huán)群G的子群，且G的生成元是a。若H={e},則H是循環(huán)群。若H，{e},由于H非空，則必存在正整數(shù) m＞0使amGH。設(shè)m是使amGH的最小的正整數(shù)，若對(duì)于任何的an€H(nN),則由帶余除法有n=mk+r,0＜r＜m則有ar=an-mk=ana-mk=an(am) GH,而因?yàn)閙是使amGH的最小的正整數(shù)，且00r＜m,所以r=0這樣n=mk,an=amk=(am),再由anCH的任意性知，H中的任意元素都是am的幕，故H=(am),即循環(huán)群的任何子群都是循環(huán)群。習(xí)題9.41.證明①顯然HG;②證明運(yùn)算*關(guān)于H的封閉性。任取a,bH,對(duì)于任意的xG有axxa,bxxb,則(ab)xa(bx)a(xb)(ax)b(xa)bx(ab),因止匕，abH；③設(shè)1是G中的單位元，因?yàn)閷?duì)于任意的 xG有x1 1x故，1H；④任取aHG,對(duì)于任意的xG,則由H的定義有，x*a=a*x,由于群的元素都有逆元，因此a也有逆元。等式x*a=a*x兩邊同時(shí)左乘、并同時(shí)右乘a的逆元a-1則有，1 , 、 1 1 , 、 1一1 1 、一1a(xa)aa(ax)a,即axxa,亦即xH。2.解群G,綜合①、②、③、④，＜H,*＞是2.解群G,真子群有如下4個(gè):<{1},>,<{1,5},>,<{1,7},><{1,11},>習(xí)題9.510 i0 0i.解⑴設(shè)E ,A ,B ,C01 0ii0G={E,A,B,C,-E,-A,-B,-C},G關(guān)于運(yùn)算的運(yùn)算表如下。表2G關(guān)于運(yùn)算的運(yùn)算表EABC-E-A-B-CEEABC-E-A-B-CAA-E-CB-AEC-BBBC-E-A-B-CEA

CC-BA-E-CB-AE-E-E-A-B-CEABC-A-AEC-BA-E-CB-B-B-CEABC-E-A-C-CB-AEC-BA-E由表1可以看出G關(guān)于運(yùn)算是封閉的。而運(yùn)算是矩陣的乘法運(yùn)算，因此滿足結(jié)合律。由表1可以看出G關(guān)于運(yùn)算的單位元是E。由表1可以進(jìn)一步看出關(guān)于運(yùn)算，G中的每一個(gè)元素都有逆元，E-1=E,A-1=-A,B-1=-B,C-1=-C,(-E)-1=-E,(-A)-1=A,(-B)-1=B,(-C)-1=C因此，＜G,＞是一個(gè)群。⑵G的所有子群是：＜{E},＞,＜{E,-E},＞,＜{E,A,-A,-E},＞,＜{E,B,-B,-E},＞,＜{E,C,-C,-E},＞。⑶證明顯然＜{E},＞,＜{E,-E},＞是正規(guī)子群，下面證明＜{E,A,-A,-E},＞是正規(guī)子群。設(shè)H={E,A,-A,-E},顯然有EH=HE=(-E)H=H(-E)=AH=HA=(-A)H=H(-A)={E,A,-A,-E}。又BH={B,C,-C,-B},HB={B,-C,C,-B}=BH,因此有H(-B)={B,-C,C,-B}=(-B)H。同理可得，CH=HC=H(-C)=(-C)H={C,-B,B,-C}。綜上所述，對(duì)于任意的aG都有aH=Ha,即＜H,＞是正規(guī)子群。同理可證，＜{E,B,-B,-E},＞,＜{E,C,-C,-E},＞也是正規(guī)子群。.解5,{3,7,11},{0,4,8}。習(xí)題9.6.解I[i]對(duì)于普通加法和乘法能構(gòu)成環(huán)。這是因?yàn)椋孩棚@然I[i]對(duì)加法+是封閉的，而復(fù)數(shù)的加法是滿足交換律和結(jié)合律的， ＜I[i],+＞的單位元是0=0+0i,任意元素a+bi的逆元是-a-bi。所以，＜I[i],+＞是可交換群。⑵I[i]對(duì)復(fù)數(shù)的加法是封閉的，且復(fù)數(shù)的乘法是滿足結(jié)合律的，即＜I[i],＞是半群。⑶復(fù)數(shù)的乘法對(duì)復(fù)數(shù)的加法滿足分配律。綜合⑴⑵⑶，I[i]對(duì)于普通加法和乘法能否構(gòu)成環(huán)。.證明⑴首先證明 {ab^2|a,b I},, 是一個(gè)環(huán)。設(shè)R {a b＜2|a,bI}對(duì)于任意的a b&,cdV2R,因?yàn)?，a,b,c,di,所以，(a+c),(b+d),(ac+2bd),(ad+bc)I,因止匕，(abV2)(cdV2)(ac) (b d)＜2R,(abV2)(c dV2)=(ac2bd)(ad bc)石R,故R對(duì)于加法和乘法都是封閉的。另一方面，實(shí)數(shù)的普通加法滿足結(jié)合律和交換律，且關(guān)于加法單位元是0,每個(gè)元素都有逆元，就是相反數(shù)。實(shí)數(shù)的普通乘法也滿足結(jié)合律。綜合上述 ＜R,+,＞是一個(gè)環(huán)。⑵因?yàn)?，?shí)數(shù)的普通乘法也滿足交換律， 且R關(guān)于乘法有單位元1,又對(duì)于abV2,cdJ2 R,若兩者都不為零，則 (a bd2)(c dJ2) 0,即＜R,+,＞無(wú)零因子。綜合⑴⑵可知，＜r,+,＞是一個(gè)整環(huán)。.證明設(shè)F={a+bia,bQ},對(duì)于任意的a+bi,c+diF,因?yàn)?，a,b,c,dQ,所以,a+c,b+d,ac-bd,ad+bcQ,因此，(a+bi)+(c+di)=(a+c)+(b+d)iF,且(a+bi)(c+di)=(ac-bd)+(ad+bc)iF,即F關(guān)于加法和乘法運(yùn)算都是封閉的；而普通的加法和乘法都滿足結(jié)合彳t和交換律；又關(guān)于加法 +,F中有單位元0=0+0i,且每個(gè)元素a+bi都有逆元-a-bio故＜尸,+,＞是一個(gè)環(huán)。另一方面，＜F,＞中有單位元1=1+0i;又對(duì)于任何的非零元a+bi,因?yàn)?，a,b不全為零，所以，a2+b20,

因此對(duì)于任何的非零元a+bi都有逆元。綜上所述，＜F,+,＞是一個(gè)域。復(fù)習(xí)題九.解⑴＜G,*＞是半群，但不是獨(dú)異點(diǎn)，更不是群；⑵不是半群；⑶不是半群，- 10⑷是群，其單位元是 。01.證明對(duì)于任意的a,b,cR,有(ab)c(abab)cababcacbcabc同時(shí)，a(bc)abcabbcacabc,故(ab)ca(bc),所以滿足結(jié)合律，故是＜R,*＞半群；又存在0R,且0aa00a0aa故。是單位元。綜上所述，＜R,*＞是獨(dú)異點(diǎn)。.證明對(duì)于任意的x,yS,因?yàn)?，xyxay,其中aS,為S; 的二元運(yùn)算，而S,是半群,又aS,所以，xa y S,即S,對(duì)運(yùn)算是封閉的。又因?yàn)镾, 是半群，所以， S, 有結(jié)合律，即對(duì)于任意的x,y,zS有，(xy)z(xay)azx a (yaz) x(yaz)x (yz)故＜s,*＞滿足結(jié)合律，綜上所述，＜s,*＞是半群。4.證明對(duì)于任意a,b,cS,由于＜s,*＞是半群，所以,<S,*>有結(jié)合律,a*c=c*a且b*c=c*b,則(ab)(bc)(cb)(ac)b(ca)bc(ab)4.證明對(duì)于任意a,b,cS,由于＜s,*＞是半群，所以,<S,*>有結(jié)合律,a*c=c*a且b*c=c*b,則(ab)(bc)(cb)(ac)b(ca)bc(ab)。5.證明對(duì)于任意a,bSa,b是＜S,*＞的嘉等元，則aa=a,bb=b,再由交換律和結(jié)合律則,(ab)(ab)(aa)(bb)a故a*b也是＜S,*＞的嘉等元。6.證明對(duì)于任意的a,b,c,d,e,fS,有6.證明對(duì)于任意的a,b,c,d,e,fS,有a,bc,dac,bd以，＜s,*＞是封閉的，又因?yàn)?a,bc,d)e,(ac)e,(b2bd)f2(bd2bd)fe,bd2bd2bf2df4bdfa(ce),b(df2df)2b(df2df)a,b(c,de,f)(a,bc,d)e,(ac)e,(b2bd)f2(bd2bd)fe,bd2bd2bf2df4bdfa(ce),b(df2df)2b(df2df)a,b(c,de,f)因此，＜S,*＞是半群；又取0,0S,所以，a,b0,0 0,0a,ba,b ，故存在單位元＜0,0＞所以＜s,*＞是獨(dú)異點(diǎn)，且a,bc,dac,bd2bdca,db2dbc,da,b即交換律成立，故＜s,*＞是可交換獨(dú)異點(diǎn)。.證明因?yàn)椋?x0=0e{0},所以，運(yùn)算封閉，又結(jié)合律是顯然的，故 ＜{0},x＞是子半群。但1{0},所以，＜{0},x＞不是子獨(dú)異點(diǎn)。.證明N4 {0,1,2,3},則{0},{1},{0,1},{0,2},{0,1,2},{0,1,2,3}都能與X4構(gòu)成＜N4,X4＞的子半群，其中＜{0},X4＞是獨(dú)異點(diǎn)，但不是＜N4,X4＞的子獨(dú)異點(diǎn)。.證明對(duì)于任意的a,bGG,由題設(shè)則有，a4b4(ab)4(ab)3(ab)a3b3ab因此，由消去律可得，TOC\o"1-5"\h\z,3 ,3 _\o"CurrentDocument"ab ba ①同理，由a5b5 (ab)5(ab)4aba4b4ab可得，\o"CurrentDocument"4 4 _\o"CurrentDocument"abba ②再由①②兩式可得，4 4 3 3 3baab(ab)b(ba)bbab由消去律消去上式中的b3可得，baab。故＜g,*＞是可交換群。.解群＜N5,+5＞只有兩個(gè)子群H1={0}和H2=N5,其中H1的左陪集和右陪集如下：0H1=H10={0},1H1=Hi1={1},2H1=Hi2={2},3H1=Hi3={3},4H1=Hi4={4};H2的左陪集和右陪集如下：0H2=H20=1H2=H21=2H2=H22=3H2=H23=4H2=H24=N5。.證明任取aH,bHGG/H,因?yàn)?，＜G,*＞是可交換群，所以對(duì)于a,bGG,有a*b=b*a又因?yàn)?，＜H,*＞是＜G,*＞的正規(guī)子群，所以，任意的aGG,都有aH=Ha由以上兩式，則有，(aH)*(bH)=a(Hb)*H=a(bH)*H=(ab)(H*H)=(ab)H(bH)*(aH)=b(Ha)*H=b(aH)*H=(ba)(H*H)=(ba)H=(ab)H即(aH)*(bH)=(bH)*(aH)。由于aH,bH的任意性,所以，商群＜G/H,*＞也是可交換群。.證明⑴先證明f是雙射。對(duì)任意的X1,X2 G,若f(xjf(X2),即有a*x1*a-1=a*x2*a-1,由群的消去律可得X1=X2,所以，f是單射。又對(duì)于任意的y^G,貝1J有X=a-1*y*a€G,使得f(X)=a*X*a-1=a*(a-1*y*a)*a-1=y。即f是滿射，故f是雙射。

⑵再證f是同態(tài)映射。對(duì)于任意的 x1,x2 G有i i i、f(x1 x2)a(x1 x2)a(a x1)(a a)(x2 a)ii

(ax1a )(a x2a )f(x1) f(x2)綜合⑴⑵可知，f是<G,*>到其自身的同構(gòu)映射。第十章 格和布爾代數(shù)習(xí)題10.1.解⑴不是，因?yàn)長(zhǎng)中的元素對(duì){2,3}沒(méi)有最小上界；⑵是，因?yàn)長(zhǎng)={1,2,3,4,6,9,12,18,36 }任何一對(duì)元素a,b,都有最小上界和最大下界；⑶是，與⑵同理；⑷不是，因?yàn)長(zhǎng)中的元素對(duì){6,7}沒(méi)有最小上界不存在最小上界。.證明⑴因?yàn)?，a<b,所以,aVb=b;又因?yàn)?，b<c,所以,bAc=b。故aVb=bAc；⑵因?yàn)?，a<b<c,所以，aAb=a,bAc=b,而aVb=b,因止匕，(aAb)V(bAc)=b；又aVb=b,bVc=c,而bAc=b,因止匕，(aVb)A(bVc)=b。即(aAb)V(bAc)=(aVb)A(bVc)。習(xí)題10.2.解由圖1知：<S,不是<L,的子格，這是因?yàn)?，eVf=gS;<&,W>不是<L,的子格，?.eAf=c S2;<Ss,<>是<L,<>的子格..解S24的包含5個(gè)元素的子格有如下的 8個(gè)：S={1,3,6,12,24},S 2={1,2,6,12,24},S 3={1,2,4,12,24},S 4={1,2,4,8,24},㈢={1,2,3,6,12},S 6={1,2,4,6,12},S 7={2,4,6,12,24},S7={2,4,8,12,24}..證明因?yàn)?，一條線上的任何兩個(gè)元素都有(偏序)關(guān)系，所以，都有最大下界和最小上界，故它是格，又因?yàn)樗?lt;L,V,A>的子集，即是<L,V,A>的子代數(shù)，故是子格。.證明由(10-4)有，aAb^a,由已知si<c,由偏序關(guān)系的傳遞性有， aAb^c；同理 aAb<do由(10-5)和以上兩式有，aAb<cAd..證明因?yàn)橛?10-4)有，aAb<a,因此，(aAb)V(cAd)<aV(cAd) ①由分配不等式有，aV(cAd)<(aVc)A(siVd) ②再由由(10-4)有,

(aVc)A(aVd)(aVc)A(aVd)<aVc由偏序關(guān)系的傳遞性和①②③則有,(aAb)V(cAd)心c同理 ( aAb)V(cAd)＜bVd因此有， (aAb)V(cAd)＜(aVc)A(bVd)。習(xí)題10.3.解⑴是，全上界是24,全下界是1;(2)1的補(bǔ)元是24;3的補(bǔ)元是8;8的補(bǔ)元是3,4、6沒(méi)有補(bǔ)元。.解圖3是兩個(gè)格的哈斯圖，其中圖⑴是有補(bǔ)格但不是分配格的例子； 圖⑵是分配格但不是有補(bǔ)格的例子。.證明先證充分性。由已知條件知，對(duì)于任何的 a,b,c€L,有(aVb)Ac《aV(bAc),因此和等嘉律、交換律可得，(aVb)Ac=((bVa)Ac)Ac<(b/(aAc))Ac=((aAc)Vb)Ac<(Mc)V(bAc)又因?yàn)?(aAc)w(aVb)Ac且(bAc)<(aVb)Ac,由①②可得,所以,(a(aAc)V(bAc)由①②可得,所以,(a(aAc)V(bAc)<(aVb)AcAc)V(bAc)=(aVb)Ac再由交換律得到,cA(aVb)=(cAa)V(cAb)再由交換律得到,由此式容易證明cV(aAb)=(cVa)A(cVb)由③④可知它是分配格。再證必要fiEo因?yàn)椋糒,0＞是分配格，則(aVb)Ac=(aAc)V(bAc)W(bAc)。4.證明因?yàn)椋?ab)(ab)(aa)(abb)000；同理有，(ab)(ab)(ab)(bab)4.證明因?yàn)椋?ab)(ab)(aa)(abb)000；同理有，(ab)(ab)(ab)(bab)111；又因?yàn)檠a(bǔ)元素是唯一的，故(ab)b成立。習(xí)題10.4.解是布爾代數(shù),因?yàn)椋糀,0＞是有補(bǔ)分配格。-,V,A在B上都是封閉的，因此，由運(yùn)算.證明因?yàn)椋?,V,A在B上都是封閉的，因此，由運(yùn)算的定義可知，運(yùn)算在B上也是封閉的。又運(yùn)算V，八都滿足交換律。因此，對(duì)于任意的 a,bB,ab(ab)(ab)=ab(ab)(ab)=((ab)a)((ab)b)=(ba)(ab)(ab)(ab)由其對(duì)稱(chēng)性可知滿足交換律。下面證明運(yùn)算滿足結(jié)合律，X^于任意的 a,b,cB由上式則有(ab)c[(ab)(ab)]([(ab)(ab)]c)((ab)(ab)c)(abc)(abc)[(ab)(ab)c](abc)(ac)(abc)(abc)([(ab)(ab)]c)((ab)(ab)c)(abc)(abc)[(ab)(ab)c](abc)(ac)(abc)(abc)同理可得a(bc)(abc)(ac)(abc)(abc)a(bc)(abc)(ac)(abc)(abc)