離散數(shù)學(xué)(第五版)清華大學(xué)出版社第6章習(xí)題解答

離散數(shù)學(xué)第五版）清大學(xué)出版社第章習(xí)題答6.1A:⑨B:⑨;C:④D:⑥分析

對(duì)于給定的集合和運(yùn)算判別它們是否構(gòu)成代數(shù)系統(tǒng)的關(guān)鍵是檢查集合對(duì)給定運(yùn)算的封閉性,具體方法已節(jié)做過(guò)說(shuō)明.下面分別討論對(duì)各種不同代數(shù)系紡的判別方法.給定集合二元運(yùn)算°,判定<S,°>是否構(gòu)成關(guān)群、獨(dú)導(dǎo)和群.根據(jù)定義，判別時(shí)要涉及到以下條件的驗(yàn)證：條件1S關(guān)于°運(yùn)算封閉：條件2運(yùn)算滿足結(jié)合集條件3運(yùn)算有幺元，條件4?x∈?1∈其中關(guān)群判定只涉及條件1和2獨(dú)導(dǎo)點(diǎn)判定涉及條件1、2、和3；而群的判定則涉及到所有的四個(gè)條件。2給定集合S和二元運(yùn)算°和*°,*>是否構(gòu)成環(huán)交換環(huán)含幺環(huán),整環(huán),域.據(jù)有關(guān)定義需要檢驗(yàn)的條件有條件1°>S構(gòu)成交換群,條件2*>構(gòu)成關(guān)群,條件3*對(duì)°運(yùn)算的分配律,條件4*對(duì)運(yùn)算滿足交換律,條件5*運(yùn)算有幺元,條件6*運(yùn)算不含零因子——消去律，條件7|S|≥2,x∈S,x≠0,有?1S（對(duì)*運(yùn)算）.其中環(huán)的判定涉及條件1,2和交換環(huán)的判定涉及條件和4;幺環(huán)的判定涉及條件和環(huán)的判定涉及條件1-6;而域的判定則涉及全部7條件.3°判定偏序集<S,≤>或代數(shù)系統(tǒng)<是否構(gòu)成格本配格補(bǔ)格和布爾格73若<S,為偏序集,先驗(yàn)證?∧y和∨y否屬于S.若滿足條件則S為格,且∨∧構(gòu)成代數(shù)系統(tǒng)若S,o,*>是代數(shù)系統(tǒng)且°和*運(yùn)算滿足交換律、結(jié)合律和吸收律，則<S,o,*>構(gòu)成格。

在此基礎(chǔ)上作為分配格的充分必要條件是不含有與圖6.3所示的格同構(gòu)的子格。而有補(bǔ)格和布爾格的判定只要根據(jù)定義進(jìn)行即可。注意對(duì)于有限格，只要元素個(gè)數(shù)不是2的冪，則一定不是布爾格。但元素個(gè)數(shù)恰為的有限格中只有唯一的布爾格。以本題為例具體的判定過(guò)程如下：（1）n+n=2nS1可知S1對(duì)+運(yùn)算不封閉，根本不構(gòu)成代數(shù)系統(tǒng)。（2）由2*2=4?S2知S2*運(yùn)算不封閉，也不構(gòu)成代數(shù)系統(tǒng)。（3S3于運(yùn)算封閉，構(gòu)成代數(shù)系統(tǒng)。S3關(guān)于模加法o足交換群的定義于模乘法*足關(guān)群的定義*o分配律而<S3,o,*>構(gòu)成環(huán)。但當(dāng)時(shí)，有中含有零因子和，不是整環(huán)，也不是域。類(lèi)似地分析可知，當(dāng)n為合數(shù)時(shí)，是域，但n素?cái)?shù)時(shí)成域。（4偏序集。對(duì)于小于等于關(guān)系,x∧∨y=max{x,y}，然有x∧y,x∨∈S4成格但S4是有補(bǔ)格沒(méi)有補(bǔ)元也不是布爾代數(shù)。（5）容易驗(yàn)證S5于矩陣加法構(gòu)成群。6．2A:②;B:③;C:⑦;D:⑩;E:⑨分析此處的G實(shí)上是Z4.Zn關(guān)于模n加法構(gòu)成群，但關(guān)于模n乘法只構(gòu)成獨(dú)導(dǎo)點(diǎn)，而不構(gòu)成群，因?yàn)?沒(méi)乘法逆元。<G,>是循環(huán)群。2是階元，和34元。如何求群中元素的階？如果，則x∈G,|x|是n的正因子。首先找74到的正因子，并從小到大列出來(lái)，然后依次檢查每相正因子。使得xr=e最小的正因子r就是的階。本題的的正因子是1，2，4。由于21=2≠0.22=2⊕所以，。類(lèi)似地有31=,32=3⊕⊕⊕⊕3=0,而6.32A:②;B:④;C:⑤D:⑦;

