2018年春季學(xué)期離散數(shù)學(xué)期末深刻復(fù)知識題

1、2018年春季學(xué)期離散數(shù)學(xué)期末復(fù)習(xí)題第一章集合論、判斷題 TOC o 1-5 h z （1）空集是任何集合的真子集.（錯）是空集.（錯 ）a a, a（對）（4）設(shè)集合 A 1,2, 1, 2，則 1, 22a.（對）（5）如果a A B,則aA或a B.（錯）解a A B則a ABA B,即a入且a B,所以a A且aB（6）如果 AU B B,則 A B.（對）（7）設(shè)集合A3電自, B 6也白,則A B a1，b1 , a2,b2 , a3,b3 （錯）（8）設(shè)集合 A 0,1,則 ,0 ,1 , 0, 0 , 0,1 是 2A到 A的關(guān)系.（對）一 A解 2 ,0,1, A，A2 A

2、,0 ,1 , 0,0 , 0,1 , 1,0 , 1,1 , A,0 , A,1 TOC o 1-5 h z （9）關(guān)系的復(fù)合運算滿足交換律.（錯 ）（10）是集合A上的關(guān)系具有傳遞性的充分必要 條件.（錯 ）（11）設(shè) 是集合A上的傳遞關(guān)系，則也是A上的傳遞關(guān)系.（對）（12 ）集合A上的對稱關(guān)系必不是反對稱的.（錯）（13）設(shè)1, 2為集合A上的等價關(guān)系，則12也是集合A上的等價關(guān)系（對）（14）設(shè) 是集合A上的等價關(guān)系，則當(dāng) a,b 時，ab（對 ）(15 )設(shè)2為集合A上的等價關(guān)系，則二、單項選擇題(1)設(shè)R為實數(shù)集合，下列集合中哪一個不是空集2A. x| x 1 0,且x R2B.

3、 x | x 9 0,且xC. x| x x 1,且xR2D. x | x1,且 x R(2)設(shè)A, B為集合，若AA. BB. BC. AD.(3)下列各式中不正確的是A.B.C.D.，( )(4)設(shè)a,a,則下列各式中錯誤的是A. a2AB.C.a2AD. a2Aa, b,cc, dA (BC)為A.c,1 ,2,cB.1,c2,cC.1,c ,c,2D.c,1 , c,2A.C.A.B.C.D.1,b,3B的恒等關(guān)系為0,0 , 1,10,0 , b,ba, b,a,ca,ca,ba,a,b,b , 3,3B.0,0 , 1,1,3,33,3上的二元關(guān)系如下,c,a , a,b ,c,

4、ac, c , b, a ,D. 0,1 , 1,b則具有傳遞性的為b,ab,c,b,3 ,3,0(8)設(shè) 為集合A上的等價關(guān)系，對任意 a A,其等價類a為 (B )A.空集；B.非空集；C.是否為空集不能確定；D. x|x A.(9)映射的復(fù)合運算滿足(B )A.交換律B.結(jié)合律C.哥等律D.分配律(10)設(shè)A, B是集合，則下列說法中( C )是正確的.A至ij B的關(guān)系都是 A至ij B的映射A到B的映射都是可逆的A到B的雙射都是可逆的AB時必不存在 A到B的雙射(11 )設(shè)A是集合，則(B )成立.#2a 2#aAX2AX A2AAD . A 2(12)設(shè)A是有限集(#A n),則A

5、上既是 又是的關(guān)系共有( B).0個1個2個n個三、填空題.設(shè) A 1, 2,1,2,則 2A .填 2A ,1,2,1,2, 1,2,1,1,2, 2,1,2, A.設(shè) A ,則 2A=.填 2A , , , A.設(shè)集合A, B中元素的個數(shù)分別為 #A 5, #B 7,且#5 B) 9,則集合A B中元素的個數(shù)#(A B) .3.設(shè)集合A x|1 x 100,x是4的倍數(shù)，x Z,B x|1 x 100,x是5的倍數(shù),x Z,則A B中元素的個數(shù)為.40A.設(shè) A a,b, 是2 上的包含于關(guān)系，則有=.,a ,b , ,A , a, a , a, A , b, b , b, A , A,

