河南工業(yè)大學(xué)《離散數(shù)學(xué)》試卷2016-2017年第一學(xué)期期末試卷D卷

河南工業(yè)大學(xué)2016～2017學(xué)年第一學(xué)期期末考試試卷試卷編號(hào)：(D)卷課程編號(hào)：課程名稱：離散數(shù)學(xué)考試形式：閉卷 適用班級(jí)：姓名：學(xué)號(hào)：班級(jí)：學(xué)院：專業(yè)：考試日期：題號(hào)一二三四總分累分人簽名題分5020得分考生注意事項(xiàng)：請(qǐng)查看試卷中是否有缺頁(yè)或破損。如有立即舉手報(bào)告以便更換一、判斷題（每題1分，共10分）1.任何命題公式都存在惟一的析取范式。()2.封閉的公式在任何解釋下都變成命題。()3.(pq)(rs)的層數(shù)是34.x(BA(x))x(BA(x)).()5.設(shè)A,B,C是三集合，已知AB＝AC，則一定有B＝C.()6.矩陣的等價(jià)、相似、合同都是等價(jià)關(guān)系。()7.已知a是群集的二階元，則<a>={a,a2}.()8.有界格中某元的的補(bǔ)元不止一個(gè)，則它不是分配格。()9.有向圖是強(qiáng)連通的，則它一定是單向連通的，也弱連通的。()10.二部圖K3,3是歐拉圖也是哈密頓圖。()二、填空題（每小題2分，共20分）1.((pq)q)p從公式的類型看，它屬于式。2.x(A(x)B(x))。3.設(shè)F(x):x是人，H(x):x呼吸，在一階邏輯中，命題“凡人都呼吸”的符號(hào)化形式為。4.6階循環(huán)群有個(gè)子群。5.A={a,b},則A的冪集P(A)到自身的雙射有___個(gè)。6.A={1,2,3}，S是A的逆元是，該元是階元。7.一個(gè)3階有向圖的度序列是2，2，4，入度序列是2，0，2，出度序列是。8.一無(wú)向圖存在生成樹(shù)的充分必要條件是。9.最優(yōu)二叉樹(shù)有n片樹(shù)葉，則它有分支點(diǎn)。10.下圖的點(diǎn)連通度等于，邊連通度等于。三、計(jì)算題（每小題10分，共50分）1.設(shè)A={a,b,c},B={b,c,d},C={d,e,f},R1={<1,2>,<2,2>,<2,3>,<3,3>},R2={<2,2>,<2,3>,<3,4>}求121在A上的限制。2.其中，A={1，2，3，4}，R={<1,2>,<2,2>,<2,3>,<3,4>},R是A上的二元關(guān)系。（1）畫(huà)出的R的關(guān)系圖；（2）求R的自反、對(duì)稱、傳遞閉包；3.S=Q×Q,其中Q為有理數(shù)集合，定義S上的二元運(yùn)算*，<a,b>,<x,y>∈S，<a,b>*<x,y>=<ax,ay+b>,(1)求<3,4>*<1,2>.(2)已知<-1,3>*<a,b>=<-5,1>,求a,b.(3)*是可交換的嗎？是可結(jié)合的嗎？4.在一個(gè)無(wú)向圖中有6條邊，3度頂點(diǎn)和5度頂點(diǎn)各1個(gè)，其余頂點(diǎn)都是2度點(diǎn)，該圖有幾個(gè)頂點(diǎn)？5.在下圖中，用克魯斯卡爾算法構(gòu)造最小生成樹(shù)，寫(xiě)出邊添加到生成樹(shù)的邊序列，并畫(huà)出生成樹(shù)。ff2e75四、證明題（共20分）1.前提：軍3x(F(x)^H(x)),vx(G(x)喻H(x))結(jié)論:vx(G(x)喻軍F(x))EQ\*jc3\*hps23\o\al(\s\up8(a),0)EQ\*jc3\*hps23\o\al(\s\up10(0