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

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

2、為_。A、 "xA( 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、 小王穿羽絨服僅當天冷的時候。C、 除非小王穿羽絨服，否則天不冷。1D、只有天冷，小王才穿羽絨服4、下列哪個表達式錯誤_。A、 "x ( A( x ) ÙB

3、 ) Û "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 , y ÎS 

4、17;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)=2x B、f(x)= -x C、 f(x)=1/x D、f(x)=x+17、 設(shè)V=<Z,+>是代數(shù)系統(tǒng), Z為整數(shù)的集合，+為普通加法在，則 (-2)- A、-8 B、8 C 、-6 D、68、 給定下列各序列，可以構(gòu)成無向簡單圖的度數(shù)序列為_。3= _。A、1,1,2,2,3 B、1,1,2,3,3 C 、0,1,1,3,3 D 、

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

6、星期一，q：明天是星期三，r：我有課，s：我備課。則推理 的 形 式 結(jié) 構(gòu) 為 ： 前 提 ： _ ； 結(jié) 論 ： _。2、 "x ($yF ( x, y ) ® "yG ( x , y ) 的前束范式為：_。訂5 、 設(shè) R ， S 是 集 合 A =1,2,3,4上 的 兩 個 關(guān) 系 ， 其 中線R =<1,1 >,<2,2 >,<2,3 >,<4,4 > ， S =<1,1 >,<2,2 >,<2,3 >,<3,2 >,<4,4 > , 則 ( R

7、 S ) =_。6、設(shè)偏序集 <A, £>的哈斯圖如右所示，若A的子集 B =3,4,5 ，則B的最大下界為_。7、在整數(shù)集 Z 上定義二元運算 *， "x, y ÎZ 有 x *y =x +y -2 ，則關(guān)于運算 * 的幺元是_。8、設(shè)a是12階群的生成元，則a3是階元素9、若連通平面圖 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 、滿足等式 x +x +x +x =8 的非負整數(shù)解的個數(shù)有1

8、2 3 4_。14、 n階無向樹至少有_片樹葉。（n>=2）得分1.5CM三、計算題 ：（6+4+6+6，共 22 分）1、設(shè)A=1, 2, 3, 4，R=<x，y>|xÎA， yÎA且x+y<5312134511244522312631 21 31 41 52 32 42 53 43 54 5（1） 寫出R的集合表達式和關(guān)系矩陣，畫出R的關(guān)系圖。（2） 畫出關(guān)系R的自反閉包r(R)、對稱閉包s(R)和傳遞閉包t(R)的關(guān)系圖。 2、分別畫出下面無向圖 A 的關(guān)聯(lián)矩陣和有向圖 B 的鄰接矩陣。eeveeV4eevee3evev圖 AV3v圖 Bv3、

9、求下面帶權(quán)圖中v 到其它頂點的最短路徑及對應(yīng)的權(quán)。v10v4v1363224v4v2v54、設(shè)有 5 個城市 v , v , v , v , v ，任意兩城市之間的鐵路造價如下（以百萬元1 2 3 4 5為 單 位 ）： W(v , v )=4, W(v , v )=7, W(v , v )=16, W(v , v )=10, W(v ,v )=13, W(v , v )=8, W(v , v )=17, W(v , v )=3, W(v ,v )=10， W(v , v )=12。試求出連接 5 個城市的且造價最低的鐵路網(wǎng)。四、證明題：（本大題共 4 個小題，每題 6 分，共 24 分）1、

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

11、，給定aG，令H=y|y*a=a*y, yG，證明：<H, *>是G的 子群。五、應(yīng)用題（共 4 分）若有 n 個人，每個人都恰有三個朋友，則 n 必為偶數(shù)。華南農(nóng)業(yè)大學(xué)期末考試參考答案（A 卷）41 3 7 8ê一、選擇題 （本大題共 10 小題，每小題 2 分，共 20 分）得分裝1 B 2 D 3 C 4 C 5 B6 C 7 D 8 B 9 D 10 C訂二、填空題（本大題共 15 空，每空 2 分，共 30 分）得分1、 ¬pq；2、 ( A( a , a ) ÙA( a , b ) Ù( A(b, a ) ÙA(b, b

12、) ；3、 (pq)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、2；8、4；9、5；10、v v v v ；11、83；12、24；13、165（或 C 8 ，或 C 3 ）11 1114、21.5CM三、計算題：（6+4+6+6，共 22 分）1、 R的集合表達式：R =<1,1 >,&

13、lt;1,2 >,<1,3 >,<2,1 >,<2,2 >,<3,1 >R的關(guān)系矩陣: R 的關(guān)系圖： é1 1 1 0ùú1 1 0 0êúúê1 0 0 0得分ê0 0 0 0ëR的自反閉包r(R)關(guān)系圖：úû對稱閉包s(R)關(guān)系圖： 傳遞閉包t(R)關(guān)系圖：5ê1 21 21 31 31 41 3 41 51 3 51 61 3 4 62、圖A的關(guān)聯(lián)矩陣：圖B的鄰接矩陣：é21 1 1 0ù

14、33;01 0 0ùêêê001 1 0 00 0 1 1úúú1êê012úúúêë00 0 0 1úûêë00 0 0úû3、解：用標號法解題如下：r viv1v2v3v4v5v60034¥¥¥13/ v1413¥¥24/ v176¥376/ v31047/ v3959/ v4w034769v 到v 的最短路徑: v v ，對應(yīng)的權(quán)為

15、3v 到v 的最短路徑: v v ，對應(yīng)的權(quán)為4v 到v 的最短路徑: v v v ，對應(yīng)的權(quán)為7v 到v 的最短路徑: v v v ，對應(yīng)的權(quán)為6v 到v 的最短路徑: v v v v ，對應(yīng)的權(quán)為94、 解： 將本題用帶權(quán)圖來描述，如下圖 (a) ，于是求解此題便成為求帶權(quán)圖的 最小生成樹問題。按 Kruskal 算法，下圖中(b)-(e) 就是求解最小生成樹的過程。6裝訂線總造價=3+4+7+10=24萬元四、證明題：（本大題共 4 個小題，每題 5 分，共 20 分） 1、 證明： 從左邊開始演算:( P ® Q ) Ù( P ® R )Û (

16、ØP ÚQ ) Ù( ØP ÚR )Û ØP Ú(Q ÙR )Û ( P ® (Q ÙR )2、證明：(1)自反性：對于任意的 <x, y >ÎA ´Ax +y =x +y Û<<x, y >,<x , y >>ÎR(2)對稱性：對于任意的 <<x, y >,<u, v >>ÎRÛ x +y =u +v Û u +v =x

17、+y Û<<u, v >,<x , y >>ÎR得分(3)傳遞性：對于任意的 <<x, y >,<u, v >>ÎRÙ<<u,v>,<r, s >>ÎRÛ x +y =u +v Ùu +v =r +s Û x +y =r +s Û<<x, y >,<r , s >>ÎR3、證明：1. 解：設(shè) p: 甲獲勝； q：乙獲勝；r：丙獲勝；s：丁不敗（或丁獲勝）。7前提為：（1） rp ® Øq ； r ® q ； Øp ® s結(jié)論為： r ® s（2）（3）（4）（5）r ® qqp ® ØqØp（6） Øp ® s（7） s4、證明： 子集。對于任一 aG，e*a=a*e，群 G 的幺元 e H, 所以 H是 G 的非空任取 a, bH，下面證明 a*b- "x G，有1與 G 中所有的元素都可交換.(a*b-1) *x = a*b-1*x = a*b-1* (x-1)-1= a* (x-1*b)