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

測試題

離散數(shù)學

一、選擇題

1.G是一棵根樹，則（）o

A.G一定是連通的B、G一定是強連通的

C.G只有一個頂點的出度為。D.G只有一個頂點的入度為1

2.下面哪個語句不是命題（）o

A.中國將成功舉辦2008年奧運會B、一億年前地球發(fā)生了大災難

C.我說的不是真話D.哈密頓圖是連通的

3、設(shè)R是實數(shù)集合，在上定義二元運算*:a,b€R,a*b=a+b-ab,則

下面的論斷中正確的是（）。

A.0是*的零元B、1是*的幺元

C.0是*的幺元D.*沒有等塞元

4.下面說法中正確的是（）。

A.所有可數(shù)集合都是等勢的B、任何集合都有與其等勢的真子集

C.有些無限集合沒有可數(shù)子集D.有理數(shù)集合是不可數(shù)集合

5.無向完全圖K3的不同構(gòu)的生成子圖有（）個。

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

6.下面哪一種圖不一定是無向樹

A.無回路的連通圖

B.有n個頂點n-1條邊的連通圖

C.每對頂點間都有通路的圖

D.連通但刪去一條邊則不連通的圖

7、設(shè)集合A={{1,2,3},{4,5},{6,7,8}},則下列各式為真的是（to

A.lAB.{{4,5}}A

