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

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

A.非

B.且

C.或

D.等價(jià)

2.在謂詞邏輯中，下列哪個(gè)符號(hào)表示“所有”？

A.?

B.?

C.→

D.?

3.設(shè)集合A={1,2,3}，B={2,3,4}，則A∪B等于？

A.{1,2,3}

B.{2,3,4}

C.{1,2,3,4}

D.{1,4}

4.下列哪個(gè)不是圖的基本概念？

A.頂點(diǎn)

B.邊

C.權(quán)重

D.環(huán)

5.在樹中，下列哪個(gè)定義是正確的？

A.至少有一個(gè)根的連通無向圖

B.沒有環(huán)的連通無向圖

C.至少有一個(gè)根的無向圖

D.沒有環(huán)的無向圖

6.下列哪個(gè)不是圖遍歷算法？

A.深度優(yōu)先搜索

B.廣度優(yōu)先搜索

C.Dijkstra算法

D.Floyd算法

7.在集合論中，下列哪個(gè)符號(hào)表示“屬于”？

A.∈

B.?

C.?

D.?

8.下列哪個(gè)不是關(guān)系的基本性質(zhì)？

A.自反性

B.對(duì)稱性

C.傳遞性

D.可逆性

9.在組合數(shù)學(xué)中，下列哪個(gè)符號(hào)表示排列？

A.P(n,k)

B.C(n,k)

C.Σ

D.∏

10.下列哪個(gè)不是數(shù)理邏輯的基本推理規(guī)則？

A.拒絕式

B.合取引入

C.附加式

D.拉格朗日規(guī)則

二、多項(xiàng)選擇題（每題4分，共20分）

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

A.非

B.且

C.或

D.等價(jià)

E.如果

2.在謂詞邏輯中，下列哪些符號(hào)表示量詞？

A.?

B.?

C.→

D.?

E.∧

3.設(shè)集合A={1,2,3}，B={2,3,4}，C={3,4,5}，則下列哪些是A∩B∩C的子集？

A.{1}

B.{2}

C.{3}

D.{4}

E.{5}

4.下列哪些是圖的基本概念？

A.頂點(diǎn)

B.邊

C.權(quán)重

D.環(huán)

E.路

5.在樹中，下列哪些定義是正確的？

A.至少有一個(gè)根的連通無向圖

B.沒有環(huán)的連通無向圖

C.至少有一個(gè)根的無向圖

D.沒有環(huán)的無向圖

E.每對(duì)頂點(diǎn)之間都有唯一的路徑

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

1.在命題邏輯中，用字母p表示命題“今天是星期一”，則命題“今天不是星期一”可以表示為________。

2.在謂詞邏輯中，謂詞P(x)表示“x是偶數(shù)”，則表達(dá)式?x(P(x)→Q(x))表示________。

3.設(shè)集合A={a,b,c}，B={b,c,d}，則集合A與B的笛卡爾積A×B等于________。

4.在圖G中，若頂點(diǎn)u和頂點(diǎn)v之間存在一條邊，則稱頂點(diǎn)u和頂點(diǎn)v是________。

5.設(shè)T是一個(gè)樹，且T有n個(gè)頂點(diǎn)，則T有________條邊。

四、計(jì)算題（每題10分，共50分）

1.給定命題公式P:"他去看電影"，Q:"他下雨"，用自然語言寫出下列命題公式所表示的句子，并判斷其真假：(P→Q)?(?Q→?P)

2.設(shè)集合A={1,2,3}，B={x|x∈N且1≤x≤4}，C={x|x∈Z且-2≤x≤2}。求(A∩B)×C。

3.畫出下列命題邏輯公式的真值表，并判斷該公式是否為重言式：(P?Q)→(P??Q)

4.設(shè)無向圖G的頂點(diǎn)集V={v1,v2,v3,v4,v5}，邊集E={e1,e2,e3,e4,e5,e6}，其中e1=(v1,v2),e2=(v1,v3),e3=(v2,v4),e4=(v3,v4),e5=(v4,v5),e6=(v2,v5)。求圖G的度數(shù)序列，并判斷圖G是否是連通圖。

5.設(shè)集合A={1,2,3,4,5}，B={a,b,c}。計(jì)算從集合A到集合B的所有的函數(shù)個(gè)數(shù)，并給出其中一個(gè)雙射函數(shù)的例子。

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

一、選擇題答案

1.D

2.A

3.C

4.C

5.B

6.C

7.A

8.D

9.A

10.D

解題過程：

1.命題邏輯的基本聯(lián)結(jié)詞包括非、且、或、等價(jià)，故D不是基本聯(lián)結(jié)詞。

