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

1.下列哪個(gè)命題公式是重言式？

A.(p∧q)→p

B.p∧(q→p)

C.(p∨q)→(p∧q)

D.p→(p∨q)

2.在集合論中，集合A的冪集P(A)的基數(shù)是多少，如果A有n個(gè)元素？

A.n

B.2^n

C.n^2

D.n!

3.下列哪個(gè)圖是歐拉圖？

A.完全圖K_3

B.星型圖（一個(gè)中心頂點(diǎn)連接多個(gè)葉子頂點(diǎn)）

C.斜線圖（一個(gè)頂點(diǎn)連接自身）

D.二分圖

4.在命題邏輯中，下列哪個(gè)聯(lián)結(jié)詞是可交換的？

A.→（蘊(yùn)涵）

B.?（雙條件）

C.∧（合?。?/p>

D.?（非）

5.下列哪個(gè)是正確的全稱量詞公式？

A.?x?yP(x,y)

B.?x?yP(x,y)

C.?x?yP(x,y)

D.?y?xP(x,y)

6.在圖論中，一個(gè)連通無向圖的最小生成樹有多少條邊？

A.n

B.n-1

C.n+1

D.2n

7.下列哪個(gè)是正確的謂詞邏輯公式？

A.?xP(x)∧?yQ(y)

B.?xP(x)∨?yQ(y)

C.?x(P(x)→Q(x))

D.?x(P(x)∧Q(x))

8.在組合數(shù)學(xué)中，8個(gè)元素的全排列有多少種？

A.8!

B.2^8

C.8^2

D.16!

9.下列哪個(gè)是正確的偏序關(guān)系？

A.<（小于）

B.≥（大于等于）

C.≠（不等于）

D.=（等于）

10.在布爾代數(shù)中，下列哪個(gè)是正確的分配律？

A.a∧(b∨c)=(a∧b)∨(a∧c)

B.a∨(b∧c)=(a∨b)∧(a∨c)

C.a∧(b∧c)=(a∧b)∧(a∧c)

D.a∨(b∨c)=(a∨b)∨(a∨c)

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

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

A.∧（合?。?/p>

B.∨（析?。?/p>

C.→（蘊(yùn)涵）

D.?（雙條件）

E.?（全稱量詞）

2.在集合論中，下列哪些是正確的集合運(yùn)算？

A.并集（∪）

B.交集（∩）

C.差集（-）

D.補(bǔ)集（'）

E.冪集（P(A)）

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

A.頂點(diǎn)（Vertex）

B.邊（Edge）

C.鄰接矩陣

D.通路

E.頂點(diǎn)度數(shù)

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

A.?（全稱量詞）

B.?（存在量詞）

C.→（蘊(yùn)涵）

D.∧（合?。?/p>

E.≠（不等于）

5.在組合數(shù)學(xué)中，下列哪些是組合計(jì)數(shù)的基本原理？

A.加法原理

B.乘法原理

C.排列

D.組合

E.鴿巢原理

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

1.謂詞邏輯中的量詞“?x”表示_________________________。

2.在圖論中，一個(gè)無向圖中所有頂點(diǎn)的度數(shù)之和等于邊數(shù)的_________________________倍。

3.集合A={1,2,3}的冪集P(A)的基數(shù)為_________________________。

4.命題邏輯中的重言式是指在任何解釋下都為_________________________的命題公式。

5.組合數(shù)學(xué)中的排列是指從n個(gè)不同元素中取出k個(gè)元素的_________________________的全體。

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

1.設(shè)命題公式P為(p→q)∧(?q→?p)，求P的真值表。

2.給定集合A={1,2,3}，B={2,3,4}，C={3,4,5}，計(jì)算(A∪B)∩C的元素。

3.設(shè)有向圖G的鄰接矩陣為：

```

0101

0010

1001

0100

```

求圖G中頂點(diǎn)1到頂點(diǎn)4的所有可能通路（至少包含2個(gè)邊）。

4.寫出謂詞邏輯公式?x?y(P(x,y)→Q(y))的否定形式。

5.從5個(gè)男生和4個(gè)女生中選出3個(gè)男生和2個(gè)女生組成一個(gè)委員會(huì)，問有多少種不同的選法？

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

一、選擇題答案及解析

1.A

解析：A.(p∧q)→p是重言式，因?yàn)楫?dāng)p為真時(shí)，p∧q為真，則蘊(yùn)涵式為真；當(dāng)p為假時(shí)，p∧q為假，根據(jù)蘊(yùn)涵式的定義，假命題蘊(yùn)涵任何命題也為真。

2.B

解析：集合A的冪集P(A)包含A的所有子集，基數(shù)為2^n，因?yàn)槊總€(gè)元素都有被包含或不被包含兩種可能，n個(gè)元素就有2^n種組合。

3.B

解析：B.星型圖是歐拉圖，因?yàn)樗嬖谝粭l經(jīng)過所有邊的簡(jiǎn)單回路。A.完全圖K_3不是歐拉圖，因?yàn)闆]有奇數(shù)度頂點(diǎn)。C.斜線圖有一個(gè)自環(huán)，不是歐拉圖。D.二分圖不一定是歐拉圖，取決于度數(shù)分布。

4.C

