離散數(shù)學(xué)形成性考核作業(yè)4

《離散數(shù)學(xué)形成性考核作業(yè)4》由會員分享，可在線閱讀，更多相關(guān)《離散數(shù)學(xué)形成性考核作業(yè)4（7頁珍藏版）》請在裝配圖網(wǎng)上搜索。

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

2、 設(shè)P：小王去上課。 Q: 小李去上課。 則P^Q 2．請將語句“他去旅游，僅當(dāng)他有時間．”翻譯成命題公式． 設(shè)P：他去旅游。 Q: 他有時間。 則P→Q 3．請將語句 “有人不去工作”翻譯成謂詞公式． 設(shè)A(x): x是人 B(x):去工作 x(A(x)^B(x)) 4．請將語句“所有人都努力學(xué)習(xí)．”翻譯成謂詞公式． 設(shè)A(x): x是人

3、 B(x):努力工作 x(A(x)^B(x)) 3 / 7 二、計算題 1．設(shè)A={{1},{2},1,2}，B={1,2,{1,2}}，試計算 （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}

4、，R={|xA，yA且x+y4}，S={|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

5、, 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>} 1 2 3 4 6 5 7 8 關(guān)系R的哈斯圖 (2) (3) 集合B沒有最大元，最小元是2 4．設(shè)G=，

6、V={ v1，v2，v3，v4，v5}，E={ (v1,v3)，(v2,v3)，(v2,v4)，(v3,v4)，(v3,v5)，(v4,v5) }，試 (1) 給出G的圖形表示； (2) 寫出其鄰接矩陣； (3) 求出每個結(jié)點的度數(shù)； (4) 畫出其補(bǔ)圖的圖形． 解：（1） （2） （3） 1、2、4、3、2 （4） 5．圖G=，其中V={ a, b, c, d, e}，E={ (a, b), (

7、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)值． b c 解：（1） 。 。 2 1 a。 6 4 2 1 3 。 。 e 5

8、 d （2） （3） b c 。 。 2 1 a。 1 3 。 。 e d 其權(quán)值為：7 6．設(shè)有一組權(quán)為2, 3, 5, 7, 17, 31，試畫出相應(yīng)的最優(yōu)二叉樹，計算該最優(yōu)二叉樹的權(quán)． 解： 65 17

9、48 5 12 17 31 2 3 5 7 權(quán)值為65。 7． 求PQR的析取范式，合取范式、主析取范式，主合取范式． 解：┐P(Q∨R）= ┐PQ∨R 所以合取范式和析取范式都是┐PQ∨R 所以主合取范式就是┐PQ∨R 所以主析取范式就是(PQ R) (PQ R) (PQ R) (PQ R) (PQ R) (PQ R) (PQ R) 8．設(shè)謂詞公式． （1）試寫出量詞的轄域； （2）指出

10、該公式的自由變元和約束變元． 解：(1)量詞$x的轄域為 P(x,y) ("z)Q(y,x,z) 量詞"z的轄域為Q(y,x,z) 量詞"y的轄域為R(y,x) (2) P(x,y)中的x是約束變元，y是自由變元 Q(y,x,z)中的x和z是約束變元，y是自由變元 R(y,x)中的x是自由變元，y是約束變元 9．設(shè)個體域為D={a1, a2}，求謂詞公式("y)($x)P(x,y)消去量詞后的等值式； 解： "y$xP(x,y)= $xP(x, a1) $xP(x, a2) =( P(a1, a1) P(a2, a1)) (

11、 P(a1, a2) P(a1, a2)) 三、證明題 1．對任意三個集合A, B和C，試證明：若AB = AC，且A，則B = C． 證明：設(shè)xA，yB，則AB， 因為AB = AC，故 AC，則有yC， 所以B C． 設(shè)xA，zC，則 AC， 因為AB = AC，故AB，則有zB，所以CB． 故得A=B． 2．試證明：若R與S是集合A上的自反關(guān)系，則R∩S也是集合A上的自反關(guān)系．

12、 證明： R1和R2是自反的，"x A， R1， R2，則 R1∩R2， 所以R1∩R2是自反的． 3．設(shè)連通圖G有k個奇數(shù)度的結(jié)點，證明在圖G中至少要添加條邊才能使其成為歐拉圖． 證明：由定理推論知：在任何圖中，度數(shù)為奇數(shù)的結(jié)點必是偶數(shù)個，則k是偶數(shù)。又由歐拉圖的充要條件是圖G中不含奇數(shù)度結(jié)點。因此，只要在每對奇數(shù)度結(jié)點間各加一條邊，使圖G的所有結(jié)點的度數(shù)變?yōu)榕紨?shù)，成為歐拉圖。故最少要加條邊才能使其成為歐拉圖。 4．試證明 (P(QR))PQ與 (PQ)等價． 證：(P

13、(QR))PQ(P(QR))PQ (PQR)PQ (PPQ)(QPQ)(RPQ) (PQ)(PQ)(PQR) PQ （吸收律） (PQ) （摩根律） 5．試證明：(A∧B)∧(B∨C)∧C A． 證明： ① 前提引入； ② 前提引入； ③ ①② 析取三段論； ④ 前提引入； ⑤ 置換；④ ⑥ ③⑤析取三段論。