山東工程職業(yè)技術(shù)大學(xué)《離散數(shù)學(xué)》2017-2018期末試卷B

1《離散數(shù)學(xué)》試卷（B）卷試中自覺(jué)遵守這些規(guī)定，保證按規(guī)定的程序和要求參加考試，如有違反，自愿按承諾人簽名：學(xué)號(hào)：班級(jí)：一．填空題（每空2分，共36分可能有多個(gè)答案）1．給出下列語(yǔ)句：（1）我正在說(shuō)謊。（2）7是自然數(shù)當(dāng)且僅當(dāng)海水是甜的。（3）x+7<0。（4）明年中秋節(jié)的晚上是晴天。其中是命題；是復(fù)合命題。2．設(shè)p：2+3=5，q：大熊貓產(chǎn)在中國(guó)，r：太陽(yáng)從西方升起，則公式(pqr)((pq)r)的真值為。3．給出下列命題：（1）(pq)(qp)（2）(qp)p（3）((pq)p)（4）((pq)(qr))(pr)其中是重言式，是矛盾式。4．設(shè)個(gè)體域D={a,b,c}，消去公式xF(x)→yG(y)的量詞為 。 5．判斷下列命題的真假（其中A,B,C,S,T均為集合,為空集答案寫(xiě)在括號(hào)中：（1）(ST)ST2）(AB)(BC)AC()6．令P（xx是質(zhì)數(shù)，E（xx是偶數(shù)，Q（xx是奇數(shù)，D（x，yx除盡y.則x(E(x)y(D(x,y)E(y)))為7．(x)(((y)P(x,y))((z)Q(z)R(x)))的前束范式是8．設(shè)G是具有8個(gè)頂點(diǎn)的樹(shù)，則G中增加條邊才能把G變成完全圖。9．給定集合A1,2,3上的3個(gè)關(guān)系如下：2R12R3}，則其中為等價(jià)關(guān)系的是。10．設(shè)f，g是自然數(shù)集N上的函數(shù)vxeN,f(x)=x+1,g(x)=2x，則f。g(x)=。11．給定集合X和Y，設(shè)|X|=n，|Y|=m則（1）從X到Y(jié)有個(gè)不同的函數(shù)；（2）當(dāng)n,m滿足時(shí)，從X到Y(jié)的函數(shù)才可為雙射。12．設(shè)G為9階無(wú)向圖，每個(gè)結(jié)點(diǎn)度數(shù)不是5就是6，則G中至少有個(gè)5度結(jié)點(diǎn)。13.設(shè)集合A,B，其中A＝{1,2,3},B={1,2},則A-B＝;二．選擇題（每小題2分，共16分）1．設(shè)p：張剛在圖書(shū)館看書(shū)，q：圖書(shū)館不開(kāi)門，r：張剛生病。命題“張剛總是在圖書(shū)館看書(shū)，除非圖書(shū)館不開(kāi)門或張剛生病?！狈?hào)化為：(A)(q∨r)→p；(C)p→(q∨r)；(D)p→﹁(q∨r)。3．以下命題中正確的結(jié)論是：(A)非空偏序集的子集如有上界，則一定有最小上界；(B)若非空偏序集的子集存在最小上界，則最小上界是唯一的；(C)若非空偏序集的子集存在極小元，則在哈斯圖中極小元不一定出現(xiàn)在最底層；(D)非空偏序集的子集一定有最大元。4．如右圖相對(duì)于完全圖K5的補(bǔ)圖為。35．設(shè)X={a,b,c,d}，Y={1,2,3}，f={<a,1>,<b,2>,<c,3>},則f是：。(A)從X到Y(jié)的二元關(guān)系，但不是從X到Y(jié)的函數(shù)；(B)從X到Y(jié)的函數(shù)，但不是滿射，也不是單射；(C)從X到Y(jié)的滿射，但不是單射；(D)從X到Y(jié)的雙射。6.設(shè)A,B為集合，當(dāng)()時(shí)A－B＝B.7.若供選擇答案中的數(shù)值表示一個(gè)簡(jiǎn)單圖中各個(gè)頂點(diǎn)的度，能畫(huà)出圖的是().(A)(1,2,2,3,4,5)(B)(1,2,3,4,5,5)(C)(1,1,1,2,3)(D)(2,3,3,4,5,6).8.設(shè)命題公式G＝軍(P喻Q)，H＝P喻(Q喻軍P)，則G與H的關(guān)系是()。(A)G牽H(B)H牽G(C)G＝H(D)以上三．解答題(共48分，請(qǐng)給出計(jì)算過(guò)程)16分）證明：對(duì)任意集合A,B,C有，An(B④C)=(AnB)④(AnC).2.（6分）設(shè)命題公式G=軍(P→Q)∨(Q∧(軍P→R)),求G的主析取范式。43.(5分)設(shè)一階邏輯公式：G=(VxP(x)∨二yQ(y))→VxR(x)，把G化成前束范式.4共10分）給出集合A={a,b,c,d,e}上的一個(gè)關(guān)系（1）寫(xiě)出它的關(guān)系矩陣A；（2）畫(huà)出它的關(guān)系圖；（3）寫(xiě)出它的自反閉包r(R)；（4）寫(xiě)出它的對(duì)稱閉包s(R)；（5）寫(xiě)出它的傳遞閉包t(R).55．(5分)有向圖D如圖所示（1）D中有多少條非同構(gòu)的初級(jí)回路圈？（2）有多少條非同構(gòu)的簡(jiǎn)單回路？（3）求a到d的短程線路和距離？（4）求d到a的短程線路和距離？（5）D是哪類連通圖？a—d—de 6.（8分）設(shè)集合A＝{1,2,3,4,6,8,9,12}，R為整除關(guān)系。(1)畫(huà)出半序集(A,R)的哈斯圖；(2)寫(xiě)出A的子集B={3,6,9,