國家開放大學(xué)《離散數(shù)學(xué)》綜合練習(xí)題參考答案

1、國家開放大學(xué)離散數(shù)學(xué)綜合練習(xí)題參考答案一、單項選擇題1若集合A a，a，1，2，則下列表述正確的是( )。Aa，aÎAB1，2ÏACaÍADÆÎA2若集合A=1，2，B=1，2，1，2，則下列表述正確的是( )。AAÌB，且AÎBBBÌA，且AÎBCAÌB，且AÏBDAËB，且AÎB3.若集合A a，1，則下列表述正確的是( )。A1ÎAB1ÍACaÎADÆÎA4.設(shè)集合A = 1, a ，則P(A) = ( )。A

2、1, aB,1, a C,1, a, 1, a D1, a, 1, a 5.若集合A的元素個數(shù)為10，則其冪集的元素個數(shù)為（ ）。A10B100C1024D16.集合A=1, 2, 3, 4, 5, 6, 7, 8上的關(guān)系R=<x，y>|x+y=10且x, yA，則R的性質(zhì)為（ ）。A自反的B對稱的C傳遞且對稱的D反自反且傳遞的7設(shè)集合A=1 , 2 , 3 , 4上的二元關(guān)系R = 1 , 1，2 , 2，2 , 3，4 , 4，S = 1 , 1，2 , 2，2 , 3，3 , 2，4 , 4，則S是R的（ ）閉包。A自反B傳遞C對稱D以上都不對 136245878.設(shè)A=1,

