2024年7月全國(guó)自考離散數(shù)學(xué)試題試卷真題及答案

7月全國(guó)自考離散數(shù)學(xué)試題試卷真題一、單項(xiàng)選擇題（本大題共15小題，每題1分，共15分）1．下列語(yǔ)句中不是命題的只有（）A．雞毛也能飛上天？ B．或重于泰山，或輕于鴻毛。C．不經(jīng)一事，不長(zhǎng)一智。 D．牙好，胃口就好。2．從真值角度看，命題公式的所有類(lèi)型是（）A．永真式B．永假式C．永真式，永假式D．永真式，永假式，可滿足式3．設(shè)M（x）：x是人；F（x）：x要吃飯。用謂詞公式體現(xiàn)下述命題：所有的人都要吃飯，其中錯(cuò)誤的體現(xiàn)式是（）A． B．C． D．4．下列公式是前束范式的是（）A． B．C． D．5．設(shè)論域?yàn)檎麛?shù)集，下列真值為真的公式是（）A． B．C． D．6．下列是謂詞演算中的合式公式的是（）A．B．C．D．（）．（）（）A．B．C．D．．（）8．下列式子對(duì)的的是（）A．（A－B）-C=A-（B∪C） B．A－（B∪C）=（A－B）∪CC．~（A－B）=~（B－A） D．~（A∩B）A9．下列集合對(duì)所給的運(yùn)算是封閉的只有（）A．非零整數(shù)集合Z*上的除法運(yùn)算B．全體n×n實(shí)可逆矩陣集合Mn（R）上的矩陣加法和乘法運(yùn)算C．全體n×n實(shí)矩陣集合Mn（R）上的矩陣加法和乘法運(yùn)算D．A={1，2，…，10}，x*y=LCM（x，y），即x，y最小公倍數(shù)10．設(shè)<A，eq\o\ac(○,+)，*>是環(huán)，則下列說(shuō)法不對(duì)的的是（）A．<A，eq\o\ac(○,+)>是互換群 B．<A，*>是半群C．*對(duì)eq\o\ac(○,+)是可分派的 D．eq\o\ac(○,+)對(duì)*是可分派的11．下列四個(gè)格，是分派格的是（）12．下列各圖是無(wú)向完全圖的是（）13．下列各有向圖是強(qiáng)連通圖的是（）14．設(shè)Ｇ是具有n個(gè)結(jié)點(diǎn)的無(wú)向簡(jiǎn)樸圖，若在Ｇ中存在一條漢密爾頓路，則Ｇ中每一對(duì)結(jié)點(diǎn)的度數(shù)之和與n-1的關(guān)系為（）A．不小于B．不小于等于C．等于D．不不小于15．設(shè)連通平面圖Ｇ，共有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分） 請(qǐng)?jiān)诿款}的空格中填上對(duì)的答案。錯(cuò)填、不填均無(wú)分。16．所謂___是指不能再分解的命題，而復(fù)合命題是由某些____通過(guò)聯(lián)結(jié)詞復(fù)合而成的命題。17．在命題演算中，兩個(gè)____的合取、析取、條件、雙條件均為_(kāi)___。18．使公式成立的條件是____中不含y，____中不含x。19．設(shè)A={1，2，3，4}，R是A上的二元關(guān)系，R={<x,y>|x/y是素?cái)?shù)}，則domR=_____;ranR=____。20．設(shè)無(wú)向圖Ｇ有n個(gè)結(jié)點(diǎn)m條邊，每個(gè)結(jié)點(diǎn)的度數(shù)為k或k+1，記Nk為度數(shù)等于k的結(jié)點(diǎn)數(shù)，則Nk=_____。假如無(wú)向簡(jiǎn)樸圖C的結(jié)點(diǎn)的度數(shù)均為相似的偶數(shù)，且m=7，則n=____。21．設(shè)X={1，3，5，9，15，45}，R是X上的整除關(guān)系，則R是X上的偏序，其最大元是___，極小元是____。22．設(shè)<>是有界格，a,bL,若ab=0,則a=b=_____；若ab=1,則a=b=____。23．設(shè)e是群G上的幺元，若aG且a2=e,則a-1=____,a-2=__________。24．代數(shù)系統(tǒng)<A,。>，其中A為命題公式集合，。為析取運(yùn)算，則<A，。>中零元素是____，幺元是____。25．樹(shù)是不包括_____的___圖。三、計(jì)算題（本大題共6小題，第26、27題各4分，第28、29題各5分，第30、31題各6分，共30分）26．假如論域是集合{a,b,c}，試消去下面公式中的量詞：27．求公式（的主析取范式。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ù)下列條件假如能畫(huà)則請(qǐng)畫(huà)出一種歐拉圖，假如不能畫(huà)則請(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)成格？并闡明理由。1)L={1,2,3,4,5}2)L={1,2,3,6,12}3)L={1,2,3,4,6,9,12,18,36}4)L={1,2,22,23,…,2n}31．設(shè)A={2，3，5，12，19}，等價(jià)關(guān)系R={<x,y>|x,(mod3)},寫(xiě)出各元素的等價(jià)類(lèi)，并求A/R。四、證明題（本大題共3小題，第32、33題各6分，第34題8分，共20分）32．用等價(jià)變換法證明：是永真式。33．若無(wú)向圖G是歐拉圖，G中與否存在割邊？為何？34．設(shè)A是一種集合，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）若要使所有村莊之間均有通路，問(wèn)需在兩村之間至少修幾條路？（2）若要使任意兩村莊之間有一條直接的路，則至少修幾種路？（3）若修一條連接所有村莊的環(huán)路，問(wèn)有多少種修路方案？36．設(shè)有推理：(a)沒(méi)有不守信用的人是可信賴的；(b)有些可以信賴的