安徽大學(xué)《離散數(shù)學(xué)》(上)試卷(A卷)及習(xí)題與講解

安徽大學(xué)20—20學(xué)年第1學(xué)期《離散數(shù)學(xué)》考試試卷（A卷）（時(shí)間120分鐘）院/系專業(yè)二姓名學(xué)號(hào)六七總分題號(hào)一得分三四五得分一、單項(xiàng)選擇題（每小題2分，共20分）Q:我去鎮(zhèn)上，則命題“天正在下雪，我沒(méi)去鎮(zhèn)上”可符號(hào)化為（D）A.PQ；B.QP；C.PQ；D.PQ。P:天沒(méi)下雪，1.設(shè)2.下列命題是重言式的是（C）A.(PQ)(QP)；B.(PQP)(PQ)；C.PQ(PQ)；D.(P(QR))PQ。3.設(shè)解釋R如下：論域D為實(shí)數(shù)集，a=0,f(x,y)=x-y,A(x,y):x<y.下列公式在R下為真的是()A.(x)(y)(z)(A(x,y)→A(f(x,z),f(y,z)))B.(x)A(f(a,x),a)C.(x)(y)（A(f(x,y),x))D.(x)(y)(A(x,y)→A(f(x,a),a))4.對(duì)任意集合A,B,C，下列確的是（B）A.[ABBC]C.[ABBC]5.9．關(guān)于X{a,b,c}到Y(jié){1,2,3}的函數(shù)結(jié)論正AC；B.[ABBC]AC；AC；D.[ABBC]AC。f{a,1,b,1,c,3}，下列結(jié)論不正確的是（）A、f1({3}){c}；B、f1(3)c；C、f({c}){3}；D、f(c)3。6.設(shè)I為整數(shù)集合，則I上的二元關(guān)系R{x,y||xy|4}具有（B）A.自反性和對(duì)稱性；B.反自反性和對(duì)稱性；C.反自反性和傳遞性；D.反對(duì)稱性和傳遞性。7.設(shè)R為非空集合A上的關(guān)系R的逆關(guān)系，則下列結(jié)論不成立的是（D）R為偏序；R為擬序；A.若R為偏序，則B.若R為擬序，則R為線序；R為良序。C.若R為線序，則D.若R為良序，則8.設(shè)和是非空集合A的劃分，則下列結(jié)論正確的是（B）1211?AA.細(xì)分；B.細(xì)分；C.非空集合的劃分細(xì)分；D.細(xì)分11211212非空集合A的劃分。21《離散數(shù)學(xué)》試卷第1頁(yè)共4頁(yè)9.設(shè)X={a,b,c},I是X上恒等關(guān)系，要使I∪{〈a,b〉，〈b,c〉，〈c,a〉，〈b,a〉}∪R為X上的等價(jià)關(guān)系，xxR應(yīng)取(D)A.｛〈c,a〉，〈a,c〉｝B.{〈c,b〉，〈b,a〉a,c〉，〈c,b〉}N和R分別為自然數(shù)和實(shí)數(shù)集合，則下列集合中與其他集合的基數(shù)不同的集合是（}C.{〈c,a〉，〈b,a〉}D.{〈10.設(shè)D）(N)；D.NnA.R；B.NN；C.（nN）。得分二、判斷題（每小題2分，共10分。對(duì)的打√，錯(cuò)的打×）1.（）命題聯(lián)結(jié)詞{，，}是最小聯(lián)結(jié)詞組。2.（）（PQ）P為矛盾式。3.（）（（4.（）A、B、C是任意集合，如果5.（）若集合A上的二元關(guān)系R是對(duì)稱的，R的絕對(duì)補(bǔ)6.（）R是A上的二元關(guān)系，R是自反的，當(dāng)且僅當(dāng)r(R)=R。PQ）（QR））AC=AB，一定有B=C。R一定是對(duì)稱的。（PR）為重言式。7.（）集合A上的等價(jià)關(guān)系確定了A的一個(gè)劃分。8.（）有理數(shù)集是可數(shù)的。9.（）若函數(shù)f，g為單射的則其復(fù)合函數(shù)也為單射的。10.（）R是集合A上的關(guān)系，R有傳遞性的充要條件是RoRR。二、填空題（每小空2分，共20分）1．設(shè)R(x)：x是實(shí)數(shù)，Q(x)：x是有理數(shù)，Z(x)：x是整數(shù)，則“有理數(shù)都是實(shí)數(shù)，但實(shí)數(shù)并非都是有理數(shù)”符號(hào)化為：；“有理數(shù)都是實(shí)數(shù)但并非都是整數(shù)”符號(hào)化為：。3.設(shè)集合A＝{a,b,c},B={a,b},那么ρ(B)－ρ(A)=______。ρ(B-A)=______2.設(shè)A{0,1,2,3,4,5}，則定義在集合R{x,y|k(xkyk2}的關(guān)系A(chǔ)上二元關(guān)系矩陣為＿＿M(jìn)＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿。＿＿＿＿＿＿＿＿。t(R)113AB6.設(shè)U[0,1]，A[,1]，B(,)，則＿＿＿＿＿＿＿＿＿＿，＿＿＿＿AB(x)(x)244＿＿＿＿＿＿。設(shè)N為自然數(shù)集合，Q為有理數(shù)集合，R為實(shí)數(shù)集合，則|NXQ||N|，|R-Q||Q|（填=，>，<）三、解答題（每小題10分，共20分）。得分1.求(PQR)(P(QR))的主析取范式和主合取范式。《離散數(shù)學(xué)》試卷第2頁(yè)共4頁(yè)A{1,2,3,4,5,6,7}上的偏序關(guān)系R={}。3.給定集合13524集合最大元最小元極大元極小元B{2,3,4}《離散數(shù)學(xué)》試卷第3頁(yè)共4頁(yè)集合上界下界上確界下確界C{3,4,5,6}A,R（1）給出了偏序集合的哈斯圖(2)求出A的最小元素和最大元素，如果不存在，則指出不存在。（3）求出A的極小元素和極大元素；(4)令B{2,3,4}，C{3,4,5}，分別求出B和C的最大、最小、極大、極小元及其上界、下界、最小上界和最大下界。得分四、證明題（每小題10分，共30分）1.設(shè)為整數(shù)集合，函數(shù)f:IIII定義為：If(x,y)xy,xy，f證明：是單射的但不是滿射的。《離散數(shù)學(xué)》試卷第4頁(yè)共4頁(yè)A{1,2,3,4,5}上的關(guān)系2.設(shè)R是集合R{(1,1),(1,3),(2,2),(2,5),(3,1),(3,3),(4,4),(5,2),(5,5)}（1）畫(huà)出（2）證明R是等價(jià)關(guān)系；（3）寫(xiě)出R的所有等價(jià)類。R的關(guān)系圖;2.用推理規(guī)則證明：x(P(x)Q(x))x(R(x)Q(x))(R(x)P(x))?！峨x散數(shù)學(xué)》試卷第5頁(yè)共4頁(yè)

3.設(shè)R為實(shí)數(shù)集合，Q為整數(shù)集合，證明：|RQ|c。《離散數(shù)學(xué)》試卷第6頁(yè)共4頁(yè)

安徽大學(xué)2007—2008學(xué)年第1學(xué)期《離散數(shù)學(xué)》考試試題（A卷）參考答案及評(píng)分標(biāo)準(zhǔn)一、單項(xiàng)選擇題（每小題2分，共20分）1.D；2.C；3.A；4.B；5.C；6.B；7.D；8.B；9.D；10.D。二、填空題（每小空2分，共20分）1111101000001000001000001[1]{3,1,1,3,5,}1.[0]{4,2,0,2,4,},；2.；223.216，；151010當(dāng)1x1時(shí)101114.M2(x)1010；5.雙，滿，單；6.0。1t(R)A當(dāng)0x時(shí)10102三、解答題（每小題10分，共30分）1.(PQR)(P(QR))(PQR)(PQR)2分(PQ)(PR)(PQ)(PR)4分(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)(1,2,3,4,5,6)(主合取范式)8分(0,7)（主析取范式）10分2.R{(1,1),(1,3),(2,2),(2,5),(3,1),(3,3),(4,4),(5,2),(5,5)}(1)R的關(guān)系圖.132544分3分3分(2)因?yàn)镽滿足自反、對(duì)稱和傳遞性，所以R是等價(jià)關(guān)系；(3)等價(jià)類：{1,3},{2,5},{4}?！峨x散數(shù)學(xué)》試卷第1頁(yè)共2頁(yè)A,R3.（1）的有向圖為2分（2）A的最小元素不存在，最大元素是1；4分（3）A的極小元為：4，5；極大元為；（4）4，極大元為：2，3，極小元為：B最大元素不存在，最小元素為：上確界為1，下確界為：；8分C的最大元素為：3，極小元為：4，5，上界為：1，3，下界不存在，16分4，上界為：1，下界為：4，43，最小元素不存在，極大元為：上確界為3，下確界不存在。10分四、證明題（每小題10分，共30分）1.（1）x1,y,x,yIIf(x,y)f(x,y)，即1，若122122xyxy2xyxy112xy,xyxy,xy，則12，3分1211112222易得xx且yyx,yx,y2f，所以是單射函數(shù)。5分，因此2121112（2）取p,q0,1II，對(duì)x,y，若f(x,y)p,q，xyp0x1/2y1/2xyq1x,y1/2,1/2則有，易得，但I(xiàn)I，8分所以對(duì)于p,qII，不存在x,yII，使得f(x,y)p,q，所以f不是滿射的。10分2.根據(jù)CP規(guī)則，上式等價(jià)于x(P(x)Q(x))x(R(x)Q(x))(R(x)P(x))2分《離散數(shù)學(xué)》試卷第2頁(yè)共2頁(yè)而x(P(x)Q(x))x(R(x)Q(x))x((P(x)Q(x))(R(x)Q(x)))Q4分10x((Q(x)P(x))(R(x)Q(x)))E,E6分24