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

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

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

在此基礎(chǔ)上作為分配格的充分必要條件是不含有與圖6.3所示的格同構(gòu)的子格。而有補格和布爾格的判定只要根據(jù)定義進行即可。注意對于有限格，只要元素個數(shù)不是2的冪，則一定不是布爾格。但元素個數(shù)恰為的有限格中只有唯一的布爾格。以本題為例具體的判定過程如下：（1）n+n=2nS1可知S1對+運算不封閉，根本不構(gòu)成代數(shù)系統(tǒng)。（2）由2*2=4?S2知S2*運算不封閉，也不構(gòu)成代數(shù)系統(tǒng)。（3S3于運算封閉，構(gòu)成代數(shù)系統(tǒng)。S3關(guān)于模加法o足交換群的定義于模乘法*足關(guān)群的定義*o分配律而<S3,o,*>構(gòu)成環(huán)。但當(dāng)時，有中含有零因子和，不是整環(huán)，也不是域。類似地分析可知，當(dāng)n為合數(shù)時，是域，但n素數(shù)時成域。（4偏序集。對于小于等于關(guān)系,x∧∨y=max{x,y}，然有x∧y,x∨∈S4成格但S4是有補格沒有補元也不是布爾代數(shù)。（5）容易驗證S5于矩陣加法構(gòu)成群。6．2A:②;B:③;C:⑦;D:⑩;E:⑨分析此處的G實上是Z4.Zn關(guān)于模n加法構(gòu)成群，但關(guān)于模n乘法只構(gòu)成獨導(dǎo)點，而不構(gòu)成群，因為0沒乘法逆元。<G,>是循環(huán)群。2是階元，和34元。如何求群中元素的階？如果，則x∈G,|x|是n的正因子。首先找74到的正因子，并從小到大列出來，然后依次檢查每相正因子。使得xr=e最小的正因子r就是的階。本題的的正因子是1，2，4。由于21=2≠0.22=2⊕所以，。類似地有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運算的幺元V運算的零元于在布爾代數(shù)的表示∧∨,',0,1>中，01作為代數(shù)常數(shù)列出來的，所以，最小的子布爾代數(shù)應(yīng)包含所有的代數(shù)常數(shù)。經(jīng)驗證{0,1}恰構(gòu)成子布爾代數(shù)，而是最小的子布爾代數(shù)。（）表達式的等價式與對偶式是兩個要,應(yīng)加以區(qū)別.容看出由吸收律、交換律、分配律有(ab)∨(a∧b∧c)(b∧=(ab)∨∧吸收集∧a)(b∧交換集=b∧∧c)分配律這說明該表達式與b∨是等價的，而其他兩個表達式都不滿足要求。6.4易證Z°運算是封閉的，且對任意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是運算的幺元x∈Z,4?x是x關(guān)°運算的逆元綜合上述，<Z，°>成群。6.5根據(jù)矩陣乘法可以得到G的運算表如下：·bdacdbbadcccbaddcb由運算表可以看出a是幺元。又由b2=a,c4=cc22=b2=a。知道G|與中元素x階相等時，有因此G是4循環(huán)群。的子群有{a},{a,b},G個。令S={{a},{a,b},G}，則<S,>的哈斯圖如圖所

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

關(guān)于⊕是封閉的成代數(shù)系統(tǒng)<S,⊕>.容易驗證⊕運算滿足結(jié)合幺元是0,因為?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.類似地,群方程中也有唯一解y=ba?1.代入本題有X={1,3}?1⊕{3,4,5}={1,3}⊕由于對任何BP(A)有B⊕?,而有77n

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

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

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

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

.以本題為例,στ(1)=σ(τ(1))=σ(6)=5.類似地有τ(2)=3,στ(3)=1,στ(4)=2,τ(5)=4,στ(6)=6,從而得到στ=(15423)(6),化簡為στ=(15423).逆的計算比乘法簡單.設(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)的計算中στ(6)出現(xiàn)觀察到τ的表示式(中不含有6,就意味著τ(6)=(6).6.11(1)是同態(tài)映射當(dāng)G={e}時為單同態(tài)滿同態(tài)和同構(gòu)而當(dāng)不是平凡群時,既不是單同態(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)于∨和∧運算是封閉的容易驗證∨和∧運算滿足交換律,結(jié)合律,吸收律,且是互相可分配的,此,偏序集構(gòu)成分配格.?∈∨y是x與y的最小公倍數(shù),x∧yx的最大公約數(shù).而A關(guān)于∨和∧運算是封閉的.容易驗證∨和∧運算滿足交換律結(jié)合律79吸收律,是互相可分配的,引,偏序集構(gòu)成分配格?x∈A,110是x的補元x這就證明了該偏序集構(gòu)成分配格.即布爾代數(shù).6.13(1)圖6.1中的3),(4),(5),(8)不是格.(3)圖中{f,g}沒有最小上界;(4)圖中的{沒有最大下界;圖中{d,e}有最大下界(8)圖中的{沒有最小上界(2)圖6.1中的(圖為分配但不是有補格和布爾;(6)圖不是分配格和布爾格,是有補格;圖不是分配格,不是有補格和布爾格.分析圖中格((2)的所有五元子格都不與圖中的格同構(gòu)因而它們都是分配格但對于圖6.1(6)和的格都能找