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

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

A.p∨?p

B.p∧?p

C.p→p

D.?(p∧q)??p∨?q

2.在集合論中，集合A={1,2,3}，集合B={2,3,4}，則A∩B等于？

A.{1,2}

B.{3,4}

C.{1,3}

D.{2,3}

3.下列哪個圖是歐拉圖？

A.完全圖K3

B.有向圖D1（有兩個頂點，一條有向邊）

C.星形圖S4

D.空圖

4.在圖論中，一棵樹的邊數(shù)等于頂點數(shù)減去？

A.1

B.2

C.3

D.4

5.下列哪個是正確的命題邏輯公式？

A.p∧(q∨r)→p

B.p∧(q∨r)→q

C.p∧(q∨r)→r

D.p∧(q∨r)→?p

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

A.(p→q)?(q→p)

B.(p→q)?(?p∨q)

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

D.(p→q)?(?p∧q)

7.在集合論中，集合A={1,2,3}，集合B={2,3,4}，則A×B的基數(shù)等于？

A.3

B.4

C.6

D.9

8.下列哪個是正確的謂詞邏輯公式？

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

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

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

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

9.在圖論中，一個無向圖G有6個頂點，每個頂點的度數(shù)都是3，則G的邊數(shù)等于？

A.6

B.9

C.12

D.18

10.在集合論中，集合A={1,2,3}，集合B={2,3,4}，則(A∪B)'等于？

A.{1}

B.{4}

C.{1,4}

D.?

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

1.下列哪些是命題邏輯中的基本連接詞？

A.與（∧）

B.或（∨）

C.非（?）

D.如果...那么...（→）

E.當(dāng)且僅當(dāng)（?）

2.在集合論中，下列哪些運算是補運算的實例？

A.A-B

B.U-A

C.A∩B

D.A∪B'

E.(A∩B)'

3.下列哪些圖是哈密頓圖？

A.完全圖K4

B.圓柱圖

C.簡單無向圖G，其中每個頂點的度數(shù)至少為n/2（n為頂點數(shù)）

D.簡單無向圖G，其中每個頂點的度數(shù)至少為n-1（n為頂點數(shù)）

E.歐拉圖

4.在圖論中，下列哪些是樹的特征？

A.沒有環(huán)

B.連通的

C.任意兩個頂點之間有且只有一條路徑

D.有n個頂點，有n-1條邊

E.可以有多個根

5.在謂詞邏輯中，下列哪些是量詞的實例？

A.?x(P(x))

B.?x(P(x))

C.?x?y(P(x,y))

D.?x?y(P(x,y))

E.P(x)

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

1.在命題邏輯中，公式p∧(q∨?r)的主析取范式為________。

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

3.一個有向圖G包含4個頂點，如果G是強連通的，則G至少有________條邊。

4.在圖論中，一棵有n個頂點的樹有________條邊。

5.謂詞邏輯公式?x?y(P(x,y))的意思是：對于每一個x，存在一個y使得P(x,y)為真。如果P(x,y)表示“x是y的朋友”，則該公式的自然語言描述為：________。

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

1.給定命題公式(p∧q)→?r，其中p,q,r為命題變元。請寫出該公式的真值表，并判斷該公式是否為重言式。

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

3.給定圖G如下，其中頂點集V={a,b,c,d,e}，邊集E={{a,b},{a,c},{b,c},{b,d},{c,e}}。請判斷圖G是否是連通圖，如果是，請給出從頂點a到頂點d的一條路徑。

4.寫出謂詞邏輯公式?x?y(P(x,y)∧Q(y))的否定，并說明其含義。其中P(x,y)表示“x喜歡y”，Q(y)表示“y是有趣的”。

5.設(shè)集合A={1,2,3}，B={2,3,4}。計算A×(B-A)。

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

一、選擇題答案及詳解

1.A.p∨?p是永真式（排中律）。

2.D.{2,3}是集合A和B的交集。

3.C.星形圖S4是歐拉圖，每個頂點的度數(shù)都是偶數(shù)。

4.A.1一棵樹的邊數(shù)等于頂點數(shù)減去1。

5.A.(p→q)?(q∨r)→p是正確的命題邏輯公式。

6.B.(p→q)?(?p∨q)是重言式（蘊涵等價式）。

7.D.9集合A和B的笛卡爾積的基數(shù)為3×3=9。

8.A.?x(P(x)→Q(x))是正確的謂詞邏輯公式。

9.B.9根據(jù)握手定理，無向圖中邊數(shù)等于所有頂點度數(shù)之和的一半，即6×3/2=9。

10.A.{1}集合A和B的并集為{1,2,3,4}，其補集為{1}。

二、多項選擇題答案及詳解

1.A,B,C,D,E所有這些都是命題邏輯中的基本連接詞。

2.B,D,E補運算是指集合在全集中的補集，U-A,A∩B',(A∩B)'都是補運算的實例。

3.A,C完全圖K4是哈密頓圖，每個頂點的度數(shù)都足夠大以形成哈密頓回路。簡單無向圖G中每個頂點的度數(shù)至少為n/2也是哈密頓圖的一個充分條件。

4.A,B,C,D樹的特征包括沒有環(huán)、連通、任意兩頂點間路徑唯一、n個頂點n-1條邊。

5.A,B,C,D,E所有這些都是謂詞邏輯中的量詞的實例。

三、填空題答案及詳解

1.(p∨q)∧(p∨?r)∧(?p∨q)∧(?p∨?r)主析取范式為所有小項的合取。

2.{1,3,4}首先計算A和B的交集為{2,3}，然后與C的并集為{1,3,4}。

3.5強連通圖至少需要5條邊，以確保所有頂點都在同一個強連通分量中。

4.n-1根據(jù)樹的定義，一棵有n個頂點的樹有n-1條邊。

5.對于每一個人，都有他的一個朋友是有趣的。謂詞邏輯公式的自然語言描述。

四、計算題答案及詳解

1.真值表：

pqr(p∧q)→?r

TTTF

TTFT

TFTT

TFFT

FTTT

FTFT

FFTT

FFFT

該公式是重言式，因為最后一列全為T。

2.(A-B)∩(C∪B)'={1,2}∩{1,2,6}={1,2}

3.圖G是連通圖，因為任意兩個頂點之間都有路徑。從a到d的一條路徑可以是a-b-d。

4.否定公式為?(?x?y(P(x,y)∧Q(y)))??x?y(?(P(x,y)∧Q(y)))??x?y((?P(x,y)∨?Q(y)))該公式的含義是：存在一個人，對于所有人，這個人都不喜歡該人或者該人不是有趣的。

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

知識點分類和總結(jié)

集合論：集合的基本運算（并、交、差、補）、集合的性質(zhì)、笛卡爾積、集合的基數(shù)的計算。

命題邏輯：基本連接詞、真值表、重言式、命題公式的主析取范式、邏輯等價式。

圖論：歐拉圖、哈密頓圖、樹的特征、握手定理、路徑的判斷和求解。

謂詞邏輯：量詞（全稱量詞?、存在量詞?）、謂詞邏輯公式的否定、自然語言描述。

計算題考察了學(xué)生對集合論、命題邏輯、圖論、謂詞邏輯等基本概念和運算的掌握程度，以及運用這些知識解決實際問題的能力。

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

選擇題：考察學(xué)生對基本概念和定理的理解，需要學(xué)生能夠快速準(zhǔn)確地判斷正確選項。例如，選擇題第1題考察了學(xué)生對命題邏輯中基本連接詞的理解。

多項選擇題：考察學(xué)生對多個知識點綜合應(yīng)用的能力，需要學(xué)生