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

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

A．{1}AB．{1}A

C．{1,2,3}AD．A

2．設A={1,2,3｝，B={1,2,3,4}，A到B的關系R={<x,y>|x大于y｝，則R=()．

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

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

3．無向圖G的結點的度數之和是10，則圖G的邊數為（）．

A．10B．15

C．20D．5

4．設連通平面圖G有v個結點，e條邊，r個面，則（）．

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

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

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

A．不確定B．由y的取值確定

C．FD．T

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

6．設集合A={a,b,c}，B={b,c}，C={c,d}，則A∩(B∪C)等于．

7．設A={2，3}，B={1，2}，C={3，4}，從A到B的函數f={<2,2>,<3,1>}，從B到C

的函數g={<1，3>,<2，4>}，則Dom(gf)等于．

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

為．

9．設G是漢密爾頓圖，S是其結點集的一個子集，若S的元素個數為4，則在G-S中

的連通分支數不超過．

10．設個體域D＝{1,2,3,4}，A(x)為“x大于5”，則謂詞公式(x)A(x)的真值

為．

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

11．將語句“雪是白色的，但天是藍色的．”翻譯成命題公式．

12．將語句“如果下雨，則活動取消．”翻譯成命題公式．

四、判斷說明題（判斷各題正誤，并說明理由．每小題7分，本題共14分）

13．集合的元素可以是集合．

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

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

15．設A={1，2，3}，R={<x，y>|xA，yA且x+y>4}，S={<x，y>|xA，yA且x<y}，

試求R，S，R-1，s(S)．

1

16．圖G=<V,E>，其中V={a,b,c,d}，E={(a,b),(a,c),(a,d),(b,c),(b,d),(c,d)}，對

應邊的權值依次為2、3、4、5、6及7，試

（1）畫出G的圖形；

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

（3）求出G權最小的生成樹及其權值．

17．試畫一棵帶權為1,1,3,4,4的最優二叉樹,并計算該最優二叉樹的權．

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

18．試證明：P∨QP→（(P∨Q)）．

2

離散數學（本）2015年10月份試題

參考解答

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

1．B2．A3．D4．C5．D

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

6．{b，c}

7．{2，3}（或A）

8．b

9．4

10．假（或F，或0）

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

11．設P：雪是白色的，Q：天是藍色的．（2分）

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

12．設P：下雨，Q：活動取消．（2分）

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

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

13．正確．（3分）

例：集合{{1}}中的元素{1}是集合．（7分）

14．錯誤．（3分）

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

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

15．

R={<2,3>,<3,2>,<3,3>}（3分）

S={<1,2>,<1,3>,<2,3>}（6分）

R-1={<2,3>,<3,2>,<3,3>}（9分）

s(S)={<1,2>,<1,3>,<2,3>,<2,1>,<3,1>,<3,2>}（12分）

16．（1）G的圖形表示為：

a4d

3

27（3分）

6

bc

5

3

0111

1011

（2）鄰接矩陣：（6分）

1101

1110

（3）粗線與結點表示的是最小生成樹，

a4d

3

27（10分）

6

bc

5

權值為9（12分）

17．13

5

8

2

344

（10分）

11

權為13+13+32+42+42=28（12分）

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

18．證明：

（1）P∨QP（1分）

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

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

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

（5）(P∨Q)T（4）E