離散數(shù)學(xué)(本科)(

1、離散數(shù)學(xué)復(fù)習(xí)資料2014 年12 月一、單項選擇題（每小題3 分，本題共15 分）1若集合A=1 ， 2， B=1， 2， 1， 2 ，則下列表述正確的是(A AB，且 ABBBA，且 ABCAB，且AA)BDAB，且AB2設(shè)有向圖（a）、（b）、（ c）與（d）如圖一所示，則下列結(jié)論成立的是(D)圖一A （ a）是強(qiáng)連通的B （b）是強(qiáng)連通的C（c）是強(qiáng)連通的D （ d）是強(qiáng)連通的3設(shè)圖 G 的鄰接矩陣為0110010011100000100101010則G的邊數(shù)為(B)A 6B 5C 4D 34無向簡單圖 G 是棵樹，當(dāng)且僅當(dāng) (A)A G 連通且邊數(shù)比結(jié)點數(shù)少1B G 連通且結(jié)點數(shù)比邊數(shù)

2、少1C G 的邊數(shù)比結(jié)點數(shù)少 1D G 中沒有回路5下列公式(C)為重言式A PQPQB(Q (PQ)( Q(PQ)C (P(QP) (P(PQ)D( P (PQ)Q6設(shè) A= a, b，B=1, 2 ，R1，R2，R3 是 A 到 B 的二元關(guān)系，且R1=< a，2>, <b，2> ，R2=< a， 1>, <a， 2>, <b， 1> ， R3=< a， 1>, <b， 2> ，則（B）不是從 A 到 B 的函數(shù)AR1和 R2B R2C R3DR1和 R37設(shè) A=1, 2, 3, 4, 5, 6, 7,

3、8 ， R 是 A 上的整除關(guān)系， B=2, 4, 6 ，則集合 B 的最大元、最小元、上界、下界依次為( B)A8、2、8、2B 無、 2、無、 2C6、 2、 6、2D8、 1、6、18若集合 A 的元素個數(shù)為10，則其冪集的元素個數(shù)為（A）A 1024B 10C100D 19設(shè)完全圖 K n 有 n 個結(jié)點 (n2)， m 條邊，當(dāng)（C）時， K n 中存在歐拉回路A m 為奇數(shù)B n 為偶數(shù)C n 為奇數(shù)D m 為偶數(shù)10已知圖G 的鄰接矩陣為，則G有（ D）A5點，8邊B6點，7邊C6點，8邊D5點，7邊11.無向完全圖K3 的不同構(gòu)的生成子圖的個數(shù)為（C）(A) 6(B) 5(C)

4、 4(D) 312 n 階無向完全圖 Kn 中的邊數(shù)為（A ）n(n1)n(n1)(C) n(D) n(n+1)(A)(B)2213.在圖 G <V ,E>中，結(jié)點總度數(shù)與邊數(shù)的關(guān)系是(C)Adeg(vi)=2E(B) deg( vi )=ECdeg(v)2 EDdeg(v)Ev Vv V二、填空題（每小題3 分，本題共 15 分）1命題公式 P(QP) 的真值是12 若 A=1,2 ， R=< x, y>|xA, yA, x+y<4 ，則 R 的自反閉包為<1,1>,<2,2>,<1,2>,<2,1>3已知一棵無向

5、樹 T 中有 8 個結(jié)點， 4 度， 3 度， 2 度的分支點各一個，T 的樹葉數(shù)為54 ( x)( P( x)Q(x) R(x， y)中的自由變元為R(x，y )中的 y5設(shè)集合 A a， b ，那么集合 A 的冪集是,a,b, a, b 6如果 R1 和 R2 是 A 上的自反關(guān)系， 則 R1 R2，R1 R2，R1- R2 中自反關(guān)系有2個7設(shè)圖 G 是有 6 個結(jié)點的連通圖，結(jié)點的總度數(shù)為18，則可從 G 中刪去4條邊后使之變成樹8無向圖 G 存在歐拉回路，當(dāng)且僅當(dāng)G 所有結(jié)點的度數(shù)全為偶數(shù)且連通9設(shè)連通平面圖 G 的結(jié)點數(shù)為5，邊數(shù)為6，則面數(shù)為310設(shè)個體域D a, b ，則謂詞公

6、式 (x) A(x)（ x） B（ x）消去量詞后的等值式為(A (a)A (b)( B（ a） B（ b） )三、邏輯公式翻譯 （每小題6 分，本題共12 分）1將語句“雪是黑色的”翻譯成命題公式設(shè) P：雪是黑色的，（ 2 分）則命題公式為：P2將語句“他不去學(xué)?！狈g成命題公式解：設(shè) P：他去學(xué)校，則命題公式為：P3將語句 “小王是個學(xué)生，小李是個職員，而小張是個軍人”翻譯成命題公式設(shè) P：小王是個學(xué)生，Q：小李是個職員，R：小張是個軍人（ 2 分）則命題公式為：P Q R4將語句“如果所有人今天都去參加活動，則明天的會議取消”翻譯成命題公式解：設(shè) P：所有人今天都去參加活動，Q：明天的會

7、議取消，則命題公式為：PQ5將語句“他去旅游，僅當(dāng)他有時間”翻譯成命題公式解：設(shè) P：他去旅游，Q：他有時間，則命題公式為： PQ6將語句“ 41 次列車下午五點開或者六點開”翻譯成命題公式解：設(shè) P： 41 次列車下午五點開， Q： 41 次列車下午六點開，（2 分）命題公式為：（ P Q）（ P Q）7將語句“小張學(xué)習(xí)努力，小王取得好成績”翻譯成命題設(shè) P：小張學(xué)習(xí)努力， Q：小王取得好成績，（2 分）則命題公式為： PQ8將語句“有人去上課” 翻譯成謂詞公式解：設(shè) P(x)： x 是人， Q( x)：x 去上課，（1 分）(x)(P(x)Q(x)9將語句“所有的人都學(xué)習(xí)努力”翻譯成命題公

8、式解：設(shè) P(x)： x 是人， Q( x)：x 學(xué)習(xí)努力，x） (P(x)Q(x)四、判斷說明題 （每小題7 分，本題共14 分） 判斷下列各題正誤，并說明理由1設(shè)集合 A=1, 2, 3, 4 ，B=2, 4, 6, 8 ，判斷下列關(guān)系 f 是否構(gòu)成函數(shù) f： A B ，并說明理由(1) f=<1, 4>, <2, 2,>, <4, 6>, <1, 8> ；(2)f=<1, 6>, <3, 4>, <2, 2> ；(3) f=<1, 8>, <2, 6>, <3, 4>,

9、 <4, 2,>答：（ 1）不構(gòu)成函數(shù)因為 3A，但 f3 沒有定義，所以不構(gòu)成函數(shù)（ 2）不構(gòu)成函數(shù)因為 4A ，但 f4 沒有定義，所以不構(gòu)成函數(shù)（3）滿足。因為任意 x A，都有 f xB 且結(jié)果唯一。2若集合 A = 1 ， 2， 3上的二元關(guān)系 R=<1, 1> ，<2, 2> ， <1, 2> ，則(1) R 是自反的關(guān)系；(2) R 是對稱的關(guān)系答：（ 1）錯誤因為 3，3R ，所以 R 不是自反的（ 2）錯誤因為1，2R ，但是2，1R ，所以 R 不是對稱的3如果 R1和 R2是 A 上的自反關(guān)系，判斷結(jié)論： “ R-1 、R

10、R、 R 是自反的”是1121 R2否成立？并說明理由答：成立因為任意 aA ，有 a, aR1 , a, aR2所以 a, a R 1， a, aR1R2 ， a, aR1R2R11、 R1 R2、R1R2 是自反的-a4若偏序集 <A，R>的哈斯圖如圖一所示，bcg則集合 A 的最大元為 a，最小元不存在答：錯誤，集合A 沒有最大元，也沒有最小元其中 a 是極大元dhef圖一5若偏序集 <A， R>的哈斯圖如圖一所示，則集合A 的最大元為a，最小元不存在解：正確對于集合 A 的任意元素x，均有 <x, a>R（或 xRa），所以 a 是集合 A 中的最大

11、元按照最小元的定義，在集合A 中不存在最小元6如果圖G 是無向圖，且其結(jié)點度數(shù)均為偶數(shù)，則圖G 存在一條歐拉回路 答：錯誤如果圖 G 是無向圖，且圖G 是連通的，同時結(jié)點度數(shù)都是偶數(shù)7設(shè) G 是一個連通平面圖，且有6 個結(jié)點 11 條邊，則G 有 7 個面答案：正確定理，連通平面圖 G 的結(jié)點數(shù)為 v，邊數(shù)是 e，面數(shù)為 r，則歐拉公式 v-e+r=2 成立所以 r=2-v+e=2-6+11=7則 G 存在一條歐拉回路8設(shè) G 是一個有6 個結(jié)點 14 條邊的連通圖，則G 為平面圖解：錯誤，不滿足“設(shè) G 是一個有v 個結(jié)點 e 條邊的連通簡單平面圖，若 v 3，則 e 3v-6”9命題公式P

12、 (PQ)P 為永真式解：正確因為，由真值表PQPQPQP (P Q)P001111011011100111110001可知，該命題公式為永真式五計算題 （每小題 12 分，本題共36 分）1設(shè)集合A=a, b, c， B= a, c，試計算（ 1）（ AB）；（ 2）（ BA）；解（ 1）（ AB）= c ；（ 3）（ AB） ×B（ 2）（ B A） = a ；（ 3）（AB） ×B= < c， a>, < c，c >2設(shè) A=0 ， 1， 2， 3，4，5，6， R=< x， y>|xA，y A 且 x+y<1 ， S=<

13、; x， y>|xA， y A且 x+y 3，試求 R， S， R S， R-1 ， S-1， r(R)解： R=<0,0>S=<0,0>,<0,1>,<0,2>,<0,3>,<1,0>,<1,1>,<1,2>,<2,0>,<2,1>,<3,0>RS=<0,0>,<0,1>,<0,2>,<0,3>R-1=<0,0>-1）S = Sr(R)=I A3圖 G=<V , E>，其中 V= a,

14、 b, c, d, e，E = ( a, b), (a, c), (a, e), ( b, d), (b, e), (c, e), ( c, d), (d,e) ，對應(yīng)邊的權(quán)值依次為 2、 1、 2、 3、 6、 1、 4 及 5，試（ 1）畫出 G 的圖形；（ 2）寫出 G 的鄰接矩陣；（ 3）求出 G 權(quán)最小的生成樹及其權(quán)值解：（ 1）G 的圖形表示為：（3 分）（ 2）鄰接矩陣：011011001110011（6分）0110111110（ 3）粗線表示最小的生成樹，權(quán)為 7：4設(shè)圖 G=<V， E >， V= v1， v2， v3， v4， v5 ， E= ( v1 , v2

15、)， (v1, v3 )， (v2, v3)， ( v2 , v4)， (v3, v4)， (v3, v5)， (v4, v5) ，試(1) 畫出 G 的圖形表示；(2) 求出每個結(jié)點的度數(shù)；(3) 畫出圖 G 的補(bǔ)圖的圖形解：（ 1）關(guān)系圖v1v2v5v3v4（2） deg(v1)=2deg(v2)=3deg(v3 )=4deg( v4)=3deg(v5 )=2（ 3）補(bǔ)圖v1v2v5v3v45設(shè)集合A=1 ， 2， 3， 4， R=<x, y>|x, y A； |xy|=1 或 xy=0 ，試（ 1）寫出 R 的有序?qū)Ρ硎?；?2）畫出 R 的關(guān)系圖；（ 3）說明 R 滿足自反

16、性，不滿足傳遞性解 :（ 1）R=<1,1>,<2,2>,<3,3>,<4,4>,<1,2>,<2,1>,<2,3>,<3,2>,<3,4>,<4,3>（3 分）（ 2）關(guān)系圖為2134（ 3）因為 <1,1>,<2,2>,<3,3>,<4,4> 均屬于 R，即 A 的每個元素構(gòu)成的有序?qū)赗 中，故 R 在 A 上是自反的。因有 <2,3> 與 <3,4>屬于 R，但 <2,4> 不屬于

17、R，所以 R 在 A 上不是傳遞的。6設(shè)集合A=1, 2, 3 ， R=<1 ， 1>, <2， 1>,<3 ， 1> ， S=<1 ， 2>, <2 ， 2>試計算（1） R S；（2）R 1；（ 3） r（ R）解： （ 1）RS =<1 ，2>, <2 ， 2>,<3 ， 2> ；（4 分）（2） R1=<1 ， 1>, <1， 2>, <1， 3> ；（8 分）（ 3） r （R） =<1 ， 1>, <2， 2> , <3，

18、 3>, <2， 1>,<3 ， 1>7、求出如圖一所示賦權(quán)圖中的最小生成樹（要求寫出求解步驟），并求此最小生成樹的權(quán)解 用 Kruskal 算法求產(chǎn)生的最小生成樹步驟為：w(v1 , v7 )1選 e1v1v7w(v3 , v4 ) 3選 e2v3v4w(v2 , v7 ) 4選 e3v2v7w(v3 , v7 ) 9選 e4v3v7w(v4 , v5 ) 18選 e5v4 v5w(v1 , v6 ) 22選 e6v1v6最小生成樹如圖四所示：圖四最小生成樹的權(quán)為：w(T)=22+1+4+9+3+18=57 8試畫一棵帶權(quán)為 2, 3, 3, 4, 5,的最優(yōu)二

19、叉樹 , 并計算該最優(yōu)二叉樹的權(quán)解：最優(yōu)二叉樹 如圖二所示171075534（6 分）（ 9 分）（ 12 分）（10分）圖二權(quán)為23+33+32+42+52=399設(shè)謂詞公式x( A( x, y)zB( x, y, z)yC( y, z) ，試（ 1）寫出量詞的轄域；（ 2）指出該公式的自由變元和約束變元（ 1）x 量詞的轄域為 ( A( x, y)zB( x, y, z) ，（2 分）z 量詞的轄域為 B( x, y, z) ,（4 分）y 量詞的轄域為 C ( y, z) （6 分）（ 2）自由變元為 (A(x, y)zB( x, y, z) 中的 y，以及 C ( y, z) 中的 z（9 分）約束變元為 ( A(x, y)zB( x, y, z) 中的 x 與 B( x, y, z) 中的 z，以及 C ( y, z) 中的 y10設(shè)謂詞公式 ( x)P( x, y)(z)Q ( x, y, z) ，試（ 1）寫出量詞的轄域；（ 2）指出該公式的自由變元和約束變元（ 1）x 量詞的轄域為 P( x, y) ，（3分）z 量詞的轄域為 Q ( x, y, z) ,（6 分）（2）自由變元為公式中的y 與 Q( x, y, z) 中的 x，（9 分）約束變元為P( x, y) 的 x 與 Q( x, y, z) z11求命題公式(PQ)(RQ)