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

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

0232420174

1、【單選題】下列命題公式為重言式的是

(P→Q)∧Q∧R

(P→?P)→?Q

A:

?(Q→R)∧R

B:

((P→Q)∧(Q→R))→(P→R)

C:

答D:案：D

解析：在各種賦值下均為真的命題公式為重言式，或者稱為永真式?？梢酝ㄟ^列出每個選

項的真值表來進行判斷。也可以用否定法來判斷，對A選項，只要Q與R有一個為假，命

題即是假，排除A；對B選項，P為假，Q為真，命題即為假，排除B；對C選項，R為假

時，命題即為假，排除C；所以選D。

2、【單選題】命題公式A中含n個命題變項，A為矛盾式的條件是A的主合取范式含

2n個極大項

1個極大項

A:

2n個極小項

B:

1個極小項

C:

答D:案：A

解析：矛盾式?jīng)]有成真賦值。每個極大項有一種成假賦值組合，因為命題公式A中含n個

命題變項，當其主合取范式恰好擁有2n個極大項時，恰好窮盡了所有賦值組合，即對A

來說，所有賦值組合都是成假的，A即是矛盾式。

3、【單選題】下列關(guān)于整數(shù)集合上的整除關(guān)系描述不正確的是

自反的

對稱的

A:

反對稱的

B:

傳遞的

C:

答D:案：B

4、【單選題】設(shè)F(x)：x是在美國的留學生，G(y):y是亞洲人。命題“并不是所有在美國

的留學生都是亞洲人”可符號化為

??x(F(x)→G(x))

A:

??x(F(x)→G(x))

??x(F(x)→?yG(y))

B:

??x(F(x)∧G(x))

C:

答D:案：B

解析：先把“所有在美國的留學生都是亞洲人”符號化為?x(F(x)→G(x))，然后再否定

即可。

5、【單選題】關(guān)于笛卡爾積，下列陳述不正確的是

A×(B∪C)=(A×B)∪(A×C)

A×(B∩C)=(A×B)∩(A×C)

A:

P(A)×P(A)=P(A×A)

B:

(A∪B)×C=(A×C)∪(B×C)

C:

答D:案：C

解析：A、B、D選項為笛卡爾積的分配律。C選項與笛卡兒積無關(guān)。

6、【單選題】設(shè)A-B=A,則有

A∩B=

B=A

A:

B?A

B:

A?B

C:

答D:案：A

解析：A-B表示元素x在A中同時在B中，但是運算之后還是A，說明B沒有起到限制作

用，即A與B沒有交集。

7、【單選題】對任意集合A、B關(guān)于其冪集的下列敘述不正確的是

|P(A)|=2|A|

|P(B)|=2|B|

A:

P(A)∩P(B)=P(A∩B)

B:

P(A)∪P(B)=P(A∪B)

C:

答D:案：D

解析：A、B都是集合的冪集元素個數(shù)的計算公式。集合冪集的交集等于交集的冪集，所以

C正確。D不正確，可以驗證如下。設(shè)A=｛1｝，B=｛2，3｝，則A的冪集是｛Φ，

｛1｝｝，B的冪集是｛Φ，｛2｝，｛3｝，｛2，3｝｝，它們的并集為｛Φ，｛1｝，

｛2｝，｛3｝，｛2，3｝｝。A與B的并集為｛1，2，3｝，它的冪集為｛Φ，｛1｝，

｛2｝，｛3｝，｛1，2｝，｛1，3｝，｛2，3｝，｛1，2，3｝｝。明顯兩者不相等。

8、【單選題】下列一階邏輯等效變換不正確的是

A:

B:

C:

答D:案：C

解析：A、B、D為量詞轄域收縮與擴張等值式，C的正確形式應(yīng)該為

?x(A(x)→B)??xA(x)→B。

9、【單選題】在整數(shù)集Z上，下列定義的運算*能構(gòu)成一個群的是

a*b=a+b-2

a*b=a-b

A:

a*b=min?{a,b}

B:

a*b=ab

C:

答D:案：A

解析：群的定義要求，必須存在單位元，同時每個元素都有逆元。A選項存在單位元為

2，a逆元為4-a。其他選項都不滿足。

10、【單選題】設(shè)都是雙射函數(shù)，則下列性質(zhì)不正確的是

A:

B:

C:

答D:案：A

解析：

A選項考核函數(shù)復(fù)合原理：兩個雙射函數(shù)復(fù)合的反函數(shù)等于反函數(shù)反向復(fù)合，因此應(yīng)為

.其他選項都是反函數(shù)基本運算。

11、【單選題】下列的度數(shù)列，可以簡單圖化的是

5,5,4,4,2,1

5,4,3,2,2

A:

3,3,3,1

B:

4,4,3,3,2,2

C:

答D:案：D

解析：可圖化的度數(shù)列需要滿足模除2為0，即能夠整除2，故排除A。B選項最大度為