分析（1根據(jù)布爾代數(shù)定義可知UI算適合交換律、結(jié)合律、冪等律、分配律、律等，適合消去律?x∈L,0VX=X,xV0=x,xV1=1,1Vx=1，所以是V運(yùn)算的幺元V運(yùn)算的零元于在布爾代數(shù)的表示∧∨,',0,1>中，01作為代數(shù)常數(shù)列出來(lái)的，所以，最小的子布爾代數(shù)應(yīng)包含所有的代數(shù)常數(shù)。經(jīng)驗(yàn)證{0,1}恰構(gòu)成子布爾代數(shù)，而是最小的子布爾代數(shù)。（）表達(dá)式的等價(jià)式與對(duì)偶式是兩個(gè)要,應(yīng)加以區(qū)別.容看出由吸收律、交換律、分配律有(ab)∨(a∧b∧c)(b∧=(ab)∨∧吸收集∧a)(b∧交換集=b∧∧c)分配律這說(shuō)明該表達(dá)式與b∨是等價(jià)的，而其他兩個(gè)表達(dá)式都不滿足要求。6.4易證Z°運(yùn)算是封閉的，且對(duì)任意x,y,z∈Z有(xoy)oz=(x+y?2)+z?2=x+y+x?4,xo(yoz)=xo(y+z?2)=x+(y+z?2)?2=x+y+z?4,75結(jié)合律成立2是運(yùn)算的幺元x∈Z,4?x是x關(guān)°運(yùn)算的逆元綜合上述，<Z，°>成群。6.5根據(jù)矩陣乘法可以得到G的運(yùn)算表如下：·bdacdbbadcccbaddcb由運(yùn)算表可以看出a是幺元。又由b2=a,c4=cc22=b2=a。知道G|與中元素x階相等時(shí)，有因此G是4循環(huán)群。的子群有{a},{a,b},G個(gè)。令S={{a},{a,b},G}，則<S,>的哈斯圖如圖所

示。分析這里對(duì)怎樣求一個(gè)循環(huán)群的生成元和子群做一點(diǎn)說(shuō)明。1°若G=<a>是無(wú)限循環(huán)群，那么G只有兩個(gè)生成元，即和?1。的子群有元數(shù)多個(gè)，它們分別由ak生成。這里的可以是，1…。將ak生成子群的元素列出來(lái)就是<ak>={e,ak,a?2k,L},該子群也是一個(gè)無(wú)限循環(huán)群。不難證明當(dāng)k≠l時(shí)，子群{ak}≠<al>。例如，是階循環(huán)群，那么G={e,a,L,anG的生成元有個(gè)，這里的φ(n)是歐拉圖函數(shù)小于等于n且與n素的正整數(shù)個(gè)數(shù)求生成元的方法是：先找到所有有小于等于且與互素的正整數(shù).對(duì)于每個(gè)這樣的正整數(shù)就是的階子群以本題為例.|D|=4,與4互素的數(shù)是和3.因此G=<c>的生成元是76c1=c,c3=d.再考慮子群.4的正因子是1,2,4以,G的子群有3個(gè)即414<c>=<c>=<a>={a}.階子群422<c>=<c>={b,a}.2階子群44階子群根據(jù)包含關(guān)系不難得到圖6.4所示的哈斯圖6.6Z[i]對(duì)普通加法和乘法是封閉,且加法滿足交換,結(jié)合律,乘法滿足結(jié)合,第六法對(duì)加法滿足分配律.又知道加法的幺元是a+bi∈?a?bi是a+bi的負(fù)元.而Z[i]關(guān)于加法和乘法構(gòu)成環(huán).易看出這是一個(gè)整環(huán),但不是域.6.7不是格,(2),(3)和(4)都是格6.8任取x,yS,由性質(zhì)有x⊕y=(x∧y)∨∧y)∈

