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

1.在集合論中，集合A={1,2,3}與集合B={3,4,5}的并集是？

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

B.{1,2,3}

C.{3,4,5}

D.{1,2,4,5}

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

A.今天天氣很好。

B.2+3=5

C.請(qǐng)開門。

D.x+y=7

3.在命題邏輯中，命題p和命題q的合取（與）表示為？

A.p∨q

B.p→q

C.p∧q

D.p⊕q

4.下列哪個(gè)是永真式？

A.p∨?p

B.p∧?p

C.p→p

D.p⊕p

5.在謂詞邏輯中，?x(P(x))表示？

A.對(duì)所有x，P(x)成立

B.存在x，P(x)成立

C.P(x)不成立

D.對(duì)所有x，P(x)不成立

6.下列哪個(gè)是謂詞邏輯中的量詞？

A.?

B.?

C.→

D.∧

7.在圖論中，一個(gè)圖G=(V,E)中，頂點(diǎn)V的度數(shù)是指？

A.頂點(diǎn)的數(shù)量

B.邊的數(shù)量

C.與該頂點(diǎn)相連的邊的數(shù)量

D.圖的總邊數(shù)

8.下列哪個(gè)不是圖的性質(zhì)？

A.無向圖

B.有向圖

C.網(wǎng)絡(luò)圖

D.拓?fù)鋱D

9.在樹論中，一個(gè)樹的度是指？

A.樹的頂點(diǎn)數(shù)量

B.樹的邊數(shù)量

C.樹的最大度數(shù)

D.樹的層次數(shù)量

10.下列哪個(gè)不是樹的結(jié)構(gòu)？

A.二叉樹

B.森林

C.有向圖

D.無向圖

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

1.下列哪些是集合論中的基本運(yùn)算？

A.并集

B.交集

C.補(bǔ)集

D.差集

E.對(duì)稱差集

2.在命題邏輯中，下列哪些是邏輯聯(lián)結(jié)詞？

A.與（∧）

B.或（∨）

C.非（?）

D.蘊(yùn)含（→）

E.等價(jià)（?）

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

A.頂點(diǎn)

B.邊

C.鄰接矩陣

D.路徑

E.連通性

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

A.樹中沒有環(huán)

B.樹是連通的

C.樹中有n個(gè)頂點(diǎn)，則有n-1條邊

D.樹的唯一根節(jié)點(diǎn)

E.樹的層次結(jié)構(gòu)

5.下列哪些是謂詞邏輯中的量詞？

A.全稱量詞（?）

B.存在量詞（?）

C.選擇量詞

D.謂詞

E.量詞的優(yōu)先級(jí)

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

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

2.在命題邏輯中，命題p為“今天是星期一”，命題q為“明天是星期二”，則p∧q的表達(dá)式為________。

3.在圖論中，一個(gè)無向圖G=(V,E)中，如果對(duì)于任意兩個(gè)頂點(diǎn)u和v，都存在一條從u到v的路徑，則稱該圖是________。

4.在樹論中，一個(gè)樹的度是指該樹中頂點(diǎn)的最大度數(shù)，度數(shù)為0的頂點(diǎn)稱為________。

5.在謂詞邏輯中，?x(P(x))∧?y(Q(y))的表達(dá)式表示________。

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

1.已知集合A={1,2,3,4}，B={3,4,5,6}，C={5,6,7,8}，求(A∩B)∪C。

2.寫出命題公式(p∧q)→?r的否定形式。

3.給定圖G如下，其中頂點(diǎn)集V={a,b,c,d,e}，邊集E={ab,ac,be,bd,ce}，求每個(gè)頂點(diǎn)的度數(shù)，并判斷該圖是否是連通圖。

4.給定一棵樹，其中頂點(diǎn)集V={1,2,3,4,5,6,7}，邊集E={12,13,24,25,26,34,37}，求該樹的高度和每個(gè)頂點(diǎn)的父節(jié)點(diǎn)。

5.給定謂詞邏輯公式?x?y(P(x,y))，解釋該公式的含義，并給出一個(gè)具體的例子來說明該公式為真。

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

一、選擇題答案及解析

1.A

解析：集合的并集是包含兩個(gè)集合中所有元素的集合，即{1,2,3,4,5}。

2.D

解析：命題是能夠判斷真假的陳述句，而x+y=7是一個(gè)含有變量的表達(dá)式，無法判斷真假。

3.C

解析：命題邏輯中的合取（與）用∧表示，p∧q表示p和q同時(shí)為真。

4.A

解析：永真式是在任何賦值下都為真的命題公式，p∨?p是矛盾律的體現(xiàn)，總是為真。

5.A

解析：?x(P(x))表示對(duì)于所有x，命題P(x)都成立。

6.AB

