華南農(nóng)業(yè)大學離散數(shù)學期末考試2011試卷及答案

1、華南農(nóng)業(yè)大學期末考試試卷(A卷)2011-2012學年第一學期考試科目：離散結(jié)構考試類型：(閉卷)考試考試時間：120分鐘學號姓名年級專業(yè)題號一二三四五總分得分評閱人林旭東黃華偉朱梅階黃沛杰考試注意事項：本試題分為試卷與答卷2部分。試卷有五大題，共4頁。所有解答必須寫在答卷上，寫在試卷上不得分。得分、選擇題(本大題共10小題，每小題2分，共20分)1、重言式的否定是()A、重言式B、矛盾式C、可滿足式D、A-C均有可能2、A(x):x在北京工作，B(x):x是北京人；則命題”在北京工作的人都是北京人?！笨杀硇?A、xA(x)B(x)B、x(A(x)B(x)C、xA(x)B(x)D、x(A(x

2、)B(x)3、 設p:天冷，q:小王穿羽絨服， 下列命題中， 和命題“只要天冷， 小王就穿羽絨服。 ”一樣符號化為pq的是。A、如果大不冷，則小王不穿羽絨服。B、小王穿羽絨服僅當天冷的時候。C、除非小王穿羽絨服，否則天不冷D、只有天冷，小王才穿羽絨服4、下列哪個表達式錯誤5、設A1,2,3,.,10,定義A上的關系Rx,y|x,ySxy10,則R具有的性質(zhì)為。A、自反的B、對稱的C、傳遞的，對稱的D、傳遞的6、設V=是代數(shù)系統(tǒng)，R*為非零實數(shù)的集合，為普通乘法，下面函數(shù)中是V的自同態(tài)的是。A、f(x)=2xB、f(x)=xC、f(x)=1/xD、f(x)=x+17、設V=是代數(shù)系統(tǒng)，Z為整數(shù)的

3、集合，+為普通加法在，則(2)3=oA、-8B、8C、-6D、68、給定下列各序列，可以構成無向簡單圖的度數(shù)序列為。A、1,1,2,2,3B、1,1,2,3,3C、0,1,1,3,3D、1,3,4,4,59、具有6個頂點，12條邊的連通簡單平面圖中，次數(shù)為3的面有個。A、5B、6C、7D、810、在下面所示的4個圖中，不是單向連通圖。A、x(A(x)B)xA(x)BB、x(A(x)B)xA(x)BC、x(P(x)Q(x)xP(x)xQ(x)D、x(P(x)Q(x)xP(x)xQ(x)1、p-q的主合取范式是、填空題(本大題共15空，每空2分，共30分)2、表達式xyA（x,y）中謂詞的個體域是

4、Da,b,將其中的量詞消去，寫成與之等價的命題公式為3、若明天是星期一或星期三，我就有課。若有課，今天必備課。我今天下午備課。所以，明天不是星期一和星期三。將命題中的4個簡單命題依次符號化為，p：明天是星期一，q：明天是星期三，r：我有課，s：我備課。則推理的形式結(jié)構為：前提：則關于運算的幺元是得分三、計算題：（6+4+6+6,共22分）4、x(yF(x,y)yG（x,y）的前束范式為:是集合A1,2,3,4上的兩個關系，其中則（R1,1S)6、設偏序集2,22,3,4,4,S1,1,2,2,2,3,A,的哈斯圖如右所示，若A的子集B3,4,5,則B的最大下界為7、在整數(shù)集Z上定義二元運算,x

5、,yZ有xyxy2,3,2,4,4,8、設a是12階群的生成元，則a3是階元素9、若連通平面圖G有4個結(jié)點，3個面，則G有條邊。10、在右邊的PERT圖中，關鍵路徑為11、一顆帶權為2,3,5,7,8,9勺最優(yōu)2元樹，其權為12、1400的不同的正因子個數(shù)為13、滿足等式XIx2x3x48的非負整數(shù)解的個數(shù)有14、n階無向樹至少有片樹葉。（n=2）修1、設人=1,2,3,4,R=|xA,yA且x+y5(1)寫出R的集合表達式和關系矩陣，畫出R的關系圖。(2)畫出關系R的自反閉包r(R)、對稱閉包s(R)和傳遞閉包t(R)的關系圖。2、分別畫出下面無向圖A的關聯(lián)矩陣和有向圖B的鄰接矩陣。3、求下

6、面帶權圖中vi到其它頂點的最短路徑及對應的權。4、設有5個城市Vi,V2,V3,V4,V5,任意兩城市之間的鐵路造價如下(以百萬元為單位):W(VI,V2)=4,W(VI,V3)=7,W(VI,V4)=16,W(VI,V5)=10,W(V2,V3)=13,W(V2,V4)=8,W(V2,V5)=17,W(V3,V4)=3,W(V3,V5)=10,W(V4,V5)=12O試求出連接5個城市的且造價最低的鐵路網(wǎng)。四、證明題：(本大題共4個小題，每題6分，共24分)1、用等值演算法證明下面的等值式(PQ)(PR)(P(QR)2、設A為整數(shù)集合，在AA上定義二元關系R:,Rx+y=u+v,證明：R是A

7、A上的等價關系。3、符號化下列各命題，并說明結(jié)論是否有效(用推理規(guī)則)。甲乙丙丁四人參加拳擊比賽，如果甲獲勝，則乙失敗；如果內(nèi)獲勝，則乙也獲勝，如果甲不獲勝，則丁不失敗。所以，如果丙獲勝，則丁不失敗。4、設是群，給定aCG,令+丫y*a=a*y,yG,證明：是6的子群。五、應用題(共4分)若有n個人，每個人都恰有三個朋友，則n必為偶數(shù)。華南農(nóng)業(yè)大學期末考試參考答案(A卷)1B2D3C4C5B6C7D8B9D10C1、?pVq;2、(A(a,a)A(a,b)(A(b,a)A(b,b);3、(pVq)r,r-s,s;?pA?q;4、xyz(F(x,y)G(x,z);5、1,1,2,2,2,3,3,

8、2,3,34,4;6、2；7、2；8、4：9、5：10、V1V3V7V8;11、83:12、24;13、165(或C81C；14、2、計算題：(6+4+6+6,共22分)1、R的集合表達式：R的關系矩陣：R的關系圖:1110110010000000R的自反閉包r(R)關系圖：對稱I加包s(R)關系圖：傳遞閉包t(R)關系圖:得分、選擇題(本大題共10小題，每小題2分，共20分)得分得分、填空題(本大題共15空，每空2分，共30分)得分R1,1,1,2,1,32,1,2,2,3,12、圖A的關聯(lián)矩陣：211100110000011000013、解：用標號法解題如下：圖B的鄰接矩陣：0100100

9、100020000rMV1V2V3V4V5V6003413/VI41324/VI76376/V31047/V3959/V4w034769vl到v2的最短路徑：V1v2,對應的權為3V1到V3的最短路徑：V1V3,對應的權為4V1到V4的最短路徑：V1V3V4,對應的權為7V1到V5的最短路徑：V1V3V5,對應的權為6V1到V6的最短路徑：V1V3V4V6,對應的權為94、解：將本題用帶權圖來描述，如下圖(a),于是求解此題便成為求帶權圖的最小生成樹問題。按Kruskal算法，下圖中(b)-(e)就是求解最小生成樹的過程。總造價=3+4+7+10=24萬元四、證明題：(本大題共4個小題，每題1

10、、證明：從左邊開始演算：(PQ)(PR)(PQ)(PR)P(QR)(P(QR)2、證明：(1)自反性：對于任意的x,yAAxyxyx,y,x,y(2)對稱性：對于任意的x,y,u,vxyuvuvxy(3)傳遞性：對于任意的x,y,u,vxyuvuvrsxy7 7yi43、證明：1.解：設p:甲獲勝；q：乙獲勝;RRu,v,x,yRRu,v,r,sRrsx,y,r,sRr：丙獲勝；s：丁不?。ɑ蚨～@勝）(1)rrq(3)q(4)pqppss4、證明：對于任一aCG,e*a=a*e,群G的幺元eH,所以H是G的非空子集。任取a,bCH,下面證明a*b1與G中所有的元素都可交換.xCG,有(a*b1)*x=a*b1*x=a*b1*(x1)1=a*(x1*b)1=a*(b*x1)1=a*(x*b1)=(a*x)*b1=(x*a)*b1=x*(a*b1)由