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

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

一、選擇題（2*10）

[■令P：今天下雨了,

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

帶傘”可符號化為（）。

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

(C)PAQ(D)PA^Q

2.下列命題公式為永真蘊含式的是（）。

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

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

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

的”的否定是（）。

（A）所有人都不是大學生，有些人不會死

（B）所有人不都是大學生，所有人都不會死

（C）存在一些人不是大學生，有些人不會死

（D）所有人都不是大學生，所有人都不會死

■永真式的否定是（）。

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

5、以下選項中正確的是（）o

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

6、以下哪個不是集合A上的等價關系的性質？（）

（A）自反性（B）有限性（C）對稱性（D）傳遞性

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

（A）自反的（B）對稱的

（C）傳遞的，對稱的（D）傳遞的

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

是（）。

（A）強連通圖（B）單向連通圖

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

9、具有6個頂點，12條邊的連通簡單平面圖中，每個面都是由（）條邊

圍成?

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

10.連通圖G是一棵樹，當且僅當G中()o

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

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

二'填空題(2*10)

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

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

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

號化表示為o

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

5、設AAB=Anc,NnB=Anc,則BCo

A={2,4,6},A上的二元運算*定義為:a*b=max{a,b},則在獨異點＜A,*＞中,

單位元是，零元是0

7、任一有向圖中，度數(shù)為奇數(shù)的結點有(奇數(shù)/偶數(shù))個。

8.如下無向圖割點是，割邊是。

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

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

3個條件，有幾種派法？如何派？

⑴若A去，則C和D中要去1個人；

（2）B和C不能都去;

⑶若C去，則D留下

五、（15分）設A={1,2,3},寫出下列圖示關系的關系矩陣，并討論它們的性質:

六、（20分）畫一個圖使它分別滿足：

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

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

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

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

答案：

一、選擇題：

1、D2、C3、A4、B5、D

6、B7、B8、C9、C10、B

二、填空：

1、2不是偶數(shù)且-3不是負數(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

四、解設4:4去工作；B-.8去工作；O.C去工作；D;“去工作。則根據

題意應有：A-^C?D,TB/\Q,八「。必須同時成立。因此

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;它是反自反的、反對稱的、傳遞的;

R[100J

/011、

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

RLioj

對稱的；

‘011、

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

〔。oJ

也不是對稱的、反對稱的、傳遞的。

~7\、

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

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

的備選項中只有一項是最符合題目要求的，請將其選出。

1.令P：他怕困難,q：他戰(zhàn)勝困難,命題〃他戰(zhàn)勝困難是因為他不怕困難〃的符

號化形式為

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

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

題“沒有完全相同的蘋果”的符號化形式為

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.一顆樹有2個4度結點，3個3度結點，其余為樹葉，則該樹中樹葉個數(shù)是

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

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

<b,a>},則A是

A.自反的B.對稱的

C.反對稱的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.表示集合之間關系的圖是

A.文氏圖B.哈斯圖C.歐拉圖D.樹

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

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

9.設T是n階樹(nN2),則T下耳凈的性質是

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

C.有n-1條邊D.至少有兩片樹葉

10.設R、S均為集合A上的二元關系，下面命題正確的是

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

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

C若R與S是對稱的，則R。S也是對稱的

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

11.以下關于圖的矩陣的描述，正確的是

A.鄰接矩陣即關系矩陣B.可達矩陣是針對無向圖的

C?無向圖有鄰接矩陣D.可達矩陣是針對有向圖的

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

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

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

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

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

14.一個6階圖,其各結點度數(shù)之和不可整為

A.10B.12a15D.20

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

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

非選擇題部分

注意事項：

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

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

16.設E={a,b]是字母表，￡?表示由工上的字符構成的有限長度的申的集合(包含長

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

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

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

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

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

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

位元是零元是O

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

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

彩珠分布的手鐲。

20.某連通平面圖有6個頂點，其平面表示中共有8個面，則其邊有條。

21.設布"集合A=[a,b,c,d}上的二元關系R={<a,b>,<b,a>,<c,c>,<d,d>|,

則R2=,R3=e

22.為了從無向完全圖5中得到其生成樹,至少需要刪除條邊。

23.設有集合A=|a,b,c|上的二元關系RI=|<a,b>,<a,c>,<c,b>},則R1的

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

24.一個無向圖有21條邊，有3個4度結點，其余結點均為3度，則其結點共有

__________個。

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

IP(A)xBI=o

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

26.用列真值表的方法說明下列邏輯等價式成立

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

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