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

1、測 試 題離散數(shù)學(xué)一、選擇題1、G是一棵根樹，則（ ）。A、G一定是連通的 B、G一定是強連通的C、G只有一個頂點的出度為0 D、G只有一個頂點的入度為12、下面哪個語句不是命題（ ）。A、中國將成功舉辦2008年奧運會 B、一億年前地球發(fā)生了大災(zāi)難C、我說的不是真話 D、哈密頓圖是連通的3、設(shè)R是實數(shù)集合，在上定義二元運算*：a，bR，a*b=a+b-ab，則下面的論斷中正確的是（ ）。A、0是*的零元 B、1是*的幺元C、0是*的幺元 D、*沒有等冪元4、下面說法中正確的是（ ）。A、所有可數(shù)集合都是等勢的 B、任何集合都有與其等勢的真子集C、有些無限集合沒有可數(shù)子集 D、有理數(shù)集合是不可

2、數(shù)集合5、無向完全圖K3的不同構(gòu)的生成子圖有（ ）個。A. 6 B.5 C. 4 D. 36、下面哪一種圖不一定是無向樹?A、無回路的連通圖B、有n個頂點n-1條邊的連通圖C、每對頂點間都有通路的圖D、連通但刪去一條邊則不連通的圖7、設(shè)集合A1,2,3,4,5,6,7,8，則下列各式為真的是( )。A.1A B.4,5A C. 1,2,3A D.A8、在有界格中，若一個元素有補元，則補元( )。A、必惟一 B、不惟一 C、不一定惟一 D、可能惟一9、設(shè)集合A=1,2,3,10，下面定義的哪種運算關(guān)于集合A是不封閉的？（ ） A、 x*y=maxx,y B、 x*y=minx,y C、 x*y=

3、GCD(x,y)，即x,y的最大公約數(shù) D、 x*y=LCM(x,y)，即x,y的最小公倍數(shù)10、集合X中的關(guān)系R，其矩陣是 ，則關(guān)于R的論述中正確的是（ ）。A、R是對稱的 B、R是反對稱的C、R是反自反的 D、R中有7個元素11. 下列各組數(shù)中，哪個可以構(gòu)成無向圖的度數(shù)列（ ）。A.1，1，1，2，2 B.2，2，2，2，3C.1，2，2，4，6 D.2，3，3，312. 是定義在Z上的二元運算，則的幺元和零元分別是（ ）。A.不存在，0 B.0，1C.1，不存在 D.不存在，不存在13. 設(shè)為自然數(shù)，且則分別是（ ）。A.0，0 B.0，0C.0，0 D.0，014. 下列命題公式中是矛

