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

1.下列哪個(gè)不是命題邏輯的基本聯(lián)結(jié)詞？

A.非

B.且

C.或

D.等價(jià)

2.在命題公式中，以下哪個(gè)是永真式？

A.(P∧?P)

B.(P∨?P)

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

D.(P∨Q)→P

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

A.{1,2}

B.{2,3}

C.{3,4}

D.{1,4}

4.下列哪個(gè)是圖G的鄰接矩陣？

A.對(duì)角矩陣

B.對(duì)稱矩陣

C.零矩陣

D.單位矩陣

5.在有向圖中，如果存在一條從頂點(diǎn)u到頂點(diǎn)v的路徑，則稱u和v是？

A.相鄰的

B.連通的

C.強(qiáng)連通的

D.偽連通的

6.下列哪個(gè)不是樹的性質(zhì)？

A.至少有兩個(gè)葉子結(jié)點(diǎn)

B.沒有環(huán)

C.任意兩個(gè)頂點(diǎn)之間有唯一路徑

D.有根結(jié)點(diǎn)

7.在集合論中，下列哪個(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)×C

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

A.?x?yP(x,y)

B.?x?yP(x,y)

C.?x?yP(x,y)

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

9.在圖論中，下列哪個(gè)是歐拉路徑？

A.經(jīng)過每條邊一次且僅一次的路徑

B.經(jīng)過每個(gè)頂點(diǎn)一次且僅一次的路徑

C.經(jīng)過每條邊至少一次的路徑

D.經(jīng)過每個(gè)頂點(diǎn)至少一次的路徑

10.下列哪個(gè)是正確的布爾代數(shù)性質(zhì)？

A.a+b=b+a

B.a∧b=b∧a

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

D.(a∧b)+c=a∧(b+c)

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

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

A.非

B.且

C.或

D.等價(jià)

E.如果

2.下列哪些是永真式？

A.(P∧?P)

B.(P∨?P)

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

D.(P∨Q)→P

E.(P∧Q)?(Q∧P)

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

A.A∪B={1,2,3,4}

B.A∩B={2,3}

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

D.B∩C={3,4}

E.A-B={1}

4.下列哪些是圖G的性質(zhì)？

A.圖G沒有環(huán)

B.圖G是連通的

C.圖G的每個(gè)頂點(diǎn)的度數(shù)都是偶數(shù)

D.圖G是歐拉圖

E.圖G是哈密頓圖

5.下列哪些是樹的結(jié)構(gòu)性質(zhì)？

A.樹沒有環(huán)

B.樹的任意兩個(gè)頂點(diǎn)之間有唯一路徑

C.樹至少有兩個(gè)葉子結(jié)點(diǎn)

D.樹有根結(jié)點(diǎn)

E.樹的邊數(shù)比頂點(diǎn)數(shù)少1

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

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

2.在集合論中，集合A包含n個(gè)元素，集合B包含m個(gè)元素，則A×B包含________個(gè)元素。

3.一個(gè)無向圖G包含n個(gè)頂點(diǎn)和m條邊，如果G是連通的，則m的最小值是________。

4.在樹中，一個(gè)頂點(diǎn)的度數(shù)是指與該頂點(diǎn)相鄰的邊的數(shù)量，一個(gè)樹的頂點(diǎn)度數(shù)之和等于________。

5.布爾代數(shù)中的分配律是指________。

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

1.化簡命題公式(P∧Q)∨(?P∧Q)∨(P∧?Q)。

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

3.給定有向圖G的鄰接矩陣如下，求頂點(diǎn)1到頂點(diǎn)4的所有可能路徑及其長度。

```

0101

1010

0101

0010

```

4.畫出下列集合的文氏圖，并求(A∪B)∩(A∪C)。

A={1,2,3,4}

B={3,4,5,6}

C={1,3,5,7}

5.對(duì)于布爾表達(dá)式F=A'B+AB'，寫出其真值表，并求其最簡與或表達(dá)式。

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

一、選擇題答案

1.D

2.B

3.B

4.B

5.A

6.A

7.A

8.A

9.A

10.A

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

1.A,B,C

2.B,C,E

3.A,B,C,D,E

4.A,B,C

5.A,B,D,E

三、填空題答案

1.全稱量詞

2.n×m

3.n-1

4.2m

5.a∧(b∨c)?(a∧b)∨(a∧c)

四、計(jì)算題答案

1.Q

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

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

-1→2→3→4，長度為3

-1→4，長度為1

4.文氏圖如下：

```

A:1234

B:3456

C:1357

```

