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

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

項是最符合題目要求的，請將其選出。

1.令P：他怕困難,q：他戰(zhàn)勝困難,命題''他戰(zhàn)勝困難是因為他不怕困難”的符號化形式為

A.rp—B.rq-*pQpAqD.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-1L(x,y)AH(x,y))

C.r3x3y(F(x)AF(y)A-1L(x,y)-?H(x,y))

D.VxVy(F(x)AF(y)ArL(x,y)A-H(x,y))

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

C.Vx3y(A(x)AB(y)-C(z))

D.Vx3y(A(x)AB(y)-3xC(?))

7.表示集合之間關系的圖是

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

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

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

9.設T是n階樹(n\2),則T不分有的性質(zhì)是

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

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

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

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

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

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

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

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

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階圖,其各結(jié)點度數(shù)之和不可型為

A.10B.12Q15D.20

15.在整數(shù)集合Z上定義*運算如下：a、beZ,a*b=a+b-10,則代數(shù)系統(tǒng)<Z,*>是

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

非選擇題部分

注意事項：

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

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

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

度為。的串，即空串在內(nèi))，A=|a,b,aa,bb,aaa,bbb|,B=|<olCDG￡*AIcol^2|,

C={<i)l(oeE*AIu)lw2},則A-(BCC)=o

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

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

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

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>|,

2J

則R=,R=o

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

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

自反閉包r(Rl)=,R1的對稱閉包s(Rl)=?

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

__________個。

25.設集合A=|l,2,3|,集合B={a,b,c,d,e|,則IAXBI=而

IP(A)xBI=.

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

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

(PT(Q-P))=(rP-(Q-rP))o

27.用等值演算法推導命題公式(PTQAR)八(rp-(rQArR))的主析取范式。

28.設解釋I為:個體域D=|a,b|,F(x)與G(x)為2個一元謂詞，且F(a)=O,F(b)=

l,G(a)=l,G(b)=0o在I下，求命題公式Vx(F(x)-G(x))的真值。

29.設集合，題29圖為S上的二元關系R的關系圖

題29圖

(1)寫出R的集合表達式;(2)寫出R的關系矩陣。

30.求下述集合等式成立的充要條件，并證明結(jié)論

(A-C)UB=AUB

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

四、證明題：本大題共3小題，每小題7分，共21分。

31.設n階無向簡單圖G=<V,E>,其中邊數(shù)滿足：

IEI>(n-l)(n-2)/2

證明C是連通圖。

32.證明下列謂詞公式為永真式：

Vy(A(y)-*3xA(x))(>

33.設a、b、c均為奇數(shù)，證明一元二次方程

ax2+bx+c=0

無有理數(shù)根。

五、綜合應用跑：本大題共2小題，每小題7分，共14分。

34.無向樹T有8片樹葉,2個3度分支點,其余的分支點都是4度，求T的階數(shù)，并畫出

全部非同構的這種樹。

35.設<A,I>為偏序關系，其中I為整除關系，即a山當且僅當a整除b。已知A={1,

2,3,5,6,15,301。畫出這個偏序關系的哈斯圖，并判斷其是否為格。

離散數(shù)學試題帶答案

一、填空題

1設集合AB,其中A={1.2.3}.B=fl.2},則A-B=⑶；p(A)-p(B)=舊}<1,3}<2,3}<123。.

2.設有限集合A,|A|=n,則|p(AxA)|=_2n"___.

3.設集合A={a,b},B={1,2},則從A到B的所有映射是a尸az=(42)}。3=a>=

但111「其中雙射的是ag.

