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

1.下列哪個命題是永假式？

A.p∨?p

B.p∧?p

C.?(p∧?p)

D.(p∨q)→p

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

A.{1,2}

B.{3,4}

C.{2,3}

D.{1,4}

3.下列哪個是命題公式？

A.p∧q→r

B.p∨≠q

C.(p∧q)∨r→s

D.p∧(q∨r)

4.設(shè)命題公式p=(q∧r)→p，則p的析取范式為？

A.q∧r

B.q∨r

C.?q∧?r

D.?q∨?r

5.下列哪個是圖G的頂點數(shù)和邊數(shù)的關(guān)系？

A.|E|=|V|-1

B.|E|=|V|+1

C.|E|=2|V|

D.|E|=|V|/2

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

0100

0010

0001

1000

則G中頂點4到頂點1的路徑長度為？

A.1

B.2

C.3

D.4

7.下列哪個是歐拉圖？

A.具有奇數(shù)個奇度頂點的連通圖

B.所有頂點的度數(shù)均為偶數(shù)的連通圖

C.至少有兩個奇度頂點的連通圖

D.不存在歐拉回路的連通圖

8.設(shè)集合A={1,2,3},B={2,3,4},則A×B等于？

A.{(1,2),(2,3),(3,4)}

B.{(1,2),(1,3),(1,4),(2,2),(2,3),(2,4),(3,2),(3,3),(3,4)}

C.{(2,1),(3,1),(4,1),(2,2),(3,2),(4,2),(2,3),(3,3),(4,3)}

D.{(1,2),(2,3),(3,4),(4,1)}

9.下列哪個是偏序集？

A.(N,<)

B.(N,>)

C.(N,≤)

D.(N,≠)

10.設(shè)函數(shù)f:N→N定義為f(x)=x^2，則f是？

A.單射

B.滿射

C.雙射

D.非一一對應(yīng)

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

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

A.p∨?p

B.p∧?p

C.?(p∧?p)

D.(p∨q)→p

2.設(shè)集合A={1,2,3},B={2,3,4},C={3,4,5},則下列哪些是正確的？

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

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

C.A∩B∩C={3}

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

3.下列哪些是圖G的歐拉回路？

A.所有頂點的度數(shù)均為偶數(shù)的連通圖

B.具有奇數(shù)個奇度頂點的連通圖

C.經(jīng)過每條邊恰好一次且回到起點的回路

D.不存在歐拉回路的連通圖

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

0100

0010

0001

1000

則下列哪些是正確的？

A.G是強連通圖

B.G是單向連通圖

C.G是連通圖

D.G不是強連通圖

5.下列哪些是偏序集？

A.(N,<)

B.(N,>)

C.(N,≤)

D.(N,≠)

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

1.設(shè)命題公式p=q∧(r∨?s)，則p的合取范式為_______。

2.一個具有n個頂點的簡單無向圖，其最大邊數(shù)為_______。

3.設(shè)集合A={a,b,c}，B={1,2}，則A到B的函數(shù)個數(shù)共有_______個。

4.在偏序集(N,≤)中，小于等于5的元素組成的子集是_______。

5.設(shè)函數(shù)f:A→B，如果對于任意b∈B，都存在a∈A使得f(a)=b，則稱f為_______。

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

1.對于命題公式p∧(q∨r)→?q，求其主析取范式。

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

3.給定有向圖G的鄰接矩陣如下：

```

0100

0010

0001

1000

```

求圖G中從頂點1到頂點4的所有簡單路徑。

4.設(shè)偏序集(P,≤)中，P={a,b,c,d}，偏序關(guān)系≤如下所示：

```

a≤b,a≤c,b≤d,c≤d

```

畫出該偏序集的哈斯圖，并寫出所有極小元和極大元。

5.設(shè)函數(shù)f:R→R定義為f(x)=x^2，求f的反函數(shù)f^(-1)的定義域和值域。

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

一、選擇題答案

1.B

2.C

3.A

4.C

5.A

6.B

7.B

8.B

9.C

10.C

二、多項選擇題答案

1.A,C

2.A,B,C

3.A,C

4.A,B,C

5.A,B,C

三、填空題答案

1.(q∧?r∧?s)∨(q∧?r∧s)∨(q∧r∧?s)∨(q∧r∧s)

2.n(n-1)/2

3.2^3=8

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

5.滿射

四、計算題答案

1.主析取范式為(p∧?q∧?r)∨(?p∧?q∧?r)

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

3.從頂點1到頂點4的所有簡單路徑為：1→2→3→4和1→4

4.哈斯圖略，極小元為{a},極大元為ama6eyu

5.f^(-1)的定義域為[0,+∞)，值域為[0,+∞)

知識點總結(jié)

離散數(shù)學(xué)是計算機科學(xué)和信息技術(shù)的基礎(chǔ)課程，主要研究離散量及其結(jié)構(gòu)。本試卷涵蓋了離散數(shù)學(xué)中的命題邏輯、集合論、圖論、函數(shù)和關(guān)系、偏序關(guān)系等基礎(chǔ)知識。

一、選擇題知識點詳解及示例

1.命題邏輯：考查永真式（重言式）的判斷。永真式在任意賦值下都為真。例如，p∨?p是永真式，因為p和?p必有一個為真。

2.集合論：考查集合的交集運算。A∩B表示A和B的公共元素。例如，A={1,2,3},B={2,3,4}，則A∩B={2,3}。

3.命題公式：考查命題公式的定義。命題公式是由命題變元、邏輯聯(lián)結(jié)詞和括號組成的字符串。例如，p∧q→r是一個命題公式。

4.命題公式：考查命題公式的等價變換。?(p∧?p)等價于?p∨p，根據(jù)排中律，這是一個永真式。

