《離散數(shù)學(xué)》考試題庫(kù)及答案一

《離散數(shù)學(xué)》考試題庫(kù)及答案

一、選擇題（2*10）

[■令P：今天下雨了,

Q：我沒(méi)帶傘，則命題“雖然今天下雨了，但是我沒(méi)

帶傘”可符號(hào)化為（）。

(A)P-「Q(B)PV^Q

(C)PAQ(D)PA^Q

2.下列命題公式為永真蘊(yùn)含式的是（）。

(A)Q—(PAQ)(B)P—(PAQ)

(C)(PAQ)-P(D)(PVQ)-Q

3、命題“存在一些人是大學(xué)生”的否定是（A）,而命題“所有的人都是要死

的”的否定是（）。

（A）所有人都不是大學(xué)生，有些人不會(huì)死

（B）所有人不都是大學(xué)生，所有人都不會(huì)死

（C）存在一些人不是大學(xué)生，有些人不會(huì)死

（D）所有人都不是大學(xué)生，所有人都不會(huì)死

■永真式的否定是（）。

（A）永真式（B）永假式（C）可滿足式（D）以上均有可能

5、以下選項(xiàng)中正確的是（）o

（A）0=0（B）070（C）OG0（D）0莊0

6、以下哪個(gè)不是集合A上的等價(jià)關(guān)系的性質(zhì)？（）

（A）自反性（B）有限性（C）對(duì)稱性（D）傳遞性

■集合A={l,2,...,10}上的關(guān)系R={<x,y>|x+y=10,x,y￡A},則R的性質(zhì)為（）。

（A）自反的（B）對(duì)稱的

（C）傳遞的，對(duì)稱的（D）傳遞的

■設(shè)D=<V,E>為有向圖，V={a,b,c,d,e,f},E={<a,b>,<b,c>,<a,d>,<d,e>,<f,e>}

是（）。

（A）強(qiáng)連通圖（B）單向連通圖

（C）弱連通圖（D）不連通圖

9、具有6個(gè)頂點(diǎn)，12條邊的連通簡(jiǎn)單平面圖中，每個(gè)面都是由（）條邊

圍成?

(A)2(B)4(C)3(D)5

10.連通圖G是一棵樹(shù)，當(dāng)且僅當(dāng)G中()o

(A)有些邊不是割邊(B)每條邊都是割邊

(C)無(wú)割邊集(D)每條邊都不是割邊

二'填空題(2*10)

1、命題“2是偶數(shù)或-3是負(fù)數(shù)”的否定是。

■設(shè)全體域D是正整數(shù)集合，則命題VxR(xy=y)的真值是。

3、令R(x):x是實(shí)數(shù)，Q(x):x是有理數(shù)。則命題”并非每個(gè)實(shí)數(shù)都是有理數(shù)”的符

號(hào)化表示為o

4、公式(「PAQ)v(「PArQ)化簡(jiǎn)為o

5、設(shè)AAB=Anc,NnB=Anc,則BCo

A={2,4,6},A上的二元運(yùn)算*定義為:a*b=max{a,b},則在獨(dú)異點(diǎn)＜A,*＞中,

單位元是，零元是0

7、任一有向圖中，度數(shù)為奇數(shù)的結(jié)點(diǎn)有(奇數(shù)/偶數(shù))個(gè)。

8.如下無(wú)向圖割點(diǎn)是，割邊是。

三、(10分)設(shè)A、8和C是三個(gè)集合，貝”AuBnTBE)。

o四、（15分）某項(xiàng)工作需要派A、B、C和D4個(gè)人中的2個(gè)人去完成，按下面

3個(gè)條件，有幾種派法？如何派？

⑴若A去，則C和D中要去1個(gè)人；

（2）B和C不能都去;

⑶若C去，則D留下

五、（15分）設(shè)A={1,2,3},寫(xiě)出下列圖示關(guān)系的關(guān)系矩陣，并討論它們的性質(zhì):

六、（20分）畫(huà)一個(gè)圖使它分別滿足：

（1）有歐拉回路和哈密爾頓回路；

（2）有歐拉回路，但無(wú)條哈密爾頓回路;

（3）無(wú)歐拉回路，但有哈密爾頓回路；

（4）既無(wú)歐拉回路，又無(wú)哈密爾頓回路。

答案：

一、選擇題：

