第一章習題答案1.判斷下列語句哪些是命題并給出命題的真值。(1)20是偶數(shù)。(2)今天是晴天嗎？(3)平行四邊形兩對邊分別平行。(4)直角三角形其中兩邊相互垂直。(5)16既能被2整除，又能被8整除。(6)請尊老愛幼！(7)4是2的倍數(shù)。(8)我們?nèi)ソ加萎斍覂H當今天不下雨。(9)我和李霞是朋友。(10)人只要肯努力就一定能成功。答：（1）、（2）、（4）、（5）、（7）、（8）、（9）、（10）是命題，其中（1）、（2）、（4）、（7）、（9）是簡單命題，（5）、（8）、（10）是復合命題。簡單命題（1）、（2）、（4）、（7）是真命題，（9）可為真命題，也可為假命題，故是命題變項。（5）因為是簡單命題“16能被2整除”和“16能被8整除”的合取，且兩個簡單命題為真命題，故（5）的真值為真，而（8）、（10）的真值即可為真也可為假。2.給出下列命題的否定命題。(1)杭州的每條街道都有綠化。(2)每一個素數(shù)都是偶數(shù)。答：(1)的否定命題為：杭州的每條街道都沒有綠化。(2)的否定命題為：每一個素數(shù)都不是偶數(shù)。3.將下列命題符號化。(1)如果天晴，我將去公園。(2)僅當你去我才離開。(3)2既能整除4又能整除8。(4)張亮和趙鵬是同班同學。(5)兩個三角形全等當且僅當它們對應的兩條邊相等且由這兩條邊構成的夾角相等。(6)周六沒有英語課或離散數(shù)學課。(7)張磊和李楠只有一人能參加這次英語競賽。(8)只要我們肯想辦法，總能克服這些困難。(9)星期天天晴或下雨。(10)只有年齡滿14歲或身高超過1.4米才能坐過山車。答：(1)令p：天晴，q：我去公園。命題符號化為：(2)令p：你去q，：我離開。命題符號化為：(3)令p：2能整除，q：4能整除8。命題符號化為：(4)令p：張亮和趙鵬是同班同學命題符號化為：p。(5)令p：兩個三角形全等，q：對應的兩條邊相等，r：兩條邊構成的夾角相等。命題符號化為：(6)令p：周六有英語課，q：周六有離散數(shù)學課。命題符號化為：(7)令p：張磊參加這次英語競賽，q：李楠參加這次英語競賽。命題符號化為：(8)令p：我們肯想辦法，q：我們能克服這些困難。命題符號化為：(9)令p：星期天天晴，q：星期天下雨。命題符號化為：(10)令p：年齡滿14歲，q：身高超過1.4米，r：能坐過山車。命題符號化為：4.令p表示命題“蘋果是添的”，q表示命題“蘋果是紅的”，r表示命題“我買蘋果”。試將下列命題符號化：(1)如果蘋果甜而紅，那么我買蘋果。(2)蘋果不是甜的。(3)我沒買蘋果，因為蘋果不紅也不甜。答：(1)命題符號化為：(2)命題符號化為：(3)命題符號化為：5.設p表示“該地區(qū)曾出現(xiàn)過灰熊”，q表示“在路上遠足很安全”，r表示“沿途蘋果成熟了”，給出描述下列命題公式的語句。(1)答：該地區(qū)未曾出現(xiàn)過灰熊。(2)答：該地區(qū)曾出現(xiàn)過灰熊或者在路上遠足很安全。(3)答：如果該地區(qū)曾出現(xiàn)過灰熊，那么在路上遠足就不安全。(4)答：該地區(qū)曾出現(xiàn)過灰熊且在路上遠足不安全。(5)答：該地區(qū)曾出現(xiàn)過灰熊或者在路上遠足很安全。(6)答：若沿途蘋果成熟了則在路上遠足是安全的，當且僅當該地區(qū)未出現(xiàn)過灰熊。6.構成下列公式的真值表，寫出成真賦值和成假賦值。(1)pq0011010110111101成真賦值為：00,01,10,11。(2)pq00110010111011011011成真賦值為：01,11；成假賦值為：00,10。(3)pq00001011001010011111成真賦值為：00,11；成假賦值為：01,10。(4)pq0011111011011110010011100111成真賦值為：00,01,10,11。(5)pq00101011101000111111成真賦值為：00,10,11；成假賦值為：01。(6)pqr0000001000101001010100010111110010011100101111001101110011111100成真賦值為：001,010；成假賦值為：000,011,100,101,110,111。7設p、q的真值為0，r、s的真值為1，求下列命題的真值。(1)答：當p、q的真值為0，r的真值為1，該命題真值為1。(2)答：當p、q的真值為0，r、s的真值為1，該命題真值為1。(3)答：當p、q的真值為0，r、s的真值為1，該命題真值為0。(4)答：當p、q的真值為0，r、s的真值為1，該命題真值為1。(5)答：當p、q的真值為0，r、s的真值為1，該命題真值為1。8.通過真值表方法判斷下列命題公式的類型。(1)p011011100100答：根據(jù)真值表可知公式真值可真可假，所以該公式是可滿足式。(2)pqr0000000101010110111110011101111101111111答：根據(jù)真值表可知公式真值可真可假，所以該公式是可滿足式。(3)pq0000011010111110答：根據(jù)真值表可知公式真值可真可假，所以該公式是可滿足式。(4)pq00001011111011111111答：根據(jù)真值表可知公式真值都為真，所以該公式是永真式。(5)pqr0001111100111111010101010111111110001001101011011101000111111111答：根據(jù)真值表可知公式真值都為真，所以該公式是永真式。(6)pq001101010011101011110101答：根據(jù)真值表可知公式真值都為真，所以該公式是永真式。9.寫出與下面給出的公式等價并且僅含有聯(lián)接詞與的最簡公式。(1)答：(2)答：(3)答：(4)答：(5)答：10.寫出與下面的公式等價并且僅含聯(lián)結詞和的最簡公式。(1)答：(2)答：(3)答：11.用等值演算法判斷下列命題公式的類型。(1)答：此公式為永真式。(2)答：此公式為永真式。(3)答：此公式為可滿足式。12.用真值表法和等值演算法證明下列等值式。(1)真值表如下：pq00011011001010011011根據(jù)真值表，和有相同真值，故等式成立。等值演算法： 所以，等式成立。(2)真值表如下：pqr0001101100110100010011000110010010011011101111111101111111111111根據(jù)真值表，和有相同真值，故等式成立。 所以，等式成立。(3)pqac00001111000111110010100000111111010011110101111101100000011111111000111110011111101011111011111111001111110111111110010011111111根據(jù)真值表，和有相同真值，故等式成立。等值演算法： 所以，等式成立。(4)pq001111011111100100110010根據(jù)真值表，和有相同真值，故等式成立。等值演算法：所以，等式成立。(5)pq001101011011010011100000000110000111根據(jù)真值表，和有相同真值，故等式成立。等值演算法： 所以，等式成立。(6)pq0011000011000010001111100101根據(jù)真值表，和p有相同真值，故等式成立。等值演算法：所以，等式成立。(7)pq001100100011001100100011000110011000根據(jù)真值表，和有相同真值，故等式成立。等值演算法：所以，等式成立。13.化簡下列公式。(1)解：(2)解：(3)解：(4)解：(5)解：14.用真值表法求下列各式的主析取和主合取范式。(1)pqr000111001101010111011101100011101011110111111111原式的主析取范式為：原式的主合取范式為：F(2)pqr000111001111010100011111100011101111110001111111原式的主析取范式為： 原式的主合取范式為：15.分別等值演算法求下列各式的主析取和主合取范式。(1) 原式的主合取范式為： (2) 原式的主合取范式為：(3)原式的主析取范式為：16.用主析取范式判斷下列各組命題公式是否等值。(1)；解：是第一個公式的主合取范式，故第一個公式的主析取范式為：；第二個公式經(jīng)等值演算的主析取范式為：，故兩公式相等。(2)；第一個公式的主析取范式為：第二個公式本身就是主析取范式，故兩公式相等。(3)；第一個公式的主析取范式為：第二個公式的主析取范式為：故兩式相等。17.證明下列蘊含式成立。(1)故有：(2)故有：(3)故有：。18.證明和是邏輯等價的。故兩式邏輯等價。19.化簡邏輯式，并設計該邏輯式的電路圖。20.使用非門，或門和與門構建組合電路，該組合電路從輸入位p，q和r產(chǎn)生輸出。第二章習題答案1.令表示“x是偶數(shù)”，判斷下列各式的真值是什么？(1)(2)(3)解：(1)假，(2)真，(3)真2.令P(x)表示“”。個體域是整數(shù)，判斷下列各式的真值是什么？(1)P(0)(2)P(1)(3)P(2)(4)P(-1)(5)(6)解：(1)真，(2)真，(3)假，(4)假，(5)真，(6)假3.若個體域是正整數(shù)集合，令表示，下列公式中哪些公式的值為真值？(1)(2)(3)(4)(5)(6)(7)(8)解：(1)假，(2)假，(3)真，(4)真，(5)假，(6)假，(7)真，(8)真4.將下列命題用謂詞邏輯符號化。解：令P(x)：x會說俄語；Q(x)：x會phython編程語言；R(x)：x在這所學校。(1)在這所學校有個能說俄語且會phython編程語言的學生。(2)在這所學校有個能說俄語但不會phython編程語言的學生。(3)在這所學校每個學生都會說俄語且會phython編程語言。(4)在這所學校沒有一個學生會說俄語或會phython編程語言。5.將下列命題用謂詞邏輯符號化。(1)在這個班里有個學生家里有一只貓和一條狗。解：令P(x)：x是這個班里的學生；Q(x,y)：x家里有只y；a：狗；b：貓。(2)趙勛既努力又聰明。解：令P(x)：x努力；Q(x)：x聰明；a：趙勛?；蚍柣癁椋毫頿：趙勛努力；q：趙勛聰明。(3)并不是所有的女人都喜歡追劇。解：令P(x)：x是女人；Q(x)：x喜歡追劇。(4)如果你不努力，就一定不能取得成功。解：令P(x)：x努力；Q(x)：x能取得成功。(5)有些人喜歡小動物，但不是所有的人都喜歡小動物。解：令P(x)：x喜歡小動物；Q(x)：x能取得成功。(6)這個班里所有學生都選修了人工智能專業(yè)的課程。解：令P(x)：x是這個班里的學生；Q(x)：x選修了人工智能專業(yè)的課程。(7)任何偶數(shù)都能被2整除。解：令P(x)：x是偶數(shù)；Q(x)：x能被2整除。(8)這個班里的男生都喜歡打籃球。解：令P(x)：x是這個班里的男生；Q(x)：x喜歡打籃球。(9)如果今天是星期六，明天就是星期日。解：令P(x)：x是星期六，a：今天；Q(x)：x是星期天，b：明天。令p：今天是興趣六；q：命題是星期日。(10)天氣好我們就去郊游。解：令p：天氣好；q：我們?nèi)ソ加巍?.在一階邏輯中將下面命題符號化。(1)每個用戶只能注冊一個賬號。解：令P(x)：x只能注冊一個賬號。(2)有些女生喜歡甜食。解：令P(x)：x喜歡甜食。(3)在杭州定居的人未必都是杭州人。解：令P(x)：x是在杭州定居的人；Q(x)：x是杭州人。(4)所有女人都愛看電視劇。解：令P(x)：x是女人；Q(x)：x愛看電視劇。(5)班上每個學生都報考了研究生考試。解：令P(x)：x是班上學生；Q(x)：x報考研究生考試。7.設個體域D={-2,-1,0}。消去下列各公式中的量詞。(1)(2)(3)(4)(5)(6) (7)(8) (9) (10)8.設個體域D={-1,1,2}，用析取和合取聯(lián)結詞表示下列命題。(1)(2) (3)(4)(5)9.給定解釋I如下：i.個體域為自然數(shù)集N；ii.元素a=1；iii.iv.N中的特定謂詞表示：x-y=0，：x>y。在解釋I下，求下列各式的真值。(1)(2)(3) (4) 10.給定解釋I如下：i.個體域為自然數(shù)集N；ii.元素a=1；iii.iv.N中的特定函數(shù)；v.N中的特定謂詞表示：x<y，：x>y。在解釋I下，求下列各式的真值。(1)(2) (3) (4)11.指出下列各公式中每個量詞的作用域，并指出個體變元是約束出現(xiàn)還是自由出現(xiàn)。(1)解：的作用域為，的作用域也為，個體變元為x和y為約束出現(xiàn)。(2)解：的作用域也為，約束出現(xiàn)的個體變元為中的x，中的y和中的x和y為自由出現(xiàn)的個體變元。(3)解：第一個的作用域也為，第二個的作用域也為，第一個公式和中的x為約束出現(xiàn)的個體變元，第一個公式和中的y為自由出現(xiàn)的個體變元，第二個公式中的y為約束出現(xiàn)的個體變元，而第二個公式的x為自由出現(xiàn)的個體變元。(4)解：的作用域為，的作用域也為，個體變元為x和y為約束出現(xiàn)。12.求下列公式的前束范式。(1)解：(2)解：(3)解：(4)解：13.求下列公式的前束范式。(1)解：(2)解：(3)解：14.化簡下列各式。(1)解：(2)解：(3)解：(4)解：15.指出下列推導中的錯誤，并加以改正。(1)前提引入(2)(1)UI(3)前提引入(4)(3)EI(5)(4)化簡律(6)(2)(5)假言推理(7)(6)EG解：第一步和第三步的順序錯誤，應該先存在量詞消去，后全稱量詞消去。改正序列：(1)前提引入(2)(1)EI(3)前提引入(4)(3)UI(5)(2)化簡律(6)(4)(5)假言推理(7)(6)EG16.構造下面的推理的證明。(1)前提：，，結論：q證明：(1) 前提引入(2)前提引入(3)(1)(2)析取三段論(4)前提引入I(5)q(2)(5)假言推理(2)前提：，，結論：證明：(1) 前提引入(2)前提引入(3)(1)(2)假言推理(4)前提引入I(5)(3)(4)假言推理(6)(5)雙重否定律(7)(6)蘊涵等值式(3)前提：，，結論：證明：(1) 前提引入(2)(5)雙重否定律(3)(2)蘊含式(4)前提引入(5)(2)(3)假言三段論(6)(5)假言推理(7)前提引入(8)(6)(7)假言三段論(4)前提：，，結論：證明：(1) 前提引入(2)(1)蘊含式(3)前提引入(4)(3)假言易位(5)(2)(4)假言三段論(6)前提引入(7)(5)(6)假言三段論(5)前提：q，，，結論：證明：(1)附加前提(2)前提引入(3)p(2)(3)析取三段論(4)前提引入(5)(3)(4)假言推理(6)q前提引入(7)s(5)(6)假言推理17.構造下列推理的證明。(1)前提：結論：證明：(1)前提引入(2)(1)EI(3)前提引入(4)(3)EI(5)(4)UI(6)(2)(5)假言推理(7)附加(8)(6)(7)假言推理(9)(8)EU(2)前提：結論：證明：(1)前提引入(2)(1)EI(3)前提引入(4)(3)EI(5)(4)UI(6)(2)(5)假言推理(7)附加(8)(6)(7)假言推理(9)(8)EU(3)前提：結論：(4)前提：結論：(5)前提：結論：(6)前提：結論：(7)前提：結論：18.證明前提：(1)若A隊得第一，則B隊或C隊獲亞軍;（2）若C隊獲亞軍，則A隊不能獲冠軍;（3）若D隊獲亞軍，則B隊不能獲亞軍;（4）A隊獲第一?？梢酝瞥鼋Y論：D隊不是亞軍。19.符號化下面的論斷，并給出相應的推理證明。(1)如果今天天氣晴，我們就去放風箏或劃船；如果刮風，我們就不去劃船。今天天氣晴但有風，所以我們就去放風箏。(2)如果期末復習肯努力，就一定能通過離散數(shù)學考試。身體不好且考試科目多。沒有通過離散數(shù)學考試。所以，期末復習沒努力且考試科目多。20.符號化下列命題，并給出推理證明。(1)如果李楠是理科學生，她必須學習微積分。如果她不是文科學生，那么她必須是理科學生。她沒有學微積分。所以她是一個文科生。(2)王敏學習英語或日語。如果王敏學習過英語，那么她就去了英國。如果去過英國，那么她去過日本。于是王敏學習日語或去了日本。(3)這個班的學生李格知道如何用JAVA編寫程序。每個知道如何用JAVA編寫程序的人都可以得到一份高薪工作。因此，這個班的學生都可以得到一份高薪工作。(4)這個班的人都喜歡觀看鯨魚表演。每個喜歡觀看鯨魚表演的人都關心海洋污染。因此，這個班上每個人都關心海洋污染。(5)這個班的每位都擁有一臺個人計算機。擁有個人計算機的每個學生都可以使用文字處理程序。因此，這個班的李爽可以使用文字處理程序。”第三章習題答案1.判斷下列集合是否相等。(1){1,2,3}和{1,1,3,2,2}(2){}和(3){}和{{},}2.設集合A={1,2,3,4,5,6}和集合B={0,3,6}。試計算下列各式：(1)(2)(3)(4)(5)(6)3.判斷下列各式是否正確。(1)(2)(3)(4)(5)(6)(7)(8)(9)(10)4.求下列集合的冪集。(1)(2){1,{a,b}}(3){,{}}(4){2,2,2,3}5.設A={}，B={1,2}，試計算。6.請用文氏圖表示以下集合。(1)(2)(3)(4)(5)7.設A和B是任意集合，證明下列恒等式。(1).(2).(3)(4)(5)(6)8.已知A、B、C是三個集合，證明：(1)(2)(3)A∩(B∪C)=(A∩B)∪(A∩C)9.已知A、B、C是三個集合，證明：(1)(2)10.假設全集U={1,2,3,4,5,6,7,8,9,10}。如果i在集合中，則字符串中第i位為1，否則為0。請按上述規(guī)則的位字符串表示下列集合。(1){3,4,5}(2){1,3,6,10}(3){2,3,4,7,8,9}11.設矩陣，計算下列各式：(1)，(2)，(3)12.設矩陣，計算下列各式：(1)，(2)13.設矩陣和。計算下列各式：(1)，(2)AT，(3)BT14.設矩陣和。計算下列各式：(1)，(2)，(2)，15.設矩陣和。計算下列各式：(1)，(2)，(3)第四章習題答案1.設集合A={a,b,c}，試求。2.設關系，試求(1)(2)ranR(3)domR3.設是集合A=上的二元關系，,。試求：(1)(2)(3)(4)4.設關系R是人類集合上的二元關系，試判斷關系是否是自反的，對稱的，反對稱的或傳遞的？(1)田蕾比趙艷漂亮。(2)田蕾和趙艷是同班同學。(3)田蕾比趙艷高。(4)田明和田蕾是兄妹。5.設R1和R2是關系，且矩陣分別表示為：和試計算下列各式：(1)(2)(3)(4)(5)(5)(6)6.畫出下面關系的關系圖。7.設集合A={1,2,3,4},R是集合A上的二元關系。試給出關系R的自反閉包、對稱閉包和傳遞閉包。R={<1,2>,<1,3>,<2,3>,<3,3>,<4,3>,<2,4>}8.設集合A={a,b,c}，R是集合A上的二元關系，關系R的關系矩陣為：.(1)給出關系R的集合表示。(2)畫出關系R的關系圖。(3)試判斷關系R具有的性質(zhì)。9.下列子集哪些是集合{1,2,3,4,5,6}的劃分?(1){1,2},{2,3,4},{4,5,6}(2){1},{2,3,6},{4},{5,6}(3){2,4,6},{1,3,5}(4){1,4,5},{2,6}10.設集合A={1,2,3},判斷下列關系是否為等價關系，為什么？(1)(2)(3)(4)11.設集合A={a,b,c,d}，關系R是A上的二元關系，即，試給出等價關系R的等價類和商集。12.設集合A={a,b,c,d}，試給出下列0-1矩陣對應的關系集合和關系圖，并判斷這些關系是否為等價關系？(1)(2)(3)13.設R是正整數(shù)集合上的二元關系，即當且僅當，其中a、b、c和d是正整數(shù)。試證明二元關系R是等價關系。14.設R是正整數(shù)集合上的二元關系，即當且僅當ad=bc，其中a、b、c和d是正整數(shù)。試證明二元關系R是等價關系。15.設集合A={1,2,3,4,6,8,12,24},是一個偏序集。這里“”代表整除關系。畫出偏序集的的哈斯圖。并指出它的極小元、最小元、極大元和最大元。16.設集合A={1,2,3,4,5,6},R是集合A上的整除關系。畫出偏序集的的哈斯圖。并指出它的極小元、最小元、極大元和最大元。其中A的子集A1={2,3,6}，A2={2,3,5}。試給出A1和A2的上界、下界、上確界和下確界。17.下列關系中哪些是從R到R的單射關系？(1)(2)(3)(4)18.下列關系中哪些是從到Z的滿射關系？(1)(2)(3)(4)19.下列關系中哪些是從到Z的雙射關系？(1)(2)(3)(4)20.設R是實數(shù)集合，并且對于，函數(shù)f(x)=x+3，f(x)=2x+4和h(x)=x2，試判斷上述函數(shù)是否有反函數(shù)？若有請給出對應的反函數(shù)。21.設函數(shù)是；函數(shù)是；函數(shù)是。試求出合成函數(shù)，和的代數(shù)表達式。求出各函數(shù)的定義域，即R的子集。第五章習題1．解：4個頂點的所有非同構連通圖如下圖所示：2．解：圖G是1-可著色的當且僅當G是空圖。3．解：(1)設w為分圖個數(shù)，由公式m≤1w=3時，m≤1(2)由一個孤立頂點和一個Kn-1組成的圖。4．解：以所有二位三進制數(shù)作為頂點，在這頂點集{aa,ab,ac,ba,bb,bc,ca,cb,cc}中，若頂點u的后一個字母與頂點v的前一個字母相同，則u到v有一個弧。這樣所得圖如下圖所示，其中e0=aaa,e1=aab,e2=aac,e3=aba,e4=abb,e5=abc,e6=aca,e7=acb,e8=acc,e9=baa,e10=bab,e11=bac,e12=bba,e13=bbb,e14=bbc,e15=bca,e16=bcb,e17=bcc,e18=caa,e19=cab,e20=cac,e21=cba,e22=cbb,e23=cbc,e24=cca,e25=ccb,e26=ccc。此圖有一條歐拉回路:（e0,e1,e3,e11,e7,e21,e10,e4,e14,e16,e22,e13,e12,e9,e2,e8,e26,e25,e23,e15,e20,e6,e19,e5,e17,e24,e18）,對應的排列是aaabacbabbcbbbaacccbcacabcc。5．解：(a)鄰接矩陣為A=01010011(b)A(2)=0111020101110011，A(3)=0212由A，A(2)，A(3)，A(4)可知從v1到v4長度為1，2，3，4的路徑分別為1，1，2，3條。(c)AT=0000101101001110，ATA=0000AAT中第(2，3)個元素為1，說明從v2和v3引出的邊能共同終止于同一結點的只有一個，即v4。AATA中第(2，3)個元素為0，說明沒有結點引出的邊同時終止于v2和v3，ATA(d)A2=0111010101110011，A3=01110111P=A∨A2∨A3∨A4=01110111(e)PT=0000111111111111，P^P所以強分圖的頂點集為：{v1}，{v2,v3,v4}。6．解：完全圖K1,K2,K3,K4分別如下圖所示：7．解：該無向圖的鄰接矩陣A=011118．解：由鄰接矩陣可知a11=1,a12=1,a13=2,a14=0,a22=2,a23=1,a24=3,a33=0,a34=1,a44=0,故頂點v1處有一個環(huán)，v1與v2間有一條邊，v1與v3間有2條邊，v1與v4間沒有邊相連，v2處有2個環(huán)，v2與v3間有一條邊，v2與v4間有3條邊，v3處沒有環(huán)，v3與v4間有一條邊，v4處沒有環(huán)，即一共有3個環(huán)和5條多重邊。根據(jù)鄰接矩陣所得多重圖G如下圖所示，經(jīng)檢驗答案正確。9．解：上圖的強分圖有：<{v1,v2,v3,v4,v5},{<v1,v2>,<v2,v3>,<v3,v4>,<v4,v1>,<v2,v5>,<v5,v3>}>;弱分圖和單向分圖有：<{v1,v2,v3,v4,v5},{<v1,v2>,<v2,v3>,<v3,v4>,<v4,v1>,<v2,v5>,<v5,v3>}>;<{v5,v6},{<v5,v6>}>;<{v6,v7,v8},{<v7,v6>,<v8,v7>}>;強分圖、弱分圖和單向分圖分別如下圖(a)(b)(c)所示：10．解：在完全圖中，每個頂點都與其余（n–1）個頂點相鄰。因此，每個頂點都需要一種新的顏色。因此，色數(shù)K6=6，K10=10，Kn=n。11．解：根據(jù)題意，有10個可能的狀態(tài)，分別為S1:<{m,d,r,c},?>;S2:<{d,c},{m,r}>;S3:<{m,d,c},{r}>;S4:<vplfbjx,{m,r,c}>;S5:<{c},{m,d,r}>;S6:<{m,d,r},{c}>;S7:<{m,r,c},jhhdbbp>;S8:<{r},{m,d,c}>;S9:<{m,r},{d,c}>;S10:<?,{m,d,c,r}>。如右圖所示，由圖可知，至少有兩個解：(S1,S2,S3,S4,S6,S8,S9,S10)或(S1,S2,S3,S5,S7,S8,S9,S10)。12．解：在圖同構意義下，具有三個結點的所有簡單有向圖如下圖所示：13．證明：先證明充分性。 給定有向圖G=<V,E>,且G有一條經(jīng)過每個結點的路為v1e1v2e2…vn-1en-1vn，其中V={v1,v2,…vn},{e1,e2,…en-1}?E,ei=<vi,vi+1>,1≤i≤n-1。任給兩個結點vj,vm∈V，不妨設j<m，則vjejvj+1ej+1…em-1vm就是從結點vj出發(fā)到達結點vm的路，故G是單向連通的。下面證明必要性。對結點數(shù)目n進行歸納證之，當n=1，n=2時，單向連通的圖顯然有一條經(jīng)過該圖中每個結點的路。當n=k時，假設有一條經(jīng)過每個結點的路v1v2…vp,其中結點可能有重復出現(xiàn)，其結點下標只表示它在路中所經(jīng)過結點的次序，顯然k≤p。當n=k+1時，取一結點u，在圖G中刪去u，使G-{u}還是單向連通圖。根據(jù)歸納假設，G-{u}有一條經(jīng)過每一條結點的路v1v2…vm,令p=max{i|vi到u有路}，q=min{i|u到vi有路}。假設q>p+1,則必有r，使p<r<q。由于圖G是單向連通的，vr與u之間有路。若該路是從vr到u，則與p=max{i|vi到u有路}矛盾。若該路是從u到vr，則與q=min{i|u到vi有路}矛盾。因此q>p+1不可能，只可能是q≤p+1。當q=p+1時，有經(jīng)過每個結點的路v1v2…vp…u…vp+1vp+2…vm,如下圖(a)所示。當q≤p時，有一條經(jīng)過每個結點的路v1v2…vq…vp…u…vq…vpvp+1…vm,如下圖(b)所示。綜上，定理得證。14．解：用Dijkstra算法，將計算結果列表如下：結點步驟kv1v2v3v4v5v6v701234560/v1322/v7∞∞1077/v6∞∞∞∞161616/v3∞1010888/v6∞744/v211/v1由上表可知，v1到v7的最短鏈是1；v1到v2，中間經(jīng)過結點是v7，其最短鏈是2；v1到v3，中間經(jīng)過結點v7，v2和v6，其最短鏈是7；v1到v4，中間經(jīng)過結點v7，v2，v6和v3，其最短鏈是16；v1到v5，中間經(jīng)過結點v7，v2和v6，其最短鏈是8。15．解：關聯(lián)矩陣為M=?11000

