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

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

02324201810

1、【單選題】下列命題是矛盾式的是

P→（P∨Q∨R）

(P→?P)→?Q

A:

?（Q→R）∧R

B:

（P→Q）→(?Q→?P)

C:

答D:案：C

解析：本題考核命題公式及其賦值，按照矛盾式的定義，在各種賦值下均為假的命題公式

即為矛盾式，也叫做永假式?？梢粤谐鍪钦嬷当韥?lái)判斷，也可以運(yùn)用邏輯思維來(lái)判斷。利

用真值表即可以得出選擇C。

2、【單選題】命題A中含有n個(gè)命題變項(xiàng)，A是重言式的條件是A的主析取范式含

2<>n個(gè)極大項(xiàng)

1個(gè)極大項(xiàng)

A:

2<>n個(gè)極小項(xiàng)

B:

1個(gè)極小項(xiàng)

C:

答D:案：C

解析：根據(jù)極小項(xiàng)的定義，由于每個(gè)命題變項(xiàng)在極小項(xiàng)中以原形或者否定式形式出現(xiàn)且僅

出現(xiàn)一次，因而n個(gè)命題變項(xiàng)共可產(chǎn)生2<>n個(gè)不同的極小項(xiàng)。

3、【單選題】設(shè)R為集合A上的關(guān)系，則下列敘述不正確的是

R在A上自反當(dāng)且僅當(dāng)IA?R

R在A上反自反當(dāng)且僅當(dāng)IA∩R=?

A:

R在A上對(duì)稱當(dāng)且僅當(dāng)R=R-1

B:

R在A上反對(duì)稱當(dāng)且僅當(dāng)R∩R-1=?

C:

答D:案：D

解析：本題考核二元關(guān)系的五種性質(zhì)的充分必要條件定理，根據(jù)這個(gè)定理判斷可見(jiàn)，R在

A上反對(duì)稱當(dāng)且僅當(dāng)R∩R-1=IA，故D錯(cuò)誤。

4、【單選題】設(shè)F（x）:x是兔子，G（y）:y是烏龜，H（x,y）:x比y跑得快。命題“并

不是所有兔子都比烏龜跑得快”可符號(hào)化為

??x(F(x)∧?y(G(y)→H(x,y)))

??x?y(F(x)∧G(y)→H(x,y))

A:

??x?y(F(x)∧G(y)→H(x,y))

B:

??x(F(x)∧?y(G(y)→H(x,y)))

C:

答D:案：B

解析：本題考核一階邏輯命題的符號(hào)化，其中“所有”對(duì)應(yīng)著全稱量詞“?”，“并不

是”表示邏輯非，“兔子都比烏龜跑得快”與“x比y跑得快”對(duì)應(yīng)，是蘊(yùn)含關(guān)系，且兔

子和烏龜是邏輯與的關(guān)系，因此組成答案B。

5、【單選題】設(shè)集合X={a,{a}}，則下列陳述不正確的是

{a}∈X

{a}?X

A:

{a,{a}}?X

B:

{a,{a}}∈X

C:

答D:案：D

解析：根據(jù)集合的運(yùn)算，可以看出{a,{a}}是原集合的子集，不是元素，因此不是屬于關(guān)

系，應(yīng)該是包含關(guān)系，因此{(lán)a,{a}}?X才是正確的。注此題選項(xiàng)為不正確的選項(xiàng)為D

6、【單選題】對(duì)非空集合A和B，若A∩B=A，則有

A-B=?

B-A=?

A:

B=?

B:

A=?

C:

答D:案：A

解析：根據(jù)集合的運(yùn)算，若A∩B=A，則A?B，因此必然有A-B=?，BCD顯然與非空集合要

求不相符。

7、【單選題】設(shè)A={1,{1},{1,{1}}}，則其冪集P（A）的元素總個(gè)數(shù)為

1

4

A:

8

B:

16

C:

答D:案：C

解析：根據(jù)，冪集是全體子集組成的集合，主要是要分清楚集合A有3個(gè)元素，則冪集個(gè)

