考研離散數(shù)學試卷一、選擇題（每題1分，共10分）

1.下列哪個集合是有限集？

A.自然數(shù)集

B.整數(shù)集

C.有理數(shù)集

D.{1,2,3,...,100}

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

A.p∨?p

B.p∧?p

C.p→?p

D.?(p∧q)→?p

3.設(shè)A={1,2,3}，B={2,3,4}，則A∩B等于？

A.{1,2}

B.{3,4}

C.{2,3}

D.{1,4}

4.下列哪個是有效的推理形式？

A.(p→q)∧q→p

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

C.(p∧q)→p

D.p→(q→p)

5.設(shè)f:A→B是一個函數(shù)，A={1,2,3}，B={a,b,c}，則下列哪個是可能的函數(shù)？

A.f={(1,a),(2,b),(3,c)}

B.f={(1,a),(2,a),(3,b)}

C.f={(1,b),(2,c),(3,a)}

D.f={(1,c),(2,a),(3,b)}

6.下列哪個是圖G的Eulerian回路？

A.G中所有頂點的度數(shù)都是偶數(shù)，且G連通

B.G中所有頂點的度數(shù)都是奇數(shù)，且G連通

C.G中存在一條經(jīng)過所有邊的路徑，且起點和終點相同

D.G中存在一條經(jīng)過所有頂點的路徑，且每條邊恰好經(jīng)過一次

7.下列哪個是偏序集？

A.(N,≤)

B.(Z,<)

C.(Q,≥)

D.(R,≠)

8.下列哪個是可判定問題？

A.判斷一個圖是否是連通的

B.判斷一個圖是否是Eulerian圖

C.判斷一個圖是否是Hamiltonian圖

D.判斷一個命題公式是否是永真式

9.下列哪個是可計算問題？

A.判斷一個數(shù)是否是素數(shù)

B.判斷一個數(shù)是否是偶數(shù)

C.判斷一個數(shù)是否是合數(shù)

D.判斷一個數(shù)是否是黃金分割數(shù)

10.下列哪個是圖G的著色問題？

A.用k種顏色給圖G的頂點著色，使得相鄰頂點顏色不同

B.用k種顏色給圖G的邊著色，使得相鄰邊顏色不同

C.用k種顏色給圖G的頂點著色，使得所有頂點顏色相同

D.用k種顏色給圖G的邊著色，使得所有邊顏色相同

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

1.下列哪些是命題邏輯的永真式？

A.p∨?p

B.(p∧q)→p

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

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

2.設(shè)A={1,2,3}，B={2,3,4}，C={3,4,5}，則下列哪些集合運算結(jié)果是有限集？

A.A∪B

B.A∩C

C.B∩C

D.A×B

3.下列哪些是有效的推理形式？

A.(p∧q)→p

B.(p→q)∧p→q

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

D.p→(q→p)

4.設(shè)f:A→B是一個函數(shù)，A={1,2,3}，B={a,b,c}，則下列哪些是可能的函數(shù)？

A.f={(1,a),(2,b),(3,c)}

B.f={(1,a),(2,a),(3,b)}

C.f={(1,b),(2,c),(3,a)}

D.f={(1,c),(2,a),(3,b),(2,c)}

5.下列哪些是圖G的Eulerian路徑？

A.G中所有頂點的度數(shù)都是偶數(shù)，且G連通

B.G中恰好有兩個頂點的度數(shù)是奇數(shù)，且G連通

C.G中存在一條經(jīng)過所有邊的路徑，且起點和終點不同

D.G中存在一條經(jīng)過所有頂點的路徑，且每條邊恰好經(jīng)過一次

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

1.若命題p為“今天下雨”，q為“我出門不帶傘”，則命題“如果今天下雨，那么我出門不帶傘”的邏輯表達式為______。

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

3.在命題邏輯中，永真式的定義是______。

4.設(shè)f:A→B是一個函數(shù)，A={1,2}，B={a,b}，則函數(shù)f的所有可能個數(shù)為______。