(A∪B)∩(A∪C)={1,2,3,4,5,6}∩{1,3,5,7}={1,3,5}

5.真值表：

```

ABA'BAB'F

00111

01100

10011

11000

```

最簡與或表達(dá)式：F=A'B+AB'

知識(shí)點(diǎn)總結(jié)及題型考察詳解

一、選擇題

1.考察命題邏輯的基本聯(lián)結(jié)詞，正確答案是“等價(jià)”，其他選項(xiàng)都是命題邏輯的基本聯(lián)結(jié)詞。

2.考察永真式的判斷，正確答案是“(P∨?P)”，因?yàn)樗硎綪和其否定?P至少有一個(gè)為真。

3.考察集合的交集運(yùn)算，正確答案是“{2,3}”，因?yàn)锳和B的共同元素是2和3。

4.考察圖的鄰接矩陣性質(zhì)，正確答案是“對(duì)稱矩陣”，因?yàn)闊o向圖的鄰接矩陣是對(duì)稱的。

5.考察有向圖中頂點(diǎn)的相鄰關(guān)系，正確答案是“相鄰的”，因?yàn)榇嬖谝粭l從u到v的路徑。

6.考察樹的結(jié)構(gòu)性質(zhì)，正確答案是“至少有兩個(gè)葉子結(jié)點(diǎn)”，因?yàn)闃淇梢灾挥幸粋€(gè)葉子結(jié)點(diǎn)。

7.考察集合論中的笛卡爾積運(yùn)算，正確答案是“A×(B∪C)=(A×B)∪(A×C)”。

8.考察謂詞邏輯公式的正確性，正確答案是“?x?yP(x,y)”，因?yàn)樗硎緦?duì)于所有x，存在一個(gè)y使得P(x,y)為真。

9.考察圖論中的歐拉路徑定義，正確答案是“經(jīng)過每條邊一次且僅一次的路徑”。

10.考察布爾代數(shù)的交換律，正確答案是“a+b=b+a”。

二、多項(xiàng)選擇題

1.考察命題邏輯的基本聯(lián)結(jié)詞，正確答案是“A,B,C”，因?yàn)榉?、且、或是命題邏輯的基本聯(lián)結(jié)詞。

2.考察永真式的判斷，正確答案是“B,C,E”，因?yàn)樗鼈兌际怯勒媸健?/p>

3.考察集合論中的集合運(yùn)算，正確答案是“A,B,C,D,E”，因?yàn)樗羞x項(xiàng)都是正確的集合運(yùn)算結(jié)果。

4.考察圖的結(jié)構(gòu)性質(zhì)，正確答案是“A,B,C”，因?yàn)闊o向圖、連通圖、每個(gè)頂點(diǎn)的度數(shù)都是偶數(shù)的圖都有特定性質(zhì)。

5.考察樹的結(jié)構(gòu)性質(zhì)，正確答案是“A,B,D,E”，因?yàn)闃涞慕Y(jié)構(gòu)具有這些性質(zhì)。

三、填空題

1.考察謂詞邏輯中的量詞，正確答案是“全稱量詞”，表示對(duì)于所有x。

2.考察集合論中的笛卡爾積運(yùn)算，正確答案是“n×m”，因?yàn)榧螦和B的笛卡爾積包含n×m個(gè)元素。

3.考察圖論中的連通圖性質(zhì)，正確答案是“n-1”，因?yàn)檫B通圖的最小邊數(shù)是n-1。

4.考察樹的結(jié)構(gòu)性質(zhì)，正確答案是“2m”，因?yàn)闃涞捻旤c(diǎn)度數(shù)之和等于2倍的邊數(shù)。

5.考察布爾代數(shù)的分配律，正確答案是“a∧(b∨c)?(a∧b)∨(a∧c)”。

四、計(jì)算題

1.考察命題邏輯的化簡，正確答案是“Q”，因?yàn)榛喓笏星闆r下都為真。

2.考察集合論中的集合運(yùn)算，正確答案是“(2,3),(2,4),(3,3),(3,4)”。

3.考察圖論中的路徑尋找，正確答案是“1→2→3→4”和“1→4”。

4.考察集合論中的集合運(yùn)算和文氏圖，正確答案是“{1,3,5}”。

5.考察布爾代數(shù)的真值表和最簡表達(dá)式，正確答案是“F=A'B+AB'”。

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

一、選擇題

考察學(xué)生對(duì)命題邏輯、集合論、圖論、樹、布爾代數(shù)等基本概念的掌握程度。通過選擇題