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

1.下列哪個(gè)命題在數(shù)理邏輯中是永真的？

A.P∨?P

B.P∧?P

C.P→P

D.P??P

2.在集合論中，集合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}

3.下列哪個(gè)是正確的命題公式？

A.(P∧Q)→P

B.(P→Q)∧(Q→P)

C.(P∨Q)?(?P∧?Q)

D.(P∧?P)∨Q

4.在圖論中，一個(gè)無向圖中每個(gè)頂點(diǎn)的度數(shù)之和等于？

A.圖的邊數(shù)

B.2倍圖的邊數(shù)

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

D.2倍圖的頂點(diǎn)數(shù)

5.下列哪個(gè)是正確的等價(jià)式？

A.P?(Q→P)

B.(P∧Q)?(Q∧P)

C.(P∨Q)?(?P∧?Q)

D.(P→Q)?(?Q→?P)

6.在命題邏輯中，下列哪個(gè)是重言式？

A.P∨?P

B.P∧?P

C.(P∧Q)→P

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

7.在集合論中，集合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}

8.在圖論中，一個(gè)有向圖中所有頂點(diǎn)的入度之和等于？

A.圖的邊數(shù)

B.2倍圖的邊數(shù)

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

D.2倍圖的頂點(diǎn)數(shù)

9.下列哪個(gè)是正確的蘊(yùn)涵式？

A.P→(Q→P)

B.(P→Q)→(Q→P)

C.(P∧Q)→(Q∧P)

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

10.在命題邏輯中，下列哪個(gè)是矛盾式？

A.P∨?P

B.P∧?P

C.(P∧Q)→P

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

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

1.下列哪些是命題邏輯中的基本聯(lián)結(jié)詞？

A.非

B.合取

C.析取

D.蘊(yùn)含

E.等價(jià)

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

A.并集

B.交集

C.差集

D.補(bǔ)集

E.冪集運(yùn)算

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

A.頂點(diǎn)

B.邊

C.度數(shù)

D.路徑

E.函數(shù)

4.下列哪些是命題邏輯中的重言式？

A.P∨?P

B.P∧?P

C.(P∧Q)→P

D.(P→Q)?(?Q→?P)

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

5.在集合論中，下列哪些是集合的基本性質(zhì)？

A.冪集合

B.并集

C.交集

D.差集

E.補(bǔ)集

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

1.在命題邏輯中，聯(lián)結(jié)詞“與非”的符號(hào)表示是______。

2.集合A={1,2,3}與集合B={3,4,5}的差集A-B=______。

3.在圖論中，一個(gè)有n個(gè)頂點(diǎn)的無向完全圖中，邊的數(shù)量是______。

4.命題公式(P→Q)?(?Q→?P)的邏輯等價(jià)式是______。

5.集合A={1,2,3}的冪集P(A)中的元素個(gè)數(shù)是______。

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

1.對(duì)于命題公式P→(Q∧?R)，請(qǐng)寫出它的真值表。

2.設(shè)集合A={x|x∈N,1≤x≤5},B={x|x∈N,3≤x≤7},請(qǐng)計(jì)算A∩B和A∪B。

3.給定圖G=<V,E>，其中V={a,b,c,d}，E={(a,b),(a,c),(b,d),(c,d)}，請(qǐng)計(jì)算每個(gè)頂點(diǎn)的度數(shù)，并判斷該圖是否是連通圖。

4.對(duì)于命題公式(P?Q)→(R→P)，請(qǐng)證明它是重言式。

5.設(shè)集合A={1,2,3}，B={2,3,4}，C={3,4,5}，請(qǐng)計(jì)算(A×B)∩(B×C)。

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

一、選擇題答案

1.A

2.A

3.A

4.B

5.B

6.A

7.B

8.A

9.A

10.B

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

1.A,B,C,D,E

2.A,B,C,D

3.A,B,C,D

4.A,C,D

5.A,B,C,D,E

三、填空題答案

1.?(P∧Q)

2.{1,2}

3.n(n-1)/2

4.P?Q

5.8

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

1.真值表：

|P|Q|R|?R|Q∧?R|P→(Q∧?R)|

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

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

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

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

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

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

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

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

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

2.計(jì)算：

A∩B={x|x∈N,1≤x≤5}∩{x|x∈N,3≤x≤7}={3,4,5}

A∪B={x|x∈N,1≤x≤5}∪{x|x∈N,3≤x≤7}={1,2,3,4,5}

3.計(jì)算頂點(diǎn)度數(shù)：

度(a)=2,度(b)=2,度(c)=2,度(d)=2

該圖是連通圖，因?yàn)槿我鈨蓚€(gè)頂點(diǎn)之間都有路徑相連。

4.證明重言式：

(P?Q)→(R→P)等價(jià)于?(P?Q)∨(?R∨P)

等價(jià)于?((P→Q)∧(Q→P))∨?R∨P

等價(jià)于?((?P∨Q)∧(?Q∨P))∨?R∨P

等價(jià)于?(?P∨Q)∨?(?Q∨P)∨?R∨P

等價(jià)于(P∧?Q)∨(Q∧?P)∨?R∨P

等價(jià)于(P∧?Q∨?R∨P)∨(Q∧?P∨?R∨P)

等價(jià)于P∨(?Q∨?R)∨(Q∧?P∨?R∨P)

等價(jià)于P∨?Q∨?R∨Q∧?P∨?R∨P

等價(jià)于T（因?yàn)镻∨?P=T，?Q∨Q=T）

所以(P?Q)→(R→P)是重言式。

5.計(jì)算：

A×B={(1,2),(1,3),(1,4),(2,2),(2,3),(2,4),(3,2),(3,3),(3,4)}

B×C={(2,3),(2,4),(2,5),(3,3),(3,4),(3,5),(4,3),(4,4),(4,5)}

(A×B)∩(B×C)={(2,3),(2,4),(3,3),(3,4)}

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

集合論：

-集合的基本運(yùn)算：并集、交集、差集、補(bǔ)集

-集合的性質(zhì)：冪集、交換律、結(jié)合律、分配律

-集合的表示：列舉法、描述法

命題邏輯：

-基本聯(lián)結(jié)詞：非、合取、析取、蘊(yùn)含、等價(jià)

-命題公式：真值表、重言式、矛盾式、等價(jià)式

-蘊(yùn)含式：邏輯推理、推理規(guī)則

圖論：

-圖的基本概念：頂點(diǎn)、邊、度數(shù)、路徑

-圖的性質(zhì)：連通圖、完全圖

-圖的表示：集合表示、矩陣表示

計(jì)算題考察學(xué)生的知識(shí)點(diǎn)詳解及示例

1.真值表：通過列出所有可能的真值組合，驗(yàn)證命題公式的真假情況。

示例：P→(Q∧?R)的真值表，需要考慮P、Q、R的所有八種組合。

2.集合運(yùn)算：計(jì)算集合的并集、交集、差集等，需要掌握集合的基本運(yùn)算規(guī)則。

示例：A∩B和A∪B的計(jì)算，需要找出兩個(gè)集合的共同元素和所有元素。

3.圖的度數(shù)和連通性：計(jì)算每個(gè)頂點(diǎn)的度數(shù)，判斷圖是否連通，需要理解圖的基本概念和性質(zhì)。

示例：度(a)=2