離散數學(屈婉玲)答案說課講解

1、離 散 數 學 ( 屈 婉 玲 ) 答案精品資料第一章部分課后習題參考答案16 設 p、 q 的真值為 0； r、 s的真值為 1，求下列各命題公式的真值。（1） p(q r) 0(0 1) 0（2）（p? r ）( qs) （0? 1）(1 1) 01 0.（3）（ p qr） ? (p qr) （111） ? (0 00) 0(4) （ r s） (p q) （01） (1 0) 00 117判斷下面一段論述是否為真：“ 是無理數。并且，如果 3 是無理數，則 2 也是無理數。另外 6 能被 2 整除， 6 才能被 4 整除?！贝穑?p: 是無理數 1q: 3 是無理數 0r: 2 是無理

2、數 1s: 6 能被 2 整除 1t: 6 能被 4 整除 0命題符號化為： p(qr)(ts)的真值為 1， 所以這一段的論述為真 。19用真值表判斷下列公式的類型：（4） (pq) ( q p)（5） (pr) ( p q)（6） (pq) (qr) (pr)答： （4）p q pq q p q p (pq)( q p)0 0 1 1 1 1 10 1 1 0 1 1 11 0 0 1 0 0 11 1 1 0 0 1 1所以公式類型為永真式 /最后一列全為 1（5）公式類型為可滿足式（方法如上例） /最后一列至少有一個 1（6）公式類型為永真式（方法如上例） /第二章部分課后習題參考答案

