《2020電大-離散數(shù)學(xué)-形考綜合練習(xí)答案》由會(huì)員分享，可在線閱讀，更多相關(guān)《2020電大-離散數(shù)學(xué)-形考綜合練習(xí)答案（9頁(yè)珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。

1、姓 名： 學(xué) 號(hào)： 得 分： 教師簽名： 離散數(shù)學(xué)形成性考核作業(yè)4 離散數(shù)學(xué)綜合練習(xí)書(shū)面作業(yè) 要求：學(xué)生提交作業(yè)有以下三種方式可供選擇： 1. 可將此次作業(yè)用A4紙打印出來(lái)，手工書(shū)寫(xiě)答題，字跡工整，解答題要有解答過(guò)程，完成作業(yè)后交給輔導(dǎo)教師批閱． 2. 在線提交word文檔． 3. 自備答題紙張，將答題過(guò)程手工書(shū)寫(xiě)，并拍照上傳． 一、公式翻譯題 1．請(qǐng)將語(yǔ)句“小王去上課，小李也去上課．”翻譯成命題公式．

2、 答： 設(shè)P：小王去上課。Q：小李去上課。 則命題公式為：P∧Q 2．請(qǐng)將語(yǔ)句“他去旅游，僅當(dāng)他有時(shí)間．”翻譯成命題公式． 答： 設(shè)P：他去旅游。Q：他有時(shí)間。 則命題公式為：P→Q 3．請(qǐng)將語(yǔ)句 “有人不去工作”翻譯成謂詞公式． 答： 設(shè)A(x)：x是人 B(x)：去工作 則謂詞公式為：?x(A(x)∧B(x)) 4．請(qǐng)將語(yǔ)句“所有人都努力學(xué)習(xí)．”翻譯成謂詞公式． 答： 設(shè)A(x)：x是人 B(x)：努力學(xué)習(xí) 則謂詞公式為：?x(A(x)∧B(x)) 二、計(jì)算題 1．設(shè)A={{1},{2},1,2}，B={1,2,

3、{1,2}}，試計(jì)算 （1）(A-B)； （2）(A∩B)； （3）AB． 解：(1)A -B ={{1},{2}} (2)A∩B ={1,2} (3)AB= {<{1},1>,<{1},2>,<{1},{1,2}>,<{2},1>,<{2},2>,<{2}, {1,2}>,<1,1>,<1,2>,<1, {1,2}>,<2,1>,<2,2>,<2, {1,2}>} 2．設(shè)A={1，2，3，4，5}，R={|xA，yA且x+y4}，S={|xA，yA且x+y<0}，試求R，S，RS，SR，R-1，S-1，r(S)，s(R)． 解：

4、 R={<1,1>,<1,2>,<1,3><2,1><2,2><3,1>} S=空集 RS=空集 SR=空集 R-1={<1,1>,<2,1><3,1><1,2><2,2><1,3>} S-1=空集 r(S)={<1,1><2,2><3,3><4,4><5,5>} 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) 寫(xiě)出關(guān)系R的表示式； (2) 畫(huà)出關(guān)系R的哈斯圖； (3) 求出集合B的最大元、最

5、小元． 解： (1) R={<1,1><1,2><1,3><1,4><1,5><1,6><1,7><1,8><2,2><2,4><2,6><2,8><3,3><3,6><4,4><4,8><5,5><6,6><7,7><8,8>} (2) R的哈斯圖為： (3) 集合B沒(méi)有最大元，最小元是2 4．設(shè)G=，V={ v1，v2，v3，v4，v5}，E={ (v1,v3)，(v2,v3)，(v2,v4)，(v3,v4)，(v3,v5)，(v4,v5) }，試 (1) 給出G的圖形表示； (2) 寫(xiě)出其鄰接矩陣； (3) 求出每個(gè)結(jié)點(diǎn)

6、的度數(shù)； (4) 畫(huà)出其補(bǔ)圖的圖形． 解： （1）G的圖形為： （2）鄰接矩陣為： （4） 補(bǔ)圖為： （3） v1結(jié)點(diǎn)度數(shù)為1，v2結(jié)點(diǎn)度數(shù)為2， v3結(jié)點(diǎn)度數(shù)為3，v4結(jié)點(diǎn)度數(shù)為2，v5結(jié)點(diǎn)度數(shù)為2： 5．圖G=，其中V={ a, b, c, d, e}，E={ (a, b), (a, c), (a, e), (b, d), (b, e), (c, e), (c, d), (d, e) }，對(duì)應(yīng)邊的權(quán)值依次為2、1、2、3、6、1、4及5，試 （1）畫(huà)出G的圖形； （2）寫(xiě)出G的鄰接矩陣