4、盾式的有（ ）。A. B.C. D. 15. 下列各Hasse圖中，是格的有（ ）。A. B. C. D.16 下列命題公式中是永假式的有（ ）。A. B.C. D.17. 設(shè)命題公式(P(QP)，記作G，則使G的真值指派為0的P，Q的取值是( )。 A.(0,0) B.(0,1) C.(1,0) D. (1,1)18. 與命題公式P（QR）等值的公式是( )。 A.(PQ)R B.(PQ)R C.(PQ)R D. P(QR)19. 命題公式(PQ)P是( )。 A.永真式 B.永假式 C.可滿足式 D.合取范式20. 設(shè)命題公式，則G與H的關(guān)系是( ) 。A. B. C. D.21謂詞公式中

5、量詞x的轄域是( )。A B. P(x) C. D.22設(shè)個體域為整數(shù)集，下列公式中其值為1的是( )。A. B.C. D.23設(shè)L(x)：x是演員，J(x)：x是老師，A(x,y)：x佩服y. 那么命題“所有演員都佩服某些老師”符號化為( )。A. B. C. D.24在謂詞演算中，P(a)是的有效結(jié)論，根據(jù)是 ( )。 A.US規(guī)則 B.UG規(guī)則 C.ES規(guī)則 D.EG規(guī)則25. 在圖G中，結(jié)點總度數(shù)與邊數(shù)的關(guān)系是( )。A.deg(vi)=2E B. deg(vi)=E C. D. 26. 設(shè)G是有n個結(jié)點的無向完全圖，則圖G的邊數(shù)為( )；設(shè)D是有n個結(jié)點的有向完全圖，則圖D的邊數(shù)為(

6、 )。A. n(n1) B. n(n+1) C. n(n1)/2 D. n(n+1)/227. 僅有一個孤立結(jié)點的圖稱為( )。A.零圖 B.平凡圖 C.補圖 D.子圖28. 設(shè)G為無向簡單圖，V=n，D(G)為G的最大度，則有（ ）。A. D(G)n D. D(G)n29. 圖G與G的結(jié)點和邊分別存在一一對應(yīng)關(guān)系，是GG(同構(gòu))的( )。A.充分條件 B.必要條件 C.充分必要條件 D.既非充分也非必要條件30. 設(shè)，則與V能構(gòu)成強連通圖的邊集合是( )。A.B.C.D.31. 相鄰矩陣具有對稱性的圖一定是( )。A.有向圖 B.無向圖 C.混合圖 D.簡單圖32. 無向圖G是歐拉圖，當(dāng)且僅

7、當(dāng)( )。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. mn+2 B.nm2 C.n+m-2 D.m+n+234. 設(shè)G是由5個結(jié)點組成的完全圖，則從G中刪去( )條邊可以得到樹。 A.4 B.5 C.6 D.1035. 由5個結(jié)點可構(gòu)成的根樹中，其叉數(shù)m最多為( )。A.2 B.3 C.5 D. 436. 下圖是( ) 。A.完全圖 B. 哈密頓圖 C.歐拉圖 D.平面圖h h h h h h 圖 37. 設(shè)集合A1,2,3,10,在集合A上定義的運算，不

8、是封閉的為( )。A.a,bA, a*b=lcma,b(最小公倍數(shù)) B.a,bA, a*b=gcda,b(最大公約數(shù))C.a,bA, a*b=maxa,b D.a,bA, a*b=mina,b38. 在自然數(shù)N上定義的二元運算，滿足結(jié)合律的是( )。A.ab=ab B. ab=a+2b C. ab=maxa,b D. ab=ab39. 下列代數(shù)系統(tǒng)(G,*)中，其中*是加法運算. ( )不是群。A.G為整數(shù)集合 B.G為偶數(shù)集合 C.G為有理數(shù)集合 D.G為自然數(shù)集合40. 設(shè)s1，s2，s3是三個置換，其中 s1(1 2)(2 3)(1 3),s2=(2 4)(1 4),s3=(1 3 2

9、 4)則s3可以表成( )。A. B.s1s2 C. D.s2s141. 下列圖表示的偏序集中，是格的為( )。A. B.C. D. 42. 設(shè)是布爾代數(shù)，則下式不成立的是( )。A. B. C. D.43. 布爾代數(shù)式=( )。A. B. C. D.44. 設(shè)集合A1,2，B=a,b,c,C=c,d, 則A(BC)( )。A., B., C., D.,45. 設(shè)A0,a,B=1,a,3,則AB的恒等關(guān)系是( )。A. , B., C., D. ,46. 設(shè)A=a，b，c，R=，則R具有性質(zhì)（ ）。A.自反的 B.反自反的 C.反對稱的 D.等價的47. 設(shè)集合是從A到B的函數(shù)， ，則s是(

10、)。A.雙射 B.滿射但不是單射 C.單射但不是滿射 D.非單射也非滿射48.下列式子中正確的是（ ）。A.=0 B. C.a,b D.49.有向圖的鄰接矩陣中，行元素之和是對應(yīng)結(jié)點的( )，列元素之和是對應(yīng)結(jié)點的( ) 。A.度數(shù) B. 出度 C.最大度數(shù) D.入度50. 給定無向圖如下所示，下面給出的頂點集子集中，不是點割集的是（ ）。 a f b g c h 圖d e A.b,d B.d C.e D.f,h 51 謂詞公式xA(x)xA(x)的類型是（ ）。A.永真式 B.矛盾式C.非永真式的可滿足式 D.不屬于(A),(B),(C)任何類型52. 謂詞公式取真值為1的充分必要條件是(

11、)。A.對任意y，使P(y)都取真值1 B.存在一個y0，使P(y0)取真值1 C.存在某些y，使P(y)都取真值1 D.存在y0，使P(y0)取真值053. 設(shè)G是群，當(dāng)G有（ ）個元素時，不能肯定G是交換群。A.4 B.5 C.6 D.754若集合Aa,b,c,為空集合，則下列表示正確的是( )。A.aAB.aAC.aAD.A55. 設(shè)A, B, C都是集合，如果ACBC，則有( ) 。 A.AB B.AB C.當(dāng)ACBC時,有A=B D.當(dāng)C=U時, 有AB 56. 設(shè)S1，S2, S3P(), S4P()，以下命題為假的是( )。A.S2S4 B.S1 S3， C.S4 S2 D.S4

12、 S357.設(shè)G是有6個元素的循環(huán)群，a是生成元素，則G的子集（ ）是子群。A.a B.a,e C.e,a3 D.e,a, a258.設(shè)集合A=a,b,c,d,e,半序關(guān)系R的哈斯圖如下，假設(shè)A的子集B=c,d,e,則元素c為B的（ ）。A.下界 B.最大下界C.最小上界 D.以上答案都不對59. 設(shè)Gx$yP(x,y)Q(z,w)，下面三個命題為真的是( )。A.G是前束范式 B.G不是前束范式 C.G不是一階公式 D.G是永真式60對任意集合S，SS，滿足( )。A.冪等律 B.零一律 C.同一律 D.互補律61設(shè)命題公式，則使公式G取真值為1的P，Q，R賦值分別是( )。 A. 0，0，

13、0 B. 0，0，1 C.0，1，0 D.1，0，062設(shè)a是集合A的元素，則以下正確的是( )。 A. B. C. D.63設(shè)集合A1，2，3，4，B：2，4，6，9，那么集合A，B的對稱差A(yù)B( )。 A.1，3 B.2，4，6 C.1，3，6，9 D.1，2，3，4，6，964. 有向完全圖D，則圖D的邊數(shù)是( )。 A.(E1)2 B.(一1)2 C.() D.()65設(shè)G是有n個結(jié)點，m條邊的連通阻，必須刪去G的( )條邊，才能確定G的一棵生成樹。 A.m一n1 B.n一m C.mn1D.nm166. 設(shè)N為自然數(shù)集合，在下面4種運算下不構(gòu)成代數(shù)系統(tǒng)的是（ ）。A. xy = x+y

14、2xy B.xy = x+y C. xy = xy D.xy = |x|+|y|67.已知圖G的相鄰矩陣為，則G有（ ）。A.6個點，度為4 B.5個點，度為6 C.4個點，度為3 D.4個點，度為668. 設(shè)集合A=1，2，3，10，半序關(guān)系是A上的整除關(guān)系，則半序集（A，）上的元素10是集合A的（ ）。A.最大元 B.最小元 C.極大元 D.極小元二、填空題1. 代數(shù)格（L，）中的運算和滿足的算律有_、_、_。2、A是含有3個元素的集合，在A上可以定義_個不同的等價關(guān)系。3、R是實數(shù)集合，R中的關(guān)系g= _ 從R到R的函數(shù)（填“是”或“不是”）。4、是群，|G|1，則G中的零元_。5、當(dāng)n

15、是_值時，無向完全圖Kn是歐拉圖。6、I是整數(shù)集合，代數(shù)系統(tǒng)（是通常乘法）的幺元是_, -1的逆元是_。7、元素數(shù)目不超過_的格一定是鏈。8、公式的主合取范式為_。9、的有效結(jié)論是_。10、已知公式A(p，q，r)的主合取范式為MMM，它的主析取范式為(寫成編碼形式)_。11、設(shè)A=a,b，B=0,1,2，那么可定義_種不同的從A到B的單射。12. 已知集合A=，1，2，則A的冪集合r (A)=_。13、設(shè)是分配格，若對任意的a，c，cA，如果有ab=ac，ab=ac成立，則a_b。14、僅當(dāng)n_時，Kn為平面圖。15. pq 的主合取范式是_ 。 16. 語句“我在說謊”_命題。（填“是”或

16、“不是”）。17. 設(shè)A=a,b,c,d，R是定義在A上的關(guān)系，R=, ，則r(R)= _。 18一個樹林G有三棵樹，G的頂點數(shù)是20，則G的邊數(shù)為_ 。 19P(P()=_ 。 20整數(shù)加法群中1的階是_ 。 21設(shè)有向圖D的鄰接矩陣為A(D)=，那么E 。 22. 語句“這句話是錯的” 命題。（填“是”或“不是”）。23設(shè)命題公式GP(QR)，則使G取真值為1的指派是 ， ，_。24. 已知命題公式為G(PQ)R,則命題公式G的析取范式是 。25. 公式的自由變元是 , 約束變元是 。26. 謂詞邏輯公式的前束范式是 。27. 設(shè)個體域Da,b,消去公式中的量詞，則 。28. 換名規(guī)則施于

17、 變元，代入規(guī)則施于 變元。29. 設(shè)圖G和G,若 ，則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é)點vj的 .。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條邊的

18、連通圖，要確定G的一顆生成樹，必須刪去G的 條邊. 。36. 一個有向樹T稱為根樹，若 ，其中 ，稱為樹根， 稱為樹葉. 。37. 在代數(shù)系統(tǒng)(N,+)中，其單位元是 ， 有逆元. 。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上兩個二元運算，如

19、果這兩個二元運算滿足 律， 律和 律，則(L,)是格。43. 在布爾代數(shù)中，有成立. 則該式的對偶式 也一定成立。44. 設(shè)R1，R2是集合A1,2,3,4上的二元關(guān)系,其中 R1, R2=,則R1R2 。45. 設(shè)R，S都是集合A上的等價關(guān)系，則對稱閉包s(RS)= 。46. 圖的通路中邊的數(shù)目稱為 . 結(jié)點不重復(fù)的通路是 通路. 邊不重復(fù)的通路是 通路。47. 將謂詞公式中的約束變元換名_。48. 寫出下列集合的子集：B= ;C=_。49設(shè)全集合E1,2,3,4,5,A=1,2,3,B=2,5,AB= ,B= 。AB= 。50. 設(shè)A, B代表集合，命題A-B=A=B的真值為 。51. 設(shè)

20、集合Aa,b,c,B=a,b,那么P(A)P(B)= ，P(B)P(A)= 。52設(shè)A=, 選擇適當(dāng)?shù)姆柼钤诟餍☆}的橫線上.（1）(1,2,3,4) N; (2) 。53關(guān)于格的命題P：a(bc)，求P的對偶命題P*=_。54計算Z6的所有理想_。55求的真值_。56判定公式(PQ)(RQ)(P R)Q)的類型_。57. 將命題公式化為只含和的盡可能簡單的等值式_。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=_。60. 設(shè)集合A中有4個元素,則A上的不同的等價關(guān)系的個數(shù)為_個。三、判斷題