數(shù)為2<>n=2<>3=8個(gè)。

8、【單選題】描述偏序集的是

哈密頓圖

哈斯圖

A:

歐拉圖

B:

樹(shù)

C:

答D:案：B

解析：畫(huà)出偏序關(guān)系的關(guān)系圖，即是哈斯圖。ACD都是圖論的理論，其中哈密頓圖是有哈

密頓回路的圖，歐拉圖是具有歐拉回路的圖，樹(shù)是連通無(wú)回路的無(wú)向圖。故選B。

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

a*b=max{a,b}

a*b=|a-b|

A:

a*b=a+b+1

B:

a*b=ab

C:

答D:案：C

解析：按照群的定義，在整數(shù)集合上，運(yùn)算是可結(jié)合的，存在單位元，每個(gè)元素都是逆

元，則是一個(gè)群。顯然只有C選項(xiàng)滿足以上要求，其單位元為-1，a的逆元是-2-a。因

此，選C。

10、【單選題】設(shè)f:X→Y，g:Y→Z是函數(shù)，則下列陳述不正確的是

若f和g都是單射的，這f°g也是單射的

若f和g都是雙射的，這f°g也是雙射的

A:

若g和f°g是滿射的，這f也是滿射的

B:

若f和g都是滿射的，這f°g也是滿射的

C:

答D:案：C

解析：根據(jù)函數(shù)復(fù)合的定理來(lái)判斷即可，都是單射就保持單射，都是雙射就保持雙射，都

是滿射就保持滿射。

11、【單選題】由4階3條邊構(gòu)成的無(wú)向簡(jiǎn)單圖的結(jié)點(diǎn)最大度數(shù)為

1

2

A:

3

B:

C:

4

答D:案：C

解析：圖的階數(shù)是圖的結(jié)點(diǎn)個(gè)數(shù)，也就是該圖有4個(gè)結(jié)點(diǎn)，簡(jiǎn)單圖是不存在平行邊與環(huán)的

圖，因此三條邊與結(jié)點(diǎn)連接的最大可能就是集中一點(diǎn)，即是三邊都與某一結(jié)點(diǎn)連接，這個(gè)

結(jié)點(diǎn)度數(shù)最大，為3。因此選C。

12、【單選題】下列為一顆6階無(wú)向樹(shù)的度數(shù)列，對(duì)應(yīng)不止一顆同構(gòu)樹(shù)的是

1,1,1,1,2,4

1,1,1,2,2,3

A:

1,1,2,2,2,2

B:

1,1,1,1,3,3

C:

答D:案：B

解析：無(wú)向樹(shù)是連通無(wú)回路的無(wú)向圖，簡(jiǎn)稱樹(shù)，根據(jù)樹(shù)的性質(zhì)，6階即6個(gè)結(jié)點(diǎn)，則樹(shù)的

邊數(shù)為6-1=5條，然后根據(jù)各個(gè)選項(xiàng)的度數(shù)列，畫(huà)出樹(shù)，即可發(fā)現(xiàn)B可以有兩種畫(huà)法：度

數(shù)為3的結(jié)點(diǎn)可以取在5個(gè)連接結(jié)點(diǎn)的第三個(gè)（五個(gè)并排結(jié)點(diǎn)的中間一個(gè)）位置，也可以

是第二或者四個(gè)（五個(gè)并排結(jié)點(diǎn)的中間一個(gè)的前一個(gè)或后一個(gè)）位置。因此選B。

13、【單選題】設(shè)有集合A、B、C，則下列描述不正確的是

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

A∪(B∩C)=(A∪B)∩(A∪C)

A:

A∩(B∪C)=(A∩B)∪(A∩C)

B:

A-(B∩C)=(A-B)∩(A-C)

C:

答D:案：D

解析：按照集合的基本運(yùn)算規(guī)律，即可得出D是不正確的。

14、【單選題】下列關(guān)于整數(shù)集合上的小于關(guān)系性質(zhì)描述不正確的是

反自反的

對(duì)稱的

