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

1.下列哪個命題是永真的？

A.p∧?p

B.p∨?p

C.p→?p

D.?(p∧q)?(?p∨?q)

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

A.{1,2}

B.{3,4}

C.{2,3}

D.{1,4}

3.下列哪個圖是歐拉圖？

A.完全圖K3

B.斐波那契數(shù)列

C.哈密頓圖

D.無向連通圖，所有頂點度數(shù)均為偶數(shù)

4.設(shè)函數(shù)f:A→B,其中A={1,2,3},B={a,b,c},則下列哪個映射是滿射？

A.f(1)=a,f(2)=b,f(3)=c

B.f(1)=a,f(2)=a,f(3)=b

C.f(1)=b,f(2)=c,f(3)=a

D.f(1)=b,f(2)=b,f(3)=b

5.下列哪個是偏序關(guān)系？

A.<,≤

B.≠,=

C.∧,∨

D.→,?

6.設(shè)G是一個無向圖，頂點數(shù)n=6,邊數(shù)m=10,則G的連通分支數(shù)最多為：

A.1

B.2

C.3

D.4

7.下列哪個是可判定的？

A.哈密頓路徑問題

B.旅行商問題

C.3-SAT問題

D.判定一個圖是否為平面圖

8.下列哪個是可歸約的？

A.停機問題

B.哈密頓路徑問題

C.旅行商問題

D.判定一個圖是否為連通圖

9.設(shè)集合A={1,2,3,4},B={a,b},則A×B的基數(shù)是：

A.4

B.6

C.8

D.16

10.下列哪個是可解的？

A.算法復(fù)雜性理論

B.不可解問題

C.可判定問題

D.遞歸函數(shù)理論

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

1.下列哪些是命題邏輯的永真式？

A.p∨?p

B.(p∧q)→p

C.p∧(q∨r)?(p∧q)∨(p∧r)

D.(p→q)?(?q→?p)

2.設(shè)集合A={1,2,3},B={a,b},C={x,y},則下列哪些是A×(B×C)的元素？

A.(1,(a,x))

B.(2,(b,y))

C.((1,a),y)

D.((2,b),x)

3.下列哪些是等價關(guān)系？

A.數(shù)軸上的點與其實數(shù)的對應(yīng)關(guān)系

B.集合的包含關(guān)系?

C.整數(shù)的模n等價關(guān)系

D.三角形的全等關(guān)系

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

A.頂點

B.邊

C.鄰接矩陣

D.歐拉回路

5.下列哪些問題屬于NP完全問題？

A.哈密頓路徑問題

B.旅行商問題

C.3-SAT問題

D.判定一個圖是否為連通圖

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

1.若集合A有n個元素，則A的冪集P(A)的基數(shù)是________。

2.關(guān)系R={(1,a),(2,b),(3,a)}的逆關(guān)系R?1是________。

3.一個具有n個頂點的無向完全圖有________條邊。

4.設(shè)函數(shù)f:Z→Z定義為f(x)=x+1，則f是________函數(shù)（單射/滿射/雙射）。

5.哈密頓路徑問題是圖論中一個著名的問題，它要求在圖中找到一條經(jīng)過所有頂點exactly一次的________。

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

1.設(shè)命題公式P為(p→q)∧(?q→?p)，求P的真值表。

2.給定集合A={1,2,3,4}，B={a,b,c}，計算A×B并寫出其所有元素。

3.設(shè)關(guān)系R定義為集合A={1,2,3}上的二元關(guān)系R={(1,2),(2,3),(3,1)}，判斷R是否是等價關(guān)系，并說明理由。

4.給定無向圖G，頂點集V={v1,v2,v3,v4}，邊集E={(v1,v2),(v2,v3),(v3,v4),(v4,v1),(v1,v3)}。求圖G的度數(shù)序列，并判斷圖G是否是連通圖。

5.設(shè)函數(shù)f:A→B定義為f(x)=2x+1，其中A={1,2,3}，B={3,5,7,9}。判斷函數(shù)f是否是滿射，并說明理由。

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

一、選擇題答案及解析

1.B

解析：p∨?p是命題邏輯中的永真式，稱為排中律。

2.C

解析：A∩B={元素屬于A且屬于B}={2,3}。

3.D

解析：無向連通圖，所有頂點度數(shù)均為偶數(shù)是歐拉圖的定義。

4.A

解析：滿射是指B中每個元素至少被A中一個元素映射。A選項中每個元素都被映射到。

5.A

解析：<,≤是自反的、antisymmetric（反對稱的）、transitive（傳遞的）關(guān)系，符合偏序關(guān)系定義。

6.C