3、 2, 3, 4, 5, 6, 7, 8，R是A上的整除關(guān)系，B=2, 4, 6，則集合B的最大元、最小元、上界、下界依次為 ( )。A8、2、8、2B8、1、6、1C6、2、6、2D無、2、無、29.設(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>，則（ ）不是從A到B的函數(shù)。AR1BR2CR3DR1和R310.設(shè)A=a，b，c，B=1，2，作f：AB，則不同的函數(shù)個數(shù)為（ ）。A2

4、B3C6D811設(shè)圖G<V, E>，vÎV，則下列結(jié)論成立的是 ( ) Adeg(v)=2|E|Bdeg(v)=|E|CD 12設(shè)無向圖G的鄰接矩陣為，則G的邊數(shù)為( )A6B5C4D3ooooabcdoe13如右圖所示，以下說法正確的是 ( ) A(a, e)是割邊 B(a, e)是邊割集C(a, e) ,(b, c)是邊割集 D(d, e)是邊割集14設(shè)有向圖（a）、（b）、（c）與（d）如下圖所示，則下列結(jié)論成立的是( )A（a）是強連通的B（b）是強連通的C（c）是強連通的D（d）是強連通的15設(shè)完全圖Kn 有n個結(jié)點(n2)，m條邊，當(dāng)（ ）時，Kn 中存在歐拉

5、回路Am為奇數(shù)Bn為偶數(shù)Cn為奇數(shù)Dm為偶數(shù)16設(shè)G是連通平面圖，有v個結(jié)點，e條邊，r個面，則r= ( )Aev2Bve2Cev2Dev217無向簡單圖G是棵樹，當(dāng)且僅當(dāng)( )AG連通且邊數(shù)比結(jié)點數(shù)少1BG連通且結(jié)點數(shù)比邊數(shù)少1CG的邊數(shù)比結(jié)點數(shù)少1DG中沒有回路18已知一棵無向樹T中有8個結(jié)點，4度，3度，2度的分支點各一個，T的樹葉數(shù)為（ ）A8B5C4D319.下列命題公式是等價公式的為( )AØPÙØQÛPÚQBA®(ØB®A) ÛØA®(A®B)CQ®(

6、PÚQÛØQÙ(PÚQ) DØAÚ(AÙB) ÛB20.下列公式 ( )為重言式AØ(ØPÚ(PÙQ) «QB(B®(AÚB) «(ØAÙ(AÚB)CAÙØB«AÚBD(P®(ØQ®P)«(ØP®(P®Q)21.命題公式Ø (P®Q)的主析取范式是( )AB C D22

7、.設(shè)C(x): x是國家級運動員，G(x): x是健壯的，則命題“沒有一個國家級運動員不是健壯的”可符號化為 ( )A BC D23.表達(dá)式中的轄域是( )AP(x, y)BP(x, y)ÚQ(z)CR(x, y) DP(x, y)ÙR(x, y)二、填空題1設(shè)集合A=0, 1, 2, 3，B=2, 3, 4, 5，R是A到B的二元關(guān)系，則R的有序?qū)蠟椋≧ = 2 , 2 ，2 , 3 ，3 , 2 ，3 , 3 ）。 2設(shè)集合A=1, 2, 3, 4 ，B=6, 8, 12， A到B的二元關(guān)系R那么R1（<6，3>，<8，4>）。 3設(shè)集合A=

8、a, b, c, d，A上的二元關(guān)系R=<a, a >, <b, b>, <b, c>, <c, d>，若在R中再增加兩個元素（<c, b>, <d, c>），則新得到的關(guān)系就具有對稱性。4設(shè)A=1, 2上的二元關(guān)系為R=<x, y>|xÎA，yÎA, x+y =10，則R的自反閉包為（IA）。 5設(shè)R是集合A上的等價關(guān)系，且1 , 2 , 3是A中的元素，則R中至少包含（<1, 1>, <2, 2>, <3, 3>）等元素。6設(shè)集合A=1, 2，B=a,

9、 b，那么集合A到B的雙射函數(shù)是（<1, a >, <2, b >，<1, b >, <2, a >）。7. 已知圖G中有1個1度結(jié)點，2個2度結(jié)點，3個3度結(jié)點，4個4度結(jié)點，則G的邊數(shù)是（15）。ooooabcdoeof8. 設(shè)給定圖G (如右圖所示)，則圖G的點割集是（f、c, e）。9. 無向圖G存在歐拉回路，當(dāng)且僅當(dāng)G連通且（結(jié)點度數(shù)都是偶數(shù)）。10. 若圖G=<V, E>中具有一條漢密爾頓回路，則對于結(jié)點集V的每個非空子集S，在G中刪除S中的所有結(jié)點得到的連通分支數(shù)為W，則S中結(jié)點數(shù)|S|與W滿足的關(guān)系式為（W(G-S)&

10、#163; |S|）。11. 設(shè)圖G是有6個結(jié)點的連通圖，結(jié)點的總度數(shù)為18，則可從G中刪去（4）條邊后使之變成樹（邊后，可以確定圖G的一棵生成樹）12.命題公式的真值是（1）。13.含有三個命題變項P，Q，R的命題公式PÙQ的主析取范式是（(PÙQÙØR)Ú( PÙQÙR)）14.設(shè)個體域D1,2,那么謂詞公式消去量詞后的等值式為（(A(1) ÚA(2)Ú(B(1) ÙB(2)）。15.謂詞命題公式("x)(P(x)Q(x)R(x，y)中的約束變元為（x）。三、判斷題ooooabdo

11、oogefho1若偏序集<A，R>的哈斯圖如右圖所示，則集合A的最大元為a，最小元不存在。（×）2設(shè)集合A=1, 2, 3, 4，B=2, 4, 6, 8，下列關(guān)系f =<1, 4>, <2, 2,>, <4, 6>, <1, 8>可以構(gòu)成函數(shù)f：AB是。（×）3. 設(shè)集合A=1, 2, 3, 4，B=2, 4, 6, 8，下列關(guān)系f =<1, 6>, <3, 4>, <2, 2>；可以構(gòu)成函數(shù)f：AB是。（×）4. 設(shè)集合A=1, 2, 3, 4，B=2, 4, 6,

12、 8，下列關(guān)系f =<1, 8>, <2, 6>, <3, 4>, <4, 2,>可以構(gòu)成函數(shù)f：AB是。（）ooooabcdoeofog圖G5. 1如果圖G是無向圖，且其結(jié)點度數(shù)均為偶數(shù)，則圖G存在一條歐拉回路（×）6. 如右圖所示的圖G不是歐拉圖而是漢密爾頓圖（）7. 設(shè)G是一個有7個結(jié)點16條邊的連通圖，則G為平面圖（×）8. （1）公式是邏輯有效式(永真式)（×） （2）下面的推理是否正確 P（a） P （"x）P（x） US 解：（1）該公式是永真式 因為 Û（2）錯誤 應(yīng)為（"

13、;x）P（x） UG 全稱指定規(guī)則與全稱推廣規(guī)則不能混淆9. 判斷下列各題正誤，并說明理由（1）公式(Q ÙØR)®P)Ù(ØP®QÚR)«PÚR為永真式（2）求命題公式(PÙQ)Ù(ØPÚØR)的真值表，并判斷它的類型. 解：（1）該公式是永真式因為 （2）作真值表PQPÙQØPØQØPÚØQ(PÙQ)Ù(ØPÚØQ)00011100101010

14、10001101110000所以，該公式為永假式四、計算題1設(shè)集合A=1, 2, 1, 2，B=1, 2, 1, 2，試計算（1）A-B； （2）AB； （3）A×B解：（1）A-B=1, 2, 1, 2- 1, 2, 1, 2=1, 2（2）AB =1, 2, 1, 21, 2, 1, 2=1, 2（3）A´ B =1, 2, 1, 2´1, 2, 1, 2=<1, 1>, <1, 2>, <1, 1, 2 >, <2, 1>, <2, 2>, <2, 1, 2 >, <1, 1>

15、;, <1, 2>, <1, 1, 2 >, < 2, 1>, < 2, 2>, < 2, 1, 2 2設(shè)A=1，2，3，4，5，R=<x，y>|xÎA，yÎA且x+y£4，S=<x，y>|xÎA，yÎA且x+y <0，試求R，S，R·S，S·R，R-1，S-1，r(S)，s(R) 解：R=<1, 1>, <1, 2>, <1, 3>, <2, 1>, <2, 2>, <3,

16、1>, S= Æ， R·S=Æ， S·R=Æ， R-1= R， S-1= Æ， r(S)=IA s(R) =<1, 1>, <1, 2>, <1, 3>, <2, 1>, <2, 2>, <3, 1>3設(shè)A=1, 2, 3, 4, 5, 6, 7, 8，R是A上的整除關(guān)系，B=2, 4, 6。（1）寫出關(guān)系R的表示式；（2）畫出關(guān)系R的哈斯圖；（3）求出集合B的最大元、最小元。解：（1）R=IÈ<1, 2>, <1, 3>,

17、 <1, 4>, <1, 5>, <1, 6>, <1, 7>, <1, 8>, <2, 4>, <2, 6>, <2, 8>, <3, 6>, <4, 8>（2）關(guān)系R的哈斯圖如下圖所示12346578關(guān)系R的哈斯圖（3）集合B沒有最大元，最小元是：24. 設(shè)G=<V，E>，V= v1，v2，v3，v4，v5，E= (v1,v3)，(v2,v3)，(v2,v4)，(v3,v4)，(v3,v5)，(v4,v5) ，試(1) 給出G的圖形表示； (2) 寫出其鄰接矩

18、陣；oooov1ov5v2v3v4(3) 求出每個結(jié)點的度數(shù)； (4) 畫出其補圖的圖形解：(1) 因為V= v1，v2，v3，v4，v5，E= (v1,v3)，(v2,v3)，(v2,v4)，(v3,v4)，(v3,v5)，(v4,v5) ，所以G的圖形表示為：(2) 分析：本題給定的簡單圖是無向圖，因此鄰接矩陣為對稱的即當(dāng)結(jié)點vi與vj相鄰時，結(jié)點vj與vi也相鄰，所以連接結(jié)點vi與vj的一條邊在鄰接矩陣的第i行第j列處和第j行第i列處各寫一個1；當(dāng)結(jié)點vi與vj沒有邊連接時，鄰接矩陣的第i行第j列處和第j行第i列處各寫一個0鄰接矩陣： (3) 由G的圖形可知，v1，v2，v3，v4，v5

19、結(jié)點的度數(shù)依次為1，2，4，3，2 oooov1ov5v2v3v4oooov1ov5v2v3v4(4) 由關(guān)于補圖的定義3.1.9可知，先畫出完全圖（見圖1），然后去掉原圖，可得補圖（見圖2）如下： 圖1 圖25圖G=<V, E>，其中V= a, 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，試cabedooooo12216435（1）畫出G的圖形； （2）寫出G的鄰接矩陣；（3）求出G權(quán)最小的生成樹及其權(quán)值解：（1）因為V

20、= a, b, c, d, e， E= (a, b), (a, c), (a, e), (b, d), (b, e), (c, e), (c, d), (d, e)， 所以G的圖形如右圖表示（2）由圖得圖G的鄰接矩陣為： （3）圖G有5個結(jié)點，其生成樹有4條邊，用Kruskal算法（避圈法）求其權(quán)最小的生成樹T：cabedooooo1213第1步，取具最小權(quán)1的邊(a, c)；第2步，取剩余邊中具最小權(quán)1的邊(c, e)；第3步，取剩余邊中不與前2條邊構(gòu)成回路的具最小權(quán)2的邊(a, b)；第4步，取剩余邊中不與前3條邊構(gòu)成回路的具最小權(quán)3的邊(b, d)所求最小生成樹T如右下圖，其權(quán)為oooo

21、o32755173410oooo1731oo65 6. 設(shè)有一組權(quán)為2, 3, 5, 7, 17, 31，試畫出相應(yīng)的最優(yōu)二叉樹，計算該最優(yōu)二叉樹的權(quán)解：從2, 3, 5, 7, 17, 31中選2, 3為最低層結(jié)點，并從權(quán)數(shù)中刪去，再添上他們的和數(shù)，即5, 5, 7, 17, 31；再從5, 5, 7, 17, 31中選5, 5為倒數(shù)第2層結(jié)點，并從上述數(shù)列中刪去，再添上他們的和數(shù)，即7, 10, 17, 31； 然后，從7, 10, 17, 31中選7, 10為倒數(shù)第3層結(jié)點，并從上述數(shù)列中刪去，再添上他們的和數(shù)，即17, 17, 31； 最優(yōu)二叉樹如右圖所示最優(yōu)二叉樹權(quán)值為：2´

22、;5+3´5+5´4+7´3+17´2+31´1 =10+15+20+21+34+31=1317求公式的析取、合取、主合取主合取范式 解： （析取、合取、主合取范式）Û(P(QQ)(RR)(PP)Q(RR)(PP)(QQ)R) Û(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)(PQR) （主析取范式）8用列真值表的方法求命題公式的主析取范式解：列真值表 PQR0001000111010100111110001101011101011111取真值為1的項，所求主析取范式為：(PQR)(PQR)(PQR)(PQR)

23、(PQR)9試求謂詞公式中，"x，$x，$y的轄域，試問G(x, y)和B(x, y)中x，y是自由變元，還是約束變元？解："x的轄域： $x的轄域：H(x,y) $y的轄域：G(x,y) G(x, y)中的x，y是約束變量，B(x, y)中的x, y是自由變量. 10請將語句翻譯成命題公式： （1）今天不是天晴 （2）你去聽課，他也去聽課 （3）如果天下雪，則我明天就不去市里 （4）盡管他參加了考試，但他沒有通過考試解：（1）設(shè)P：今天是天晴； 命題公式為： Ø P （2）設(shè)P：你去聽課，Q：他去聽課： 命題公式為：PÙQ （3）設(shè)P：天下雪，Q：我明

24、天去市里； 命題公式為：P®ØQ （4）設(shè)P：他參加了考試，Q：他沒有通過考試； 命題公式為：PÙØ Q11請將語句翻譯成謂詞公式： （1）所有人都不去上課 （2）有人不去工作 解：（1）設(shè)P(x)：x是人，Q(x)：x去上課 謂詞公式為： ("x)(P(x)® Q(x) （2）設(shè)P(x)：x是人，Q(x)：x去工作， 謂詞公式為： ($x)(P(x) ÙQ(x)五、證明題1試證明集合等式：AÈ (BÇC)=(AÈB) Ç (AÈC)證明：若xAÈ (BÇ

25、C)，則xA或xBÇC，即 xA或xB 且 xA或xC即xAÈB 且 xAÈC ，即 xT=(AÈB) Ç (AÈC)，所以AÈ (BÇC)Í (AÈB) Ç (AÈC) 反之，若x(AÈB) Ç (AÈC)，則xAÈB 且 xAÈC， 即xA或xB 且 xA或xC，即xA或xBÇC，即xAÈ (BÇC)，所以(AÈB) Ç (AÈC)Í AÈ (

26、BÇC) 因此AÈ (BÇC)=(AÈB) Ç (AÈC)2對任意三個集合A, B和C，試證明：若A´B = A´C，且A¹，則B = C 證明：設(shè)xÎA，yÎB，則<x，y>ÎA´B， 因為A´B = A´C，故<x，y>Î A´C，則有yÎC， 所以B Í C 設(shè)xÎA，zÎC，則<x，z>Î A´C， 因為A´B =

27、 A´C，故<x，z>ÎA´B，則有zÎB，所以CÍB 故得B = C 3.試證明：若A´A=B´B，則A=B證明：設(shè)xÎA，則<x，x>ÎA´A， 因為A´A=B´B，故<x，x>ÎB´B，則有xÎB，所以AÍB 設(shè)xÎB，則<x，x>ÎB´B， 因為A´A=B´B，故<x，x>ÎA´A，則有xÎA，所以B