21、1. 空間中的平行六面體是平面圖。（ ）2、每個頂點的度都是偶數(shù)的無向圖一定是歐拉圖。（ ）3、頂點數(shù)目相同，邊數(shù)也相同的兩個無向圖一定同構(gòu)。（ ）4、函數(shù)的逆關(guān)系還是函數(shù)。（ ）5、A，B，C都是集合，如果AB=AC，則B=C。（ ）6、設(shè)R是環(huán)，A,B是R的兩個理想，且B包含于A,則A/B是R/B的理想，并且R/B /(A/B)同構(gòu)于 R/A。（ ）7. 的對偶是 。（ ）8. 設(shè)G是有r個面的連通平面圖，頂點數(shù)和邊數(shù)分別是n和m，則n-m+r=2 。（ ）9. n階有向完全圖有n（n-1）條邊。（ ）10. 在代數(shù)系統(tǒng)中，若，則 。（ ）11. 設(shè)無向圖T是樹，則T中一定沒有簡單回路。（

22、 ） 12. 能夠畫在一張平面上的圖是平面圖。13. 設(shè)是代數(shù)系統(tǒng)，B是S的非空子集，則是的子代數(shù)。（ ）14. 循環(huán)群的子群仍然是循環(huán)群。（ ）15. 格不一定是布爾代數(shù)。（ ）161+101=110是命題 。（ ）17“全體立正是命題” 。（ ）18“明天是否開大會？”是命題 。（ ）19“如果天氣好，那么我去散步”是命題。（ ）20. 判斷(Z,)是否為格？其中是數(shù)的小于或等于關(guān)系。（ ）21設(shè) R是實數(shù)集，“”為數(shù)的加法，“”定義為. 試問R對二元運算和是否構(gòu)成環(huán)。（ ）22. 設(shè)集合A18的正整數(shù)因子，為整除關(guān)系，說明是否是偏序關(guān)系。（ ）23是對的。（ ）24是的子集。（ ） 25