解析：C.∧（合?。┦强山粨Q的，即p∧q與q∧p意義相同。其他聯(lián)結(jié)詞不滿足交換律。

5.C

解析：C.?x?yP(x,y)表示對(duì)于所有x，所有y，P(x,y)都成立，這是正確的全稱量詞公式。其他選項(xiàng)中量詞和謂詞的順序或搭配不當(dāng)。

6.B

解析：一個(gè)連通無向圖的最小生成樹有n-1條邊，其中n是頂點(diǎn)數(shù)。這是最小生成樹的基本性質(zhì)。

7.A

解析：A.?xP(x)∧?yQ(y)是正確的謂詞邏輯公式，表示所有x滿足P(x)，并且存在至少一個(gè)y滿足Q(y)。其他選項(xiàng)中量詞和謂詞的順序或邏輯聯(lián)結(jié)詞使用不當(dāng)。

8.A

解析：8個(gè)元素的全排列有8!=40320種，即8個(gè)元素可以按不同順序排列的總數(shù)。

9.B

解析：B.≥（大于等于）是偏序關(guān)系，滿足自反性、反對(duì)稱性和傳遞性。其他選項(xiàng)不滿足偏序關(guān)系的定義。

10.A

解析：A.a∧(b∨c)=(a∧b)∨(a∧c)是布爾代數(shù)中的分配律。其他選項(xiàng)不是分配律。

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

1.A,B,C,D

解析：命題邏輯的聯(lián)結(jié)詞包括合?。ā模?、析?。ā牛?、蘊(yùn)涵（→）和雙條件（?）。E.?是全稱量詞，不屬于聯(lián)結(jié)詞。

2.A,B,C,D,E

解析：集合論中的集合運(yùn)算包括并集（∪）、交集（∩）、差集（-）、補(bǔ)集（'）和冪集（P(A)）。

3.A,B,C,D,E

解析：圖論的基本概念包括頂點(diǎn)（Vertex）、邊（Edge）、鄰接矩陣、通路和頂點(diǎn)度數(shù)。

4.A,B

解析：謂詞邏輯中的量詞包括全稱量詞（?）和存在量詞（?）。C,D,E不是量詞。

5.A,B,C,D,E

解析：組合計(jì)數(shù)的基本原理包括加法原理、乘法原理、排列、組合和鴿巢原理。

三、填空題答案及解析

1.對(duì)于所有x，P(x)都成立。

解析：謂詞邏輯中的量詞“?x”表示對(duì)于所有x，后面的謂詞P(x)都成立。

2.2

解析：根據(jù)握手定理，無向圖中所有頂點(diǎn)的度數(shù)之和等于邊數(shù)的2倍。

3.8

解析：集合A={1,2,3}有3個(gè)元素，其冪集P(A)的基數(shù)為2^3=8。

4.真

解析：命題邏輯中的重言式是指在任何解釋下都為真的命題公式。

5.有序

解析：組合數(shù)學(xué)中的排列是指從n個(gè)不同元素中取出k個(gè)元素的有序的全體。

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

1.真值表：

```

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

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

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

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

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

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

```

解析：通過計(jì)算真值表，可以看到命題公式P在不同情況下的真值。

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

解析：首先計(jì)算A和B的并集，然后與C取交集，得到最終結(jié)果。

3.頂點(diǎn)1到頂點(diǎn)4的通路有：

1-3-4,1-4-3,1-2-3-4,1-3-2-4

解析：通過遍歷鄰接矩陣，找出所有從頂點(diǎn)1到頂點(diǎn)4的通路，至少包含2條邊。

4.否定形式：?x?y?(P(x,y)→Q(y))≡?x?y(P(x,y)∧?Q(y))

解析：根據(jù)謂詞邏輯的否定規(guī)則，逐層否定量詞和謂詞，得到否定形式。

5.選法數(shù)為C(5,3)*C(4,2)=10*6=60

解析：先從5個(gè)男生中選出3個(gè)，再從4個(gè)女生中選出2個(gè)，根據(jù)乘法原理計(jì)算總數(shù)。

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

謂詞邏輯：量詞（全稱量詞?和存在量詞?）、命題邏輯聯(lián)結(jié)詞（合取∧、析取∨、蘊(yùn)涵→、雙條件?）、命題公式及其真值表。

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

圖論：無向圖、有向圖、歐拉圖、最小生成樹、鄰接矩陣、通路、頂點(diǎn)度數(shù)、握手定理。

組合數(shù)學(xué)：基本原理（加法原理、乘法原理）、排列、組合、鴿巢原理。

布爾代數(shù)：基本運(yùn)算（與∧、或∨、非?）、分配律、德摩根律。

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

選擇題：考察學(xué)生對(duì)基本概念和定義的理解，如聯(lián)結(jié)詞、量詞、圖的基本性質(zhì)、集合運(yùn)算等。示例：判斷一個(gè)圖是否為歐拉圖，需要知道歐拉圖的定義和性質(zhì)。

多項(xiàng)選擇題：考察學(xué)生對(duì)多個(gè)相關(guān)概念的理解和區(qū)分，如命題邏輯聯(lián)結(jié)詞、集合運(yùn)算、圖論基本概念、謂詞邏輯量詞等。示例：列