離散數(shù)學(xué)復(fù)習(xí)題

1、離散數(shù)學(xué)復(fù)習(xí)題一、 單項選擇題1. 下列句子是原子命題的是 （ A ）A. 大熊貓產(chǎn)在我國；B. 2+x=5; C. 小王和小李是學(xué)生；D. 別講話了！2. 設(shè)p：天下雨，q：我去新華書店，命題“除非天不下雨，我去新華書店”的符號化形式為 （ D ）Apqqpqp pq3. 以下命題不是重言式的有 （ A ）A. PP B. PP C. (PQ)(QP) D. PPQ4. 以下語句中不是命題的為 （ B ）A明天我要上門去謝你。謝謝你給了我機會。 如果不說，我就不謝你。除非你做了，我才謝你5與Ø($x) M(x) 等價的是 （ D ）A("x) M(x)($x) Ø

2、;M(x)("x) M(x)("x) ØM(x)6. 設(shè)P(x)為“x是大學(xué)生”，Q(x)為“x滿30歲”。命題“所有大學(xué)生都不滿30歲”寫成謂詞公式為 （ C ）A. x(P(x)Q(x) B. x(P(x)Q(x) C.x(P(x)Q(x) D. x(P(x)Q(x)7.公式 ("x) (P(x)("y)R(x, y)中，"x的轄域為 （ B ）AP(x)(P(x)("y)R(x, y) P(x)和R(x, y)P(x)("y)8設(shè)S=a, b, c,則S的冪集的元素的個數(shù)有 （ C ） A3 6 . 899以

3、下等式中不正確的是： ( A )AA(B×C)=(AB)×(AC)A×(BC)=(A×B)(A×C) （AB)×C=(A×C)(A×C)(A×B)×C=A×(B×C)10設(shè)A=1, 2, 3, 4, A上的等價關(guān)系R=<1, 2>, <2, 1>, <3, 4>, <4, 3>IA, 則對應(yīng)于R的A的劃分是 ( D )A1,2, 3, 41, 2,3, 4 1,2, 3, 41,2, 3, 411設(shè)函數(shù) f：1，21，則f是 (

4、 B ) A入射B滿射C雙射D非入射非滿射 12設(shè)Z是負(fù)正整數(shù)集合，+，*，是普通數(shù)的加法、減法和平方運算，則能構(gòu)成代數(shù)系統(tǒng)是 ( B )A< Z, +> < Z, > < Z, *>< Z, >13若 他聰明， 他用功，則“他雖聰明但不用功”，可符號化為 （ B ）A. B. C. D. 14. 若一個代數(shù)系統(tǒng)(A，*)滿足運算封閉性及結(jié)合律，且有幺元，則它是 ( A )A獨異點 B群C格  D布爾代數(shù)15設(shè)G為無限群，則 ( C ) A G是交換群 G是循環(huán)群 G中每個元素都有逆元G中每個元素的階都是無限的 16

5、在有3個結(jié)點的圖中，度數(shù)是奇數(shù)的結(jié)點的個數(shù)為 ( D )A13. 1或30或217在5階圖G中，若從結(jié)點v1到v4存在路，則從v1到v4的路中必存在路，其長度小于等于 ( D )A12. 34 18連通平面圖G的面的次數(shù)之和為10，則其邊數(shù)為 ( A )A510. 152019. 在自然數(shù)集合上，下列哪種運算不是可交換的 （ D ）A. B. C. D. 20. 設(shè)簡單圖的最大結(jié)點度數(shù)為，圖的結(jié)點數(shù)為,則與的關(guān)系為 ( B )A. B. C. D. 與沒關(guān)系21下列各項中錯誤的是（ A ）A B C D22設(shè)，下列各式成立的是（ C ）A B C D23連通平面圖中，所有面的次數(shù)之和是 （ C

6、 ）A邊數(shù) B邊數(shù)的一半 C邊數(shù)的兩倍 D邊數(shù)的一倍24無向圖 具有一條歐拉回路，那么圖 的所有結(jié)點的度數(shù)都是（ B ）A奇數(shù) B偶數(shù)C素數(shù) D125. 下列集合哪個是最小聯(lián)結(jié)詞集 （ D ）A. B. C. D. 26. 設(shè)簡單圖的最大結(jié)點度數(shù)為，圖的結(jié)點數(shù)為,則與的關(guān)系為 （ B ）A. B. C. D. 與沒關(guān)系27. 設(shè)集合A=1,2,3，B=2,3,4,5，C=2,4,8,16,D=1,2,3,4,設(shè)“|”是集合上的“整除”關(guān)系，則下列偏序集中能構(gòu)成格的是 （ C ）A. <A,|>B. <B,|>C. <C,|>D. <D,|>28設(shè)

7、 上的二元關(guān)系,則關(guān)系具有的性質(zhì)是哪一個 （ B ）A. 自反性B. 對稱性C. 傳遞性D. 反對稱性29判斷下列各式中不是合式公式的是哪一個 （ C ）A. B. C. D. 30. 代數(shù)系統(tǒng)(S,)中以下斷言正確的是 （ C ）A. 單位元與零元總是不相等； B. 可能有二個左單位元和一個右單位元；C. 單位元總有逆元； D. 若S'S，則(S',)是(S,)的子代數(shù)31. 指出下列語句中哪個是原子命題 （ A ）A. 蘇州是中國的首都。B. 王強不但聰明而且用功。C. 明天下午我乘Z86次或K256次列車去北京。D. 如果天不下雨，我就騎車上班。32. 設(shè)，則下列哪個集合

8、是從的函數(shù)（ C ）A. B. C. D33. 在謂詞演算中，下列各式正確的是 （ A ）A. B. C. D. 34. 設(shè)（A,+, ）是整環(huán)，則以下斷言錯誤的是 （ D ）A. （A,+）是阿貝爾群 B.（A,）是可交換獨異點 C. 運算對可分配 D.（A,）有零因子35. 以下格是分配格的是 （ C ）A. 鉆石格 B. 五角格 C. 小于5個元素的格 D. 含與鉆石格同構(gòu)的子格的格36. 指出下列語句中哪個是復(fù)合命題 ( C )A. 5是奇數(shù) 。B. 蘇州是中國的首都。C. 如果天不下雨，我就騎車上班。D. 火星上有生物。37前提的結(jié)論是 （ A ）A. B.C. D.38謂詞公式中變

9、是 （ C ）A.自由變元 B.約束變元C.既是自由變元又是約束變元 D.既不是自由變元又不是約束變元39. 公式(x)(y)(P(x,y) Q(x,y) (x)P(x,y)中(x)的轄域是 （ B ）A. P(x,y) B. P(x,y)Q(x,y) C. Q(x,y) D. (P(x,y) Q(x,y)(x)P(x,y)40. 以下符號串不是合式公式的是 （ B ）A. PPQ B. (PQ)(QP) C. PPS D. P(PQ)Q41公式中 的轄域為 （ C ）A. B. C. D. 42若 今天下雪了； 路滑；則“雖然今天下雪了，但是路不滑”，可符號化為 （ D ）A. B. C.

10、D. 43. 設(shè)上的二元關(guān)系,則等于是(B ）A. B. C. D. 44. 指出下列語句中哪個是命題 （ D ）A. 這本書真好看啊！B. 上課請不要遲到！C. 你吃午飯了嗎？D. 李白是唐朝的詩人。45. 設(shè)A=1,2,3,4,5,6,7,8,式子為真是 （ C ）A. 1 A; B. 1,2,3 A; C. 4,5 A; D. ø A.46. 設(shè) A=a,b,c 上的關(guān)系如下, 有傳遞性的為 （ D ）A. A1=<a,c>,<c,a>,<a,b>,<b,a> B. A2=<a,c>,<c,a> C. A3

11、=<a,b>,<c,c>,<b,a>,<b,c> D. A4=<a,a> 47. 集合A上的等價關(guān)系R, 其等價類的集合稱為 （ C ）A. A與R的并集, 記作 A R B. A與R的交集, 記作 A R C. A關(guān)于R的商集, 記作 A/RD. A與R的差集, 記作 A-R.48設(shè)是連通平面圖，中有6個頂點8條邊，則的面的數(shù)目是 （ C ）A2個面B3個面 C4個面D5個面49. 設(shè)A = 1,2,3,4 , A上關(guān)系R1 = (1,2),(2,3),(3,4),(4,1), R2 = (1,2),(2,3), (3,2), 則中

12、是映射的為 （ B ）A. R1,R2; B. R1; C. R2; D. 沒有50. 設(shè)N是自然數(shù)集，a,bN使(N,*)不是半群的運算是 （ D ）A. a*b=max(a,b) B. a*b=min(a,b)C. a*b=a+b+2 D. a*b=a+2b51. 由n個點0條邊組成的圖稱為 （ A ）A. 零圖 B. 平凡圖 C. 完全圖 D. 多重圖52. 給定下列序列, 哪一個不能構(gòu)成無向簡單圖的結(jié)點度數(shù)序列 （ D ）A. (1,1,2,2,4) B. (1,1,2,2,2,) C . (2,1,3,3,3) D. (1,3,4,4,5)53設(shè)是個結(jié)點，條邊和個面的連通平面圖，則等

13、于 （ A ）ABCD54無向圖具有一條歐拉回路，那么它們所有結(jié)點度數(shù)是 （ A ）A偶數(shù)B奇數(shù)C素數(shù) D155. 設(shè)的真值為0，的真值為1，則下列命題公式中真值為1的是 （ D ）A. B. C. D. 56. 下列各式中永真式是 （ A ）A. B. C. D. 57設(shè)，雪是黑的，太陽從東方升起，下列命題為真的是 （ A ）A. B. C. D. 58下面集合關(guān)于整除關(guān)系構(gòu)成格的是哪一個 （ C ）A.2，3，6，12 B.3，6，9，12C.1，3，5，6，15，30 D.6，12，24，3659個結(jié)點的無向完全圖的邊數(shù)為 （ D ）A BC D60設(shè)是任意三個集合，下列結(jié)論正確的是 （

14、 A ）A若且，則 B若且，則C若且，則 D若且，則61在一個有4個元素的集合上，可以有不同關(guān)系的個數(shù)為 （ D ）ABCD62設(shè)為整數(shù)集，下面那個序偶不構(gòu)成偏序集 （ A ）A（<：小于關(guān)系）B（：小于等于）C（：等于關(guān)系）D：整除關(guān)系）63給定上的關(guān)系為，則滿足的性質(zhì)是 （ C ）A自反的B對稱的C傳遞的D不可傳遞的64指出下列語句中哪個不是命題 （ C ）A. 3+2=5。 B. 北京是中國的首都。C. 請勿吸煙！ D. 李白是唐朝的詩人。65. 命題公式A與B是等價的是指 （ D ）A. A與B有相同的原子變元B. A與B是可滿足的C. 當(dāng)A的真值為真時，B的真值也為真D. A與

15、B有相同的真值66下列等值式不正確的是 （ C ）A. B.C. D.67下列各式中，哪個不成立 （ A ）A. B. C. D. 68設(shè)是演員，是老師， 欽佩 ，命題“所有演員都?xì)J佩某些老師”符號化為 （ B ）A. B. C. D. 69設(shè)為任意集合，則下列等式不成立的是 （ C ）ABCD70下列式子正確的是 （ B ）A B C D71已知集合，上的兩個二元關(guān)系，則為 （ A ）ABCD72已知集合上關(guān)系，則等于 （ B ）AB CD73已知集合，為上的整除關(guān)系，則的極小元是 （ A ）A1 B2 C3D4 74設(shè)有函數(shù)和，且有，則復(fù)合函數(shù)是 （ B ）A BCD 75含5個結(jié)點，4條

16、邊的無向連通圖（不同構(gòu)）的個數(shù)為 （ B ）A1 B3 C6 D7 二、 填空題1. 設(shè)，如果為集合的一個覆蓋，要使成為的一個劃分，那么必須滿足 AiAj = (i,j=1,2,3,m,ij) 。2. 合式公式（x）F(x) G(x,y)中 變元y是_自由_變元.（填自由或約束） 3. 設(shè)Mx | (x是整數(shù)) (1x12) (x被2整除) ,N=x | ( x是整數(shù)) (1x12) (x被3整除) ， 則MN=_6,12_。4. 若集合A有n個元素，則冪集(A）中有_2 n _個元素。5. 若集合中有201個元素，則的子集有 2201 個。6. 一個命題公式如果_若在它的各種指派下，取值均為

17、假_，則稱它為矛盾式。7. 不含多重邊和 環(huán) 的圖，稱為簡單圖。8. 任意兩個大項的析取為 永真 。9. 在根樹中，若每個結(jié)點的出度 小于等于m ，則稱這棵樹為叉樹。10. 設(shè)集合A=1,2, B=3,4, C=5,6, 則A×B×C _(1,3,5),(1,3,6),(1,4,5),(1,4,6),(2,3,5),(2,3,6),(2,4,5),(2,4,6)_.11. 為兩個命題，當(dāng)且僅當(dāng) P為真，Q為假時 ，為假。12. 是 可滿足 式（填永真，永假或可滿足）。13. 如果一個獨異點滿足 A中每個元素存在逆元 ，則為群。J8814. 一個映射，如果對任意，若，則有 f

18、(xi)f(xj) ，則此映射叫從 到的入射。15. 在公式，量詞的轄域是。16. 量詞與否定聯(lián)結(jié)詞之間有以下關(guān)系：Ø"xQ(x) Û$xØQ(x) 。17. 設(shè)A=1，2，B=1，2，則A與B 相等 （相等、不相等）。18. 在數(shù)理邏輯中, 規(guī)定聯(lián)結(jié)詞,的優(yōu)先次序是 _, ,_. 19. 設(shè)P,Q是兩個命題，德摩根定律可表示為_ (PQ) PQ, (PO) PQ _。20. 設(shè)，的冪集。21. 99M=(aij)是無向圖G(V,E)的鄰接矩陣，V=v1,v2,vn, Mk中的第i行j列的元素值表示_結(jié)點vi到vj的長度為k的路徑的數(shù)目 25.5_。22

19、. 若某連通簡單平面圖有4個頂點，3 個區(qū)域，則有_5_條邊。23. 在根樹中，如果每一個結(jié)點的出度恰好等于 或零，則稱這棵樹為完全叉樹。24. 是 永真 式（填永真，永假或可滿足）。25. 一個命題公式稱為合取范式，當(dāng)且僅當(dāng)它具有型式： A1A2An ，其中A1，A2，An都是由命題變元或其否定所組成的析取式。26. 在公式中，量詞的轄域是 。27. 有集合與，則的充分必要條件是 AB 且BA 。28. 若關(guān)系是反對稱的，當(dāng)且僅當(dāng)關(guān)系矩陣中以主對角線為對稱的元素不能同時為 1 。29. 設(shè)為自然數(shù)集，若，則是 雙 射的。30. 若集合中有101個元素，則的冪集中有 2101 元素。31. 如

20、果一個獨異點滿足 A中每個元素存在逆元 ，則為群。32. 給定集合上的關(guān)系，若是 自反的 、對稱的，則稱是上的相容關(guān)系。33. 若和是滿射的，則是 滿射 。34. 在一個有個元素的集合上，可以有 種不同的函數(shù)。35. 代數(shù)系統(tǒng)如果對內(nèi)的任意元素均有 (a*b)*c=(a*b)*c ，則稱此代數(shù)系統(tǒng)中的運算“*”對是可結(jié)合的。36. 無向圖G具有一條歐拉圖，當(dāng)且僅當(dāng)G是連通的且_有零個或兩個奇數(shù)度結(jié)點_.37. 個結(jié)點的無向完全圖的邊數(shù)為。38. 任意兩個大項的析取為永真，全體大項的合取為 永假 。39. 命題“如果1+1=0，則明天太陽在東邊落下”的真值為T 。40. ( PÙ

21、16;P) ®(QÙØ Q )Ù ØR ) 是永假 式。41. 設(shè)R，Q都是集合A上的等價關(guān)系，則s(RQ)=RQ 。42. 設(shè)為根樹，若每個結(jié)點的出度都小于等于，則稱為 叉樹。43. 設(shè)<G, *>是群，H是G的非空子集，H是G的子群當(dāng)且僅當(dāng)a*b-1ÎH 。44. 若<A，b>是一個偏序集 ，且A中任意兩個元素都有最小上界和最大下界，則A是格。45. 8個結(jié)點的無向完全圖的邊數(shù)為28 。46. 為兩個命題，當(dāng)且僅當(dāng) P、Q同時為真 ，為真。47. 設(shè) 則= 2,3,4,5 。48. 存在 歐拉 回路的圖，稱

22、為歐拉圖。49. 在根樹中，入度為零的結(jié)點稱為 根 。三、 名詞解釋1. 集合的對稱差：設(shè)A和B為任意兩個集合，A和B的對稱差是由或者屬于A，或者屬于B，但不能既屬于A又屬于B的元素所組成的集合。2. 復(fù)合命題：由聯(lián)結(jié)詞、標(biāo)點符號和原子命題復(fù)合構(gòu)成的命題。3. 是集合A上的全序關(guān)系：設(shè)是集合A上的二元關(guān)系，如果對于A中任意兩個元素a,bA，必有ab或ba，則稱是A上的全序關(guān)系。4. 強連通圖：在簡單有向圖G中，任何一對結(jié)點的兩者之間相互可達(dá)，則稱G為強連通圖。5. 重言式：給定一命題公式，若無論對分量作怎樣的指派，其對應(yīng)的真值永真.6. 阿貝爾群：如果群<G，* >中的運算*是可交

23、換的，則稱該群為阿貝爾群。 7. 自反閉包：設(shè)R是一個二元關(guān)系，如果存在一個關(guān)系滿足：是自反的；對于任何自反關(guān)系如果有就有。則稱為R自反閉包。8. 命題公式A和B是等價的：設(shè)P1,P2,Pn為所有出現(xiàn)在A和B中的原子變元, 若給 P1,P2,Pn的任一組指派, A和B的真值都相等, 稱A和B是等價的.9. 子群：設(shè)是一個群，S是G的非空子群，如果也構(gòu)成群，則稱是的一個子群。10. 半群<S,*>：<S,*>是代數(shù)系統(tǒng)，*是集合S上的二元運算，若運算*是封閉的，并且*是可結(jié)合的，則稱<S,*>是半群。11. 無向圖簡單圖G的鄰接矩陣：設(shè)無向圖G有n個結(jié)點v1,

24、v2,vn, 無多重邊，定義n×n階矩陣M=(mij)是G的鄰接矩陣，其中12. 約束變元的換名：對公式中的約束變元，遵照一定規(guī)則更改名稱符號，稱為約束變元的換名。13. 單側(cè)連通：在簡單有向圖中,任何一對結(jié)點間,至少有一個結(jié)點到另一個結(jié)點是可達(dá)的,則稱這個圖是單側(cè)連通的。14. 歐拉回路：給定有向圖G，通過圖中每邊一次且一次的一條回路稱作歐拉回路。15. 二元關(guān)系：設(shè)A、B是任意集合，A×B的子集R稱為從A到B的二元關(guān)系，當(dāng)A=B時，稱R為A上的關(guān)系。16. 相容關(guān)系：給定集合A上的關(guān)系R，若R是自反的、對稱的，則稱R為A上的相容關(guān)系。17. 漢密爾頓圖：給定圖G，若存在

25、一條回路，經(jīng)過圖中的每個結(jié)點恰好一次，這條回路稱為漢密爾頓回路。具有漢密爾頓回路的圖稱作漢密爾頓圖。18. 集合A上的擬序關(guān)系：設(shè)R是集合A上的一個關(guān)系，若R滿足反自反性和傳遞性.19. 對稱關(guān)系：設(shè)R為X上的關(guān)系，對于每一個，每當(dāng)時，就有，則稱R為X上的對稱關(guān)系。20. 等價關(guān)系：一個二元關(guān)系若滿足自反性，對稱性和傳遞性稱為等價關(guān)系。21. 對稱閉包：設(shè)R是一個二元關(guān)系，如果存在一個關(guān)系滿足：是對稱的；對于任何對稱關(guān)系如果有就有。則稱為R的對稱閉包。22. 圖：圖是三元組，其中是一個非空的結(jié)點集合，是邊集合，是從邊集合E到結(jié)點無序偶（有序偶）集合上的函數(shù)。23. 樹：連通且無回路的無向圖稱為

26、樹。24. 格：給定偏序集合<A , >，若A的任意子集均存在最小上界和最大下界，稱<A , >為格。25. 命題公式的對偶式：命題公式A中含聯(lián)結(jié)詞，將互換，T與F互換所得公式A*稱為A的對偶式。四、 解答題1. 已知"y(R(y) ÚB(y)，其中R(3)= B(4)=T，R(4)= B(3)=F，且論域是3, 4，求該式的真值。解："y(R(y) ÚB(y) Û(R(3) ÚB(3) Ù(R(4) ÚB(4) Û(T ÚF) Ù(FÚT) 

27、9;T 2. 下列句子中哪些是命題？1 她能歌善舞。2 如果我有時間，我就來看你。3 你喜歡看電影嗎？4 小王今年20歲或21歲。5 別講話了！6 小王和小李是同學(xué)。解：是命題分別為1、2、4。3. 試求公式：PÙ(P ®Q ) 的析取范式和合取范式。解：PÙ(P ®Q ) Û PÙ(ØPÚQ)合取范式 Û (PÙØP) Ú (PÙQ) 析取范式 4. 設(shè)A是18的除1以外的正因數(shù)組成的集合，“|”為整除關(guān)系，畫出（A，|）的哈斯圖；若存在的話，分別求出其最大元、最

28、小元，極大元，極小元，上確界，下確界，上界和下界。解：（2分）最大元、極大元，上確界和上界為18；極小元為2，3；沒有最小元，下確界和下界。5. 求表達(dá)式：(a+b×c)÷d-e(f-g)的樹形表示。解： 6. 在一階邏輯中，將下面命題符號化，并且要求只能使用全稱量詞：（1） 沒有人長著綠色頭發(fā)。（2） 有的上海市民沒有去過東方明珠塔。解：（1） 設(shè)M（x）：x是人，B（x）：x長著綠色頭發(fā) 則命題（1）可表示為：（2） 設(shè)M（x）：x是上海市民，B（x）：x去過東方明珠塔； 則命題（2）可表示為：7. 給定有向圖G=<V, E>如下：試求：（1）各頂點的出、入

29、度； (2) 寫出 G 的鄰接矩陣 ； （3）利用矩陣計算求出從頂點1到4長度分別為1，2和3的路各有幾條。解：（1） 結(jié)點 1 2 3 4 結(jié)點的出度 2 2 2 1 結(jié)點的入度 0 3 1 3 （2）鄰接矩陣：（3）因為：所以從頂點1到4長度分別為1，2和3的路分別有1、1、2條。8. 設(shè)的關(guān)系為：，求以及。解：設(shè)則， 故， 有 9. 設(shè)G=（a）為6階循環(huán)群。試找出G的所有子群。解： a0=e，（1分）（a）， a0=e , a3， a0=e , a2, a4 10. 求的主析取范式和主合取范式。解：11. 在一階邏輯中，將下面命題符號化，并且要求只能使用全稱量詞：（1） 沒有人長著綠色

30、頭發(fā)。（2） 有的上海市民沒有去過東方明珠塔。解：（1）設(shè)M（x）：x是人，B（x）：x長著綠色頭發(fā)則命題（1）可表示為：（2）設(shè)M（x）：x是上海市民，B（x）：x去過東方明珠塔； 則命題（2）可表示為：12. 設(shè)是上的整除關(guān)系。 （1） 求出關(guān)系；（2） 畫出的哈斯圖；（3） 求出子集的極大元、最大元、上界、上確界。 解：（1）R=<1,1>,<1,3>,<1,4>,<1,12>,<1,24>,<3,3>,<3,12>,<3,24>,<4,4>,<4,12>,<4,

31、24>,<12,12>,<12,24>,<24,24>（2）畫出哈斯圖得2分。（3）3，4，12的極大元為12，最大元為12、上界為12，24，上確界為12。13. 求的主析取范式和主合取范式。解法一：（PQ）（PQ）（PQ）(PQ) (PQ) (PQ)(PQ) (PQ) (PQ)(PQ) （主析取范式）(PQ)P) (PQ)Q) (PP )(QP) (PQ )(QQ) T(QP) (PQ )T（1分(PQ) (PQ ) （主合取范式）解法二：PQPQPQ（PQ）（PQ）TTTTTTFTFFFTTFFFFFTT主析取范式：(PQ)(PQ) 主合取范式：

32、(PQ) (PQ )14. 二元運算在實數(shù)集上是否滿足交換律和結(jié)合律？解：（1）因為 所以滿足交換律（2）因為所以滿足結(jié)合律15. 設(shè)為任意命題公式。（1）已知，問嗎？（2）已知，問嗎？解：（1）設(shè)有某種指派，使公式的真值為，但的真值為，的真值為，則和的真值為，故成立，但不一定成立。（2）設(shè)有某種指派，使公式的真值為，但的真值為，的真值為，則和的真值為，故成立，但不一定成立。16. 畫出符合下列條件的圖（1） 畫一個有一條歐拉回路和一條漢密爾頓回路的圖。（2） 畫一個有一條歐拉回路，但沒有一條漢密爾頓回路的圖。（3） 畫一個沒有一條歐拉回路，但有一條漢密爾頓回路的圖。解：（1）（2）（3）17

33、. 設(shè)集合X=1,2,3,4, A1=1,2,2,3,4, A2=1,2,3, A3=1,2,3,4.(1). 判別A1, A2, A3分別是否是X的一個覆蓋？是否是X的一個劃分？(2). 寫出X的劃分所確定的等價關(guān)系。答：(1). A1是X的一個覆蓋，但不是X的一個劃分；A2不是X的一個覆蓋； A3是X的一個劃分。(2). 劃分A3確定的X上的等價關(guān)系R，R=<1,1>,<2,2>,<3,3>,<3,4>,<4,3>,<4,4>. 18. 設(shè)是上的等價關(guān)系，在什么條件下，自然映射是雙射？解：因為是等價關(guān)系的等價類構(gòu)成的集

34、合，即是關(guān)于的商集，要使自然映射是雙射，則商集的元素個數(shù)必須和中元素個數(shù)一樣多，因此，必須是上的恒等關(guān)系。19. 設(shè) X=a,b,c 上關(guān)系 R=<a,b>,<a,c>,<b,c> , 求R的自反閉包 r(R) , 對稱閉包 s(R) , 和傳遞閉包 t(R) 。解：r(R)=<a,a>,<a,b>,<a,c>,<b,b>,<b,c>,<c,c>s(R)=<a,b>,<a,c>,<b,a>,<b,c>,<c,a>,<c,b

35、>t(R)=<a,b>,<a,c>,<b,c>. 20. 設(shè)R是集合X=1,2,3,5,6,12,上的整除關(guān)系，（1）. 列出R的所有元素；(2). 畫出(X,R)的哈斯圖；(3). 若X有最大、最小元，極大、極小元，請寫出。解：(1). R=<1,1>,<1,2>,<1,3>,<1,5>,<1,6>,<1,12>,<2,2>,<2,6>,<2,12>,<3,3>,<3,6>, <3,12>, <5,5&

36、gt;, <6,6>,<6,12>,<12,12> (2). (X,R)的哈斯圖為：(3). X無最大元； 有最小元1； 極大元5,12； 極小元1. 21. 設(shè)，其上關(guān)系為，寫出關(guān)系中的各元素，并求出dom, ran及。解：dom； ran22. 在實數(shù)域R上定義運算*, a*b=a+b+2ab，則<R,*>是代數(shù)系統(tǒng)。(1). 運算*滿足結(jié)合律嗎？(2). <R,*>有單位元e，求e。(3). <R,*>中每個元素有逆元嗎？任一元素a的逆元是什么？解：(1). a,b,cR，由a*(b*c)=a*(b+c+2bc)=a

37、+b+c+2bc+2a(b+c+2bc)=a+b+c+2ab+2ac+2bc+4abc,(a*b)*c=( a+b+2ab)*c= a+b+c +2ab+2(a+b+2ab)c= a+b+c+2ab+2ac+2bc+4abc,得 運算*滿足結(jié)合律。 因為*滿足交換律，所以右單位元就是單位元，元素的右逆元就是該元素的逆元。(2). e是單位元，a R有a*e=a， 即a+e+2ae=a，得 e(1+2a)=0, 于是由a的任意性得 e=0. (3). 設(shè)b是a的逆元，有a*b=0, 即 a+b+2ab=0, 得b= -a/(1+2a), 所以不是R中每個元素有逆元。當(dāng)a=-1/2時，a無逆元；否

38、則a-1= -a/(1+2a). 23. 設(shè)無向圖 G<V,E> , 其中 V=1,2,3,4,5 , E=(1,2),(1,5),(2,3),(2,4),(2,5),(3,4),(3,5),(4,5)(1). 畫出 G 所對應(yīng)的圖; (2). 求各結(jié)點的度；(3). G 是否具有歐拉回路? 是否具有歐拉通路? 為什么? 若有請寫出解：(1). 圖G為：(2). 結(jié)點 1 2 3 4 5 結(jié)點的度 2 4 3 3 4 (3). 因為結(jié)點3的度是奇數(shù)，所以圖G無歐拉回路；因為僅有兩個結(jié)點3、4的度是奇數(shù)，所以圖G有歐拉通路；歐拉通路為（3,2,1,5,2,4,5,3,4） 24. 設(shè)

39、，定義上的二元關(guān)系，稱稱為小于關(guān)系，也可記為，試求出，dom，ran，。解：dom，（1分）ran，（1分）。25. 求的主析取范式和主合取范式。 解：26. 將公式化為只含聯(lián)結(jié)詞、的等價公式。解：27. 設(shè)和是任意兩個非空集合，成立嗎？解：一般情況下，只要就不成立。如取，則。所以28. 求出從到的所有函數(shù)，并指出哪些是雙射函數(shù)，哪些是滿射函數(shù)？解：； ；雙射：滿射：29. 設(shè)的意義如下：李華乘坐火車 李華在看書 李華在思考問題試用日常語言復(fù)述下列復(fù)合命題。（1） （2）解：（1） 李華乘坐火車并且在看書，但沒有思考問題。（2） 李華既沒乘火車，也沒在看書，李華在思考問題。30. 求公式 (P

40、 Q)(P Q) 的主析取范式和主合取范式。解：設(shè)A= (P Q)(P Q) , 由真值表 P Q Q P Q (P Q) P Q A 0 0 1 1 0 1 0 0 1 0 0 1 1 1 1 0 1 1 0 0 0 1 1 0 1 0 1 0 得使A為1的小項是 PQ, 所以A的主析取范式為PQ,； 使A為0的大項是PQ , PQ , PQ, 所以A的主合取范式為：(PQ) (PQ) (PQ)。 五、 證明題1 證明：(P®R) Ú (Q®R) Û (PÙQ)®R。證明： (P®R) Ú (Q®R)

41、Û (ØPÚR) Ú(ØQÚR) Û(ØPÚØQ)ÚR Û(ØPÙQ)ÚR Û (PÙQ)®R 2 證明：證明： 而所以 3 證明：n個頂點的樹T，其頂點度數(shù)之和為2n-2。證明：設(shè)n個頂點的度數(shù)分別為：d1,d2,dn，由于d1+d2+dn=2m，其中m為邊數(shù),而m=n-1（T為樹），從而d1+d2+dn=2(n-1）=2n-2。4 設(shè)函數(shù)；若是滿射的，則是滿射的。證明：令是滿射， 使令，則是滿射的5 設(shè)<H

42、, *>是群<G, *>的子群，<K, *>是<H, *>的子群。證明：<K, *>是<G, *>的子群。證明：因為<H, *>是<G, *>的子群，所以<G, *>的幺元eÎH，且為<H, *>的幺元；又因為<K, *>是<H, *>的子群，所以<H, *>的幺元eÎK，且為<K, *>的幺元。此外，對任意a, bÎK，由于<K, *>是<H, *>的子群，故a*bÎK，a-1ÎK。綜上所述，由定理<K, *>是<G, *>的子群。6 證明：證明： A（BC）A（BC） A（BC）C（AB）C（AB）C（AB）（CA）B（AC）BA（CB） A（BC）所以A（BC） C（AB）也可以用真值表法證明。7 用CP規(guī)則證明證明： （1） （附加前提）（2） （3） （4） （5） （6） 8 形式化下命題，并用推理規(guī)則證明其結(jié)論每一個