C.{1,2,3}(AD.((A

8、在有界格中,若一個元素有補元，則補元（）o

A.必惟一B、不惟一

C.不一定惟一D.可能惟一

9、設(shè)集合A={1,2,3,…,10},下面定義的哪種運算關(guān)于集合A是不封閉

的？（）

A.x*y=max{x,y}

B.x*y=min{x,y}

C.x*y=GCD(x,y),即x,y的最大公約數(shù)

D.x*y=LCM（x,y）,即x,y的最小公倍數(shù)

10、集合X中的關(guān)系R,其矩陣是，則關(guān)于R的論述中正確的是（）o

A.R是對稱的B、R是反對稱的

C.R是反自反的D.R中有7個元素

11.下列各組數(shù)中，哪個可以構(gòu)成無向圖的度數(shù)列（）o

A.l,1,1,2,2B.2,2,2,2,3

C.l,2,2,4,6D.2,3,3,3

12.是定義在Z上的二元運算，，則的幺元和零元分別是（）o

A.不存在，0B.0,1

C.1,不存在D.不存在，不存在

13.設(shè)為自然數(shù)，且

I若x為奇數(shù)

/W=-若x為偶數(shù)

12

則/（。）和r（{。}）分別是（）o

A.O,0B.0,{0}

C.{0},{0}D.{0},0

14.下列命題公式中是矛盾式的有（）o

A.(〃一＞—1〃)一＞—\pB.-i(qtp)八p

C.(—＞pfq)f(qT—1〃)D.(。vq)f;?

15.下列各Hasse圖中，是格的有（）。

A.B.

C.D.

16.下列命題公式中是永假式的有（）o

A.(〃—＞―i〃)一＞—1〃B.Tq-?〃)A〃

C.(r?f夕)f(Ffp)D?(pvq)Tr

17.設(shè)命題公式((P((Q((P)),記作G,則使G的真值指派為。的P,Q的取

值是()o

A.(0,0)B.(0,l)C.(l,0)D.(l,l)

18.與命題公式P((Q(R)等值的公式是()o

A.(P(Q)(RB.(P(Q)(RC.(P(Q)(RD.P((Q(R)

19.命題公式伊9乂「是()o

A.永真式B.永假式C.可滿足式D.合取范式

（）o

A.充分條件B.必要條件C.充分必要條件D.既非充分也非必

要條件

30.設(shè),則與V能構(gòu)成強連通圖的邊集合是（）。

A..E={<a,d>,<>,<b,d>,<c,b>,<d,c>}

B.E={<a,d>,<b、a>,<Z?,c>,</?,J>,<d,c>}

C.E={<a.c>,<b,a>,<Z?,c>,<d,a>,<d,c>}

D.E={<a,b>,vayc>,va,d>,<b,d>,<c,d>}

31.相鄰矩陣具有對稱性的圖一定是（）。

A.有向圖B.無向圖C.混合圖D.簡單圖

32.無向圖G是歐拉圖，當且僅當（）o

A.G的所有結(jié)點的度數(shù)全為偶數(shù)B.G的所有結(jié)點的度數(shù)全為奇

數(shù)

C.G連通且所有結(jié)點的度數(shù)全為偶數(shù)D.G連通且所有結(jié)點的度數(shù)全

為奇數(shù)

33.設(shè)為連通平面圖且有r個面，則r=（）。

A.m—n+2B.n-m—2C.n+m-2D.m+n+2

34.設(shè)G是由5個結(jié)點組成的完全圖，則從G中刪去（）條邊可以得到

樹。

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

35.由5個結(jié)點可構(gòu)成的根樹中，其叉數(shù)m最多為（）o

A.2B.3C.5D.4

36.下圖是（）。

A.完全圖B.哈密頓圖C.歐拉圖D.平面圖

37.設(shè)集合A={1,2,3,…,10},在集合A上定義的運算，不是封閉的為

()o

A.a,bA,ab=lcm{a,b}(最小公倍數(shù))B.a,bA,

ab=gcd{a,b}(最大公約數(shù))

C.a,bA,ab=max{a,b}D.a,bA,

ab=min{a,b}

38.在自然數(shù)N上定義的二元運算。滿足結(jié)合律的是()o

A.a(b=a—bB.a(b=a+2bC.a(b=max{a,b}D.a(b=(a-b(

39.下列代數(shù)系統(tǒng)(G,*)中，其中*是加法運算.()不是群。

A.G為整數(shù)集合B.G為偶數(shù)集合

C.G為有理數(shù)集合D.G為自然數(shù)集合

4。設(shè)(1,(2,(3是三個置換,其中(1=(12)(23)(13),(2=(24)(1

4),(3=(1324)

則3可以表成()o

A.B.(l(2C.D.(2(l

41.下列圖表示的偏序集中，是格的為()。

A.B.

C.D.

42.設(shè)是布爾代數(shù)，，則下式不成立的是()o

A.QB=OB.67+/?=1C.a+b=aD.4+分=1

43.布爾代數(shù)式=()o

A.a+加B.Z?+cQ.b+cD.b+c

44.設(shè)集合A={1,2},B={a,b,c},C={c,d},則Ax(B(C)=()。

A.{<c,l>,<2,c>}B.{<l,c>,<2,c>}C.{<c,l>,<c,2>}

D.{<l,c>,<c,2>}

45.設(shè)A={0,a},B={l,a,3},則A(B的恒等關(guān)系是()。

A.{<0,0><l,l>,<3,3>,<a,a>}B.{<O,O>,<1,1>,<3,3>}

C.{<l,l>,<a,a>,<3,3>}D.{<0,l>,<l,a>,<a,3>,<3,0>}

46.設(shè)A={a,b,c},R={<a,a>,<b,b>},則R具有性質(zhì)()。

A.自反的B.反自反的C.反對稱的D.等價的

47.設(shè)集合是從A到B的函數(shù)，

,則(是()。

A.雙射B.滿射但不是單射C.單射但不是滿射D.非單射也非滿射

48.下列式子中正確的是()0

A.=0B.C.{a,b}D.{}

49.有向圖的鄰接矩陣中，行元素之和是對應結(jié)點的（）,列元素之和

是對應結(jié)點的()。

A.度數(shù)B出度C.最大度數(shù)D.入度

50.給定無向圖如下所示，下面給出的頂點集子集中，不是點割集的是

()o

A.{b,d}BJd}

C.{e}D.{f,h}

51.謂詞公式xA(x)xA(x)的類型是()o

A.永真式B.矛盾式

C.非永真式的可滿足式D.不屬于(A),(B),(C)任何類型

52.謂詞公式取真值為1的充分必要條件是()。

A.對任意y,使P(v)都取真值1

B.存在一個y0,使P(y0)取真值1

C.存在某些y,使P(y)都取真值1

D.存在y0,使P(yO)取真值。

53.設(shè)G是群，當6有()個元素時，不能肯定G是交換群。

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

54.若集合A={a,b,c},(為空集合，則下列表示正確的是()o

A.{a}AB.{a}AC.aAD.A

55.設(shè)A,B,C都是集合，如果A(C=B(C,則有()。

A.A=BB.ABC.當A-C=B-C時，有A=BD.當C=U

時，有AB

56.設(shè)Sl=(,S2={(},S3=P({(}),S4=P((),以下命題為假的是()。

A.S2(S4B.S1(S3,C.S4(S2D.S4(S3

57.設(shè)G是有6個元素的循環(huán)群,a是生成元素，則G的子集()是

子群。

A.{a}B.{a,e}C.{e,a3}D.{e,a,a2}

58.設(shè)集合A={a,b,c,d,e},半序關(guān)系R的哈斯圖

如下，假設(shè)A的子集B={c,d,e},則元素c為B的()o

A.下界B.最大下界

C.最小上界D.以上答案都不對

59.設(shè)G((x(yP(x,y)(Q(z,w),下面三個命題為真的是()。

A.G是前束范式B.G不是前束范式

C.G不是一階公式D.G是永真式

60.對任意集合S,S((=S,滿足()o

A.塞等律B.零一律C.同一律D.互補律

61.設(shè)命題公式，則使公式G取真值為1的P,Q,R賦值分別是()0

A.0,0,0

B.0,0,1

C.O,1,0

D.l,0,0

62.設(shè)a是集合A的元素，則以下正確的是()o

A.Qq{a}

B.{a}qA

C.a^A

D.{rz}eA

63.設(shè)集合A{1,2,3,4},B:{2,4,6,9},則集合A,B的對稱差A，B=

()o

A.{1,3}

B.{2,4,61

C.{1,3,6,9}

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

64.有向完全圖D=<V,E>,則圖D的邊數(shù)是()0

A.|E|(|E|-1)/2

B.|V|(|V|-1)/2

C.|E|(|E|-1)

D.|V|(|V|-1)

65.設(shè)G是有n個結(jié)點，m條邊的連通阻，必須刪去G的()條邊，才

能確定G的一棵生成樹。

A.m-n+1

B.n-m

C.m+n+1

D.n—m+1

66.設(shè)N為自然數(shù)集合，＜N,＞在下面4種運算下不構(gòu)成代數(shù)系統(tǒng)的

是（）。

A.xy=x+y—2xyB.xy=x+y

C.xy=xyD.xy=|x|+|y|

67.已知圖G的相鄰矩陣為，則6有（）。

A.6個點，度為4B.5個點，度為6

C.4個點，度為3D.4個點，度為6

68.設(shè)集合A={1,2,3,……,10）,半序關(guān)系（是A上的整除關(guān)系，則

半序集（A,（）上的元素1。是集合A的（）。

A.最大元B.最小元C.極大元D.極小元

二、填空題

1.代數(shù)格（L,（,（）中的運算（和（滿足的算律有、、

2.A是含有3個元素的集合，在A上可以定義個不同的等價關(guān)系。

3.R是實數(shù)集合,R中的關(guān)系g=kx2,x＞}從R到R的函數(shù)（填

“是”或“不是”）。

4.vG,*＞是群，|G|＞1,則G中的零元o

5、當n是____________值時，無向完全圖Kn是歐拉圖。

6、I是整數(shù)集合，代數(shù)系統(tǒng)〈I,X＞（X是通常乘法）的幺元是______,-1

的逆元是___________o

7、元素數(shù)目不超過_______的格一定是鏈。

8、公式T/，vQ)c(〃人⑵的主合取范式為o

9、的有效結(jié)論是__________o

1。、已知公式A(p,q,r)的主合取范式為MAMAM，它的主析取

范式為(寫成編碼形式)。

11.設(shè)A={a,b},B={0,l,2},則可定義種不同的從A到B的單射。

12.已知集合A={(,1,2},則A的塞集合((A六o

13.設(shè)〈A,<>是分配格，若對任意的a,c,c￡A,如果有aAb=aAc,aV

b=aVc成立，則abo

14、僅當n時，Kn為平面圖。

15.p->q的主合取范式是_________________________o

16.語句“我在說謊"命題。(填“是”或“不是”)。

17.設(shè)A={a,b,c,d}>R是定義在A上的關(guān)系,R={<a,b>,<c,d>,<a,d>},

貝Ur(R)=o

18.一個樹林G有三棵樹，G的頂點數(shù)是20,則G的邊數(shù)為

19.P(P(0))=o

20.整數(shù)加法群<Z,+>中1的階是________________o

21.設(shè)有向圖D=VV,E>的鄰接矩陣為A(D)=，則(E(=o

22.語句“這句話是錯的”命題。(填“是”或“不是

23.設(shè)命題公式G=P(((Q(R),則使G取真值為1的指派

是，，o

24.已知命題公式為G=((P(Q)(R,則命題公式G的析取范式

是。

25.公式的自由變元是,約束變元是

26.謂詞邏輯公式的前束范式是

27.設(shè)個體域D={a,b},消去公式中的量詞，則

28.換名規(guī)則施于變元，代入規(guī)則施于變元。

29.設(shè)圖G=<V,E>和G(=〈V(,E(>,若，則G(是G的

真子圖，若，則G(是G的生成子圖。

30.在無向圖中，結(jié)點間的連通關(guān)系具有性,性,

性，是關(guān)系

31.無環(huán)有向圖D的關(guān)聯(lián)矩陣M(D)中，第i行值為1的元素個數(shù)為結(jié)點

vi的

第j列值為-1的元素個數(shù)為結(jié)點%的

32.設(shè)G是完全二叉樹，G有15個結(jié)點，其中有8個是樹葉，則G有

條邊，G的總度數(shù)是，G的分支點數(shù)是,G中度數(shù)為3

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

33.連通有向圖D含有歐拉回路的充分必要條件

是

34.設(shè)G是有n個結(jié)點的簡單圖，若G中每對結(jié)點的度數(shù)之

和，則G一定是哈密頓圖

35.設(shè)G是有n個結(jié)點，m條邊的連通圖,要確定G的一顆生成樹,

必須刪去G的條邊

36.一個有向樹T稱為根樹，若,其中,稱

為樹根,

稱為樹葉

37.在代數(shù)系統(tǒng)(N,+)中，其單位元是，有逆

兀.O

38.設(shè)A是非空集合，集合代數(shù)(P(A),(,。中，P(A)對運算(的單位元

是,P(A)對運算(的單位元是。

39.把置換表成輪換的乘積是，表成對換

的乘積是。

40.設(shè)G是由6個元素構(gòu)成的循環(huán)群，a是G的一個生成元素，則G有

個子群，G的生成元是。

41.非空集合L,其上定義二元運算(和(，如果是交換群，(L,()

是，而且滿足分配律，則L對二元運算(和(構(gòu)

成環(huán)。

42.設(shè)L是一個集合，(和(是L上兩個二元運算，如果這兩個二元運算滿足

律，律和律，則(L,(,()是格。

43.在布爾代數(shù)中，有成立.則該式的對偶式也一定

成立。

44.設(shè)RI,R2是集合A={1,2,3,4}上的二元關(guān)系，其中R1=

{<1,1>,<1,2>,<2,4>},R2={<l,4>,<2,3>,<2,4>,<3,2>},ljllJR1(R2

=o

45.設(shè)R,S都是集合A上的等價關(guān)系，則對稱閉包

s(R(S)=o

46.圖的通路中邊的數(shù)目稱為.結(jié)點不重復的通路是通

路.邊不重復的通路是通路。

47.將謂詞公式中的約束變元換名___。

48.寫出下列集合的子集：BHO；C-(o

49.設(shè)全集合E

{1,2,3,4,5},A={1,2,3},B={2,5},A(B=,~B=。

?A?B=o

50.設(shè)A,B代表集合，命題A(B((((((的真值為。

51.設(shè)集合A={a,b,c},B={a,b},則P(A)-

P(B)=,P(B)-P(A)=o

52.設(shè)人={=,(,(,(,(}選擇適當?shù)姆柼钤诟餍☆}的橫線上.(1)(1,2,3,4)

N;(2)o

53.關(guān)于格的命題P：aA(bVc),求P的對偶命題P*=o

54.計算Z6的所有理想o

55.求的真值_____________o

56.判定公式((P(Q(((R(Q()(((P(R((Q)的類型__________。

57.將命題公式化為只含(和(的盡可能簡單的等值式o

58.設(shè)n(A)=m，則A上有個不同的自反關(guān)系。

59.設(shè)集合A={a,b,c,d(,A上的關(guān)系R={(a,a),(a,c),(b,d)),則關(guān)系

R2=o60.設(shè)集合A中有4個元素，則A上的不同的等

價關(guān)系的個數(shù)為個。

三、判斷題

1.空間中的平行六面體是平面圖。()

2.每個頂點的度都是偶數(shù)的無向圖一定是歐拉圖。()

3、頂點數(shù)目相同，邊數(shù)也相同的兩個無向圖一定同構(gòu)。()

4.函數(shù)的逆關(guān)系還是函數(shù)。()

5.A,B,C制S是集合，如果AUB-AUC,貝ijB三C。（）

6、設(shè)R是環(huán),A,B是R的兩個理想，且B包含于A,則A/B是R/B的理

想，并且

R/B/（A/B）同構(gòu)于R/Ao（）

7.的對偶是。（）

8.設(shè)G是有r個面的連通平面圖，頂點數(shù)和邊數(shù)分別是n和m,則

n-m+r=2°（）

9.n階有向完全圖有n（n-1）條邊。（）

1。.在代數(shù)系統(tǒng)中，若，則。（）

11.設(shè)無向圖T是樹，則T中一定沒有簡單回路。（）

12.能夠畫在一張平面上的圖是平面圖。

13.設(shè)是代數(shù)系統(tǒng),B是S的非空子集，則是的子代數(shù)。（）

14.循環(huán)群的子群仍然是循環(huán)群。（）

15.格不一定是布爾代數(shù)。（）

16.1+101=110是命題。（）

17.“全體立正是命題"o（）

18.“明天是否開大會？”是命題。（）

19.“如果天氣好，則我去散步”是命題。（）

20.判斷億,（）是否為格？其中（是數(shù)的小于或等于關(guān)系。（）

21.設(shè)R是實數(shù)集，“+”為數(shù)的加法，“X”定義為.試問R對二元

運算+和X是否構(gòu)成環(huán)。（）

22.設(shè)集合人={18的正整數(shù)因子},(為整除關(guān)系，說明＜A,(，是否是偏序

關(guān)系。()

23.是對的。()

24.(是(的子集。()

25.如果S(T=S(M,則丁=乂。()

26.已知S={2,a,{3},4},R={{a},3,4,l}〃J{a}(S0()

27.整數(shù)集合Z和普通的減法運算是封閉的。()

28.在R中定義二元運算：*,a*b=a+b+ab,對于任意a,b屬于R,則

＜R,*＞是獨異點。()

29.整數(shù)集合{1,2,3,4,6,12}關(guān)于整除關(guān)系構(gòu)成了偏序集，并且該偏序集

是格。()

四、證明題

1.設(shè)〈G,*＞是群，具有幺元e,如果對G的任意元素a,都有

a2=e,貝kG,*＞是交換群

2.形式證明

3.證明：P((Q(R)(P(Q(R.

4.試證明:

5.試證明：

6.證明：(

7.設(shè)G是圖，無回路，但若外加任意一條邊于G后，就形成一回路.

試證明G必為樹.

8.設(shè)B是任意集合，試驗證(P(B),()是群.P(B)是集合B的希集，(是集合

的對稱差運算,

9.給定代數(shù)系統(tǒng)(G,+,*),二元運算見表一，表二.

表二

+abcD*abcD

AabcDaaaaa

BbadCbabcd

CcDaBcacdb

DdCbAdadbc

證明(G,+,*)是域.

10.證明如果非空集合A上的二元關(guān)系R和S是偏序關(guān)系，則也是A上

的偏序關(guān)系.

11.試證A-(B—C)=(A-B)((A(C)

12.設(shè)非空集合A,驗證()是布爾代數(shù)，

13.試證明屬于關(guān)系不滿足傳遞性，即對于任意的集合A,B,C若A€B且

BCC不一定有

AWC

14.設(shè)A,B為兩個集合，證明A—8=人當且僅當ACB=。

15.設(shè)R,S都是非空集合A上的二元關(guān)系，且他們是對稱的，證明:

RoS具有對稱性當且僅當RoS=SoR.

16.已知g:A->B,f:B->C

1)已知fog是單射的且g是滿射的，證明f是單射的

2)已知fog是滿射的且f是單射的，證明g是滿射的

17.設(shè)A是傳遞集，證明A+也是傳遞集。

18.設(shè)G是n階無向簡單圖，其直徑為d(G)=2,o(G)-n-2,證明G的邊

數(shù)m>2n-4

19.V=〈S,*>是可交換半群，若a,b€S是V中得得等元，證明a*b也是V

中的塞等元

20.設(shè)L是格,證明對于任意a,b,c,d€L有：(aAb)V(cAd)<(aVc)

A(bVd)

五、計算題

L無向樹T有2個2度頂點，1個3度頂點，3個4度頂點，其他的都是

樹葉，問T中有多少片樹葉？

2.設(shè)公式，其中P(x):x>2,

Q(x):x=0,F是永假式，個體域是{1,2},求公式A(x)的真值

3.設(shè)集合乂={1,2,3,4),X中的關(guān)系為

F={<1,1>,<1,2>,<1,4>,<2,1>,<2,2>,<3,3>,<4,1>,<4,4>}

寫出F的關(guān)系矩陣與其關(guān)系圖，F(xiàn)有哪些性質(zhì)？

4.(1)n(n>1)階無向完全圖與有向完全圖各有多少條邊為什么？

(2)完全二部圖K中共有多少條邊為什么？

(3)每個頂點的度都為k的無向圖稱為k正則圖，問：n階k

正則圖中共有多少條邊為什么？

5.設(shè)集合1=g，b},在L中規(guī)定+和?如下：

a+a=a,a+b=b+a=b,b+b=b

a?a^a,a?b-b?a-a,b?b三b

問vL,+,?>能構(gòu)成代數(shù)系統(tǒng)嗎？若可以，寫出該代數(shù)系統(tǒng)的運算表。

該代數(shù)系統(tǒng)有什么特性？

6.設(shè)多重集A={{},{,1},{1,1,}},B={{,1},{1}}.計算AB,AB,

A-B

7.設(shè)集合M={1,2,3,4,5},(和(是M上的兩個置換，(=,(=(1

45)(23),用輪換的形式寫出((，(()(-1((-lo

8.對集合L,規(guī)定對于x,yEL,x<y當且僅當x是y的因子。問下面哪

幾個偏序集是格為什么？

(1)L={1,2,3,4,6,12}

出1={1,2,3,48,12,14}

(3)L={1,2,3,4,5,6,7,8,9,10}

9.在全總個體域中符號化下列命題。

(1)是金子總是要發(fā)光的。

(2)并非所有微笑的人都是高興的。

(3)平面圖的色數(shù)不超過4

10.若無向圖G是歐拉圖，G中是否存在割邊為什么

11.設(shè)集合，區(qū)是定義在A上的二元關(guān)系，，寫出R的關(guān)系矩陣并求

R的對稱閉包。

12.設(shè)集合A={2,3,4,6,8,12,24},R為A上的整除關(guān)系。

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

(2)寫出集合A中的最大元、最小元、極大元、極小元；

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

13.令X-｛,，…，｝,YH,，…，｝o問

⑴有多少個不同的由X到Y(jié)的關(guān)系？

⑵有多少個不同的由X到Y(jié)的函數(shù)？

⑶當n,m滿足什么條件時，存在單射，且有多少個不同的單射？

14.在全總個體域中符號化下列命題。

(1)在中國工作的人并非都是中國人。

(2)有的人在微笑但內(nèi)心不高興。

(3)每種金屬都可以溶解在某種液體種。

15.將下列命題符號化：

(1)雖然交通堵塞，但是老王還是準時到達火車站；

(2)張力是三好學生或優(yōu)秀共青團員

(3)老李或小刁中有一個人去廣州出差

16.判定公式P(Q與(P(Q是否等值.

17.用等值演算法判定公式P(((Q(R"P(Q(R是永真式？永假式？

18.求公式的主合取范式和主析取范式.

19.化簡下式：(A(B(C)(((A(B(C)

20.設(shè)命題P,Q的真值為0,命題R,S的真值為1,求命題公式的真

值.

21.將下列命題符號化：

(1)每個母親都愛自己的孩子；

(2)所有的人都呼吸；

(3)有某些實數(shù)是有理數(shù).

22.指出下列公式

VxVy(7?(x,y)vL(y,z))AZ1X77(X,y)

中量詞的每次出現(xiàn)轄域，并指出變元的每次出現(xiàn)是約束出現(xiàn)，還是自由出

現(xiàn)，以與公式的約束變元，自由變元.

23.給定解釋I:

①D={2,3};

②D中特定元素a=2;

③函數(shù)為〃2)=3J⑶=2

④謂詞F(x)為F⑵=0,F⑶=1

G(x,y)為G(2,2)=G(2,3)=G(3,2)=0,G(3,3)=l

L(x,y)為L(2,2)=L(3,3)=1,L(2,3)=L(3,2)=0

求在解釋I下各公式的真值.

(1)VxR(x)AG(A,a)；

(2)Vx3yL(x,y);

24.討論公式的類型.

25.將公式F化為前束范式.

26.判定下面二圖是否同構(gòu)？

27.設(shè)G=(V,E)是一個無向圖，

E={<Vj,V2>,<v2,v3>,<匕，匕>?<V,,V5>,<v5,v4>,<v3,v4>,<V7,V8>}

(1)畫出G的圖解；

⑵指出與V3鄰接的結(jié)點，以與與V3關(guān)聯(lián)的邊;

(3)指出與e1關(guān)聯(lián)的結(jié)點；

(4)該圖是否有孤立結(jié)點和孤立邊？

(5)求出各結(jié)點的度數(shù)，并判斷是不是完全圖？

(6)G=〈V,E>的(V(,(E(各是多少？

28.給定下列六個圖(如圖)，

Gi=〈Vi,Ei>,其中Vi={a,b,c,d,e},Ei={(a,b),(b,c),(c,d),(a,e)}

G2=〈V2,E2>淇中V2=Vi,E2={(a,b),(b,e),(e,b),(a,e),(d,e)}

G3=〈V3,E3>,其中V3=V],E3={(a,b),(b,e),(e,d),(c,c)}

=<V4,E4>,其中

V4=V1,E4={<a,b>,<b,c>,<c,a>,<a,d>,<d,a>,<d,e>}

G5=<V5,E5>,其中

V5=Vi,E5={<a,b>,<b,a>,<b,c>,<c,d>,<d,e>,<e,a>}

G6=〈V6,E6>,其中V6=V1,E6={<a,a>,<a,b>,<b,c>,<e,c>,<e,d>}

試問：

(1)哪些圖是有向圖？哪些圖是無向圖?

(2)哪些是簡單圖？

(3)哪些是強連通圖？哪些是單側(cè)連通圖？哪些是弱連通圖?

29.求圖G的點割集、割點、邊割集和割邊.

30.已知有關(guān)人員a,b,c,d,e,f,g的有關(guān)信息：

a：說英語；

b:說英語或西班牙語；

c;說英語，意大利語和俄語；

d:說日語和西班牙語

e:說德語和意大利語；

f：說法語、日語和俄語；

g：說法語和德語.

試問上述7人中是否任意兩人都能交談(如果

必要，可由其余5人中組成的譯員鏈幫助)

31.在具有n個結(jié)點的完全圖Kn中，需要刪去多少條邊才能得到樹.

32.畫出具有下列條件的有5個結(jié)點的圖.

(1)沒有哈密頓問路，也不能適當指定各邊的方向，使其具有歐拉

回路；

(2)有哈密頓回路，但是不能適當指定各邊的方向，使其具有歐拉回

路；

⑶沒有哈密頓回路，但是能適當指定各邊的方向，使其具有歐拉回路;

(4)有哈密頓回路，也能適當指定各邊的方向，使其具有歐拉回路.

33.通常數(shù)的加法運算可看作正整數(shù)N+上的二元運算.下列集合是N+的

子集，加法運算在這些子集上封閉嗎？為什么？

(1)是15的因子}⑵邑={m是1%勺倍麴

(3)§3={“6整的,24整除〃1

;運算*是否有單位元和富等元？若有單位元的話，哪些元素有逆元？

35.是布爾代數(shù)，，化簡,

36.設(shè)是定義在Z5(={0」,2,3,4})上的多項式(即系數(shù)是Z5的元素的多

項式)，試計算P(x)+Q(x),P(x)Q(x).

37.回答下列代數(shù)系統(tǒng)是環(huán)嗎？是交換環(huán)嗎？

(l)(Zm,+,*),其中Zm={0,l,2,…,m—l},+和*是模m加法和

乘法.

(2)(Mn(R),+,(),其中Mn(R)是n階實矩陣全體，+,(分別是矩陣的加

法和乘法.

38.設(shè)集合A={a,b},R是P(A)上的包含關(guān)系，寫出R的表達式和關(guān)系

矩陣.

39.設(shè)A={1,2,3},用列舉法給出A上的恒等關(guān)系IA,全關(guān)系EA,A上的小

于關(guān)系

與其逆關(guān)系和關(guān)系矩陣.

40.設(shè)A={1,2,3,4},R是A上的二元關(guān)系，其關(guān)系矩陣為

Io()r

1000

MR=

“0001

1000

試求⑴R的關(guān)系表達式；⑵Dom(R)和Ran(R);

(3)RR中有多少個有序?qū)?4)R-的關(guān)系圖中有多少條自回路

41.設(shè)集合判定下列關(guān)系，哪些是自反的，對稱的，反對稱的，傳遞的？

R[={<a,a>,<h,a>},&={<aya>,<>,<

&={<c,d>),/?4={<a,a>,<b,b>,<c,c>),/?5={<a,c>,<b,d>),

42.設(shè)A={1,2,3,4,5,6},定義A上的二元關(guān)系

R={<1,1>,<1,4>,<2,2>,<2,3>,<2,6>,<3,2>,<3,3>,<3,6>,

<4,1>,<4,4>,<5,5>,<6,2>,<6,3>,<6,6>}

判定R是否為等價關(guān)系？(2)若是等價關(guān)系，寫出A的關(guān)于R的等價

類.

43.設(shè)集合A={a,b,c,d},定義R={<a,b>,<b,a>,<b,c>,<c,d>},求

r(R),s(R),t(R).

44.求謂詞公式的真值.其中44(3,Q(x):x(l,R(x):x(2.

f((3)=1,f(1)=5,f(5)=(3.a：5.

個體域D=((3,1,5).

45.化簡

46.設(shè)集合人=匕,可舊={1,2,3}?=息},求(人乂8)乂(3,AXBXC,BxA.

47.用列舉法表示以下集合：

(1)A={AJXGAA2<7);(2)4={A|XWNA|3-A|<3}；

2

(3)iA={G/?A(x+1)<0}

48.列出下列集合的各元子集，并求騫集

(1)A={a,b,c)(2)A={1,{2,3}}(3)A={0,{0}}

49.A={a,b,c},B={l,2},令al=P(A),a2=A->B,構(gòu)造一個al到a2的雙射

函數(shù)，再構(gòu)造一個

a2到al的雙射函數(shù)

50.由f:A->B導出A上的等價關(guān)系定義為：

R={<x,y>|xCAAy€AAf(x)=f(y)}

設(shè)WNUN且

fl(n)=nf2(n)=1n為奇數(shù)f3(n)=0n為偶數(shù)

f3(n)=j,n=3k+j,j=0,1,2,k€Nf4(n)=j,n=6k+j,j=0,l,---,5,k€N

Rk為fk導出的N上的等價關(guān)系,k=l,2,3,4

1)求商集N/Rkk=l,2,3,4

2)求14={10卜也€琳在fl,f2,f3,f4下的象!

51.對圖給出的二叉樹分別進行先根遍歷、中根遍歷和后根遍歷。

更多課程資料請到大學課程網(wǎng)學習

測試題答案

離散數(shù)學

一、選擇題

l.A2.C3.C4.A.5.D6.C7.D8.C9.D

10.D

11.B12.D13.B14.B15.B16.B17.C18.B

19.A20.D

21.C22.A23.D24.A25.C26.C,A27.B28.A

29.B30.A

31.B32.C33.A34.C35.D36.B37.A38.C

39.D40.D

41.C42.D43.B44.B45.C46.A47.B48.D

49.BQ50.A

51.B52.A53.D54.B55.C56.A57.C58.C

59.B60.C

61.D62.B63.C64.D65.A66.A67.D68.C

二、填空題

1.交換律、結(jié)合律、吸收律

2.5

3.不是

4.不存在

5.奇數(shù)

6.1,-1

7.3

8.

9.R

10.mlVm2Vm4vm6Vm7

11.6

12、((A)={(,{ft,{1},{2},{(,1},{(,2},{1,2},A}

13=

14.奇數(shù)

15.

16.不是

17、{<a,b>,<c,d>,<a,d>,<a,a>,<b,b>,<c,c>,<d,d>}

18、17

19、{cp,{cp}}

20、無限

21.7

22.不是

23.(1,0,0,)(1,0,1)(1,1,1)

24.P((Q(R

25.y,xx,z

26.

27.

28.約束自由

29.

30.自反性對稱性傳遞性等價.

31.出度入度

32.142876

33.D中每個結(jié)點的入度=出度.

34.大于或等于n

35.m+l—n

36.若有向圖T恰有一個結(jié)點的入度為0,其余結(jié)點入度為1入度為。的

結(jié)點入度為1的結(jié)點.

37.0僅有單位元0.

38.(A.

39.(123)(56)(13)(12)(56)(不唯一)

40.4a,a5

41.(L,()半群二元運算(對運算(

42.交換律結(jié)合律吸收律

43.

44.{<1,4>,<1,3>}

46.45.R(S

47.通路出度初級簡單.

48.V〃(P(〃)TR(u)vQ(〃,z))A3v7?(v)—>w)

49.??{}????

50.{2},{1,3,4},{1,3,4,5}

51.0

52.{{c},{a,c},{b,c},{a;b,c}};

53.

54.（aAb）V（aAc）

55.{0},{0,3},{0,2,4}{0,l,2,3,4,5）

56.1

57.永真式

57.

582,n2~m

59.R2={（a,a）,（a5c）}

60.15

三、判斷題

1.正確（從同構(gòu)的角度說明理由）

2.錯誤（舉反例）

3.錯誤（舉反例）

4.錯誤（從同構(gòu)的角度說明理由）

5.錯誤（舉反例）

6.正確

7.錯誤

8.正確

9.正確

10.錯誤

12.11.正確

13.錯誤

14.錯誤

15.正確

16.正確

17.否

18.否

19.否

20.是

21.是

22.否

23.是

24.錯誤

25.真

26.假

27.錯誤

28.正確

29.是

30.是

四、證明題

證明：由條件，所以，則對任意的％b,

a*b=a7*b-]

另外，由，得

兩邊同時左乘以，右乘以，利用結(jié)合律，得

b*a=a*b

所以，＜G,*＞是交換群

2.證明：

(1)“AS前提引入

(2)P(1)化簡

(3)s(1)化簡

(4)p->qVr前提引入

(5)qVr(2)(4)分離

(6)s->-ir前提引入

(7)-ir(3)(6)分離

(8)q(5)(7)析取三段論

3.證明

P(QR)

P(QR)(等值蘊含式)

P(QR)(等值蘊含式)

(PQ)R(結(jié)合律)

(PQ：1R(摩根律)

PQR(等值蘊含式)

所以，P((Q(R)((P(Q)(R

4.證明

(1)SCP規(guī)則

(2)SPP

⑶P(1),(2)析取三段論

⑷P(QR)P

(5)QR⑶，⑷假言推理

(6)QP

(7)R(5),⑹假言推理

5.證明

(1)QRP

(2)RP

(3)Q(1),(2)析取三段論

(4)(PQ)P

(5)PQ⑷置換

(6)Q(3),(5)析取三段論

6.證明

前提:

結(jié)論：

(1)-(Vx(A(x)fB(x)))附加前提

⑵3x(-i(A(x)tB(x)))(1)”

⑶—i(/4(c)—>B(。))(2),ES

⑷A(c)(3),T,E

⑸B(c)(3),T,E

(6)BxA(y)(4),EG

⑺3X4(A)-VxB(x)P

(8)VXB(A)(6),(7),T,E

(9)B(c)(8),US

(10)—iB(c)A6(c)(5),(9)矛盾式

7.由樹的定義可知，只需證G連通即可.任取不相鄰兩點u,v,由題設(shè)，加

上邊vu,v>就形成一回路，于是去掉邊vu,v>,從U到V仍有路U,…,V,即

u,v連通，由u,v的任意性可知，G是連通的，故G必是樹.

8.證明

對任意集合C,D,E(P(B),有

(C十。)十E=[(CC~0D(3I~CWE

=[((Cn?D)。(DA~Q)n?0U[En~((Cn?。)u(Qfl~C))]

=(cn~on~E)u(~cnDn~E)u(￡n~cn~o)u(cnon?

C十(。十E)=C十[(Oc?七)。(牙1~O)]

=(cn1~((Dn~E)51~r>))U~cni(r>n~石)5殖~D)]

=(cn~￡n~￡)u(cnon￡)u(~cnon~￡)u(~cn~on&

所以，故(P(B),()是半群.

0￡?(8),任意。￡尸(8),

0十C=(0-C)U(C-0)=C=C^0

所以(是二元運算(的單位元.

,任意元素C,二元運算(的逆元是它自身.

可見，(P(B),0是群.

1。.9.用運算表知(G,+)是可結(jié)合的和可交換的，a是運算+的單位元，任

一元素的逆元是它自身；所以(G,+)是交換群；容易驗證｛G一值｝,*｝也是

交換群.且*對+是可分配的.故(G,+,*)是域.

證明①，所以有自反性；

②因為R,S是反對稱的,

所以.R(S有反對稱性.

③，因為R,S是傳遞的，

<x,y>￡AcSA<y,z>￡RcS

<=><x,y>GRA<x,y>GSA<y,z>G7?A<y,z>GS

<=><x,y>GR/\<y,z>GR/\<x,y>GSA<y,z>GS

=<x,z>wR八<x,z>eS<=><x,z>eRnS

所以，有傳遞性.

總之，R是偏序關(guān)系.

11.證明對任意先

XGA-(I3-C)

nxeA八xm(Be-C)=>xeAA(x5vxeC)

=(xwA△x任8)v(xw4八xwC)=>xw(A-B)D(AcC)

A—(B—C)c(A—B)u(AcC)

同理，有

xe(A-B)<j(Ar>C)=>xeA-(B-C)

所以，A-(B-C)=(A-B)((A(C)

12.證明因為集合A非空，故P(A)至少有兩個元素，顯然(，(是P(A)

上的二元運算.由定理，任給B,C,D(P(A),

HiBD=DCCD=DC

H2B(CD)=(BC)(BD)

B(CD)=(BC)(BD)

H3P(A)存在(和A,(B(P(A),有B((=B,B(A=B

H4,(B(P(A),B(A,存在A(~B,有

BA~B)=AB(A?B)

所以(P(A),jC~,0,A)是布爾代數(shù).

13.證明：本題也就是要證明：(1)AWBAB€C-〉A(chǔ)WC不為永真

式。

則就任意舉一個反例：A反1},B={2,{1}},C={{2,{1}}}

其中AWB且B€C

很顯然AC

故(1)式不為永真式

命題得證。

14.證明：A—B=A

AD~B=A

=>AA-BAB=AAB

=>AnB=0

AClB=0

=>(AAB)U?B=~B

=>AU?B=~B

=>ACl(AU~B)=An~B

=>AU(AA-B)=A-B

=>A=A-B

證明：

1)必要性

對于任意vx,y>€RoS

<=><y.x>RoS

<=>存在z(<y,z>€SA<z,x>€R)

存在z(<z,y>€SA<x,z>€R)

<=><x,y>€SoR

所以RoS=SoR.

2)充