關(guān)于⊕是封閉的成代數(shù)系統(tǒng)<S,⊕>.容易驗(yàn)證⊕運(yùn)算滿足結(jié)合幺元是0,因?yàn)?x∈x⊕0=(x∧∨∧∨(x'∧0)=x∨0=x.同理有0xx⊕x=(x∧(x''∧x)=0∨0=0.6.9X(2)?}.分析

設(shè)為群a,b∈G.群方程在G中有唯一解?1b.類(lèi)似地,群方程中也有唯一解y=ba?1.代入本題有X={1,3}?1⊕{3,4,5}={1,3}⊕由于對(duì)任何BP(A)有B⊕?,而有77n

Bn奇數(shù)B=?n偶數(shù)盡管<中包含了B的所有冪,但只有兩個(gè)結(jié)果即B和.6.10(1)σ=(124)(356),τ=(1634)(25).(2)στ=(15423)(356),σ=(15462),στσ?1=(15423)(563)(421)=(1256)(34).分析

為了求出σ的輪換表示,先任選一個(gè)元比如說(shuō)從上述表示式中找到σ(1).如果σ(1)=1,則第一個(gè)輪換就找到了

,(1).如果σ(1)=i1,i1≠1,接下去找σ(i1)=i2.繼續(xù)這一過(guò)程,直到某ik滿σ(ik)=1止.過(guò)這樣的挑選,{1,2,L,n}中選出了一個(gè)序列:其中的元素滿足σ(1)=i1,σ(i1)=i2,L,σ(ik)=ik,σ(ik)=1.這就是從中中解出來(lái)的第一個(gè)輪換?1(1,i1,i2Lik).如果該輪換包含了{(lán)1,2,L,n}中的所有元素那么分解結(jié)否并且有σ=(1,i1,i2Lik);否則任取{1,2,L,n}中沒(méi)有剩下的元素為止.以本題的σ為例由的置換表示知道σ(1)=2,σ(2)=4,σ(4)=4,σ(4)=1,從而得到第一個(gè)輪換著從{中選取3,繼續(xù)這一過(guò),得到σ(3)=6,σ(6)=5,σ(5)=3,這

就是第二個(gè)輪換(365).的元素都出現(xiàn)在輪換之中束,并且σ=(124)(365).在求置換σ的輪換表示時(shí)可將表示式中的1輪換省略例如σ=(13)(2)(46)(5)中的(2)和(5)都是1-輪換,可將σ簡(jiǎn)記為(此外要說(shuō)明的是表示式中的輪換是不相交即同一個(gè)元素不能出現(xiàn)在兩個(gè)輪換之中.如果交換了輪換的次序,者選擇了輪換中不同的元素作為首元素而保持順序不變那么所得的輪換表示是相同的.如,σ=(124)(365)可以寫(xiě)作σ=(365)(124)或σ=(124)(365)等給定n元置換σ和τ,怎樣求στ或σ?1,τ?1呢根據(jù)復(fù)合函數(shù)的定義只需求78出στ(1),στ(2),…,στ(n)就可到στ的置換表示或輪換表示

.以本題為例,στ(1)=σ(τ(1))=σ(6)=5.類(lèi)似地有τ(2)=3,στ(3)=1,στ(4)=2,τ(5)=4,στ(6)=6,從而得到στ=(15423)(6),化簡(jiǎn)為στ=(15423).逆的計(jì)算比乘法簡(jiǎn)單.設(shè)σ=ττLτ為σ的輪換表示式那么σ?1=?1,Lτ?1τ?1,其中的τ若為12kk21j換(i,iLi),則有?1=(iLii),j=1,2,L,k.例如,σ=(124)(365),則12lj12lσ?1=(563)(421).從而στσ?1=(τ)σ?1=(15423)(563)(421).而στσ?1(1)=τ(4)=2,,σσ?1(2)=στ(1)=5,στσ?1(3)=τ(5)=4,σσ?1(4)=στ(2)=3,στσ?1(5)=τ(6)=6,σσ?1(6)=στ(3)=1,因此,到στσ?1=(1256)(34).在στ?1=(5)的計(jì)算中στ(6)出現(xiàn)觀察到τ的表示式(中不含有6,就意味著τ(6)=(6).6.11(1)是同態(tài)映射當(dāng)G={e}時(shí)為單同態(tài)滿同態(tài)和同構(gòu)而當(dāng)不是平凡群時(shí),既不是單同態(tài),也不是滿同態(tài)(2)是同態(tài)映射,且為單同態(tài),不是滿同態(tài)(3)是同態(tài)映射,也是單同態(tài)和滿同態(tài).6.12(1)哈斯圖如圖6.5所示(2)可以構(gòu)成布爾代數(shù)x,y∈yxy的最小公倍數(shù),x∧是xy的最

大公約數(shù).A關(guān)于∨和∧運(yùn)算是封閉的容易驗(yàn)證∨和∧運(yùn)算滿足交換律,結(jié)合律,吸收律,且是互相可分配的,此,偏序集構(gòu)成分配格.?∈∨y是x與y的最小公倍數(shù),x∧yx的最大公約數(shù).而A關(guān)于∨和∧運(yùn)算是封閉的.容易驗(yàn)證∨和∧運(yùn)算滿足交換律結(jié)合律79吸收律,是互相可分配的,引,偏序集構(gòu)成分配格?x∈A,110是x的補(bǔ)元x這就證明了該偏序集構(gòu)成分配格.即布爾代數(shù).6.13(1)圖6.1中的3),(4),(5),(8)不是格.(3)圖中{f,g}沒(méi)有最小上界;(4)圖中的{沒(méi)有最大下界;圖中{d,e}有最大下界(8)圖中的{沒(méi)有最小上界(2)圖6.1中的(圖為分配但不是有補(bǔ)格和布爾;(6)圖不是分配格和布爾格,是有補(bǔ)格;圖不是分配格,不是有補(bǔ)格和布爾格.分析圖中格((2)的所有五元子格都不與圖中的格同構(gòu)因而它們都是分配格但對(duì)于圖6.1(6)和的格都能找