1、D2、C3、A4、B5、D

6、B7、B8、C9、C10、B

二、填空：

1、2不是偶數(shù)且-3不是負(fù)數(shù)

2、F

3、「Vx(R(x)-Q(x))

4、

5、等于

6、2,6

7、偶數(shù)

8、d,e5

三、證明：

Vx(x€4fxeB)AB/\x史4)=Vx(x史4Vx￡B)A3^r(x€B/\x^A)

<=>—i3x(x€AAB)A—iVKxgSVxC4)n—imKxCAAx^,B)V—i\/x(xEAVx^B)

=—i(3x(xCA/\x年B)NVx(x€AVx七功igMxCAAB)AVA(X€B~^X￡4))

—l(-Sty4)o

四、解設(shè)4:4去工作；B-.8去工作；O.C去工作；D;“去工作。則根據(jù)

題意應(yīng)有：A-^C?D,TB/\Q,八「。必須同時(shí)成立。因此

A」(8入QA

=(「4V(CA「。V(「。八。)A(「8V」0A(「CV

V(CA「。V(「。入。)八((「8人」0V(「8AV「CV(「CN」0

<=>(—iAA—18A—\C)V(~A—18A—\D)V(~i/A—?C)V(~i^4A—?C/\—\D)

V(CA—?Dl\―\BN―?C)V(CA—?D!\―18A―iZT)V(CA―?Dt\―\C)V(CA—?D/\

—?C/\—\D)

NrCNDJBJQNCCNDJBJD)NJCNDJQNCCNDJC

入「o

=FVFVJ4A「QVFVFV(CA「。八」乃)VFVFV(「CA。入」歹)VFV

(「CA。VF

=(-4人「QV八C"D)N(「CADN「B)V(」CA。

入VJBNCA「。V(」CAD)

oT

故有三種派法：BND,ANC,AND。

五、

"000、

(1)R={<2,1>,<3,1>,<2,3>};M=101;它是反自反的、反對(duì)稱的、傳遞的;

R[100J

/011、

(2)R={<1,2>,<2,1>,<1,3>,<3,1>,<2,3>,<3,2>};M=101;它是反自反的、

RLioj

對(duì)稱的；

‘011、

(3)R={<1,2>,<2,1>,<1,3>,<3,3>};MR=100;它既不是自反的、反自反的、

〔。oJ

也不是對(duì)稱的、反對(duì)稱的、傳遞的。

~7\、

《離散數(shù)學(xué)》考試題庫(kù)及答案

一、單項(xiàng)選擇題：本大題共15小題，每小題1分，共15分，在每小題列出

的備選項(xiàng)中只有一項(xiàng)是最符合題目要求的，請(qǐng)將其選出。

1.令P：他怕困難,q：他戰(zhàn)勝困難,命題〃他戰(zhàn)勝困難是因?yàn)樗慌吕щy〃的符

號(hào)化形式為

A.p—?qB.q—?pC.pAqD.pVq

2.令F(x)：x為蘋(píng)果，H(x,y)：x與y完全相同，L(x,y):x=y,則命

題“沒(méi)有完全相同的蘋(píng)果”的符號(hào)化形式為

Ar3x3y(F(x)AF(y)AL(x,y)-H(x,y))

B.r3x3y(F(x)AF(y)A-L(x,y)AH(x,y))

Cr3x3y(F(x)AF(y)ArL-H(x,y))

D.VxVy(F(x)AF(y)ArL(x,y)ArH(x,y))

3.一顆樹(shù)有2個(gè)4度結(jié)點(diǎn)，3個(gè)3度結(jié)點(diǎn)，其余為樹(shù)葉，則該樹(shù)中樹(shù)葉個(gè)數(shù)是

A.7B.8C.9D.10

4.設(shè)集合A={a,b,c,d},現(xiàn)有A上的二元關(guān)系R={<a,b>,<b,c>,<c,b>,

<b,a>},則A是

A.自反的B.對(duì)稱的

C.反對(duì)稱的D.傳遞的

5.下圖中為歐拉圖的是

6.下列謂詞公式中，不是前束范式的為

A.VxVy(A(x)4B(y))

B.Vx3y(A(x)AB(y))

CVx3y(A(x)AB(y)-C(z))

D.Vx3y(A(x)AB(y)—>3zC(z))

7.表示集合之間關(guān)系的圖是

A.文氏圖B.哈斯圖C.歐拉圖D.樹(shù)

8.無(wú)向完全圖A的邊的條數(shù)為

A.10B.15C.20D.30

9.設(shè)T是n階樹(shù)(nN2),則T下耳凈的性質(zhì)是

A.連通圖???B.哈密頓圖

C.有n-1條邊D.至少有兩片樹(shù)葉

10.設(shè)R、S均為集合A上的二元關(guān)系，下面命題正確的是

A.若R與S是自反的，則R?S也是自反的

B.若R與S是反自反的，則R?S也是反自反的

C若R與S是對(duì)稱的，則R。S也是對(duì)稱的

D.若R與S是傳遞的，則R。S也是傳遞的

11.以下關(guān)于圖的矩陣的描述，正確的是

A.鄰接矩陣即關(guān)系矩陣B.可達(dá)矩陣是針對(duì)無(wú)向圖的

C?無(wú)向圖有鄰接矩陣D.可達(dá)矩陣是針對(duì)有向圖的

12.一個(gè)6階連通圖的邊數(shù)至少為

A.4B.5C.6D.7

13.下列關(guān)于反函數(shù)的命題，正確的是

A.單射函數(shù)有反函數(shù)B.任意函數(shù)均有反函數(shù)

C.滿射函數(shù)有反函數(shù)D.雙射函數(shù)有反函數(shù)

14.一個(gè)6階圖,其各結(jié)點(diǎn)度數(shù)之和不可整為

A.10B.12a15D.20

15.在整數(shù)集合Z上定義*運(yùn)算如下：江也€2述*卜=&+1)-10,則代數(shù)系統(tǒng)<2,*>是

A.格B.環(huán)C.域D.群

非選擇題部分

注意事項(xiàng)：

用黑色字跡的簽字筆或鋼筆將答案寫(xiě)在答題紙上，不能答在試題卷上。

二、填空題：本大題共10小題，每小題2分，共20分。

16.設(shè)E={a,b]是字母表，￡?表示由工上的字符構(gòu)成的有限長(zhǎng)度的申的集合(包含長(zhǎng)

度為0的串，即空串在內(nèi))，A=|a,bvaa,bb,aaa,bbb|,B={colcoG￡'A,

C=|(i)l(De￡*AI<i)l^2],貝ijA-(BCC)=o

浙02324#離散數(shù)學(xué)試題第2頁(yè)(共4頁(yè))

17.在整數(shù)域中，命題公式Vxmy(x?y=0)的真值為，命題公式

3xVy(x-y=D的真值為。

18.設(shè)A為非空有限集合,P(A)為A的再集，U為集合的并運(yùn)算，群<P(A),U>中，單

位元是零元是O

19.一個(gè)手錫等距離地鑲嵌著5顆彩珠，每顆彩珠可以從紅、白、藍(lán)、綠、黃5種顏色中挑

選。如果要求手銀匕的彩珠顏色都不相同,則可以構(gòu)成種不同顏色

彩珠分布的手鐲。

20.某連通平面圖有6個(gè)頂點(diǎn)，其平面表示中共有8個(gè)面，則其邊有條。

21.設(shè)布"集合A=[a,b,c,d}上的二元關(guān)系R={<a,b>,<b,a>,<c,c>,<d,d>|,

則R2=,R3=e

22.為了從無(wú)向完全圖5中得到其生成樹(shù),至少需要?jiǎng)h除條邊。

23.設(shè)有集合A=|a,b,c|上的二元關(guān)系RI=|<a,b>,<a,c>,<c,b>},則R1的

自反閉包r(RI)=R1的對(duì)稱閉包s(Rl)=o

24.一個(gè)無(wú)向圖有21條邊，有3個(gè)4度結(jié)點(diǎn)，其余結(jié)點(diǎn)均為3度，則其結(jié)點(diǎn)共有

__________個(gè)。

25.設(shè)集合A=[1,2,3|,集合8=|a,，<;,<1,“，則1人*81=而

IP(A)xBI=o

三、計(jì)算題：本大題共5小題，每小題6分，共30分。

26.用列真值表的方法說(shuō)明下列邏輯等價(jià)式成立

(P-(Q-P))o(rP-(Q-rP))o

27.用等值演算法推導(dǎo)命題公式(PTQAR)八5P-(rQArR))的主析