試卷代號：1009座位號

2014年1月

題號一二三四五六總分

得分

一、單項選擇題（每小題3分，本題共15分）

1．若集合A＝{a,b,c}，則下列表述正確的是()．

A．{a}AB．{a}A

C．AD．{a,b,c}A

2．設(shè)A＝｛1,2｝，B={1,2,3,4,5}，A到B的關(guān)系R＝｛〈x,y〉|xA,yB且x+1=y｝，則

R=()．

A．{<1,1>,<2,2>}B．{<1,1>,<1,2>,<1,3>,<1,4>,<1,5>}

C．{<1,1>,<2,1>}D．{<1,2>,<2,3>}

3．無向圖G的邊數(shù)為12，則圖G的結(jié)點的度數(shù)之和是（）．

A．24B．12

C．6D．18

4．設(shè)連通平面圖G有v個結(jié)點，e條邊，r個面，則．

A．v+e-r=2B．r+v-e=2

C．v+e-r=4D．v+e–r=–4

5．設(shè)個體域D是整數(shù)集合，則命題xy(xy=y)的真值是（）．

A.不確定B.F

C.TD.以上說法都不是

二、填空題（每小題3分，本題共15分）

6．設(shè)集合A={1,2,3}，B={3,4,5}，C={5,6,7}，則A∪B–C等

于．

7．設(shè)A={1，2}，B={a，b}，C={3，4，5}，從A到B的函數(shù)f={<1,a>,<2,b>}，從B

到C的函數(shù)g={<a，4>,<b，3>}，則Ran(gf)等于．

8．若圖G=<V,E>，其中V={a,b,c,d}，E={(a,b),(a,d),(b,c),(b,d)}，則該圖中的割

邊為．

9．設(shè)G是歐拉圖，則G的奇數(shù)度數(shù)的結(jié)點數(shù)為個．

10．設(shè)個體域D＝{2,4,6}，A(x)為“x是偶數(shù)”，則謂詞公式(x)A(x)的真值為．

三、邏輯公式翻譯（每小題6分，本題共12分）

11．將語句“我學英語，并且學法語．”翻譯成命題公式．

12．將語句“除非小王來，否則小李不去．”翻譯成命題公式．

四、判斷說明題（每小題7分，本題共14分）

判斷下列各題正誤，并說明理由．

1

13．空集的冪集也是空集．

14．(x)(P(x)→Q(y)∧R(z))中的約束變元為y．

五、計算題（每小題12分，本題共36分）

15．設(shè)集合A={1,2,3}，R={<1，1>,<2，1>,<3，1>}，S={<1，2>,<2，2>}試計算

（1）RS；（2）R1；（3）r（R）．

16．圖G=<V,E>，其中V={a,b,c,d}，E={(a,b),(a,c),(a,d),(b,c),(c,d)}，對應(yīng)邊的

權(quán)值依次為6、5、2、3及8，試

（1）畫出G的圖形；

（2）寫出G的鄰接矩陣；

（3）求出G權(quán)最小的生成樹及其權(quán)值．

17．試畫一棵帶權(quán)為1,2,3,3,4的最優(yōu)二叉樹,并計算該最優(yōu)二叉樹的權(quán)．

六、證明題（本題共8分）

18．試證明：P→QP→(P∧Q)．

2

中央廣播電視大學學年度第學期“開放本科”期末考試

離散數(shù)學（本）試題答案及評分標準

(供參考)

一、單項選擇題（每小題3分，本題共15分）

1．B2．D3．A4．B5．C

二、填空題（每小題3分，本題共15分）

6．{1,2,3,4}

7．{3，4}

8．(b,c)

9．0

10．真（或T，或1）

三、邏輯公式翻譯（每小題6分，本題共12分）

11．設(shè)P：我學英語，Q：我學法語．（2分）

則命題公式為：P∧Q．（6分）

12．設(shè)P：小王來，Q：小李去．（2分）

則命題公式為：Q→P．（6分）

或P→Q

四、判斷說明題（每小題7分，本題共14分）

13．錯誤．（3分）

空集的冪集為{}．（7分）

14．錯誤．（3分）

(x)(P(x)→Q(y)∧R(z))中的約束變元為x．（7分）

五、計算題（每小題12分，本題共36分）

15．（1）RS=={<1，2>,<2，2>,<3，2>}；（4分）

（2）R1={<1，1>,<1，2>,<1，3>}；（8分）

（3）r（R）={<1，1>,<2，2>,<3，3>,<2，1>,<3，1>}（12分）

16．（1）G的圖形表示如圖一所示：

a2d

6

58

bc（分）

33

圖一

（2）鄰接矩陣：

0111

1010

（6分）

1101

1010

（3）圖二中的粗線與結(jié)點表示的是最小生成樹：

3

a2d

6

58

bc

3（10分）

圖二

權(quán)值為10（12分）

17．最優(yōu)二叉樹如圖三所示：

13

76

3

433

（10分）

12

圖三

權(quán)為13+23+32+32+42=29（12分）

說明：最優(yōu)二叉樹樹葉權(quán)值順序不同，參照評分．

六、證明題（本題共8分）

18．證明：

（1）P→QP（1分）

（2）PP（附加前提）（3分）

（3）QT（1）（2）I（5分）

（4）P∧QT（2）（3）I（7分）

（5）P→(P∧Q)CP規(guī)則（8分）

另證：

設(shè)P→(P∧Q)為F，（1分）

則P為T，PQ為F．（3分）

所以P為T，Q為F，（5分