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

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

A．{1,2}AB．{1,2,3}A

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

2．已知無向圖G的結點度數之和為10，則G的邊數為（）．

A．10B．20

C．30D．5

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

A.5B.10

C.9D.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）ES（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={1，2}，B={a,b,c}，則AB的元素個數為．

7．有n個結點的無向完全圖的邊數為．

8．設無向圖G中存在歐拉路，則G的奇數度數的結點數為．

9．設G是有10個結點的連通圖，邊數為20，則可從G中刪去條邊后使

之變成樹．

10．設個體域D＝{1,2,3,4}，則謂詞公式(x)A(x)消去量詞后的等值式

為．

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

11．將語句“小明是個學生．”翻譯成命題公式．

12．將語句“他上午去教室上課，下午去體育館參加比賽．”翻譯成命題公式．

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

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

14．完全圖K4不是平面圖．

1

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

15．設關系R的關系圖如下，試

d

bc

a

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

（2）判斷R是否為等價關系，并說明理由．

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

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

（2）寫出其鄰接矩陣；

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

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

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

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

18．對任意集合A，B和C，試證明A(BC)=(AB)(AC)．

2

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

參考解答

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

1．B2．D3．C4．C5．A

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

6．6

7．n(n-1)/2

8．兩個或零個（注：答“兩個”也給3分）

9．11

10．A(1)∧A(2)∧A(3)∧A(4)

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

11．設P：小明是個學生．（2分）

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

12．設P：他上午去教室上課，

Q：他下午去體育館參加比賽．（2分）

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

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

13．正確．（3分）

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

則有AB且AB．（7分）

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

14．錯誤．（3分）

完全圖K4是平面圖，（5分）

如K4可以如下圖示嵌入平面．（7分）

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

15．解：（1）R={<a,b>,<b,a>,<a,c>,<c,a>,<c,d>,<d,c>}．（4分）

（2）不是等價關系（8分）

因為該關系不滿足自反性（或答：不滿足傳遞性）（12分）

16．解：（1）關系圖

3

（3分）

（2）鄰接矩陣

0101

1001（6分）

0000

1100

（3）deg(v1)=2

deg(v2)=2

deg(v3)=0

deg(v4)=2（9分）

（4）補圖

（12分）

17．解：P∨(Q∧R)(P∨Q)∧(P∨R)合取范式（2分）

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

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

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

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

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

18．證明：設S=A(BC)，T=(AB)(AC)，

若<x,y>∈S，則有x∈A且y∈(BC)，即x∈A且y∈B或y∈C，（1分）

即有x∈A且y∈B，或x∈A且y∈C，（2分）

可得<x,y>∈(AB)，或<x,y>∈(AC)，（3分）

則有<x,y>∈(AB)(AC)，即<x,y>∈T，（4分）

所以ST．（5分）

反之，若<x,y>∈T，則有<x,y>∈(AB)，或<x,y>∈(AC)，

則有x∈A且y