一、單項(xiàng)選擇題（每小題3分，本題共15分）

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

則R=()．

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

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

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

A．AB．{a}A

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

3．設(shè)個(gè)體域?yàn)檎麛?shù)集，則公式(x)(y)(x-y=2)的解釋可為()．

A．存在一整數(shù)x有整數(shù)y滿足x-y=2

B．存在一整數(shù)x對(duì)任意整數(shù)y滿足x-y=2

C．對(duì)任一整數(shù)x存在整數(shù)y滿足x-y=2

D．任一整數(shù)x對(duì)任意整數(shù)y滿足x-y=2

4．n階無(wú)向完全圖Kn的邊數(shù)及每個(gè)結(jié)點(diǎn)的度數(shù)分別是（）．

A．n(n-1)與nB．n(n-1)與n-1

C．n-1與nD．n(n-1)/2與n-1

5．設(shè)G為連通無(wú)向圖，則（）時(shí)，G中存在歐拉回路．

A．G不存在奇數(shù)度數(shù)的結(jié)點(diǎn)B．G存在一個(gè)奇數(shù)度數(shù)的結(jié)點(diǎn)

C．G存在兩個(gè)奇數(shù)度數(shù)的結(jié)點(diǎn)D．G存在偶數(shù)度數(shù)的結(jié)點(diǎn)

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

6．設(shè)集合A={x|x是小于4的正整數(shù)}，用集合的列舉法

A=．

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

b>}，從B到C的函數(shù)g={<a，2>,<b，1>}，則復(fù)合函數(shù)gf

=．

8．設(shè)G=<V，E>是一個(gè)圖，結(jié)點(diǎn)度數(shù)之和為30，則G的邊數(shù)

為．

9．設(shè)G是具有n個(gè)結(jié)點(diǎn)m條邊k個(gè)面的連通平面圖，則n+k2

=．

10．設(shè)個(gè)體域D＝{2,3,4}，A(x)為“x小于3”，則謂詞公式（x）A(x)的真值

為．

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

11．將語(yǔ)句“如果今天下雨，那么明天的比賽就要延期．”翻譯成命題公式．

1

12．將語(yǔ)句“地球是圓的，太陽(yáng)也是圓的．”翻譯成命題公式．

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

13．設(shè)A={a，b，c，d}，R={<a，b>,<b，a>，<a，a>，<b，b>，<c，

c>}，則R是等價(jià)關(guān)系．

14．(x)(P(x)∧Q(y))→R(x)中量詞的轄域?yàn)?P(x)∧Q(y))．

五．計(jì)算題（每小題12分，本題共36分）

15．設(shè)集合A={a,b,c}，B={b,c,d}，試計(jì)算

（1）AB；（2）AB；（3）A×B．

16．設(shè)G=<V，E>，V={v1,v2,v3,v4}，E={(v1,v2),(v1,v3),(v1,v4),(v2,v3),(v3,v4)}，

試

（1）給出G的圖形表示；（2）寫出其鄰接矩陣；

（3）求出每個(gè)結(jié)點(diǎn)的度數(shù)；（4）畫出其補(bǔ)圖的圖形．

17．試?yán)肒ruskal算法求出如下所示賦權(quán)圖中的最小生成樹(shù)（要求寫出求

解步驟），并求此最小生成樹(shù)的權(quán)．

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

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

2

離散數(shù)學(xué)（本）2018年1月份試題

參考解答

一、單項(xiàng)選擇題（每小題3分，本題共15分）

1．B2．D3．C4．D5．A

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

6．{1,2,3}7．{<1，2>,<2，1>}

8．159．m

10．假（或F，或0）

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

11．設(shè)P：今天下雨，Q：明天的比賽就要延期．（2分）

則命題公式為：PQ．（6分）

12．設(shè)P：地球是圓的，Q：太陽(yáng)是圓的．（2分）

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

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

13．錯(cuò)誤．（3分）

R不是等價(jià)關(guān)系，因R中不含<d，d>，故不滿足自反性．（7分）

14．正確．（3分）

轄域?yàn)榫o接量詞之后的最小子公式(P(x)∧Q(y))．（7分）

五．計(jì)算題（每小題12分，本題共36分）

15．（1）AB={a,b,c,d}；（4分）

（2）AB={a}；（8分）

（3）A×B={<a,b>,<a,c>,<a,d>,<b,b>,<b,c>,<b,d>,<c,b>,

<c,c>,<c,d>}（12分）

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

v1

v2

v3v4

圖一（3分）

（2）鄰接矩陣：

3

（6分）

（3）deg(v1)=3，

deg(v2)=2，

deg(v3)=3，

deg(v4)=2（9分）

（4）補(bǔ)圖如圖二所示：

v1

v2

v3v4

圖二（12分）

17．用Kruskal算法求產(chǎn)生的最小生成樹(shù)．步驟為：

w(v1,v7)=1選e1=v1v7

w(v7,v4)=1選e2=v7v4

w(v1,v6)=2選e3=v1v6

w(v3,v4)=3選e4=v3v4

w(v2,v7)=4選e5=v2v7

w(v5,v7)=5選e6=v5v7（6分）

最小生成樹(shù)如圖三所示：

（9分）

圖三

最小生成樹(shù)的權(quán)W(T)=1+1+2+3+4+5=16．（12分）

說(shuō)明：用其它方法，結(jié)果正確參照給分．

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

18．證明：

（1）P→QP（1分）

4

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

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

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

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

（6）(P→Q)T（5）E