PAGE2PAGE3一、單項(xiàng)選擇題（每小題3分，本題共15分）1．若集合A＝{1,2,3}，則下列表述不正確的是()．A．1AB．{1}AC．AD．{2}A2．設(shè)A={2,3｝，B={3,4}，A到B的關(guān)系R={<x,y>|xA,yB，且x不大于y｝，則R=()．A．{<3,3>,<4,4>}B．{<2,3>,<2,4>,<3,3>,<3,4>}C．{<2,3>,<2,4>,<3,4>}D．{<2,2>,<3,3>,<4,4>}3．無向圖G的結(jié)點(diǎn)的度數(shù)之和是24，則圖G的邊數(shù)為（）．A．12B．24C．48D．234．設(shè)連通平面圖G有v個(gè)結(jié)點(diǎn)，e條邊，r個(gè)面，則（）．A．v+e–r=–4B．v+e-r=4C．v+e-r=2D．r+v-e=2 5．設(shè)個(gè)體域D是實(shí)數(shù)集合，則命題(x)(y)(xy=y)的真值是（）．A．TB．F C．由y的取值確定D．不確定 二、填空題（每小題3分，本題共15分）6．設(shè)集合A={a,b}，B={b,c}，C={c,d}，則(AB)–(BC)=．7．設(shè)A={3，6}，B={1，6}，C={3，5}，從A到B的函數(shù)f={<3,1>,<6,6>}，從B到C的函數(shù)g={<1，3>,<6，5>}，則Dom(gf)=．8．結(jié)點(diǎn)數(shù)相等是兩個(gè)圖同構(gòu)的條件．9．設(shè)G是漢密爾頓圖，S是其結(jié)點(diǎn)集的一個(gè)子集，若S的元素個(gè)數(shù)為4，則在G-S中的連通分支數(shù)不超過．10．設(shè)個(gè)體域D＝{a,b}，則謂詞公式(x)Q(x)消去量詞后的等值式為．三、邏輯公式翻譯（每小題6分，本題共12分）11．將語句“昨天是公休日，今天也是公休日．”翻譯成命題公式．12．將語句“如果今天是周五，則明天是周四．”翻譯成命題公式．四、判斷說明題（判斷各題正誤，并說明理由．每小題7分，本題共14分）13．如果A是集合B的元素，則A不可能是B的子集．14．(x)(A(x)→(B(y)→C(z)))中的約束變?cè)獮閥．五．計(jì)算題（每小題12分，本題共36分）15．設(shè)A={1，2，3}，R={<x，y>|xA，yA且x>y}，S={<x，y>|xA，yA且xy}，試求R，S，R-1，s(S)．16．設(shè)圖G=<V,E>，其中，結(jié)點(diǎn)集V={a,b,c,d,e}，邊集E={(a,c),(a,e),(b,d),(b,e),(c,e),(d,e)}，對(duì)應(yīng)邊的權(quán)值依次為2、3、3、4、1及5，請(qǐng)畫出G的圖形、寫出G的鄰接矩陣并求出G權(quán)最小的生成樹及其權(quán)值．17．畫一棵帶權(quán)為1,2,3,4,5的最優(yōu)二叉樹,并計(jì)算該最優(yōu)二叉樹的權(quán)．六、證明題（本題共8分）18．試證明：P→QP→(P∧Q)．

離散數(shù)學(xué)（本）2018年10月份試題參考解答一、單項(xiàng)選擇題（每小題3分，本題共15分）1．C2．B3．A4．D5．A二、填空題（每小題3分，本題共15分）6．{a,b}7．{3，6}8．必要9．410．Q(a)∧Q(b)三、邏輯公式翻譯（每小題6分，本題共12分）11．設(shè)P：昨天是公休日，Q：今天是公休日．（2分）則命題公式為：P∧Q．（6分）12．設(shè)P：今天是周五，Q：明天是周四．（2分）則命題公式為：P→Q．（6分）四、判斷說明題（每小題7分，本題共14分）13．錯(cuò)誤．（3分）反例：設(shè)A={1}，B={1,{1}}，則A是B的元素，也是B的子集．（7分）說明：舉出符合條件的反例均給分．14．錯(cuò)誤．（3分）(x)(A(x)→(B(y)→C(z)))中的y是自由變?cè)?，約束變?cè)獮閤．（7分）五．計(jì)算題（每小題12分，本題共36分）15．R={<2,1>,<3,1>,<3,2>}（3分）S={<1,1>,<1,2>,<1,3>,<2,2>,<2,3>,<3,3>}（6分）R-1={<1,2>,<1,3>,<2,3>}（9分）s(S)={<1,1>,<2,1>,<1,2>,<3,1>,<1,3>,<2,2>,<3,2>,<2,3>,<3,3>}（12分）說明：對(duì)于每一個(gè)求解項(xiàng)，如果基本求出了解，可以給對(duì)應(yīng)1分．16．G的圖形表示為：（3分）鄰接矩陣：（6分）如下為最小的生成樹，權(quán)為10：（9分）（12分）17．（10分）權(quán)為13+23+32+42+52=33（12分）六、證明題（本題共8分） 18．證明：（1）P→QP（1分）（2）PP（附加前提）（3分）（3）QT（1）（2）I（5分）（4）P∧QT（2）（3）I（7分）（5）P→(P∧Q)CP規(guī)則（8分）說明1：因證明過程中，公式引用的次序可以不同，一般引用前提正確得1分，利用兩個(gè)公式得出有效結(jié)論得1或2分，最后得出結(jié)論得2或1分。說明2：另證如下：設(shè)P→(P∧Q)為F，（1分）則P為T，PQ為F。（3分）所以P為T，Q為F，