3、僅供學習與交流，如有侵權請聯(lián)系網站刪除 謝謝 2精品資料3. 用等值演算法判斷下列公式的類型，對不是重言式的可滿足式，再用真值表法求出成真賦值 .(1) (pqq)(2)(p(pq)(pr)(3)(pq)(pr)答： (2) （p(pq)）(pr) ( p(pq)( pr) ppqr 1所以公式類型為永真式(3) P 0 0 0 0 1 1 1 1q00110011r01010101pq00111111pr00000101（pq） (pr)11000101所以公式類型為可滿足式4. 用等值演算法證明下面等值式：(2)(p q) (p r) (p (q r)(4)(p q) ( pq) (p q

4、) (p q) 證明（ 2） (p q) (p r)( pq) ( pr)p(q r)p (q r)（4） (p q) ( pq) (p ( pq) ( q( pq) (p p) (p q) ( q p) ( qq)1(p q) (p q) 1(p q) (p q)5. 求下列公式的主析取范式與主合取范式，并求成真賦值(1)( pq) ( qp)(2) (p q) qr僅供學習與交流，如有侵權請聯(lián)系網站刪除 謝謝 3精品資料(3)(p (q r) (p qr)解：（1）主析取范式( pq) ( q p)(p q) ( q p)( p q) ( q p)( p q) ( q p) ( q p)

5、(p q) (p q)( p q) (p q) (p q)m0 m2 m3(0,2,3)主合取范式：( pq) ( q p)(p q) ( q p)( p q) ( q p)( p ( q p) ( q ( q p)1 (p q)(p (1)(2) 主合取范式為： (p q) (pq)q q)rqM1r( p q) q r0所以該式為矛盾式 .主合取范式為 (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 ( p (p q r) ( qr)r) (p q r)僅供學習

6、與交流，如有侵權請聯(lián)系網站刪除 謝謝 4精品資料1 11所以該式為永真式 .永真式的主合取范式為 1主析取范式為 (0,1,2,3,4,5,6,7)第三章部分課后習題參考答案14. 在自然推理系統(tǒng) P 中構造下面推理的證明：(2) 前提： p q, (q r),r結論： p(4) 前提： q p,q s,s t,t r 結論： p q證明：（ 2） (q r) 前提引入 q r 置換q r 蘊含等值式 r 前提引入 q 拒取式p q 前提引入p 拒取式證明（ 4）：t r 前提引入t 化簡律q s 前提引入 s t 前提引入q t 等價三段論（ q t） (t q) 置換僅供學習與交流，如有侵

7、權請聯(lián)系網站刪除 謝謝 5精品資料（q t） 化簡q 假言推理q p 前提引入p 假言推理(11)p q 合取15 在自然推理系統(tǒng)(1) 前提： p (q 結論： s rP 中用附加前提法證明下面各推理：r),s p,q證明s 附加前提引入s p 前提引入p 假言推理p (q r) 前提引入q r 假言推理q 前提引入r 假言推理16 在自然推理系統(tǒng) P 中用歸謬法證明下面各推理：(1) 前提： p q, r q,r s 結論： p證明：p 結論的否定引入p q 前提引入q 假言推理r q 前提引入r 化簡律r s 前提引入r 化簡律僅供學習與交流，如有侵權請聯(lián)系網站刪除 謝謝 6精品資料r

8、r 合取由于最后一步 r r 是矛盾式 , 所以推理正確 .第四章部分課后習題參考答案3. 在一階邏輯中將下面將下面命題符號化題的真值 :(1) 對于任意 x, 均有 2=(x+ )(x(2) 存在 x, 使得 x+5=9.其中(a) 個體域為自然數集合 .(b) 個體域為實數集合 .解：F(x): 2=(x+ )(x )., 并分別討論個體域限制為 (a),(b) 條件時命).G(x): x+5=9.(1) 在兩個個體域中都解釋為 xF (x)，在（ a）中為假命題，在 (b) 中為真命題。(2) 在兩個個體域中都解釋為 xG( x) ，在（ a） (b) 中均為真命題。4. 在一階邏輯中將

9、下列命題符號化 :(1) 沒有不能表示成分數的有理數 .(2) 在北京賣菜的人不全是外地人 .解:(1)F(x): x 能表示成分數H(x): x 是有理數命題符號化為 : x( F( x) H (x)(2)F(x): x 是北京賣菜的人 H(x): x 是外地人命題符號化為 : x( F (x) H (x)5. 在一階邏輯將下列命題符號化 :(1) 火車都比輪船快 .僅供學習與交流，如有侵權請聯(lián)系網站刪除 謝謝 7比 y 快.精品資料(3) 不存在比所有火車都快的汽車 .解:(1)F(x): x 是火車 ; G(x): x 是輪船 ; H(x,y): x 比 y 快命題符號化為 : x y(

10、 F ( x) G( y) H (x , y)(2) (1)F(x): x 是火車 ; G(x): x 是汽車 ; H(x,y): x 命題符號化為 : y(G( y) x( F (x) H ( x , y)9. 給定解釋 I 如下:(a) 個體域 D 為實數集合 R.(b) D 中特定元素 =0.(c) 特定函數 (x,y)=x y,x,y D(d) 特定謂詞 (x,y):x=y, (x,y):xy,x,y D .說明下列公式在 I 下的含義 , 并指出各公式的真值 :(1) x y(G ( x , y) F ( x, y)(2) x y( F ( f ( x, y), a) G (x ,

11、y)答:(1) 對于任意兩個實數 x,y, 如果 xy, 那么 x y. 真值 1.(2) 對于任意兩個實數 x,y, 如果 x-y=0, 那么 xy. 真值 0.10. 給定解釋 I 如下：（a） 個體域 D=N(N為自然數集合 ).（b） D 中特定元素 =2.（c） D 上函數 =x+y, (x,y)=xy.（d） D 上謂詞 (x,y):x=y.說明下列各式在 I 下的含義，并討論其真值 .(1) xF(g(x,a),x)(2) x y(F(f(x,a),y) F(f(y,a),x)答:(1) 對于任意自然數 x, 都有 2x=x, 真值 0.(2) 對于任意兩個自然數 x,y, 使得

12、如果 x+2=y, 那么 y+2=x. 真值 0.11. 判斷下列各式的類型 :(1)僅供學習與交流，如有侵權請聯(lián)系網站刪除 謝謝 8精品資料(3) yF(x,y).解:(1) 因為 p (q p) p ( q p) 1 為永真式；所以 為永真式；(3) 取解釋 I 個體域為全體實數F(x,y) ： x+y=5所以 , 前件為任意實數 x 存在實數 y使 x+y=5，前件真；后件為存在實數 x 對任意實數 y都有 x+y=5，后件假， 此時為假命題再取解釋 I 個體域為自然數 N，F(xiàn)(x,y) ： :x+y=5所以 , 前件為任意自然數 x 存在自然數 y 使 x+y=5，前件假。此時為假命題

13、。此公式為非永真式的可滿足式。13. 給定下列各公式一個成真的解釋，一個成假的解釋。(1) (F(x)(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. 給定解釋如下 :(a)

14、個體域 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.僅供學習與交流，如有侵權請聯(lián)系網站刪除 謝謝 9精品資料試求下列公式在下的真值 .(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

15、), 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) F (4 ,3) (1 F (3,4) (0 F (3,3)(0 0) (1 1) (1 1) (0 0) 112. 求下列各式的前束范式。(

16、1) xF ( x) yG( x, y)(5) x1 F (x1 , x2 ) ( H (x1 ) x2 G(x1 , x2 ) ( 本題課本上有錯誤 )解:(1) xF ( x) yG( x , y) xF ( x) yG(t , y) x y( F ( x) G(t , y)(5) x1 F ( x1 , x2 ) ( H (x1 ) x2 G ( 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 ( x1 , x4 ) ( H

17、(x3 ) G (x3 , x2 )15. 在自然數推理系統(tǒng) F 中, 構造下面推理的證明 :(1) 前提 : xF ( x) y( F ( y) G( y) R( y) , xF (x)結論 : xR(x)(2) 前提 : x(F(x) (G(a) R(x), xF(x)結論 : x(F(x) R(x)證明(1) xF (x) 前提引入僅供學習與交流，如有侵權請聯(lián)系網站刪除 謝謝 10精品資料F(c) EI xF (x) y( F ( y) G( y) R( y) 前提引入 y( F ( y) G( y) R( y) 假言推理(F(c) G(c) R(c)F(c) G(c)R(c) xR(x

18、)UI附加假言推理EG(2) xF(x) 前提引入F(c) EI x(F(x) (G(a) R(x)F(c) (G(a) R(c) G(a) R(c)R(c)F(c) R(c) x(F(x) R(x)前提引入UI假言推理化簡合取引入第六章部分課后習題參考答案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 假僅供學習與交流，如有侵權請聯(lián)系網站刪除 謝謝 11精品資料6設 a,b,c 各不相同，判斷下述等式中哪個等式為真 :

19、（ 1） a,b， c, = a,b ,c 假（2） a ,b,a =a,b 真（3） a， b = a,b （4） ， ， a,b = 8求下列集合的冪集：假, ,a,b 假（ 1） a,b,c P(A)=（2） 1， 2， 3 P(A)=（3） P(A)=（4） ， P(A)=14化簡下列集合表達式：,a,b,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） B ） - （A B）（2）（ A B C） - （B C） A解:(1) （A B） B ） - （A B） = （A B） B ） （ A

20、B）=（A B） （ A B） ) B= B=（2）（ A B C） - （B C） A=（ A B C） （ B C） A= （A （ B C） （ B C ） （ B C） A= （A （ B C） A=（A （ B C） A=A18某班有 25 個學生，其中 14 人會打籃球， 12 人會打排球， 6 人會打籃球和排球， 5人會打籃球和網球，還有 2 人會打這三種球。已知 6 個會打網球的人都會打籃球或排球。求不會打球的人數。解: 阿 A=會打籃球的人 ， B=會打排球的人 ， C=會打 網球的人|A|=14, |B|=12, |A B|=6,|A C|=5,| A B C|=2,|C|

21、=6,C A B如圖所示。25-(5+4+2+3)-5-1=25-14-5-1=5僅供學習與交流，如有侵權請聯(lián)系網站刪除 謝謝 12精品資料不會打球的人共 5 人21. 設集合 A1 ， 2， 2， 3， 1， 3,（ 1） A （2） A （3） A （4） A 解 : （1） A=1， 2 2， HYPERLINK l _bookmark1 3（2） A=1， 2 2， 3（3） A=1 2 3 =（4） A=27、設 A,B,C 是任意集合，證明(1)(A-B)-C=A- B C(2)(A-B)-C=(A-C)-(B-C)證明1， 3 1， 3 , 計算下列表達式：=1， 2， 3, =

22、(1) (A-B)-C=(A B) C= A ( B C)= A (B C) =A- B C(2) (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 上的恒等關系 I A ,全域關系 EA ,小于或等于關系 LA ,整除關系 DA .解： I A =,E A=,LA=,DA=13.設 A=,B=,僅供學習與交流，如有侵權請聯(lián)系網站刪除 謝謝 132R2 =R2=2 3精品資料求 A B,A B, domA, dom

23、B, dom(A B), ranA, ranB, ran(A B ), fld(A-B).解： A B=,A B=domA=1,2,3domB=1,2,4dom(A B)=1,2,3,4ranA=2,3,4ranB=2,3,4ran(A B)=4fld R=dom R ran RA-B=, ， fld(A-B)=1,2,314.設 R=,求 R R, R-1 , R 0,1, R1,2解： R R=,R-1, =,R 0,1=,R1,2=ran(R 1,2)=2,316設 A=a,b,c,d， R1 R2 為 A 上的關系，其中 ，R1 a, a , a, b , b, dR2 a, d ,

24、b,c , b,d , c, b求 R1 R2 , R2 R1 , R1 , R2 。解: R 1 R2=,R 2 R1=R1 =R1 R1=,2 R2=,僅供學習與交流，如有侵權請聯(lián)系網站刪除 謝謝 14精品資料R23=R2 R22=,36設 A=1， 2， 3， 4 ，在 A A 上定義二元關系 R，, A A ， u,v R u + y = x + v.(1) 證明 R 是 A A上的等價關系 .(2) 確定由 R 引起的對 A A 的劃分 .（ 1）證明： R u+y=x-y R u-v=x-y A Au-v=u-vRR是自反的任意的 , AA如果R ，那么 u-v=x-yx-y=u-

25、v RR是對稱的任意的 , AA若R,R則 u-v=x-y,x-y=a-bu-v=a-b RR是傳遞的R是 AA上的等價關系(2) =, , , , , , 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 導出的劃分 .僅供學習與交流，如有侵權請聯(lián)系網站刪除 謝謝 15精品資料(1) 證明： a， b A Aa+b=a+bRR是自反的任意的 , AA設R ，則 a+b=c+dc+d=a+b RR是對稱的任意的 , AA若R,R則 a+b=c

26、+d,c+d=x+ya+b=x+y RR是傳遞的R是 A A上的等價關系(2) =, , , , , 43. 對于下列集合與整除關系畫出哈斯圖 :(1) 1,2,3,4,6,8,12,24(2) 1,2,3,4,5,6,7,8,9,10,11,12解:8422412631107842126319511(1) (2)45. 下圖是兩個偏序集 的哈斯圖 . 分別寫出集合 A 和偏序關系 R 的集合表達式 .僅供學習與交流，如有侵權請聯(lián)系網站刪除 謝謝 16ca bb de g精品資料d e f g fb ca a(a) (b)解 : (a)A=a,b,c,d,e,f,gR =, I A(b) A=

27、a,b,c,d,e,f,gR =, I A46. 分別畫出下列各偏序集 的哈斯圖 , 并找出 A 的極大元 極小元 最大元和最小元 .(1)A=a,b,c,d,eR =, I A.(2)A=a,b,c,d,e, R = IA.解:edb c dea c(1) (2)項目 (1) (2)極大元 : e a,b,d,e極小元 : a a,b,c,e最大元 : e 無最小元 : a 無僅供學習與交流，如有侵權請聯(lián)系網站刪除 謝謝 172，精品資料第八章部分課后習題參考答案1設 f :N N, 且1，若x為奇數f (x)= x 若x為偶數求 f (0), f (0), f (1), f (1), f

28、(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. 判斷下列函數中哪些是滿射的 ?哪些是單射的(1) f:N(2) f:NN, f(x)=x 2+2 不是滿射，不是單射N,f(x)=(x)mod 3, x 除以 3 的余數?哪些是雙射的 ?不是滿射，不是單射(3) f:N N,f(x)=1，若x為奇數 0，若x為偶數不是滿射，不是單射(4) f:N 0,1,f(x)=0，若x為奇數 1，

29、若x為偶數是滿射，不是單射(5) f:N-0 R,f(x)=lgx 不是滿射，是單射(6) f:R R,f(x)=x 2-2x-15 不是滿射，不是單射5. 設 X=a,b,c,d,Y=1,2,3,f=, 判斷以下命題的真假 :(1)f 是從 X 到 Y 的二元關系 ,但不是從 X 到 Y 的函數 ; 對(2)f 是從 X 到 Y 的函數 ,但不是滿射 ,也不是單射的 ; 錯(3)f 是從 X 到 Y 的滿射 ,但不是單射 ; 錯(4)f 是從 X 到 Y 的雙射 . 錯第十章部分課后習題參考答案4 判斷下列集合對所給的二元運算是否封閉：僅供學習與交流，如有侵權請聯(lián)系網站刪除 謝謝 18精品資

30、料（ 1） 整數集合 Z 和普通的減法運算。封閉 ,不滿足交換律和結合律，無零元和單位元（2） 非零整數集合 普通的除法運算。 不封閉（3） 全體 n n 實矩陣集合 （R）和矩陣加法及乘法運算，其中 n 2。封閉 均滿足交換律，結合律，乘法對加法滿足分配律；加法單位元是零矩陣，無零元；乘法單位元是單位矩陣，零元是零矩陣；（4）全體 n n 實可逆矩陣集合關于矩陣加法及乘法運算，其中 n 2 。 不封閉（5）正實數集合 和 運算，其中 運算定義為：不封閉 因為 1 1 1 1 1 1 1 R（6） n 關于普通的加法和乘法運算。 封閉，均滿足交換律，結合律，乘法對加法滿足分配律加法單位元是 0

31、，無零元；乘法無單位元（ n 1），零元是 0； n 1 單位元是 1（7） A = a1 , a2 , , an n 運算定義如下：封閉 不滿足交換律，滿足結合律，（8） S = 關于普通的加法和乘法運算。封閉 均滿足交換律，結合律，乘法對加法滿足分配律（9） S = 0,1,S 是關于普通的加法和乘法運算。加法不封閉，乘法封閉；乘法滿足交換律，結合律（ 10） S = ,S 關于普通的加法和乘法運算。加法不封閉，乘法封閉，乘法滿足交換律，結合律5對于上題中封閉的二元運算判斷是否適合交換律，結合律，分配律。見上題7 設 * 為 Z 上的二元運算 x, y Z ，X * Y = min ( x

32、 ， y ), 即 x 和 y 之中較小的數 .僅供學習與交流，如有侵權請聯(lián)系網站刪除 謝謝 19精品資料(1) 求 4 * 6 ， 7 * 3 。4, 3(2)* 在 Z 上是否適合交換律，結合律，和冪等律？滿足交換律，結合律，和冪等律(3) 求* 運算的單位元，零元及 Z 中所有可逆元素的逆元。單位元無，零元 1, 所有元素無逆元8 S Q Q Q 為有理數集， * 為 S 上的二元運算， , S 有* = （1） * 運算在 S 上是否可交換，可結合？是否為冪等的？不可交換： *= *可結合： (*)*=*= *(*)=*=(*)*=*(*)不是冪等的（2） * 運算是否有單位元，零元？

33、 如果有請指出，并求 S 中所有可逆元素的逆元。設是單位元， S， *= *=則= ，解的 =，即為單位。設是零元， S， *= *=則= ，無解。即無零元。 S，設 是它的逆元 *= *=僅供學習與交流，如有侵權請聯(lián)系網站刪除 謝謝 20精品資料a=1/x,b=-y/x所以當 x 0 時， x, y1 1x,yx10令 S=a， b， S 上有四個運算： *， 分別有表 10.8 確定。(a) (b) (c) (d)(1) 這 4 個運算中哪些運算滿足交換律，結合律，冪等律？(a) 交換律，結合律，冪等律都滿足， 零元為 a,沒有單位元；(b)滿足交換律和結合律，不滿足冪等律，單位元為 a,

34、沒有零元a 1 a, b 1 b(c)滿足交換律 ,不滿足冪等律 ,不滿足結合律 a (b b) a a b, ( a b) b a b a a (b b) (a b) b沒有單位元 , 沒有零元(d) 不滿足交換律，滿足結合律和冪等律 沒有單位元 , 沒有零元(2) 求每個運算的單位元，零元以及每一個可逆元素的逆元。見上16設 V= N， + ， ，其中 + ， 分別代表普通加法與乘法，對下面給定的每個集合確定它是否構成 V 的子代數，為什么？（1） S1= 是（2） S2= 不是 加法不封閉（3） S3 = -1 ， 0， 1 不是，加法不封閉第十一章部分課后習題參考答案僅供學習與交流，如

35、有侵權請聯(lián)系網站刪除 謝謝 211 31精品資料8. 設 S=0， 1， 2， 3， 為模 4 乘法，即 x,y S, x y=(xy)mod 4問 S，解： (1)是否構成群？為什么？x,y S, x y=(xy)mod 4 S , 是 S 上的代數運算。(2) x,y,z S, 設 xy=4k+r (x y) z =(xy)mod 4)0 r 3z=r z=(rz)mod 4=(4kz+rz)mod 4=(4k+r)z)mod 4 =(xyz)mod 4同理 x (y 所以， (x(3) xS, (x(4) 1 1 ,z) =(xyz)mod 4y) z = x (y z) ，結合律成立。

36、 1)=(1 x)=x, ，所以 1 是單位元。3, 0 和 2 沒有逆元所以， S， 不構成群9. 設 Z 為整數集合，在 Z 上定義二元運算。如下： x,y Z,xoy= x+y-2問 Z 關于 o運算能否構成群？為什么？解： (1) x,y Z, xoy= x+y-2 Z ,o 是 Z 上的代數運算。(2) x,y,z Z,(xoy) oz =(x+y-2)oz=(x+y-2)+z-2=x+y+z-4同理(xoy)oz= xo(yoz) ，結合律成立。(3) 設 e 是單位元， xZ, xo e = e ox=x, 即 x+e-2= e+x-2=x, e=2(4) xZ , 設 x 的逆

37、元是 y, xoy= yox= e , 即 x+y-2=y+x-2=2, 所以， x 1 y 4 x所以 Z， o構成群11. 設 G=解： (1)1 0 1,0 1 0 x,y G,0 1 0 1 0, , ，證明 G關于矩陣乘法構成一個群1 0 1 0 1易知 xyG,乘法是 Z 上的代數運算。僅供學習與交流，如有侵權請聯(lián)系網站刪除 謝謝 22精品資料(2)1 (3) 設0矩陣乘法滿足結合律0是單位元，1(4) 每個矩陣的逆元都是自己。所以 G關于矩陣乘法構成一個群14. 設 G為群，且存在G=a證明： G是交換群。證明: x,y G，設 x xy ak a l ak l所以， G是交換群

38、aG,使得k kZak , y al ，則a l k al ak yx17. 設 G為群，證明 e 為 G中唯一的冪等元。證明: 設e0G 也是冪等元，則 e e0 ，即 ee0e ，由消去律知 e0 e18. 設 G為群， a,b,c證明： 先證設 ( abc)kG,證明abc = bca = cab e (bca) k e設 (abc)k即左邊同乘e, 則 (abc)(abc)(abc) ( abc) e，a(bca)(bca)(bca) (bca)a 1 ea 1 ，右邊同乘 a 得(bca)(bca)(bca) (bca) (bac) k a 1ea e反過來，設 (bac)k e,

39、則 (abc)k e.由元素階的定義知， abc = bca ，同理 bca = cab 19. 證明：偶數階群 G必含 2 階元。僅供學習與交流，如有侵權請聯(lián)系網站刪除 謝謝 23x axx 所以 N（a）構成 G的子群精品資料證明： 設群 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是偶數階的 矛盾。所以，偶數階群 G必含 2 階元20. 設 G為非

40、 Abel 群，證明 G中存在非單位元 a 和 b,a b, 且 ab=ba.證明： 先證明 G含至少含 3 階元。若 G只含 1 階元 , 則 G=e,G 為 Abel 群矛盾；若 G除了 1 階元 e 外, 其余元 a 均為 2 階元，則 a 2 e， a 1 a, b G , a 1 a , b 1 b, (ab ) 1 ab , 所以 ab a 1b 1 (ba) 1與 G為 Abel 群矛盾；aba，所以， G含至少含一個 3 階元，設為 a ，則 a a 2 ，且 a2 a aa 2 。令b a 2 的證。21. 設 G是 Mn(R) 上的加法群， n2 ，判斷下述子集是否構成子群

41、。（ 1）全體對稱矩陣（2）全體對角矩陣（3）全體行列式大于等于是子群是子群0 的矩陣 . 不是子群（4）全體上（下）三角矩陣。 是子群22. 設 G為群， a 是 G中給定元素， a 的正規(guī)化子 N（a）表示 G中與 a可交換的元素構 成的集合，即N （a） =x xGxa=ax證明 N（a）構成 G的子群。證明： ea=ae, e N (a)x , y N ( a), 則 ax xa ,ay yaa( xy) (ax) y ( xa) y x(ay) x( ya ) ( xy)a , 所以 xy N (a)由 ax xa ，得 1 1 x 1 xax 1 , x 1ae eax 1 ，即

42、x 1a ax 1 ，所以 x 1 N (a)31. 設 1 是群 G1 到 G2 的同態(tài)， 2 是 G2 到 G3 的同態(tài)，證明 1 2 是 G1 到 G3 的同態(tài)。僅供學習與交流，如有侵權請聯(lián)系網站刪除 謝謝 241精品資料證明： 有已知 1 是 G1 到 G2 的函數， 2 是 G2 到 G3 的函數，則 1 2 是 G1 到 G3 的函數。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 是 G1 到 G3 的同態(tài)。33. 證明循環(huán)

43、群一定是阿貝爾群，說明阿貝爾群是否一定為循環(huán)群，并證明你的結論。證明： 設 G是循環(huán)群 , 令 G=,xy a k a l a k l a l k al ak 克萊因四元群 , G e, a , b , cx , y G , 令 x ak , y al , 那么yx,G 是阿貝爾群e a b ce e a b ca a e c bb b c e ac c b a e是交換群 , 但不是循環(huán)群 , 因為 e是一階元， a,b,c是二階元。36. 設 , 是 5 元置換，且12345，123452145334512(1) 計算 , , 1 , 1 , 1 ；(2) 將,1,1表示成不交的輪換之積。

44、(3) 將（ 2）中的置換表示成對換之積，并說明哪些為奇置換，哪些為偶置換。解： (1)1(2)(3)11 2 3 44 5 3 21 2 3 4 52 1 5 3 4(1425) 1(14)(12)(15)(14)(12)(15)(13)511(14253)1 24 31 25 41奇置換，偶置換3 4 51 2 53 4 51 3 2(143)( 25)11 2 3 4 54 5 1 2 3(14)(13)(25) 奇置換第十四章部分課后習題參考答案僅供學習與交流，如有侵權請聯(lián)系網站刪除 謝謝 25精品資料5、設無向圖 G有 10 條邊， 3 度與 4 度頂點各 2 個，其余頂點的度數均小

45、于 3，問 G至少有多少個頂點？在最少頂點的情況下，寫出度數列、 (G) 、 (G) 。解： 由握手定理圖 G的度數之和為： 2 10 203 度與 4 度頂點各 2 個，這 4 個頂點的度數之和為 14 度。其余頂點的度數共有 6 度。其余頂點的度數均小于 3，欲使 G的頂點最少，其余頂點的度數應都取 2,所以， G至少有 7 個頂點 , 出度數列為 3,3,4,4,2,2,2, (G) 4 , (G) 2 .7、設有向圖 D 的度數列為 2， 3， 2， 3，出度列為 1， 2， 1， 1，求 D 的入度列，并求 ( D ), ( D )，( D ), ( D ) , ( D ), ( D

46、 ) .解： D的度數列為 2， 3， 2， 3，出度列為 1， 2， 1， 1， D 的入度列為 1,1,1,2.( D ) 3 , ( D) 2 , ( D ) 2, ( D ) 1, ( D ) 2 , ( D ) 18、設無向圖中有 6 條邊， 3 度與 5 度頂點各 1 個，其余頂點都是 2 度點，問該圖有多少個頂點？解： 由握手定理圖 G的度數之和為： 2 6 12設 2 度點 x 個，則 3 1 5 1 2x 12， x 2 ，該圖有 4 個頂點 .14、下面給出的兩個正整數數列中哪個是可圖化的？對可圖化的數列，試給出 3 種非同構的無向圖，其中至少有兩個時簡單圖。(1) 2,2

47、,3,3,4,4,5 (2) 2,2,2,2,3,3,4,4解： (1) 2+2+3+3+4+4+5=23 是奇數，不可圖化；(2) 2 2+2+2+3+3+4+4=16, 是偶數，可圖化；18、設有 3 個 4 階 4 條邊的無向簡單圖 G1、 G2 、 G3，證明它們至少有兩個是同構的。僅供學習與交流，如有侵權請聯(lián)系網站刪除 謝謝 26m解：e4精品資料證明： 4 階 4 條邊的無向簡單圖的頂點的最大度數為列為 2， 2， 2， 2； 3， 2， 2， 1； 3， 3， 1， 1。但 3， 3，以從同構的觀點看， 4 階 4 條邊的無向簡單圖只有兩個：3，度數之和為 8，因而度數1， 1

48、對應的圖不是簡單圖。所所以， G1 、 G2、 G3 至少有兩個是同構的。20、已知 n 階無向簡單圖 G 有 m條邊，試求 G 的補圖 G 的邊數 m 。解： mn( n 1)221、無向圖 G 如下圖(1)求 G 的全部點割集與邊割集，指出其中的割點和橋；(2) 求 G 的點連通度 k (G) 與邊連通度 (G) 。a e1e2 db e5 ee3 c解： 點割集 : a,b,(d)邊割集 e2,e3,e3,e4,e1,e2,e1,e4e1,e3,e2,e4,e5k(G) = (G) =123、求 G 的點連通度 k(G) 、邊連通度 (G) 與最小度數 (G) 。解： k(G) 2 、

49、(G) 3 、 (G) 428、設 n 階無向簡單圖為 種非同構的情況？3n 2m2n 3 m3-正則圖，且邊數 m 與 n滿足 2n-3=m 問這樣的無向圖有幾得 n=6,m=9.僅供學習與交流，如有侵權請聯(lián)系網站刪除 謝謝 27232 3 4精品資料31、設圖 G 和它的部圖 G 的邊數分別為解： m m n(n 1) 得 n 145、有向圖 D 如圖m和 m ，試確定 G 的階數。1 8(m m)2(1)求 v2 到v5 長度為 1， 2， 3， 4 的通路數；(2)求 v5 到 v5 長度為 1， 2， 3， 4 的回路數；(3)求 D(4)求 D(5)寫出中長度為 4 的通路數；中長

50、度小于或等于 4 的回路數；D 的可達矩陣。v1v4v5v2解： 有向圖 D 的鄰接矩陣為：0 0 0 0 1 0A1000100001 ，2A001 0 1 0 0 00 1 0 1 0 20 0 0 0 41010000002v31 0 2 0 20 2 0 2 01 0 A 2 0 20 2 0 2 00 0 0 0 00 1 2 1 5020200000440400A4A000044 0 4 0 00 4 0 4 0(1) v2 到 v5 長度為 1， 2， 3，(2) v5 到 v5 長度為 1， 2， 3，A A A4 的通路數為4 的回路數為5 22 14 22 50,2,0,0

51、；0,0,4,0；5 2 22 1 55 2 22 5 4僅供學習與交流，如有侵權請聯(lián)系網站刪除 謝謝 2810；精品資料(3)D 中長度為 4 的通路數為 32；(4)D 中長度小于或等于(4)出 D 的可達矩陣 P4 的回路數1 1 1 11 1 1 11 1 1 11 1 1 11 1 1 111111第十六章部分課后習題參考答案1 、畫出所有 5 階和 7 階非同構的無向樹 .2 、一棵無向樹 T 有 5 片樹葉， 3 個 2 度分支點，其余的分支點都是 3 度頂點，問 T 有幾個頂點?解： 設 3 度分支點 x 個，則5 1 3 2 3x 2 (5 3 x 1) ，解得 x 3T 有 11 個頂點3 、無向樹 T 有 8 個樹葉， 2 個 3 度分支點，其余的分支點都是 4 度頂點，問 T 有幾個 4 度分支點？根據 T 的度數列，