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

1.在集合論中，集合A包含n個元素，則A的子集總數(shù)為多少？

A.n

B.2^n

C.n!

D.n^2

2.下列哪個不是命題？

A.今天天氣很好。

B.2+2=4

C.請開門。

D.他很高。

3.在命題邏輯中，符號“∧”代表什么？

A.或

B.非

C.與

D.蘊含

4.下列哪個是永真式？

A.p∧?p

B.p∨?p

C.p→?p

D.?p∨?p

5.在謂詞邏輯中，符號“?”代表什么？

A.存在量詞

B.全稱量詞

C.選擇量詞

D.非量詞

6.設(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}

7.在圖論中，一個圖G=(V,E)中，V代表什么？

A.邊

B.頂點

C.權(quán)重

D.鄰接矩陣

8.一個有n個頂點的簡單無向圖，其最大邊數(shù)是多少？

A.n

B.n(n-1)/2

C.n^2

D.2n

9.在樹論中，一個樹的頂點度數(shù)最大為多少？

A.1

B.2

C.3

D.n-1

10.下列哪個不是圖論中的基本概念？

A.頂點

B.邊

C.回路

D.函數(shù)

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

1.下列哪些是命題邏輯的基本連接詞？

A.與

B.或

C.非

D.蘊含

E.等價

2.在集合論中，下列哪些運算是補運算的逆運算？

A.并集

B.交集

C.補集

D.差集

E.對稱差集

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

A.頂點

B.邊

C.回路

D.樹

E.函數(shù)

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

A.存在量詞

B.全稱量詞

C.選擇量詞

D.非量詞

E.無量詞

5.下列哪些是樹論中的基本概念？

A.根

B.子樹

C.邊

D.回路

E.葉子頂點

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

1.在命題邏輯中，符號“?”代表________。

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

3.在圖論中，一個有n個頂點的簡單無向圖，其最大邊數(shù)是________。

4.在樹論中，一個樹是________連通的。

5.在謂詞邏輯中，符號“?”代表________。

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

1.對于命題公式(p→q)∧(?p∨r)，請寫出其真值表。

2.設(shè)集合A={1,2,3}，B={x|x∈N且1≤x≤4}，C={x|x∈Z且-2≤x≤2}，請計算(A∩B)∪C的所有元素。

3.給定圖G=(V,E)，其中V={v1,v2,v3,v4}，E={<v1,v2>,<v2,v3>,<v3,v4>,<v4,v1>}，請判斷圖G是否是歐拉圖，并說明理由。

4.設(shè)一棵樹T有10個頂點，請計算樹T的邊數(shù)，并畫出一種可能的樹形結(jié)構(gòu)。

5.對于謂詞邏輯公式?x(P(x)→Q(x))，其中P(x)表示“x是偶數(shù)”，Q(x)表示“x可以被2整除”，請解釋該公式的含義，并舉例說明其真假。

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

一、選擇題答案

1.B

2.D

3.C

4.B

5.B

6.C

7.B

8.B

9.D

10.D

二、多項選擇題答案

1.A,B,C,D,E

2.A,B,C,D,E

3.A,B,C,D

4.A,B

5.A,B,C,E

三、填空題答案

1.非

2.{2,3}

3.n(n-1)/2

4.連通

5.存在量詞

四、計算題答案

1.真值表：

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

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

|T|T|T|T|F|T|T|

|T|T|F|T|F|F|F|

|T|F|T|T|F|T|T|

|T|F|F|T|F|F|F|

|F|T|T|T|T|T|T|

|F|T|F|T|T|T|T|

|F|F|T|T|T|T|T|

|F|F|F|T|T|T|T|

2.(A∩B)∪C={1,2,3}

3.圖G不是歐拉圖，因為圖G中存在奇數(shù)度頂點（v1,v3,v4的度數(shù)為2，v2的度數(shù)為3），根據(jù)歐拉圖的定義，一個圖是歐拉圖當且僅當它是連通的且所有頂點的度數(shù)都是偶數(shù)。

4.樹T的邊數(shù)為9。一種可能的樹形結(jié)構(gòu)如下：

```

v1

/\

v2v3

\/

v4

```

5.?x(P(x)→Q(x))的含義是“對于所有的x，如果x是偶數(shù)，那么x可以被2整除”。例如，x=2是偶數(shù)，且2可以被2整除，所以該公式為真。

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

集合論：集合的運算（并集、交集、補集、差集、對稱差集）、集合的性質(zhì)、子集、冪集、卡inality的計算。

命題邏輯：命題、連接詞（與、或、非、蘊含、等價）、量詞、真值表、永真式、永假式。

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

圖論：頂點、邊、圖、有向圖、無向圖、歐拉圖、哈密頓圖、樹、森林、頂點度數(shù)、路徑、回路。

樹論：根、子樹、葉子頂點、樹的性質(zhì)、樹的遍歷、樹的計數(shù)。

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

選擇題：考察學(xué)生對基本概念和定義的掌握程度，例如命題邏輯中的連接詞、集合論中的集合運算、圖論中的基本概念等。示例：題目“在命題邏輯中，符號‘∧’代表什么？”考察學(xué)生對命題邏輯連接詞的掌握。

多項選擇題：考察學(xué)生對多個相關(guān)概念的理解和區(qū)分能力，例如命題邏輯中的連接詞、集合論中的集合運算、圖論中的基本概念等。示例：題目“下列哪些是圖論中的基本概念？”考察學(xué)生對圖論基本概念的掌握。

填空題：考察學(xué)生對基本概念的準確記憶和表達能力，例如命題邏輯中的連接詞、集合論中的集合運算、圖論中的基本概念等。示例：題目“在命題邏輯中，符號‘?’代表