《2020電大-離散數(shù)學-形考綜合練習答案》由會員分享，可在線閱讀，更多相關《2020電大-離散數(shù)學-形考綜合練習答案（9頁珍藏版）》請在裝配圖網(wǎng)上搜索。

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

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

3、{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．設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．設A={1, 2, 3, 4, 5, 6, 7, 8}，R是A上的整除關系，B={2, 4, 6}． (1) 寫出關系R的表示式； (2) 畫出關系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沒有最大元，最小元是2 4．設G=，V={ v1，v2，v3，v4，v5}，E={ (v1,v3)，(v2,v3)，(v2,v4)，(v3,v4)，(v3,v5)，(v4,v5) }，試 (1) 給出G的圖形表示； (2) 寫出其鄰接矩陣； (3) 求出每個結(jié)點

6、的度數(shù)； (4) 畫出其補圖的圖形． 解： （1）G的圖形為： （2）鄰接矩陣為： （4） 補圖為： （3） v1結(jié)點度數(shù)為1，v2結(jié)點度數(shù)為2， v3結(jié)點度數(shù)為3，v4結(jié)點度數(shù)為2，v5結(jié)點度數(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) }，對應邊的權值依次為2、1、2、3、6、1、4及5，試 （1）畫出G的圖形； （2）寫出G的鄰接矩陣

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

8、詞公式． （1）試寫出量詞的轄域； （2）指出該公式的自由變元和約束變元． 答： （1）量詞x的轄域為：P(x,y)→(?z)Q(y,x,z) 量詞z的轄域為：Q(y,x,z) 量詞y的轄域為：R(y,z) （2）P(x,y)中的x是約束變元，y是自由變元 Q(y,x,z)中的x和z是約束變元，y是自由變元R(y,z)中的z是自由變元，y是約束變元 9．設個體域為D={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．對任意三個集合A, B和C，試證明：若AB = AC，且A，則B = C． 證明： (1)對于任意∈AB,其中a∈A,b∈B,因為AB= AC,必有∈AC,其中b∈C因此B?C (2)同理,對于任意∈AC,其中,a∈A,c∈C,因為AB= AC，必有∈AB,其中c∈B,因此C?B 由(1)(2)，得B=C。 2．試證明：若R與S是集合A上的自反關系，則R∩S也是集合A上的自反關系． 證明： 若R與S是集合A上的自反關系,則任意x∈A,∈R,∈S

10、,從而∈R∩S,注意x是A的任意元素,所以R∩S也是集合A上的自反關系. 3．設連通圖G有k個奇數(shù)度的結(jié)點，證明在圖G中至少要添加條邊才能使其成為歐拉圖． 證明： 由定理3.1.2，任何圖中度數(shù)為奇數(shù)的結(jié)點必是偶數(shù)，可知k是偶數(shù)． 又根據(jù)定理4.1.1的推論，圖G是歐拉圖的充分必要條件是圖G不含奇數(shù)度結(jié)點．因此只要在每對奇數(shù)度結(jié)點之間各加一條邊，使圖G的所有結(jié)點的度數(shù)變?yōu)榕紨?shù)，成為歐拉圖．故最少要加k/2條邊到圖G才能使其成為歐拉圖． 4．試證明 (P(QR))PQ與 (PQ)等價． 證明： (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”