貴州高校離散數(shù)學試卷

貴州高校離散數(shù)學試卷一、選擇題（每題1分，共10分）

1.在集合論中，集合A={1,2,3}與集合B={3,4,5}的并集是？

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

B.{1,2,5}

C.{3,4}

D.{1,2,3}

2.下列哪個是命題？

A.今天天氣真好！

B.x+y=5

C.請勿吸煙

D.這個問題很難

3.邏輯運算中，命題p和命題q的合?。ā模┑恼嬷当砣缦?，當p為假、q為真時，p∧q的真值是？

A.真

B.假

C.無法確定

D.以上都不對

4.在圖論中，一個有n個頂點的無向完全圖有多少條邊？

A.n(n-1)/2

B.n(n+1)/2

C.n^2

D.2n

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

A.如果p則q，非q，所以非p

B.如果p則q，p，所以q

C.如果p則q，非p，所以非q

D.如果p則q，q，所以p

6.在集合論中，集合A={a,b,c}的冪集有多少個元素？

A.3

B.6

C.7

D.8

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

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

B.判斷一個圖是否是哈密頓圖

C.判斷一個命題是否是重言式

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

8.在邏輯運算中，命題p的否定（?p）的真值表如下，當p為真時，?p的真值是？

A.真

B.假

C.無法確定

D.以上都不對

9.在圖論中，一個有n個頂點的有向完全圖有多少條邊？

A.n(n-1)

B.n(n+1)

C.n^2

D.2n(n-1)

10.下列哪個是正確的數(shù)學歸納法證明步驟？

A.假設(shè)命題對n成立，證明命題對n+1成立

B.假設(shè)命題對n+1成立，證明命題對n成立

C.假設(shè)命題對任意n成立，不需要證明

D.以上都不對

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

1.下列哪些是命題的例子？

A.2+3=5

B.這個句子是假的

C.請打開門

D.x是正數(shù)

2.在集合論中，下列哪些運算滿足交換律？

A.并集（∪）

B.交集（∩）

C.差集（-）

D.補集（'）

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

A.頂點

B.邊

C.鄰接矩陣

D.路徑

4.在邏輯運算中，下列哪些是正確的等價式？

A.p∧q≡q∧p

B.p∨q≡q∨p

C.p∧(q∨r)≡(p∧q)∨(p∧r)

D.p∨(q∧r)≡(p∨q)∧(p∨r)

5.在離散數(shù)學中，下列哪些是可計算問題？

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

B.判斷一個圖是否是二分圖

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

D.判斷一個命題是否是可滿足的

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

1.集合A={1,2,3}與集合B={3,4,5}的交集是________。

2.在命題邏輯中，命題p:"今天是星期一"，命題q:"明天是星期二"，則命題"如果今天是星期一那么明天不是星期二"的符號表達式是________。

3.一個有n個頂點的無向完全圖有________條邊。

4.在圖論中，一個有向圖G的鄰接矩陣為M，若M[i][j]=1表示從頂點i到頂點j有一條有向邊，則M的轉(zhuǎn)置矩陣M^T表示________。

5.在集合論中，集合A的補集是指相對于全集U，不屬于集合A的元素組成的集合，記作________。

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

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

2.寫出命題公式p∧(q∨r)的析取范式。

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

M=|0100|

|0010|

|0001|

|1000|

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

4.對于命題公式(p∨q)→?r，寫出其真值表。

5.已知集合A={a,b,c}，求集合A的所有非空子集。

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

一、選擇題答案及解析

1.A{1,2,3,4,5}并集是集合A和集合B中所有元素的合集。

2.A2+3=5是一個可以判斷真假的陳述句。

3.B假合取運算只有當p和q都為真時才為真，否則為假。

4.An(n-1)/2無向完全圖的定義是任意兩個頂點之間都有一條邊，邊數(shù)為n(n-1)/2。

5.B如果p則q，p，所以q這是肯定前件的推理形式，符合推理規(guī)則。

6.D8冪集是集合的所有子集的集合，包括空集和集合本身，2^n個元素。

7.C判斷一個命題是否是重言式是可判定問題，可以通過真值表等方法確定。

8.B假否定運算將命題的真假值反轉(zhuǎn)。

9.D2n(n-1)有向完全圖的定義是任意兩個頂點之間都有方向相反的兩條邊，邊數(shù)為2n(n-1)。

10.A假設(shè)命題對n成立，證明命題對n+1成立數(shù)學歸納法的標準步驟。

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

1.A,D2+3=5和x是正數(shù)可以判斷真假。

2.A,B,C并集、交集、差集都滿足交換律。

3.A,B,D頂點、邊、路徑是圖論的基本概念。

4.A,B,C,D都滿足邏輯等價式的定義。

5.A,C,D判斷偶數(shù)、合數(shù)、可滿足性都是可計算問題。

三、填空題答案及解析

1.{3,4}交集是集合A和集合B中共同擁有的元素。

2.p→?q如果今天是星期一（p）則明天不是星期二（?q）。

3.n(n-1)/2無向完全圖的邊數(shù)公式。

4.從頂點j到頂點i有一條有向邊轉(zhuǎn)置矩陣表示邊的方向反轉(zhuǎn)。

5.A'補集是相對于全集的不屬于該集合的元素。

四、計算題答案及解析

1.{1,3,4,7,8}(A∩B)={3,4}，(A∩B)∪C={1,3,4,7,8}。

2.p∧q∨p∧r析取范式是將合取項通過析取連接。

3.1→2→3→41→44個路徑。

4.真值表如下：

pqrp∨q?r(p∨q)→?r

TTTTFF

TTFTTT

TFTTFF

TFFTTT

FTTTFF

FTFTTT

FFTFFT

FFFFTT

5.{a},,{c},{a,b},{a,c},{b,c},{a,b,c}2^3-1個非空子集。

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

集合論：集合的運算（并、交、差、補）、冪集、子集、交集、并集的性質(zhì)、運算律。

命題邏輯：命題的定義、邏輯聯(lián)結(jié)詞（∧、∨、?、→、?）、真值表、等價式、推理形式、重言式、可判定問題。

圖論：圖的基本概念（頂點、邊、路徑）、無向圖、有向圖、完全圖、鄰接矩陣、圖的表示、路徑的求解。

數(shù)學歸納法：證明技巧，適用于與自然數(shù)相關(guān)的命題。

可計算性問題：判斷哪些問題是可以通過算法解決的問題。

題型考察知識點詳解及示例

選擇題：考察對基本概念和定義的掌握，通過單選題和多選題檢驗學生對知識的全面理解。例如，集合論中的并集、交集運算，命題邏輯中的推理形式，圖論中的完全圖