離散數(shù)學(xué)期末試題

百度文庫-讓每個人平等地提升自我百度文庫-讓每個人平等地提升自我離散數(shù)學(xué)考試試題(A卷及答案)一、(10分)求(PQ)(P八(QVR))的主析取范式解：(PQ)(PA(QVR)) ((PVQ))V(PAQAR))(PVQ)V(PAQAR))/ (PVQVP)A(PVQVQ)A(PVQVR)(PVQ)A(PVQVR) \(PVQV(RAR))A(PVQVR)\/ (PVQVR)A(PVQVR)A(PVQVR)M0AMi \m2Vm3Vm4Vm5Vm6Vm7二、(10分)在某次研討會的休息時間， 3名與會者根據(jù)王教授的口音分別作出下述判斷：,\甲說：王教授不是蘇州人，是上海人。乙說：王教授不是上海人，是蘇州人。丙說：王教授既不是上海人，也不是杭州人。王教授聽后說：你們3人中有一個全說對了，有一人全說錯了，還有一個人對錯各一半。試判斷王教授是哪里人？解設(shè)設(shè)P:王教授是蘇州人；Q:王教授是上海人；R:王教授是杭州人。則根據(jù)題意應(yīng)有：甲：PAQ'乙：QAP丙:\QAR王教授只可能是其中一個城市的人或者 3個城市都不是。所以，丙至少說對了一半。因此，可得甲或乙必有一人全錯了。又因為，若甲全錯了，則有QAP,因此，乙全對。同理，乙全錯則甲全對。所以丙必是一對一錯。故王教授的話符號化為：TOC\o"1-5"\h\z((PAQ)A((QAR)V(QAR)))V((QAP)A(QAR)) /(PAQAQAR)V(PAQAQAR)V(QAPAQAR) /(PAQAR)V(PAQAR)PAQAR\ /T因此，王教授是上海人。三、(10分)證明tsr(R)是包含R的且具有自反性、對稱性和傳遞性的最小關(guān)系。證明設(shè)R是非空集合A上的二元關(guān)系，則tsr(R)是包含R的且具有自反性、對稱性和傳遞性的關(guān)系。若R’是包含R的且具有自反性、對稱性和傳遞性的任意關(guān)系，則由閉包的定義知 r(R)R'o則

