離散數(shù)學本科

1、離散數(shù)學復習資料 2014年12月一、單項選擇題（每小題3分，本題共15分）1若集合A=1，2，B=1，2，1，2，則下列表述正確的是( A ) A AÌB，且AÎB BBÌA，且AÎB CAÌB，且AÏB DAËB，且AÎB 2設有向圖（a）、（b）、（c）與（d）如圖一所示，則下列結論成立的是 ( D ) 圖一 A（a）是強連通的 B（b）是強連通的C（c）是強連通的 D（d）是強連通的3設圖G的鄰接矩陣為則G的邊數(shù)為( B )A6 B5 C4 D34無向簡單圖G是棵樹，當且僅當( A )AG連通且邊數(shù)比結點數(shù)

2、少1 BG連通且結點數(shù)比邊數(shù)少1CG的邊數(shù)比結點數(shù)少1 DG中沒有回路5下列公式 ( C )為重言式AØPÙØQ«PÚQ B(Q®(PÚQ) «(ØQÙ(PÚQ)C(P®(ØQ®P)«(ØP®(P®Q) D(ØPÚ(PÙQ) «Q6設A=a, b，B=1, 2，R1，R2，R3是A到B的二元關系，且R1=<a，2>, <b，2>，R2=<a，1&g

3、t;, <a，2>, <b，1>，R3=<a，1>, <b，2>，則（ B ）不是從A到B的函數(shù)AR1和R2 BR2 CR3 DR1和R37設A=1, 2, 3, 4, 5, 6, 7, 8，R是A上的整除關系，B=2, 4, 6，則集合B的最大元、最小元、上界、下界依次為 ( B ) A8、2、8、2 B無、2、無、2 C6、2、6、2 D8、1、6、18若集合A的元素個數(shù)為10，則其冪集的元素個數(shù)為（ A ） A1024 B10 C100 D19設完全圖K有n個結點(n2)，m條邊，當（ C ）時，K中存在歐拉回路Am為奇數(shù) Bn為偶數(shù) Cn

4、為奇數(shù) Dm為偶數(shù)10已知圖G的鄰接矩陣為 ，則G有（ D ） A5點，8邊 B6點，7邊 C6點，8邊 D5點，7邊11.無向完全圖K3的不同構的生成子圖的個數(shù)為（ C ）(A) 6 (B) 5 (C) 4 (D) 312 n階無向完全圖Kn中的邊數(shù)為（ A ）(A) (B) (C) n (D)n(n+1) 13.在圖G<V,E>中，結點總度數(shù)與邊數(shù)的關系是( C )A deg(vi)=2½E½ (B) deg(vi)=½E½ C D二、填空題（每小題3分，本題共15分）1命題公式的真值是 1 2若A=1,2，R=<x, y>|

5、xÎA, yÎA, x+y<4，則R的自反閉包為 <1,1>,<2,2>,<1,2>,<2,1> 3已知一棵無向樹T中有8個結點，4度，3度，2度的分支點各一個，T的樹葉數(shù)為 5 4("x)(P(x)Q(x)R(x，y)中的自由變元為 R(x，y )中的y 5設集合Aa，b，那么集合A的冪集是 Æ,a,b,a,b 6如果R1和R2是A上的自反關系，則R1R2，R1R2，R1-R2中自反關系有 2 個 7設圖G是有6個結點的連通圖，結點的總度數(shù)為18，則可從G中刪去 4 條邊后使之變成樹8無向圖G存在歐

6、拉回路，當且僅當G所有結點的度數(shù)全為偶數(shù)且 連通 9設連通平面圖G的結點數(shù)為5，邊數(shù)為6，則面數(shù)為 3 10設個體域Da, b，則謂詞公式("x)A(x)（$x）B（x）消去量詞后的等值式為 (A (a)A (b)(B（a）B（b）) 三、邏輯公式翻譯（每小題6分，本題共12分） 1將語句“雪是黑色的”翻譯成命題公式設P：雪是黑色的， （2分）則命題公式為：P2將語句“他不去學?！狈g成命題公式解：設P：他去學校， 則命題公式為： Ø P 3將語句“小王是個學生，小李是個職員，而小張是個軍人”翻譯成命題公式設P：小王是個學生，Q：小李是個職員，R：小張是個軍人 （2分）則命

7、題公式為：PQR4將語句“如果所有人今天都去參加活動，則明天的會議取消”翻譯成命題公式解：設P：所有人今天都去參加活動，Q：明天的會議取消， 則命題公式為： P® Q5將語句“他去旅游，僅當他有時間”翻譯成命題公式解：設 P：他去旅游，Q：他有時間， 則命題公式為： P ®Q6將語句“41次列車下午五點開或者六點開”翻譯成命題公式解：設P：41次列車下午五點開，Q：41次列車下午六點開， （2分）命題公式為：（PØQ）（ØPQ） 7將語句“小張學習努力，小王取得好成績”翻譯成命題設P：小張學習努力，Q：小王取得好成績， （2分）則命題公式為：PÙ

8、;Q8將語句“有人去上課” 翻譯成謂詞公式 解：設P(x)：x是人，Q(x)：x去上課， （1分）($x)(P(x) ÙQ(x) 9將語句“所有的人都學習努力”翻譯成命題公式 解：設P(x)：x是人，Q(x)：x學習努力， "x）(P(x)®Q(x) 四、判斷說明題（每小題7分，本題共14分）判斷下列各題正誤，并說明理由 1設集合A=1, 2, 3, 4，B=2, 4, 6, 8，判斷下列關系f是否構成函數(shù)f：，并說明理由(1) f=<1, 4>, <2, 2,>, <4, 6>, <1, 8>； (2)f=<

9、1, 6>, <3, 4>, <2, 2>；(3) f=<1, 8>, <2, 6>, <3, 4>, <4, 2,> 答：（1）不構成函數(shù) 因為，但沒有定義，所以不構成函數(shù) （2）不構成函數(shù) 因為，但沒有定義，所以不構成函數(shù) （3）滿足。 因為任意，都有且結果唯一。2若集合A = 1，2，3上的二元關系R=<1, 1>，<2, 2>，<1, 2>，則(1) R是自反的關系； (2) R是對稱的關系答：（1）錯誤 因為，所以R不是自反的 （2）錯誤 因為，但是，所以R不是對稱的 3

10、如果R1和R2是A上的自反關系，判斷結論：“R-11、R1R2、R1R2是自反的” 是否成立？并說明理由 答：成立 因為任意，有所以， R-11、R1R2、R1R2是自反的ooooabcd圖一ooogefho4若偏序集<A，R>的哈斯圖如圖一所示，則集合A的最大元為a，最小元不存在 答：錯誤，集合A沒有最大元，也沒有最小元 其中a是極大元5若偏序集<A，R>的哈斯圖如圖一所示，則集合A的最大元為a，最小元不存在 解：正確對于集合A的任意元素x，均有<x, a>ÎR（或xRa），所以a是集合A中的最大元按照最小元的定義，在集合A中不存在最小元 6如果

11、圖G是無向圖，且其結點度數(shù)均為偶數(shù)，則圖G存在一條歐拉回路答：錯誤 如果圖G是無向圖，且圖G是連通的，同時結點度數(shù)都是偶數(shù)7設G是一個連通平面圖，且有6個結點11條邊，則G有7個面答案：正確 定理，連通平面圖G的結點數(shù)為v，邊數(shù)是e，面數(shù)為r，則歐拉公式v-e+r=2成立 所以r=2-v+e=2-6+11=7 則G存在一條歐拉回路8設G是一個有6個結點14條邊的連通圖，則G為平面圖解：錯誤，不滿足“設G是一個有v個結點e條邊的連通簡單平面圖，若v3，則e3v-6” 9命題公式ØPÙ(P®ØQ)ÚP為永真式 解：正確 因為，由真值表PQØ

12、;PØQP®ØQØP(PØQ)P001111011011100111110001可知，該命題公式為永真式 五計算題（每小題12分，本題共36分）1設集合A=a, b, c，B=a, c，試計算（1）（AB）； （2）（B - A）； （3）（AB）×B解（1）（AB）=c； （2）（B - A）=a； （3）（AB）×B=<c，a>, < c，c > 2設A=0，1，2，3，4，5，6，R=<x，y>|xÎA，yÎA且x+y<1，S=<x，y>|x&#

13、206;A，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> R·S=<0,0>,<0,1>,<0,2>,<0,3> R-1=<0,0> S-1= S ）r(R)=IA 3圖G=<V, E>，其中V

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

15、 ，試(1) 畫出G的圖形表示；(2) 求出每個結點的度數(shù)； (3) 畫出圖G的補圖的圖形v1v2v3v4v5ooooo解：（1）關系圖 （2）deg(v1)=2 deg(v2)=3 deg(v3)=4deg(v4)=3 v1v2v3v4v5ooooodeg(v5)=2 （3）補圖 5設集合A=1，2，3，4，R=<x, y>|x, yÎA；|x-y|=1或x-y=0，試（1）寫出R的有序對表示； （2）畫出R的關系圖；（3）說明R滿足自反性，不滿足傳遞性解:（1）R=<1,1>,<2,2>,<3,3>,<4,4>,<

16、1,2>,<2,1>,<2,3>,<3,2>,<3,4>,<4,3> （3分）°°°°1234（2）關系圖為 （3）因為<1,1>,<2,2>,<3,3>,<4,4>均屬于R，即A的每個元素構成的有序對均在R中，故R在A上是自反的。 因有<2,3>與<3,4>屬于R，但<2,4>不屬于R，所以R在A上不是傳遞的。6設集合A=1, 2, 3，R=<1，1>, <2，1>,<3，1

17、>，S=<1，2>, <2，2>試計算（1）R·S； （2）R -1； （3）r（R）解： （1）R·S =<1，2>, <2，2>,<3，2>； （4分）（2）R -1=<1，1>, <1，2>, <1，3> ； （8分）（3）r（R）=<1，1>, <2，2> , <3，3>, <2，1>,<3，1> 7、求出如圖一所示賦權圖中的最小生成樹（要求寫出求解步驟），并求此最小生成樹的權解 用Kruskal算法求產(chǎn)生

18、的最小生成樹步驟為： 選 選 選 選 選 選 （6分）最小生成樹如圖四所示： （9分） 圖四 最小生成樹的權為：w(T)=22+1+4+9+3+18=57 （12分）8試畫一棵帶權為2, 3, 3, 4, 5,的最優(yōu)二叉樹,并計算該最優(yōu)二叉樹的權ooooooooo23345510717解： 最優(yōu)二叉樹如圖二所示 （10分） 圖二 權為2´3+3´3+3´2+4´2+5´2=39 9設謂詞公式，試（1）寫出量詞的轄域； （2）指出該公式的自由變元和約束變元（1）$x量詞的轄域為， （2分）"z量詞的轄域為, （4分） "y量詞

19、的轄域為 （6分）（2）自由變元為中的y，以及中的z （9分）約束變元為中的x與中的z，以及中的y 10設謂詞公式，試（1）寫出量詞的轄域； （2）指出該公式的自由變元和約束變元（1）$x量詞的轄域為， （3分）"z量詞的轄域為, （6分） （2）自由變元為公式中的y與中的x， （9分）約束變元為的x與z 11求命題公式(PÚQ)®(RÚQ) 的主析取范式、主合取范式解：PQRPÚQRÚQ(PÚQ)®(RÚQ)極小項極大項0000111100110011010101010011111101110111 1

20、 1 1 1 0 1 1 1ØPÙØQÙØRØPÙØQÙRØPÙQÙØRØPÙQÙRPÙØQÙRPÙQÙØRPÙQÙRØPÚQÚR 主析取范式（極小項析取）： （ØPÙØQÙØR）Ú（ØPÙØQÙR）Ú（ØPÙQÙØR）