5，不滿足最大度小于階數(shù)n-1的要求，C不能構(gòu)成簡單圖。因此只能選D。

12、【單選題】一顆無向樹有5片樹葉，有3個2度結(jié)點，其余都是3度結(jié)點，那么這顆樹

的結(jié)點數(shù)是

10

11

A:

12

B:

13

C:

答D:案：B

解析：根據(jù)無向樹的定義，3個2度結(jié)點可以寫成三點連一線，組成小樹A，5片葉子再

與A相連則需要3個3度點，這樣需要11點即可完成。

13、【單選題】設(shè)R1，R2是A上的兩個二元關(guān)系，則下列描述不正確的是

A:

B:

C:

答D:案：C

解析：根據(jù)二元關(guān)系閉包的運算性質(zhì)可得C為錯誤。

14、【單選題】下列關(guān)于歐拉圖的描述正確的是

K4是歐拉圖

K5是歐拉圖

A:

完全圖都是歐拉圖

B:

K6是歐拉圖

C:

答D:案：B

解析：根據(jù)歐拉圖判斷方法即得K5是歐拉圖，歐拉圖需要每個結(jié)點度數(shù)都為偶數(shù)。

15、【單選題】設(shè)X={1,2,3,6}，D是X上的整除運算，下列關(guān)于代數(shù)系統(tǒng)<X，D>的描述

正確的是

格

群

A:

半群

B:

二元關(guān)系

C:

答D:案：A

解析：格首先需要具有偏序關(guān)系，在X上的整除只能是偏序。

16、【問答題】

答案：{〈1，2〉，〈3，1〉，〈2，1〉}，{〈4，5〉，〈5，4〉，〈2，5〉}

解析：

按照左右復(fù)合的定義進行計算。為S對R的右復(fù)合，為S對R的左復(fù)合。

17、【問答題】命題公式(p→(Q∧R))的成真指派為_____________，成假指派為

_______________。

答案：000，001，010，011，111；100，101，110

解析：列出真值表即可得到。

18、【問答題】公式的約束變元為

___________，自由變元為________________。

答案：x，z；y

解析：凡是受到?和?限制的叫做約束變元，其他的微自由變元。

19、【問答題】集合A={1，2，3}上的劃分共有___________種,其中劃分S={{1},{2，3}}中

有序?qū)Φ膫€數(shù)為______________。

答案：5；5

解析：集合A共有5個非空子集，所以其劃分為5種。有S中兩個元素{1},{2，3}組成的

有序?qū)€數(shù)為5個。

20、【問答題】完全圖K4是平面圖，其面數(shù)r為__________，記節(jié)點數(shù)為n,邊數(shù)為m，則

n-m+r=______________________。

答案：4；2

解析：完全圖K4共4個節(jié)點，兩兩相連，共分割成4個面，邊數(shù)為6個，所以n-m+r=4-

6+4=2。

21、【問答題】實數(shù)集R中的運算*定義如下:a*b=a+b-5ab，則*運算的單位元為

________________，*運算的零元為________________。

答案：0；1/5

解析：設(shè)單位元為e，由a*e=a有，a+e-5ae=a，解得e=0；設(shè)零元為?，由a*?=?有，

a+?-5a?=?，即a=5a?，解得?=1/5。

22、【問答題】

中，1的階為

____________，9階為____________。

答案：10；10

解析：群中元素a滿足ak=e的最小正整數(shù)k稱為該元素的階。<Z10,+>的單位元e=0，則

可以計算出1與10的階都是10。

23、【問答題】一個簡單無向連通圖，有n個結(jié)點，m條邊，則邊數(shù)m的最大值為

____________，邊數(shù)m的最小值為____________。

答案：n(n-1)/2；n-1

解析：確保n個結(jié)點相連，只要一條線即可，所以邊數(shù)最少為n-1；當任意兩個不同點之

間都有連通線時候，邊數(shù)最多，這時候恰好是無向完全圖，故邊數(shù)為n(n-1)/2。

24、【問答題】下題24圖的格中，b的補元是____________，c的補元是

___________。

答案：a，c，d；b，d

解析：根據(jù)格的補元定義進行判斷即可。

25、【問答題】一顆n階(n＞2)無向樹T，其最大度數(shù)的最小值為

____________，的最大值為____________。

答案：2；n-1

解析：因為n＞2，因此最大度數(shù)最小值為2。根據(jù)最大度數(shù)定義可以得出無向樹的最大

度數(shù)最小值為n-1。

26、【問答題】1000以內(nèi)既不能被5或6整除，也不能被8整除的正整數(shù)有多少個。

答案：【解】S={x|x∈Z∧1≤x≤1000}A={x|x∈Z∧x可被5整除}B={x|x∈Z∧x可被6整

除}C={x|x∈Z∧x可被8整除}(2分)易得|A|=200（1000/5=200），|B|=166