A:

反對(duì)稱的

B:

傳遞的

C:

答D:案：B

解析：整數(shù)集合上的小于關(guān)系是二元關(guān)系，根據(jù)二元關(guān)系的性質(zhì)及整數(shù)的排序性質(zhì)，可以

得出其具有反自反性、反對(duì)稱性和傳遞性，顯然不正確的選擇B.

15、【單選題】分別記Z、N、Q、R為整數(shù)、自然數(shù)、有理數(shù)、實(shí)數(shù)集合，下列關(guān)于普通加

法的代數(shù)系統(tǒng)不是群的是

??<'Z，+><z，+></z，+><z，+></z，+><z，+></z，+><z，+><

/z，+><z，+></z，+><z，+></z，+><z,+></z,+>

A:

<'N，+><n，+></n，+><n，+></n，+><n,+></n,+>

<'Q，+><q，+></q，+><q，+></q，+><q,+></q,+>

B:

?<'R，+><r，+></r，+><r，+></r，+><r,+></r,+>

C:

答D:案：B

解析：按照，在整數(shù)集合上，運(yùn)算是可結(jié)合的，存在單位元，每個(gè)元素都是逆元，則是一

個(gè)群。對(duì)上面選項(xiàng)進(jìn)行驗(yàn)證，發(fā)現(xiàn)只有B不是群，因此選B。

16、【問(wèn)答題】集合A={1,2,3,4,5}，集合B={a,b,c,d,e},現(xiàn)有從A到B的二元關(guān)系R={<

1,b>,<3,e>,<5,e>}，和從B到A的二元關(guān)系S={<b,4>,<a,5>,<e,2>}，則

R°S=__________，S°R=_______________。

答案：{<1,4>}，{<a,e>}

解析：根據(jù)二元關(guān)系復(fù)合的計(jì)算方法，<1,b>與<b,4>復(fù)合即得出{<1,4>}，<a,5>

與<5,e>的復(fù)合得出{<a,e>}。

17、【問(wèn)答題】命題公式（?P→Q）→（P∧?Q）的成真指派為_(kāi)________，成假指派為

______________。

答案：00、10；01、11

解析：根據(jù)命題公式中P，Q不同取值列出真值表，即可得出其成真指派和成假指派。

18、【問(wèn)答題】公式（?x）（（P（x,y）→Q（z））

R（z））的約束變?cè)獮?/p>

_______，自由變?cè)獮開(kāi)______。

答案：x，y、z

解析：根據(jù)一階邏輯符號(hào)化的概念及全稱量詞與存在量詞，可以判斷約束變?cè)獮閤，而自

由取值沒(méi)有被約束的為y、z。

19、【問(wèn)答題】設(shè)A={a,b}，B={1,2,3,}，則|A×B|=_________，|A×P（B）

|=_________。

答案：6，16

解析：根據(jù)笛卡爾積的定義，笛卡爾積是指的二元有序?qū)M成的集合，顯然上述兩個(gè)集合

構(gòu)成的笛卡爾積共有元素為2×3=6個(gè)；P(B)表示B的冪集，是B的所有子集組成集合，

其元素有2n=23=8個(gè)，于是A×P(B)的元素個(gè)數(shù)為2×8=16個(gè)。

20、【問(wèn)答題】設(shè)實(shí)數(shù)集合上的函數(shù)f（x）=x2，g（x）=2x+1，那么復(fù)合函數(shù)fog（x）

=______，反函數(shù)g-1（x）=_______。

答案：1+2x2；(x-1)/2

解析：根據(jù)函數(shù)的復(fù)合與反函數(shù)的定義即可得出。

21、【問(wèn)答題】有理數(shù)Q中的運(yùn)算*定義如下：a*b=a+b+ab，則運(yùn)算*的單位元為

________；設(shè)a有逆元，則其逆元a-1為_(kāi)___________。

答案：0；-a/(a+1)

解析：根據(jù)二元運(yùn)算及其性質(zhì)計(jì)算。設(shè)運(yùn)算*的單位元e，則有

