【正文】 8。216。P217。(Q217。R))218。P218。Q218。R 219。216。((P217。216。(Q217。R))218。(216。P217。Q217。R))218。P218。Q218。R 219。(216。(P217。216。(Q217。R))217。216。(216。P217。Q217。R))218。P218。Q218。R 219。((216。P218。(Q217。R))217。(P218。216。Q218。216。R))218。P218。Q218。R 219。(216。P218。(Q217。R)) 218。P218。Q218。R)217。((P218。216。Q218。216。R)218。P218。Q218。R) (218。對(duì)217。的分配律) 219。(216。P218。P)218。Q218。R218。(Q217。R)217。1 219。1217。1219。1 因此，P`218。(Q217。R)174。P218。Q218。R是永真式. 18．解 先將公式化為合取范式. (去掉171。) (去掉174。) (合取范式) (添齊命題變項(xiàng)) 所求主析取范式為主合取范式五個(gè)極大項(xiàng)所對(duì)應(yīng)的三個(gè)極小項(xiàng)，即為 或通過求析取范式求主析取范式. (去掉171。) (去掉174。) (合取范式) 19. 解 (A217。B217。C)218。(216。A217。B217。C)20. 真值為0. 21．(1) 設(shè)個(gè)體域是所有母親的集合. M(x)：x表示愛自己的孩子；該命題符號(hào)化為xM(x). (2) 設(shè)個(gè)體域?yàn)槿说募? H(x)：x表示要呼吸. 該命題符號(hào)化為xH(x) 或設(shè)個(gè)體域?yàn)樯锛希?M(x)：x是人. H(x)：x表示要呼吸. 該命題符號(hào)化為x(M(x)174。H(x)) (3) 設(shè)個(gè)體域?yàn)閿?shù)的集合. R(x)：x表示實(shí)數(shù) Q(x)：x表示有理數(shù). 該命題符號(hào)化$x(R(x)217。Q(x)).22．在公式中，x只有一次出現(xiàn)，轄域是；y只有一次出現(xiàn)，轄域是；$x只有一次出現(xiàn)，轄域是H(x,y). 變?cè)獂在公式中有四次出現(xiàn)，其中第一次出現(xiàn)是在x中，是約束出現(xiàn)；第二次出現(xiàn)是在x的轄域中，也是約束出現(xiàn)；第三次出現(xiàn)是在$x中，也是約束出現(xiàn)；第四次出現(xiàn)是在$x的轄域中，也是約束出現(xiàn). 這四次出現(xiàn)都是約束出現(xiàn)，. 其中第一次是在y中的出現(xiàn)，是約束出現(xiàn)；第二次出現(xiàn)和第三次出現(xiàn)是在y的轄域中的出現(xiàn)，也是約束出現(xiàn)；第四次出現(xiàn)是自由出現(xiàn). y在該公式中有三次約束出現(xiàn)，一次自由出現(xiàn)，因此變?cè)獃既是該公式的約束變?cè)?，也是自由變?cè)? 變?cè)獄在公式中只有一次自由出現(xiàn)，所以z是該公式的自由變?cè)? 23．設(shè)所求二個(gè)公式分別記作A，C. 有 24．用A表示該公式. 取解釋I如下：個(gè)體域?yàn)檎麛?shù)集，F(xiàn)(x,y)：x 163。 y，在I下，若A的前件為真，但后件為假，所以A為假，這說明B不是永真式；再取解釋I162。：個(gè)體域認(rèn)為仍為整數(shù)集，F(xiàn)(x,y)：x=y. 在解釋I162。下，當(dāng)A的前件為真時(shí)，后件為真. 故A為真，這又說明A不是永假式. 綜上所述，A是可滿足式. 25．解 ①消去聯(lián)結(jié)詞174。(0171。，`218。)； ② 將聯(lián)結(jié)詞216。移至原子公式之前. ③ 換名④ 把量詞提到整個(gè)公式的前面為所求前束范式.26. 在G1中，一度結(jié)點(diǎn)有3個(gè)，在G2中一度結(jié)點(diǎn)有4個(gè). 即度數(shù)相同的結(jié)點(diǎn)數(shù)不同，故G1與G2不同構(gòu).27. 解 (1) 所給圖G的一個(gè)圖解，如圖. (2) 結(jié)點(diǎn)v1, v2, v4是與v3鄰接，v3關(guān)聯(lián)的邊為e1, e2, e3. (3)與邊e1關(guān)聯(lián)的結(jié)點(diǎn)為v2, v3. (4) 結(jié)點(diǎn)v6是孤立點(diǎn)；e5是孤立邊. (5) deg(v1)=3，deg(v2)=2，deg(v3)=3，deg(v4)=2，deg(v5)=2，deg(v6)=0，deg(v7)=1，deg(v8)=1，因?yàn)榻Y(jié)點(diǎn)v6是孤立點(diǎn)，所以這不是完全圖. 或用握手定理判別：不滿足(6) G=V,E是有189。V189。=8個(gè)結(jié)點(diǎn)，189。E189。=7條邊的圖，故又稱是8階圖. 28. (1) G1, G2, G3是無向圖；G4, G5, G6是有向圖. (2) G1, G4, G5, G6中既無平行邊，也無自回路，故為簡(jiǎn)單圖. (3) G5是強(qiáng)連通圖，必是單側(cè)連通圖和弱連通圖；G4是單側(cè)連通圖，也是弱連通圖；G6只是弱連通圖. 29. 點(diǎn)割集：V162。＝{v4,v5,v10},割點(diǎn)：v3,v6,v7,v8；邊割集：E162。＝{e1,e2,e3}或{ e8,e9,e10},割邊：e4,e5 e6,e7,e11等.30. 設(shè)7個(gè)人為7個(gè)結(jié)點(diǎn)，將兩個(gè)懂同一語(yǔ)言的人之間連一條邊(即他們能直接交談)，這樣就得到一個(gè)簡(jiǎn)單圖G，問題就轉(zhuǎn)化為G是否連通. 如圖所示，因?yàn)镚的任意兩個(gè)結(jié)點(diǎn)是連通的，所以G是連通圖. 因此，上述7個(gè)人中任意兩個(gè)人能交談. 31．n個(gè)結(jié)點(diǎn)的完全圖共有條邊，而n個(gè)結(jié)點(diǎn)的樹共有n－1條邊. 因此需要?jiǎng)h去 條邊后方可得到樹. 32．解 作圖如圖 (1) (2) (3) (4) 圖 在圖(1)中，可以走遍5個(gè)點(diǎn)，但不是回路，無哈密頓回路，故不是哈密頓圖. 無論指定怎樣的方向，可以走遍所有邊，但不是回路，不能構(gòu)成歐拉回路. 在圖(2)中，容易找出走遍5個(gè)點(diǎn)的回路，即有哈密頓回路，故是哈密頓圖. 但是構(gòu)成回路，要么出現(xiàn)重復(fù)邊，要么漏掉邊，即不存在歐拉回路，因此不是歐拉圖. 在圖(3)中，不重復(fù)地走遍5個(gè)點(diǎn)是不可能的，故不是哈密頓圖. 如指定右邊垂直邊方向向上，就可以畫出一個(gè)走遍所有的邊，又不重復(fù)的回路，所以有歐拉回路，故是歐拉圖. 在圖(4)中 ，滿足要求的條件是顯然的.33. (1) 加法運(yùn)算在S1上不封閉，因?yàn)?206。S1，5206。S1，但3＋5＝8207。S1. (2) 加法運(yùn)算在S2上封閉，證明如下. n1,n2206。S2, 設(shè), 則 (3) 加法運(yùn)算在S3上封閉，證明如下. 首先，對(duì)于任意n1,n2206。S3, 設(shè)則 . 又根據(jù)題意，能被24整除，能被24整除，而 也能被24整除，因此能被24整除. 由此知.34. 解 運(yùn)算*的定義為：. (1) 若r1是單位元，則對(duì)任意元素r206。R,有 由于元素*是可交換的，僅考慮，即 于是 由于r是任意的，要使上式成立，只有r1=0. 因此0是運(yùn)算*的單位元. (2) 若r206。R是冪等元，則應(yīng)有,即 于是 要使上式成立，只有r=0或r=1. 因此0或1是運(yùn)算*的冪等元. (3) 設(shè)r2是r1的逆元，則應(yīng)有 (*的單位元)于是 因此， 對(duì)于R中的任何元素r(只要r185。1)均有逆元，其逆元是.35. 36. P(x)+Q(x)=2x3+4x+2。 P(x)Q(x)=x5+4x4+4x++137. (1) 是環(huán)，且是交換環(huán)；(2) 是環(huán)，但不是交換環(huán)，因?yàn)榫仃嚦朔ㄒ话悴痪哂薪粨Q律.38. 解 用描述法表示； 用列舉法表示：因?yàn)椋? 198。 161。 {a}161。 161。 A 161。 圖關(guān)系矩陣：，關(guān)系圖如圖39. , LA的逆關(guān)系 . 有 40. (1) {1,1,1,4,2,1,4,1,3,4} (2) {1,2,3,4}, {1,4} (3) 7個(gè)是1,1,1,4,2,1,2,4,3,1,4,14,4 (4) 1個(gè)是1,141. R1反對(duì)稱的、傳遞的；R2反對(duì)稱的、傳遞的；R3反自反的、反對(duì)稱的、傳遞的；R4傳遞的；R5反自反的、反對(duì)稱的、傳遞的. 42. (1) 是等價(jià)關(guān)系；(2) 等價(jià)類分別為{2,3,6}, (1,4), {5}43. 解 求自反閉包，R不具有自反性，由自反性的定義，只需在R上添加IA，于是 r(R)=R200。IA={a,a,a,b,b,a,b,b,b,c,c,c,c,d，d,d}其中下畫線者為添加元素. s(R)==R200。{c,b,d,c}={ a,b,b,a,b,c,c,b,c,d,d,c} t(R)==R200。{a,a,b,b,a,c,b,d,a,d} ={a,a, a,b,a,c,a,d,b,a,b,b,b,c,b,d,c,d}44．解 = = 45．解 46．解 先計(jì)算AB＝{a,1,a,2,a,3,b,1,b,2,b,3} (AB)C＝{a,1,a,2,a,3,b,1,b,2,b,3}nhcuj7d3 ＝{a,1,d,a,2,d,a,3,d,b,1,d,b,2,d,b,3,d}ABC＝{a,1,d,a,2,d,a,3,d,b,1,d,b,2,d,b,3,d} BA＝{1,a,2,a,3,a,1,b,2,b,3,b}47．(1) A={0,1,2}；(2) A={1,2,3,4,5}； (3) A={－1}48. (1) 0元子集為：248。 1元子集為：{a},,{c} 2元子集為：{a,b},{a,c},{b,c} 3元子集為：{a,b,c}所以A 的冪集：P(A)={ 248。 , {a},,{c},{a,b},{a,c},{b,c},{a,b,c}}(2) 0元子集為：248。 1元子集為：{1},{{2,3}} 2元子集為：{1,{2,3}}所以A 的冪集：P(A)={ 248。 , {1},{{2,3}},{1,{2,3}}}(3) 0元子集為：248。 1元子集為：{ 248。 },{{ 248。 }} 2元子集為：{ 248。,{ 248。 }}所以A 的冪集：P(A)={ 248。 , { 248。 },{{ 248。 }},{ 248。,{ 248。 }}}49. P(A)={φ, {a}, , {c}, {a, b}, {a, c}, {b, c}, {a, b, c}} A→B={{a, 1, b, 1, c, 1}, {a, 1, b, 1, c, 2}, {a, 1, b, 2, c, 1}, {a, 1, b, 2, c, 2}, {a, 2, b, 1, c, 1}, {a, 2, b, 1, c, 2}, {a, 2, b, 2, c, 1}, {a, 2, b, 2, c, 2} } 都是8個(gè)元素，將它們一一對(duì)應(yīng)就可以得到A到B和B到A的雙射函數(shù)。50. 1) 求商集 N/R1 = {{x}| x∈N} = {{1}, {2}, ...} N/R2 = {{x=2k1| k∈N}, {x=2k| k∈N}} = {{1, 3, ...}, {2, 4, ...}} N/R3 = {{x=3k2| k∈N}, {x=3k1| k∈N}, {x=3k| k∈N}} = {{1, 4, ...}, {2, 5, ...}, {3, 6, ...}} N/R4 = {{x=6k5| k∈N}, {x=6k4| k∈N}, {x=6k3| k∈N}, {x=6k2| k∈N}, {x=6k1| k∈N}, {x=6k| k∈N}} = {{1, 7, ...}, {2, 8, ...}, {3, 9, ...}, {4, 10, ...}, {5, 11, ...}, {6, 12, ...}} N/R1={[1],[2],[3],…} N/R2={[1],[2],…} N/R3={[1],[2],[3]} N/R4={[1],[2],[3],[4],[5],[6]} 2) f1[H] = {10*k|, k∈N} f2[H] = {0} f3[H] = {0, 1, 2} f4[H] = {0,2,4} 51．先根遍歷：abcdfgjehklim 中根遍歷：bafdjgckhleim后根遍歷：bfjgdklhmieca