解析：無向圖最多有n-1條邊連通，超過n-1則必不連通。n=6,m=10>5，最多3個連通分支。

7.D

解析：判定一個圖是否為平面圖可以使用歐拉公式或庫拉托夫斯基定理等方法，屬于可判定問題。其他問題均為NP難問題。

8.A

解析：停機問題是不可解的，根據(jù)圖靈論題，任何試圖解決停機問題的算法本身就會導(dǎo)致矛盾，因此它是不可歸約的（不可解的）。

9.C

解析：A×B={(a,x)|a∈A,x∈B}，共有3×2=6個元素。基數(shù)是8。

10.C

解析：可判定問題是指存在一個算法能在有限步驟內(nèi)給出確定答案的問題。判定一個圖是否為連通圖就是這樣的問題。

二、多項選擇題答案及解析

1.A,B,C

解析：A是排中律，永真。B是蘊含式的恒真賦值（當(dāng)q為假時，p→q為真）。C是分配律，永真。D是反證法等價式，永真。

2.A,B,D

解析：A×(B×C)={(x,(y,z))|x∈A,(y,z)∈B×C}。B×C={(a,x),(b,x),(a,y),(b,y)}。所以A×(B×C)={(1,(a,x)),(1,(b,y)),(2,(a,x)),(2,(b,y))}。選項A(1,(a,x))，B(2,(b,y))，D((2,b),x)在展開后屬于該集合。選項C((1,a),y)屬于A×B。

3.A,B,C,D

解析：A中實數(shù)在數(shù)軸上關(guān)于原點對稱，滿足自反、對稱、傳遞，是等價關(guān)系。B中?滿足自反、antisymmetric、傳遞，是偏序關(guān)系，也是等價關(guān)系（若改為?且=，則為等價關(guān)系）。C中模n等價關(guān)系滿足自反、對稱、傳遞，是等價關(guān)系。D中全等三角形滿足自反、對稱、傳遞，是等價關(guān)系。

4.A,B,C,D

解析：頂點和邊是圖的基本組成元素。鄰接矩陣是圖的表示方法之一。歐拉回路是圖論中的一個重要概念和研究對象。

5.A,B,C

解析：哈密頓路徑問題、旅行商問題、3-SAT問題都是已知的NP完全問題。判定一個圖是否為連通圖是可判定的（甚至很易判定），不屬于NP完全問題。

三、填空題答案及解析

1.2?

解析：集合A有n個元素，其冪集P(A)包含所有可能的子集，數(shù)量為2?。

2.{(a,1),(b,2),(a,3)}

解析：逆關(guān)系R?1={(y,x)|(x,y)∈R}。將原關(guān)系中的元素順序互換即可。

3.n(n-1)/2

解析：無向完全圖是指每對不同的頂點之間都有一條邊。n個頂點有n(n-1)/2對不同的頂點，因此有n(n-1)/2條邊。若允許自環(huán)，則為n2條邊。

4.單射

解析：對于任意x?,x?∈Z，若x?≠x?，則f(x?)=x?+1≠x?+1=f(x?)。滿足單射定義。但不是滿射，例如2不在像集{...,0,2,3,...}中。

5.路徑

解析：哈密頓路徑問題是指在圖中尋找一條經(jīng)過所有頂點exactly一次的路徑。

四、計算題答案及解析

1.真值表：

|p|q|p→q|?q→?p|(p→q)∧(?q→?p)|

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

|T|T|T|T|T|

|T|F|F|T|F|

|F|T|T|F|F|

|F|F|T|T|T|

解析：計算各子公式真值，然后根據(jù)邏輯連接符計算最終結(jié)果。該公式永真。

2.A×B={(1,a),(1,b),(2,a),(2,b),(3,a),(3,b),(4,a),(4,b)}

解析：將集合A中的每個元素與集合B中的每個元素配對，構(gòu)成笛卡爾積的元素。

3.不是等價關(guān)系。

解析：判斷是否滿足自反性：(1,1),(2,2),(3,3)?R，不滿足自反性。因此R不是等價關(guān)系。無需判斷對稱性和傳遞性。

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

解析：度數(shù)序列為各頂點的度數(shù)按頂點順序排列。v1度數(shù)2（v1v2,v1v3）；v2度數(shù)3（v1v2,v2v3,v2v4）；v3度數(shù)3（v1v3,v2v3,v3v4）；v4度數(shù)2（v1v4,v2v4,v3v4）。圖連通性可通過觀察或使用深度優(yōu)先搜索/廣度優(yōu)先搜索驗證，如圖中存在從任一頂點可達其他所有頂點的路徑（如v1→v2→v3→v4或v1→v3→v4→v2），故連通。

