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

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

A．A＝BB．BA

C．BAD．BA

2．設A＝｛1,2,3｝，B={2,4,6}，A到B的關系R＝｛〈x,y〉|2x=y｝，則R=()．

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

C.{<1,1>,<2,2>,<3,3>}D.{<1,2>,<2,4>,<3,6>}

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

A.20B.9

C.10D.11

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

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（x）ES（1）．

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

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

5．設個體域為整數集，則公式xy(x+y=2)的解釋可為()．

A.任一整數x，對任意整數y滿足x+y=2B.對任一整數x，存在整數y滿足x+y=2

C.存在一整數x，對任意整數y滿足x+y=2D.存在一整數x，有整數y滿足x+y=2

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

6．設集合A={1,2,3}，B={2,3,4}，C={3,4,5}，則B∪(A–C)等于．

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

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

8．兩個圖同構的必要條件包括結點數相等、邊數相等與．

9．設G是連通平面圖，v,e,r分別表示G的結點數，邊數和面數，v值為5，e值為4

則r的值為．

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

為．

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

11．將語句“昨天下雨，今天仍然下雨．”翻譯成命題公式．

12．將語句“若不下雨，我們就去參加比賽．”翻譯成命題公式．

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

13．若圖G是一個歐拉圖，則圖G中存在歐拉路．

14．無向圖G的結點數比邊數多1，則G是樹．

1

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

15．設集合A={1,2,3,4}上的關系：

R={<1，2>,<2，3>,<3，4>}，S={<1，1>,<2，2>,<3，3>}，

試計算（1）RS；（2）R1；（3）r（RS）．

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

邊的權值依次為1、1、5、2、3及4，請畫出G的圖形、寫出G的鄰接矩陣并求出G權最小

的生成樹及其權值．

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

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

18．設A，B，C均為任意集合，試證明：A(BC)=(AB)(AC)．

2

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

參考解答

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

1．C2．D3．A4．D5．B

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

6．{1,2,3,4}

7．{3,4}

8．度數相同的結點數相等

9．1

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

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

11．設P：昨天下雨，Q：今天下雨．（2分）

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

12．設P：下雨，Q：我們去參加比賽．（2分）

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

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

13．正確．（3分）

因為若圖G是一個歐拉圖，則圖中存在歐拉回路．（5分）

按定義知，歐拉回路也是歐拉路．（7分）

14．錯誤．（3分）

反例：如圖G的結點數比邊數多1，但不是樹．

（或：按定義有：無向圖G是樹當且僅當無向圖G是連通圖且邊數比結點數少1．）

（7分）

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

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

15．解：（1）RS=={<1，2>，<2，3>}；（4分）

（2）R1={<2，1>,<3，2>,<4，3>}；（8分）

（3）r（RS）={<1，1>,<2，2>,<3，3>,<4，4>}（12分）

16．解：G的圖形表示為：

3

（3分）

鄰接矩陣：

0111

1011

（6分）

1101

1110

粗線表示的圖是最小的生成樹，權為5：（9分）

（12分）

17．解：（P∨Q）∨R

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

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

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

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

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

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

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

18．證明：

設S=A(BC)，T=(AB)(AC)，

若x∈S，則x∈A且x∈BC，即x∈A，并且x∈B且xC，（2分）

所以x∈(AB)且x(AC)，得x∈T，（3分）

所以ST．（4分）

反之，若x∈T，則x∈(AB)且x(AC)，