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

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

A.A?B

B.A?B

C.A∩B

D.A∪B

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

A.非

B.與

C.或

D.等價(jià)

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

A.存在

B.對于所有

C.且

D.或

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

A.u是v的先驅(qū)

B.v是u的先驅(qū)

C.u和v是相鄰的

D.u和v是不相鄰的

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

A.u是v的鄰接點(diǎn)

B.v是u的鄰接點(diǎn)

C.u和v是相鄰的

D.u和v是不相鄰的

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

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

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

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

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

7.在組合數(shù)學(xué)中，從n個(gè)不同元素中取出k個(gè)元素的組合數(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ù)中，邏輯運(yùn)算符?表示？

A.與

B.或

C.非

D.異或

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

A.每個(gè)頂點(diǎn)都與其他所有頂點(diǎn)相鄰的圖

B.沒有邊的圖

C.每個(gè)頂點(diǎn)都與其他所有頂點(diǎn)不相鄰的圖

D.只有兩條邊的圖

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

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

A.p∧q

B.?p

C.p∨q

D.p→q

E.p?q

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

A.并集運(yùn)算（∪）

B.交集運(yùn)算（∩）

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

D.補(bǔ)集運(yùn)算（′）

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

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

A.無環(huán)

B.連通

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

D.存在唯一的路徑連接任意兩個(gè)頂點(diǎn)

E.可以有多個(gè)根節(jié)點(diǎn)

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

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

B.階乘n!

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

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

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

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

A.與運(yùn)算（∧）

B.或運(yùn)算（∨）

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

D.異或運(yùn)算（⊕）

E.同或運(yùn)算（⊙）

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

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

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

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

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

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

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

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

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

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

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

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

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

一、選擇題答案

1.A

2.D

3.B

4.A

5.C

6.A

7.B

8.B

9.C

10.A

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

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

四、計(jì)算題答案

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.該圖的所有強(qiáng)連通分量是{v1,v2,v3,v4}，因?yàn)樗许旤c(diǎn)都是相互可達(dá)的。

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

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

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

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

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

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

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

集合論：集合的基本運(yùn)算（并、交、差、補(bǔ)）、冪集、集合恒等式。

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

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

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

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

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

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

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

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