5.不是滿射。

解析：滿射要求B中每個元素至少是A中某個元素的像。f(1)=3,f(2)=5,f(3)=7。B={3,5,7,9}中元素9不是A中任何元素的像（因為f(x)=2x+1最大值為f(3)=7），因此f不是滿射。

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

本試卷主要涵蓋離散數(shù)學(xué)中的基礎(chǔ)理論部分，包括命題邏輯、集合論、關(guān)系論、圖論和函數(shù)論。其核心知識點可歸納為以下幾類：

1.**命題邏輯**：

*基本概念：命題、聯(lián)結(jié)詞（?,∧,∨,→,?）、真值表。

*邏輯等價式：掌握常見的等價式定律（如結(jié)合律、交換律、分配律、德摩根律、反證律、排中律等）及其應(yīng)用。

*范式：知識深度要求可能涉及主范式（析取范式和合取范式）的概念，但不一定需要深入轉(zhuǎn)換。

*考察點：通過真值表判斷公式的類型（永真式、矛盾式、可滿足式），運用等價式進行推理和化簡。

2.**集合論**：

*基本概念：集合、元素、子集、冪集、笛卡爾積。

*集合運算：并集、交集、差集、補集，及其性質(zhì)和運算律。

*基數(shù)：有限集的基數(shù)計算，無限集基數(shù)的概念（如可數(shù)集、不可數(shù)集）。

*考察點：計算集合運算結(jié)果，求冪集基數(shù)，理解笛卡爾積結(jié)構(gòu)。

3.**關(guān)系論**：

*關(guān)系的概念：有序?qū)Α㈥P(guān)系矩陣、關(guān)系圖。

*關(guān)系的性質(zhì)：自反性、對稱性、傳遞性（判斷關(guān)系是否為等價關(guān)系、偏序關(guān)系）。

*關(guān)系的運算：復(fù)合關(guān)系、逆關(guān)系。

*考察點：判斷關(guān)系是否具有特定性質(zhì)，計算復(fù)合關(guān)系和逆關(guān)系，理解關(guān)系矩陣和關(guān)系圖的應(yīng)用。

4.**圖論**：

*基本概念：無向圖、有向圖、頂點、邊、度數(shù)（入度、出度、總度數(shù)）、路徑、回路、連通性。

*圖的表示：鄰接矩陣、鄰接表。

*圖的性質(zhì)：歐拉圖、哈密頓圖、平面圖。

*圖的運算：補圖、并圖、交圖。

*考察點：計算度數(shù)序列，判斷圖的基本性質(zhì)（如連通性、歐拉性），理解圖的表示方法，計算圖的度數(shù)。

5.**函數(shù)論**：

*基本概念：函數(shù)、定義域、值域、像集、單射（Injection）、滿射（Surjection）、雙射（Bijection）。

*函數(shù)的性質(zhì)：判斷函數(shù)是否為單射、滿射、雙射。

*函數(shù)的運算：復(fù)合函數(shù)。

*考察點：判斷函數(shù)的類型，計算復(fù)合函數(shù)，理解函數(shù)的基本概念和性質(zhì)。

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

***選擇題**：主要考察對基本定義、定理、性質(zhì)的記憶和理解。題型豐富，可能涉及判斷正誤、選擇最符合條件者、比較不同概念等。例如，判斷關(guān)系是否為偏序關(guān)系，需要同時檢驗自反性、反對稱性和傳遞性。判斷函數(shù)是否為滿射，需要檢查值域是否等于目標集合。

*示例：判斷“圖論中，所有頂點度數(shù)均為偶數(shù)的無向連通圖是歐拉圖”是否正確?？疾禳c是歐拉圖的定義。正確。

***多項選擇題**：考察對知識點的全面掌握和辨析能力。一個題目可能涉及多個相關(guān)或易混淆的概念，需要選出所有正確的選項。例如，判斷哪些命題公式是永真式，需要熟悉常見的永真式形式，并可能需要通過真值表或推理判斷。

*示例：判斷哪些關(guān)系是等價關(guān)系?？疾禳c是等價關(guān)系的定義。正確選項應(yīng)包含滿足自反、對稱、傳遞性的關(guān)系。

***填空題**：考察對核心概念、公式、定理的準確記憶和應(yīng)用能力。通常填寫關(guān)鍵術(shù)語、數(shù)字或簡潔的表達式。例如，填寫集合的冪集基數(shù)公式，考察點是指數(shù)運算與集合元素數(shù)量的關(guān)系。2?。

*示例：填寫函數(shù)f(x)=x+1的類型?？疾禳c是單射的定義。