北京科技大學(xué)– 離散試題

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

2、. 量詞的約束順序?qū)秸婕僦禑o(wú)影響。 ( )8. 自然數(shù)集是無(wú)限集中最小的集合。 ( )9. 質(zhì)數(shù)階群必是循環(huán)群。 ( )10. 若r(r)=r，則r一定是自反的。 ( )11. 若f為函數(shù)，則(f-1)-1=f。 ( )12. 群中有幺元，零元。 ( )13. 若無(wú)向圖中有兩對(duì)結(jié)點(diǎn)的度數(shù)為奇數(shù)，則存在歐拉路。 ( )14. 任意一棵樹至少有兩片樹葉。 ( )15. ( )16. 設(shè)是群g到群h的同態(tài)映射，若g是交換群，則h也是交換群。 ( )17. 設(shè)v，其中 + 和分別代表普通加法和乘法，則集合s-1, 0, 1可以構(gòu)成v的子代數(shù)。 ( )18. 偶數(shù)階群必含2階元。 ( )19. 任何

3、一個(gè)循環(huán)群必定是阿貝爾群。 ( )20. , =, ( )得 分二、填空題（共30分，每個(gè)空格2分）1. 已知集合a =，1，2，則a的冪集合p（a）= 。2. 設(shè)集合a= a, b, c, d，a上的關(guān)系r= ， ，則關(guān)系r2= 。3. 設(shè)集合a = 0, 1, 2, 3, 4, 5，a上的關(guān)系r = ，則r在a上構(gòu)成的等價(jià)類是_ 。4. 設(shè)集合a = a, b, c, d, e，a上半序關(guān)系r的哈斯圖如圖1所示，則a的極小元為_ 。圖15. 已知命題公式g = （pq）r，則g的主析取范式是_ 。6. 設(shè)d：a , b，將表達(dá)式x$ y (x, y)中的量詞消除后，與之等價(jià)的命題公式是 。

4、7. 設(shè)g是完全二叉樹，g有15個(gè)點(diǎn)，其中有8個(gè)葉點(diǎn)，則g的分枝點(diǎn)數(shù)是 。8. 對(duì)下圖（圖2）中樹的點(diǎn)圖2中序遍歷的次序是 。9. 設(shè)有限集a, b，|a| = m, |b| = n, 則笛卡兒積 ab 的子集個(gè)數(shù)有 _個(gè).10. 設(shè)x= x | xr, x 0,1, 在x上如下定義6個(gè)函數(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, f6關(guān)于函數(shù)合成運(yùn)算構(gòu)成群. 則子群 f1, f2 的所有的右陪集是_.11. 設(shè)

5、g是由k1, k2, k3 3個(gè)連通分支組成的平面圖，則g共有 個(gè)面。12. 設(shè)gs4為4元對(duì)稱群，則= .13. 設(shè)s=，則下列集合s，p(s)，n，nnn，p(n)，r，rr裝 訂 線 內(nèi) 不 得 答 題自 覺 遵 守 考 試 規(guī) 則，誠(chéng) 信 考 試，絕 不 作 弊中基數(shù)為的有： 。14. 一個(gè)班70個(gè)學(xué)生，在第一次考試中有36人得5分，在第二次考試中有29人得5分，如果兩次考試中都沒有得5分的有26人，那么兩次考試都得5分的有 人。15. 的前束范式是 。得 分三、在自然推理系統(tǒng)f中構(gòu)造下面推理的證明（8分）前提：，結(jié)論： 得 分四、試證：一個(gè)有限非交換群至少含有6個(gè)元（8分）得 分五、

6、設(shè)a=a,b,c，求出a上所有的等價(jià)關(guān)系。（10分）得 分六、對(duì)下圖（圖3）所示無(wú)向帶權(quán)圖g求一棵最小生成樹t，并計(jì)算出t的權(quán)w(t)。（6分）裝 訂 線 內(nèi) 不 得 答 題自 覺 遵 守 考 試 規(guī) 則，誠(chéng) 信 考 試，絕 不 作 弊圖3得 分七、設(shè)為單射函數(shù)，為在下的像。證明也是單射的。（4分）得 分八、求當(dāng)連通平面圖的每個(gè)面至少有5條邊圍成時(shí)，邊數(shù)與結(jié)點(diǎn)數(shù)所滿足的關(guān)系式（4分）一、判斷正誤（共30分，每小題1.5分）1. 2. 3 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14. 15. 16. 17. 18. 19. 20.二、填空題（共30分，每個(gè)空格2分）

7、a) ，1，2，1，2，1，2，ab) ，c) m1 0，m2 1，2，3，m3 4，5d) c，de) pqr或m5f) （f（a，a）f（a，b）（f（b，a）f（b，b）或（f（a，a）f（b，a）（f（a，b）f（b，b）g) 7h) dbkhleaficgmjni)j) f1, f2，f1, f2f3 = f3, f5, f1, f2f4 = f4, f6.k) 2個(gè)l) (1234), (13)(24), (1432), (1)m) n，nnnn) 21人o)三、證明（8分）在自然推理系統(tǒng)f中構(gòu)造下面推理的證明前提：，結(jié)論：證明：(1) 附加前提引入(2) (1) ei （1分）(

8、3) (2)化簡(jiǎn)(4) (2)化簡(jiǎn)(5) 前提引入(6) (3)eg （1分）(7) (5)(6)假言推理 （1分）(8) 前提引入(9) (4)eg （1分）(10) (8) (9)假言推理 （1分）(11) (10)ei （1分）(12) (7)ui （1分）(13) (11) (12) 假言推理 （1分）(14) (13)eg四、試證：一個(gè)有限非交換群至少含有6個(gè)元（8分）證明：由拉格朗日定理的推論知，1，2，3，5階群都是循環(huán)群，從而是可交換的。（4分）若g為4階群，除單位元e外，g的元素的階或?yàn)?或?yàn)?。只有兩種可能。(1) g中存在一個(gè)階為4的元素a。此時(shí)必有g(shù)=，是由a生成的循環(huán)

9、群，由上一步的討論知g是可交換的。（2分）(2) 若g中不存在階為4的元素，由拉格朗日定理的推論知，除e外，g的所有元素的階為2。設(shè)g=e,a,b,c。則。由于，（反之有a或b等于e），且，所以必有。同理，。也是可交換的。（2分）故非交換群至少有6個(gè)元素。五、設(shè)a=a,b,c，求出a上所有的等價(jià)關(guān)系。（10分）解 先求出a上有多少個(gè)不同的分劃。分成一個(gè)分劃塊的分劃 分成兩個(gè)分劃塊的分劃 、分成三個(gè)分劃塊的分劃 因此，a上有5個(gè)不同的分劃（5分），記與分劃 相對(duì)應(yīng)的等價(jià)關(guān)系為（5分）六、對(duì)下圖所示無(wú)向帶權(quán)圖g求一棵最小生成樹t，并計(jì)算出t的權(quán)w(t)。（6分）解：按kruskal算法，細(xì)心的尋找在最小生成樹中的邊，所得最小生成樹如下圖所示（4分），w(t)31。（2分）七、設(shè)為單射函數(shù)，為在下的像。證明也是單射的。（4分）證明：假設(shè)，且。（1分）不妨