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

1.在集合論中，集合A包含于集合B的符號表示是？

A.A?B

B.A?B

C.A∩B

D.A∪B

2.下列哪個不是命題邏輯的基本聯(lián)結詞？

A.非

B.與

C.或

D.等價

3.在謂詞邏輯中，量詞?表示？

A.存在

B.對于所有

C.且

D.或

4.有向圖G中，如果從頂點u到頂點v存在一條有向邊，則稱？

A.u是v的先驅

B.v是u的先驅

C.u和v是相鄰的

D.u和v是不相鄰的

5.無向圖G中，如果頂點u和頂點v之間存在一條邊，則稱？

A.u是v的鄰接點

B.v是u的鄰接點

C.u和v是相鄰的

D.u和v是不相鄰的

6.在圖論中，樹的定義是？

A.無環(huán)連通圖

B.有環(huán)連通圖

C.無環(huán)非連通圖

D.有環(huán)非連通圖

7.在組合數(shù)學中，從n個不同元素中取出k個元素的組合數(shù)表示為？

A.P(n,k)

B.C(n,k)

C.A(n,k)

D.G(n,k)

8.在數(shù)理邏輯中，命題p∧q表示？

A.p或q

B.p且q

C.非p

D.非q

9.在布爾代數(shù)中，邏輯運算符?表示？

A.與

B.或

C.非

D.異或

10.在圖論中，完全圖K_n的定義是？

A.每個頂點都與其他所有頂點相鄰的圖

B.沒有邊的圖

C.每個頂點都與其他所有頂點不相鄰的圖

D.只有兩條邊的圖

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

1.下列哪些是命題邏輯的真值表中的基本命題形式？

A.p∧q

B.?p

C.p∨q

D.p→q

E.p?q

2.在集合論中，下列哪些運算滿足交換律？

A.并集運算（∪）

B.交集運算（∩）

C.差集運算（?）

D.補集運算（′）

E.冪集運算（P(A)）

3.在圖論中，下列哪些是樹的基本性質？

A.無環(huán)

B.連通

C.有n個頂點的樹有n-1條邊

D.存在唯一的路徑連接任意兩個頂點

E.可以有多個根節(jié)點

4.在組合數(shù)學中，下列哪些是常見的組合計數(shù)公式？

A.組合數(shù)C(n,k)=n!/(k!(n-k)!)

B.階乘n!

C.排列數(shù)P(n,k)=n!/(n-k)!

D.二項式定理(a+b)^n=∑_{k=0}^{n}C(n,k)a^kb^{n-k}

E.階乘之和n!=∑_{k=0}^{n}k!

5.在布爾代數(shù)中，下列哪些運算是雙射運算？

A.與運算（∧）

B.或運算（∨）

C.非運算（?）

D.異或運算（⊕）

E.同或運算（⊙）

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

1.在謂詞邏輯中，表示“對于所有x，P(x)”的量詞符號是________。

2.如果集合A中有n個元素，則A的冪集P(A)中有________個元素。

3.在圖論中，一個有n個頂點的無向完全圖中，有________條邊。

4.在組合數(shù)學中，從n個不同元素中取出k個元素的排列數(shù)記作P(n,k)，其計算公式為________。

5.布爾代數(shù)中的基本運算包括與運算(______)、或運算(______)和非運算(______)。

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

1.給定命題公式(p∧q)→?r和r→(?p∨?q)，求該命題公式的真值表，并判斷該公式是否為重言式。

2.設集合A={1,2,3},B={2,3,4},C={3,4,5}，求(A∩B)∪C以及A∩(B∪C)，并驗證分配律(A∩B)∪C=A∩(B∪C)是否成立。

3.考慮一個有向圖G，其頂點集V={v1,v2,v3,v4}，邊集E={(v1,v2),(v2,v3),(v3,v4),(v4,v1)}。求該圖的所有強連通分量。

4.計算組合數(shù)C(10,3)和排列數(shù)P(10,3)，并解釋二者的區(qū)別。然后，利用組合數(shù)的性質計算C(10,7)。

5.在布爾代數(shù)中，給定表達式F=A'B+AB'+AB，化簡該表達式，并畫出對應的邏輯門電路圖。

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

一、選擇題答案

1.A

2.D

3.B

4.A

5.C

6.A

7.B

8.B

9.C

10.A

二、多項選擇題答案

1.ABCDE

2.AB

3.ABCD

4.ABCD

5.C

三、填空題答案

1.?

2.2^n

3.n(n-1)/2

4.n!/(n-k)!

5.AND,OR,NOT

四、計算題答案

1.真值表：

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

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

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

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

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

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

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

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

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

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

真值表顯示該公式在所有情況下的真值均為T，故為重言式。

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

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

分配律不成立。

3.該圖的所有強連通分量是{v1,v2,v3,v4}，因為所有頂點都是相互可達的。

4.C(10,3)=10!/(3!*(10-3)!)=120

P(10,3)=10!/(10-3)!=720

組合數(shù)表示從10個元素中取3個不考慮順序，排列數(shù)表示考慮順序。

C(10,7)=C(10,3)=120

5.F=A'B+AB'+AB=(A'+A)(B'+B)=1*1=1

邏輯門電路圖為一個恒等門（輸出始終為1）。

知識點總結

集合論：集合的基本運算（并、交、差、補）、冪集、集合恒等式。

命題邏輯：命題、聯(lián)結詞、量詞、真值表、重言式。

圖論：有向圖、無向圖、圖的性質（連通性、環(huán)、路徑）、樹、完全圖、強連通分量。

組合數(shù)學：組合數(shù)、排列數(shù)、二項式定理、組合恒等式。

布爾代數(shù)：基本運算（與、或、非）、邏輯門、表達式化簡。

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

選擇題：考察學生對基本概念的掌握，如集合運算、命題聯(lián)結詞、圖論基本定義、組合數(shù)學公式、布爾代數(shù)運算等。示例：選擇正確的集合運算符、命題聯(lián)結詞的含義、樹的定義等。

多項選擇題：考察學生對多個相關概念的理解和區(qū)分，如集合運算的交換律、樹的性質、組合數(shù)學公式、布爾代數(shù)運算的雙射性等。示例：選擇滿足交換律的集合運算、樹的性質、組合數(shù)學公式、布爾代數(shù)運算的雙射性等。

填空題：考察學生對重要概念和公式的記憶，