姓 名： 學(xué) 號： 得 分： 教師簽名： 離散數(shù)學(xué)形成性考核作業(yè)4離散數(shù)學(xué)綜合練習(xí)書面作業(yè)要求：學(xué)生提交作業(yè)有以下三種方式可供選擇：1. 可將此次作業(yè)用A4紙打印出來，手工書寫答題，字跡工整，解答題要有解答過程，完成作業(yè)后交給輔導(dǎo)教師批閱2. 在線提交word文檔3. 自備答題紙張，將答題過程手工書寫，并拍照上傳一、公式翻譯題 1請將語句“小王去上課，小李也去上課”翻譯成命題公式 答：設(shè)P：小王去上課。Q：小李去上課。則命題公式為：PQ 2請將語句“他去旅游，僅當(dāng)他有時間”翻譯成命題公式答：設(shè)P：他去旅游。Q：他有時間。則命題公式為：PQ 3請將語句 “有人不去工作”翻譯成謂詞公式答：設(shè)A(x)：x是人 B(x)：去工作則謂詞公式為：x(A(x)B(x) 4請將語句“所有人都努力學(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=<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=<x，y>|xA，yA且x+y4，S=<x，y>|xA，yA且x+y<0，試求R，S，RS，SR，R-1，S-1，r(S)，s(R) 解：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) 寫出關(guān)系R的表示式； (2) 畫出關(guān)系R的哈斯圖； (3) 求出集合B的最大元、最小元 解：(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沒有最大元，最小元是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) 寫出其鄰接矩陣；(3) 求出每個結(jié)點(diǎn)的度數(shù)； (4) 畫出其補(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, 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，試（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+31=1317 求PQR的析取范式，合取范式、主析取范式，主合取范式解：PQR RQR取范式、合取范式、主合取范式都為：RQR主析取范式為：（PQR)(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)8設(shè)謂詞公式（1）試寫出量詞的轄域；（2）指出該公式的自由變元和約束變元答：（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是約束變元，y是自由變元Q(y,x,z)中的x和z是約束變元，y是自由變元R(y,z)中的z是自由變元，y是約束變元 9設(shè)個體域?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,a1)(P(a1,a2)P(a2,a2)三、證明題 1對任意三個集合A, B和C，試證明：若AB = AC，且A，則B = C證明：(1)對于任意<a,b>AB,其中aA,bB,因?yàn)锳B= AC,必有<a,b>AC,其中bC因此BC(2)同理,對于任意<a,c>AC,其中,aA,cC,因?yàn)锳B= AC，必有<a,c>AB,其中cB,因此CB由(1)(2)，得B=C。2試證明：若R與S是集合A上的自反關(guān)系，則RS也是集合A上的自反關(guān)系證明：若R與S是集合A上的自反關(guān)系,則任意xA,<x,x>R,<x,x>S,從而<x,x>RS,注意x是A的任意元素,所以RS也是集合A上的自反關(guān)系.3設(shè)連通圖G有k個奇數(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)因此只要在每對奇數(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”