【正文】 關(guān)系的個(gè)數(shù)為_(kāi)_________個(gè)。（ ）每個(gè)頂點(diǎn)的度都是偶數(shù)的無(wú)向圖一定是歐拉圖。（ ）函數(shù)的逆關(guān)系還是函數(shù)。（ ）設(shè)R是環(huán)，A,B是R的兩個(gè)理想，且B包含于A,則A/B是R/B的理想，并且R/B /(A/B)　同構(gòu)于 R/A。（ ）8. 設(shè)G是有r個(gè)面的連通平面圖，頂點(diǎn)數(shù)和邊數(shù)分別是n和m，則nm+r=2 。（ ）10. 在代數(shù)系統(tǒng)中，若，則 。（ ） 12. 能夠畫(huà)在一張平面上的圖是平面圖。（ ）14. 循環(huán)群的子群仍然是循環(huán)群。（ ）16．1+101=110是命題 。（ ）18．“明天是否開(kāi)大會(huì)？”是命題 。（ ）20. 判斷(Z,163。是數(shù)的小于或等于關(guān)系。（ ）22. 設(shè)集合A＝{18的正整數(shù)因子}，163。是否是偏序關(guān)系。（ ）24．198。的子集。T＝S200。（ ）26. 已知S＝{2,a,{3},4},R={{a},3,4,1},則{a}206。（ ）27. 整數(shù)集合Z和普通的減法運(yùn)算是封閉的。（ ）29．整數(shù)集合{1,2,3,4,6,12}關(guān)于整除關(guān)系構(gòu)成了偏序集，并且該偏序集是格。=e, 則G，*是交換群2. 形式證明3. 證明：P174。R)219。Q174。7．設(shè)G是圖，無(wú)回路，但若外加任意一條邊于G后，就形成一回路. 試證明G必為樹(shù). 8. 設(shè)B是任意集合，試驗(yàn)證(P(B),197。是集合的對(duì)稱差運(yùn)算， 9．給定代數(shù)系統(tǒng)(G,+,*), 二元運(yùn)算見(jiàn)表一，表二. 表一 表二 +abcD *abcDAabcDaaaaaBbadCbabcdCcDaBcacdbDdCbAdadbc證明(G,+,*)是域. 10. 證明如果非空集合A上的二元關(guān)系R和S是偏序關(guān)系，則也是A上的偏序關(guān)系．11．試證A－(B－C)＝(A－B)200。C)12．設(shè)非空集合A，驗(yàn)證()是布爾代數(shù)，13. 試證明屬于關(guān)系不滿足傳遞性，即對(duì)于任意的集合A,B,C若A∈B且B∈C 不一定有A∈C14．設(shè) A,B為兩個(gè)集合，證明 A—B=A當(dāng)且僅當(dāng)A∩B= 248。18．設(shè)G是n階無(wú)向簡(jiǎn)單圖，其直徑為d(G)=2, ο(G)=n2，證明G的邊數(shù)m≥2n419．V=S,*是可交換半群,若a,b ∈S是V中得冪等元，證明a*b也是V中的冪等元20．設(shè) L是格，證明對(duì)于任意a,b,c,d∈L有：( a∧b)∨(c∧d)≤(a∨c)∧(b∨d)五、計(jì)算題 1. 無(wú)向樹(shù)T有2個(gè)2度頂點(diǎn)，1個(gè)3度頂點(diǎn)，3個(gè)4度頂點(diǎn)，其他的都是樹(shù)葉，問(wèn)T中有多少片樹(shù)葉？2. 設(shè)公式 ，其中P(x)：x2，Q(x)：x=0，F(xiàn)是永假式，個(gè)體域是{1，2}，求公式A(x)的真值3. 設(shè)集合X={1，2，3, 4}，X中的關(guān)系為F={1，1，1，2，1，4，2，1，2，2，3，3，4，1，4，4}寫(xiě)出F的關(guān)系矩陣及其關(guān)系圖，F(xiàn)有哪些性質(zhì)？4. (1) n(n≥1)階無(wú)向完全圖與有向完全圖各有多少條邊?為什么？(2)完全二部圖K中共有多少條邊?為什么？(3) 每個(gè)頂點(diǎn)的度都為k的無(wú)向圖稱為k正則圖，問(wèn)：n階k正則圖中共有多少條邊?為什么？5. 設(shè)集合L={a，b}，在L中規(guī)定 + 和a=a，aa=a，b能構(gòu)成代數(shù)系統(tǒng)嗎？若可以，寫(xiě)出該代數(shù)系統(tǒng)的運(yùn)算表。8. 對(duì)集合L，規(guī)定對(duì)于x，y∈L，x≤y當(dāng)且僅當(dāng)x是y的因子。（1）是金子總是要發(fā)光的。（3）平面圖的色數(shù)不超過(guò)410． 若無(wú)向圖G是歐拉圖，G中是否存在割邊?為什么?11. 設(shè)集合，R是定義在A上的二元關(guān)系，寫(xiě)出R的關(guān)系矩陣并求R的對(duì)稱閉包。（1）畫(huà)出半序集（A，R）的哈斯圖；（2）寫(xiě)出集合A中的最大元、最小元、極大元、極小元；（3）寫(xiě)出A的子集B={2，3，6，12}的上界、下界、最小上界，最大下界。問(wèn)⑴有多少個(gè)不同的由X到Y(jié)的關(guān)系？⑵有多少個(gè)不同的由X到Y(jié)的函數(shù)？⑶當(dāng)n,m滿足什么條件時(shí)，存在單射，且有多少個(gè)不同的單射？ 14．在全總個(gè)體域中符號(hào)化下列命題。（2）有的人在微笑但內(nèi)心不高興。15. 將下列命題符號(hào)化：(1) 雖然交通堵塞，但是老王還是準(zhǔn)時(shí)到達(dá)火車(chē)站； (2) 張力是三好學(xué)生或優(yōu)秀共青團(tuán)員(3) 老李或小刁中有一個(gè)人去廣州出差16. 判定公式P174。P218。(Q217。P218。R是永真式？永假式？18．求公式的主合取范式和主析取范式.19. 化簡(jiǎn)下式： (A217。C)218。A217。C)20． 設(shè)命題P,Q的真值為0，命題R,S的真值為1，求命題公式的真值.21． 將下列命題符號(hào)化：（1）每個(gè)母親都愛(ài)自己的孩子；(2) 所有的人都呼吸；(3) 有某些實(shí)數(shù)是有理數(shù). 22．指出下列公式 中量詞的每次出現(xiàn)轄域，并指出變?cè)拿看纬霈F(xiàn)是約束出現(xiàn)，還是自由出現(xiàn)，以及公式的約束變?cè)杂勺冊(cè)? 23．給定解釋I： ① D＝{2,3}。 (2) ；24．討論公式的類(lèi)型.25．將公式F 化為前束范式.26. 判定下面二圖是否同構(gòu)？ 27. 設(shè)G＝(V,E)是一個(gè)無(wú)向圖， (1) 畫(huà)出G的圖解；(2) 指出與v3鄰接的結(jié)點(diǎn)，以及與v3關(guān)聯(lián)的邊；(3) 指出與e1關(guān)聯(lián)的結(jié)點(diǎn)；(4) 該圖是否有孤立結(jié)點(diǎn)和孤立邊？(5) 求出各結(jié)點(diǎn)的度數(shù)，并判斷是不是完全圖？(6) G＝V,E的189。189。各是多少？28. 給定下列六個(gè)圖(如圖)，G1＝V1,E1,其中V1={a,b,c,d,e},E1={(a,b）,(b,c),(c,d),(a,e)}G2＝V2,E2,其中V2=V1,E2={(a,b),(b,e),(e,b),(a,e),(d,e)}G3＝V3,E3,其中V3=V1,E3={(a,b),(b,e),(e,d),(c,c)}G4＝V4,E4,其中V4=V1,E4={a,b,b,c,c,a,a,d,d,a,d,e}G5＝V5,E5,其中V5=V1,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} 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 l d cl ld cl ld cl ld (G1) (G2) (G3) (G4) (G5) (G6) 圖試問(wèn)：(1) 哪些圖是有向圖？哪些圖是無(wú)向圖？ (2) 哪些是簡(jiǎn)單圖？(3) 哪些是強(qiáng)連通圖？哪些是單側(cè)連通圖？哪些是弱連通圖？29. 求圖G的點(diǎn)割集、割點(diǎn)、邊割集和割邊. 30. 已知有關(guān)人員a,b,c,d,e,f,g的有關(guān)信息： a：說(shuō)英語(yǔ)；b：說(shuō)英語(yǔ)或西班牙語(yǔ)；c；說(shuō)英語(yǔ)，意大利語(yǔ)和俄語(yǔ)；d：說(shuō)日語(yǔ)和西班牙語(yǔ)e：說(shuō)德語(yǔ)和意大利語(yǔ)；f：說(shuō)法語(yǔ)、日語(yǔ)和俄語(yǔ)；g：說(shuō)法語(yǔ)和德語(yǔ). 試問(wèn)上述7人中是否任意兩人都能交談(如果必要，可由其余5人中組成的譯員鏈幫助)31. 在具有n個(gè)結(jié)點(diǎn)的完全圖Kn中，需要?jiǎng)h去多少條邊才能得到樹(shù). 32．畫(huà)出具有下列條件的有 5個(gè)結(jié)點(diǎn)的圖. (1) 沒(méi)有哈密頓回路，也不能適當(dāng)指定各邊的方向，使其具有歐拉回路；(2) 有哈密頓回路，但是不能適當(dāng)指定各邊的方向，使其具有歐拉回路；(3) 沒(méi)有哈密頓回路，但是能適當(dāng)指定各邊的方向，使其具有歐拉回路； (4) 有哈密頓回路，也能適當(dāng)指定各邊的方向，使其具有歐拉回路. 33. 通常數(shù)的加法運(yùn)算可看作正整數(shù)N＋上的二元運(yùn)算. 下列集合是N＋的子集，加法運(yùn)算在這些子集上封閉嗎？為什么？ (1) (2) (3) 34. ；運(yùn)算*是否有單位元和冪等元？若有單位元的話，哪些元素有逆元？ 35. 是布爾代數(shù)，化簡(jiǎn). 36. 設(shè)是定義在Z5(＝{0,1,2,3,4})上的多項(xiàng)式(即系數(shù)是Z5的元素的多項(xiàng)式)，試計(jì)算P(x)+Q(x)，P(x)Q(x).37. 回答下列代數(shù)系統(tǒng)是環(huán)嗎？是交換環(huán)嗎？ (1) (Zm,＋，*),其中Zm＝{0,1,2,…,m－1}，＋和*是模m加法和乘法. (2) (Mn(R)，＋，176。分別是矩陣的加法和乘法.38. 設(shè)集合A＝{a,b},R是P(A)上的包含關(guān)系，寫(xiě)出R的表達(dá)式和關(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)系矩陣為 試求 (1) R的關(guān)系表達(dá)式； (2) Dom(R)和Ran(R)； (3) R2．f（3）=1，f（1）=5，f（5）= 3．a(chǎn)：5．個(gè)體域D=（3，1，5）．45．化簡(jiǎn)46．設(shè)集合 A={a,b},B={1,2,3},C=nhcuj7d3,求(AB)C，ABC，BA. 47．用列舉法表示以下集合：(1) ； (2) 。,{ 248。N且 f1(n)=n f2(n)= 1 n為奇數(shù) f3(n)=0 n為偶數(shù) f3(n)=j,n=3k+j,j=0,1,2,k∈N f4(n)=j,n=6k+j,j=0,1,…,5,k∈N Rk為fk導(dǎo)出的N上的等價(jià)關(guān)系,k=1,2,3,4 1) 求商集N/Rk k=1,2,3,4 2) 求H={10k|k∈N }在f1,f2,f3,f4 下的象！ 51．對(duì)圖給出的二叉樹(shù)分別進(jìn)行先根遍歷、中根遍歷和后根遍歷。{198。1}，{198。216。R25. y,x x,z26. 27. 28. 約束 自由29. 30. 自反性 對(duì)稱性 傳遞性 等價(jià). 31. 出度 入度32. 14 28 7 6 33. D中每個(gè)結(jié)點(diǎn)的入度＝出度.34. 大于或等于n35. m+1－n36. 若有向圖T恰有一個(gè)結(jié)點(diǎn)的入度為0，其余結(jié)點(diǎn)入度為1 入度為0的結(jié)點(diǎn) 入度為1的結(jié)點(diǎn).37. 0 僅有單位元0.38. 198。) 半群 二元運(yùn)算42. 交換律 結(jié)合律 吸收律43. 44. {1,4,1,3}45. R199。{198。49. {2},{1,3,4}，{1,3,4,5} 50. 051. {{c},{a,c},{b,c},{a,b,c}}；198。 207。53. (a∧b)∨(a∧c)54. {0},{0,3},{0,2,4}{0,1,2,3,4,5}55. 156. 永真式57. 58 59. R2={（a,a），(a,c) }60. 15三、判斷題1. 正確（從同構(gòu)的角度說(shuō)明理由）2. 錯(cuò)誤（舉反例）3. 錯(cuò)誤（舉反例）4. 錯(cuò)誤（從同構(gòu)的角度說(shuō)明理由）5. 錯(cuò)誤（舉反例）6. 正確7. 錯(cuò)誤 8. 正確 9. 正確10. 錯(cuò)誤11. 正確12. 錯(cuò)誤13. 錯(cuò)誤14. 正確15. 正確16. 否17. 否18. 否19. 是20. 是21. 否22. 是23. 錯(cuò)誤24. 真25. 假26. 錯(cuò)誤27. 正確28. 是29. 是四、證明題1． 證明：由條件，所以，則對(duì)任意的a，b，另外，由，得，兩邊同時(shí)左乘以，右乘以，利用結(jié)合律，得所以，G，*是交換群2. 證明： （1） 前提引入（2） p （1）化簡(jiǎn)（3） s （1）化簡(jiǎn)（4） p→q∨r 前提引入（5） q∨r （2）（4）分離（6） s→172。r （3）（6）分離（8） q （5）（7）析取三段論3. 證明 P174。R）219。(216。R) (等值蘊(yùn)含式)219。P218。Q218。（216。216。R (結(jié)合律)219。(P217。R