6、A .設(shè)1, 2為集合 A上的二元關(guān)系，則1.集合A上的二元關(guān)系為傳遞的充分必要條件是 .設(shè)集合A 0,1, 2上的關(guān)系i 0, 2 , 2, 0 及集合A到集合B 0,2,4的關(guān)系 2 a,b | a,b A B 且 a, b AnB,則 12填 0,0 , 0,2 , 2,0 , 2,2 )四、解答題1.設(shè)集合 A ,1, 2, B 1,2 ,B_ A 2B求(1) AU 2 ; (2) 2B解(1) AU 2, 1, 2, U , 1 , 2 , B,1,2, 1 , 2, B.(2) A 2B 匕所以 2A 2B2 , a,b , b,a , c,d , d,c 2.設(shè)A a,b, c

7、, d, A上的關(guān)系 a,a , b,b , c,c , d,d(1)寫出的關(guān)系矩陣；(2)驗證是A上的等價關(guān)系；(3)求出A的各元素的等價類。解(1)的關(guān)系矩陣為110 0110 0 M0 0 110 0 11(2)從 的關(guān)系矩陣可知：是自反的和對稱的。又由于110 0110 00 0 110 0 11110 0110 00 0 110 0 11110 0110 0 M0 0 110 0 11或滿足 所以是傳遞的。因為是自反的、對稱的和傳遞的，所以是A上的等價關(guān)系。(3) a b a,b, c d c,d3.設(shè)集合A 1,2,3,5 ,6,15,30, 是A上的整除關(guān)系，寫出的關(guān)系矩陣M畫出

8、偏序集A,的哈斯圖;(3)求出A的子集B 3,6,15的最小上界和最大下界;(4)判斷其是否為格。1111111 TOC o 1-5 h z 0100101解：(1) M001011100010 1100001 01(3) lubB=30, glbB=3五、證明題1.設(shè)1, 2為集合A上的等價關(guān)系，試證12也是集合A上的等價關(guān)系。證明：由于1, 2是自反的，所以對任意a A, a, aa, a2 ,因而a, a i 2,即 i 2是自反的。若 a,b i 2,則 a,b i, a,b 2,由于i, 2是對稱的，所以 b, a i, b, a 2,從而 b, a i 2,即i 2是對稱的。若a,

9、b , b, c i 2,則a,b , b,c i, a,b , b,c 2 ,由于 i, 2是傳遞的，所以a,c i, a,c 2,從而 a,c i 2,即 i2是傳遞的。由于i2是自反的、對稱的和傳遞的，所以 i 2是等價關(guān)系。第二章代數(shù)系統(tǒng)一、判斷題 TOC o 1-5 h z （i ）集合A上的任一運算對 A是封閉的.（對 ）（2）代數(shù)系統(tǒng)的零元是可逆元.（錯）（3）設(shè)A是集合，：A A A, a b b,則 是可結(jié)合的. （對 ）（4）設(shè)a, b是代數(shù)系統(tǒng) A,的元素，如果abba e（e是該代數(shù)系統(tǒng)的單位元），則ab.（對 ）設(shè)a, b是群G,的元素，則（a b） i a i b

10、i.（錯）2. 2（6）設(shè) G,是群.如果對于任意 a,b G,有（a b） a b ,則 G,是阿貝爾群.（對）（7）設(shè)L,是格,則運算滿足曷等律.（對 ）（8）設(shè)集合 A a,b,則 ,a,b, A, 是格.（對 ）（ii ） 是格.（對 ）（9）設(shè) B,是布爾代數(shù)，則 B, 是格.（對 ）（10）設(shè) B,是布爾代數(shù)，則對任意a,b B,有、單項選擇題 TOC o 1-5 h z （1）在整數(shù)集Z上，下列哪種運算是可結(jié)合的（B ）A. a b a bB.ab maxa, bC. a b a 2bD. a b | a b |（2）下列定義的實數(shù)集 R上的運算*中可結(jié)合的是.（C ）a b a

