山西中醫(yī)藥大學(xué)《離散數(shù)學(xué)》2018-2019學(xué)年期末試卷

山西中醫(yī)藥大學(xué)期末課程考核2018-2019學(xué)年第一學(xué)期《離散數(shù)學(xué)》一二三四五一、單項(xiàng)選擇題(本大題共15小題，每小題1分，共15分)1．下列語(yǔ)句中不是命題的只有A．雞毛也能飛上天?B．或重于泰山，或輕于鴻毛。C．不經(jīng)一事，不長(zhǎng)一智。D．牙好，胃口就好。2．從真值角度看，命題公式的全部類型是【【】】A．永真式B．永假式C．永真式，永假式D．永真式，永假式，可滿足式3．設(shè)M(x)：x是人；F(x)：x要吃飯。用謂詞公式表達(dá)下述命題：所有的人都要吃飯，其中錯(cuò)誤的表達(dá)式是【】14．設(shè)G是具有n個(gè)結(jié)點(diǎn)的無向簡(jiǎn)單圖，若在G中存在一條漢密爾頓路，則G中每一對(duì)結(jié)點(diǎn)的度數(shù)之和與n-l的關(guān)系為【】A．大于B．大于等于C．等于D．小于15．設(shè)連通平面圈G，共有n個(gè)結(jié)點(diǎn)，e條邊，r個(gè)面，則歐拉證明成立的公式是【】A．e-n+r=2B．n+r-e=2C．n-r+e=2D．n-e-r=2二、填空題(本大題共10小題，每小題2分，共20分)16．所謂是指不能再分解的命題，而復(fù)合命題是由一些經(jīng)過聯(lián)結(jié)詞復(fù)合而成的命題。17．在命題演算中，兩個(gè)的合取、析取、條件、雙條件均為。20．設(shè)無向圖G有n個(gè)結(jié)點(diǎn)m條邊，每個(gè)結(jié)點(diǎn)的度數(shù)為k或k+1，記Nk為度數(shù)等于k的結(jié)點(diǎn)數(shù)，則Nk=。如果無向簡(jiǎn)單圖G的結(jié)點(diǎn)的度數(shù)均為相同的偶數(shù)，且m=7，則n=。21．設(shè)X={1，3，5，9，15，45}，R是X上的整除關(guān)系，則R是X上的偏序，其最大元是 三、計(jì)算題(本大題共6小題，第26、27題各4分，第28、29題各5分，第30、3l題各6分，共30分)26．如果論域是集合{a．b，c}，試消去下面公式中的量詞：((vx)(二y)(x+y=0)28．設(shè)A={a，b．c}，A上二元關(guān)系R={(a，a)，(a，c)，(b，a)}，用關(guān)系矩陣法求最小的自然數(shù)m，n，m<n使Rm=Rn。29．根據(jù)下列條件如果能畫則請(qǐng)畫出一個(gè)歐拉圖，如果不能畫則請(qǐng)說明理由。(1)偶數(shù)個(gè)頂點(diǎn)，偶數(shù)條邊(2)奇數(shù)個(gè)頂點(diǎn)，奇數(shù)條邊(3)偶數(shù)個(gè)頂點(diǎn)，奇數(shù)條邊(4)奇數(shù)個(gè)頂點(diǎn)，偶數(shù)條邊30．下列各整數(shù)集合對(duì)于整除關(guān)系“”都構(gòu)成偏序集．判斷哪些偏序集能構(gòu)成格?并說明理由。31．設(shè)A={2，3，5，12，19}，等價(jià)元素的等價(jià)類，并求A／R。四、證明題(本大題共3小題，第32、33題各6分，第34題8分，共20分)32．用等價(jià)變換法證明：(P喻Q)喻((R喻Q)喻((P量R)喻Q))是永真式。33．若無向圖C是歐拉圖，G中是否存在割邊?為什么?34．設(shè)A是一個(gè)集合，X=P(A)，R是X上元素之間的包含關(guān)系，試證明(X，R)是偏序集。(注：P(A)為A的冪集)五、應(yīng)用題(本大題共2小題，第35題6分，第36題9分，共15分)35．設(shè)有n個(gè)村莊要修路，(1)若要使所有村莊之間都有通路，問需在兩村之間至少修幾條路?(2)若要使任意兩村莊之間有一條直接的路，則至少修幾條路?(3)若修一條連接所有村莊的環(huán)路，問有多少種修路方案?36．設(shè)有推理：(a)沒有不守信用的人是可信賴的；(b)有些可以信賴的人是受過教育的人；(c)因此有些受過教育的人是守信用的。試構(gòu)造推理的證明，