2015年4月自考02324離散數(shù)學(xué)試題及答案含解析

離散數(shù)學(xué)年月真題

0232420154

1、【單選題】設(shè)有一個(gè)連通平面圖G，共有6個(gè)面，13條邊，則G的頂點(diǎn)個(gè)數(shù)為

6

7

A:

8

B:

9

C:

答D:案：D

解析：根據(jù)歐拉定理，設(shè)G為n階m條邊r個(gè)面的連通平面圖，則n-m+r=2。所以其邊數(shù)

n=m-r+2=13-6+2=9.

2、【單選題】下列謂詞公式中與公式

等價(jià)的是

A:

B:

C:

答D:案：A

解析：

3、【單選題】設(shè)p:天下雨;q:我走路上班。命題"只有不下雨，我才走路上班"可符號化為

A:

B:

C:

答D:案：D

解析：命題"只有不下雨，我才走路上班"可理解為“不下雨”是“我走路上班”的必要條

件。

4、【單選題】設(shè)R1，R2都是從集合A到B的二元關(guān)系，則下列各式成立的是

A:

B:

C:

答D:案：C

解析：

用互為子集法證明。

5、【單選題】設(shè)簡單無向圖G有16條邊，有3個(gè)4度頂點(diǎn)，有4個(gè)2度頂點(diǎn)，其余頂點(diǎn)的

度數(shù)均大于3，則G中的頂點(diǎn)個(gè)數(shù)至多為

9個(gè)

10個(gè)

A:

11個(gè)

B:

12個(gè)

C:

答D:案：B

解析：

設(shè)G中結(jié)點(diǎn)個(gè)數(shù)為x，由握手定理得方程：

6、【單選題】設(shè)α、β是集合A上的等價(jià)關(guān)系，則下列關(guān)系不一定是等價(jià)關(guān)系的是

A:

B:

C:

答D:案：A

解析：

（A或C都對）等價(jià)關(guān)系滿足自反性、對稱性和可傳遞性。兩個(gè)滿足某種性質(zhì)的關(guān)系經(jīng)過

某種運(yùn)算后是否仍保持這種性質(zhì)，可由下表的結(jié)論給出。可見，可傳遞關(guān)系的并運(yùn)算，其

結(jié)果不一定是可傳遞關(guān)系。對稱關(guān)系的復(fù)合也未必就是對稱關(guān)系，傳遞關(guān)系的復(fù)合也未必

是傳遞關(guān)系。

7、【單選題】下列語句為假命題的是

如果3是偶數(shù)，那么就是有理數(shù)

A:

只要3是偶數(shù)，就是有理數(shù)

B:

除非是有理數(shù)，否則3不是偶數(shù)

C:

只有3是偶數(shù)，才是有理數(shù)

D:

答案：D

解析：

“只有3是偶數(shù)，才是有理數(shù)”可理解為“3是偶數(shù)”是“是有理數(shù)”的必要

條件，顯然該命題是假的。

8、【單選題】設(shè)R(x):x是實(shí)數(shù);p(x):x的平方;L(x):x大于等于0;語句"實(shí)數(shù)的平方大于

等于0"可符號化為

A:

B:

C:

答D:案：D

解析：符號化時(shí)，如果使用全稱量詞，則特性謂詞與普通謂詞之間的關(guān)系是單條件。

9、【單選題】有界格如題9圖所示，則元素d的補(bǔ)元是

a

A:

b

c

B:

1

C:

答D:案：A

解析：因?yàn)閍∨d=1,a∧d=0

10、【單選題】給定A={1，2，3，4}，考慮A上的關(guān)系R，若

，則R是

自反的

對稱的

A:

傳遞的

B:

反自反的

C:

答D:案：C

解析：

11、【單選題】設(shè)集合A有3個(gè)元素，則A上的等價(jià)關(guān)系的個(gè)數(shù)為

3個(gè)

4個(gè)

A:

5個(gè)

B:

6個(gè)

C:

答D:案：C