23、如果STSM，則TM。（ ）26. 已知S2,a,3,4,R=a,3,4,1,則aS。（ ）27. 整數(shù)集合Z和普通的減法運算是封閉的。（ ）28在R中定義二元運算：* ,a*b=a+b+ab,對于任意a,b 屬于 R，則是獨異點。（ ）29整數(shù)集合1,2,3,4,6,12關(guān)于整除關(guān)系構(gòu)成了偏序集，并且該偏序集是格。（ ）四、證明題1. 設(shè)是群，具有幺元e，如果對G的任意元素a，都有a=e, 則是交換群2. 形式證明3. 證明：P(QR)PQR.4試證明：5試證明：6. 證明：7設(shè)G是圖，無回路，但若外加任意一條邊于G后，就形成一回路. 試證明G必為樹. 8. 設(shè)B是任意集合，試驗證(P(B)

24、,)是群. P(B)是集合B的冪集，是集合的對稱差運算， 9給定代數(shù)系統(tǒng)(G,+,*), 二元運算見表一，表二. 表一 表二 +abcD *abcDAabcDaaaaaBbadCbabcdCcDaBcacdbDdCbAdadbc證明(G,+,*)是域. 10. 證明如果非空集合A上的二元關(guān)系R和S是偏序關(guān)系，則也是A上的偏序關(guān)系11試證A(BC)(AB)(AC)12設(shè)非空集合A，驗證()是布爾代數(shù)，13. 試證明屬于關(guān)系不滿足傳遞性，即對于任意的集合A,B,C若AB且BC 不一定有AC14設(shè) A,B為兩個集合，證明 AB=A當(dāng)且僅當(dāng)AB= 15. 設(shè)R,S都是非空集合A上的二元關(guān)系，且他們是對