第六章習題1．解：由歐拉公式n-m+r=2可知，此題區(qū)域數(shù)目R=2+E-V，故R=2+E-V=2+14-10=6；R=2+E-V=2+7-6=3；R=2+E-V=2+60-25=37；R=2+E-V=2+13-14=1；2．解：由歐拉公式n-m+r=2可知，此題頂點數(shù)V=2+E-R，故V=2+E-R=2+6-3=5;V=2+E-R=2+4-1=5;V=2+E-R=2+10-8=4;V=2+E-R=2+27-11=18;3．解：對于平面圖有:邊數(shù)小于等于3倍頂點數(shù)減6。所以對于8個頂點的平面圖而言，邊數(shù)最多可能是3×8-6=18。對于4個頂點的平面圖而言，邊數(shù)最多可能是3×4-6=6。4．解：(a)該圖的一種2-著色如下圖所示：從v1開始的6個循環(huán)：v1v3v2v4v1，v1v3v2v5v1，v1v3v2v6v1，v1v4v2v5v1，v1v4v2v6v1，v1v5v2v6v1成為偶圖的充分必要條件是Ｇ的所有回路的長度均為偶數(shù)，所以這個圖的回路都是偶數(shù)長度的。該題6個從v1開始的循環(huán)長度都是4，符合定理。5．證明：在上圖的(a,c)和(j,i)邊上新增一點，并使用A和B標記所得圖的頂點，如下圖所示。上圖有哈密爾頓圖回路當且僅當下圖有哈密爾頓回路。而下圖有6個A和7個B，相差1個，因此沒有哈密爾頓回路，所以上圖也沒有哈密爾頓回路。6．解：令G'=G+[v2,v3]，且v2,v3不相鄰，d(v2)+d(v3)≥7。G'若是哈密爾頓圖，G也是哈密爾頓圖。因為在G'中，δ(G')≥(7/2)，可知G'是哈密爾頓圖，故G也是哈密爾頓圖。 G的哈密爾頓圈是：v1v2v4v5v6v3v7v1。7．證明：用反證法。假設G不是哈密爾頓圖，必存在v1,v2∈V，使得d(v1)+d(v2)≤m-1。在圖G-{v1,v2}中，其結點數(shù)為|V|-2=m-2，故它的邊數(shù)≤(1/2)(m-2)(m-3)。G中的邊數(shù)n，有n≤(1/2)(m-2)(m-3)+(m-1)＜(1/2)(m-2)(m-3)+m=(m?128．證明：給定彼得森圖G如圖所示，令邊集E={(v1,v6),(v2,v7),(v3,v8),(v4,v9),(v5,v10)},于是G-E為非連通圖。故G中任意哈密爾頓圈必含E中的偶數(shù)條邊。若G中某圈只含E中兩條邊，則該圈不可能是哈密爾頓圈。于是，G中每一個哈密爾頓圈必含E中4條邊。 設C是含(v5,v10),(v1,v6),(v2,v7)和(v3,v8)，而不含邊(v4,v9)的哈密爾頓圈，則該圈C中必含(v4,v5),(v3,v4),(v6,v9)和(v7,v9)。又因為v3和v5在C中的度為2，所以邊(v1,v5)和(v2,v3)不在C中。此時，v1和v2在C中的度為2，所以邊(v1,v2)必在C中。但邊(v1,v2),(v2,v7),(v7,v9),(v9,v6)和(v6,v1)構成一圈且在C中，這是不可能的。所以，彼得森圖G不是哈密爾頓圖。9．證明：令|V1|=m1,則|V2|=m-m1,于是有n≤m1(m-m1)=m1m-m1因為(m/2-m1)2≥0，即m2/4≥mm1-m12,故n≤m10．解：它們的對偶圖如下圖所示：11．解：如下圖所示：12．解：在圖G1中，存在奇度結點，如v2,v4等，而在圖G2中，每個結點都是偶結點。所以G1不是歐拉圖，G2是歐拉圖。G2的歐拉圈是v1v2v3v2v11v4v3v11v5v4v5v6v11v10v6v7v6v9v7v8v9v10v2v9v1v8v1。