解析：謂詞邏輯中的量詞有全稱量詞?和存在量詞?。

7.C

解析：頂點(diǎn)的度數(shù)是指與該頂點(diǎn)相連的邊的數(shù)量。

8.C

解析：網(wǎng)絡(luò)圖通常指帶有權(quán)重的圖，不是圖的基本性質(zhì)。

9.C

解析：樹的度是指樹中頂點(diǎn)的最大度數(shù)。

10.C

解析：有向圖是圖的一種類型，不是樹的結(jié)構(gòu)。

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

1.ABCDE

解析：集合論中的基本運(yùn)算包括并集、交集、補(bǔ)集、差集和對(duì)稱差集。

2.ABCDE

解析：邏輯聯(lián)結(jié)詞包括與、或、非、蘊(yùn)含和等價(jià)。

3.ABCDE

解析：圖論中的基本概念包括頂點(diǎn)、邊、鄰接矩陣、路徑和連通性。

4.ABCDE

解析：樹的性質(zhì)包括沒有環(huán)、連通、n個(gè)頂點(diǎn)n-1條邊、唯一根節(jié)點(diǎn)和層次結(jié)構(gòu)。

5.AB

解析：謂詞邏輯中的量詞有全稱量詞和存在量詞。

三、填空題答案及解析

1.{3,4}

解析：集合的交集是兩個(gè)集合中共同擁有的元素。

2.今天是星期一且明天是星期二

解析：合取用“且”表示，p∧q表示p和q同時(shí)為真。

3.連通圖

解析：如果對(duì)于任意兩個(gè)頂點(diǎn)都存在一條路徑，則該圖是連通的。

4.葉子節(jié)點(diǎn)

解析：度數(shù)為0的頂點(diǎn)稱為葉子節(jié)點(diǎn)。

5.對(duì)所有x，P(x)成立并且存在一個(gè)y，Q(y)成立

解析：?x(P(x))表示對(duì)所有x，P(x)成立；?y(Q(y))表示存在一個(gè)y，Q(y)成立。

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

1.{3,4,5,6,7,8}

解析：(A∩B)∪C即{3,4}∪{5,6,7,8}，合并后為{3,4,5,6,7,8}。

2.?(p∧q)∨r

解析：根據(jù)命題邏輯的德摩根律，命題公式的否定形式為?(p∧q)∨r。

3.度數(shù)：a-2,b-3,c-2,d-2,e-2；連通圖

解析：計(jì)算每個(gè)頂點(diǎn)的度數(shù)，ab,ac,be,bd,ce分別連接了頂點(diǎn)a,b,c,d,e，度數(shù)分別為2,3,2,2,2。由于所有頂點(diǎn)都通過邊相連，因此是連通圖。

4.高度：3；父節(jié)點(diǎn)：1-無，2-1，3-1，4-1，5-2，6-2，7-3

解析：樹的高度是樹中最高頂點(diǎn)的層次數(shù)，該樹的高度為3。父節(jié)點(diǎn)是指連接到子節(jié)點(diǎn)的頂點(diǎn)，1是根節(jié)點(diǎn)沒有父節(jié)點(diǎn)，2,3,4連接到1，5,6連接到2，7連接到3。

5.對(duì)所有x，存在一個(gè)y，使得P(x,y)成立；例如，P(x,y)表示x是y的老師，則公式表示對(duì)所有學(xué)生x，都存在一個(gè)老師y。

解析：?x?y(P(x,y))表示對(duì)于所有x，存在一個(gè)y，使得P(x,y)成立。例如，P(x,y)可以表示x是y的老師，則公式表示對(duì)于所有學(xué)生x，都存在一個(gè)老師y。

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

集合論：集合的基本運(yùn)算（并集、交集、補(bǔ)集、差集、對(duì)稱差集），集合的性質(zhì)（冪集、子集、真子集）。

命題邏輯：命題、邏輯聯(lián)結(jié)詞（與、或、非、蘊(yùn)含、等價(jià)）、量詞（全稱量詞、存在量詞）、命題公式及其推理規(guī)則。

圖論：圖的基本概念（頂點(diǎn)、邊、鄰接矩陣、路徑、連通性），圖的基本性質(zhì)（無向圖、有向圖、網(wǎng)絡(luò)圖），樹的基本概念（根節(jié)點(diǎn)、葉子節(jié)點(diǎn)、父節(jié)點(diǎn)、子節(jié)點(diǎn)、樹的高度、樹的性質(zhì)）。

謂詞邏輯：謂詞、量詞、謂詞邏輯公式及其解釋。

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

選擇題：考察學(xué)生對(duì)集合論、命題邏輯、圖論、樹論和謂詞邏輯的基本概念和性質(zhì)的理解，通過選擇題的形式考察學(xué)生的記憶和