5.一個圖G是Eulerian圖的充分必要條件是______。

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

1.對于命題公式p∧(q∨?r)→(?p∨r)，請寫出其真值表，并判斷該公式是否為永真式。

2.設(shè)集合A={1,2,3}，B={2,3,4}，C={3,4,5}。計算A×(B∩C)和(A×B)∩(A×C)的結(jié)果。

3.給定函數(shù)f:Z→Z，定義為f(x)=x+1。請判斷該函數(shù)是否為單射、滿射、雙射，并說明理由。

4.考慮圖G，其頂點集V={v1,v2,v3,v4}，邊集E={(v1,v2),(v1,v3),(v2,v4),(v3,v4)}。請計算該圖的度數(shù)列，并判斷該圖是否為連通圖。

5.對于偏序集(S,≤)，其中S={a,b,c,d}，偏序關(guān)系≤如下所示：

a≤a

a≤b

a≤c

b≤b

b≤c

c≤c

d≤d

請畫出該偏序集的Hasse圖，并找出其所有極大元和極小元。

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

一、選擇題答案

1.D

2.A

3.C

4.C

5.A

6.A

7.A

8.D

9.A

10.A

二、多項選擇題答案

1.A,B,C,D

2.A,B,C,D

3.A,B,C

4.A,B,C

5.B,C

三、填空題答案

1.p→q

2.{1,2,3,4},{2,3}

3.對于任意輸入的真值組合，該命題公式都為真

4.4

5.圖G中所有頂點的度數(shù)都是偶數(shù)，且G連通

四、計算題答案

1.真值表：

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

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

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

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

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

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

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

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

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

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

該公式為永真式。

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

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

3.f(x)=x+1是單射，因為對于任意x1,x2∈Z，若f(x1)=f(x2)，則x1+1=x2+1，即x1=x2。

f(x)=x+1不是滿射，因為不存在x∈Z使得f(x)=0，即0?Im(f)。

f(x)=x+1不是雙射，因為它不是滿射。

4.度數(shù)列：deg(v1)=2,deg(v2)=2,deg(v3)=2,deg(v4)=1。

該圖不是連通圖，因為頂點v4與其他頂點不相連。

5.Hasse圖：

```

b

/\

ac

/

d

```

極大元：{b,c}

極小元：wea4oy2

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

1.命題邏輯

-命題：能夠判斷真假的陳述句。

-邏輯連接詞：?（非），∧（與），∨（或），→（蘊涵），?（雙蘊涵）。

-永真式：對于任意真值賦值，命題公式都為真的表達式。

-推理形式：從前提推導出結(jié)論的合法形式。

2.集合論

-集合：一組確定的、互不相同的對象的全體。

-集合運算：并集（∪），交集（∩），差集（-），笛卡爾積（×）。

-子集：A?B表示集合A中的每個元素都是集合B中的元素。

3.函數(shù)

-函數(shù)：一個集合到另一個集合的映射。

-單射：對于任意x1,x2∈A，若f(x1)=f(x2)，則x1=x2。

-滿射：對于任意y∈B，都存在x∈A使得f(x)=y。

-雙射：既是單射又是滿射的函數(shù)。

4.圖論

-圖：由頂點集合和邊集合組成的結(jié)構(gòu)。

-度數(shù)：與頂點相連的邊的數(shù)量。

-Eulerian圖：所有頂點的度數(shù)都是偶數(shù)，且圖連通。

-連通圖：任意兩個頂點之間都存在路徑的圖。

5.偏序集

-偏序關(guān)系：滿足自反性、反對稱性和傳遞性的關(guān)系。

-Hasse圖：偏序集的圖形表示，忽略傳遞閉包中的邊。

-極大元：沒有其他元素嚴格大于它的元素。

-極小元：沒有其他元素嚴格小于它的元素。

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

1.選擇題

-考察學生對命題邏輯、集合論、函數(shù)、圖論、偏序集等基本概念的掌握程度。

-示例：判斷一個命題公式是否