江南大學(xué)離散數(shù)學(xué)試卷一、選擇題（每題1分，共10分）

1.在集合論中，集合A包含元素1,2,3，集合B包含元素2,3,4，則集合A與集合B的交集是？

A.{1,2,3,4}

B.{2,3}

C.{1}

D.?

2.下列哪個不是命題？

A.今天天氣很好。

B.2+2=5。

C.請開門。

D.這個數(shù)是偶數(shù)。

3.命題公式(p→q)?(?p∨q)的等價形式是？

A.p?q

B.p→q

C.?p??q

D.p∨?q

4.在命題邏輯中，下列哪個是重言式？

A.p∧?p

B.p∨?p

C.p→?p

D.?p→p

5.在謂詞邏輯中，?x(P(x)→Q(x))的否定是？

A.?x(P(x)∧?Q(x))

B.?x(P(x)∧?Q(x))

C.?x(P(x)∧Q(x))

D.?x(P(x)→Q(x))

6.設(shè)有一個有向圖G，其頂點集V={v1,v2,v3,v4}，邊集E={(v1,v2),(v2,v3),(v3,v4),(v4,v1)}，則圖G的鄰接矩陣是？

A.

0100

0010

0001

1000

B.

1001

0100

0010

0001

C.

0100

0010

0001

1000

D.

1001

0100

0010

0001

7.在圖論中，一棵樹的邊數(shù)與其頂點數(shù)的關(guān)系是？

A.邊數(shù)=頂點數(shù)

B.邊數(shù)=頂點數(shù)-1

C.邊數(shù)=頂點數(shù)+1

D.邊數(shù)=2×頂點數(shù)

8.在組合數(shù)學(xué)中，從n個不同元素中取出k個元素的組合數(shù)記作C(n,k)，其計算公式是？

A.C(n,k)=n!/(k!×(n-k)!)

B.C(n,k)=k!/(n!×(n-k)!)

C.C(n,k)=n!/k!

D.C(n,k)=k!/n!

9.在數(shù)理邏輯中，下列哪個是正確的推理規(guī)則？

A.拒絕前件

B.合取引入

C.選擇引入

D.演繹推理

10.在布爾代數(shù)中，下列哪個是正確的等式？

A.a+a=0

B.a×a=0

C.a+0=a

D.a×1=0

二、多項選擇題（每題4分，共20分）

1.下列哪些是命題邏輯中的基本聯(lián)結(jié)詞？

A.與

B.或

C.非

D.如果

E.當且僅當

2.在集合論中，下列哪些運算滿足交換律？

A.并集

B.交集

C.差集

D.補集

E.笛卡爾積

3.在圖論中，下列哪些是樹的性質(zhì)？

A.無環(huán)

B.連通

C.頂點數(shù)等于邊數(shù)加1

D.可以有多個根

E.每對頂點之間有唯一路徑

4.在組合數(shù)學(xué)中，下列哪些是排列的計算公式？

A.P(n,k)=n!/(n-k)!

B.P(n,k)=n×(n-1)×...×(n-k+1)

C.P(n,k)=k!/(n-k)!

D.P(n,k)=n!/k!

E.P(n,k)=n×k

5.在數(shù)理邏輯中，下列哪些是正確的推理規(guī)則？

A.假言推理

B.拒絕后件

C.合取消除

D.析取引入

E.演繹推理

三、填空題（每題4分，共20分）

1.在命題邏輯中，公式(p∧q)→r的對偶式是________。

2.設(shè)集合A={1,2,3}，B={2,3,4}，則A∪B=________，A∩B=________。

3.在圖論中，一個有n個頂點的無向完全圖有________條邊。

4.在組合數(shù)學(xué)中，從n個不同元素中取出k個元素的組合數(shù)記作________，其計算公式是________。

5.在謂詞邏輯中，?x(P(x)→Q(x))的否定是________。

四、計算題（每題10分，共50分）