7、； （3）求出G權(quán)最小的生成樹(shù)及其權(quán)值． 解： （1）G的圖形： （2）鄰接矩陣： （3）最小生成樹(shù)及權(quán)值 6． 設(shè)有一組權(quán)為2, 3, 5, 7, 17, 31，試畫(huà)出相應(yīng)的最優(yōu)二叉樹(shù)，計(jì)算該最優(yōu)二叉樹(shù)的權(quán)． 解：二叉樹(shù)如下（方形為給定權(quán)）： 權(quán)：2*5+3*5+5*4+7*3+17*2+31=131 7． 求PQR的析取范式，合取范式、主析取范式，主合取范式． 解： PQR ?RQR 取范式、合取范式、主合取范式都為：RQR 主析取范式為：（PQR)(PQR)(PQR) (PQR)(PQR)(PQR)(PQR) 8．設(shè)謂

8、詞公式． （1）試寫(xiě)出量詞的轄域； （2）指出該公式的自由變?cè)图s束變?cè)? 答： （1）量詞x的轄域?yàn)椋篜(x,y)→(?z)Q(y,x,z) 量詞z的轄域?yàn)椋篞(y,x,z) 量詞y的轄域?yàn)椋篟(y,z) （2）P(x,y)中的x是約束變?cè)?，y是自由變?cè)? Q(y,x,z)中的x和z是約束變?cè)?，y是自由變?cè)猂(y,z)中的z是自由變?cè)瑈是約束變?cè)? 9．設(shè)個(gè)體域?yàn)镈={a1, a2}，求謂詞公式("y)($x)P(x,y)消去量詞后的等值式； 答： ("y)($x)P(x,y) =$xP(x, a1)$xP(x, a2) = (P(a1,a1)P(a2,

9、a1))(P(a1,a2)P(a2,a2)) 三、證明題 1．對(duì)任意三個(gè)集合A, B和C，試證明：若AB = AC，且A，則B = C． 證明： (1)對(duì)于任意∈AB,其中a∈A,b∈B,因?yàn)锳B= AC,必有∈AC,其中b∈C因此B?C (2)同理,對(duì)于任意∈AC,其中,a∈A,c∈C,因?yàn)锳B= AC，必有∈AB,其中c∈B,因此C?B 由(1)(2)，得B=C。 2．試證明：若R與S是集合A上的自反關(guān)系，則R∩S也是集合A上的自反關(guān)系． 證明： 若R與S是集合A上的自反關(guān)系,則任意x∈A,∈R,∈S

10、,從而∈R∩S,注意x是A的任意元素,所以R∩S也是集合A上的自反關(guān)系. 3．設(shè)連通圖G有k個(gè)奇數(shù)度的結(jié)點(diǎn)，證明在圖G中至少要添加條邊才能使其成為歐拉圖． 證明： 由定理3.1.2，任何圖中度數(shù)為奇數(shù)的結(jié)點(diǎn)必是偶數(shù)，可知k是偶數(shù)． 又根據(jù)定理4.1.1的推論，圖G是歐拉圖的充分必要條件是圖G不含奇數(shù)度結(jié)點(diǎn)．因此只要在每對(duì)奇數(shù)度結(jié)點(diǎn)之間各加一條邊，使圖G的所有結(jié)點(diǎn)的度數(shù)變?yōu)榕紨?shù)，成為歐拉圖．故最少要加k/2條邊到圖G才能使其成為歐拉圖． 4．試證明 (P(QR))PQ與 (PQ)等價(jià)． 證明： (P(QR))PQ ?(P(QR))PQ ?(PQR)PQ ?(PPQ)(QPQ)(RPQ) ?(PQ)(PQ)(PQR) ?PQ ? (PQ) 5．試證明：(A∧B)∧(B∨C)∧C A． 證明： (A∧B)∧(B∨C)∧C ?(A∨B)∧(B∨C)∧C ?(A∨B)∧(B∧C)∨(C∧C) ?(A∨B)∧(B∧C) ?(A∧(B∧C))∨(B∧(B∧C)) ?A∧(B∧C) ?(A∨B∨C) 所以左邊不能推出右邊的“A”