計(jì)算機(jī)離散數(shù)學(xué)試卷一、選擇題（每題1分，共10分）

1.下列哪個(gè)集合是有限集？

A.自然數(shù)集

B.整數(shù)集

C.有理數(shù)集

D.{1,2,3}

2.設(shè)A和B是集合，以下哪個(gè)式子是正確的？

A.A∪B=B∪A

B.A∩B=B∩A

C.A×B=B×A

D.A?B?B?A

3.下列哪個(gè)命題是永真式？

A.p∨?p

B.p∧?p

C.p→p

D.?p→p

4.設(shè)有命題p:今天下雨，q:我會去圖書館。命題“如果今天不下雨，那么我會去圖書館”可以表示為：

A.p→q

B.?p→q

C.q→p

D.?q→?p

5.下列哪個(gè)是圖G的Eulerian路的充分必要條件？

A.G是連通的

B.G是連通的且所有頂點(diǎn)的度數(shù)都是偶數(shù)

C.G是連通的且至少有兩個(gè)頂點(diǎn)的度數(shù)是奇數(shù)

D.G是連通的且所有頂點(diǎn)的度數(shù)都是奇數(shù)

6.設(shè)有函數(shù)f:A→B，以下哪個(gè)是函數(shù)的必要條件？

A.f是單射

B.f是滿射

C.f是雙射

D.A和B的元素個(gè)數(shù)相同

7.下列哪個(gè)是偏序關(guān)系的性質(zhì)？

A.傳遞性

B.對稱性

C.反對稱性

D.以上都是

8.設(shè)有命題公式p∧q→p，以下哪個(gè)是它的等價(jià)式？

A.p∨q

B.p∧q

C.?p∨?q

D.?p∧?q

9.下列哪個(gè)是組合數(shù)學(xué)中的基本原理？

A.加法原理

B.乘法原理

C.排列

D.以上都是

10.設(shè)有有向圖D，以下哪個(gè)是D的強(qiáng)連通分量的定義？

A.D的最大連通子圖

B.D的最大強(qiáng)連通子圖

C.D的最小連通子圖

D.D的最小強(qiáng)連通子圖

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

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

A.并集

B.交集

C.差集

D.補(bǔ)集

E.冪集

2.下列哪些命題公式是永真式？

A.p∨?p

B.p∧?p

C.(p→q)→(q→p)

D.(p∧q)→p

E.?(p∧?p)

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

A.頂點(diǎn)

B.邊

C.鄰接矩陣

D.通路

E.網(wǎng)絡(luò)流

4.下列哪些是組合數(shù)學(xué)中的計(jì)數(shù)方法？

A.排列

B.組合

C.二項(xiàng)式定理

D.遞推關(guān)系

E.鴿巢原理

5.下列哪些是數(shù)理邏輯中的基本概念？

A.命題

B.謂詞

C.量詞

D.謂詞邏輯公式

E.模型論

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

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

2.命題公式p∧q的否定是________。

3.一個(gè)有n個(gè)頂點(diǎn)的簡單無向圖中，最多有________條邊。

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

5.設(shè)集合A={a,b,c}，則A的所有子集個(gè)數(shù)是________。

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

1.設(shè)有命題公式A=(p→q)∧(?q→?p)。求命題公式A的主析取范式。

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

3.證明命題公式(p∧q)→p是重言式。

4.設(shè)有向圖G如下，其中頂點(diǎn)集V={a,b,c,d}，邊集E={(a,b),(b,c),(c,d),(d,a),(a,c)}。判斷圖G是否是強(qiáng)連通圖，并說明理由。

5.計(jì)算從5個(gè)不同元素中取出3個(gè)元素的排列數(shù)P(5,3)。

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

一、選擇題（每題1分，共10分）

1.D{1,2,3}是一個(gè)包含三個(gè)元素的有限集。A、B、C都是無限集。

2.A、B、CA∪B=B∪A是集合的并運(yùn)算滿足交換律。A∩B=B∩A是集合的交運(yùn)算滿足交換律。(A×B)一般不等于(B×A)因?yàn)樵氐捻樞蚝徒M合方式不同。A?B不一定意味著B?A，例如A={1,2}，B={2}，則A?B但B?A。

3.Ap∨?p是一個(gè)永真式，因?yàn)樗偸菫檎?。?dāng)p為真時(shí)，?p為假，p∨?p為真；當(dāng)p為假時(shí)，?p為真，p∨?p為真。

