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

1.在集合論中，符號(hào)∪表示什么運(yùn)算？

A.交集

B.并集

C.差集

D.補(bǔ)集

2.下列哪個(gè)是命題？

A.今天天氣很好

B.2+3=5

C.請(qǐng)開(kāi)門(mén)

D.火星人存在

3.在命題邏輯中，符號(hào)?表示什么連接詞？

A.或

B.與

C.非

D.雙條件

4.下列哪個(gè)是可滿足的命題公式？

A.(P∧?P)

B.(P∨?P)

C.(P∧Q)→P

D.(P→Q)∧(Q→P)

5.在圖論中，一個(gè)圖的頂點(diǎn)數(shù)V和邊數(shù)E滿足關(guān)系E≤V(V-1)/2，這個(gè)圖是什么類型的圖？

A.樹(shù)

B.完全圖

C.平凡圖

D.二分圖

6.在圖論中，一個(gè)有向圖中，如果存在一條從頂點(diǎn)u到頂點(diǎn)v的路徑，那么稱u和v是什么關(guān)系？

A.無(wú)向相鄰

B.有向相鄰

C.等價(jià)

D.相似

7.在數(shù)理邏輯中，謂詞邏輯的符號(hào)?表示什么？

A.對(duì)于所有

B.存在

C.非

D.雙條件

8.在集合論中，符號(hào)?表示什么關(guān)系？

A.等價(jià)

B.包含

C.不包含

D.相似

9.在圖論中，一個(gè)連通無(wú)向圖的最小生成樹(shù)有多少條邊？

A.1

B.2

C.V-1

D.V

10.在命題邏輯中，符號(hào)?表示什么運(yùn)算？

A.合取

B.析取

C.非運(yùn)算

D.雙條件

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

1.下列哪些是命題邏輯的合式公式？

A.P∧Q

B.(P∨Q)→R

C.P→(Q∧R)

D.(P∧?P)

E.?x(P(x)∨Q(x))

2.在集合論中，下列哪些關(guān)系是等價(jià)關(guān)系？

A.數(shù)軸上的點(diǎn)之間的距離關(guān)系

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

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

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

E.向量之間的平行關(guān)系

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

A.無(wú)向圖

B.有向圖

C.頂點(diǎn)的度數(shù)

D.邊的權(quán)重

E.圖的連通性

4.在謂詞邏輯中，下列哪些是量詞？

A.?（全稱量詞）

B.?（存在量詞）

C.?（非運(yùn)算）

D.∧（合取運(yùn)算）

E.∨（析取運(yùn)算）

5.在集合論中，下列哪些是基數(shù)？

A.可數(shù)無(wú)限集合的基數(shù)

B.實(shí)數(shù)集合的基數(shù)

C.自然數(shù)集合的基數(shù)

D.空集合的基數(shù)

E.有限集合的基數(shù)

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

1.在命題邏輯中，表達(dá)式(P∧Q)∨?P的等價(jià)式是________。

2.在集合論中，集合A={1,2,3}和B={3,4,5}的交集A∩B是________。

3.在圖論中，一個(gè)有n個(gè)頂點(diǎn)的完全圖有________條邊。

4.在謂詞邏輯中，表達(dá)式?x(P(x)→Q(x))的否定是________。

5.在集合論中，可數(shù)無(wú)限集合的基數(shù)用________表示。

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

1.已知集合A={x|x是小于10的正偶數(shù)}，B={x|x是小于10的正奇數(shù)}。求A∪B和A∩B。

2.寫(xiě)出命題公式(P∧Q)→?R的真值表。

3.給定圖G=<V,E>，其中V={a,b,c,d}，E={(a,b),(a,c),(b,d),(c,d)}。判斷圖G是否是連通圖，如果是，請(qǐng)給出一個(gè)生成樹(shù)。

4.在謂詞邏輯中，解釋表達(dá)式?x?y(P(x,y))的意義，并給出一個(gè)滿足該表達(dá)式的具體例子。

5.已知集合A={1,2,3,4,5}，B={2,4,6,8}。求A到B的所有可能函數(shù)的數(shù)量。

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

一、選擇題答案及解析

1.B并集

解析：∪符號(hào)表示集合的并集運(yùn)算，將兩個(gè)集合中的所有元素合并在一起，去除重復(fù)元素。

2.B2+3=5

解析：命題是能夠判斷真假的陳述句，2+3=5是一個(gè)數(shù)學(xué)等式，可以判斷真假。

3.D雙條件

解析：?符號(hào)表示雙條件連接詞，當(dāng)P和Q同時(shí)為真或同時(shí)為假時(shí)，P?Q為真。

4.B(P∨?P)

