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

河南工業(yè)大學(xué)2016～2017學(xué)年第一學(xué)期期末考試試卷試卷編號：(D)卷課程編號：課程名稱：離散數(shù)學(xué)考試形式：閉卷 適用班級：姓名：學(xué)號：班級：學(xué)院：專業(yè)：考試日期：題號一二三四總分累分人簽名題分5020得分考生注意事項：請查看試卷中是否有缺頁或破損。如有立即舉手報告以便更換一、判斷題（每題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.矩陣的等價、相似、合同都是等價關(guān)系。()7.已知a是群集的二階元，則<a>={a,a2}.()8.有界格中某元的的補(bǔ)元不止一個，則它不是分配格。()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呼吸，在一階邏輯中，命題“凡人都呼吸”的符號化形式為。4.6階循環(huán)群有個子群。5.A={a,b},則A的冪集P(A)到自身的雙射有___個。6.A={1,2,3}，S是A的逆元是，該元是階元。7.一個3階有向圖的度序列是2，2，4，入度序列是2，0，2，出度序列是。8.一無向圖存在生成樹的充分必要條件是。9.最優(yōu)二叉樹有n片樹葉，則它有分支點。10.下圖的點連通度等于，邊連通度等于。三、計算題（每小題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）畫出的R的關(guān)系圖；（2）求R的自反、對稱、傳遞閉包；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.在一個無向圖中有6條邊，3度頂點和5度頂點各1個，其余頂點都是2度點，該圖有幾個頂點？5.在下圖中，用克魯斯卡爾算法構(gòu)造最小生成樹，寫出邊添加到生成樹的邊序列，并畫出生成樹。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