2019年秋季離散數(shù)學(xué)綜合考試

2019年秋季離散數(shù)學(xué)綜合考試2019年秋季離散數(shù)學(xué)綜合考試2019年秋季離散數(shù)學(xué)綜合考試資料僅供參考文件編號(hào)：2022年4月2019年秋季離散數(shù)學(xué)綜合考試版本號(hào)：A修改號(hào)：1頁次：1.0審核：批準(zhǔn):發(fā)布日期：姓名：嚴(yán)先貴姓名：嚴(yán)先貴學(xué)號(hào)1944201250206得分：教師簽名：離散數(shù)學(xué)綜合練習(xí)書面作業(yè)要求：學(xué)生提交作業(yè)有以下三種方式可供選擇：1.可將此次作業(yè)用A4紙打印出來，手工書寫答題，字跡工整，解答題要有解答過程，完成作業(yè)后交給輔導(dǎo)教師批閱．2.在線提交word文檔．3.自備答題紙張，將答題過程手工書寫，并拍照上傳．一、公式翻譯題1．請(qǐng)將語句“小王去上課，小李也去上課．”翻譯成命題公式．設(shè)：P:小王去上課。Q：小李去旅游。則PQ2．請(qǐng)將語句“他去旅游，僅當(dāng)他有時(shí)間．”翻譯成命題公式．設(shè)：P:他去旅游Q：他有時(shí)間則PQ3．請(qǐng)將語句“有人不去工作”翻譯成謂詞公式．設(shè)???A（x）：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）(AB)；（2）(A∩B)；（3）A×B．解（AB）={{1},{2}}（A∩B）={1,2}（3）A×B={<1}，1＞，{{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的最大元、最小元．解：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〉}4．設(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)關(guān)系R的哈斯圖1515637482(3)集合B的沒有最大元，最小元是2．4．設(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)求出每個(gè)結(jié)點(diǎn)的度數(shù)；(4)畫出其補(bǔ)圖的圖形．解：(1)v1v5v2v3v4(2)鄰接矩陣為(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(4)補(bǔ)圖圖形為v1v5v2v3v45．圖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)}，對(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）寫出G的鄰接矩陣3）G權(quán)最小的生成樹及其權(quán)值6．設(shè)有一組權(quán)為2,3,5,7,17,31，試畫出相應(yīng)的最優(yōu)二叉樹，計(jì)算該最優(yōu)二叉樹的權(quán)．335251071731173465權(quán)為2*5+3*5+5*4+7*3+17*2+31=1317．求PQR的析取范式，合取范式、主析取范式，主合取范式．8．設(shè)謂詞公式．（1）試寫出量詞的轄域；（2）指出該公式的自由變?cè)图s束變?cè)?．設(shè)個(gè)體域?yàn)镈={a1,a2}，求謂詞公式(y)(x)P(x,y)消去量詞后的等值式；三、證明題1．對(duì)任意三個(gè)集合A,B和C，試證明：若AB=AC，且A，則B=C．證明：（1）對(duì)于任意〈a，b〉∈AB，其中a∈A，b∈B，因?yàn)锳B=AC，必有〈a，b〉∈AC，其中b∈C，因此BC。（2）同理，對(duì)于任意〈a，c〉∈AC，其中a∈A，c∈C，因?yàn)锳B=AC，必有〈a，c〉∈AB，其中c∈B，因此CB。由（1）、（2）得：B=C．2．試證明：若R與S是集合A上的自反關(guān)系，則R∩S也是集合A上的自反關(guān)系．證明：若R與S是集合A上的自反關(guān)系，則任意x∈A,＜x,x＞∈R,＜x,x＞∈S,??從而＜x,x＞∈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的推論，圖