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

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

2、)：x是人 B(x)：去工作則謂詞公式為：x(A(x)B(x) 4請(qǐng)將語句“所有人都努力學(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,1,2，試計(jì)算（1）(A-B)； （2）(AB)； （3）AB解：(1)A -B =1,2(2)AB =1,2(3)AB=,2設(shè)A=1，2，3，4，5，R=|xA，yA且x+y4，S=|xA，yA且x+y0，試求R，S，RS，SR，R-1，S-1，r(S)，s(R) 解：R=,S=空集RS=空集SR=空集R-1=,S-1=空集r(S)=s(R)= 3設(shè)A=1, 2,

3、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=(2) R的哈斯圖為：(3) 集合B沒有最大元，最小元是24設(shè)G=，V= v1，v2，v3，v4，v5，E= (v1,v3)，(v2,v3)，(v2,v4)，(v3,v4)，(v3,v5)，(v4,v5) ，試(1) 給出G的圖形表示； (2) 寫出其鄰接矩陣；(3) 求出每個(gè)結(jié)點(diǎn)的度數(shù)； (4) 畫出其補(bǔ)圖的圖形解：（1）G的圖形為：（2）鄰接矩陣為：（4） 補(bǔ)圖為：（3） v1結(jié)點(diǎn)度數(shù)為1，v2結(jié)點(diǎn)度數(shù)為2，

4、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）畫出G的圖形； （2）寫出G的鄰接矩陣；（3）求出G權(quán)最小的生成樹及其權(quán)值解：（1）G的圖形：（2）鄰接矩陣：（3）最小生成樹及權(quán)值6 設(shè)有一組權(quán)為2, 3, 5, 7, 17, 31，試畫出相應(yīng)的最優(yōu)二叉樹，計(jì)算該最優(yōu)二叉樹的權(quán)解：二叉樹如下（方形為給定權(quán)）：權(quán)：2*5+3*5+5*4+7*3+17*2

5、+31=1317 求PQR的析取范式，合取范式、主析取范式，主合取范式解：PQR RQR取范式、合取范式、主合取范式都為：RQR主析取范式為：（PQR)(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)8設(shè)謂詞公式（1）試寫出量詞的轄域；（2）指出該公式的自由變?cè)图s束變?cè)穑海?）量詞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è)瑈是自由變?cè)猀(y,x,z)中的x和z是約束變?cè)?，y是自由變?cè)猂(y,z)中的z是自由變?cè)?，y是約束變?cè)?9設(shè)個(gè)體域?yàn)镈=a1, a2，求謂詞公式(y)($x)

6、P(x,y)消去量詞后的等值式；答：(y)($x)P(x,y) =$xP(x, a1)$xP(x, a2)= (P(a1,a1)P(a2,a1)(P(a1,a2)P(a2,a2)三、證明題 1對(duì)任意三個(gè)集合A, B和C，試證明：若AB = AC，且A，則B = C證明：(1)對(duì)于任意AB,其中aA,bB,因?yàn)锳B= AC,必有AC,其中bC因此BC(2)同理,對(duì)于任意AC,其中,aA,cC,因?yàn)锳B= AC，必有AB,其中cB,因此CB由(1)(2)，得B=C。2試證明：若R與S是集合A上的自反關(guān)系，則RS也是集合A上的自反關(guān)系證明：若R與S是集合A上的自反關(guān)系,則任意xA,R,S,從而RS,

7、注意x是A的任意元素,所以RS也是集合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試證明：(AB)(BC)C A證明： (AB)(BC)C(AB)(BC)C(AB)(BC)(CC)(AB)(BC)(A(BC)(B(BC)A(BC)(ABC)所以左邊不能推出右邊的“A”