【正文】 為整數(shù)集合，在 Z 上定義二元運算。，對于所有 x，y ∈Z都有x。y=x + y，試問〈Z?！的芊駱嫵扇?，為什麼 ？答：由題已知，集合Z滿足封閉性；二元運算滿足結合律，依此集合Z為半群；有幺元為 －5， e,則一個方程來自于二元運算定義, 即e。x= e + x，一個方程來自該特殊元素的定義的性質,即e。x = : e+x=x x,e=0 的結果不是就有了嗎!；,也要解聯(lián)方程,如同求幺元一樣的道理；結論是：代數(shù)系統(tǒng)〈 Z?！禈嫵扇骸５诙糠謭D論方法第四章 圖41 10 個頂點的簡單圖 G 中有 4 個奇度頂點，問 G 的補圖中有幾個偶數(shù)度頂點 ？ 答：因為10階完全圖的每個頂點的度數(shù)都是n1=9――為奇數(shù)。這樣一來，一個無向簡單圖 G 的某頂點的度數(shù)是奇數(shù)，其補圖的相應頂點必偶數(shù)，因為一個偶數(shù)與一個奇數(shù)之和才是奇數(shù)．所以，Ｇ的補圖中應有 104＝6 個奇數(shù)度頂點。42 是非判斷：無向圖G中有10條邊,4個3度頂點,其余頂點度數(shù)全是2,共有 8 個頂點.[是]43 填空補缺：1條邊的圖 G 中，所有頂點的度數(shù)之和為[2]第五章樹51握手定理的應用（指無向樹）（1）在一棵樹中有 7 片樹葉，3 個 3 度頂點，其余都是 4 度頂點，問有(有1個4度頂點)個？（2）一棵樹有兩個 4 度頂點，3 個 3 度頂點，其余都是樹葉，問有(9個1度頂點)片？52 一棵樹中有 i 個頂點的度數(shù)為 i（i=2，…k），其余頂點都是樹葉(即一度頂點)，問樹葉多少片？設有x片,則 x=答：假設有 x 片樹葉，根據握手定理和樹的頂點與邊數(shù)的關系，有關于樹葉的方程，解方程得到樹葉數(shù) x = Σi（i—2）i + 2，（i = 2，3，……k）。53 求最優(yōu) 2 元樹：用 Huffman 算法求帶權為 1，2，3，5，7，8 的最優(yōu) 2 元樹 T。試問：（1）T 的權 W（T）？（2）樹高幾層 ？答：用 Huffman 算法，以 1，2，3，5，7，8 為權，最優(yōu) 2 元樹 T ；然后，計算并回答所求問題：（1）T 的權 W（T）= 61；（2）樹高幾層：4 層樹高。54以下給出的符號串集合中，那些是前綴碼？將結果填入[] = {0，10，110，1111}[是]B2 = {1，01，001，000}[是]B3 = {a，b，c，aa，ac，aba，abb，abc}[非]B4 = {1，11，101，001，0011}[非]55(是非判斷題)11階無向連通圖G中17條邊，其任一棵生成樹 T 中必有6條樹枝 [非]56(是非判斷題)二元正則樹有奇數(shù)個頂點。[是]57 在某次通信中 a，b，c，d，e 出現(xiàn)的頻率分別為 5%。10%。20%。30%。35%.求傳輸他們的最佳前綴碼。最優(yōu)二元樹 T；；答：每個字母出現(xiàn)頻率分別為：G、D、B、E、Y：14%，O：28%；(也可以不歸一,某符號出現(xiàn)次數(shù)即為權，如右下圖).。100（近似）7.。563..4。282..2..2。..1..141414141111所以，得到編碼如下：G（000），D（001），B（100），E（101），Y（01），O（11）。第三部分邏輯推理理論第六章 命題邏輯61 判斷下列語句是否命題，簡單命題或復合命題。（1）2月 17 號新學期開始。[真命題]（2）離散數(shù)學很重要。[真命題]（3）離散數(shù)學難學嗎 ？[真命題]（4）C 語言具有高級語言的簡潔性和匯編語言的靈活性。[復合命題]（5）x + 5 大于 2。[真命題]（6）今天沒有下雨，也沒有太陽，是陰天。[復合命題]62 將下列命題符號化.（1）2 是偶素數(shù)。（2）小李不是不聰明，而是不好學。（3）明天考試英語或考數(shù)學。（兼容或）（4）你明天不去上海，就去北京。（排斥或）答：（1）符號化為： p ∧ q。（2）符號化為：p ∧ ﹃q。（3）符號化為：p ∨ q。（4）符號化為：（﹃p ∧ q）∨（p ∧ ﹃q）。63分別用等值演算法,真值表法,主析取范式法,判斷下列命題公式的類型.（1）﹃（p→q）∧ q；（2）（（p→q）∧ p）→q；（3）（p→q）∧ q。答：（1）0；（2）Σ（0，1，2，3）；（3）Σ（1，3）。以下兩題(64。65)為選擇題,將正確者填入[] 令 p：經一塹；q：長一智。命題’’只有經一塹，才能長一智’’符號化為[B]A． p→q；B．q→p；C．p∧q；D．﹁q→﹁p65 p：天氣好；q：我去游玩．命題 ”如果天氣好，則我去游玩” 符號化為［B］A． p→q；B．q→p；C．p∧q；D．﹁q→p66證明題:用不同方法(必須有構造證明法)判斷推理結果是否正確。如果今天下雨，則明天不上體育課。今天下雨了。所以，明天沒有上體育課。答：將公式分成前提及結論。前提：（p→﹃q），p；結論：﹃q；證明：（1）（p→﹃q）前提引入（2）p前提引入（3）（p→﹃q）∧p（1）（2）假言推理（4）﹃q要證明的結論與證明結果一致，所以推理正確。第七章謂詞邏輯71 在謂詞邏輯中用 0 元謂詞將下列命題符號化（1）這臺機器不能用。（2）如果 2 ＞ 3，則 2 ＞ 5。答：（1）﹃F（a）。（2）L（a，b）→ H（a，z）。72 填空補缺題：設域為整數(shù)集合Ｚ，命題xy彐z（xy=z）的真值為（0）73在謂詞邏輯中將下列命題符號化（1）有的馬比所有的牛跑得慢。（2）人固有一死。答：（1）符號化為：彐x（F（x）∧ 彐y（G（y）∧ H（x，y）））。（2）與（1）相仿，要注意量詞、聯(lián)結詞間的搭配：x（F（x）→y（G（y）→ H（x，y）））?！陡戒洝妨曨}符號集216。 空集, ∪ 并, ∩ 交,⊕ 對稱差,～ 絕對補,∑ 累加或主析取范式表達式縮寫 , － 普通減法, 247。 普通除法, ㏑ 自然對數(shù), ㏒ 對數(shù)，﹃ 非，量詞 ”所有”，”每個”，∨ 析取聯(lián)結詞，∧ 合取聯(lián)結詞，彐 量詞”存在”，”有的”。2010年8月12號。