1.對于命題公式(p→q)?(?p∨q)，寫出它的真值表，并判斷它是否是重言式。

2.設(shè)集合A={x|x是小于10的正偶數(shù)}，B={x|x是小于10的正奇數(shù)}，C={1,3,5,7}。求(A∪B)×C。

3.給定有向圖G的鄰接矩陣如下：

```

0101

0010

0001

0000

```

求圖G的度數(shù)序列，并判斷圖G是否是強連通的。

4.計算C(10,3)和P(10,3)，并解釋它們的區(qū)別。

5.對于謂詞邏輯公式?x?y(P(x,y)∧Q(y))，假設(shè)解釋域為自然數(shù)集合N，P(x,y)表示"x小于y"，Q(y)表示"y是偶數(shù)"。在該解釋下，判斷該公式是否為真。

本專業(yè)課理論基礎(chǔ)試卷答案及知識點總結(jié)如下

一、選擇題答案

1.B

2.D

3.B

4.B

5.A

6.A

7.B

8.A

9.B

10.C

二、多項選擇題答案

1.A,B,C

2.A,B,D,E

3.A,B,C,E

4.A,B

5.A,C,E

三、填空題答案

1.(p∨q)→r

2.{1,2,3,4},{2,3}

3.n(n-1)/2

4.C(n,k),n!/(k!×(n-k)!)

5.?x(P(x)∧?Q(x))

四、計算題答案

1.真值表：

|p|q|p→q|?p∨q|(p→q)?(?p∨q)|

|---|---|-------|--------|----------------------|

|T|T|T|T|T|

|T|F|F|F|T|

|F|T|T|T|T|

|F|F|T|T|T|

該公式是重言式。

2.(A∪B)×C={(2,1),(2,3),(2,5),(2,7),(4,1),(4,3),(4,5),(4,7),(6,1),(6,3),(6,5),(6,7)}

3.度數(shù)序列：3,2,2,0。圖G不是強連通的，因為存在頂點無法通過有向邊到達所有其他頂點。

4.C(10,3)=10!/(3!×(10-3)!)=120，P(10,3)=10!/(10-3)!=720。組合數(shù)表示從10個元素中取3個不考慮順序，排列數(shù)表示考慮順序。

5.假設(shè)解釋域為自然數(shù)集合N，P(x,y)表示"x小于y"，Q(y)表示"y是偶數(shù)"。對于任意自然數(shù)x，存在一個自然數(shù)y（例如y=x+1）使得P(x,y)為真（因為x<x+1）。同時，如果y是偶數(shù)，則Q(y)為真。因此，對于任意自然數(shù)x，總能找到一個自然數(shù)y（當y為偶數(shù)時）使得P(x,y)∧Q(y)為真。所以該公式為真。

知識點分類和總結(jié)

離散數(shù)學(xué)的理論基礎(chǔ)部分主要包括以下知識點：

1.集合論：集合的運算（并集、交集、差集、補集）、集合的性質(zhì)、笛卡爾積等。

2.命題邏輯：命題、聯(lián)結(jié)詞、真值表、推理規(guī)則、對偶式等。

3.謂詞邏輯：謂詞、量詞、解釋域、公式等。

4.圖論：圖的表示（鄰接矩陣）、圖的性質(zhì)（無環(huán)、連通、度數(shù)序列）、圖的類型（完全圖、強連通圖）等。

5.組合數(shù)學(xué)：排列、組合、組合數(shù)計算公式等。

各題型所考察學(xué)生的知識點詳解及示例

一、選擇題

-考察學(xué)生對命題邏輯、集合論、圖論、組合數(shù)學(xué)等基本概念的掌握程度。

-示例：選擇題第1題考察集合的交集運算，第6題考察圖的鄰接矩陣表示。

二、多項選擇題

-考察學(xué)生對多個相關(guān)概念的理解和區(qū)分能力。

-示例：多項選擇題第1題考察命題邏輯