a*e=a?a+e+ae=a?e(1+a)=0?e=0；運(yùn)算*的逆元a<>-1，這有a*a<>-1=e?a+a<>-

1+aa<>-1=0?a<>-1=-a/(a+1)

22、【問(wèn)答題】

答案：6；3

解析：

23、【問(wèn)答題】設(shè)5階簡(jiǎn)單連通圖G所有結(jié)點(diǎn)的度數(shù)之和為18，則G的結(jié)點(diǎn)的最大度數(shù)為

_________，最小度數(shù)為_(kāi)______。

答案：4，3

解析：根據(jù)簡(jiǎn)單連通圖的性質(zhì)，其度數(shù)之和恰等于邊數(shù)之和的兩倍，因此邊數(shù)為9條，5

階說(shuō)明有5個(gè)頂點(diǎn)，這樣在保證連通的要求下，可以畫(huà)出圖形結(jié)構(gòu)，就會(huì)看到其結(jié)點(diǎn)的最

大度數(shù)為4，最小度數(shù)為3。

24、【問(wèn)答題】下圖的格中，b的補(bǔ)元是_________，c的補(bǔ)元是______________。

答案：a,cb,d

解析：由圖可見(jiàn)該格L為有界格，1為其全上界，0為其全下界。如果<L,∧,∨,0,1>是有

界格,a∈L,若存在b∈L,使得a∧b=0和a∨b=1成立,則稱b是a的補(bǔ)元。按照以上定

義，我們可以看到b的補(bǔ)元是a,c；c的補(bǔ)元是b,d。

25、【問(wèn)答題】設(shè)二元關(guān)系A(chǔ)={<2,5>,<3,5>,<3,4>}，B={<1,3>,<2,5>,<

3,4>}，那么dom（A∩B）=_______，ran（A∪B）=________。

答案：{2,3}，{3,4,5}

解析：先計(jì)算出A∩B={<2,5>,<3,4>}，A∪B={<2,5>,<3,5>,<3,4>,<1,3>}，

然后再求定義域dom(A∩B)={2,3}，值域ran(A∪B)={3,4,5}。

26、【問(wèn)答題】研究4階完全圖K4，判斷其是否存在歐拉回路？是否存在哈密頓回路？如果

存在，共有多少個(gè)非同構(gòu)的回路？

答案：對(duì)與4階完全圖K<>4，每個(gè)結(jié)點(diǎn)的度數(shù)均為3，為奇數(shù)，因而不存在歐拉回路。4

階完全圖K_4中存在哈密頓回路。而且存在3個(gè)不同構(gòu)的哈密頓回路。

解析：完全圖是一個(gè)簡(jiǎn)單的無(wú)向圖，其中每對(duì)不同的結(jié)點(diǎn)之間都恰連有一條邊相連。4階

恰有4個(gè)結(jié)點(diǎn)。一個(gè)無(wú)向圖存在歐拉回路，當(dāng)且僅當(dāng)該圖所有頂點(diǎn)度數(shù)都為偶數(shù),且該圖

是連通圖。從圖中的任意一點(diǎn)出發(fā)，路途中經(jīng)過(guò)圖中每一個(gè)結(jié)點(diǎn)當(dāng)且僅當(dāng)一次，則成為哈

密頓回路。根據(jù)以上歐拉回路與哈密頓回路的定義與性質(zhì)，則可以判斷出解的結(jié)論。

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

答案：

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

28、【問(wèn)答題】給出集合A={1,2,3}上所有等價(jià)關(guān)系的個(gè)數(shù)，并列出這些關(guān)系的集合表達(dá)

式。

答案：

解析：在集合A上建立的二元關(guān)系符合自反的、對(duì)稱的、傳遞的，此關(guān)系是等價(jià)的。顯然

恒等關(guān)系I<>A滿足以上要求。再根據(jù)自反、對(duì)稱和傳遞要求，我們可以得出其他組合，

這個(gè)組合與恒等關(guān)系I<>A取并集，即得到結(jié)論。