sr(R)s(R)=R,進(jìn)而有tsr(R)t(R)=R。綜上可知，tsr(R)是包含R的且具有自反性、對稱性和傳遞性的最小關(guān)系。四、(15分)集合A={a,b,c,de}上的二元關(guān)系R為R={<a,a>,<a,b>,<a,c>,<a,d>,四、(15分)集合A={a,b,c,de}上的二元關(guān)系R為R={<a,a>,<a,b>,<a,c>,<a,d>,<a,e>,<b,b>,<b,c>,<be>,<c,c>,<c,<ce>,<d,d>,<d,e>,<e,e>},(1)寫出R(1)寫出R的關(guān)系矩陣。(2)判斷R是不是偏序關(guān)系，解(1)R的關(guān)系矩陣為：為什么?計算對應(yīng)的關(guān)系矩陣為:M(R)(2)由關(guān)系矩陣可知，對角線上所有元素全為1,故R是自反的；rij計算對應(yīng)的關(guān)系矩陣為:M(R)(2)由關(guān)系矩陣可知，對角線上所有元素全為1,故R是自反的；rij+rji<1,故R是反對稱的；可由以上矩陣可知R是傳遞的。02M(R由以上矩陣可知R是傳遞的。02M(R2) 001M(R)1五、(10分)設(shè)五、(10分)設(shè)A、B、C和D為任意集合，證明(A—B)XC=(AXC)—(BXC)。(X(X(x(X<X<X€AA€AAXB)Ay€CyeCAXB)(X(X(x(X<X<X€AA€AAXB)Ay€CyeCAXB)V(Xy€C)a(xbvyy€C)A(X€BA€AAy€CAyc)C)yCC),y>e(AXC)A<X,y>(BXC),y>€(AXC)-(BXC)所以，(A—B)XC=(AXC—BXC)。證明：因為<x,y>C(A—B)XCxC(A—B)AyCCfhg=Ib,gfh=Ic,貝Uf、六、(10分)設(shè)f:AB,g:BC,h:%CA,證明：如果hgf=Ia,g、h均為雙射，并求出fhg=Ib,gfh=Ic,貝Uf、解因Ia恒等函數(shù)，由hgf=lA可得f是單射，h是滿射；因Ib恒等函數(shù)，由fhg=lB可得g是單射，f是滿射；因IC恒等函數(shù)，由gfh=Ic可彳#h是單射，g是滿射。從而f、g、h均為雙射。由hgf=E,得f=hg；由fhg=IB,得g=fh；由gfh=k,得h=gf。七、(15分)設(shè)<G,*>是一代數(shù)系統(tǒng)，運算*滿足交換律和結(jié)合律，且a*x=a*yx=y,證明：若G有限，則G是一群。 / \證明因G有限，不妨設(shè)G={a1,a2，…，an}。由a*x=a*yx=y得，若xwy,則a*xwa*y。于是可證，對任意的aCG,有aG=Go又因為運算*滿足交換律，所以aG=G=Ga。令eCG使得a*e=a。對任意的bCG,令c*a=b,則b*e=(c*a)*e=c*(a*e)=c*a=b,再由運算*滿足交換律得e*b=b,所以e是關(guān)于運算*的幺元。對任意aCG,由aG=G可知，存在bCG使得%a*b=e,再由運算*滿足交換律得b*a=e,所以b是a的逆元。由a的任意性知，G中每個元素都存在逆元。故G是一群。八、(20分)(1)證明在n個結(jié)點的連通圖G中，至少有n-1條邊。證明不妨設(shè)G是無向連通圖(若G為有向圖，可略去邊的方向討論對應(yīng)的無向圖)、。設(shè)G中結(jié)點為V1、V2、…、環(huán)。由連通性，必存在與V1相鄰的結(jié)點，不妨設(shè)它為V2(否則可重新編號)，連接V］和V2,得邊6| ,還是由連通性，在 V3、V4、…、Vn中必存在與W或V2相鄰的結(jié)點，不妨設(shè)為V3,將其連接得邊比,續(xù)行此法，Vn必與V、V2、…、Vn1中的某個結(jié)點相鄰，得新邊91,由此可見G中至少有n—1條邊。 \(2)給定簡單無向圖G=<V,E>,且|V|=m,|E|=n。試證：若n>41+2,則G是哈密爾頓圖。證明若nAa1+2,則2nAm2-3m+6 (1)。2右存在兩個不相鄰結(jié)點u、v使彳導(dǎo)d(u)+d(V)vm,則有2n=d(w)vm+(m—2)(m—3)+m=m—wV3m+6,與(1)矛盾。所以，對于G中任意兩個不相鄰結(jié)點u、v都有d(u)+d(v)>m。由定理可知，G是哈密爾頓圖。離散數(shù)考試試題（B卷及答案）、（10、（10分）使用將命題公式化為主范式的方法，證明(PQ)\(PAQ)(QP)A(PVQ)。證明：因為(PQ)(PAQ) (PVQ)V(PAQ)證明：因為(PQ)(PAQ) (PVQ)V(PAQ)(Q(PAQ)V(PAQ)P)A(PVQ)(QVP)A(PVQ)(PA(PAQ)VP(PA(PA(PAQ)V(PA(QVQ))Q)V(PAQ)V(PAQ)Q)V(PAQ)Q)V(QAQ)V(PAP)V(PAQ)(Q(PAQ)V(PAQ)P)A(PVQ)(QVP)A(PVQ)(PA(PAQ)VP(PA(PA(PAQ)V(PA(QVQ))Q)V(PAQ)V(PAQ)Q)V(PAQ)Q)V(QAQ)V(PAP)V(PAQ)所以,(PQ)(PAQ)(QP)A(PVQ)o所以,二、（10分）證明下述推理： 如果A努力工作，那么B或C感到愉快；如果B愉快，那么A不努如果D愉快那么C不愉快。所以，如果A努力工作，則D不愉快。力工作;解BVC,BA設(shè)A:A努力工作;B、C、DC1AD分別表示B、C、D愉快；則推理化形式為:附加前提(2)ABVCBVCT(1)(2)如果D愉快那么C不愉快。所以，如果A努力工作，則D不愉快。力工作;解BVC,BA設(shè)A:A努力工作;B、C、DC1AD分別表示B、C、D愉快；則推理化形式為:附加前提(2)ABVCBVCT(1)(2)(5)(6)BT(1)(5)T(4),ET(3)(6)(8)(9)T(7)(8)(10)ACP、（10分）證明xy(P(x)Q(y))(xP(x)yQ(y))。xy(P(x)Q(y))xy(P(x)VQ(y))P(x)VyQ(y))xy(P(x)Q(y))xy(P(x)VQ(y))P(x)VyQ(y))x(P(x)VyQ(y)xP(x)VyQ(y)

(xP(x)四、(10分)設(shè)A={1,{1}},yQ(y))B={0,{0}},求P(A)、P(B)—{0}、P(B)B。解P(A)={{1},{{1}},{,1},{J{1}},{1，{1}},{,1,{1}}}P(B)—{0}={，{0}{{0}}，{0{0}}—{0}={d{0},{{0}}{0{0}}P(B)B={，五、(15分)設(shè){0}，{{0}}X={1<3,2>,<4,3>,<4,1>,<4(1)畫出R的關(guān)系圖。(2)寫出R的關(guān)系矩陣。(xP(x)四、(10分)設(shè)A={1,{1}},yQ(y))B={0,{0}},求P(A)、P(B)—{0}、P(B)B。解P(A)={{1},{{1}},{,1},{J{1}},{1，{1}},{,1,{1}}}P(B)—{0}={，{0}{{0}}，{0{0}}—{0}={d{0},{{0}}{0{0}}P(B)B={，五、(15分)設(shè){0}，{{0}}X={1<3,2>,<4,3>,<4,1>,<4(1)畫出R的關(guān)系圖。(2)寫出R的關(guān)系矩陣。(3)說明R是否是自反、，{0,{0}} {0,{0}}={3,4},R是X上的二元關(guān)系,2>,<1,2>}反自反、對稱、傳遞的。R的關(guān)系圖如圖所示:(2)R的關(guān)系矩陣為:0,{{0}}R={<1{01>,{0}}<3,1>,<1,3>,<3,3>,M(R)⑶對于R的關(guān)系矩陣,由于對角線上不全為R不是自反的；由于又捫t線上存在非 0元，R不是反自反的；由于矩陣不對稱,R不是對稱的;經(jīng)過計算可得M(R2)0M(R),所以0R是傳遞的。六、(15分)設(shè)函數(shù)f:RXRRXR,f定義為：f(<x,y>)=<x+y,x—y>。(2)證明f是滿射。(3)求逆函數(shù)f1o1 X(4)求復(fù)合函數(shù)ff和ff。Xi—y1>,證明(1)對任意的x,y,Xi,y1CR,若f(<x,y>)=f(<X1,y>),貝U<x+y,x-y>=<X1+y1x+y=x1+y1,x-y=x1-y1,從而x=x1,y=y1,故fXi—y1>,uwuw uw,uw(2)對任，國的<u,w>CRXR,令x= ,y= ,則f(<x,y>)=< + u—w>=<u,w>,所以f是滿射。2，…1, 、uwuwTOC\o"1-5"\h\zf(<u,w>)=< , >。,八「1 I,一 、、 「1, , 、、xyxyxy(xy)ff(<x,y>)=f(f(<x,y>))=f(<x+y,x-y>)=< , ->=<x,y>Z\ 2 2ff(<x,y>)=f(f(<x,y>))=f(<x+y,x-y>)=<x+y+x-y,x+y—(x—y)>=<2x,2y>。七、(15分)給定群<G,*>,若對G中任意元a和b,有a3*b3=(a*b)3,a4*b4=(a*b)4,a5*b5=(a*b)5,試證<G,*>是Abel群。 \證明對G中任意元a和bo因為a3*b3=(a*b)3,所以a1*a3*b3*b1=a1*(a*b)3*b1,即得a2*b2=(b*a)2。同理，由a4*b4=(a*b)4可得，a3*b3=(b*a)3。由a5*b5=(a*b)5可得，a4*b4=(b*a)4。于是(a3*b3)*(b*a)=(b*a)4=a4*b4,即b4*a=a*b4。同理可得，(a2*b2)*(b*a)=(b*a)3=a3*b3,即TOC\o"1-5"\h\zb3*a=a*b3。 \由于(a*b)*b3=a*b4=b4*a=b*(b3*a)=b*(a*b3)=(b*a)*b3,故a*b=b*a。 \八、(15分)(1)證明在n個結(jié)點的連通圖G中，至少有n-1條邊。證明