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