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

蚌埠工商學(xué)院2019-2020學(xué)年第二學(xué)期期末考生姓名：學(xué)號：專業(yè)班名：一、選擇題（每小題3分,共15分,答案請寫在下框中）123451.下列圖中不含有哈密頓通路的是()ABCD2.設(shè)A為整數(shù)集合，R為A上的關(guān)系且R={<x,y>|x=y},則R不具有的性質(zhì)是()A.自反性B.反自反性C.反對稱性D.傳遞性3.一個無向圖有4個頂點，有3個度數(shù)為2,3,3，則第4個結(jié)點度數(shù)不可能是()A.0B.1C.2D.44.如圖，以下集合中不是邊割集是()A.{e1,e2}B.{e1,e3,e5,e6}C.{e5,e6,e7,e9}D.{e8}5.如圖,生成樹為邊集{a,b,c,d}導(dǎo)出的子圖,以下集合不是基本割集的是()A.{a,f,g}B.{b,e,f,g}C.{c,e,f,d}D.{c,e,f,g}二、填空題（每小題3分，共15分）},若D的鄰接矩陣為A=|1010|,則從v2到v4的長度為2的通路數(shù)目為條.2.權(quán)為2,2,4,6,8,10的最優(yōu)二叉樹T的權(quán)是3.令F(x):x是人,G(x):x喜歡吃饅頭,H(x):x喜歡吃米飯。命題“雖然有人不喜歡吃饅頭，但也不是所有人都喜歡吃米飯.”的符號化形式為4.設(shè)P(x,y)為二元謂詞,給定如下解釋:D={a,b},P(a,a)=P(b,a)=1,P(a,b)=P(b,b)=0,求公式vx3yP(x,y)在該解釋下的真值5.設(shè)集合A={0,1,2,3},B={x|x2<2且x是自然數(shù)},則A④B=三、計算證明題（共70分，答案請寫在答題紙上）110分）利用等值演算求公式(pq)^(qr)^(rp)的主析取范式和主合取范式,并求成真賦值和成假賦值.2.（10分）構(gòu)造下面推理的證明:如果他是數(shù)學(xué)系本科生,那么他一定學(xué)過《數(shù)學(xué)分析》和《高等代數(shù)》.只要他學(xué)過《數(shù)學(xué)分析》或《高等代數(shù)》,那么他就學(xué)過《離散數(shù)學(xué)》.因此,如果他是數(shù)學(xué)系本科生,那么他就學(xué)過《離散數(shù)學(xué)》.4.（10分）已知R是建立在集合A={1,2,3,5,6,9,18,27,36,54}上的整除關(guān)系,請畫出R的哈斯圖,并指出極大元、極小元、最大元和最小元,并求集合B={3,6,9}的上界、上確界、下界和下確界.516分）設(shè)R為集合A={a,b,c,d}上的二元關(guān)系,R={<a,c>,<b,a><b,c>,<c,d>,<d,d>},計算:（1）R的關(guān)系矩陣及關(guān)系圖.（2）判斷R的性質(zhì),并給出理由.（3）計算R的自反閉包r(R),對稱閉包s(R),傳遞閉包t(R),用集合方式表示.（4）在關(guān)系R中添加最少的有序?qū)κ蛊涑蔀锳上的偏序關(guān)系T,求添加的有序?qū)?6.（9分）求權(quán)為5、5、5、10、10、15、20、30的最優(yōu)二叉樹