4.已知命題公式G=「(P'Q)八R,則G的主析取范式是(PArQAR)

5.設G是完全二叉樹，G有7個點，其中4個葉點，則G的總度數(shù)為12,分枝點數(shù)為3.

6設A、B為兩個集合,A={1,2,4},B={3,4},則從AcB={4};AuB^(l,2,3,41;

A~B={1,2}.

7.設R是集合A上的等價關系，則R所具有的關系的三個特性是自反性，對稱性

傳遞性.

8.設命題公式G=TP->(QAR))，則使公式G為真的解釋有(1,0,0),(1,0,1),(1,1,0)

設集合上的關系則RI*R=

9.A={1,2,3,4},ARi={(1,4),(2,3),(3,2)},R2={(2,1),(3,2),(4,3)},2

{(1,3),(2,2),(3,1)},R2?RI={(2,43(33,(4,2)}RP={(2,21(3,3).

10.設有限集A,B,|A|=m,|B|=n,則||p(AxB)|=_2"'x".

11設A,B,R是三個集合，其中R是實數(shù)集，A={x|-lWxWl,xeR},B={x|OWx<2,xeR},則A-B=-l<=x<0,B-A

={x|1<xv2,XER},

AOB={xIxwR},.

13.設集合人={2,3,4,5,6},R是A上的整除關系，則R以集合形式(列舉法)記為

{(2,2),(2,4),(2,6),(3,3),(3,6),(4,4),(5,5),(6,6))

14.設一階邏輯公式6=\^^儀)-王(1僅)，則G的前束范式是mx(「P(x)VQ(x)).

15.設G是具有8個頂點的樹，則G中增加條邊才能把G變成完全圖。(完全圖的邊數(shù)妁土D,樹的邊數(shù)

2

為n-1)

16.設謂詞的定義域為{a,b},將表達式VxR(x)-mxS(x)中量詞消除，寫成與之對應的命題公式是.(R(a)AR(b))一

(S(a)VS(b)).

17.設集合A={1,2,3,4},A上的二元關系R={(1,1),(1,2),(2,3)},S={(1,3),(2,3),(3,2)}。則RS={(1,3),(2,2)},

R2={(1,1),(L2),(1,3)}.

二、選擇題

1設集合A={2,{a},3,4},B={{a},3,4,l},E為全集，則下列命題正確的是(C)。

(A){2}eA(B){a}cA(C)0c{{a}}cBcE(D){{a},l,3,4}cB.

2設集合A={1,2,3},A上的關系R={(1,1),(2,2),(2,3),(3,2),(3,3)},則R不具備(D).

(A)自反性(B)傳遞性(C)對稱性(D)反對稱性

3設半序集(A,W)關系W的哈斯圖如下所示，若A的子集B={2,3,4,5},則元素6為8的(B)?

(A)下界(B)上界(C)最小上界(D)以上答案都不對

4下列語句中，(B)是命題。

(A)請把門關上(B)地球外的星球上也有人

(C)x+5>6(D)下午有會嗎？

、幾口，十wa,,,P(a,a)P(a,b)P(b,a)P(b,b)

5設I是如下一個解6釋：D=a,b,''-~~

1010

則在解釋I下取真值為1的公式是(D).

(A)3xVyP(x,y)(B)VxVyP(x,y)(C)VxP(x,x)(D)Vx3yP(x,y).

6,若供選擇答案中的數(shù)值表示一個簡單圖中各個頂點的度，能畫出圖的是(C).

(A)(l,2,2,3,4,5)(B)(l,2,3,4,5,5)(C)(l,l,l,2,3)(D)(2,3,3,4,5,6).

7.設G、H是一階邏輯公式，P是一個謂詞，G=mxP(x),H=VxP(x),則一階邏輯公式GfH是(C).

(A)恒真的(B)恒假的(C)可滿足的(D)前束范式.

8設命題公式G=「(PfQ),H=P->(Qf「P),則G與H的關系是(A)。

(A)GnH(B)HnG(C)G=H(D)以上都不是.

9設A,B為集合，當(D附A—B=B.

(A)A=B(B)AcB(C)BcA(D)A=B=0.

10設集合A={1,234},A上的關系R={(1」),(2,3),(2,4),(3,4)},則R具有(B)。

(A)自反性(B)傳遞性(C)對稱性(D)以上答案都不對

11下列關于集合的表示中正確的為(B)o

(A){a}G{azb,c}(B){a}q{a,b,c}(C)0G{a,b,c}(D){a,b}w{a,b,c}

12命題VxG(x)取真值1的充分必要條件是(A).

(A)對任意x,G(x)都取真值1.(B)有一個xo,使G(xo)取真值1.

(Q有某些X,使G(x0)取真值L(D)以上答案都不對.

13.設G是連通平面圖，有5個頂點，6個面，則G的邊數(shù)是(A).

(A)9條(B)5條(C)6條(D)ll條.

14.設G是5個頂點的完全圖，則從G中刪去(A)條邊可以得到樹.

(A)6(B)5(C)10(D)4.

01111

10100

15.設圖G的相鄰矩陣為則G的頂點數(shù)與邊數(shù)分別為(D).

11011

10101

10110

(A)4,5(B)5,6(C)4,10(D)5,8.

三、計算證明題

1.設集合A={1,2,3,4,6,8,9,12},R為整除關系。

(1)畫出半序集(A,R)的哈斯圖；

(2)寫出A的子集B={3,6,9,12}的上界，下界，最小上界，最大下界;

(3)寫出A的最大元，最小元，極大元，極小元。

解：⑴

(2)B無上界，也無最小上界。下界1,3;最大下界是3

(3)A無最大元，最小元是1,極大元8,12,9;極小元是1

2.設集合A={1,2,3,4},A上的關系R={(x,y)|x,yeA且x>y},求

(1)畫出R的關系圖；

(2)寫出R的關系矩陣.

1000'

1100

(2)MR=

R1110

1111

3.設R是實數(shù)集合，是R上的三個映射，CT(X)=x+3,T(X)=2x,<p(x)=x/4,試求復合映射a?a,o?(p,<p?T,

解：

(1)O*T=C(T(X))=T(X)+3=2X+3=2X+3.

(2)o?o=<J(O(X))=CT(X)+3=(x+3)+3=x+6/

(3)a?(p=c((p(x))=(p(x)+3=xA+3,

(4)(P?T=(P(T(X))=T(X)A—2x/^l=x/2,

(5)o?(p”=5((p?T)=(p2+3=2x/U3=x/2+3.

A4.設I是如下一個解釋：D={2,3},

ab/(2)/⑶P(2,2)P(2,3)P(3,2)P(3,3)

32320011

試求(1)P(a,f(a))/\P(b,f(b));

(2)Vx3yP(y,x).

解:

(1)P(a,f(a))^P(b,f(b))=P(3,/(3))AP(2,7(2))

=P(3,2)AP(2,3)

=1AO

=0.

(2)Vx3yP(y,x)=Vx(P(2,x)VP(3,x))

=(P(2,2)VP(3,2))A(P(2,3)VP(3,3))

=(0Vl)A(0Vl)

=1A1

=1.

5.設集合A={1,2,4,6,8,12},R為A上整除關系。

(1)畫出半序集(A,R)的哈斯圖；

(2)寫出A的最大元，最小元，極大元，極小元；

(3)寫出A的子集B={4,6,8,12}的上界，下界，最小上界，最大下界.

解：⑴(2)無最大元，最小元1,極大元8,12;極小元是1.

(3)B無上界，無最小上界。下界1,2;最大下界2.

6.設命題公式G=「(pfQ)V(QAjpfR)),求G的主析取范式。

解：

G=-.(P-Q)V(QA(-.P-R))

=-.(-1PVQ)V(QA(PVR))

=(PA-.Q)V(QA(PVR))

=(PA-.Q)V(QAP)V(QAR)

=(PA-iQAR)V(PA-1QA-1R)V(PAQAR)V(PAQA-1R)V(PAQAR)V(-1PAQAR)

=(PA-.QAR)V(PA^QA-.R)V(PAQAR)V(PAQA-nR)V(-iPAQAR)

=m3vm4Vm5Vm6Vm7=S(3,4,5,6,7).

7.(9分)設一階邏輯公式：G=(VxP(x)V3yQ(j/))-Vx/?(x),把G化成前束范式.

解:

G=(VxP(x)V3yQ(y))->Vx/?(x)

=—1(VxP(x)V3yQ(y))VVx/?(x)

=(-1VxP(x)A->3yQ(y))VVxR(x)

=(3x-.P(x)AVy-1Q(y))VVzR(z)

=3xVyVz((-iP(x)A-iQ(y))VR(z))

9,設R是集合A={a,b,c,d}.R是A上的二元關系,R={(a,b),(b,a),(b,c),(c,d)},

(1)求出r(R),s(R),t⑻;

(2)畫出r(R),s(R),t(R)的關系圖.

解：(1)

r(R)=RUlA={(a,b),(b,a),(b,c),(c,d),(a,a),(b,b),(c,c),(d,d)},

s(R)=RURr={(a,b),(b,a),(b,c),(c,b)(c,d),(d,c)},

t(R)=RUR2UR3UR4={(a,a),(a,b),(a,c),(a,d),(b,a),(b,b),(b,c),(b,d),(c,d)}；

(2)關系圖：

r(R)s(R)t(R)

11.通過求主析取范式判斷下列命題公式是否等價：

(1)G=(PAQ)VHPAQAR)

(2)H=(PV(QAR))A(QV(-.PAR))

解：

G=(PAQ)V(-1PAQAR)

=(PAQA-.R)V(PAQAR)V(^PAQAR)

=m6Vm7Vm3

=E(3,6,7)

H=(PV(QAR))A(QV<-.PAR))

=(PAQ)V(QAR))V(-.PAQAR)

=(PAQA-.R)V(PAQAR>V(^PAQAR)V(PAQAR)VHPAQAR)

=(PAQA-iR)VHPAQAR)V(PAQAR)

=m6Vm3Vm7

G,H的主析取范式相同，所以G=H.

13.設R和S是集合A={a,b,c,d}上的關系，其中R={(a,a),(a,c),(b,c),(c,d)},S={(a,b),{b,c),(b,d),(d,d)}.

(1)試寫出R和5的關系矩陣；

(2)計算R?S,RU5,R，5-i?Ri.

解：

'1010''0100'

00100011

⑴MR=M,=

0001J0000

00000001

(2)R?S={(a,b),(c,d)},

RUS={(a,a),(a,b),(a,c),(b,c),(b,d),(c,d),(d,d)},

Ri={(a,a),(c,a),(c,b),(d,c)},

5r?限】={(b,a),(d,c)}.

四、證明題

1.利用形式演繹法證明：｛PfQ,Rf$PVR｝蘊涵QV5。

解：

(1)PV/?P

⑵—CUI)

⑶pfQP

⑷「RfQQ⑵⑶

⑸「QfRQ⑷

(6)Rf5P

(7)「Qf5Q⑸⑹

(8)QVSQ⑺

2.設A,B為任意集合，證明：(A-B)-C=A-(BUC).

解：(A-B)-C=(An歷ne

=An(Bnc)

=ACI(BUC)

=A-(BUC)

3.(本題10分)利用形式演繹法證明：{「AVB,-.Cf-,B,C—D}蘊涵A-Do

解：

⑴AD(附加)

(2)-.AVBP

⑶BQ⑴⑵

(4)-,C-->BP

⑸BfCQ⑷

(6)CQ⑶⑸

⑺C-Dp

⑻DQ⑹⑺

(9)AfDD(D(8)

所以JAVB,CfD｝蘊涵A—D.

4.(本題10分)A,B為兩個任意集合，求證：

A-(AnB)=(AUB)-B.

解：

4.A-(AAB)

=An~(AClB)

=AC(~AU~B)

=(An-A)u(An-B)

=0U(AC~B)

=(AA~B)

=A-B

而(AUB)-B

=(AUB)A-B

=(ACl-B)U(Bn-B)

=(An-B)U0

=A—B

所以：A-(AAB)=(AUB)-B.

參考答案

一、填空題

1.{3};{{3},{1,3},{2,3},{1,2,3}}.

2.2M.

3.ai={(o,l),a2={(a,2),(b,2)},a3={(a,l),(b,2)},a4={(a,2),(b,l)};a3,a4.

4.(PA^QAR).

5.12,3.

6.{4},{1,2,3,4},{1,2}.

7.自反性；對稱性；傳遞性.

8.(1,0,0),(1,0,1),(1,1,0).

9.{(1,3),(2,2),(3,1)};{(2,4),(3,3),(4,2)};{(2,2),(3,3)}.

10.2mxn.

11.{x|-lWx<0,xeR};{x|1<x<2,xeR};{x|OWxWl,xeR}.

12.12;6.

13.{(2,2),(2,4),(2,6),(3,3),(3,6),(4,4),(5,5),(6,6)}.

14.3x(-.P(x)VQ(x)).

15.21.

16.(R(a)AR(b)H(S(a)VS(b)).

17.{(1,3),(2,2)};{(1,1),(1,2),(1,3)).

二、選擇題

1.C.2.D.3.B.4.B.

5.D.6.C.7.C.

8.A.9.D.10.B.11.B.

13.A.14.A.15.D

三、計算證明題

1.

⑴

(2)B無上界，也無最小上界。下界1,3;最大下界是3.

⑶A無最大元，最小元是1,極大元8,12,90+;極小元是1.

2.R={(1/1),(2,1M2,2),(3,1),(3,2)/(3,3),(4,1M4,2),(4,3),(4,4)).

⑴

I4

p0001

1100

⑵311

11;力

3.(1)Q*T=Q(T(X))=T(X)+3=2X+3=2X+3.

(2)o?c=o(a(x))=Q(X)+3=(x+3)+3=x+6,

(3)o->(p=o((p(x))=(p(x)+3=x/4+3z

(4)(P*T=(P(T(X))=T(X)A=2X/4=x/2,

(5)a*(p*T=c*(<p?T)=(peT+3=2x/l+3=x/2+3.

4.(1)P(aJ(a))AP(bJ(b))=P(3J(3))AP(2J(2))

=P(3,2)AP(2,3)

=1AO

=0.

(2)Vx3yP(y,x)=Vx(P(2,x)VP(3,x))

=(P(2,2)VP(3,2))A(P(2,3)VP(3,3))

=(0Vl)A(0Vl)

=1A1

=1.

元，最小元1,極大元8,12;極小元是1.

(3)B無上1界，無最小上界。下界1,2;最大下界2.

6.G=「(P-QMQAJPfR))

=->HPVQ)V(QA(PVR))

=(PA-.Q)V(QA(PVR))

=(PA-.Q)V(QAP)V(QAR)

=(PA^QAR)V(PA^QA^R)V(PAQAR)V(PAQA-1R)V(PAQAR)VHPAQAR)

=(PA^QAR)V(PA^QA^R)V(PAQAR)V(PAQA-.R)VHPAQAR)

=m3vm4Vm5Vm6vm7=S(3,4,5,6,7).

7.G=(VxP(x)V3yQ(y))->VxR(x)

=->(VxP(x)V3yQ(y))VVxR(x)

=(->VxP(x)A->3yQ(y))WxR(x)

=(3x->P(x)AVy->Q(y))VVz/?(z)

=3xVyVz((-.P(x)A-iQ(y))VR(z))

9.(1)r(R)=RUlA={(a,b),(b,a),(b,c),(c,d),(a,a),(b,b),(c,c),(d,d)},

s(R)=RURi={(a,b),(b,a),(b,c),(c,b)(c,d),(d,c)},

t(R)=RUR2UR3UR4={(a,a),(a,b),(a,c),(a,d),(b,a),