11、 a baba2ababbabab其中，+, I I分別為實數(shù)的加法、乘法和取絕對值運算.（3）設(shè)集合A 1,2, 3,4,10 ,下面定義的哪種運算關(guān)于集合A不是封閉的xymax x, yxymin x, yxyGCDx, y,即x,y的最大公約數(shù)xyLCMx, y,即x,y的最小公倍數(shù) TOC o 1-5 h z （4）下列哪個集關(guān)于減法運算是封閉的（B ）A. N （自然數(shù)集）；B. 2x|x Z（整數(shù)集）;C. 2x 1| x Z ;D. x|x是質(zhì)數(shù).設(shè)Q是有理數(shù)集，在 Q定義運算為a b a b ab ,則（Q,，的單位元為（D ）A. a ；B. b；C. 1 ;D. 0（6）設(shè)

12、代數(shù)系統(tǒng) A, ,則下面結(jié)論成立的是.（C ）A.如果A, 是群，則 A, 是阿貝爾群B.如果 A, ,是阿貝爾群，則 A, ,是循環(huán)群C.如果A, 是循環(huán)群，則 A, 是阿貝爾群D.如果 A, 是阿貝爾群，則 A, 必不是循環(huán)群(7)循環(huán)群(Z,)的所有生成元為(D )A. 1,0B, -1 , 2C, 1,2D. 1 , -1三、填空題AA.設(shè)A為非空有限集，代數(shù)系統(tǒng)2 , 中，2對運算的單位元為 ,零元為.填，A.代數(shù)系統(tǒng)Z, 中(其中 Z為整數(shù)集合，+為普通加法)，對任意的 x I,其x 1 .填 x.在整數(shù)集合Z上定義 運算為a b a 2b,則Z, 的單位元為.解設(shè)單位元為e, a

13、 e a 2 e a ,所以e 2,又 a ( 2) a 2 ( 2) a, (2) a (2)2 aa,所以單位元為e 2.在整數(shù)集合Z上定義運算為a b a b ab,則 Z,的單位元為 .解設(shè)單位元為e, a e a e ae a, (1 a)e 0,所以e 0.設(shè)(G,)是群，對任意a,b,c G ,如果a b a c,則.填b c.設(shè)(G,)是群，e為單位元，若 G元素a滿足a2 a,則a .填e 四、解答題.設(shè) 為實數(shù)集R上的二元運算，其定義為a, b2:R R, a b a b 2ab求運算的單位元和零元。2ae解：設(shè)單位元為e,則對任意a R,不0,即e(1 2a) 0 ,由a

14、的任意性知 e又對任意a R, a 0 a 0 0 a所以單位元為02a設(shè)零元為，則對任意a R,有a即 a(1 2 ) 0 ,由a的任意性知、1又對任息a R, a ( -) a - a2所以零元為2.設(shè) 為集合I5 0,1,2,3,4上的二元運算，其定義為1 2:I5 I5, a b (ab)mod5 ,對于任意 a,b I5寫出運算的運算表;說明運算 是否滿足交換律、結(jié)合律，是否有單位元和零元、如果有請指出;(3)寫出所有可逆元的逆元解：(1 )運算表為01234000000101234202413303142404321(2)運算滿足交換律、結(jié)合律，有單位元，單位元為1 ,有零元，零元

15、為0;1的逆元為 1, 2的逆元為 3, 3的逆元為2, 4的逆元 4, 0沒有逆元五、證明題.設(shè) G,是一個群，試證 G是交換群 當(dāng)且僅當(dāng)對任意的a, b G ,有22a b (a b).證明：充分性若在群 G,中，對任意的a, b G，有a2 b2 (a b)2 .則(a a) (b b) (a b) (a b)a (a b) b a (b a) b abba 從而 G,是一個交換群。必要性若 G,是一個交換群，對任意的a, b G ,有a b b a,則a (a b) b a (b a) b(a a) (b b) (a b) (a b) TOC o 1-5 h z -222即 a b (

16、a b).2.證明代數(shù)系統(tǒng)Z, 是群，其中二元運算定義如下:r 2rc：Z Z , x y x y 3(這里，+,分別是整數(shù)的加法與減法運算.)證明(1)運算滿足交換律對任意x, y, z 乙由(x y) z(x y3) zxyz6,x (y z)x (yz 3)xyz6得(x y) z x (y z),即滿足結(jié)合律；(2)有單位元 3是單位元；(3)任意元素有逆元對任意x Z, x 16 x.所以，Z, 是群.第三章圖論一、判斷題 TOC o 1-5 h z (1) n階完全圖的任意兩個不同結(jié)點的距離都為1.(對)(2)圖G的兩個不同結(jié)點Vi,Vj連接時一定鄰接.(錯)(3)圖G中連接結(jié)點V

