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

精心整理 學習幫手 離散數(shù)學答案屈婉玲版 第二版 高等教育出版社課后答案 第一章部分課后習題參考答案 16設p、q的真值為0; r、s的真值為1 ,求下列各命題公式的真值。 (1) pV(qAr) 0 V (0 A1) 0 (2) (p? r) A (「qVs) (0?1)A(1V1) 0A 1 0. (3)( pA qAr) ? (p AqA「r) (1A1A1) ?(0A0A 0) 0 (4) ( rAs) 一(pA q) (0A1) 一(1A0) 0—0 1 17.判斷下面一段論述是否為真：”是無理數(shù)。并且，如果3是無理數(shù)，則4f2也是無 理數(shù)。另外6能被2整除，6才能被4整除。” 答：p: 是無理數(shù)1 q: 3 是無理數(shù)0 r: 72是無理數(shù)1 s: 6能被2整除1 t: 6 能被4整除0 命題符號化為：p A(q-r) A(t -s)的真值為1,所以這一段的論述為真 19.用真值表判斷下列公式的類型: (4) (p—q) 一( q - p) (5) (p Ar) ( pA q) (6) ((p-q) A(q - r)) —(p—r) p 1 1 1 1 q - p (p 一 q)一( q - p) 答： (4) p q p - q q 0 0 1 1 1 1 0 1 1 0 1 1 1 0 0 1 0 0 1 1 1 0 0 1 所以公式類型為永真式 (5)公式類型為可滿足式(方法如上例) (6)公式類型為永真式(方法如上例) 第二章部分課后習題參考答案 3.用等值演算法判斷下列公式的類型，對不是重言式的可滿足式，再用真值表法求出 成真賦值. (1) (pAq-q) ⑵(p 一 (p V q)) V(p — r) (3)(p Vq)-(pAr) pV pVqV r 答：(2) (p 一 (pVq)) V(p - r) ( pV (p V q)) V ( pV r) ⑶P q r p Vq p A 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.用等值演算法證明下面等值式： (pVq) 一(p A r) ⑵(p 一 q) A (p 一 r) (p 一 (q A r)) ⑷(p A q) V ( pA q) (p V q) A (p A q) 證明(2) (p — q) A (p—r) (pVq)A( pVr) pV(q A r)) p 一 (q 八 r) (4) (pA q) V( pAq) (p V ( pAq)) A( qV( pA q) (p V p)A(pVq)A( qV p) A ( qVq) 1 A (p V q) A (p A q) A 1 (p V q) A (p A q) 5.求下列公式的主析取范式與主合取范式，并求成真賦值 (1)( p-q)—( qvp) (2) (p — q)AqAr ⑶(p V (q A r)) 一(p Vq V r) 解： (1)主析取范式 (p 一 q)—( q p) (p q) ( q p) (p q) ( q p) (p q) ( q p) ( q p) (p q) (p q) ( p q) (p q) (p q) mo m2 m3 E (0,2,3) 主合取范式： (p-q)―( q p) (p q) ( q p) (p q) ( q p) (p ( q p)) ( q ( q p)) 1 (p q) (p q) Mi n⑴ (2) 主合取范式為： (p-q) q r ( p q) q r (p q) q r 0 所以該式為矛盾式. 主合取范式為n (0,1,2,3,4,5,6,7) 矛盾式的主析取范式為0 (3)主合取范式為： (p (q r)) 一 (p q r) (p (q r)) 一 (p q r) (p ( q r)) (p q r) (p (p q r)) (( q r)) (p q r)) 1 1 所以該式為永真式. 永真式的主合取范式為1 主析取范式為三(0,1,2,3,4,5,6,7) 第三章部分課后習題參考答案 14.在自然推理系統(tǒng)P中構(gòu)造下面推理的證明： (2)前提：p q, (q r),r 結(jié)論： p (4)前提：q p,q s,s t,t r 結(jié)論：p q 證明：(2) ①(q r) 前提引入 ②q r ①置換 ③q r ②蘊含等值式 ④r 前提引入 ⑤q ③④拒取式 ⑥p q 前提引入 ⑦「p(3) ⑤⑥拒取式 證明(4): ①t r 前提引入 ②t ①化簡律 ③q s 前提引入 ④s t 前提引入 ⑤q t ③④等價三段論 ⑥(q t) (t q) ⑤置換 ⑦(q t) ⑥化簡 ⑧q ②⑥假言推理 ⑨q p 前提引入 ⑩p ⑧⑨假言推理 (11)p q ⑧⑩合取 15在自然推理系統(tǒng)P中用附加前提法證明下面各推理: ⑴前提：p (q r),s p,q 結(jié)論：s r 證明 ①s 附加前提引入 ②s p 前提引入 ③p ①②假言推理 ④p (q r)前提引入 ⑤q r ③④假言推理 ⑥q 前提引入 ⑦r ⑤⑥假言推理 16在自然推理系統(tǒng)P中用歸謬法證明下面各推理： (1)前提：p q, r q,r s 結(jié)論： p 證明： ①p 結(jié)論的否定引入 ②p」q 前提引入 ③「q ①②假言推理 ④「r q 前提引入 ⑤「r ④化簡律 ⑥r(nóng) 「s 前提引入 ⑦r ⑥化簡律 ⑧r 「r ⑤⑦合取 由于最后一步r 「r是矛盾式，所以推理正確. 第四章部分課后習題參考答案 3.在一階邏輯中將下面將下面命題符號化，并分別討論個體域限制為(a),(b)條件時命 題的真值: (1)對于任意x,均有它-2=(x+a)(x T). (2)存在x,使彳# x+5=9. 其中(a)個體域為自然數(shù)集合. (b) 個體域為實數(shù)集合. 解： F(x): ——2=(x+ 一 W). G(x): x+5=9. (1)在兩個個體域中都解釋為 xF(x),在(a)中為假命題，在(b)中為真命題。 (2)在兩個個體域中都解釋為 xG(x),在(a) (b)中均為真命題。 4 .在一階邏輯中將下列命題符號化： (1)沒有不能表示成分數(shù)的有理數(shù). (2)在北京賣菜的人不全是外地人. 解： (1)F(x): x 能表示成分數(shù) H(x): x 是有理數(shù) 命題符號化為： x( F(x) H(x)) (2)F(x): x 是北京賣菜的人 H(x): x 是外地人 命題符號化為： x(F(x) H(x)) 5 .在一階邏輯將下列命題符號化： (1) 火車都比輪船快. (3) 不存在比所有火車都快的汽車. 解： (1)F(x): x 是火車；G(x): x 是輪船；H(x,y): x 比 y 快 命題符號化為： x y((F(x) G(y)) H(x, y)) (2) (1)F(x): x 是火車；G(x): x 是汽車；H(x,y): x 比 y 快 命題符號化為： y(G(y) x(F(x) H(x,y))) 9.給定解釋I如下： (a) 個體域D為實數(shù)集合R. (b) D 中特定元素a-=0. (c) 特定函數(shù)雙y)=x —y,x,y D . (d) 特定謂詞 G(x,y):x=y, G(x,y):x<y,x,y D. 說明下列公式在I下的含義，并指出各公式的真值: (1) x y(G(x,y) F(x, y)) (2) x y(F(f(x,y),a) G(x, y)) 答：(1)對于任意兩個實數(shù)x,y,如果x<y,那么x y.真值1. (2)對于任意兩個實數(shù)x,y,如果x-y=0,那么x<y.真值0. 10.給定解釋I如下： (a)個體域D=N(N為自然數(shù)集合). (b) D中特定元素三=2. (c) D 上函數(shù)=x+y,宮(x,y)=xy. (d) D 上謂詞 F(x,y):x=y. 說明下列各式在I下的含義，并討論其真值. (1) -xF(g(x,a),x) (2) wy(F(f(x,a),y) 一F(f(y,a),x) 答：(1)對于任意自然數(shù)x,都有2x=x,真值0. (2)對于任意兩個自然數(shù)x,y,使得如果x+2=y,那么y+2=x.真值0. 11.判斷下列各式的類型： (1) 7 .-.-二 (3):二二二二 二、：yF(x,y). 解：(1)因為p (q p) p ( q p) 1 為永真式； 所以Fk德一伯值巾- F值為永真式； (3)取解釋I個體域為全體實數(shù) F(x,y) : x+y=5 所以，前件為任意實數(shù)x存在實數(shù)y使x+y=5,前件真； 后件為存在實數(shù)x對任意實數(shù)y都有x+y=5,后件假，］ 此時為假命題 再取解釋I個體域為自然數(shù)N, F(x,y) : :x+y=5 所以，前件為任意自然數(shù)x存在自然數(shù)y使x+y=5,前件假。此時為假命題。 此公式為非永真式的可滿足式。 13.給定下列各公式一個成真的解釋，一個成假的解釋。 (1) 一(F(x):內(nèi)略微 (2)三 x(F(x) G(x) H(x)) 解：(1)個體域：本班同學 F(x) : x會吃飯，G(x) : x會睡覺.成真解釋 F(x)： x是泰安人,G(x) : x是濟南人.(2)成假解釋 (2)個體域：泰山學院的學生 F(x) : x出生在山東,G(x):x出生在北京，H(x):x出生在江蘇，成假解釋. F(x) : x會吃飯,G(x) : x會睡覺,H(x) : x會呼吸.成真解釋. 第五章部分課后習題參考答案 5.給定解釋I如下： (a)個體域 D={3,4}; (b) f(x)為f(3) 4,f(4) 3 (c) F(x,y)為F(3,3) F(4,4) 0, F(3,4) F(4,3) 1. 試求下列公式在I下的真值. (1) x yF(x, y) (3) x y(F(x,y) F(f (x), f(y))) 解:(1) x yF(x,y) x(F(x,3) F(x,4)) (F(3,3) F(3,4)) (F(4,3) F(4,4)) (0 1) (1 0) 1 (2) x y(F(x,y) F(f(x), f(y))) x((F(x,3) F(f(x), f (3))) (F(x,4) F(f(x), f (4)))) x((F(x,3) F(f (x),4)) (F(x,4) F(f (x),3))) ((F(3,3) F(f(3),4)) (F(3,4) F(f(3),3))) ((F(4,3) F(f (4),4)) (F(4,4) F(f(4),3))) ((0 F(4,4)) (F(3,4) (0 0) (1 1) (1 12.求下列各式的前束范式。 (1) xF(x) yG(x, y) (5) X1F (X1,X2) (H(x1) 解:⑴ xF(x) yG(x,y) (5) x1 F (x1, x2) (H(x1) F(4,3))) ((1 F(3,4)) (0 F(3,3))) 1) (0 0) 1 x2G(x1,x2))(本題課本上有錯誤) xF(x) yG(t,y) x y(F(x) G(t, y)) x2G(x1, x2)) x1 F (x1, x2) (H (x3) X2 G(x3,x2)) x1 F (x1, x4) x2(H (x3) G(x3,x2)) x1 x2(F(x［，x4) (H (x3) G(x3,x2))) 15.在自然數(shù)推理系統(tǒng)F中，構(gòu)造下面推理的證明： (1)前提：xF(x) y((F(y) G(y)) R(y)), xF(x) 結(jié)論：xR(x) (2)前提： x(F(x) 一(G(a) A R(x))),三 xF(x) 結(jié)論：三x(F(x) A R(x)) 證明(1) ①xF (x) 前提引入 ②F⑹ ①EI ③ xF(x) y((F(y) G(y)) R(y)) 前提引入 ④y((F(y) G(y)) R(y))①③假言推理 ⑤(F⑹ V G(c)) 一R⑹) ④UI ⑥F(c) VG(c) ②附加 ⑦R(c) ⑤⑥假言推理 ⑧ xR(x) ⑦ EG  ①xF(x) 前提引入 ②F(c) ①EI ③ x(F(x) 一(G(a) A R(x))) 前提引入 ④F(c) 一(G(a) A R(c)) ③UI ⑤G(a) A R(c) ②④假言推理 ⑥R(c) ⑤化簡 ⑦F(c)AR(c) ②⑥合取引入 ⑧ x(F(x) A R(x)) ⑦ EG 第六章部分課后習題參考答案 5.確定下列命題是否為真： (1) 真 (2) 假 (3) { } 真 (4) { } 真 (5) {a,b} {a,b,c, {a,b,c }} 真 (6) {a,b} {a,b,c, {a,b}} 真 ⑺{a,b} {a,b, {{a,b}}} 真 (8) {a,b} {a,b, {{a,b}}} 假 6.設a,b,c各不相同，判斷下述等式中哪個等式為真 (1) {{a,b}, c, } = {{a,b} ,c} 假 (2) {a ,b,a } = {a,b } 真 (3) {{a}, } = {{a,b}} 假 (4) { , { }, a,b} = {{ , { }} ,a,b }假 8.求下列集合的募集： ,{a},,{c},{a,b},{a,c},{b,c},{a,b,c}} ,{1}, {{2,3}}, {1 , {2, 3}} } ,{ } } ,{1}, {{2,3}}, {1 , {2, 3}} } (1) {a,b,c } P(A)={ (2) {1, {2, 3}} P(A)={ (3) { } P(A)={ (4) { , { }} P(A)={ 14.化簡下列集合表達式: (1) (A B) B ) - (A B) (2) ((A B C) - (B C)) A 解： (1) (A B) B ) - (A B) = (A B) B ) ?(A B) =(A B) ?(A B) ) B= B= (2) ((A B C) - (B C)) A= ((A B C) ?(B C)) A =(A ?(B O) ((B C ) ?(B C)) A =(A ?(B O) A= (A ?(B O) A=A 18 .某班有25個學生，其中14人會打籃球，12人會打排球，6人會打籃球和排球，5 人會打籃球和網(wǎng)球，還有2人會打這三種球。已知6個會打網(wǎng)球的人都會打籃球或排球。 求不會打球的人數(shù)。 網(wǎng)球 解：阿A={會打籃或勺人}, B={會打排球的人}, C={會打 的人} |A|=14, |B|=12, |A B|=6,|A C|=5,| A B C|=2, |C|=6,C A B 如圖所示 25-(5+4+2+3)-5-1=25-14-5-1=5 不會打球的人共5人 21.設集合人={{1 , 2}, {2 , 3}, {1 , 3},{ }},計算下列表達式: (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=1 2 3 = (4) A= 27、設A,B,C是任意集合，證明 (1)(A-B)-C=A- B C ⑵(A-B)-C=(A-C)-(B-C) 證明 (1) (A-B)-C=(A ?B) -C= A (?B ?C)= A ?(B C) =A- B C ⑵(A-C)-(B-C)=(A ?C) ?(B ?C)= (A ?C) (?B C) =(A ?C ?B) (A ?C C)= (A ?C ?B) =A ?(B C) =A- B C 由(1)得證。 第七章部分課后習題參考答案 7.列出集合A={2,3,4}上的恒等關系Ia,全域關系E,小于或等于關系La,整除關系D. 解：Ia ={<2, 2>,<3,3>,<4,4>} E a={<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>} CA={<2,4>} 13.設 A={<1,2>,<2,4>,<3,3>} B={<1,3>,<2,4>,<4,2>} 求 A B,A B, domA, domB, dom(A B), ranA, ranB, ran(A B ), fld(A-B). 解：A B={<1,2>,<2,4>,<3,3>,<1,3>,<4,2>} A B={<2,4>} domA={1,2,3} domB={1,2,4} dom(A V B)={1,2,3,4} ranA={2,3,4} ranB={2,3,4} ran(A B)={4} A-B={<1,2>,<3,3>} , fld(A-B尸{1,2,3} 14.設 R={<0,1><0,2>,<0,3>,<1,2>,<1,3>,<2,3>} 求 R R, R-1, R {0,1,}, R[{1,2}] 解：R R={<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.設A={a,b,c,d} , R R2為A上的關系，其中 Ri= ：a,aj/a,b；；b,d； R2 ：a,dj, b,c , b,d ：,；c,b 2 3 求 Ri o R2, R2 oRi,Ri , R2 o 解：Ri R={<a,d>,<a,c>,<a,d>} R 2 R={<c,d>} R2=R R={<a,a>,<a,b>,<a,d>} 2 R =R R={<b,b>,<c,c>,<c,d>} R3=R R2={<b,c>,<c,b>,<b,d>} 36.設人={1, 2, 3, 4},在A A上定義二元關系 R, <u,v>,<x,y> A A , <u,v> R <x,y> u + y = x + v. (1)證明R是A A上的等價關系. (2)確定由R引起的對A A的劃分. (1) 證明：<u,v>R<x,y> u+y=x-y <u,v>R<x,y> u-v=x-y <u,v> A A .? u-v=u-v <u,v>R<u,v> ??.R是自反的 任意的 <u,v>,<x,y> A AX A 如果 <u,v>R<x,y> ,那么 u-v=x-y x-y=u-v <x,y>R<u,v> ??.R是對稱的 任意的 <u,v>,<x,y>,<a,b> C AX A 若 <u,v>R<x,y>,<x,y>R<a,b> 貝U u-v=x-y,x-y=a-b ? ? u-v=a-b .. <u,v>R<a,b> R是傳遞的 ??.R是AX A上的等價關系 ⑵ n={{<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.設 A={1, 2, 3, 4}, R為 A A上的二元關系， 〈a, b〉，<c, d> A A , <a, b> R <c, d> a + b = c + d (1)證明R為等價關系. (2)求R導出的劃分. ⑴證明： <a, b> A A a+b=a+b . . <a,b>R<a,b> ? ?.R是自反的 任意的 <a,b>,<c,d> C Ax A 設<a,b>R<c,d> , a+b=c+d ? ?c+d=a+b .. <c,d>R<a,b> R是對稱的 任意的 <a,b>,<c,d>,<x,y> A AX 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是AX A上的等價關系 ⑵ n={{<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>}} (1) {1,2,3,4,6,8,12,24} (2) {1,2,3,4,5,6,7,8,9,10,11,12} 解： 24 8介2 4 6 2</3 1 (1) (2) 45.下圖是兩個偏序集<A,Rp >的哈斯圖 8 12 10^4 J，6/ 9 7n 11 1 .分別寫出集合A和偏序關系Rp的集合表達式. 43.對于下列集合與整除關系畫出哈斯圖 a (a) 解：(a)A={a,b,c,d,e,f,g} Rp ={<a,b>,<a,c>,<a,d>,<a (b) A={a,b,c,d,e,f,g} Rp ={<a,b>,<a,c>,<a,d>,<a 46.分別回出卜列各偏序集 最小元. (1)A={a,b,c,d,e} Rp ={<a,d>,<a,c>,<a,b>,〈 (2)A={a,b,c,d,e}, R bM-g a (b) e>,<a,f>,<a,g>,<b,d>,<b,e>,<c,f>,<c,g>} I a e>,<a,f>,<d,f>,<e,f>} I a <A,RP >的哈斯圖，并找出A的極大元 極小元 最大元和 ;a,e>,vb,e>,vc,e>,<d,e>} I a p ={<c,d>} IA. 解: ⑴ 項目 (1) (2) 極人兒： e a,b,d,e 極小元： a a,b,c,e 取大兀： e 最小元： a (2) 第八章部分課后習題參考答案 1.設 f :N N,且 1,若以奇數(shù) f (x)= 三若x為偶數(shù) 2, 求 f (0), -1({3,5,7}). ({0})， f (1), f ({1}), f ({0,2,4,6,…}) , f ({4,6,8}), 解：f (0)=0, f({0})={0}, f (1)=1, f({1})={1}, -1 ({3,5,7})={6,10,14}. f ({0,2,4,6, …}尸N, f ({4,6,8})={2,3,4}, f 4.判斷下列函數(shù)中哪些是滿射的？哪些是單射的？哪些是雙射的？ (1) f:N N, f(x)=x 2+2 不是滿射，不是單射 (2) f:N N,f(x)=(x)mod 3,x 除以 3 的余數(shù) 不是滿射，不是單射 ⑶f:N 1, N,f(x)= 0, 若x為奇數(shù) 若x為偶數(shù) 不是滿射，不是單射 ⑷f:N {0,1},f(x)= 0,若x為奇數(shù) 1,若x為偶數(shù) 是滿射，不是單射 ⑸ f:N-{0} R,f(x)=lgx 不是滿射，是單射 (6) f:R R,f(x)=x 2-2x-15 不是滿射，不是單射 5.設*=國上6~}丫={1,2,3}力={<2,1>,<02>,<63>,} 判斷以下命題的真假 (1)f是從X到Y(jié)的二元關系，但不是從X到Y(jié)的函數(shù)； 對 (2)f是從X到Y(jié)的函數(shù)，但不是滿射，也不是單射的； 錯 (3)f是從X到Y(jié)的滿射，但不是單射； 錯 (4)f是從X到Y(jié)的雙射. 錯 第十章部分課后習題參考答案 4 .判斷下列集合對所給的二元運算是否封閉： (1) 整數(shù)集合Z和普通的減法運算。 封閉，不滿足交換律和結(jié)合律，無零元和單位元 (2) 非零整數(shù)集合K和普通的除法運算。不封閉 (3) 全體n n實矩陣集合M (R)和矩陣加法及乘法運算，其中 生2。 封閉 均滿足交換律，結(jié)合律，乘法對加法滿足分配律； 加法單位元是零矩陣，無零元； 乘法單位元是單位矩陣，零元是零矩陣； (4) 全體n n實可逆矩陣集合關于矩陣加法及乘法運算，其中 e2。不封閉 (5) 正實數(shù)集合艮一和二運算，其中"運算定義為： 爐工 b = R-, at-b = al — a — b 不封閉 因為111111 1 R (6) n巨Z+hZ = {m|z e ZI遙關于普通的加法和乘法運算。 封閉，均滿足交換律，結(jié)合律，乘法對加法滿足分配律 加法單位元是0,無零元； 乘法無單位元(n 1),零元是0; n 1單位元是1 (7) A = { a1，a2， 冏} nN”運算定義如下： va, b E A, a= b = t 封閉 不滿足交換律，滿足結(jié)合律， (8) S =⑦-小"用關于普通的加法和乘法運算。 封閉 均滿足交換律，結(jié)合律，乘法對加法滿足分配律 (9) S = {0,1},S 是關于普通的加法和乘法運算。 加法不封閉，乘法封閉；乘法滿足交換律，結(jié)合律 (10) S = ［工］”2小巨2+) ,S關于普通的加法和乘法運算。 加法不封閉，乘法封閉，乘法滿足交換律，結(jié)合律 5 .對于上題中封閉的二元運算判斷是否適合交換律，結(jié)合律，分配律。 見上題 7 .設*為Z上的二元運算 x, y Z , X * Y = min ( x , y ),即x和y之中較小的數(shù). (1)求4 * 6 , 7 * 3 。 4. 3 (2)*在Z上是否適合交換律，結(jié)合律，和幕等律？ 滿足交換律，結(jié)合律，和幕等律 (3)求*運算的單位元，零元及Z中所有可逆元素的逆元。 單位元無，零元1,所有元素無逆元 8. S Q Q Q為有理數(shù)集，*為$上的二元運算，v<a,b>,<x,y >憶S有 < a , b >*<x , y> = <ax , ay + b> (1) *運算在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) *運算是否有單位元，零元？ 如果有請指出，并求S中所有可逆元素的逆元 設<a,b> 是單位元，v<x,y > s S , <a,b >*<x,y>= <x,y>*<a,b >=<x,y> 貝U<ax,ay+b>=<xa,xb+y>=<x,y> ,解的 <a,b>=<1,0> ,即為單位。 設<2口>是零元，爐<x,y > e S , <a,b >*<x,y>= <x,y>*<a,b >=<a,b> 貝U<ax,ay+b>=<xa,xb+y>=<a,b> ,無解。即無零元。 v<x,y > 七 S,設<2口>是它的逆元 <a,b >*<x,y>= <x,y>*<a,b >=<1,0> <ax,ay+b>=<xa,xb+y>=<1,0> a=1/x,b=-y/x 所以當x 0時, x, y (a)交換律，結(jié)合律，幕等律都滿足， 零元為a,沒有單位元； (b)滿足交換律和結(jié)合律，不滿足幕等律，單位元為 a,沒有零元 a 1 a, b 1 b (c)滿足交換律，不滿足幕等律，不滿足結(jié)合律 a (b b) a a b, (a b) b a b a a (b b) (a b) b 沒有單位元，沒有零元 (d)不滿足交換律，滿足結(jié)合律和幕等律 沒有單位元，沒有零元 (2)求每個運算的單位元，零元以及每一個可逆元素的逆元。 見上 16.設V=〈 N, + , ?〉，其中+ , ?分別代表普通加法與乘法，對下面給定的每個集合 確定它是否構(gòu)成V的子代數(shù)，為什么？ (1) S1=(2n.| n Z!是 (2) S2=2n + i||nmZ! 不是 加法不封閉 (3) & = {-1 , 0, 1} 不是，加法不封閉 第十一章部分課后習題參考答案 8.設S={0, 1, 2, 3},⑨為模4乘法，即 "x,y C S, x y=(xy)mod 4 問〈S,悔〉是否構(gòu)成群？為什么？ 解：(1) x,y € S, x y=(xy)mod 4 S,a 是 S上的代數(shù)運算 (2) x,y,z CS,設 xy=4k+r 0 r 3 (x v) z =((xy)mod 4) z=r 8 z=(rz)mod 4 =(4kz+rz)mod 4=((4k+r)z)mod 4 =(xyz)mod 4 同理 x--：(y|z) =(xyz)mod 4 所以，(x y) z = x因(y&z),結(jié)合律成立。 ⑶ x € S, (x g 1)=(1 0x)=x,,所以1是單位元。 ⑷1 1 1, 3 1 3, 0和2沒有逆元 所以，〈S」〉不構(gòu)成群 9.設Z為整數(shù)集合，在Z上定義二元運算。如下： " x,y 6 Z,xoy= x+y-2 問Z關于o運算能否構(gòu)成群？為什么？ 解：(1) x,y € Z, xoy= x+y-2 Z ,o是Z上的代數(shù)運算。 (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é)合律成立。 ⑶設e是單位元， x C Z, xo e= eox=x，即 x+e-2= e+x-2=x, e=2 (4) x C Z ,設 x 的逆元是 y, xoy= yox= e,即 x+y-2=y+x-2=2, 所以，x 1 y 4 x 所以〈Z, o＞構(gòu)成群 10 10 1 0 1 0 ,,, 一… … 11.設G= , , , ，證明G關于矩陣乘法構(gòu)成一個群. 0 10 1 0 1 0 1 解：（1） x,y € G,易知xy C G,乘法是Z上的代數(shù)運算 (2)矩陣乘法滿足結(jié)合律 1 0 、，、 ⑶設1 0是單位元， 0 1 ⑷ 每個矩陣的逆元都是自己。 所以G關于矩陣乘法構(gòu)成一個群. 14 .設G為群，且存在aCG,使得 G={a k I k C Z} 證明：G是交換群。 證明：x,y C G,設 x ak, y al ,則 xy akal ak l al k alak yx 所以，G是交換群 17 .設G為群，證明e為G中唯一的幕等元。 證明：設e0 G也是幕等元，則e2 a ,即e2 ee ,由消去律知e e 18 .設G為群，a,b,c CG,證明 I abc I = I bca I = I cab I 證明：先證設(abc)k e (bca)k e 設(abc)k e, 則(abc)(abc)(abc) (abc) e, 即 a(bca)(bca)(bca) (bca)a 1 e 左邊同乘a 1 ,右邊同乘a得 k 1 (bca)( bca)(bca) (bca) (bac) a ea e 反過來，設(bac)k e,則(abc)k e. 由元素階的定義知，I abc I = I bca I ,同理I bca I = I cab I 19 .證明：偶數(shù)階群G必含2階元。 證明：設群G不含2階元，a G,當a e時，a是一階元，當a e時，a至少是3 階元,因為群G時有限階的，所以a是有限階的，設a是k階的，則a 1也是k階的，所以 高于3階的元成對出現(xiàn)的,G不含2階元，G含唯一的1階元e,這與群G是偶數(shù)階的矛 盾。所以，偶數(shù)階群G必含2階元 20 .設G為非Abel群，證明G中存在非單位元a和b,awb,且ab=ba. 證明：先證明G含至少含3階元。 若G只含1階元，則G={e},G為Abel群矛盾； 若G除了 1階元e外，其余元a均為2階元，則a2 e, a 1 a 1 1 1 1 1 1 a, b G, a a, b b, (ab) ab,所以 ab a b (ba) ba, 與G為Abel群矛盾； 所以，G含至少含一個3階元，設為a,則a a2,且a2a aa2。 令b a2的證。 21 .設G是M(R)上的加法群，n>2,判斷下述子集是否構(gòu)成子群。 (1)全體對稱矩陣 是子群 (2)全體對角矩陣 是子群 (3)全體行列式大于等于0的矩陣.不是子群 (4)全體上(下)三角矩陣。 是子群 22 .設G為群，a是G中給定元素，a的正規(guī)化子N (a)表示G中與a可交換的元素構(gòu)成 的集合，即 N (a) ={x I x C GA xa=ax} 證明N (a)構(gòu)成G的子群。 證明：ea=ae, e N (a) x, y N (a), 貝1J ax xa, ay ya a(xy) (ax)y (xa)y x(ay) x(ya) (xy)a,所以 xy N(a) 由 ax xa ,得 x 1 axx 1 x 1 xax 1,x 1ae eax 1 ,即 x 1a ax 1 ,所以 x 1 N(a) 所以N (a)構(gòu)成G的子群 31.設1是群G到G的同態(tài)，2是G到G的同態(tài)，證明1 2是G到G的同態(tài)。 證明：有已知1是G到G的函數(shù)，2是G到G的函數(shù)，則1 - 2是G到G的函數(shù)。 a,b G1, ( 1 2)(ab) 2( 1(ab)) 2( 1(a) 1(b)) (2( 1(a)))( 2( 1(b))) ( 1 2)(a)( 1 2)(b) 所以：1 - 2是G到G的同態(tài) 33.證明循環(huán)群一定是阿貝爾群，說明阿貝爾群是否一定為循環(huán)群，并證明你的結(jié)論 證明：設G是循環(huán)群，令G=<a>, x,y G,令x ak, y al,那么 xy akal ak l al k alak yx,G 是阿貝爾群 e a b c e e a b c 是交換群，但不是循環(huán)群，因為e是一階元, a,b,c是二階元。 克萊因四元群，G {e,a,b,c} a b c a b c e c b c e a b a e 36.設，是5元置換，且 12345 12345 21453’ 3 4 5 1 2 ⑴計算，，1, 1, 1 ； ⑵將，1, 1表成不交的輪換之積。 (3)將(2)中的置換表示成對換之積，并說明哪些為奇置換，哪些為偶置換 解：⑴ 1 1 2 3 4 5 2 15 3 4 1 2 3 4 5 4 3 12 5 1 2 3 4 5 5 4 13 2 1 2 3 4 5 4 5 12 3 (1425) 1 (14253) 1 (143)(25) (3) (14)(12)(15) 奇置換, (14)(12)(15)(13) 偶置換 (14)(13)(25)奇置換 第十四章部分課后習題參考答案 5、設無向圖G有10條邊，3度與4度頂點各2個，其余頂點的度數(shù)均小于 3,問G至 少有多少個頂點？在最少頂點的情況下，寫出度數(shù)列、 (G)、(G)。 解：由握手定理圖G的度數(shù)之和為：2 10 20 3度與4度頂點各2個，這4個頂點的度數(shù)之和為14度。 其余頂點的度數(shù)共有6度。 其余頂點的度數(shù)均小于3,欲使G的頂點最少，其余頂點的度數(shù)應都取 2, 所以，G至少有7個頂點，出度數(shù)列為3,3,4,4,2,2,2, (G) 4, (G) 2. 7、設有向圖D的度數(shù)列為2,3,2, 3,出度列為1,2,1,1,求D的入度列，并求(D), (D), (D), (D), (D), (D). 解：D的度數(shù)列為2, 3, 2, 3,出度列為1, 2, 1, 1, D的入度列為1,1,1,2. (D) 3, (D) 2, (D) 2, (D) 1, (D) 2, (D) 1 8、設無向圖中有6條邊，3度與5度頂點各1個，其余頂點都是2度點，問該圖有多少 個頂點？ 解：由握手定理圖G的度數(shù)之和為：2 6 12 設2度點x個，則3 1 5 1 2x 12, x 2,該圖有4個頂點. 14、下面給出的兩個正整數(shù)數(shù)列中哪個是可圖化的？對可圖化的數(shù)列，試給出 3種非同 構(gòu)的無向圖，其中至少有兩個時簡單圖。 (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+3+3+4+4=16,是偶數(shù)，可圖化； 18、設有3個4階4條邊的無向簡單圖G、G、G,證明它們至少有兩個是同構(gòu)的。 證明：4階4條邊的無向簡單圖的頂點的最大度數(shù)為 3,度數(shù)之和為8,因而度數(shù)列 為2, 2, 2, 2; 3, 2, 2, 1; 3, 3, 1, 1。但3, 3, 1, 1對應的圖不是簡單圖。所以 從同構(gòu)的觀點看，4階4條邊的無向簡單圖只有兩個: 所以，G、G、G至少有兩個是同構(gòu)的。 20、已知n階無向簡單圖G有m條邊，試求G的補圖G的邊數(shù)m 解：m n(n」m 2 21、無向圖G如下圖 (1)求G的全部點割集與邊割集，指出其中的割點和橋； (2)求G的點連通度k(G)與邊連通度(G)。 解：點割集：{a,b},(d) 邊割集{e2,e3},{e3,e4},{e1,e2},{e1,e4}{e1,e3},{e2,e4},{e5} k(G)= (G)=1 28、設n階無向簡單圖為3-正則圖，且邊數(shù)m與n滿足2n-3=m問這樣的無向圖有幾種 非同構(gòu)的情況？ 解： 3n 2m 得 n=6,m=9. 2n 3 m 31、設圖G和它的部圖G的邊數(shù)分別為m和m,試確定G的階數(shù)。 解：m m n(n一1) 2 45、有向圖D如圖 (1) 求V2到V5長度為1 1 1 8(m m) 得n 2 ,2, 3, 4的通路數(shù); ⑵求V5到V5長度為1, 2, 3, 4的回路數(shù); (3)求D中長度為4的通路數(shù)； (4)求D中長度小于或等于4的回路數(shù)； (5)寫出D的可達矩陣。 解：有向圖D的鄰接矩陣為: 0 0 2 0 1 , A2 0 0 0 10 10 0 10 10 0 0 0 0 2 0 1 0 1 0 A3 0 0 0 0 2 2 0 2 0 0 2 0 2 0 0 0 2 0 2 0 2 0 2 0 0 0 2 0 2 0 0 0 0 0 4 0 0 0 0 4 4 0 4 0 0 4 A 0 0 0 0 4 4 0 4 0 0 0 4 0 4 0 2 n 3 AAA A4 0 12 15 5 2 5 2 2 2 12 15 4 2 5 2 2 2 5 2 5 4 (1) V2到V5長度為1, 2, 3, 4的通路數(shù)為0,2,0,0 ; (2) V5到V5長度為1, 2, 3, 4的回路數(shù)為0,0,4,0 ; ⑶D中長度為4的通路數(shù)為32; ⑷D中長度小于或等于4的回路數(shù)10; 11111 11111 ⑷出D的可達矩陣P 11111 11111 11111 第十六章部分課后習題參考答案 1、畫出所有5階和7階非同構(gòu)的無向樹 2、一棵無向樹T有5片樹葉，3個2度分支點，其余的分支點都是 3度頂點，問T有幾個頂點？ 解：設3度分支點x個，則 5 1 3 2 3x 2 (5 3 x 1),解得 x 3 T有11個頂點 3、無向樹T有8個樹葉，2個3度分支點，其余的分支點都是 4度頂點，問T有幾個4度分支 點？根據(jù)T的度數(shù)列，請至少畫出 4棵非同構(gòu)的無向樹。 解：設4度分支點x個，則 2 3 4x 2 (8 2 x 1),解得 x 2 度數(shù)列 111111113344 4、棵無向樹T有Q(i=2 , 3,…，k)個i度分支點，其余頂點都是樹葉，問 T應該有幾片樹 葉？ 解：設樹葉x片，則 ni i x 1 2 (ni x 1),解得 x (i 2)ni 2 評論：2, 3, 4題都是用了兩個結(jié)論，一是握手定理，二是 m n 1 5、n(n>3)階無向樹T的最大度A(T)至少為幾？最多為幾？ 解：2, n-1 6、若n(n>3)階無向樹T的最大度=2,問T中最長的路徑長度為幾？ 解：n-1 7、證明：n(n > 2)階無向樹不是歐拉圖. 證明：無向樹沒有回路，因而不是歐拉圖。 8、證明：n(n > 2)階無向樹不是哈密頓圖. 證明：無向樹沒有回路，因而不是哈密頓圖。 9、證明：任何無向樹 T都是二部圖. 證明：無向樹沒有回路，因而不存在技術長度的圈，是二部圖。 10、什么樣的無向樹 T既是歐拉圖，又是哈密頓圖 ？ 解：一階無向樹 14、設e為無向連通圖G中的一條邊，e在G的任何生成樹中，問e應有什么性質(zhì)？ 解：e是橋 15、設e為無向連通圖G中的一條邊，e不在G的任何生成樹中， 問e應有什么性質(zhì)？ 解：e是環(huán) 23、已知n階m條的無向圖G是k(k >2)棵樹組成的森林，證明：m = n-k.； 證明：數(shù)學歸納法。k=1時，m = n-1 ,結(jié)論成立； 設k=t-1(t-1 1)時，結(jié)論成立，當k=t時，無向圖G是t棵樹組成的森林，任取兩棵樹，每棵 樹任取一個頂點，這兩個頂點連線。則所得新圖有 t-1棵樹，所以m = n- (k-1). 所以原圖中m = n-k 得證。 24、在圖16.6所示2圖中，實邊所示的生成子圖 T是該圖的生成樹. (1)指出T的弦，及每條弦對應的基本回路和對應 T的基本回路系統(tǒng) (2)指出T的所有樹枝， 及每條樹枝對應的基本割集和對應 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)有關問題仿照給出 25、求圖16.17所示帶權(quán)圖中的最小生成樹 . 圖 16.17 (a) (b) 解： 注：答案不唯一。 37、畫一棵權(quán)為3, 4, 5, 6, 7, 8, 9的最優(yōu)2叉樹，并計算出它的權(quán) 38.下面給出的各符號串集合哪些是前綴碼 ？ 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.設7個字母在通信中出現(xiàn)的頻率如下 ： a: 35% b: 20% c: 15% d: 10% e: 10% f: 5% g: 5% .并指出傳輸 用Huffman算法求傳輸它們的前綴碼.要求畫出最優(yōu)樹，指出每個字母對應的編碼 10n(n >2)個按上述頻率出現(xià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)個按上述頻率出現(xiàn)的字母，需要 255*10 n-2個二進制數(shù)字