安徽大學期末試卷離散數(shù)學(上)試卷及參考答案.doc

1、安徽大學期末試卷安徽大學20 09 20 10學年第1學期«離散數(shù)學考試試卷（A卷）得 分)、單項選擇題（每小題2分，共20分）（時間120分鐘）院/系 專業(yè) 姓名 學號題號一一二四五六七總分得分1 .設P:天沒下雪，Q:我去鎮(zhèn)上，則命題 天正在下雪，我沒去鎮(zhèn)上 ”可符號化為（A. p q ；B.P；C.小學數(shù)學經(jīng)典測試卷單元測2 .下列命題是重百式的是A. (P Q) (QP);B.(PP) (PQ);C. P Q (PQ) .，D.(P(QR)Q。3.設解釋R如下：論域D為實數(shù)集,f(x,y)f （x, y） x y。下列公式在R下為真的是（）4.5.6.7.a. x y z(A

2、(x, y) A( f (x, z), f (y, z)；C. x yA( f (x, y), x);對任意集合 A, B,C ,下列結(jié)論正確的是（A.C.關(guān)于A、B.xA( f(a,x), a)；D.x y(A(x,y) A( f (x,a),a)。A B B CA B B CX a,b,c到 Yf 1(3)c;AC; B.AC; D.1,2,3的函數(shù)fB、f 1(3) c；設I為整數(shù)集合，則I上的二元關(guān)系R A.自反性和對稱性；B.反自反性和對稱性;設R為非空集合A上的關(guān)系R的逆關(guān)系,A.若R為偏序，則R為偏序;B.AA a,1CC,b,1 ,C 、f (c)C；c,33；x, y |x

3、y | 4具有C.反自反性和傳遞性;則下列結(jié)論不成立的是（,下列結(jié)論不正確的是（D 、 f(c) 3。D.反對稱性和傳遞性。c.若R為線序，則 R為線序;D.若R為擬序，則為擬序;若R為良序，則F%為良序。8.設1和2是非空集合 A的劃分，則下列結(jié)論正確的是()A.1 細分 1? 2； B. 1 細分 12；非空集合A的劃分1 U 2。9 .設X a,b,c , Ix是X上恒等關(guān)系，要使Ix 等價關(guān)系，R應取()A. c,a,a,c ;B.C. c, a,b,a ;D.10 .設N和R分別為自然數(shù)和實數(shù)集合，則下列集合中A. R; B. NN; C. (N); D.；.非空集合A的劃分1 I

4、2細分1 ； D. 1細分a,b ,b,c ,c, a, b, a R 為 X 上的 c,b, b,a; a,c, c,b。,其他集合的基數(shù)不同的集合是()Nn ( n N )。得 分三、填空題(每小空2分，共20分)得 分.、判斷題(每小題2分，共10分。對的打，錯的打X)1 .() (P Q)P為矛盾式。2 . () A、B、C是任意集合，如果A C A B, 一定有B C。3 .()若集合A上的二元關(guān)系 R是對稱的，R的絕對補R 一定是對稱的。4 .()有理數(shù)集是可數(shù)的。5 .()若函數(shù)f, g為單射，則它們的復合函數(shù)也為單射的。1.設R(x) : x是實數(shù),Q(x) ： x是有理數(shù)，Z

5、(x) ： x是整數(shù)，則“有理數(shù)都是實數(shù)，但實數(shù)并非都是有理數(shù)”符號化為： “不是這樣情況：某些整數(shù)不是有理數(shù)”符號化為： 2 .設集合 A a,b,c, B a,b,那么(B)(A) =；(BA) =3 .設A 0,1,2,3,4,5,則定義在集合A上二元關(guān)系R x,y | k(x kyk2的關(guān)系矩陣為Mr=； M t(R) °1 一 1 34 .僅 U 0,1 , A -,1 , B (-,-),則 AUB(x) , A B(x) 24 45 .設N為自然數(shù)集合，Q為有理數(shù)集合，R為實數(shù)集合,則| N Q| | N |, | R Q| |Q| (填=,>,<)。、解答

6、題（每小題10分，共20分）得 分1 .求（P Q R） （ P （ Q R）的主析取范式和主合取范式。2 .給定集合A 1,2,3,4,5,6上的偏序關(guān)系R 6,2 , 2,1 , 6,1 , 4,2 , 4,3 , 4,1 , 3,1 , 5,3 , 5,1 相。求：（1）給出了偏序集合A, R 的哈斯圖；（2分）（2）完成下表。（每空2分）集合取大兀最小元極大兀極小元B 2,3,4集合上界下界上確界下確界C 3,4,5,6四、證明題（每小題10分，共30分）得 分1 .用推理規(guī)則證明：x(P(x) Q(x) x(R(x) Q(x)(R(x)P(x)。2 .設Ri是A上的等價關(guān)系，R是B上

7、的等價關(guān)系，A豐 且Bw。關(guān)系R滿足：<<xi,yi>,<x2,y2>>CR <xi, *2>6兄且</，y2>CR2,證明R是AX B上的等價關(guān)系。3 .設I為整數(shù)集合，E為偶數(shù)集合，函數(shù) f:I I E E定義為：f( x, y ) x y,x 證明：f是雙射函數(shù)。安徽大學20 07 20 08學年第1學期«離散數(shù)學考試試題（A卷）參考答案及評分標準、單項選擇題（每小題2分，共20分）8.B ; 9.D ; 10.D。二、判斷題（每空2分,共10分）1. V, 2. X, 3.、填空題（每小空2分，共20分）1.x(Q(

8、x)R(x) x(R(x) Q(x)或x(Q(x) R(x)x(R(x) Q(x);2.3.4.x(Z(x)(B)(B A)10M R= 000A B (x)Q(x)或 x(Z(x) Q(x)。(A)11000 c, a,c, b,c, a,b, c,c。10100100101000110；M t(R) = 0001100010100100101000110,幻4,1百1.,1)B( x)w/1 1、,3 -當x(-,) ,14 2411 3當x叼Q4)5.|NQ| j| N |；|RQ Q |。解答題（每小題10分,共30分）1. (PQ R) ( PR)R)(PR)(PQ)R)R)P R)

9、(P(PQ) (PR) (PR) ( PR)R)Q R)10(1,2,3,4,5,6)(主合取范式) (0,7)(主析取范式)2.(1)A, R的哈斯圖為分(2)(空2分)集合取人兒最小元極大兀極小元B 2,3,4不存在42, 34集合上界下界上確界下確界C 3,4,5,61不存在1不存在10分四、證明題(每小題10分，共30分)1.根據(jù)CP規(guī)則，上式等價于x(P(x) Q(x) x(R(x)而Q(x)(R(x)P(x)x(P(x) Q(x) x(R(x)x(P(x)Q(x) (R(x)x( Q(x) P(x) (R(x) (Q(x)P(x) (R(x)R(x) P(x)Q(x)Q(x)Q(x

10、) Q(x)所以， x(P(x) Q(x) x(R(x) Q(x)Q10E5E4Q1I 6(R(x)2分4分6分8分10分P(x)2.證明對任意的<x, y>CAXB,由Ri是A上的等價關(guān)系可得<x, x>CRi,由R是B上的等價關(guān)系可得<y, y>CR。再由R的定義，有<<x, y>, <x, y>> R,所以R是自反的。2 分對任意的 <x, y>、<u, v>C AX B,若 <x, y>R<u, v>,則 <x, u>CR 且<y, v>C R

11、2。由 Ri 對稱得 <u,x>e Ri,由R2對稱得<v, y>e R2o再由R的定義，有<<u,對稱的。v>, <x, y>>CR,即 <u, v>R<x, y>,所以 R是分對任意的 <x, y>、<u, v>、<s, t>CAXB,若 <x, y>R<u, v> 且 <u, v>R<s, t>,貝 U <x, u>CR 且 <y, v>e R2,<u, s>CRi且 <v, t> R20由 <x, u>CRi、<u, s>eRi 及 Ri 的傳遞性得<x,s>CRi,由 <y,v>£ R2、<v, t>e R2及R2的傳遞性得<y, t>e Rio再由R的定義，有<<x,y>, <s, t>>CR,即 <x, y>R<s,t>,所以10R是傳遞的。綜上可得，R是AX B上的等價關(guān)系。3. (i)Xi, yiX2,y2 Ixi，