4.B“如果今天不下雨，那么我會去圖書館”是命題?p→q的形式。原命題是“如果今天不下雨(?p)，那么我會去圖書館(q)”。

5.B圖G有Eulerian路的充分必要條件是G是連通的，并且G中恰好有兩個(gè)頂點(diǎn)的度數(shù)是奇數(shù)。A是必要非充分條件。C和D描述的是Eulerian回路的條件。

6.B函數(shù)f:A→B是一個(gè)函數(shù)，如果對于A中的每一個(gè)元素，在B中都有唯一的元素與之對應(yīng)。這是函數(shù)的基本定義。A單射、C雙射、D都是更強(qiáng)的條件，不是所有函數(shù)都必須滿足。

7.A、C偏序關(guān)系是指集合中的元素之間可以定義一種“小于等于”或“大于等于”的關(guān)系，它滿足自反性、反對稱性和傳遞性。對稱性不是偏序關(guān)系的性質(zhì)。

8.B?p∨?q是p∧q→p的等價(jià)式。根據(jù)蘊(yùn)涵式的等價(jià)式，p→q≡?p∨q。所以p∧q→p≡?(p∧q)∨p≡(?p∨?q)∨p≡?p∨p∨?q≡T∨?q≡T。但更標(biāo)準(zhǔn)的轉(zhuǎn)換是p∧q→p≡?(p∧q)∨p≡(?p∨?q)∨p≡?p∨p∨?q≡T∨?q≡T。或者用分配律(?p∨p)∧(?q∨p)≡T∧(?q∨p)≡?q∨p。但最直接的等價(jià)形式是?p∨?q。

9.A、B、C加法原理、乘法原理和排列都是組合數(shù)學(xué)中的基本原理和方法。組合數(shù)學(xué)研究計(jì)數(shù)、排列組合等問題。

10.B有向圖D的強(qiáng)連通分量是指D的最大強(qiáng)連通子圖。一個(gè)強(qiáng)連通子圖是其中任意兩個(gè)頂點(diǎn)之間都有雙向的路徑。最大強(qiáng)連通子圖是指在該定義下包含最多頂點(diǎn)的子圖。

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

1.A、B、C、D集合論中的基本運(yùn)算包括并集、交集、差集和補(bǔ)集。E冪集是集合的子集構(gòu)成的集合，也是一個(gè)重要概念，但不是基本運(yùn)算。

2.A、D、Ep∨?p是永真式（排中律）。?(p∧?p)是永真式（矛盾律）。(p∧q)→p是永真式（合取對蘊(yùn)含式的分離規(guī)則）。B是永假式。C不是永真式，例如p=True,q=False時(shí)，(True→False)→(False→True)=(False→True)=True，但當(dāng)p=False,q=True時(shí)，(False→True)→(True→False)=(True→False)=True，但當(dāng)p=False,q=False時(shí)，(False→False)→(False→True)=(True→True)=True。這個(gè)選項(xiàng)需要更仔細(xì)的驗(yàn)證，或者可能題目有誤。根據(jù)標(biāo)準(zhǔn)永真式定義，A、D、E是正確的。

3.A、B、C、D頂點(diǎn)、邊、鄰接矩陣和通路是圖論中的基本概念。E網(wǎng)絡(luò)流是圖論的一個(gè)應(yīng)用分支，雖然重要，但通常不被視為最基礎(chǔ)的概念。

4.A、B、C、D、E排列、組合、二項(xiàng)式定理、遞推關(guān)系和鴿巢原理都是組合數(shù)學(xué)中的重要計(jì)數(shù)方法和概念。

5.A、B、C、D、E命題、謂詞、量詞、謂詞邏輯公式和模型論都是數(shù)理邏輯的基本組成部分和研究內(nèi)容。

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

1.{1,2,3,4,5}集合的并集包含兩個(gè)集合中的所有元素，不重復(fù)。

2.?(p∧q)根據(jù)德摩根律，命題公式p∧q的否定是?p∨?q。

3.n(n-1)/2在簡單無向圖中，任意兩個(gè)不同的頂點(diǎn)之間至多有一條邊。對于n個(gè)頂點(diǎn)，第一個(gè)頂點(diǎn)可以與其他n-1個(gè)頂點(diǎn)連線，第二個(gè)頂點(diǎn)可以與剩下的n-2個(gè)頂點(diǎn)連線，依此類推?？傔厰?shù)為1+2+...+(n-1)=n(n-1)/2。