5.圖論：考查無向圖的邊數(shù)關(guān)系。簡單無向圖的最大邊數(shù)是n(n-1)/2，其中n是頂點數(shù)。例如，n=4時，最大邊數(shù)為6。

6.圖論：考查有向圖中的路徑長度。路徑長度是指路徑上邊的數(shù)量。例如，1→2→3→4的路徑長度為3。

7.圖論：考查歐拉回路的定義。歐拉回路是經(jīng)過每條邊恰好一次且回到起點的回路。所有頂點的度數(shù)均為偶數(shù)的連通圖存在歐拉回路。

8.集合論：考查集合的笛卡爾積。A×B表示A和B的所有有序?qū)M合。例如，A={1,2,3},B={2,3,4}，則A×B={(1,2),(1,3),(1,4),(2,2),(2,3),(2,4),(3,2),(3,3),(3,4)}。

9.偏序關(guān)系：考查偏序集的定義。偏序關(guān)系是自反的、antisymmetric的、傳遞的。例如，(N,≤)是一個偏序集。

10.函數(shù)：考查函數(shù)的雙射性。雙射函數(shù)是一一對應(yīng)且滿射的函數(shù)。例如，f(x)=x^2是一個雙射函數(shù)，因為每個正數(shù)都有一個唯一的平方根。

二、多項選擇題知識點詳解及示例

1.命題邏輯：考查永真式的判斷。永真式在任意賦值下都為真。例如，p∨?p是永真式，因為p和?p必有一個為真。?(p∧?p)也是永真式，因為p∧?p是永假式。

2.集合論：考查集合的運算和笛卡爾積。A∩(B∪C)表示A與B和C的并集的交集。例如，A={1,2,3},B={2,3,4},C={3,4,5}，則A∩(B∪C)={2,3}。(A∩B)∪C表示A和B的交集與C的并集。例如，A∩B={2,3}，(A∩B)∪C={2,3,4,5}。A∩B∩C表示A、B和C的交集。例如，A∩B∩C={3}。A×(B∩C)表示A與B和C的交集的笛卡爾積。例如，B∩C={3,4}，A×(B∩C)={(1,3),(1,4),(2,3),(2,4),(3,3),(3,4)}。

3.圖論：考查歐拉回路的定義。歐拉回路是經(jīng)過每條邊恰好一次且回到起點的回路。所有頂點的度數(shù)均為偶數(shù)的連通圖存在歐拉回路。具有奇數(shù)個奇度頂點的連通圖不存在歐拉回路。

4.圖論：考查有向圖的連通性。強連通圖是指任意兩個頂點之間都有雙向路徑的圖。單向連通圖是指任意兩個頂點之間都有單向路徑的圖。連通圖是指任意兩個頂點之間都有路徑的圖。例如，給定的有向圖是單向連通圖和連通圖，但不是強連通圖，因為頂點之間的路徑不是雙向的。

5.偏序關(guān)系：考查偏序集的定義。偏序關(guān)系是自反的、antisymmetric的、傳遞的。例如，(N,<)是一個偏序集，因為小于關(guān)系是自反的、antisymmetric的、傳遞的。(N,>)也是一個偏序集，因為大于關(guān)系是自反的、antisymmetric的、傳遞的。(N,≤)也是一個偏序集，因為小于等于關(guān)系是自反的、antisymmetric的、傳遞的。(N,≠)不是一個偏序集，因為不等關(guān)系不滿足antisymmetric和transitive。

三、填空題知識點詳解及示例

1.命題邏輯：考查命題公式的主析取范式。主析取范式是命題公式所有真值指派下的真值組合的合取范式。例如，p∧(q∨r)→?q的主析取范式為(p∧?q∧?r)∨(?p∧?q∧?r)。

2.圖論：考查無向圖的邊數(shù)關(guān)系。簡單無向圖的最大邊數(shù)是n(n-1)/2，其中n是頂點數(shù)。例如，n=3時，最大邊數(shù)為3。

3.函數(shù)：考查函數(shù)的個數(shù)。A到B的函數(shù)個數(shù)等于B的元素個數(shù)的A的元素次方。例如，A={a,b,c}，B={1,2}，則A到B的函數(shù)個數(shù)共有2^3=8個。

4.偏序關(guān)系：考查偏序集中的子集。例如，在偏序集(N,≤)中，小于等于5的元素組成的子集是{1,2,3,4,5}。

5.函數(shù)：考查滿射的定義。滿射函數(shù)是指對于B中的每個元素，都存在A中的一個元素映射到它。例如，f:A→B，如果對于任意b∈B，都存在a∈A使得f(a)=b，則稱f為滿射。

四、計算題知識點詳解及示例

1.命題邏輯：考查命題公式的主析取范式。主析取范式是命題公式所有真值指派下的真值組合的合取范式。例如，p∧(q∨r)→?q的主析取范式為(p∧?q∧?r)∨(?p∧?q∧?r)。

2.集合論：考查集合的運算和笛卡爾積。A∩B表示A和B的公共元素。B∪C表示B和C的并集。A×(B∪C)表示A與B和C的并集的笛卡爾積。例如，A={1,2,3},B={2,3,4},C={3,4,5}，則A∩B={2,3}，B∪C={2,3,4,5}，A×(B∪C)={(1,2),(1,3),(1,4),(1,5),(2,2),(2,3),(2,4),(2,5),(3,2),(3,3),(3,4),(3,5)}。

3.圖論：考查有向圖中的路徑。路徑是指頂點序列，其中相鄰頂點之間有邊。簡單路徑是指不重復(fù)經(jīng)過任何頂點的路徑。例如，給定的有向圖，從頂點1到頂點4的所有簡單路徑為：1→2→3→4和1→