2009年7月自考離散數(shù)學(xué)試題

1、全國2009年7月自考離散數(shù)學(xué)試題課程代碼：02324一、單項(xiàng)選擇題(本大題共15小題，每小題1分，共15分)在每小題列出的四個備選項(xiàng)中只有一個是符合題目要求的，請將其代碼填寫在題后的括號內(nèi)。錯選、多選或未選均無分。1.下列句子為命題的是( )A.走，看電影去B.x+y0C.空集是任意集合的真子集D.你明天能來嗎?2.下列式子不是謂詞合式公式的是( )A.(x)(P(x)($x)(Q(x) A(x，y)B.(x)($y)P(x，y)C.(x)P(x)R(y)D.($x)P(x)Q(y，z)3.下列式子為重言式的是( )A.PPQB.(PQ)(PQ)C. (P Q)D.(PQ) (PQ)4.設(shè)個

2、體域?yàn)閷?shí)數(shù)集，特定元素a=0，函數(shù)f(x，y)=x-y，特定謂詞F(x，y)為xy，下列公式真值為真的是( )A.(x)(y)F(x，f(f(x，y)，y)B.(x)(y)(F(f(x，y)，x)C.(x)(y)(z)(F(x，y)F(f(x，z)，f(y，z)D.(x)F(f(a，x)，a)5.對于公式(x)(y)P(x，y)Q(x，z)($x)P(x，y)，下列說法正確的是( )A.x是自由變元B.x是約束變元C.( x)的轄域是P(x，y)Q(x，z)D.(x)的轄域是P(x，y)6.設(shè)論域?yàn)?，2，與公式(x)A(X)等價的是( )A. A(1) A(2)B. A(1)(A2)C. A

3、(1) A(2)D. A(1) A(2)7.設(shè)Z+是正整數(shù)集，f：Z+Z+Z+，f(n，m)=nm，則f( )A.僅是入射B.僅是滿射C.是雙射D.不是函數(shù)8.下列哪個關(guān)系矩陣所對應(yīng)的關(guān)系具有自反性( )A.B.C.D.9.設(shè)R1和R2是集合A上的相容關(guān)系，下列關(guān)系哪個可能不是相容關(guān)系( )A.R1R2B.RlR2C.R1-1D.RlR210.在整數(shù)集上，下面哪個運(yùn)算不是二元運(yùn)算( )A.加法B.減法C.乘法D.除法11.設(shè)A是奇數(shù)集合，為乘法運(yùn)算，則是( )A.半群B.群C.循環(huán)群D.交換群12.下面不滿足結(jié)合律的運(yùn)算是( )A.a*b=min(a，b)B.a*b=max(a，b)C.a*b

4、=2(a+b)D.a*b=2ab13.右圖的最小入度是( )A.0B.1C.2D.314.下面既是漢密爾頓圖又是歐拉圖的圖形是( )15.一棵樹有3個5度點(diǎn)、1個4度點(diǎn)、3個2度點(diǎn)，其它的都是1度，那么它的邊數(shù)是( )A.17B.18C.19D.20二、填空題(本大題共10小題，每小題2分，共20分)請?jiān)诿啃☆}的空格中填上正確答案。錯填、不填均無分。16.設(shè)命題變元為P，Q，R，則小項(xiàng)m100=_，大項(xiàng)M010=_。17.置換規(guī)則：在證明的任何步驟上，命題公式中的任何子命題公式都可以_，記為_規(guī)則。18.一個公式，如果量詞均在全式的_，其作用域延伸到整個公式的_，則該公式稱為前束范式。19.請

5、用聯(lián)結(jié)詞，表示聯(lián)結(jié)詞和聯(lián)結(jié)詞 ：_，_。20.設(shè)A=l，2，3，4，A上的二元關(guān)系R=，S=，則RS=_，(RS)-1=_。21.代數(shù)系統(tǒng)是整環(huán)，則是_，是_，且無零因子。22.在實(shí)數(shù)集R上定義運(yùn)算ab=a+b+ab，則幺元為_，元素2的逆元為_。23.若回路中，除_外_各不相同，則此回路稱為圈(或初級回路)。24.偶圖記為Kn,m那么當(dāng)_時，Kn,m是平面圖，當(dāng)_時，Kn,m是非平面圖。25.若圖中存在_，它經(jīng)過圖中所有的邊恰好_次，則稱該圖為歐拉圖。三、計(jì)算題(本大題共6小題，每小題5分，共30分)26.用等值演算求(PQ)R的主合取范式。27.列出(P(QR) (PQ)的真值表。28設(shè)A=a,b,c,d，R=，求R的傳遞閉包。29.設(shè)A=2，3，6，12，24，36，請畫出A上整除關(guān)系的哈斯圖，并給出子集6，12，24，36的下界、下確界、極大元、最大元。30.求右圖所示格的所有5元子格。31.用矩陣的方法求右圖中結(jié)點(diǎn)u2，u5之間長為2的路徑的數(shù)目。四、證明題(本大題共3小題，第32小題8分，第33、34小題各6分，共20分)32.用推理方法證明：PQ，PR，QSRS。33.設(shè)A=|a，bZ+，Z+為整數(shù)集，A上的關(guān)系R=,|ad=bc，證明R是等價關(guān)系。34證明：一個圖是強(qiáng)連通的，當(dāng)且僅當(dāng)圖中有一個回路，它至少包含每個結(jié)點(diǎn)一次。五、綜合應(yīng)用題（本大題共2小