PAGE2PAGE3一、單項選擇題（每小題3分，本題共15分）1．若集合A＝{1,2,3,4}，則下列表述不正確的是()．A．1AB．{1,2,3}AC．{1,2,3}AD．A2．設A＝｛1,2,3｝，B={1,2,3,4}，A到B的關系R＝｛〈x,y〉|x=y｝，則R為()．A.{<1,2>,<2,3>}B.{<1,1>,<1,2>,<1,3>,<1,4>,<1,5>}C.{<1,1>,<2,1>}D.{<1,1>,<2,2>,<3,3>}3．無向圖G的邊數(shù)是10，則圖G的結(jié)點度數(shù)之和為（）．A.10B.20C.30D.54．設連通平面圖G有v個結(jié)點，e條邊，r個面，則（）．A．r+v-e=2B．v+e-r=4C．v+e–r=–4D．v+e-r=2 5．設個體域D是整數(shù)集合，則命題xy(x=y+2)的真值是（）．A.不確定B.T C.由y的取值確定D.F 二、填空題（每小題3分，本題共15分）6．設集合A={a,b,c}，B={b,c,d}，C={c,d,e}，則(BC)–A等于．7．設A={2,3}，B={1,2}，C={3,4}，從A到B的函數(shù)f={<2,2>,<3,1>}，從B到C的函數(shù)g={<1，3>,<2，4>}，則Dom(gf)等于．8．若圖G=<V,E>，其中V={a,b,c,d}，E={(a,b),(a,d),(b,c),(b,d)}，則該圖中的割邊為．9．設G是漢密爾頓圖，S是其結(jié)點集的一個子集，若S的元素個數(shù)為6，則在G-S中的連通分支數(shù)不超過．10．設個體域D＝{1,2,3,4}，A(x)為“x小于10”，則謂詞公式(x)A(x)的真值為．三、邏輯公式翻譯（每小題6分，本題共12分）11．將語句“小明是學生，小張是飛行員．”翻譯成命題公式．12．將語句“當大家都進入教室，則討論會開始進行．”翻譯成命題公式．四、判斷說明題（判斷各題正誤，并說明理由．每小題7分，本題共14分）13．空集的冪集是空集．14．(x)(P(x)→Q(y)∨R(z))中的約束變元有x與y．五．計算題（每小題12分，本題共36分）15．設A={1,2,3}，R={<x,y>|xA，yA且x+y=4}，S={<x,y>|xA，yA且x=y}，試求R，S，R-1，r(S)．16．圖G=<V,E>，其中V={a,b,c,d,e}，E={(a,b),(a,c),(a,d),(b,c),(b,d),(c,d),(c,e),(d,e)}，對應邊的權值依次為2、3、4、5、6、7，6及2，試（1）畫出G的圖形；（2）寫出G的鄰接矩陣；（3）求出G權最小的生成樹及其權值．17．試畫一棵帶權為1,2,4,5,6的最優(yōu)二叉樹,并計算該最優(yōu)二叉樹的權．六、證明題（本題共8分）18．試證明：P→QP→（(P∨Q)）．

離散數(shù)學（本）2016年10月份試題參考解答一、單項選擇題（每小題3分，本題共15分）1．C2．D3．B4．A5．B二、填空題（每小題3分，本題共15分）6．uqm66k67．{2，3}8．(b,c)9．610．真（或T，或1）三、邏輯公式翻譯（每小題6分，本題共12分）11．設P：小明是學生，Q：小張是飛行員．（2分）則命題公式為：P∧Q．（6分）12．設P：大家都進入教室，Q：討論會開始進行．（2分）則命題公式為：P→Q．（6分）四、判斷說明題（每小題7分，本題共14分）13．錯誤．（3分）空集的冪集不為空，為{}（7分）14．錯誤．（3分）約束變元僅有x．（7分）五．計算題（每小題12分，本題共36分）15．解：R={<1,3>,<2,2>,<3,1>}（3分）S={<1,1>,<2,2>,<3,3>}（6分）R-1={<3,1>,<2,2>,<1,3>}（9分）r(S)={<1,1>,<2,2>,<3,3>}（12分）說明：對于每一個求解項，如果基本求出了解，可以給對應1分．16．解：（1）G的圖形表示為：（3分）（2）鄰接矩陣：（6分）（3）粗線表示的圖是最小生成樹，（10分）權值為11（12分）1256347111817．解：（10分）權為13+23+42+52+62=39．（12分）六、證明題（本題共8分） 18．證明：（1）P→QP（1分）（2）PP（附加前提）（3分）（3）QT（1）（2）I（5分）（4）P∧QT（2）（3）I（6分）（5）(P∨Q)T（4）E（7分）（6）P→(P∨Q)CP規(guī)則（8分）另證：設P→（(P∨Q)）為F，（1分）則P為T，(P∨Q)為F，（3分）即P∧Q為F．（4分）所以P為T，Q為F，（5分）從而P→Q也為F．