離散數(shù)學(xué)2007-2008A卷

1、北京科技大學(xué) 2007 2008學(xué)年 第 I 學(xué)期 離散數(shù)學(xué) 試卷（A）院(系) 班級 學(xué)號 姓名 試卷卷面成績占課程考核成績70平時 成績占30%課程考核成績題號一二三四五六七八小計得分裝 訂 線 內(nèi) 不 得 答 題自 覺 遵 守 考 試 規(guī) 則，誠 信 考 試，絕 不 作 弊得 分一、判斷正誤（共30分，每小題1.5分）1. 樹是無環(huán)連通簡單圖。 ( )2. 命題具有確定的真假值。 ( )3. p®q和Øpq命題等價。 ( )4. 有向圖中結(jié)點入度之和等于出度之和。 ( )5. 設(shè)R和S是非空集合A上的等價關(guān)系，則也是A上的等價關(guān)系。 ( )6. 若A為矛盾式，則A的主

2、析取范式為1。 ( )7. 量詞的約束順序?qū)秸婕僦禑o影響。 ( )8. 自然數(shù)集是無限集中最小的集合。 ( )9. 質(zhì)數(shù)階群必是循環(huán)群。 ( )10. 若r(R)=R，則R一定是自反的。 ( )11. 若f為函數(shù)，則(f-1)-1=f。 ( )12. 群中有幺元，零元。 ( )13. 若無向圖中有兩對結(jié)點的度數(shù)為奇數(shù)，則存在歐拉路。 ( )14. 任意一棵樹至少有兩片樹葉。 ( )15. ( )16. 設(shè)是群G到群H的同態(tài)映射，若G是交換群，則H也是交換群。 ( )17. 設(shè)V<Z, +, ·>，其中 + 和·分別代表普通加法和乘法，則集合S-1, 0, 1

3、可以構(gòu)成V的子代數(shù)。 ( )18. 偶數(shù)階群必含2階元。 ( )19. 任何一個循環(huán)群必定是阿貝爾群。 ( )20. Æ, Æ Æ=Æ, Æ ( )得 分二、填空題（共30分，每個空格2分）1. 已知集合A =Æ，1，2，則A的冪集合P（A）= 。2. 設(shè)集合A= a, b, c, d，A上的關(guān)系R= < a , a >， <a , c>，<b, d>，則關(guān)系R2= 。3. 設(shè)集合A = 0, 1, 2, 3, 4, 5，A上的關(guān)系R = <0, 0>，<1, 1>，<

4、1, 2>，<1, 3>，<2, 1>，<2, 2>，<2, 3>，<3, 1>，<3, 2>，<3, 3>，<4, 4>，<4, 5>，<5, 4>，<5, 5>，則R在A上構(gòu)成的等價類是_ 。4. 設(shè)集合A = a, b, c, d, e，A上半序關(guān)系R的哈斯圖如圖1所示，則A的極小元為_ 。圖15. 已知命題公式G = Ø（P®Q）ÙR，則G的主析取范式是_ 。6. 設(shè)D：a , b，將表達式"x$ y (x,

5、y)中的量詞消除后，與之等價的命題公式是 。7. 設(shè)G是完全二叉樹，G有15個點，其中有8個葉點，則G的分枝點數(shù)是 。8. 對下圖（圖2）中樹的點圖2中序遍歷的次序是 。9. 設(shè)有限集A, B，|A| = m, |B| = n, 則笛卡兒積 A´B 的子集個數(shù)有 _個.10. 設(shè)X= x | xÎR, x ¹0,1, 在X上如下定義6個函數(shù)：f1(x) = x， f2(x) =1/x, f3(x) = 1-x, f4(x) = 1/(1-x), f5(x) = (x-1)/x, f6(x) = x/(x-1), 則G = f1, f2, f3, f4, f5, f