4.C(n,k)或∑_{i=0}^{k}(-1)^{i}C(n,i)組合數(shù)表示從n個(gè)不同元素中取出k個(gè)元素的組合方式的總數(shù)，記作C(n,k)或?qū)懽?binom{n}{k}。計(jì)算公式為C(n,k)=n!/(k!*(n-k)!).

5.2^3=8集合A有3個(gè)元素，其子集個(gè)數(shù)為2的3次方，即2^3=8個(gè)。這些子集包括空集、單元素子集、雙元素子集和全集。

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

1.主析取范式為p∧?q∧?r∧s。分析略。

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

3.證明略。p∧q→p是重言式。

4.圖G不是強(qiáng)連通圖。因?yàn)轫旤c(diǎn)a不能通過有向邊到達(dá)頂點(diǎn)c(沒有a→c的邊)，所以a和c不在同一個(gè)強(qiáng)連通分量中。存在至少兩個(gè)頂點(diǎn)不在同一個(gè)強(qiáng)連通分量中，所以圖不是強(qiáng)連通的。

5.P(5,3)=5!/(5-3)!=5!/2!=(5×4×3×2×1)/(2×1)=5×4×3=60。

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

本試卷主要涵蓋離散數(shù)學(xué)的基礎(chǔ)理論部分，包括集合論、命題邏輯、謂詞邏輯、圖論、組合數(shù)學(xué)和數(shù)理邏輯初步等知識點(diǎn)。

一、選擇題知識點(diǎn)詳解及示例：

集合論：理解集合的基本運(yùn)算（并、交、差、補(bǔ)）、集合的性質(zhì)（冪集、子集）、集合的計(jì)數(shù)（子集個(gè)數(shù)）。示例：計(jì)算{1,2}∪{2,3}={1,2,3}。

命題邏輯：掌握命題的概念、邏輯聯(lián)結(jié)詞（與、或、非、蘊(yùn)含、等價(jià)）、命題公式及其真值表、永真式和永假式、等價(jià)式轉(zhuǎn)換。示例：證明p∧(q∨r)≡(p∧q)∨(p∧r)。

謂詞邏輯：理解謂詞、量詞（全稱量詞?、存在量詞?）的概念和表示。示例：將“所有的人都是會死的”表示為?x(Person(x)→Mortal(x))。

圖論：掌握圖的基本概念（頂點(diǎn)、邊、有向圖、無向圖、帶權(quán)圖）、圖的基本性質(zhì)（連通性、路徑、回路）、Eulerian路和回路的條件、圖的表示方法（鄰接矩陣）。示例：判斷一個(gè)圖是否有Eulerian回路。

組合數(shù)學(xué)：掌握基本的計(jì)數(shù)原理（加法原理、乘法原理）、排列（有序選?。?、組合（無序選?。⒍?xiàng)式定理、遞推關(guān)系、鴿巢原理。示例：計(jì)算從5人中選出3人組成一個(gè)委員會的選法數(shù)。

數(shù)理邏輯初步：了解邏輯推理的基本規(guī)則、模型論的基本概念。示例：使用邏輯推理證明一個(gè)命題公式是重言式。

二、多項(xiàng)選擇題知識點(diǎn)詳解及示例：

本題型考察學(xué)生對多個(gè)知識點(diǎn)的綜合理解和應(yīng)用能力，需要學(xué)生能夠識別正確的選項(xiàng)，并排除錯(cuò)誤選項(xiàng)。通常涉及的概念較多，需要扎實(shí)的基礎(chǔ)知識。示例：選擇所有屬于圖論基本概念的項(xiàng)目。

三、填空題知識點(diǎn)詳解及示例：

本題型考察學(xué)生對基本概念、公式和定理的準(zhǔn)確記憶和理解。要求學(xué)生能夠準(zhǔn)確填寫答案，通常答案簡潔明了。示例：填寫集合A={1,2,3}和B={3,4,5}的并集。

四、計(jì)算題知識點(diǎn)詳解及示例：

本題型考察學(xué)生運(yùn)用所學(xué)理論知識解決具體問題的能力，需要學(xué)生能夠進(jìn)行邏輯推理、代數(shù)計(jì)算和證明。通常涉及具體的計(jì)算過程或證明步驟。示例：計(jì)算