離散數(shù)學(xué)答案-屈婉玲版-第二版-高等教育出版社課后答案

離散數(shù)學(xué)答案 屈婉玲版第二版 高等教育出版社課后答案第一章部分課后習(xí)題參考答案16 設(shè)p、q的真值為0；r、s的真值為1，求下列各命題公式的真值。 （1）p(qr) 0(01) 0 （2）（pr）(qs) （01）(11) 010. （3）（pqr）(pqr) （111） (000)0(4)（rs）(pq) （01）(10) 00117判斷下面一段論述是否為真：“是無(wú)理數(shù)。并且，如果3是無(wú)理數(shù)，則也是無(wú)理數(shù)。另外6能被2整除，6才能被4整除?！贝穑簆: 是無(wú)理數(shù) 1 q: 3是無(wú)理數(shù) 0 r: 是無(wú)理數(shù) 1 s:6能被2整除 1t: 6能被4整除 0 命題符號(hào)化為： p(qr)(ts)的真值為1，所以這一段的論述為真。19用真值表判斷下列公式的類型：（4）(pq) (qp)（5）(pr) (pq)（6）(pq) (qr) (pr)答： （4） p q pq q p qp (pq)(qp) 0 0 1 1 1 1 1 0 1 1 0 1 1 1 1 0 0 1 0 0 1 1 1 1 0 0 1 1 所以公式類型為永真式（5）公式類型為可滿足式（方法如上例）（6）公式類型為永真式（方法如上例）第二章部分課后習(xí)題參考答案3.用等值演算法判斷下列公式的類型，對(duì)不是重言式的可滿足式，再用真值表法求出成真賦值.(1) (pqq)(2)(p(pq)(pr)(3)(pq)(pr)答：(2)（p(pq)）(pr)(p(pq)(pr)ppqr1 所以公式類型為永真式(3) P q r pq pr （pq）(pr)0 0 0 0 0 10 0 1 0 0 10 1 0 1 0 00 1 1 1 0 01 0 0 1 0 01 0 1 1 1 11 1 0 1 0 01 1 1 1 1 1 所以公式類型為可滿足式4.用等值演算法證明下面等值式：(2)(pq)(pr)(p(qr)(4)(pq)(pq)(pq) (pq)證明（2）(pq)(pr) (pq)(pr)p(qr)p(qr)（4）(pq)(pq)(p(pq) (q(pq)(pp)(pq)(qp) (qq)1(pq)(pq)1(pq)(pq) 5.求下列公式的主析取范式與主合取范式，并求成真賦值(1)(pq)(qp)(2)(pq)qr(3)(p(qr)(pqr)解：（1）主析取范式(pq)(qp) (pq)(qp) (pq)(qp) (pq)(qp)(qp)(pq)(pq)(pq)(pq)(pq) (0,2,3) 主合取范式： (pq)(qp) (pq)(qp) (pq)(qp) (p(qp)(q(qp) 1(pq) (pq) M1 (1) (2) 主合取范式為： (pq)qr(pq)qr (pq)qr0 所以該式為矛盾式. 主合取范式為(0,1,2,3,4,5,6,7) 矛盾式的主析取范式為 0 (3)主合取范式為：(p(qr)(pqr) (p(qr)(pqr)(p(qr)(pqr)(p(pqr)(qr)(pqr) 11 1 所以該式為永真式. 永真式的主合取范式為 1 主析取范式為(0,1,2,3,4,5,6,7)第三章部分課后習(xí)題參考答案14. 在自然推理系統(tǒng)P中構(gòu)造下面推理的證明： (2)前提：pq,(qr),r結(jié)論：p (4)前提：qp,qs,st,tr結(jié)論：pq證明：（2）(qr) 前提引入qr 置換qr 蘊(yùn)含等值式r 前提引入q 拒取式pq 前提引入p（3） 拒取式證明（4）：tr 前提引入t 化簡(jiǎn)律qs 前提引入st 前提引入qt 等價(jià)三段論（qt）(tq) 置換（qt） 化簡(jiǎn)q 假言推理qp 前提引入p 假言推理(11)pq 合取 15在自然推理系統(tǒng)P中用附加前提法證明下面各推理：(1) 前提：p(qr),sp,q結(jié)論：sr證明s 附加前提引入sp 前提引入p 假言推理p(qr) 前提引入qr 假言推理q 前提引入r 假言推理16在自然推理系統(tǒng)P中用歸謬法證明下面各推理：(1)前提：pq,rq,rs 結(jié)論：p證明：p 結(jié)論的否定引入pq 前提引入q 假言推理rq 前提引入r 化簡(jiǎn)律rs 前提引入r 化簡(jiǎn)律rr 合取由于最后一步rr 是矛盾式,所以推理正確.第四章部分課后習(xí)題參考答案3. 在一階邏輯中將下面將下面命題符號(hào)化,并分別討論個(gè)體域限制為(a),(b)條件時(shí)命題的真值:(1) 對(duì)于任意x,均有x2-2=(x+2)(x-2).(2) 存在x,使得x+5=9.其中(a)個(gè)體域?yàn)樽匀粩?shù)集合. (b)個(gè)體域?yàn)閷?shí)數(shù)集合.解：F(x): x2-2=(x+2)(x-2). G(x): x+5=9.(1)在兩個(gè)個(gè)體域中都解釋為，在（a）中為假命題，在(b)中為真命題。(2)在兩個(gè)個(gè)體域中都解釋為，在（a）(b)中均為真命題。4. 在一階邏輯中將下列命題符號(hào)化:(1) 沒(méi)有不能表示成分?jǐn)?shù)的有理數(shù).(2) 在北京賣菜的人不全是外地人.解:(1)F(x): x能表示成分?jǐn)?shù) H(x): x是有理數(shù)命題符號(hào)化為: (2)F(x): x是北京賣菜的人 H(x): x是外地人命題符號(hào)化為: 5. 在一階邏輯將下列命題符號(hào)化: (1) 火車都比輪船快. (3) 不存在比所有火車都快的汽車. 解:(1)F(x): x是火車; G(x): x是輪船; H(x,y): x比y快命題符號(hào)化為: (2) (1)F(x): x是火車; G(x): x是汽車; H(x,y): x比y快命題符號(hào)化為: 9.給定解釋I如下: (a) 個(gè)體域D為實(shí)數(shù)集合R. (b) D中特定元素a =0. (c) 特定函數(shù)f(x,y)=x-y,x,y. (d) 特定謂詞F(x,y):x=y,G(x,y):x<y,x,y. 說(shuō)明下列公式在I下的含義,并指出各公式的真值:(1)(2)答:(1) 對(duì)于任意兩個(gè)實(shí)數(shù)x,y,如果x<y, 那么xy. 真值1.(2) 對(duì)于任意兩個(gè)實(shí)數(shù)x,y,如果x-y=0, 那么x<y. 真值0.10. 給定解釋I如下： （a） 個(gè)體域D=N(N為自然數(shù)集合). （b） D中特定元素a=2. （c） D上函數(shù)fx,y =x+y,g(x,y)=xy. （d） D上謂詞F(x,y):x=y.說(shuō)明下列各式在I下的含義，并討論其真值.(1) xF(g(x,a),x)(2) xy(F(f(x,a),y)F(f(y,a),x)答:(1) 對(duì)于任意自然數(shù)x, 都有2x=x, 真值0.(2) 對(duì)于任意兩個(gè)自然數(shù)x,y,使得如果x+2=y, 那么y+2=x. 真值0.11. 判斷下列各式的類型:(1) Fx,yGx,yFx,y.(3) xyF(x,y)xyF(x,y).解:(1)因?yàn)?為永真式； 所以 Fx,yGx,yFx,y.為永真式；(3)取解釋I個(gè)體域?yàn)槿w實(shí)數(shù)F(x,y)：x+y=5所以,前件為任意實(shí)數(shù)x存在實(shí)數(shù)y使x+y=5，前件真；后件為存在實(shí)數(shù)x對(duì)任意實(shí)數(shù)y都有x+y=5，后件假，此時(shí)為假命題再取解釋I個(gè)體域?yàn)樽匀粩?shù)N，F(xiàn)(x,y)：:x+y=5所以,前件為任意自然數(shù)x存在自然數(shù)y使x+y=5，前件假。此時(shí)為假命題。此公式為非永真式的可滿足式。13. 給定下列各公式一個(gè)成真的解釋，一個(gè)成假的解釋。(1) x(F(x)G(x)(2) x(F(x)G(x)H(x)解:(1)個(gè)體域:本班同學(xué)F(x)：x會(huì)吃飯, G(x)：x會(huì)睡覺(jué).成真解釋F(x)：x是泰安人,G(x)：x是濟(jì)南人.（2）成假解釋(2)個(gè)體域:泰山學(xué)院的學(xué)生F(x)：x出生在山東,G(x):x出生在北京,H(x):x出生在江蘇,成假解釋.F(x)：x會(huì)吃飯,G(x)：x會(huì)睡覺(jué),H(x)：x會(huì)呼吸. 成真解釋.第五章部分課后習(xí)題參考答案5.給定解釋如下:(a)個(gè)體域D=3,4;(b)f為(c). 試求下列公式在下的真值.(1) (3)解:(1) (2) 12.求下列各式的前束范式。(1) (5) (本題課本上有錯(cuò)誤)解:(1) (5) 15.在自然數(shù)推理系統(tǒng)F中,構(gòu)造下面推理的證明:(1) 前提: ,結(jié)論: xR(x)(2) 前提: x(F(x)(G(a)R(x), xF(x)結(jié)論:x(F(x)R(x)證明(1) 前提引入 F(c) EI 前提引入 假言推理 (F(c)G(c)R(c) UI F(c)G(c) 附加 R(c) 假言推理 xR(x) EG(2)xF(x) 前提引入F(c) EIx(F(x)(G(a)R(x) 前提引入F(c)(G(a)R(c) UIG(a)R(c) 假言推理R(c) 化簡(jiǎn)F(c)R(c) 合取引入x(F(x)R(x) EG 第六章部分課后習(xí)題參考答案5.確定下列命題是否為真：（1） 真 （2） 假（3） 真（4） 真（5）a,ba,b,c,a,b,c 真（6）a,ba,b,c,a,b 真（7）a,ba,b,a,b 真（8）a,ba,b,a,b 假6設(shè)a,b,c各不相同，判斷下述等式中哪個(gè)等式為真:（1）a,b，c,=a,b,c 假（2）a ,b,a=a,b 真（3）a，b=a,b 假（4），a,b=,a,b 假8求下列集合的冪集：（1）a,b,c P(A)= ,a,b,c,a,b,a,c,b,c,a,b,c（2）1，2，3 P(A)= , 1, 2,3, 1，2，3 （3） P(A)= , （4）， P(A)= , 1, 2,3, 1，2，3 14化簡(jiǎn)下列集合表達(dá)式：（1）（AB）B ）-（AB）（2）（ABC）-（BC）A解:(1)（AB）B ）-（AB）=（AB）B ）（AB）=（AB）（AB）)B=B=（2）（ABC）-（BC）A=（ABC）（BC）A=（A（BC）（BC ）（BC）A=（A（BC）A=（A（BC）A=A18某班有25個(gè)學(xué)生，其中14人會(huì)打籃球，12人會(huì)打排球，6人會(huì)打籃球和排球，5人會(huì)打籃球和網(wǎng)球，還有2人會(huì)打這三種球。已知6個(gè)會(huì)打網(wǎng)球的人都會(huì)打籃球或排球。求不會(huì)打球的人數(shù)。解: 阿A=會(huì)打籃球的人，B=會(huì)打排球的人，C=會(huì)打網(wǎng)球的人 |A|=14, |B|=12, |AB|=6,|AC|=5,| ABC|=2, |C|=6,CAB如圖所示。25-(5+4+2+3)-5-1=25-14-5-1=5不會(huì)打球的人共5人21.設(shè)集合A1，2，2，3，1，3,計(jì)算下列表達(dá)式：（1）A（2）A（3）A（4）A解: （1）A=1，22，31，3=1，2，3,（2）A=1，22，31，3=（3）A=123= （4）A=27、設(shè)A,B,C是任意集合，證明(1)(A-B)-C=A- BC(2)(A-B)-C=(A-C)-(B-C)證明(1) (A-B)-C=(AB) C= A( BC)= A(BC) =A- BC(2) (A-C)-(B-C)=(AC) (B C)= (AC) (BC)=(ACB) (ACC)= (ACB) = A(BC) =A- BC 由（1）得證。第七章部分課后習(xí)題參考答案7.列出集合A=2,3,4上的恒等關(guān)系I A,全域關(guān)系EA,小于或等于關(guān)系LA,整除關(guān)系DA.解：IA =<2，2>,<3,3>,<4,4> EA=<2,2>,<2,3>,<2,4>,<3,4>,<4,4>,<3,2>,<3,3>,<4,2>,<4,3>LA=<2,2>,<2,3>,<2,4>,<3,3>,<3,4>,<4,4>DA=<2,4>13.設(shè)A=<1,2>,<2,4>,<3,3> B=<1,3>,<2,4>,<4,2>求AB,AB, domA, domB, dom(AB), ranA, ranB, ran(AB ), fld(A-B).解：AB=<1,2>,<2,4>,<3,3>,<1,3>,<4,2> AB=<2,4>domA=1,2,3 domB=1,2,4 dom(AB)=1,2,3,4ranA=2,3,4 ranB=2,3,4ran(AB)=4A-B=<1,2>,<3,3>，fld(A-B)=1,2,314.設(shè)R=<0,1><0,2>,<0,3>,<1,2>,<1,3>,<2,3>求RR, R-1, R0,1, R1,2解：RR=<0,2>,<0,3>,<1,3> R-1,=<1,0>,<2,0>,<3,0>,<2,1>,<3,1>,<3,2>R0,1=<0,1>,<0,2>,<0,3>,<1,2>,<1,3>R1,2=ran(R|1,2)=2,316設(shè)A=a,b,c,d，為A上的關(guān)系，其中=求。解: R1R2=<a,d>,<a,c>,<a,d> R2R1=<c,d>R12=R1R1=<a,a>,<a,b>,<a,d>R22=R2R2=<b,b>,<c,c>,<c,d>R23=R2R22=<b,c>,<c,b>,<b,d>36設(shè)A=1，2，3，4，在AA上定義二元關(guān)系R， <u,v>,<x,y>AA ，u,v> R <x,y>u + y = x + v.(1) 證明R 是AA上的等價(jià)關(guān)系.(2)確定由R 引起的對(duì)AA的劃分.（1）證明：<u,v>R<x,y> u+y=x-y<u,v>R<x,y>u-v=x-y<u,v>AAu-v=u-v<u,v>R<u,v>R是自反的任意的<u,v>,<x,y>AA如果<u,v>R<x,y> ，那么u-v=x-yx-y=u-v <x,y>R<u,v> R是對(duì)稱的任意的<u,v>,<x,y>,<a,b>AA若<u,v>R<x,y>,<x,y>R<a,b>則u-v=x-y,x-y=a-bu-v=a-b <u,v>R<a,b>R是傳遞的R是AA上的等價(jià)關(guān)系(2) =<1,1>,<2,2>,<3,3>,<4,4>, <2,1>,<3,2>,<4,3>, <3,1>,<4,2>,<4,1>, <1,2>,<2,3>,<3,4>, <1,3>,<2,4>, <1,4> 41.設(shè)A=1，2，3，4，R為AA上的二元關(guān)系, a，b，c，d AA , a，bRc，da + b = c + d(1) 證明R為等價(jià)關(guān)系.(2) 求R導(dǎo)出的劃分.(1)證明：<a，b AA a+b=a+b<a,b>R<a,b> R是自反的任意的<a,b>,<c,d>AA設(shè)<a,b>R<c,d>，則a+b=c+dc+d=a+b <c,d>R<a,b>R是對(duì)稱的任意的<a,b>,<c,d>,<x,y>AA若<a,b>R<c,d>,<c,d>R<x,y>則a+b=c+d,c+d=x+ya+b=x+y <a,b>R<x,y>R是傳遞的R是 AA上的等價(jià)關(guān)系(2)=<1,1>, <1,2>,<2,1>, <1,3>,<2,2>,<3,1>, <1,4>,<4,1>,<2,3>,<3,2>, <2,4>,<4,2>,<3,3>, <3,4>,<4,3>, <4,4>43. 對(duì)于下列集合與整除關(guān)系畫出哈斯圖:(1) 1,2,3,4,6,8,12,24(2) 1,2,3,4,5,6,7,8,9,10,11,12解: (1) (2)45.下圖是兩個(gè)偏序集<A,R>的哈斯圖.分別寫出集合A和偏序關(guān)系R的集合表達(dá)式. (a) (b)解: (a)A=a,b,c,d,e,f,g R=<a,b>,<a,c>,<a,d>,<a,e>,<a,f>,<a,g>,<b,d>,<b,e>,<c,f>,<c,g> (b) A=a,b,c,d,e,f,gR=<a,b>,<a,c>,<a,d>,<a,e>,<a,f>,<d,f>,<e,f>46.分別畫出下列各偏序集<A,R>的哈斯圖,并找出A的極大元極小元最大元和最小元.(1)A=a,b,c,d,eR=<a,d>,<a,c>,<a,b>,<a,e>,<b,e>,<c,e>,<d,e>IA.(2)A=a,b,c,d,e, R=<c,d>IA.解: (1) (2)項(xiàng)目 (1) (2)極大元: e a,b,d,e 極小元: a a,b,c,e最大元: e 無(wú)最小元: a 無(wú)第八章部分課后習(xí)題參考答案1 設(shè)f :NN,且 f (x)=求f (0), f (0), f (1), f (1), f (0,2,4,6,)，f (4,6,8), f -1(3,5,7).解：f (0)=0, f (0)=0, f (1)=1, f (1)=1, f (0,2,4,6,)=N，f (4,6,8)=2,3,4, f -1 (3,5,7)=6,10,14.4. 判斷下列函數(shù)中哪些是滿射的?哪些是單射的?哪些是雙射的? (1) f:NN, f(x)=x2+2 不是滿射，不是單射 (2) f:NN,f(x)=(x)mod 3,x除以3的余數(shù) 不是滿射，不是單射 (3) f:NN,f(x)= 不是滿射，不是單射 (4) f:N0,1,f(x)= 是滿射，不是單射 (5) f:N-0R,f(x)=lgx 不是滿射，是單射 (6) f:RR,f(x)=x2-2x-15 不是滿射，不是單射5. 設(shè)X=a,b,c,d,Y=1,2,3,f=<a,1>,<b,2>,<c,3>,判斷以下命題的真假: (1)f是從X到Y(jié)的二元關(guān)系,但不是從X到Y(jié)的函數(shù); 對(duì) (2)f是從X到Y(jié)的函數(shù),但不是滿射,也不是單射的; 錯(cuò) (3)f是從X到Y(jié)的滿射,但不是單射; 錯(cuò) (4)f是從X到Y(jié)的雙射. 錯(cuò)第十章部分課后習(xí)題參考答案4判斷下列集合對(duì)所給的二元運(yùn)算是否封閉：（1） 整數(shù)集合Z和普通的減法運(yùn)算。封閉,不滿足交換律和結(jié)合律，無(wú)零元和單位元（2） 非零整數(shù)集合Z*和普通的除法運(yùn)算。不封閉（3） 全體實(shí)矩陣集合Mn（R）和矩陣加法及乘法運(yùn)算，其中n2。封閉 均滿足交換律，結(jié)合律，乘法對(duì)加法滿足分配律；加法單位元是零矩陣，無(wú)零元；乘法單位元是單位矩陣，零元是零矩陣；（4）全體實(shí)可逆矩陣集合關(guān)于矩陣加法及乘法運(yùn)算，其中n2。不封閉（5）正實(shí)數(shù)集合R+和 運(yùn)算，其中 運(yùn)算定義為： a，b R+，a b = ab-a-b 不封閉 因?yàn)?（6） Z+, nZ=nz z Z .nZ關(guān)于普通的加法和乘法運(yùn)算。封閉，均滿足交換律，結(jié)合律，乘法對(duì)加法滿足分配律加法單位元是0，無(wú)零元；乘法無(wú)單位元（），零元是0；單位元是1（7）A = n2. 運(yùn)算定義如下： a，b A，a b = b 封閉 不滿足交換律，滿足結(jié)合律，（8）S = 2x-1xZ+關(guān)于普通的加法和乘法運(yùn)算。封閉 均滿足交換律，結(jié)合律，乘法對(duì)加法滿足分配律（9）S = 0,1,S是關(guān)于普通的加法和乘法運(yùn)算。 加法不封閉，乘法封閉；乘法滿足交換律，結(jié)合律（10）S = x x=2n,nZ+ ,S關(guān)于普通的加法和乘法運(yùn)算。加法不封閉，乘法封閉，乘法滿足交換律，結(jié)合律5對(duì)于上題中封閉的二元運(yùn)算判斷是否適合交換律，結(jié)合律，分配律。 見(jiàn)上題7設(shè) * 為上的二元運(yùn)算，X * Y = min ( x，y ),即x和y之中較小的數(shù).(1) 求4 * 6，7 * 3。 4, 3(2)* 在上是否適合交換律，結(jié)合律，和冪等律？滿足交換律，結(jié)合律，和冪等律(3)求*運(yùn)算的單位元，零元及中所有可逆元素的逆元。單位元無(wú)，零元1, 所有元素?zé)o逆元8 為有理數(shù)集，*為S上的二元運(yùn)算，<a,b>,<x,y > S有 < a，b >*<x，y> = <ax，ay + b>（1）*運(yùn)算在S上是否可交換，可結(jié)合？是否為冪等的？不可交換：<x,y>*<a,b >= <xa，xb +y>< a，b >*<x，y>可結(jié)合：(<a,b >*<x,y>)*<c,d>=<ax，ay + b>*<c,d>=<axc，axd +(ay+b) ><a,b >*(<x,y>*<c,d>)=<a, b>*<xc,xd+y>=<axc，a(xd +y)+b >(<a,b >*<x,y>)*<c,d>=<a,b >*(<x,y>*<c,d>)不是冪等的（2）*運(yùn)算是否有單位元，零元？ 如果有請(qǐng)指出，并求S中所有可逆元素的逆元。 設(shè)<a,b>是單位元，<x,y > S ，<a,b >*<x,y>= <x,y>*<a,b >=<x,y> 則<ax,ay+b>=<xa,xb+y>=<x,y>，解的<a,b>=<1,0>，即為單位。設(shè)<a,b>是零元，<x,y > S ，<a,b >*<x,y>= <x,y>*<a,b >=<a,b> 則<ax,ay+b>=<xa,xb+y>=<a,b>，無(wú)解。即無(wú)零元。<x,y > S，設(shè)<a,b>是它的逆元<a,b >*<x,y>= <x,y>*<a,b >=<1,0><ax,ay+b>=<xa,xb+y>=<1,0>a=1/x,b=-y/x所以當(dāng)x0時(shí)，10令S=a，b，S上有四個(gè)運(yùn)算：*，和分別有表10.8確定。 (a) (b) (c) (d)(1)這4個(gè)運(yùn)算中哪些運(yùn)算滿足交換律，結(jié)合律，冪等律？(a) 交換律，結(jié)合律，冪等律都滿足， 零元為a,沒(méi)有單位元；(b)滿足交換律和結(jié)合律，不滿足冪等律，單位元為a,沒(méi)有零元 (c)滿足交換律,不滿足冪等律,不滿足結(jié)合律 沒(méi)有單位元, 沒(méi)有零元(d) 不滿足交換律，滿足結(jié)合律和冪等律 沒(méi)有單位元, 沒(méi)有零元(2) 求每個(gè)運(yùn)算的單位元，零元以及每一個(gè)可逆元素的逆元。見(jiàn)上16設(shè)V= N，+ ， ，其中+ ，分別代表普通加法與乘法，對(duì)下面給定的每個(gè)集合確定它是否構(gòu)成V的子代數(shù)，為什么？（1）S1=2n nZ 是（2）S2=2n+1 nZ 不是 加法不封閉（3）S3 = -1，0，1 不是，加法不封閉第十一章部分課后習(xí)題參考答案8.設(shè)S=0，1，2，3，為模4乘法，即 "x,yS, xy=(xy)mod 4 問(wèn)S，是否構(gòu)成群？為什么？解：(1) x,yS, xy=(xy)mod 4,是S上的代數(shù)運(yùn)算。(2) x,y,zS,設(shè)xy=4k+r (xy)z =(xy)mod 4)z=rz=(rz)mod 4=(4kz+rz)mod 4=(4k+r)z)mod 4 =(xyz)mod 4同理x(yz) =(xyz)mod 4所以，(xy)z = x(yz)，結(jié)合律成立。(3) xS, (x1)=(1x)=x,，所以1是單位元。(4) 0和2沒(méi)有逆元所以，S，不構(gòu)成群9.設(shè)Z為整數(shù)集合，在Z上定義二元運(yùn)算。如下： " x,yZ,xoy= x+y-2 問(wèn)Z關(guān)于o運(yùn)算能否構(gòu)成群？為什么？解：(1) x,yZ, xoy= x+y-2,o是Z上的代數(shù)運(yùn)算。(2) x,y,zZ, (xoy) oz =(x+y-2)oz=(x+y-2)+z-2=x+y+z-4同理(xoy)oz= xo(yoz)，結(jié)合律成立。(3)設(shè)是單位元，xZ, xo= ox=x,即x+-2= +x-2=x, e=2(4) xZ , 設(shè)x的逆元是y, xoy= yox=, 即x+y-2=y+x-2=2, 所以，所以Z，o構(gòu)成群11.設(shè)G=，證明G關(guān)于矩陣乘法構(gòu)成一個(gè)群解：(1) x,yG, 易知xyG,乘法是Z上的代數(shù)運(yùn)算。(2) 矩陣乘法滿足結(jié)合律(3)設(shè)是單位元，(4)每個(gè)矩陣的逆元都是自己。所以G關(guān)于矩陣乘法構(gòu)成一個(gè)群14.設(shè)G為群，且存在aG,使得 G=akkZ證明：G是交換群。證明:x,yG，設(shè)，則所以，G是交換群17.設(shè)G為群，證明e為G中唯一的冪等元。證明:設(shè)也是冪等元，則，即，由消去律知18.設(shè)G為群，a,b,cG,證明 abc=bca=cab證明：先證設(shè)設(shè)則，即左邊同乘，右邊同乘得反過(guò)來(lái)，設(shè)則由元素階的定義知，abc=bca，同理bca=cab19.證明：偶數(shù)階群G必含2階元。證明：設(shè)群G不含2階元，當(dāng)時(shí)，是一階元，當(dāng)時(shí)，至少是3階元,因?yàn)槿篏時(shí)有限階的，所以是有限階的，設(shè)是k階的,則也是k階的，所以高于3階的元成對(duì)出現(xiàn)的，G不含2階元，G含唯一的1階元,這與群G是偶數(shù)階的矛盾。所以，偶數(shù)階群G必含2階元20.設(shè)G為非Abel群，證明G中存在非單位元a和b,ab,且ab=ba.證明：先證明G含至少含3階元。若G只含1階元,則G=e,G為Abel群矛盾；若G除了1階元e外,其余元均為2階元，則，與G為Abel群矛盾；所以，G含至少含一個(gè)3階元，設(shè)為，則，且。令的證。21.設(shè)G是Mn(R)上的加法群，n2，判斷下述子集是否構(gòu)成子群。（1）全體對(duì)稱矩陣 是子群（2）全體對(duì)角矩陣 是子群（3）全體行列式大于等于0的矩陣. 不是子群（4）全體上（下）三角矩陣。 是子群22.設(shè)G為群，a是G中給定元素，a的正規(guī)化子N（a）表示G中與a可交換的元素構(gòu)成的集合，即 N（a）=xxGxa=ax證明N（a）構(gòu)成G的子群。證明：ea=ae, ,所以由，得，即，所以所以N（a）構(gòu)成G的子群31.設(shè)1是群G1到G2的同態(tài)，2是G2到G3的同態(tài)，證明12是G1到G3的同態(tài)。證明：有已知1是G1到G2的函數(shù)，2是G2到G3的函數(shù)，則12是G1到G3的函數(shù)。 所以:12是G1到G3的同態(tài)。33.證明循環(huán)群一定是阿貝爾群，說(shuō)明阿貝爾群是否一定為循環(huán)群，并證明你的結(jié)論。 證明：設(shè)G是循環(huán)群,令G=<a>,令,那么,G是阿貝爾群 克萊因四元群,是交換群,但不是循環(huán)群,因?yàn)閑是一階元，a,b,c是二階元。36.設(shè)是5元置換，且，(1)計(jì)算；(2)將表成不交的輪換之積。(3)將（2）中的置換表示成對(duì)換之積，并說(shuō)明哪些為奇置換，哪些為偶置換。解：(1) (2) (3) 奇置換， 偶置換 奇置換第十四章部分課后習(xí)題參考答案5、設(shè)無(wú)向圖G有10條邊，3度與4度頂點(diǎn)各2個(gè)，其余頂點(diǎn)的度數(shù)均小于3，問(wèn)G至少有多少個(gè)頂點(diǎn)？在最少頂點(diǎn)的情況下，寫出度數(shù)列、。解：由握手定理圖G的度數(shù)之和為：3度與4度頂點(diǎn)各2個(gè)，這4個(gè)頂點(diǎn)的度數(shù)之和為14度。其余頂點(diǎn)的度數(shù)共有6度。其余頂點(diǎn)的度數(shù)均小于3，欲使G的頂點(diǎn)最少，其余頂點(diǎn)的度數(shù)應(yīng)都取2,所以，G至少有7個(gè)頂點(diǎn), 出度數(shù)列為3,3,4,4,2,2,2,.7、設(shè)有向圖D的度數(shù)列為2，3，2，3，出度列為1，2，1，1，求D的入度列，并求，,.解：D的度數(shù)列為2，3，2，3，出度列為1，2，1，1，D的入度列為1,1,1,2.,8、設(shè)無(wú)向圖中有6條邊，3度與5度頂點(diǎn)各1個(gè)，其余頂點(diǎn)都是2度點(diǎn)，問(wèn)該圖有多少個(gè)頂點(diǎn)？解：由握手定理圖G的度數(shù)之和為：設(shè)2度點(diǎn)個(gè)，則，該圖有4個(gè)頂點(diǎn).14、下面給出的兩個(gè)正整數(shù)數(shù)列中哪個(gè)是可圖化的？對(duì)可圖化的數(shù)列，試給出3種非同構(gòu)的無(wú)向圖，其中至少有兩個(gè)時(shí)簡(jiǎn)單圖。(1) 2,2,3,3,4,4,5 (2) 2,2,2,2,3,3,4,4解：(1) 2+2+3+3+4+4+5=23 是奇數(shù)，不可圖化；(2) 22+2+2+3+3+4+4=16, 是偶數(shù)，可圖化；18、設(shè)有3個(gè)4階4條邊的無(wú)向簡(jiǎn)單圖G1、G2、G3，證明它們至少有兩個(gè)是同構(gòu)的。證明：4階4條邊的無(wú)向簡(jiǎn)單圖的頂點(diǎn)的最大度數(shù)為3，度數(shù)之和為8，因而度數(shù)列為2，2，2，2；3，2，2，1；3，3，1，1。但3，3，1，1對(duì)應(yīng)的圖不是簡(jiǎn)單圖。所以從同構(gòu)的觀點(diǎn)看，4階4條邊的無(wú)向簡(jiǎn)單圖只有兩個(gè)：所以，G1、G2、G3至少有兩個(gè)是同構(gòu)的。20、已知n階無(wú)向簡(jiǎn)單圖G有m條邊，試求G的補(bǔ)圖的邊數(shù)。解：21、無(wú)向圖G如下圖(1)求G的全部點(diǎn)割集與邊割集，指出其中的割點(diǎn)和橋；(2) 求G的點(diǎn)連通度與邊連通度。解：點(diǎn)割集: a,b,(d)邊割集e2,e3,e3,e4,e1,e2,e1,e4e1,e3,e2,e4,e5=123、求G的點(diǎn)連通度、邊連通度與最小度數(shù)。解：、 、28、設(shè)n階無(wú)向簡(jiǎn)單圖為3-正則圖，且邊數(shù)m與n滿足2n-3=m問(wèn)這樣的無(wú)向圖有幾種非同構(gòu)的情況？解： 得n=6,m=9.31、設(shè)圖G和它的部圖的邊數(shù)分別為和，試確定G的階數(shù)。解： 得45、有向圖D如圖 (1)求到長(zhǎng)度為1，2，3，4的通路數(shù)；(2)求到長(zhǎng)度為1，2，3，4的回路數(shù)；(3)求D中長(zhǎng)度為4的通路數(shù)；(4)求D中長(zhǎng)度小于或等于4的回路數(shù)；(5)寫出D的可達(dá)矩陣。解：有向圖D的鄰接矩陣為：， (1)到長(zhǎng)度為1，2，3，4的通路數(shù)為0,2,0,0；(2)到長(zhǎng)度為1，2，3，4的回路數(shù)為0,0,4,0；(3)D中長(zhǎng)度為4的通路數(shù)為32；(4)D中長(zhǎng)度小于或等于4的回路數(shù)10；(4)出D的可達(dá)矩陣第十六章部分課后習(xí)題參考答案1、畫出所有5階和7階非同構(gòu)的無(wú)向樹(shù).2、一棵無(wú)向樹(shù)T有5片樹(shù)葉，3個(gè)2度分支點(diǎn)，其余的分支點(diǎn)都是3度頂點(diǎn)，問(wèn)T有幾個(gè)頂點(diǎn)?解：設(shè)3度分支點(diǎn)個(gè)，則 ，解得T有11個(gè)頂點(diǎn)3、無(wú)向樹(shù)T有8個(gè)樹(shù)葉，2個(gè)3度分支點(diǎn)，其余的分支點(diǎn)都是4度頂點(diǎn)，問(wèn)T有幾個(gè)4度分支點(diǎn)？根據(jù)T的度數(shù)列，請(qǐng)至少畫出4棵非同構(gòu)的無(wú)向樹(shù)。解：設(shè)4度分支點(diǎn)個(gè)，則 ，解得度數(shù)列1111111133444、棵無(wú)向樹(shù)T有 (i=2，3，k )個(gè)i度分支點(diǎn)，其余頂點(diǎn)都是樹(shù)葉，問(wèn)T應(yīng)該有幾片樹(shù)葉?解：設(shè)樹(shù)葉片，則 ，解得評(píng)論：2，3，4題都是用了兩個(gè)結(jié)論,一是握手定理，二是5、n(n3)階無(wú)向樹(shù)T的最大度(T)至少為幾？最多為幾？解：2，n-16、若n(n3)階無(wú)向樹(shù)T的最大度(T) =2，問(wèn)T中最長(zhǎng)的路徑長(zhǎng)度為幾？解：n-17、證明：n(n2) 階無(wú)向樹(shù)不是歐拉圖.證明：無(wú)向樹(shù)沒(méi)有回路，因而不是歐拉圖。8、證明：n(n2) 階無(wú)向樹(shù)不是哈密頓圖.證明：無(wú)向樹(shù)沒(méi)有回路，因而不是哈密頓圖。9、證明：任何無(wú)向樹(shù)T都是二部圖.證明：無(wú)向樹(shù)沒(méi)有回路，因而不存在技術(shù)長(zhǎng)度的圈，是二部圖。10、什么樣的無(wú)向樹(shù)T既是歐拉圖，又是哈密頓圖?解：一階無(wú)向樹(shù)14、設(shè)e為無(wú)向連通圖G中的一條邊， e在G的任何生成樹(shù)中，問(wèn)e應(yīng)有什么性質(zhì)?解：e是橋15、設(shè)e為無(wú)向連通圖G中的一條邊， e不在G的任何生成樹(shù)中， 問(wèn)e應(yīng)有什么性質(zhì)?解：e是環(huán) 23、已知n階m條的無(wú)向圖 G是k(k2)棵樹(shù)組成的森林，證明：m = n-k.；證明：數(shù)學(xué)歸納法。k=1時(shí), m = n-1，結(jié)論成立；設(shè)k=t-1(t-1)時(shí)，結(jié)論成立，當(dāng)k=t時(shí), 無(wú)向圖 G是t棵樹(shù)組成的森林,任取兩棵樹(shù)，每棵樹(shù)任取一個(gè)頂點(diǎn)，這兩個(gè)頂點(diǎn)連線。則所得新圖有t-1棵樹(shù)，所以m = n-（k-1）.所以原圖中m = n-k得證。24、在圖16.6所示2圖中，實(shí)邊所示的生成子圖T是該圖的生成樹(shù). (1)指出T的弦，及每條弦對(duì)應(yīng)的基本回路和對(duì)應(yīng)T的基本回路系統(tǒng).(2) 指出T的所有樹(shù)枝， 及每條樹(shù)枝對(duì)應(yīng)的基本割集和對(duì)應(yīng)T的基本割集系統(tǒng). (a) (b) 圖16.16 解：(a)T的弦：c,d,g,hT的基本回路系統(tǒng): S=a,c,b,a,b,f,d,e,a,b,h,e,a,b,f,gT的所有樹(shù)枝: e,a,b,fT的基本割集系統(tǒng): S=e,g,h,a,c,d,g,h,b,c,d,g,h,f,d,g(b)有關(guān)問(wèn)題仿照給出25、求圖16.17所示帶權(quán)圖中的最小生成樹(shù). (a) (b)圖16.17解：注：答案不唯一。37、畫一棵權(quán)為3，4，5，6，7，8，9的最優(yōu)2叉樹(shù)，并計(jì)算出它的權(quán).38.下面給出的各符號(hào)串集合哪些是前綴碼? A1=0，10，110，1111 是前綴碼 A2=1，01，001，000 是前綴碼 A3=1，11，101，001，0011 不是前綴碼 A4=b，c，aa，ac，aba，abb，abc 是前綴碼 A5= b，c，a，aa，ac，abc，abb，aba 不是前綴碼41.設(shè)7個(gè)字母在通信中出現(xiàn)的頻率如下: a: 35% b: 20% c: 15% d: 10% e: 10% f: 5% g: 5%用Huffman算法求傳輸它們的前綴碼.要求畫出最優(yōu)樹(shù)，指出每個(gè)字母對(duì)應(yīng)的編碼.并指出傳輸10n(n2)個(gè)按上述頻率出現(xiàn)的字母，需要多少個(gè)二進(jìn)制數(shù)字.解：a:01 b:10 c:000 d:110 e:001 f:1111 g:1110W(T)=5*4+5*4+10*3+10*3+15*3+20*2+35*2=255傳輸10n(n2)個(gè)按上述頻率出現(xiàn)的字母，需要255*10n-2個(gè)二進(jìn)制數(shù)字.30