6、6關(guān)于函數(shù)合成運算構(gòu)成群. 則子群 f1, f2 的所有的右陪集是_.11. 設(shè)G是由K1, K2, K3 3個連通分支組成的平面圖，則G共有 個面。12. 設(shè)GS4為4元對稱群，則<(1432)>= .13. 設(shè)S=，則下列集合S，P(S)，N，N×N×N，P(N)，R，R×R裝 訂 線 內(nèi) 不 得 答 題自 覺 遵 守 考 試 規(guī) 則，誠 信 考 試，絕 不 作 弊中基數(shù)為的有： 。14. 一個班70個學(xué)生，在第一次考試中有36人得5分，在第二次考試中有29人得5分，如果兩次考試中都沒有得5分的有26人，那么兩次考試都得5分的有 人。15. 的前束

7、范式是 。得 分三、在自然推理系統(tǒng)F中構(gòu)造下面推理的證明（8分）前提：，結(jié)論： 得 分四、試證：一個有限非交換群至少含有6個元（8分）得 分五、設(shè)A=a,b,c，求出A上所有的等價關(guān)系。（10分）得 分六、對下圖（圖3）所示無向帶權(quán)圖G求一棵最小生成樹T，并計算出T的權(quán)W(T)。（6分）裝 訂 線 內(nèi) 不 得 答 題自 覺 遵 守 考 試 規(guī) 則，誠 信 考 試，絕 不 作 弊圖3得 分七、設(shè)為單射函數(shù)，為在下的像。證明也是單射的。（4分）得 分8、 求當(dāng)連通平面圖的每個面至少有5條邊圍成時，邊數(shù)與結(jié)點數(shù)所滿足的關(guān)系式（4分）B卷北京科技大學(xué)200 200 學(xué)年度第 學(xué)期 離散數(shù)學(xué) 試題答案及

8、評分標(biāo)準(zhǔn)一、 判斷正誤（共36分，答錯不扣分）1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14. 15. 16. 17. 18. 19. 20. 21. 22. 23. 24. 評分：每錯一個扣1.5。二、 填空（每題2分，共20分）1. 2nn ; 2nn 2. l, m; a, b, c; k; k, l, m 3. 6 4. 6 5. e=v-1 6. b=c三、 證明（12分）(1) 證明：Ø"x(P(x) ®Q(x)$x(P(x)ØQ(x) 得1分P(a)Q(a) 得1分"x(A(x)

9、74;Q(x)"x(ØA(x) Q(x)ØA(a) Q(a) 得1分Q(a) ØA(a) "x(P(x)®A(x)B(x)"x(ØP(x) A(x)B(x)ØP(a) A(a)B(a) 得1分P(a), ØA(a) 得1分B(a)P(a) B(a) 得1分$x (P(x) B(x)(2) 證明：Ø(P(ØPQ) ÛØPØ (ØPQ) 得1分ÛØP (PØQ) 得1分Û(ØPP)(

10、6;PØQ) 得2分Û0(ØPØQ) 得2分ØPØQ四、 (1)證明：1)R是自反的得1分2)R是對稱的得1分3)R是傳遞的得1分所以，R為等價關(guān)系。得1分(2)1=4=7=10=1,4,7,10得2分2=5=8=2,5,8得1分3=6=9=3,6,9得1分五、 證明：(1) ab, 又bbbab得1分bab得1分b=ab得2分(2) b=abb=aba得2分ab得2分六、 證明：設(shè)連通平面圖G的面數(shù)為r，當(dāng)v=3，e=2時，上式顯然成立。得1分若e3，則每一面的次數(shù)不小于3，面的次數(shù)之和為2e，因此2e3r, r2/3e得2分帶入歐

11、拉定理:2=v-e+rv-e+2/3e得2分2v-e/363v-e即e3v-6. 得1分七、 證明：(1)"a,bC, a,bG1有f(ab)=f(a)*f(b)g(ab)=g(a)*g(b)f(a)=g(a), f(b)=g(b)abC則，<c, >是封閉的。得1分(2)設(shè)< G1, >的幺元為e，顯然有"aC, aG1f(ae)=f(a)*f(e)=f(a)g(ae)=g(a)*g(e)=g(a)f(a)=g(a)f(e)=g(e)eC得1分(3) "aC, 顯然aG1f(aa-1)=f(a)*f(a-1)=f(e)g(aa-1)=g(a)*g(a-1)=g(e)f(a)=g(a), 又f(e)=g(e)f(a-1)=g(a-1)a-1C得1分