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

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

2、x) B(x)B、 x(A(x) B(x)C、 xA(x) B(x)D、 x(A(x) B(x)3、設(shè) p:天冷, q:小王穿羽絨服， 下列命題中，和命題“只要天冷， 小王就穿羽絨服。 ”一樣符號化為 p? q 的是 。A、如果天不冷，則小王不穿羽絨服。B、小王穿羽絨服僅當(dāng)天冷的時候。C、除非小王穿羽絨服，否則天不冷。D、只有天冷，小王才穿羽絨服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)5、設(shè) A 1,2,3,.,10 ，定義 A 上的關(guān)系 R x,y |x

3、,y S x y 10 ， 則 R 具有的性質(zhì)為 。A、自反的B、對稱的C、傳遞的，對稱的D 、傳遞的6、設(shè) V=<R*, × >是代數(shù)系統(tǒng), R*為非零實數(shù)的集合，×為普通 乘法，下面函數(shù)中是 V 的自同態(tài)的是 。A、f(x)=2xB、f(x)= - xC、 f(x)=1/ xD、f(x)=x+12 / 117、設(shè)V=<Z,+> 是代數(shù)系統(tǒng) , Z為整數(shù)的集合， +為普通加法在， 則(-2)-3= 。A、-8B、8C、-6D 、 68、給定下列各序列， 可以構(gòu)成無向簡單圖的度數(shù)序列為 A、 1,1,2,2,3B、1,1,2,3,3C、0,1,1,3

4、,3D 、1,3,4,4,59、具有6 個頂點， 12條邊的連通簡單平面圖中， 次數(shù)為 3的面有 個。A 、5 B、 6C、 7D、 810、在下面所示的 4個圖中， 不是單向連通圖。C得分二、填空 題(本大題共 15 空，每空 2 分，共 30 分)1、p q 的主合取范式是 。2、表達式 x yA(x,y) 中謂詞的個體域是 D a,b ，將其中的量詞消去，寫成與之等價的命題公式為 3、若明天是星期一或星期三， 我就有課。 若有課， 今天必備課。 我今天下午備課。所以， 明天不是星期一和星期三。 將命題中的 4個簡單命題依次符號化為， p：明天是星期一， q：明天是星期三， r ：我有課，

5、 s：我備課。則推理的形式結(jié)構(gòu)為：前 提 ： ； 結(jié) 論 ：4、 x( yF(x,y)yG( x, y)的前束范式為： 。5 、 設(shè) R， S是 集 合 A 1,2,3,4 上 的 兩 個 關(guān) 系 ， 其 中A的子集x,y Z 有2,2 , 2,3 , 3,2 , 4,4 ,R 1,1 , 2,2 , 2,3 , 4,4 ， S 1,1則 (R S) 1 。6、設(shè)偏序集 A, 的哈斯圖如右所示，若B 3,4,5 ，則 B的最大下界為 。7、在 整 數(shù) 集 Z 上 定 義 二 元 運算 ，x y x y 2 ，則關(guān)于運算 的幺元是 8、設(shè) a是12階群的生成元，則 a3是階元素9、若連通平面圖

6、G 有 4個結(jié)點， 3個面，則 G 有條邊。10、在右邊的 PERT圖中，關(guān)鍵路徑為 11、一顆帶權(quán)為 2,3,5,7,8,9的最優(yōu) 2元樹，其權(quán)為 。12、1400 的不同的正因子個數(shù)為 13、滿足等式 x1 x2 x3 x4 8 的非負整數(shù)解的個數(shù)有 14、n階無向樹至少有 片樹葉。( n>=2 )得分4 / 11三、計算題 ：（6+4+6+6 ，共 22 分 ）1、設(shè)A=1, 2, 3, 4 ， R=<x ，y>|x A，y A且x+y<5 （1）寫出 R的集合表達式和關(guān)系矩陣，畫出 R的關(guān)系圖。（ 2）畫出關(guān)系 R的自反閉包 r（R）、對稱閉包 s（R）和傳遞閉

7、包 t（R） 的關(guān)系圖。2、分別畫出下面無向圖 A 的關(guān)聯(lián)矩陣和有向圖 B的鄰接矩陣。e53、求下面帶權(quán)圖中 v1到其它頂點的最短路徑及對應(yīng)的權(quán)。4、設(shè)有 5 個城市 v1,v2 , v3 , v4 , v5 ，任意兩城市之間的鐵路造價如下（以百萬元為單位）： W(v1, v2)=4,W(v1,v3)=7,W(v1,v4)=16,W(v1, 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)=12。試求出連接 5 個城市的且造價最低的鐵路網(wǎng)。四、證明題：（本大題共 4 個小題，每題 6 分，

8、共 24 分）1、用等值演算法證明下面的等值式(P Q) (P R) (P (Q R)2、設(shè) A為整數(shù)集合，在 AA上定義二元關(guān)系 R：<< x,y>,< u,v>>? R ? x+y = u+ v，證明： R是A A上的等價關(guān)系。3、符號化下列各命題，并說明結(jié)論是否有效（用推理規(guī)則） 。 甲乙丙丁四人參加拳擊比賽，如果甲獲勝，則乙失??；如果丙 獲勝，則乙也獲勝，如果甲不獲勝，則丁不失敗。所以，如果 丙獲勝，則丁不失敗。4、設(shè)<G, *> 是群，給定 aG，令H=y y*a=a*y, y G ，證 明：<H, *> 是G的子群。五、應(yīng)

9、用題（共 4 分）若有 n 個人，每個人都恰有三個朋友，則 n 必為偶數(shù)。華南農(nóng)業(yè)大學(xué)期末考試參考答案（ A 卷）得分一、選擇題 （本大題共 10 小題，每小題 2 分， 共 20 分）1B2D3C4C5B6C7D8B9D10C6 / 11得分、填空 題(本大題共 15 空，每空 2 分，共 30分)1、?p q ；2、(A(a,a) A(a,b) (A(b,a) A(b,b)；3、 (p q) r, rs, s； ?p?q ；4、 x y z(F(x, y) G(x,z)；5、 1,1 , 2,2 , 2,3 , 3,2 , 3,3 4,4 ； 6、2； 7、8、4 ； 9、 5 ； 10、

10、 v1v3v7v8；11、8312、 24 ； 13、 165(或 C181 ，或 C131 )14、2三、計算題：(6+4+6+6 ，共 22 分 )1、R的集合表達式：R 1,1 , 1,2 , 1,3 , 2,1 , 2,2 , 3,1 R的關(guān)系矩陣 :1110110010000000R的關(guān)系圖：得分R的自反閉包 r(R)關(guān)系圖： 對稱閉包 s(R)關(guān)系圖： 傳遞閉包 t(R) 關(guān)系圖：2、圖A的關(guān)聯(lián)矩陣：圖B的鄰接矩陣：2111001000110010010001100020000100003、解：用標號法解題如下：rviv1v2v3v4v5v6003413/ v 141324/ v

11、176376/ v 31047/ v 3959/ v 4w034769v1到v2的最短路徑 : v1 v2 ，對應(yīng)的權(quán)為 3v1到v3的最短路徑 : v1 v3 ，對應(yīng)的權(quán)為 4v1到 v4的最短路徑 : v1 v3 v4 ，對應(yīng)的權(quán)為 7v1到v5的最短路徑 : v1 v3 v5 ，對應(yīng)的權(quán)為 6v1到 v6的最短路徑 : v1 v3 v4 v6 ，對應(yīng)的權(quán)為 97 / 114、解： 將本題用帶權(quán)圖來描述，如下圖 (a)，于是求解此題便成 為求帶權(quán)圖的最小生成樹問題。 按 Kruskal 算法，下圖中 (b)-(e) 就 是求解最小生成樹的過程?？傇靸r =3+4+7+10=24 萬元四、證明

12、題：( 本大題共 4 個小題，每題5 分，得分共 20 分)1、證明： 從左邊開始演算 :(P Q) (P R)( P Q) ( P R)P (Q R)(P (Q R)2、證明：(1)自反性：對于任意的x,y A Axyx y x,y ,x, yR(2)對稱性：對于任意的x,y, u,v Rx y u v uvxy u,v ,x, y(3)傳遞性：對于任意的x,y, u,v Ru,vxyuvuvrsxyrsx, yRr,sr,s3、證明： 1. 解：設(shè) p: 甲獲勝； q：乙獲勝； r：丙獲勝； s：丁 不敗(或丁獲勝) 。前提為： p q； r q； p s 結(jié)論為： r s1) r2) r q3) q4) p q5) p6) p s7) s4、證明： 對于任一 a G，e*a=a*e，群 G的幺元 e H, 所以 H 是 G 的非空子集。任取 a, bH ，下面證明 a*b-1與 G 中所有的元素都 可交換 ."xG，有(a*b-1) *x = a*b -1*x = a*b -1* (x-1)-1 = a* (x -1*b) -1 = a* (b*x -1)-1=10 / 11a* (x*b-1) = (a*x) *b-1