25、稱的，證明：RoS具有對稱性當(dāng)且僅當(dāng) 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, (G)=n-2，證明G的邊數(shù)m2n-419V=是可交換半群,若a,b S是V中得冪等元，證明a*b也是V中的冪等元20設(shè) L是格，證明對于任意a,b,c,dL有：( ab)(cd)(ac)(bd)五、計算題 1. 無向樹T有2個2度頂點，1個3度頂點，3個4度頂點，其他的都是樹葉，問T中有多少片樹葉？2. 設(shè)公式

26、 ，其中P(x)：x2，Q(x)：x=0，F(xiàn)是永假式，個體域是1，2，求公式A(x)的真值3. 設(shè)集合X=1，2，3, 4，X中的關(guān)系為F=，寫出F的關(guān)系矩陣及其關(guān)系圖，F(xiàn)有哪些性質(zhì)？4. (1) n(n1)階無向完全圖與有向完全圖各有多少條邊?為什么？(2)完全二部圖K中共有多少條邊?為什么？(3) 每個頂點的度都為k的無向圖稱為k正則圖，問：n階k正則圖中共有多少條邊?為什么？5. 設(shè)集合L=a，b，在L中規(guī)定 + 和如下：a+a=a，a+b=b+a=b，b+b=baa=a，ab=ba=a，bb=b問能構(gòu)成代數(shù)系統(tǒng)嗎？若可以，寫出該代數(shù)系統(tǒng)的運算表。該代數(shù)系統(tǒng)有什么特性？6. 設(shè)多重集A=

27、，1，1，1， B=，1，1.計算AB，AB，A-B7. 設(shè)集合M=1，2，3，4，5，s 和t 是M上的兩個置換，s =，t =（1 4 5）（2 3），用輪換的形式寫出s t，ts，t1is 1。8. 對集合L，規(guī)定對于x，yL，xy當(dāng)且僅當(dāng)x是y的因子。問下面哪幾個偏序集是格?為什么？(1)L=1, 2, 3, 4, 6, 12(2)L=1, 2 , 3, 48, 12, 14(3)L=1, 2, 3, 4, 5, 6, 7, 8, 9, 109 在全總個體域中符號化下列命題。（1）是金子總是要發(fā)光的。（2）并非所有微笑的人都是高興的。（3）平面圖的色數(shù)不超過410 若無向圖G是歐拉圖，

28、G中是否存在割邊?為什么?11. 設(shè)集合，R是定義在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=,Y=,。問有多少個不同的由X到Y(jié)的關(guān)系？有多少個不同的由X到Y(jié)的函數(shù)？當(dāng)n,m滿足什么條件時，存在單射，且有多少個不同的單射？ 14在全總個體域中符號化下列命題。（1）在中國工作的人并非都是中國人。（2）有的人在微笑但內(nèi)心不高興。（3）每種金屬都可以

