離散數(shù)學(xué)試卷及答案

1、1一、單項(xiàng)選擇題(本大題共15小題，每小題1分，共15分)在每小題列出的四個(gè)選項(xiàng)中只有一個(gè)選項(xiàng)是符合題目要求的，請將正確選項(xiàng)前的字母填在題后的括號內(nèi)。1.一個(gè)連通的無向圖G，如果它的所有結(jié)點(diǎn)的度數(shù)都是偶數(shù)，那么它具有一條()A.漢密爾頓回路B.歐拉回路C.漢密爾頓通路D.初級回路2.設(shè)G是連通簡單平面圖，G中有11個(gè)頂點(diǎn)5個(gè)面，則G中的邊是()A.10B.12C.16D.143.在布爾代數(shù)L中，表達(dá)式(a∧b)∨(a∧b∧c)∨(b∧c

2、)的等價(jià)式是()A.b∧(a∨c)B.(a∧b)∨(a’∧b)C.(a∨b)∧(a∨b∨c)∧(b∨c)D.(b∨c)∧(a∨c)4.設(shè)i是虛數(shù)，是復(fù)數(shù)乘法運(yùn)算，則G=是群，下列是G的子群是()A.B.〈1〉C.〈i〉D.〈i〉5.設(shè)Z為整數(shù)集，A為集合，A的冪集為P(A)、、為數(shù)的加、減、除運(yùn)算，∩為集合的交運(yùn)算，下列系統(tǒng)中是代數(shù)系統(tǒng)的有()A.〈Z，，〉B.〈Z，〉C.〈Z，，〉D.〈P(A)，∩〉6.下列各代數(shù)系統(tǒng)中不含有零元素的

3、是()A.〈Q，〉Q是全體有理數(shù)集，是數(shù)的乘法運(yùn)算B.〈Mn(R)〉Mn(R)是全體n階實(shí)矩陣集合，是矩陣乘法運(yùn)算C.〈Z，〉，Z是整數(shù)集，定義為xxy=xyxy∈Z????D.〈Z，〉，Z是整數(shù)集，是數(shù)的加法運(yùn)算7.設(shè)A=123，A上二元關(guān)系R的關(guān)系圖如下：R具有的性質(zhì)是A.自反性B.對稱性C.傳遞性D.反自反性8.設(shè)A=abc，A上二元關(guān)系R=〈aa〉，〈bb〉〈ac〉，則關(guān)系R的對稱閉包S(R)是()A.R∪IAB.RC.R∪

4、〈ca〉D.R∩IA9.設(shè)X=abcIx是X上恒等關(guān)系，要使Ix∪〈ab〉，〈bc〉，〈ca〉，〈ba〉∪R為X上的等價(jià)關(guān)系，R應(yīng)取()A.｛〈ca〉，〈ac〉｝B.〈cb〉，〈ba〉C.〈ca〉，〈ba〉D.〈ac〉，〈cb〉10.下列式子正確的是()A.∈B.C.D.∈??????????11.設(shè)解釋R如下：論域D為實(shí)數(shù)集，a=0f(xy)=xyA(xy):xy.下列公式在R下為真的是()A.(x)(y)(z)(A(xy))

5、→A(f(xz)f(yz))???B.(x)A(f(ax)a)?C.(x)(y)（A(f(xy)x))??3整數(shù)，求(a1ba)nanbnan?28.(6分)設(shè)A=12345A上偏序關(guān)系R=〈1，2〉，〈3，2〉，〈4，1〉，〈4，2〉，〈4，3〉，〈3，5〉，〈4，5〉∪IA(1)作出偏序關(guān)系R的哈斯圖(2)令B=1235，求B的最大，最小元，極大、極小元，上界，下確界，下界，下確界。29.(6分)求┐(P→Q)(P→┐Q)的主合取范

6、式并給出所有使命題為真的賦值。?30.(5分)設(shè)帶權(quán)無向圖G如下，求G的最小生成樹T及T的權(quán)總和，要求寫出解的過程。31.(4分)求公式┐((x)F(xy)→(y)G(xy))∨(x)H(x)的前束范式。???四、證明題(共20分)32.(6分)設(shè)T是非平凡的無向樹，T中度數(shù)最大的頂點(diǎn)有2個(gè)，它們的度數(shù)為k(k≥2)證明T中至少有2k2片樹葉。33.(8分)設(shè)A是非空集合，F(xiàn)是所有從A到A的雙射函數(shù)的集合，是函數(shù)復(fù)合運(yùn)算。?證明：〈F〉

7、是群。?34.(6分)在個(gè)體域D=a1a2…，an中證明等價(jià)式：(x)(A(x)→B(x))(x)A(x)→(x)B(x)????五、應(yīng)用題(共15分)35.(9分)如果他是計(jì)算機(jī)系本科生或者是計(jì)算機(jī)系研究生，那么他一定學(xué)過DELPHI語言而且學(xué)過C語言。只要他學(xué)過DELPHI語言或者C語言，那么他就會編程序。因此如果他是計(jì)算機(jī)系本科生，那么他就會編程序。請用命題邏輯推理方法，證明該推理的有效結(jié)論。36.(6分)一次學(xué)術(shù)會議的理事會共有