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

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

A．1AB．{1}A

C．AD．{2}A

2．設A={2,3｝，B={3,4}，A到B的關系R={<x,y>|xA,yB，且x不大于y｝，則R=

()．

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

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

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

A．12B．24

C．48D．23

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

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

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

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

A．TB．F

C．由y的取值確定D．不確定

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

6．設集合A={a,b}，B={b,c}，C={c,d}，則(AB)–(BC)=．

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

的函數g={<1，3>,<6，5>}，則Dom(gf)=．

8．結點數相等是兩個圖同構的條件．

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

的連通分支數不超過．

10．設個體域D＝{a,b}，則謂詞公式(x)Q(x)消去量詞后的等值式

為．

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

11．將語句“昨天是公休日，今天也是公休日．”翻譯成命題公式．

12．將語句“如果今天是周五，則明天是周四．”翻譯成命題公式．

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

13．如果A是集合B的元素，則A不可能是B的子集．

14．(x)(A(x)→(B(y)→C(z)))中的約束變元為y．

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

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

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

1

16．設圖G=<V,E>，其中，結點集V={a,b,c,d,e}，邊集E={(a,c),(a,e),(b,d),(b,e),

(c,e),(d,e)}，對應邊的權值依次為2、3、3、4、1及5，請畫出G的圖形、寫出G的鄰接

矩陣并求出G權最小的生成樹及其權值．

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

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

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

2

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

參考解答

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

1．C2．B3．A4．D5．A

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

6．{a,b}

7．{3，6}

8．必要

9．4

10．Q(a)∧Q(b)

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

11．設P：昨天是公休日，Q：今天是公休日．（2分）

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

12．設P：今天是周五，Q：明天是周四．（2分）

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

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

13．錯誤．（3分）

反例：設A={1}，B={1,{1}}，則A是B的元素，也是B的子集．（7分）

說明：舉出符合條件的反例均給分．

14．錯誤．（3分）

(x)(A(x)→(B(y)→C(z)))中的y是自由變元，約束變元為x．（7分）

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

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

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

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

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

說明：對于每一個求解項，如果基本求出了解，可以給對應1分．

16．G的圖形表示為：

（3分）

鄰接矩陣：

3

（6分）

如下為最小的生成樹，權為10：（9分）

（12分）

17．

（10分）

權為13+23+32+42+52=33（12分）

六、證明題（本題共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規則（8分）

說明1：因證明過程中，公式引用的次序可以不同，一般引用前提正確得1分，利用兩個公

式得出有效結論得1或2分，最后得出結論得2或1分。

說明2：另證如下：

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

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

所以P