解析：不妨設(shè)A={a,b,c}，則其只有一個(gè)劃分塊的劃分?jǐn)?shù)只有1個(gè)；有兩個(gè)劃分塊的劃分

數(shù)有3個(gè)；有3個(gè)劃分塊的劃分?jǐn)?shù)只有1個(gè)，故總的劃分有5個(gè)。每個(gè)劃分都對應(yīng)一等價(jià)

關(guān)系。

12、【單選題】是一個(gè)偏序集，其中

為A上的整除關(guān)系，則覆蓋元素6的元

素是

6

12

A:

24

B:

36

C:

答D:案：B

解析：

13、【單選題】謂詞公式

中，量詞的轄

域是

A:

B:

C:

答D:案：B

解析：

給定一個(gè)謂詞公式A，其中有一部分公式形如B(x)或B(x)，則稱它為A的

x約束部分，稱B(x)為相應(yīng)量詞的轄域。原公式中H(x,y)與量詞無關(guān)，故其轄

域?yàn)椤?/p>

14、【單選題】連通圖G是一棵樹的充要條件是

有些邊不是割邊

每條邊都是割邊

A:

無邊割集

B:

每條邊都不是割邊

C:

答D:案：B

解析：樹是連通、無回路的圖，因此其每條邊均為割邊，否則圖中必存在回路。

15、【單選題】在自然數(shù)集N上，下列滿足結(jié)合律的運(yùn)算是

A:

B:

C:

答D:案：C

解析：因?yàn)?a*b)*c=c;a*(b*c)=b*c=c。故(a*b)*c=a*(b*c)。

16、【問答題】構(gòu)造命題公式的真值表。

答案：

解析：構(gòu)造真值表時(shí)可根據(jù)命題公式的特點(diǎn)，先求其成真指派（或成假指派）。構(gòu)造真值

表時(shí)要注意真值指派的書寫規(guī)律。

17、【問答題】利用等值演算法求命題公式

的主析取范式。

答案：

解析：

求命題公式的主合取范式可用等值演算法和真值表法。本題中要求用等值演算法求。其具

體步驟包括：①化歸為析取范式。②除去析取范式中所有永假的簡單合取式。③在簡單

合取式中，將重復(fù)出現(xiàn)的合取項(xiàng)和相同變元合并。④在簡單合取式中補(bǔ)入沒有出現(xiàn)的命

題變元，即添加再用分配律展開，最后合并相同的小項(xiàng)。同一公式的

主析取范式中m的下標(biāo)和主合取范式中M的下標(biāo)是互補(bǔ)的。因此，知道了主析(合)取范式

就可以寫出主合(析)取范式。如果其主合取范式比較容易求得，也可以利用主合取范式與

主析取范式之間的關(guān)系，直接寫出其主析取范式。

18、【問答題】設(shè)為偏序集，其哈斯圖如題28圖所示，試求:(1)寫

出偏序關(guān)系≤。(2)設(shè)B={c,d，f}，求B的極大元、極小元、上界和下界。

答案：

（2）B={c,d，f}，B的極大元是f；極小元是c,d；上界是f,g；下界是a。

解析：

偏序關(guān)系滿足自反性，反對稱性和可傳遞性。偏序關(guān)系與哈斯圖是一一對應(yīng)的。

19、【問答題】已知集合s={{1,2,4},{3},{5}}是集合A={1，2，3，4，5}的一

個(gè)劃分，(1)寫出由S導(dǎo)出的A上的等價(jià)關(guān)系ρ(2)求ρ的關(guān)系矩陣Mρ。

答案：

20、【問答題】設(shè)解釋I如下:D={2，3}，F(xiàn)(2,2)=F(3,3)=0,F(2,3)=

F(3,2)=1,f(2,2)=f(2,3)=2,f(3,2)=f(3,3)=3。求謂詞公式

在I下的真值。

答案：

解析：

若指定謂詞公式的論域?yàn)橛邢藜瘎t可通過下列公式將量詞?、

?消去。消去量詞

和個(gè)體變元后，就變成普通的命題公式進(jìn)行賦值運(yùn)算，得到給定的謂詞公式的真值。