29、溶解在某種液體種。15. 將下列命題符號化：(1) 雖然交通堵塞，但是老王還是準(zhǔn)時到達火車站； (2) 張力是三好學(xué)生或優(yōu)秀共青團員(3) 老李或小刁中有一個人去廣州出差16. 判定公式PQ與PQ是否等值.17 用等值演算法判定公式P(QR)PQR是永真式？永假式？18求公式的主合取范式和主析取范式.19. 化簡下式： (ABC)(ABC)20 設(shè)命題P,Q的真值為0，命題R,S的真值為1，求命題公式的真值.21 將下列命題符號化：（1）每個母親都愛自己的孩子；(2) 所有的人都呼吸；(3) 有某些實數(shù)是有理數(shù). 22指出下列公式 中量詞的每次出現(xiàn)轄域，并指出變元的每次出現(xiàn)是約束出現(xiàn)，還是自由

30、出現(xiàn)，以及公式的約束變元，自由變元. 23給定解釋I： D2,3; D中特定元素a=2； 函數(shù)為 謂詞F(x)為F(2)=0,F(3)=1G(x,y)為G(2,2)=G(2,3)=G(3,2)=0,G(3,3)=1L(x,y)為L(2,2)=L(3,3)=1,L(2,3)=L(3,2)=0求在解釋I下各公式的真值. (1) ;(2) ；24討論公式的類型.25將公式F 化為前束范式.26. 判定下面二圖是否同構(gòu)？ 27. 設(shè)G(V,E)是一個無向圖， (1) 畫出G的圖解；(2) 指出與v3鄰接的結(jié)點，以及與v3關(guān)聯(lián)的邊；(3) 指出與e1關(guān)聯(lián)的結(jié)點；(4) 該圖是否有孤立結(jié)點和孤立邊？(5)

