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

安徽大學期末試卷安徽大學期末試卷小學數(shù)學經(jīng)典測試卷單元測小學數(shù)學經(jīng)典測試卷單元測安徽大學2009—2010學年第1學期《離散數(shù)學》考試試卷（A卷）（時間120分鐘）院系 專業(yè) 姓名 學號題號一二三四五六七總分得分得分得分設P:天沒下雪，Q:我去鎮(zhèn)上，則命天正在下雪，我沒去鎮(zhèn)可符號化為（ A.PQ； B.QP； C.PQ； D.PQ。下列命題是重言式的是（ ）A.(PQ(QP； B.(PQP)(PQ)；C.PQ(PQ； D.(P(QRPQ設解釋R如下：論域D為實數(shù)集，a0，f(x,y)xy，f(x,y)xy。下列公式在R下為真的是( )A.xyz(A(x,y)f(x,z),f(y,z)))； B.xA(f(a,x),a)；C.f(xyx； D.xyA(xyf(xaa。對任意集合B,C，下列結論正確的是（ ）A.[ABBC]AC； B.[ABBC]AC；C.ABBCAC； D.ABBCAC。5.關于X{a,b,到Y的函數(shù)fa,1,b,1,c,3}，下列結論不正確的是（ A、f1({3}){c}； 、f1(3)c； 、f、f(c)3。設I為整數(shù)集合，則I上的二元關系Rx,yxy|具有（ ）自反性和對稱性；B.反自反性和對稱性；C.反自反性和傳遞性；D.反對稱性和傳遞性。設R為非空集合A上的關系R的逆關系，則下列結論不成立的是（ A.若R為偏序，則R為偏序； 若R為擬序，則R為擬序；C.若R為線序，則R為線序； 若R為良序，則R為良序。設和 是非空集合A的劃分，則下列結論正確的是（ ）1 2細分； B. 細分；C.非空集合A的劃分1 1 2 1 1 2 12。A2。1

細分；D.細分2 1 1X等價關系，R應( )XA.c,X等價關系，R應( )XA.c,a,a,c；B.c,b,b,a}；C.c,a,b,a；D.accb}。

是X上恒等關系，要使I

{abbccabaRX上的設N和R分別為自然數(shù)和實數(shù)集合，則下列集合中與其他集合的基數(shù)不同的集合是（ ）R； B.NN； C.(N； D.Nn（nN。得分得分1.（ ）(PQP為矛盾式。2.（ ）AB、CACABBC。3.（ ）ARRR一定是對稱的。4.（ ）有理數(shù)集是可數(shù)的。5.（ ）fg為單射，則它們的復合函數(shù)也為單射的。得分得分1．R(xxQ(xxZ(xx是整數(shù)，則“有理數(shù)都是實數(shù)，但實數(shù)并非都是有理數(shù)”符號化為： ；“不是這樣情況：某些整數(shù)不是有理數(shù)”符號化為： 。2.設集合A{a,b,c}，B，那么(B)(= ；(B= 。3.AARxyk(xkyk2}的關系矩陣為M =＿＿＿＿＿＿＿＿＿＿ M ＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿。R t(R)(x)B4.設UA[1B13)，則(x)B

＿＿＿＿＿＿＿＿＿＿，

(x)＿＿＿＿2＿＿＿＿＿＿。

44 A

AB5.設N為自然數(shù)集合為有理數(shù)集合，R為實數(shù)集合則|NQ| |N|RQ| |Q填<。得分得分1.求(PQR)(P(QR))的主析取范式和主合取范式。2.給定集合A{1,2,3,4,5,6}上的偏序關系R6,24,2I 。A）給出了偏序集合,R（2分）（2）完成下表。（每空2分）集合最大元最小元極大元極小元B{2,3,4}集合C{3,4,5,6}上界下界上確界下確界得分得分用推理規(guī)則證明：x(P(x)Q(x))x(R(x)Q(x))(R(x)P(x))。R1ABB≠RR<x1，x2>∈R1且<y1，y2>∈R2RA×B上的等價關系。IEf:IIEEf(x,y)xyxy，f是雙射函數(shù)。安徽大學2007—2008學年第1學期《離散數(shù)學》考試試題（A卷）參考答案及評分標準一、單項選擇題（每小題2分，共20分）1.D；2.C；3.A；4.B；5.B；6.B；7.D；8.B；9.D；10.D。二、判斷題（每空2分，共10分）1.√，2.×，3.√，4.√，5.√三、填空題（每小空2分，共20分）1.x(Q(xR(xx(R(xQ(x或x(Q(xR(xx(R(x)Q(x))；x(Z(x)Q(x))或x(Z(x)Q(x))。2.(B)({{c},{a,c},{a,b,c}}；(BA){,{c}}。1 1 1 1 1 1 1 1 1 10 1 0 0 0 0 1 0 0 0 3.

=R

0 1 0 0；0 0 1 0

t(R

=

0 1 0 00 0 1 0 0

0 0 0

0

0 0 0 14.

(x)1

1 1x x 4112 ；AB

x( , 42 (x)

當x11 ( , )當x11 AB

當x

1 13[0, ] [ , 4 245.|NQ|=|N|；|RQ|>|Q|。三、解答題（每小題10分，共30分）1. (PQR)(P(QR))(PQR(PQR) 2(PQ(PR(PQ(PR) 4(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)(主合取范) 8分(0,7)（主析取范式） 10分2.（1）R的哈斯圖為123123645（2（空2分）集合集合B最大元最小元極大元極小元不存在42，34集合上界下界上確界下確界C{3,4,5,6}1不存在1不存在四、證明題（1030）

10分根據(jù)CPx(P(x)Q(xx(R(x)Q(x))(R(x)P(x)) 2而x(P(x)Q(x))x(R(x)Q(x))x((P(x)Q(x))(R(xQ(x))) Q 410x((Q(x)P(x))(R(xQ(x))) EE 65 24(Q(x)P(x))(R(x)Q(x)) Q1R(x)P(x) I

8分10分6所以，x(P(x)Q(x))x(R(x)Q(x))(R(x)P(x))證明對任意的<RARB上的等價關系可得1 1 2<y，y>∈R。再由R的定義，<<x，y>，<x，y>>∈R，所以R是自反的。 2分2對任意的<x，y>、<u，v>∈A×B，若<x，y>R<u，v>，則<x，u>∈R且<y，v>∈R。由R對稱得<u，1 2 1x>∈RRv，y>∈RRu，v>，<x，y>>∈Ru，v>R<x，yR是1 2 2對稱的。 6分1∈R，<u，s>∈R且<v，t>∈R。由<x，u>∈R、<u，s>∈RRx，s>∈Ry，v>∈R、2 1 2 1 1 1 1 2<v，t>∈RRy，t>∈RRx，y>R<s，t>，所以2 2 1R是傳遞的。 10分綜上可得，R是A×B上的等價關系。x,y3.（1） 1

,x2,y2II，若f(x,y1 1

)f(x,y2 2

，即xy x yxy,x

x

y,x y

，則1 1 2 2，1 1 1 1

2 2 2 2

xy1

x y2 2

x且y

x,y

x

,y2，所以f是單射函數(shù)。 4分1 2 1

1 1 2（2）取任意pqEE，若存在xyIIf(x,y)pq，xyp

x

pq2則有 ，易