2.?表示“所有”，?表示“存在”，→表示“蘊(yùn)涵”，?表示“等價(jià)”，∧表示“合取”，故A表示“所有”。

3.A∪B包含A和B中的所有元素，即{1,2,3,4}。

4.圖的基本概念包括頂點(diǎn)、邊、環(huán)、路等，權(quán)重不是基本概念。

5.樹是至少有一個(gè)根的連通無向圖，且沒有環(huán)，故B正確。

6.圖遍歷算法包括深度優(yōu)先搜索和廣度優(yōu)先搜索，Dijkstra算法和Floyd算法是求最短路徑的算法。

7.∈表示“屬于”，?表示“包含于”，?表示“真包含于”，?表示“包含于”，故A表示“屬于”。

8.關(guān)系的基本性質(zhì)包括自反性、對(duì)稱性、傳遞性，可逆性不是基本性質(zhì)。

9.P(n,k)表示從n個(gè)元素中取出k個(gè)元素的排列數(shù)，C(n,k)表示組合數(shù)，Σ表示求和，∏表示求積，故A表示排列。

10.數(shù)理邏輯的基本推理規(guī)則包括合取引入、附加式、拒絕式等，拉格朗日規(guī)則不是基本推理規(guī)則。

二、多項(xiàng)選擇題答案

1.A,B,C,D

2.A,B

3.A,C

4.A,B,D,E

5.A,B,D

解題過程：

1.命題邏輯的基本聯(lián)結(jié)詞包括非、且、或、等價(jià)，故全選。

2.?表示“所有”，?表示“存在”，故A和B表示量詞。

3.A∩B∩C包含A、B、C中的公共元素，即{3}，其子集為{3}和空集{}，故A和C。

4.圖的基本概念包括頂點(diǎn)、邊、環(huán)、路，故全選。

5.樹是至少有一個(gè)根的連通無向圖，且沒有環(huán)，故A、B、D。

三、填空題答案

1.?P

2.對(duì)于所有的x，如果x是偶數(shù)，那么Q(x)成立

3.{(a,b),(a,c),(a,d),(b,b),(b,c),(b,d),(c,b),(c,c),(c,d)}

4.鄰接

5.n-1

解題過程：

1.?P表示命題P的否定，即“今天不是星期一”。

2.?x(P(x)→Q(x))表示對(duì)于所有的x，如果P(x)成立，那么Q(x)也成立。

3.A×B包含A中每個(gè)元素與B中每個(gè)元素的有序?qū)?，即{(a,b),(a,c),(a,d),(b,b),(b,c),(b,d),(c,b),(c,c),(c,d)}。

4.若頂點(diǎn)u和頂點(diǎn)v之間存在一條邊，則稱頂點(diǎn)u和頂點(diǎn)v是鄰接的。

5.樹有n個(gè)頂點(diǎn)，則必有n-1條邊。

四、計(jì)算題答案

1.命題公式表示的句子為：“如果他去看電影，那么他下雨”與“如果他不下雨，那么他不看電影”是等價(jià)的。該公式為重言式，因?yàn)槠湔嬷当碓谒星闆r下都為真。

2.(A∩B)×C={(1,1),(1,0),(1,-1),(2,1),(2,0),(2,-1),(3,1),(3,0),(3,-1)}。

3.真值表如下：

PQP?Q?Q→?P(P?Q)→(P??Q)

TTTTT

TFFTT

FTFTT

FFTTT

該公式為重言式。

4.度數(shù)序列為3,3,2,3,2。圖G是連通圖。

5.從集合A到集合B的所有的函數(shù)個(gè)數(shù)為3^5=243個(gè)。一個(gè)雙射函數(shù)的例子為f={1→a,2→b,3→c,4→a,5→b}。

知識(shí)點(diǎn)總結(jié)：

1.命題邏輯：基本聯(lián)結(jié)詞、量詞、命題公式、真值表、推理規(guī)則。

2.集合論：集合的基本運(yùn)算（并、交、差、補(bǔ)）、笛卡爾積、子集。

3.圖論：基本概念（頂點(diǎn)、邊、環(huán)、路）、度數(shù)序列、連通圖、遍歷算法。

4.組合數(shù)學(xué)：排列、組合、求和、求積。

5.數(shù)理邏輯：基本推理規(guī)則、重言式。

各題型所考察學(xué)生的知識(shí)點(diǎn)詳解及示例：

1.選擇題：考察學(xué)生對(duì)基本概念和定理的掌握程度，如命題邏輯的基本聯(lián)結(jié)詞、集合論的基本運(yùn)算、圖論的基本概念等。

2.多項(xiàng)選