31、 求出各結(jié)點的度數(shù)，并判斷是不是完全圖？(6) G的V，E各是多少？28. 給定下列六個圖(如圖)，G1,其中V1=a,b,c,d,e,E1=(a,b）,(b,c),(c,d),(a,e)G2,其中V2=V1,E2=(a,b),(b,e),(e,b),(a,e),(d,e)G3,其中V3=V1,E3=(a,b),(b,e),(e,d),(c,c)G4,其中V4=V1,E4=,G5,其中V5=V1,E5=,G6,其中V6=V1,E6=, al a l a l a l a l a l bl le bl le bl l e b l l e b l l e bl l e cl ld cl ld cl

32、l d cl ld cl ld cl ld (G1) (G2) (G3) (G4) (G5) (G6) 圖試問：(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

33、中，需要刪去多少條邊才能得到樹. 32畫出具有下列條件的有 5個結(jié)點的圖. (1) 沒有哈密頓回路，也不能適當(dāng)指定各邊的方向，使其具有歐拉回路；(2) 有哈密頓回路，但是不能適當(dāng)指定各邊的方向，使其具有歐拉回路；(3) 沒有哈密頓回路，但是能適當(dāng)指定各邊的方向，使其具有歐拉回路； (4) 有哈密頓回路，也能適當(dāng)指定各邊的方向，使其具有歐拉回路. 33. 通常數(shù)的加法運算可看作正整數(shù)N上的二元運算. 下列集合是N的子集，加法運算在這些子集上封閉嗎？為什么？(1) (2) (3) 34. ；運算*是否有單位元和冪等元？若有單位元的話，哪些元素有逆元？ 35. 是布爾代數(shù)，化簡. 36. 設(shè)是定義在

34、Z5(0,1,2,3,4)上的多項式(即系數(shù)是Z5的元素的多項式)，試計算P(x)+Q(x)，P(x)Q(x).37. 回答下列代數(shù)系統(tǒng)是環(huán)嗎？是交換環(huán)嗎？(1) (Zm,，*),其中Zm0,1,2,m1，和*是模m加法和乘法. (2) (Mn(R)，), 其中Mn(R)是n階實矩陣全體，分別是矩陣的加法和乘法.38. 設(shè)集合Aa,b,R是P(A)上的包含關(guān)系，寫出R的表達式和關(guān)系矩陣.39. 設(shè)A1,2,3,用列舉法給出A上的恒等關(guān)系IA，全關(guān)系EA，A上的小于關(guān)系 及其逆關(guān)系和關(guān)系矩陣. 40. 設(shè)A1,2,3,4, R是A上的二元關(guān)系，其關(guān)系矩陣為試求 (1) R的關(guān)系表達式； (2)

35、Dom(R)和Ran(R)；(3) RR中有多少個有序?qū)?(4) R1的關(guān)系圖中有多少條自回路?41. 設(shè)集合判定下列關(guān)系，哪些是自反的，對稱的，反對稱的，傳遞的？42. 設(shè)A1,2,3,4,5,6,定義A上的二元關(guān)系 R, ,(1) 判定R是否為等價關(guān)系？ (2) 若是等價關(guān)系，寫出A的關(guān)于R的等價類.43. 設(shè)集合Aa,b,c,d,定義R,求r(R),s(R),t(R). 44求謂詞公式的真值其中P：43，Q（x）：x1，R（x）：x2f（-3）=1，f（1）=5，f（5）= -3a：5個體域D=（-3，1，5）45化簡46設(shè)集合 A=a,b,B=1,2,3,C=d,求(AB)C，ABC，

36、BA. 47用列舉法表示以下集合：(1) ； (2) ;(3) 48. 列出下列集合的各元子集，并求冪集（1）A=a,b,c (2) A=1,2,3 (3)A=, 49. A=a,b,c,B=1,2,令a1=P(A),a2=A-B, 構(gòu)造一個a1到a2的雙射函數(shù)，再構(gòu)造一個a2到a1的雙射函數(shù) 50. 由f:A-B導(dǎo)出A上的等價關(guān)系定義為： R=|xA yA f(x)=f(y) 設(shè)f1,f2,f3,f4NN且 f1(n)=n f2(n)= 1 n為奇數(shù) f3(n)=0 n為偶數(shù) f3(n)=j,n=3k+j,j=0,1,2,kN f4(n)=j,n=6k+j,j=0,1,5,kN Rk為fk導(dǎo)

37、出的N上的等價關(guān)系,k=1,2,3,4 1) 求商集N/Rk k=1,2,3,4 2) 求H=10k|kN 在f1,f2,f3,f4 下的象！ 51對圖給出的二叉樹分別進行先根遍歷、中根遍歷和后根遍歷。更多課程資料請到大學(xué)課程網(wǎng)學(xué)習(xí)測 試 題 答 案離散數(shù)學(xué)一、選擇題 1. A 2. C 3. C 4. A. 5. D 6. C 7. D 8. C 9. D 10. D 11.B 12. D 13. B 14. B 15. B 16.B 17.C 18.B 19.A 20.D 21.C 22.A 23.D 24.A 25.C 26.C,A 27.B 28.A 29.B 30.A 31.B 32

38、.C 33.A 34.C 35.D 36.B 37.A 38.C 39.D 40.D 41.C 42.D 43.B 44.B 45.C 46.A 47.B 48.D 49.B,D 50.A 51.B 52.A 53.D 54.B 55.C 56.A 57.C 58.C 59.B 60.C 61.D 62.B 63.C 64.D 65.A 66.A 67.D 68.C 二、填空題1. 交換律、結(jié)合律、吸收律 2. 5 3. 不是4. 不存在5. 奇數(shù)6. 1, -17. 38. 9. R 10. m1m2m4m6m711. 612、r(A)=，1，2，1，2，1，2，A13、= 14、奇數(shù)15.

39、 16. 不是17、,18、1719、，20、無限21、722. 不是23. (1,0,0,) (1,0,1) (1,1,1)24. PQR25. y,x x,z26. 27. 28. 約束 自由29. 30. 自反性 對稱性 傳遞性 等價. 31. 出度 入度32. 14 28 7 6 33. D中每個結(jié)點的入度出度.34. 大于或等于n35. m+1n36. 若有向圖T恰有一個結(jié)點的入度為0，其余結(jié)點入度為1 入度為0的結(jié)點 入度為1的結(jié)點.37. 0 僅有單位元0.38. A.39. (1 2 3)(5 6) (1 3)(1 2)(5 6)(不唯一)40. 4 a，a541. (L,) 半群 二元運算對運算42. 交換律 結(jié)合律 吸收律43. 44. ,45. RS46. 通路出度 初級 簡單.47. ， 4