（1000/6=166.666…），|C|=125(1000/8=125)，且|A∩B|=33，|C∩B|=41，|C∩A|=25，

|C∩B∩A|=8(2分)則根據(jù)文氏圖可得，不能被5、6和8整除的數(shù)有1000-[|A|+|B|

+|C|-|A∩B|-|C∩B|-|C∩A|+|C∩B∩A|]=1000-(200+166+125-33-41-25+8）=1000-

400=600個(2分)

解析：本題解決主要是轉(zhuǎn)化為集合運算。

27、【問答題】構(gòu)造命題P→（P∨Q∨R）公式的真值表。

答案：

解：

解析：按照P、Q、R的賦值情況依次計算列表即可。

28、【問答題】

答案：

解：(1)關(guān)系圖:(2)關(guān)系矩陣為

（3）R具有反自反性和反對稱性，但是不具有自反性和

對稱性。

解析：掌握住圖的基本表示方法和基本性質(zhì)即可解決。

29、【問答題】求公式(P→Q)Λ(Q→R)的主析取范式和主合取范式。

答案：

解：（1）主析取范式（3分）

（2）主合取范式（3分）由主析取范式和主合取范式之間的關(guān)系可得

解析：主要利用蘊涵式向析取式和合取式的轉(zhuǎn)化規(guī)則，把公式化成主析取范式和主合取范

式，特別是要把主析取范式轉(zhuǎn)換成極小項形式。再求主合取范式時候，直接利用極大項與

極小項的關(guān)系進行轉(zhuǎn)換，比較方便。

30、【問答題】下面是某偏序集〈A，R〉的哈斯圖寫出集合A和偏序關(guān)系R的表達式。

答案：解：（1）由圖得出A=｛1，2，3，4，5｝（2）根據(jù)偏序關(guān)系的自反性、反對稱性

和傳遞性，可以得出R=｛<1，3>，<3，5>，<1，5>,<2，4>，<4，5>,<2，

5>，<1，1>，<2，2>，<3，3>，<4，4>，<5，5>｝=｛<1，3>，<3，5>，<

1，5>,<2，4>，<4，5>,<2，5>｝∪IA

解析：通過偏序關(guān)系的定義與哈斯圖進行反推即可得到。

31、【問答題】設(shè)

證明G關(guān)于矩

陣乘法構(gòu)成一個群。

答案：

證明：（1）對矩陣乘法來說，任意矩陣，因

此為單位元e。（2分）（2）剩下三個矩陣分別記作b，c，d，利用

矩陣乘法可以驗證bb=cc=dd=e，bd=db=c，cd=dc=b，bc=cb=d，可見G對矩陣乘法是封閉

的。（2分）（3）由bb=cc=dd=e可得b，c，d有逆元，其逆元都是本身。（2分）綜合

（1）（2）（3），得G關(guān)于矩陣乘法滿足群定義，構(gòu)成一個群。（1分）

解析：根據(jù)群的定義來判定。

32、【問答題】

答案：證明：（1）因為對?x，y∈R，f（〈x，y〉）=〈（x+y）/2，（x-y）/2〉，設(shè)有

存在〈x1，y1〉也使得f（〈x1，y1〉）=〈（x+y）/2，（x-y）/2〉，而根據(jù)f計算公式

f（〈x1，y1〉）=〈（x1+y1）/2，（x1-y1）/2〉f（〈x，y〉），則有方程組：（x+y）

/2=（x1+y1）/2，（x-y）/2=（x1-y1）/2可解得，x1=x，y1=y?？梢娒總€象具有唯一的

原象，f為單射。（3分）（2）對于R×R上的任意〈a，b〉，可設(shè)f（〈x，y〉）=〈a，

b〉，由定義f（〈x，y〉）=〈（x+y）/2，（x-y）/2〉有方程組：（x+y）/2=a，（x-

y）/2=b可解得，x=a+b，y=a-b。根據(jù)實數(shù)的封閉性，a+b∈R，a-b∈R。即可見，值域中

每個元素都有原象，f為滿射。（3分）綜合（1）、（2）得出，f是一個雙射函數(shù)。（1

分）

解析：根據(jù)雙射函數(shù)定義，要證明雙射，必須先滿射單射與滿射。單射與滿射都按照最基

本定義來證明。

33、【問答題】設(shè)圖G有n個結(jié)點，n+1條邊。證明：圖G中至少有一個結(jié)點度數(shù)≥3。

答案：證明：由于圖G有n+1條，故G的n個結(jié)點度數(shù)之和為2（n+1）條。2（n+1）

/n=2+2/n，所以G中至少有一個結(jié)點的度數(shù)不小于3。由此可見，圖G中至少有一個結(jié)點

度數(shù)≥3。(基本正確5分，完整7分)

解析：主要是考慮圖的邊、點與度數(shù)的關(guān)系。

34、【問答題】有向圖D如圖所示。求2到5的長度為2

的通路數(shù)；