29、【問(wèn)答題】求命題公式?（P∨（Q∧R））的主析取范式和主合取范式

答案：

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

式，最后要把主析取范式轉(zhuǎn)換成極小項(xiàng)形式。主合取范式可以借助極小項(xiàng)與極大項(xiàng)關(guān)系來(lái)

確定

30、【問(wèn)答題】集合A={a,b,c,d,e}上有偏序關(guān)系R={<a,d>,<a,c>,<a,b>,<a,e>,<

b,e>,<c,e>,<d,e>}∪IA（1）畫(huà)出偏序集<A,R>的哈斯圖；（2）找出A的極大元、

極小元、最大元和最小元。

答案：

解析：按照哈斯圖的作圖規(guī)則：（1）以“圓圈”表示元素；（2）若x≤y,則y畫(huà)在x的

上層；（3）若y覆蓋x,則連線；（4）不可比的元素可畫(huà)在同一層。即可做出哈斯圖。再

根據(jù)極大元、極小元、最大元和最小元的定義就可以得出結(jié)論。

31、【問(wèn)答題】設(shè)Z是整數(shù)集合，在Z上定義二元運(yùn)算*如下：?x,y∈Z,x*y=x+y-2證明Z

關(guān)于運(yùn)算*構(gòu)成群。

答案：證明：?x,y∈Z,x*y=x+y-2∈Z，因而*運(yùn)算是封閉的。顯然，*運(yùn)算可結(jié)合，且單

位元e=2。?a∈Z,由（a*a<>-1）=a+a<>-1-2=e=2可得a<>-1=4-a即任一元素均存在逆

元。綜上，Z關(guān)于運(yùn)算*構(gòu)成群。

解析：判斷某集合和運(yùn)算能不能構(gòu)成群，主要是根據(jù)群的定義研究其封閉性、可結(jié)合性、

單位元、逆元，都滿足要求即是群。

32、【問(wèn)答題】設(shè)集合A={<a,b>|a,b為正整數(shù)}，在A上定義二元關(guān)系~如下：<a,b>~<c,d>

當(dāng)且僅當(dāng)a+d=b+c。證明~是一個(gè)等價(jià)關(guān)系。

答案：證明：（1）自反性對(duì)?<a,b>∈A，有a+b=a+b，所以<a,b>~<a,b>。故~具有自反

性。（2）對(duì)稱性設(shè)<a,b>~<c,d>，則有a+d=b+c，亦即c+b=d+a，所以<c,d>~<a,b>。故~

具有對(duì)稱性。（3）傳遞性設(shè)<a,b>~<c,d>且<c,d>~<e,f>，則有a+d=b+c，c+f=e+d，上述

兩式兩邊分別相加后消去c+d，從而a+f=b+e。所以<a,b>~<e,f>。故~具有傳遞性。綜合

（1）（2）（3），~是一個(gè)等價(jià)關(guān)系。

解析：證明二元關(guān)系中的等價(jià)關(guān)系，主要是從定義出發(fā)，滿足自反性、對(duì)稱性和傳遞性。

33、【問(wèn)答題】在9階無(wú)向圖G中，每個(gè)結(jié)點(diǎn)的度數(shù)不是5就是6，證明G中至少有5個(gè)6

度結(jié)點(diǎn)或至少有6個(gè)5度結(jié)點(diǎn)。

答案：證明：（1）假設(shè)G中至少有5個(gè)6度結(jié)點(diǎn)，則結(jié)論成立。（2）如果G中至多只

有4個(gè)6度結(jié)點(diǎn)，由于每個(gè)結(jié)點(diǎn)的度數(shù)不是5就是6，則至少有5個(gè)度數(shù)為5的結(jié)點(diǎn)，而

奇度數(shù)結(jié)點(diǎn)不能為奇數(shù)個(gè)，因而這時(shí)G中度數(shù)為5的結(jié)點(diǎn)應(yīng)當(dāng)有6個(gè)或者8個(gè)，即至少有

6個(gè)5度結(jié)點(diǎn)。綜合（