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

______________________________________________________________________________________________________________ 離散數(shù)學(xué)答案 屈婉玲版 第二版 高等教育出版社課后答案 第一章部分課后習(xí)題參考答案 16 設(shè)p、q的真值為0；r、s的真值為1，求下列各命題公式的真值。 （1）p∨(q∧r) 0∨(0∧1) 0 （2）（p?r）∧(﹁q∨s) （0?1）∧(1∨1) 0∧10. （3）（p∧q∧r）?(p∧q∧﹁r) （1∧1∧1） ? (0∧0∧0)0 (4)（r∧s）→(p∧q) （0∧1）→(1∧0) 0→01 17．判斷下面一段論述是否為真：“是無(wú)理數(shù)。并且，如果3是無(wú)理數(shù)，則也是無(wú)理數(shù)。另外6能被2整除，6才能被4整除。” 答：p: 是無(wú)理數(shù) 1 q: 3是無(wú)理數(shù) 0 r: 是無(wú)理數(shù) 1 s:　6能被2整除 1 t: 6能被4整除 0 命題符號(hào)化為： p∧(q→r)∧(t→s)的真值為1，所以這一段的論述為真。 19．用真值表判斷下列公式的類型： （4）(p→q) →(q→p) （5）(p∧r) (p∧q) （6）((p→q) ∧(q→r)) →(p→r) 答： （4） p q p→q q p q→p (p→q)→(q→p) 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) (p∧q→q) (2)(p→(p∨q))∨(p→r) (3)(p∨q)→(p∧r) 答：(2)（p→(p∨q)）∨(p→r)(p∨(p∨q))∨(p∨r)p∨p∨q∨r1 所以公式類型為永真式 (3) P q r p∨q p∧r （p∨q）→(p∧r) 0 0 0 0 0 1 0 0 1 0 0 1 0 1 0 1 0 0 0 1 1 1 0 0 1 0 0 1 0 0 1 0 1 1 1 1 1 1 0 1 0 0 1 1 1 1 1 1 所以公式類型為可滿足式 4.用等值演算法證明下面等值式： (2)(p→q)∧(p→r)(p→(q∧r)) (4)(p∧q)∨(p∧q)(p∨q) ∧(p∧q) 證明（2）(p→q)∧(p→r) (p∨q)∧(p∨r) p∨(q∧r)) p→(q∧r) （4）(p∧q)∨(p∧q)(p∨(p∧q)) ∧(q∨(p∧q) (p∨p)∧(p∨q)∧(q∨p) ∧(q∨q) 1∧(p∨q)∧(p∧q)∧1 (p∨q)∧(p∧q) 5.求下列公式的主析取范式與主合取范式，并求成真賦值 (1)(p→q)→(q∨p) (2)(p→q)∧q∧r (3)(p∨(q∧r))→(p∨q∨r) 解： （1）主析取范式 (p→q)→(qp) (pq)(qp) (pq)(qp) (pq)(qp)(qp)(pq)(pq) (pq)(pq)(pq) ∑(0,2,3) 主合取范式： (p→q)→(qp) (pq)(qp) (pq)(qp) (p(qp))(q(qp)) 1(pq) (pq) M1 ∏(1) (2) 主合取范式為： (p→q)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é)論的否定引入 ②p﹁q 前提引入 ③﹁q ①②假言推理 ④￢rq 前提引入 ⑤￢r ④化簡(jiǎn)律 ⑥r(nóng)￢s 前提引入 ⑦r ⑥化簡(jiǎn)律 ⑧r﹁r ⑤⑦ 合取 由于最后一步r﹁r 是矛盾式,所以推理正確. 第四章部分課后習(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) 沒有不能表示成分?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) ?x?y(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,y→Gx,y→Fx,y. (3) ?x?yF(x,y)→?x?yF(x,y). 解:(1)因?yàn)? 為永真式； 所以 Fx,y→Gx,y→Fx,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(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ì)睡覺.成真解釋 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ì)睡覺,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) ①EI ③x(F(x)→(G(a)∧R(x))) 前提引入 ④F(c)→(G(a)∧R(c)) ③UI ⑤G(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,b｝｛a,b,c,｛a,b,c｝｝ 真 （6）｛a,b｝｛a,b,c,｛a,b｝｝ 真 （7）｛a,b｝｛a,b,｛｛a,b｝｝｝ 真 （8）｛a,b｝｛a,b,｛｛a,b｝｝｝ 假 6．設(shè)a,b,c各不相同，判斷下述等式中哪個(gè)等式為真: （1）｛｛a,b｝，c,｝ =｛｛a,b｝,c｝ 假 （2）｛a ,b,a｝=｛a,b｝ 真 （3）｛｛a｝，｝=｛｛a,b｝｝ 假 （4）｛，｛｝，a,b｝=｛｛,｛｝｝,a,b｝ 假 8．求下列集合的冪集： （1）｛a,b,c｝ P(A)={ ,{a},,{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=A 18．某班有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è)集合A＝{{1，2}，{2，3}，{1，3},{}},計(jì)算下列表達(dá)式： （1）A （2）A （3）A （4）A 解: （1）A={1，2}{2，3}{1，3}{}={1，2，3,} （2）A={1，2}{2，3}{1，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=(A～B) ～C= A( ～B～C)= A～(BC) =A- BC (2) (A-C)-(B-C)=(A～C) ～(B ～C)= (A～C) (～BC) =(A～C～B) (A～CC)= (A～C～B) = 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(A∨B)={1,2,3,4} ranA={2,3,4} ranB={2,3,4} ran(AB)={4} A-B={<1,2>,<3,3>}，fld(A-B)={1,2,3} 14.設(shè)R={<0,1><0,2>,<0,3>,<1,2>,<1,3>,<2,3>} 求RR, R-1, R{0,1,}, R[{1,2}] 解：RR={<0,2>,<0,3>,<1,3>} R-1,={<1,0>,<2,0>,<3,0>,<2,1>,<3,1>,<3,2>} R{0,1}={<0,1>,<0,2>,<0,3>,<1,2>,<1,3>} R[{1,2}]=ran(R|{1,2})={2,3} 16．設(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>AA ∵u-v=u-v ∴<u,v>R<u,v> ∴R是自反的 任意的<u,v>,<x,y>∈A×A 如果<u,v>R<x,y> ，那么u-v=x-y ∴x-y=u-v ∴<x,y>R<u,v> ∴R是對(duì)稱的 任意的<u,v>,<x,y>,<a,b>∈A×A 若<u,v>R<x,y>,<x,y>R<a,b> 則u-v=x-y,x-y=a-b ∴u-v=a-b ∴<u,v>R<a,b> ∴R是傳遞的 ∴R是A×A上的等價(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，b〉R〈c，d〉a + 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>∈A×A 設(shè)<a,b>R<c,d>，則a+b=c+d ∴c+d=a+b ∴<c,d>R<a,b> ∴R是對(duì)稱的 任意的<a,b>,<c,d>,<x,y>∈A×A 若<a,b>R<c,d>,<c,d>R<x,y> 則a+b=c+d,c+d=x+y ∴a+b=x+y ∴<a,b>R<x,y> ∴R是傳遞的 ∴R是 A×A上的等價(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,g} R={<a,b>,<a,c>,<a,d>,<a,e>,<a,f>,<d,f>,<e,f>} 46.分別畫出下列各偏序集<A,R>的哈斯圖,并找出A的極大元`極小元`最大元和最小元. (1)A={a,b,c,d,e} R={<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:N{0,1},f(x)= 是滿射，不是單射 (5) f:N-{0}R,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)算，其中n≥2。 封閉 均滿足交換律，結(jié)合律，乘法對(duì)加法滿足分配律； 加法單位元是零矩陣，無(wú)零元； 乘法單位元是單位矩陣，零元是零矩陣； （4）全體實(shí)可逆矩陣集合關(guān)于矩陣加法及乘法運(yùn)算，其中n≥2。不封閉 （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 = { n≥2. ° 運(yùn)算定義如下： ? a，b ∈ A，a ° b = b 封閉 不滿足交換律，滿足結(jié)合律， （8）S = 2x-1x∈Z+關(guān)于普通的加法和乘法運(yùn)算。 封閉 均滿足交換律，結(jié)合律，乘法對(duì)加法滿足分配律 （9）S = {0,1},S是關(guān)于普通的加法和乘法運(yùn)算。 加法不封閉，乘法封閉；乘法滿足交換律，結(jié)合律 （10）S = x x=2n,n∈Z+ ,S關(guān)于普通的加法和乘法運(yùn)算。 加法不封閉，乘法封閉，乘法滿足交換律，結(jié)合律 5．對(duì)于上題中封閉的二元運(yùn)算判斷是否適合交換律，結(jié)合律，分配律。 見上題 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,沒有單位元； (b)滿足交換律和結(jié)合律，不滿足冪等律，單位元為a,沒有零元 (c)滿足交換律,不滿足冪等律,不滿足結(jié)合律 沒有單位元, 沒有零元 (d) 不滿足交換律，滿足結(jié)合律和冪等律 沒有單位元, 沒有零元 (2) 求每個(gè)運(yùn)算的單位元，零元以及每一個(gè)可逆元素的逆元。 見上 16．設(shè)V=〈 N，+ ，? 〉，其中+ ，?分別代表普通加法與乘法，對(duì)下面給定的每個(gè)集合確定它是否構(gòu)成V的子代數(shù)，為什么？ （1）S1=2n n∈Z 是 （2）S2=2n+1 n∈Z 不是 加法不封閉 （3）S3 = {-1，0，1} 不是，加法不封閉 第十一章部分課后習(xí)題參考答案 8.設(shè)S={0，1，2，3}，為模4乘法，即 "x,y∈S, xy=(xy)mod 4 問(wèn)〈S，〉是否構(gòu)成群？為什么？ 解：(1) x,y∈S, xy=(xy)mod 4,是S上的代數(shù)運(yùn)算。 (2) x,y,z∈S,設(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) x∈S, (x1)=(1x)=x,，所以1是單位元。 (4) 0和2沒有逆元 所以，〈S，〉不構(gòu)成群 9.設(shè)Z為整數(shù)集合，在Z上定義二元運(yùn)算。如下： " x,y∈Z,xoy= x+y-2 問(wèn)Z關(guān)于o運(yùn)算能否構(gòu)成群？為什么？ 解：(1) x,y∈Z, xoy= x+y-2,o是Z上的代數(shù)運(yùn)算。 (2) x,y,z∈Z, (xoy) oz =(x+y-2)oz=(x+y-2)+z-2=x+y+z-4 同理(xoy)oz= xo(yoz)，結(jié)合律成立。 (3)設(shè)是單位元，x∈Z, xo= ox=x,即x+-2= +x-2=x, e=2 (4) x∈Z , 設(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,y∈G, 易知xy∈G,乘法是Z上的代數(shù)運(yùn)算。 (2) 矩陣乘法滿足結(jié)合律 (3)設(shè)是單位元， (4)每個(gè)矩陣的逆元都是自己。 所以G關(guān)于矩陣乘法構(gòu)成一個(gè)群． 14.設(shè)G為群，且存在a∈G,使得 G={ak∣k∈Z} 證明：G是交換群。 證明:x,y∈G，設(shè)，則 　　 所以，G是交換群 17.設(shè)G為群，證明e為G中唯一的冪等元。 證明:設(shè)也是冪等元，則，即，由消去律知 18.設(shè)G為群，a,b,c∈G,證明 ∣abc∣=∣bca∣=∣cab∣ 證明：先證設(shè) 設(shè)則， 即　　　 左邊同乘，右邊同乘得 　　反過(guò)來(lái)，設(shè)則 由元素階的定義知，∣abc∣=∣bca∣，同理∣bca∣=∣cab∣ 19.證明：偶數(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,a≠b,且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)上的加法群，n≥2，判斷下述子集是否構(gòu)成子群。 （1）全體對(duì)稱矩陣 是子群 （2）全體對(duì)角矩陣 是子群 （3）全體行列式大于等于0的矩陣. 不是子群 （4）全體上（下）三角矩陣。 是子群 22.設(shè)G為群，a是G中給定元素，a的正規(guī)化子N（a）表示G中與a可交換的元素構(gòu)成的集合，即 N（a）={x∣x∈G∧xa=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ù)，則1·2是G1到G3的函數(shù)。 所以:1·2是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) 2＋2+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,e4}{e1,e3},{e2,e4},{e5} ==1 23、求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ú)向樹. 2、一棵無(wú)向樹T有5片樹葉，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ú)向樹T有8個(gè)樹葉，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è)4度分支點(diǎn)個(gè)，則 ，解得 度數(shù)列111111113344 4、棵無(wú)向樹T有 (i=2，3，…，k )個(gè)i度分支點(diǎn)，其余頂點(diǎn)都是樹葉，問(wèn)T應(yīng)該有幾片樹葉? 解：設(shè)樹葉片，則 ，解得 評(píng)論：2，3，4題都是用了兩個(gè)結(jié)論,一是握手定理，二是 5、n(n≥3)階無(wú)向樹T的最大度?(T)至少為幾？最多為幾？ 解：2，n-1 6、若n(n≥3)階無(wú)向樹T的最大度?(T) =2，問(wèn)T中最長(zhǎng)的路徑長(zhǎng)度為幾？ 解：n-1 7、證明：n(n≥2) 階無(wú)向樹不是歐拉圖. 證明：無(wú)向樹沒有回路，因而不是歐拉圖。 8、證明：n(n≥2) 階無(wú)向樹不是哈密頓圖. 證明：無(wú)向樹沒有回路，因而不是哈密頓圖。 9、證明：任何無(wú)向樹T都是二部圖. 證明：無(wú)向樹沒有回路，因而不存在技術(shù)長(zhǎng)度的圈，是二部圖。 10、什么樣的無(wú)向樹T既是歐拉圖，又是哈密頓圖? 解：一階無(wú)向樹 14、設(shè)e為無(wú)向連通圖G中的一條邊， e在G的任何生成樹中，問(wèn)e應(yīng)有什么性質(zhì)? 解：e是橋 15、設(shè)e為無(wú)向連通圖G中的一條邊， e不在G的任何生成樹中， 問(wèn)e應(yīng)有什么性質(zhì)? 解：e是環(huán) 23、已知n階m條的無(wú)向圖 G是k(k≥2)棵樹組成的森林，證明：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棵樹組成的森林,任取兩棵樹，每棵樹任取一個(gè)頂點(diǎn)，這兩個(gè)頂點(diǎn)連線。則所得新圖有t-1棵樹，所以m = n-（k-1）. 所以原圖中m = n-k 得證。 24、在圖16.6所示2圖中，實(shí)邊所示的生成子圖T是該圖的生成樹. (1)指出T的弦，及每條弦對(duì)應(yīng)的基本回路和對(duì)應(yīng)T的基本回路系統(tǒng). (2) 指出T的所有樹枝， 及每條樹枝對(duì)應(yīng)的基本割集和對(duì)應(yīng)T的基本割集系統(tǒng). (a) (b) 圖16.16 解：(a)T的弦：c,d,g,h T的基本回路系統(tǒng): S={{a,c,b},{a,b,f,d},{e,a,b,h},{e,a,b,f,g}} T的所有樹枝: e,a,b,f T的基本割集系統(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)圖中的最小生成樹. (a) (b) 圖16.17 解： 注：答案不唯一。 37、畫一棵權(quán)為3，4，5，6，7，8，9的最優(yōu)2叉樹，并計(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)樹，指出每個(gè)字母對(duì)應(yīng)的編碼.并指出傳輸10n(n≥2)個(gè)按上述頻率出現(xiàn)的字母，需要多少個(gè)二進(jìn)制數(shù)字. 解： a:01 b:10 c:000 d:110 e:001 f:1111 g:1110 W(T)=5*4+5*4+10*3+10*3+15*3+20*2+35*2=255 傳輸10n(n≥2)個(gè)按上述頻率出現(xiàn)的字母，需要255*10n-2個(gè)二進(jìn)制數(shù)字.  THANKS !!! 致力為企業(yè)和個(gè)人提供合同協(xié)議，策劃案計(jì)劃書，學(xué)習(xí)課件等等 打造全網(wǎng)一站式需求 歡迎您的下載，資料僅供參考 -可編輯修改-