第七章習題1．解：是。二叉樹是有序樹，每個結點最多兩棵子樹。一般樹是無序樹，且每個結點可以有多棵子樹。2．解：(a)前序為：ABDEHKCFIJLMG中序為：DBKHEAIFLJMCG后序為：DKHEBILMJFGCA3．解：具有六個結點的不同的樹如下圖所示：4．證明：設G是一棵樹且e是G的一條邊。由于G無回路，所以e包含在G的無回路部分中，由定理“當且僅當G的一條邊e不包含在G的回路中時，e才是割邊”可知，e是G的一條割邊。反之，設G連通但不是樹，則G包含一條回路C，則C中的邊不會是G的割邊。5．證明：用反證法。令T=<V,E'>是簡單連通無向圖G=<V,E>的生成圖。假設存在G的一割邊集E"，使E'∩E"=?，即割邊集E"與生成樹T沒有公共邊。于是，刪去割邊集E"后，留下一棵完整的生成樹T，這表明刪去一割邊集后，不能將圖分成兩個分圖，這與割邊集的定義相矛盾。故G的每個割邊集至少含有T中一條邊。6．解：對應二叉樹如下圖所示：7．解：求解如下圖所示：8．解：根據(jù)題意求解該樹如下圖：9．解：對應的二叉樹求解如下圖T'所示。10．解：最優(yōu)二叉樹求解如下：11．解：根據(jù)題意畫出下圖(a)，對應二叉樹如下圖(b)：習題冊第8章1、設A=P({a,b})，寫出A上的和～運算的運算表，是否滿足封閉性。答：由運算表可知和～對于A都滿足封閉性。2、設代數(shù)系統(tǒng)<A,*>，A中任意元素x和y,x?y=x+y+5xy,(1)判斷*運算是否滿足交換律和結合律，并說明理由.(2)求出*運算的單位元、零元和所有可逆元素的逆元.答：(1)*運算可交換，可結合.任取A中元素x,yx?y=x+y+5xy=y+x+5yx=y?x,任取A中元素x,y,z(x?y)?z=(x+y+5xy)+z+5(x+y+5xy)z=x+y+z+5xy+5xz+5yz+25xyzx?(y?z)=x+(y+z+5yz)+5x(y+z+5yz)=x+y+z+5xy+5xz+5yz+25xyz(x?y)?z=x?(y?z)(2)設*運算的單位元和零元分別為e和θ，則對于任意x有x?e=x成立，即x+e+5xe=x則e=0由于*運算可交換，所以0是幺元。對于任意x有x?θ=θ成立，即x+θ+5xθ=θx+5xθ=0θ=-1/5對于任意x，設x的逆元為y,則有x?y=0成立，即x+y+5xy=0(5x+1)y=-xy=-x/(5x+1)(x≠-1/5)因此當x≠-1/5時，-x/(5x+1)是x的逆元。3、設*是集合A上可結合的二元運算，且a,bA,若a?b=b?a，則a=b。試證明：（1）aA,a?a=a，即a是等冪元；（2）a,bA,a?b?a=a;（3）a,b,cA,a?b?c=a?c。證明：（1）aA,記b=a?a。因為*是可結合的，故有b*a=(a*a)*a=a*(a*a)=a*b。由已知條件可得a=a*a。（2）a,bA,因為由（1），a*(a*b*a)=(a*a)*(b*a)=a*(b*a),(a*b*a)*a=(a*b)*(a*a)=(a*b)*a=a*(b*a)。故a*(a*b*a)=(a*b*a)*a，從而a*b*a=a。（3）a,b,cA,（a*b*c）*（a*c）=（（a*b*c）*a）*c=(a*(b*c)*a)*c且(a*c)*(a*b*c)=a*(c*(a*b*c))=a*(c*(a*b)*c))。由（2）可知a*(b*c)*a=a且c*(a*b)*c=c，故（a*b*c）*（a*c）=(a*(b*c)*a)*c=a*c且(a*c)*(a*b*c)=a*(c*(a*b)*c))=a*c，即（a*b*c）*（a*c）=(a*c)*(a*b*c)。從而由已知條件知，a*b*c=a*c。4、證明代數(shù)系統(tǒng)(N3,+3)到(N6,+6)單一同態(tài)。證明：今構造映射函數(shù)如下：f(0)=0,f(1)=2,f(2)=4,試證明f是同態(tài)映射。函數(shù)f寫成f(k)=2k，f(a+3b)=2(a+3b)=2(a+b-3[(a+b)/3])=2a+2b-6[(2a+2b)/6]=2a+62b=f(a)+6f(b)所以代數(shù)系統(tǒng)(N3,+3)到(N6,+6)存在同態(tài)映射f,f為單一同態(tài)。5、設<A,*>為半群，aA。令Aa={ai|iI+}。試證<Aa,*>是<A,*>的子半群。證明：b，cAa，則存在k,lI+，使得b=ak,c=al。從而b*c=ak*al=ak+l。因為k+lI+，所以b*cAa，即Aa關于運算*封閉。故<Aa,*>是<A,*>的子半群。6、Z上的二元運算*定義為：a,bZ，a*b=a+b-2。試證：<Z,*>為獨異點。證明：（1）a,bZ，a+b-2Z，滿足封閉性。（2）a,b,cZ，(a*b)*c=(a*b)+c-2=(a+b-2)+c-2=a+b+c-4,a*(b*c)=a+(b*c)-2=a+(b+c-2)-2=a+b+c-4。故(a*b)*c=a*(b*c)，從而*滿足結合律。（3）記e=2。對aZ，a*2=a+2-2=a=2+a-2=2*a.。故e=2是Z關于運算*的單位元。綜上所述，<Z,*>為獨異點。設（A,*）是一個獨異點，使得對于A中每個x，x*x=e，其中e是單位元，證明（A，*）是阿貝爾群。證明：每個xA逆元均為自己，(A,*)是群。a*b=a*e*b=a*((a*b)*(a*b))*b=(a*a)*(b*a)*(b*b)=e*(b*a)*e=b*a(可交換)。8、設<G,>是一個群，則對于a,b∈G，必有唯一的x∈G，使得ax=b。證明：因為a-1*b∈G，且a*(a-1*b)=(a*a-1)*b=e*b=b，所以對于a,b∈G，必有x∈G，使得ax=b。若x1,x2都滿足要求。即ax1=b且ax2=b。故ax1=ax2。由于*滿足消去律，故x1=x2。從而對于a,b∈G，必有唯一的x∈G，使得ax=b。設<A,>是群，A中元素a,b，且a的階數(shù)是2，b的階數(shù)是3，如果a*b=b*a，證明a*b是6階元素。證明：由于a*b=b*a，所以(a*b)6=a6*b6=e現(xiàn)再證6是使(a*b)6=e的最小正整數(shù)。根據(jù)定理：設<A,*>為群，a是A中元素，且a的階數(shù)為k，若an=e，n是k的整數(shù)倍。若a*b是k階元素，k只能是6的因子，即ｋ只能是2，3，6。由于(a*b)2＝a2*b2＝ｅ*b2＝b2≠ｅ；(a*b)3＝a3*b3＝a3*e＝a≠ｅ；由此可知其階數(shù)為6。10、證明代數(shù)系統(tǒng)（｛1,i,-1,-i｝，·）和代數(shù)系統(tǒng)（｛｝,o）是否都是群，·是復數(shù)乘法，o是矩陣乘法，并且判別是否同構。解：（1）寫出（｛1,i,-1,-i｝，·）的運算表·1i-1-i11i-1-iii-1-i1-1-1-i1i-i-i1i-1通過運算表可以看出具有封閉性，復數(shù)乘法滿足結合性，幺元為1，i與-i互為逆元，-1逆元等于本身，所以（｛1,i,-1,-i｝，·）是群。寫出（｛｝,o）的運算表·通過運算表可以看出具有封閉性，矩陣乘法滿足結合性，幺元為，每個元素的逆元等于本身，所以（｛1,i,-1,-i｝，·）是群。根據(jù)運算表得到（｛1,i,-1,-i｝，·）中e=1,（｛｝,o），e=且（｛1,i,-1,-i｝，·）中i與-i互逆，而（｛｝,o）每個元素都是自己的逆，因此不同構。11、設群G的運算表如表所示，求出每個元素的階數(shù)，并構造所有子群。解：通過運算表可以看出a為幺元。分別找出其他元素的階數(shù)，b階數(shù)為6，b的逆元為f,f階數(shù)也為6。c階數(shù)為3，c的逆元e，所以e階數(shù)也為3。d階數(shù)為2。子群：一階子群{a},二階子群{d1,d2}={a,d},三階子群{c1,c2,c3}={c,e,a},六階子群{a,b,c,d,e,f}。12、設群<B,*>為群<A,*>的子群，它是群<A,*>的正規(guī)子群(a)(a∈A→aBa-1B)。證明充分性：假設對任意aA，有aBa-1B，再證aB=Ba。任意bB,a*baB,a*b*a-1aBa-1因aBa-1B，則對某個b1B，有a*b*a-1=b1于是a*b=(a*b*a-1)*a=b1*a可見b1*aBa故aBBa只要注意：a-1Ba=a-1B(a-1)-1B，可類似地證明BaaB，于是aB=Ba。必要性：假設對每個aA，任意bB,有aBBa且a*b*a-1aBa-1。則因aB=Ba，必存在b1B，使得a*b=b1*a于是a*b*a-1=(b1*a)*a-1=b1因此a*b*a-1B，故aBa-1B。設A={1,-1,i,-i},對于復數(shù)的乘法運算，證明<A,*>是循環(huán)群。解：幺元為1，(-1)2=1,-1是二階元素，i2=-1，i3=-i，i4=1，所以i為四階元素，(-i)2=-1，(-i)3=i，(-i)4=1，所以-i為四階元素，由上述可得i和-i都是生成元，所以<A,*>是循環(huán)群。I上的二元運算*定義為：a,bI，a*b=a+b-2。試問<I,*>是循環(huán)群嗎？解：<I,*>是循環(huán)群。因為<I,*>是無限階的循環(huán)群，則它只有兩個生成元。1和3是它的兩個生成元。因為an=na-2(n-1)，故1n=n-2(n-1)=2-n。從而對任一個kI,k=2-(2-k)=12-k，故1是的生成元。又因為1和3關于*互為逆元，故3也是<I,*>的生成元。15、證明群(N12,+12)和群(N13-{0},×13)同構,并寫出同構映射,并寫出群(N13-{0},×13)所有的子群。(1)群(N12,+12)的生成元為1，(N13-{0},×13)的生成元為,2，20=1,21=2,22=4,23=8,24=3,25=6,26=12,27=11,28=9,29=5,210=10,211=7,212=1，根據(jù)定理k階循環(huán)群同構于(Nk,+k)，f(k)=ak，a為生成元，可得群(N12,+12)和群(N13-{0},×13)同構。(2)設置函數(shù)f：N12→N13-{0}，f(k)=ak=2kf(0)=20=1，f(1)=21=2，f(2)=22,...,f(11)=211可得證f(i+j)=2i+j=2i×132j=f(i)×13f(j)。根據(jù)(N12,+12)的子群{0},{0,6},{0,4,8},{0,3,6,9},{0,2,4,6,8,10},N12(N13-{0},×13)的子群群{20},{20,26},{20,24,28},{20,23,26,29},{20,22,24,26,28,210},N13-{0}。16、求循環(huán)群C12={e,a,a2,…,a11}中H={e,a4,a8}的所有右陪集。解：因為|C12|=12，|H|=3，所以H的不同右陪集有4個：H，{a,a5,a9},{a2,a6,a10},{a3,a7,a11}。17、設e是奇數(shù)階交換群<G,*>的單位元，則G的所有元素之積為e。證明：設G=<{e,a,a,…,a},*>，n為正整數(shù)。因為G的階數(shù)為奇數(shù)2n+1，所以由拉格朗日定理知G中不存在2階元素，即除了單位元e以外，G的所有元素的階都大于2。故對G中的任一非單位元a，它的逆元a不是它本身，且G中不同的元素有不同的逆元。由此可見，G中的2n個非單位元構成互為逆元的n對元素。因為G是交換群，故G的所有元素之積可變成單位元和n對互為逆元的元素之積的積，從而結果為e。18、6階群必有3階子群。證明設<A,>是是6階群，e是幺元。A中元素的階數(shù)可能為1，2，3或6。如果A中有6階元a，即o(a)=6，則G是6階循環(huán)群，a2為3階元素，得知({a2,a4,a6}，*)為3階子群。如果A中有3階元a，({a,a2,a3}，*)為3階子群。如果非幺元都是2階元素，則為克萊因群，克萊因群一定是可交換群，在A中任取兩個不同的非幺元的a和b,令H={e,a,b,a*b}，通過驗證可知，*對于H是封閉的，(H,*)是(A,)的4階子群，而(A，*)是6階群，根據(jù)Lagrange定理，這是不可能的。得證6階群必有3階子群。19、在4次對稱群中找出