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

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

A．{b,c,d}AB．A{c,d}

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

2．已知無向圖G的鄰接矩陣為

01100

10010

10011，

01101

00110

則G有（）．

A．6點，10邊B．5點，12邊

C．6點，5邊D．5點，6邊

3．無向圖G是個棵樹，結點數為10，則G的邊數是（）．

A．9B．10

C．11D．12

4．設A（x）：x是人，B（x）：x是工人，則命題“有人是工人”可符號化為（）．

A．(x)(A(x)∧B(x))B．┐(x)(A(x)→B(x))

C．(x)(A(x)∧B(x))D．┐(x)(A(x)∧┐B(x))

5．下面的推理正確的是（）．

A．(1)（x）F（x）→G（x）前提引入

(2)F（y）→G（y）US（1）．

B．(1)（x）（F（x）→G（x））前提引入

(2)F（y）→G（y）US（1）．

C．(1)（x）F（x）→G（x）前提引入

(2)F（y）→G（y）US（1）．

D．(1)（x）(F（x）→G（x））前提引入

(2)F（y）→G（x）ES（1）．

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

6．設A={a，b，c}，B={1，2，3}，作f：A→B，則不同的函數個數為．

7．任一無向圖中，度數為奇數的結點的個數為．

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

連通分支數不超過．

9．設G是有8個結點的連通圖，結點的度數之和為28，則可從G中刪去條

邊后使之變成樹．

10．設個體域D＝{1,2}，則謂詞公式(x)P(x)∨（x）Q（x）消去量詞后的等值式

為．

1

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

11．將語句“小張和小李都可以完成這項工作”翻譯成命題公式．

12．將語句“a是偶數當且僅當a能被2整除．”翻譯成命題公式．

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

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

13．存在集合A與B，使得AB與AB同時成立．

14．完全圖K5是平面圖．

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

15．設A={2,3,6,12,24,36}，B為A的子集，其中B={6,12}，R是A上的整除關系，試

（1）寫出R的關系表達式；

（2）說明R為偏序關系；

（3）畫出關系R的哈斯圖；

（4）求出B的最大元素、極大元素、上確界．

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

(v2,v4)，(v2,v5)，(v3,v4)，(v3,v5)，(v4,v5)}，試

（1）畫出G的圖形表示；

（2）寫出其鄰接矩陣；

（3）求出每個結點的度數；

（4）畫出圖G的補圖的圖形．

17．求P→（Q∧R）的合取范式與主合取范式．

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

18．對任意集合A，B和C，若有C，則有：AB的充分必要條件是CACB．

2

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

參考解答

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

1．D2．D3．A4．C5．B

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

6．27

7．偶數

8．6

9．7

10．(P(1)∧P(2))∨(Q（1）∨Q（2))

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

11．設P：小張可以完成這項工作，Q：小李可以完成這項工作．（2分）

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

12．設P：a是偶數，Q：a能被2整除．（2分）

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

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

13．正確．（3分）

例：設A={a}，B={a，{a}}（5分）

則有AB且AB．（7分）

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

14．錯誤．（3分）

完全圖K5是有5個結點10條邊，因35-6<10，即e3v-6對K5不成立，（5分）

故K5不是平面圖．（7分）

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

15．（1）因為在集合A={2,3,6,12,24,36}中，集合A上的整除關系R為：

R={<2,2>,<3,3>,<6,6>,<12,12>,<24,24>,<36,36>,<2,6>,<3,6>,

<2,12>,<3,12>,<6,12>,<2,24>,<3,24>,<6,24>,<12,24>,

<2,36>,<3,36>,<6,36>,<12,36>}．（3分）

（2）R中的每個有序對的第一個元素都可以整除第二個元素，即R為整除關系．每個數

可以整除自身，則關系R是自反的；

由R的元素可看出，若xy，當存在<x,y>R，就有<y,x>R，則說明關系R是反對稱

的；

由R的元素可看出，若存在<x,y>R，<y,z>R,就有<x,z>R，則說明關系R是傳遞的．

所以A上的整除關系R為偏序關系．（6分）

說明：只要指出R是自反的、反對稱的、傳遞的，即可給分．

（3）關系R的哈斯圖如圖一所示：

3

（9分）

圖一

（4）集合B的最大元素12、極大元素12、上確界為12（12分）

16．（1）關系圖如圖二所示：

v1

v2

v5

v3v4（3分）

圖二

（2）鄰接矩陣

01101

10111

11011（6分）

01101

11110

（3）deg(v1)=3

deg(v2)=4

deg(v3)=4

deg(v4)=3

deg(v5)=4（9分）

（）補圖如圖三所示：

4v1

v2

v5

v3v4

（12分）

圖三

17．P→（Q∧R）

P∨(Q∧R)（2分）

(P∨Q)∧(P∨R)合取范式（5分）

(P∨Q)∨(R∧R)∧(P∨R)（7分）

(P∨Q)∨(R∧R)∧(P∨R)∨(Q∧Q)（9分）

(P∨Q∨R)∧(P∨Q∨R)∧(P∨R∨Q)∧(P∨R∨Q)（11分）

(P∨Q∨R