蚌埠工商學(xué)院《離散數(shù)學(xué)》2017-2018期末試卷

蚌埠工商學(xué)院2017-2018學(xué)年第一學(xué)期考生姓名：學(xué)號：專業(yè)班名：一、選擇題（每小題3分,共15分,答案請寫在下框中）123451.公式軍vxvy(F(x)^G(y)喻H(x,y))等值于下面哪個公式()A.3xvy(F(x)^G(y)^軍H(x,y))B2.下圖中既不是歐拉圖，也不是哈密爾頓圖的圖是()3.設(shè)集合X={1,2,3,4,5,6,7,8,9}，則下列是X的劃分的是()4.設(shè)A為整數(shù)集合，R為A上的關(guān)系且R={<x,y>|x≥y},則R不具有的性質(zhì)是()A.自反性B.反自反性C.反對稱性D.傳遞性5.如圖所示，以下集合中是點割集是()二、填空題（每小題3分，共15分）1.設(shè)F(x):x是人,G(x):x是考試滿分的,H(x):x是考試不及格的.命題“雖然有些同學(xué)考試沒有滿分,但也不是所有的人考試都及格.”符號化為:2.P(x,y)為二元謂詞,給定解釋:D={a,b},P(a,a)=P(b,a)=1,P(a,b)=P(b,b)=0,求公式二xvyP(x,y)在該解釋下的真值 3.權(quán)為2,3,4,6,8,10的最優(yōu)二叉樹T的權(quán)是 4.設(shè)集合A={0,1,2,3},B={x|x2≤2且x是整數(shù)},則A①B=5.含pqr命題變項公式中,全部成真賦值為110和111的最簡公式為三、計算證明題（共70分，答案請寫在答題紙上）110分）利用等值演算求公式(q喻r)^(p喻q)的主析取范式和主合取范式,并求成真賦值和成假賦值.2.（8分）構(gòu)造下面推理的證明:如果他是計算機系本科生或計算機系研究生,那么他一定學(xué)過Java語言而且學(xué)過C語言.只要他學(xué)過Java語言或C語言,那么他就會編程.因此,如果他是計算機系本科生,那么他就會編程.3.（8分）已知R是建立在冪集P({a,b,c})上的包含關(guān)系,請畫出R的哈斯圖,并指出極大元、極小元、最大元和最小元,并求集合B={{a},{a,b},{a,c}}的上界、上確界、下界和下確界.4.（12分1）用Dijkstra標號法,求圖從點b到其余各點的最短路徑及長度；（2）求該圖所對應(yīng)的基圖的最小生成樹及其權(quán)值.516分）已知集合A={a,b,c,d}及A上的三個關(guān)系為R1,R2,R3,具體如下:R2R3,將結(jié)果用集合表示.（2）求關(guān)系R1的對稱閉包s(R1)和傳遞閉包t(R1),將結(jié)果用集合表示,并判斷t(R1)是否為偏序關(guān)系(需給出理由).（3）R1,R2,R3中哪些是等價關(guān)系,請說明理由,并求等價關(guān)系的等價類及A在此關(guān)系下的商集.6.（10分）已知以下字母在通信中出現(xiàn)的頻率如下:字母ABCDEFGH頻率25%20%5%5%（1）編制最佳2元前綴碼,寫出每個字母對應(yīng)的編碼及編碼長度;（2）傳輸100個按上述比例的字母需多少個二進制數(shù)字,比等長編