17、i,Vj的初級通路為Vi,Vj之間的短程.(錯)(4)在有向圖中，結(jié)點 Vi到結(jié)點Vj的有向短程即為Vj到Vi的有向短程.( 錯)(5)強連通有向圖一定是單向連通的.( 對 )(6)不論無向圖或有向圖，初級回路一定是簡單回路.(對 )(7)設(shè)圖G是連通的，則任意指定 G的各邊方向后所得的有向圖是弱連通的.(對 )(8)設(shè)A是某個無向圖的鄰接矩陣，則 A AT (AT是A的轉(zhuǎn)置矩陣).(9)設(shè)有向圖D的可達矩陣為則G是單向連通的.(對)(10)有生成樹的無向圖是連通的.(13 )下圖中為歐拉圖的是( CA.B.C.D.二、單項選擇題(1)僅由孤立點組成的圖稱為A.零圖;B.平凡圖;C.完全圖;D

18、.多重圖.(2)僅由一個孤立點組成的圖稱為A.零圖;B.平凡圖；C.多重圖；D.子圖.(3)在任何圖G中必有偶數(shù)個A.度數(shù)為偶數(shù)的結(jié)點;C.入度為奇數(shù)的結(jié)點;B.度數(shù)為奇數(shù)的結(jié)點;D.出度為奇數(shù)的結(jié)點(4)設(shè)G為有n個結(jié)點的無向完全圖，則 G的邊數(shù)為A. n(n 1)B. n(n 1) C. n(n 1)/2D. (n 1)/2(5)在有n個結(jié)點的連通圖 G中，其邊數(shù)A.最多n 1條;B.至少n 1條;C.最多n條;C.既是偏序關(guān)系又是等價關(guān)系;D.既不是偏序關(guān)系也不是等價關(guān)系D.至少n條.(6)任何無向圖G中結(jié)點間的連通關(guān)系是B.等價關(guān)系;A.偏序關(guān)系;(7)對于無向圖，下列說法中正確的是.

19、(B )A.不含平行邊及環(huán)的圖稱為完全圖B.任何兩個不同結(jié)點都有邊相連且無平行邊及環(huán)的圖稱為完全圖C.具有經(jīng)過每條邊一次且僅一次回路的圖稱為哈密爾頓圖D.具有經(jīng)過每個結(jié)點一次且僅一次回路的圖稱為歐拉圖(8)設(shè)D是有向圖，則 D強連通的充分必要條件為.(C )A.略去D中各邊方向后所得到的無向圖是連通的D是單向連通圖，且改變它的各邊方向后所得到的有向圖也是單向連通圖D的任意兩個不同的結(jié)點都可以相互到達D是完全圖(9)對于無向圖 G,以下結(jié)論中不正確的是 .(A )A.如果G的兩個不同結(jié)點是連接的，則這兩個結(jié)點之間有初級回路B.如果G的兩個不同結(jié)點是連接的，則這兩個結(jié)點之間至少有一條短程C.如果G

20、是樹，則任何兩個不同結(jié)點之間有且僅有一條初級通路D.如果G是歐拉圖，則G有歐拉回路(10)設(shè)簡單無向圖G的鄰接矩陣為A (aj)nn，記Al (ai(l)nn(l 1,2,)，則正確的是.(C )A.當(dāng)M,Vj是G的兩個不同結(jié)點時，a;為Vi,Vj之間長度為l的初級通路條數(shù)B.當(dāng)M,Vj是G的兩個不同結(jié)點時，a為w,Vj之間長度為l的簡單通路條數(shù)C.當(dāng)Vi,Vj是G的兩個不同結(jié)點時，a;為Vi,Vj之間長度為l的的通路條數(shù)D.當(dāng)V是G的結(jié)點時，a)為通過Vi的長度為l的初級回路條數(shù)M mijnm是無向圖G V, E 的關(guān)聯(lián)矩陣，Vi V是G中的孤立點，則(A )A.Vi對應(yīng)的一行元素全為0;B

21、 .Vi對應(yīng)的一行元素全為1;C.Vi對應(yīng)的一列元素全為0;D.Vi對應(yīng)的一列元素全為1.三、填空題.設(shè)樹T中有7片樹葉，3個3度結(jié)點，其余都是 4度結(jié)點，則T中有 個4度結(jié)點.解 用握手定理和樹的性質(zhì)列出方程求解，設(shè)有X個4度結(jié)點，7 9 4x 2(7 3 x 1) , X 1.設(shè)T V, E 為樹，T中有4度，3度，2度分支點各1個，問T中有一片樹葉。解與上題解法相同，設(shè)有 x片樹葉，4 3 2 x 2(3 x 1) , x 5.n階完全圖的任意兩個不同結(jié)點的距離都為 . 1.圖G為n階無向完全圖，則 G共有 條邊。n(n 1)/2.設(shè)G為(n,m)圖，則圖中結(jié)點度數(shù)的總和為 。 2m.設(shè)

22、圖G有6結(jié)點，若各結(jié)點的度數(shù)分別為：1, 4, 4, 3, 5, 5,則G共有 條邊。用握手定理 22 2m, m=11.圖G為歐拉圖的充分必要條件是 .曲無奇度結(jié)點的連通圖 四、解答題1.對下圖所示的圖G,求(1 ) G的鄰接矩陣A;G的結(jié)點VV3之間長度為3的通路;G的連接矩陣C ；G的關(guān)聯(lián)矩陣M 。解(1)V1V2V3V4V5V101110A= V210101V311011V410100V5011007A3 =(2)因為3 12 121 3 2 2 1A2= 2 2 4 1 112 12 12 1112所以，結(jié)點V1,V3之間長度為3的通路共有7條，它們是V1V3V1V3 ,%V2 V5

23、 V3,V1V2V1V3,V1V4V1V3, V1 v3 V5 V3,V1V3V2V3, V1V3V4V3.(3)由于圖G是連通的，所以V1 V2 V3 V4 V5 TOC o 1-5 h z V111111V211111C=v311111V411111(4)V511111ee263V1101v2110M=v3011v4000v500010 0000010110110000112.在下面的有向圖 D中，回答下列問題(1)寫出圖D的鄰接矩陣A;(2)寫出結(jié)點v1到結(jié)點v3的長度為3的所有有向通路;(3)寫出結(jié)點v5到自身的長度為3的所有有向回路；解：(1) A0 0 0 0 110 10 00

24、0 1100 0 0 0 10 10 10(2) A20 10 100 0 1110 0 1110 10 1010 10 110 1010 1121A30 112110 1010 1121所以結(jié)點v1到結(jié)點v3的長度為3的所有有向通路只有一條：v1v5V2V3(3)結(jié)點v5到自身的長度為3的所有有向回路只有一條：v5V25丫53.在下面的無向圖bC: c(1)寫出a,d之間的所有初級通路；(2)寫出a,d之間的所有短程，并求 d(a,d)；(3)判斷無向圖G是否為歐拉圖并說明理由。解(1) a,d之間的所有初級通路共有 7條，分別為aed, aecd, aebcd, abed, abcd, abecd, abced(2) a, d之間的長度最短的通路只有1條，即aed,因而它是a,d之間唯一的短程，d(a,d) 2(3)由于無向圖 G中有兩個奇度頂點 deg(b) 3,deg(c) 3,所以無向圖 G沒有 歐拉回路，因而不是歐拉圖。第四章數(shù)理邏輯一、判斷題 TOC o 1-5 h