解析：(P∨?P)是一個(gè)永真式，因?yàn)镻和?P必有一個(gè)為真，所以它們的析取總是真。

5.B完全圖

解析：E≤V(V-1)/2表示圖中任意兩個(gè)頂點(diǎn)之間都有邊相連，這是完全圖的定義。

6.B有向相鄰

解析：在有向圖中，如果存在一條從頂點(diǎn)u到頂點(diǎn)v的路徑，則稱u和v有向相鄰。

7.B存在

解析：?符號(hào)表示存在量詞，用于表達(dá)存在至少一個(gè)元素滿足某個(gè)性質(zhì)。

8.B包含

解析：?符號(hào)表示集合的包含關(guān)系，A?B表示集合A中的所有元素都屬于集合B。

9.CV-1

解析：連通無(wú)向圖的最小生成樹(shù)有V-1條邊，這是最小生成樹(shù)的性質(zhì)。

10.C非運(yùn)算

解析：?符號(hào)表示非運(yùn)算，對(duì)命題取反，如果命題為真則結(jié)果為假，反之亦然。

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

1.A,B,C

解析：合式公式是按照邏輯語(yǔ)法規(guī)則構(gòu)造的命題，A,B,C都是合法的合式公式，而D不是。

2.A,C,D

解析：等價(jià)關(guān)系具有自反性、對(duì)稱性和傳遞性，A,C,D滿足這些性質(zhì)，而B(niǎo)和E不滿足。

3.A,B,C,D,E

解析：這些都是圖的性質(zhì)，包括圖的類型、頂點(diǎn)的度數(shù)、邊的權(quán)重和圖的連通性。

4.A,B

解析：量詞用于表達(dá)命題的適用范圍，?和?是謂詞邏輯中的量詞，而C,D,E是命題邏輯中的運(yùn)算符。

5.A,C,D,E

解析：基數(shù)是描述集合大小的概念，A,C,D,E都是常見(jiàn)的基數(shù)類型，而B(niǎo)不是。

三、填空題答案及解析

1.Q

解析：(P∧Q)∨?P等價(jià)于Q，因?yàn)闊o(wú)論P(yáng)真假，析取范式總能簡(jiǎn)化為Q。

2.{3}

解析：交集是兩個(gè)集合中都包含的元素，A和B都包含3，所以交集是{3}。

3.n(n-1)/2

解析：完全圖是每對(duì)頂點(diǎn)之間都有一條邊，n個(gè)頂點(diǎn)的完全圖有n(n-1)/2條邊。

4.?x(?P(x)∨Q(x))

解析：命題的否定是將其中的量詞和連接詞取反，并應(yīng)用德摩根律得到結(jié)果。

5.??或0

解析：可數(shù)無(wú)限集合的基數(shù)用阿列夫零表示，也可以用0表示。

四、計(jì)算題答案及解析

1.A∪B={1,2,3,4,5,6,7,8,9}，A∩B=?

解析：A是小于10的正偶數(shù)集合，B是小于10的正奇數(shù)集合，它們的并集是1到9的所有整數(shù)，交集為空。

2.真值表略

解析：需要列出P,Q,R的所有真值組合，并計(jì)算(P∧Q)→?R的結(jié)果。

3.圖G是連通圖，一個(gè)生成樹(shù)是{a,b,c,d}

解析：圖G中任意兩個(gè)頂點(diǎn)之間都有路徑相連，所以是連通圖，可以通過(guò)深度優(yōu)先搜索或廣度優(yōu)先搜索得到生成樹(shù)。

4.?x?y(P(x,y))表示對(duì)于所有x，都存在一個(gè)y使得P(x,y)為真

解析：例如，P(x,y)表示x是y的倍數(shù)，那么表達(dá)式表示所有自然數(shù)都是某個(gè)自然數(shù)的倍數(shù)。

5.2^5=32

解析：A到B的函數(shù)數(shù)量是B的基數(shù)（4）的A的基數(shù)（5）次方，即2^5。

知識(shí)點(diǎn)分類和總結(jié)

集合論：集合的運(yùn)算（并集、交集、差集、補(bǔ)集），集合的關(guān)系（包含、等價(jià)），基數(shù)，可數(shù)無(wú)限集合，無(wú)限集合。

命題邏輯：命題，連接詞（合取、析取、非、雙條件、蘊(yùn)含），命題公式，真值表，永真式，永假式。

謂詞邏輯：謂詞，量詞（全稱量詞、存在量詞），謂詞公式，解釋。

圖論：圖的基本概念（頂點(diǎn)、邊、無(wú)向圖、有向圖），圖的性質(zhì)（連通性、度數(shù)、權(quán)重），樹(shù)，生成樹(shù)，完全圖。

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

選擇題：考察學(xué)生對(duì)基本概念和