21、【問答題】設(shè)A，B是任意集合，證

明:。

答案：

解析：證明集合相等的典型方法是用互為子集法。

22、【問答題】在整數(shù)集Z上定義一個(gè)二元運(yùn)算*，使得對于Z中的任意元素a和b，都有

a*b=a+b+ab，證明:<Z,*>是獨(dú)異點(diǎn)。

答案：

解析：驗(yàn)證代數(shù)系統(tǒng)是否為獨(dú)異點(diǎn)，只需要逐一驗(yàn)證以下三個(gè)條件：(1)封閉性(2)結(jié)合

律(3)有幺元

23、【問答題】設(shè)圖G如題33圖所示，證

明:圖G不是哈密頓圖。

答案：

24、【問答題】如果小明沒有去上學(xué)，那他一定是生病了。如果小明生病了，他就會在家休

息。只要小明去上學(xué)，他就會在教室認(rèn)真學(xué)習(xí)。小明要么在教室認(rèn)真學(xué)習(xí)，要么在家休息。

符號化上述推理過程，并構(gòu)造推理證明。

答案：

解析：在符號化并證明推理有效性的題目中，要特別注意以下幾點(diǎn)：（1）是命題邏輯的

推理有效性還是謂詞邏輯中的推理有效性問題；（2）如有必要，假設(shè)合理的論域；（3）

用適當(dāng)?shù)姆柋硎舅械脑用}；（4）寫出推理的假設(shè)和結(jié)論；（5）證明推理的有效

性。特別注意的是量詞消去的次序不能有誤！

25、【問答題】用Kruskal算法求題35圖中的一棵最小生成樹，并畫出此樹。(須寫出詳

細(xì)過程)

答案：

按照Kruskal算法求其最小生成樹。步驟如下：

解析：

利用Kruskal算法求最小生成樹的步驟如下：

26、【填空題】設(shè)A={1，2，3}，B={3，4，5}，則B-A

=,__________=__________。

答案：{4,5}；{1,2,4,5}

解析：

27、【填空題】設(shè)

是集合A={1,2,3,4}到集合B={a，b，c，d}的關(guān)系，則ranR=__________,domR

=__________

答案：{a,b,d}；{1,2,4}

解析：ranR表示R的值域；domR表示R的定義域

28、【填空題】命題公式的成真指派有__________個(gè)，成假

指派有__________個(gè)。

答案：7，1

解析：

剛好是一個(gè)大項(xiàng)，根據(jù)大項(xiàng)的性

質(zhì)，當(dāng)且僅當(dāng)其真值指派為FTT時(shí)，其取值為假。

29、【填空題】設(shè)ρ(A)是非空集合A的冪集，代數(shù)系統(tǒng)<ρ(A),U>的零元是

__________，幺元是__________。

答案：

A，

解析：

因?yàn)?/p>

30、【填空題】謂詞公式

中的約束變

元有__________，自由變元有__________。

答案：約束變元有x,y；自由變元有x,y

解析：

受量詞指導(dǎo)的變元為約束變元.在公式中，x是自由變元，

y是約束變元；而在公式中，x是約束變元，y是自由變元。

31、【填空題】設(shè)集合A={a，b，c}以及A上的一個(gè)二元關(guān)系

,則自反閉包r(R)

=__________對稱閉包s(R)=__________

答案：

解析：

32、【填空題】命題公式的二進(jìn)制數(shù)編碼大項(xiàng)Mi為

__________

答案：M110

解析：大項(xiàng)的編碼規(guī)則。

33、【填空題】設(shè)無向樹T有4個(gè)度數(shù)為3的結(jié)點(diǎn)，其余結(jié)點(diǎn)都為樹葉，則T的樹葉數(shù)為

__________。

答案：6

解析：設(shè)無向樹T中的樹葉數(shù)為x，則根據(jù)樹的性質(zhì)，其邊數(shù)為4+x-1=x+3。由握手定理

得方程：4×3+x×1=（x+3）×2，解得x=6.

3