課件作業(yè)題解分析與答案

1、 課件作業(yè)題解分析與答案 第一部分 集合論第一章 集合的基本概念和運(yùn)算 1-1 設(shè)集合 A =1，2，a，4，3，下面命題為真是 B A2 A； B1 A； C5 A； D2 A。題解與分析：A 是集合，2，5 不是他的元素。所以，（A）,(C)無(wú)可爭(zhēng)議的是錯(cuò)誤。然而，某集合若是另一集合子集，則子集也可以成為集合的元素，二者從而產(chǎn)生隸屬關(guān)系,例如，本題的集合A與集合2。而說(shuō)2是A的子集而不是元素,就是錯(cuò)誤的了所以，只有（B）為正確。1-2 A,B為任意集合，則他們的共同子集是 D AA； BB； CAB； D Ø 。題解與分析： 1-3 設(shè) S = N，Z，Q，R，判斷下列命題是否成

2、立 ？（1） N Q，Q S，則 N S，錯(cuò)（2）-1 Z，Z S， 則 -1 S 。錯(cuò)題解與分析：S 實(shí)際上是實(shí)數(shù)集合 R ，自然數(shù)集合，有理數(shù)集合的集合，諸如“N S”，“Q S”，“2 S”，“-1 S” 之類(lèi)的命題都是錯(cuò)誤的。所以，(1）,(2)都錯(cuò)。 1-4 設(shè)集合 A =3，4，B = 4，3 Ø ， C = 4，3 Ø ，D = 3，4，Ø ，E = xx R 并且 x2 - 7x + 12 = 0，F(xiàn) = 4，Ø ，3，3，試問(wèn)哪兩個(gè)集合之間可用等號(hào)表示 ？題解與分析：根據(jù)題意，A = E；B = C；D = F 。 1-5 用列元法表示

3、下列集合（1）A = xx N 且 x2 9 （2）A = xx N 且 3x 3 題解與分析：本題以謂詞給出集合的表達(dá)式。要求把解析表達(dá)式所含的元素列出；當(dāng)然，有的集合的元素需要通過(guò)計(jì)算才能得到。所以結(jié)果為：（1）A = 0，1，2，3 ； （2）A = 1，2，3，4， = Z+；第二章 二元關(guān)系 2-1 給定 X =（3, 2，1），R 是 X 上的二元關(guān)系，其表達(dá)式如下： R = x，yx，y X 且 x y 求：(1)domR =?; (2)ranR =?; (3)R 的性質(zhì)。題解與分析：所謂謂詞表達(dá)法，即是將集合中所有元素的共同性質(zhì)用一個(gè)謂詞概括起來(lái)，如本題幾例所示。有的書(shū)上稱(chēng)其為

4、抽象原則。反過(guò)來(lái)，列元法則是遵照元素的性質(zhì)和要求，逐一將他們列出來(lái)，以備下用,結(jié)果如下：R = <2，3>，<1,2>，<1,3>；DomR=R中所有有序?qū)Φ膞=2,1,1=2,1;RanR=R中所有有序?qū)Φ膟=3,2,3=3,2；R 的性質(zhì):反自反,反對(duì)稱(chēng),傳遞性質(zhì).2-2 設(shè) R 是正整數(shù)集合上的關(guān)系，由方程 x + 3y = 12 決定，即 R = x，yx，y Z+ 且 x + 3y = 12，試求：（1）R 的列元表達(dá)式； （2）給出 dom（R 。R）。 題解與分析：在求解關(guān)系的諸問(wèn)題時(shí)，較好的辦法是列出關(guān)系的每個(gè)有序?qū)?，以及解決其他問(wèn)題。根據(jù)方

5、程式有：y=4-x/3，x 只能取 3，6,9。 結(jié)果如下：（1）R = 3，3,6，2,9，1； 至于(2),望大家認(rèn)真完成合成運(yùn)算 R 。R=<3,3>.然后,給出 R 。R 的定義域,即（2）dom（R 。R）= 3。2-3 判斷下列映射 f 是否是 A 到 B 的函數(shù)；并對(duì)其中的 f：AB 指出他的性質(zhì)，即是否單射、滿(mǎn)射和雙射，并說(shuō)明為什么。 （1）A = 1，2，3，B = 4，5， f = 1，42，43，5。（2）A = 1，2，3 = B， f = 1，12，23，3。（3）A = B = R， f = x 。（4）A = B = N， f = x2 。（5）A =

6、 B = N， f = x + 1 。分析與題解：判斷映射的性質(zhì)，要分三步考慮：第一，是否函數(shù) ？第二，是否 A 到 B 的函數(shù)？第三，是否單射、滿(mǎn)射。結(jié)論如下：（1） 是 A 到 B 的函數(shù)，是滿(mǎn)射而不是單射；（2） 是雙射；（3）是雙射；（4）是單射，而不是滿(mǎn)射；（5）是單射而不是滿(mǎn)射。2-4 設(shè) A =1，2，3，4，A 上的二元關(guān)系 R =x，y（x-y）能被3整除，則自然映射 g：AA/R使 g(1) = C A1,2； B1,3； C1,4； D1。分析與題解：大家明白，在本題條件下，只有0和3才能被3整除，這樣一來(lái)，在關(guān)系中，必有<1,1>,<4,1>兩個(gè)

7、有序?qū)Τ霈F(xiàn)，就是說(shuō)，自然映射 g：AA/R使 g(1) =11,42-5 設(shè) A =1，2，3，則商集A/IA = D A3； B2； C1； D1，2，3。分析與題解：記住商集的元素是等價(jià)類(lèi)而各元素的等價(jià)類(lèi)分別為11，22，33所以有A/IA2-6設(shè)(x)x+1，(x)x-1 都是從實(shí)數(shù)集合到的函數(shù)，則。 C Ax+1； Bx-1； Cx； Dx2。分析與題解：函數(shù)的合成運(yùn)算很簡(jiǎn)單即將g(x)做為一個(gè)整體代入到f(x)的x處即可本題為：f(g(x)=(x-1)+1)=x. 第三章 結(jié)構(gòu)代數(shù)(群論初步)3-1 給出集合及二元運(yùn)算，判斷是否代數(shù)系統(tǒng)，何種代數(shù)系統(tǒng) ？（1）S1 = 1，1/4,1

8、/3,1/2,2，3，4，二元運(yùn)算 * 是普通乘法。（2）S2 = a1，a2，an，ai R，i = 1，2，n ；二元運(yùn)算 。定義如下：對(duì)于所有 ai，aj S2，都有 ai 。aj = ai 。（3）S3 = 0，1，二元運(yùn)算 * 是普通乘法。分析與題解：一個(gè)代數(shù)系統(tǒng)，通常由三個(gè)條件構(gòu)成。第一，要有一個(gè)集合；第二，要有若干個(gè) n 元運(yùn)算；第三，n 元運(yùn)算在集合內(nèi)自我封閉。所以，我們的結(jié)論應(yīng)是：（1）二元運(yùn)算*在S1上不封閉所以，S1，*不能構(gòu)成代數(shù)系統(tǒng)。（2）由二元運(yùn)算的定義不難知道，。在 S2 內(nèi)是封閉的，所以，S2， 。構(gòu)成代數(shù)系統(tǒng)；然后看該代數(shù)系統(tǒng)的類(lèi)型：該代數(shù)系統(tǒng)只是半群。（3）

9、很明顯，0，1，*構(gòu)成代數(shù)系統(tǒng)；滿(mǎn)足結(jié)合律，為半群；1是幺元，為獨(dú)異點(diǎn)；而 0 為零元；結(jié)論：僅為獨(dú)異點(diǎn)，而不是群。3-2 在自然數(shù)集合上，下列那種運(yùn)算是可結(jié)合的 A Ax*y = max(x,y) ； Bx*y = 2x+y ；Cx*y = x2+y2 ； Dx*y =x-y.分析與題解：結(jié)合律的驗(yàn)證很簡(jiǎn)單然而，沒(méi)有竅門(mén)只有在（x*y）*z=x*(y*z)時(shí)，才可以得出滿(mǎn)足結(jié)合律的結(jié)論3-3 設(shè) Z 為整數(shù)集合，在 Z 上定義二元運(yùn)算 。，對(duì)于所有 x，y Z 都有 x 。y = x + y 5，試問(wèn)Z，。能否構(gòu)成群，為什麼 ？分析與題解：判別一個(gè)代數(shù)系統(tǒng)是否是群，當(dāng)然要滿(mǎn)足群的定義條件。然

10、而，判別過(guò)程要分步走。因?yàn)轭}中以代數(shù)系統(tǒng)形式給出，第一步封閉性問(wèn)題判斷可省去.之所以說(shuō)該步驟可以略去,是在題中已經(jīng)告知代數(shù)系統(tǒng)成立的前提下.否則要進(jìn)行討論:此二元運(yùn)算中,只有加減法,在集合 Z 中必然滿(mǎn)足封閉性；第二步，二元運(yùn)算滿(mǎn)足結(jié)合律，以決定半群；第三步，有幺元為 5，為獨(dú)異點(diǎn).必須記住,求特殊元素時(shí),都要解聯(lián)立方程.假設(shè)代數(shù)系統(tǒng)的幺元是集合中的元素 e,則一個(gè)方程來(lái)自于二元運(yùn)算定義, 即e 。x = e + x 5，一個(gè)方程來(lái)自該特殊元素的定義的性質(zhì),即e 。x = x.由此而來(lái)的兩個(gè)方程聯(lián)立結(jié)果就有: e+x5=x 成立.削去 x,e=5 的結(jié)果不是就有了嗎!；第四步，每個(gè)元素都有逆.

11、求每個(gè)元素的逆元素,也要解聯(lián)方程,如同求幺元一樣的道理；第五步，結(jié)論是：代數(shù)系統(tǒng) Z，。構(gòu)成群。 第二部分 圖論方法第四章 圖 4-1 10 個(gè)頂點(diǎn)的簡(jiǎn)單圖 G 中有 4 個(gè)奇度頂點(diǎn)，問(wèn) G 的補(bǔ)圖中有幾個(gè)奇度頂點(diǎn) ？題解分析：提到圖的補(bǔ)圖，必須首先想到完全圖.因?yàn)?0階完全圖的每個(gè)頂點(diǎn)的度數(shù)都是n-1=9為奇數(shù)。這樣一來(lái)，一個(gè)無(wú)向簡(jiǎn)單圖 G 的某頂點(diǎn)的度數(shù)是奇數(shù)，其補(bǔ)圖的相應(yīng)頂點(diǎn)必偶數(shù)，因?yàn)橐粋€(gè)偶數(shù)與一個(gè)奇數(shù)之和才是奇數(shù)所以，的補(bǔ)圖中應(yīng)有 10-46 個(gè)奇數(shù)度頂點(diǎn)。4-2 是非判斷：無(wú)向圖G中有10條邊,4個(gè)3度頂點(diǎn),其余頂點(diǎn)度數(shù)全是2,共有 8 個(gè)頂點(diǎn). 是分析與題解：握手定理告訴我們：2

12、04x32，所以，4，即4個(gè)2度頂點(diǎn)，共8個(gè)頂點(diǎn)4-3 填空補(bǔ)缺：1條邊的圖 G 中，所有頂點(diǎn)的度數(shù)之和為 分析與題解：握手定理是普適定理任何無(wú)向圖中，所有頂點(diǎn)的度數(shù)之和都是邊的兩倍第五章 樹(shù)5-1 握手定理的應(yīng)用（指無(wú)向樹(shù)）（1）在一棵樹(shù)中有 7 片樹(shù)葉，3 個(gè) 3 度頂點(diǎn)，其余都是 4 度頂點(diǎn)，問(wèn)有幾個(gè)？（2）一棵樹(shù)有兩個(gè) 4 度頂點(diǎn)，3 個(gè) 3 度頂點(diǎn)，其余都是樹(shù)葉，問(wèn)有幾片？題解分析：對(duì)于圖論中樹(shù)的有關(guān)問(wèn)題的解決，無(wú)非是利用握手定理以及利用樹(shù)是連續(xù)而無(wú)回路的性質(zhì)，即 d（Vi）= 2m 定理和利用 n1= m 定理。所以有如下結(jié)果：（1）有 1 個(gè) 4 度頂點(diǎn)； （2） 9 個(gè) 1 度

13、頂點(diǎn)。 5-2 一棵樹(shù)中有 i 個(gè)頂點(diǎn)的度數(shù)為 i（=2，k），其余頂點(diǎn)都是樹(shù)葉，問(wèn)樹(shù)葉多少片？題解分析：假設(shè)有 x 片樹(shù)葉，根據(jù)握手定理和樹(shù)的頂點(diǎn)與邊數(shù)的關(guān)系，有關(guān)于樹(shù)葉的方程，解方程得到樹(shù)葉數(shù) x = i（i2） i + 2，（i = 2，3，k）。5-3 求最優(yōu) 2 元樹(shù)：用 Huffman 算法求帶權(quán)為 1，2，3，5，7，8 的最優(yōu) 2 元樹(shù) T。試問(wèn)：（1） T 的權(quán) W（T）？ （2）樹(shù)高幾層 ？ 題解分析：用 Huffman 算法，以 1，2，3，5，7，8 為權(quán)，最優(yōu) 2 元樹(shù) T ；然后，計(jì)算并回答所求問(wèn)題：（1）T 的權(quán) W（T）= 61；（2）樹(shù)高幾層：4 層樹(shù)高。5-

14、4 以下給出的符號(hào)串集合中，那些是前綴碼？ B1 = 0，10，110，1111； B2 = 1，01，001，000； B3 = a，b，c，aa，ac，aba，abb，abc B4 = 1，11，101，001，0011題解分析：根據(jù)前綴碼的定義，判斷 B1，B2 是前綴碼，而 B3，B4 不是。5-5 11 階無(wú)向連通圖 G 中有 17 條邊，其任一棵生成樹(shù) T 中必有6條樹(shù)枝 非 題解分析：階無(wú)向連通圖 G 的任一棵生成樹(shù) T 中必有條樹(shù)枝，而與邊數(shù)無(wú)關(guān)所對(duì)應(yīng)的基本回路數(shù)才與邊數(shù)有關(guān)系務(wù)必注意此點(diǎn)！ 5-6 二元正則樹(shù)有奇數(shù)個(gè)頂點(diǎn)。 對(duì) 題解分析：在書(shū)中第頁(yè)，正則條件是：s=(t-1)

15、/(r-1)當(dāng)時(shí)，分母消失，便有（）！，得到2-1，由此可判斷頂點(diǎn)數(shù)為奇數(shù)5-7 奧運(yùn)年歡送外國(guó)朋友時(shí),在網(wǎng)上傳輸 GOODBYE 的最佳前綴碼,共用多少位二 進(jìn)制碼。 求：1、最優(yōu)二元樹(shù) T； 2. 30位； 3、每個(gè)字母的碼字；題解分析：每個(gè)字母出現(xiàn)頻率分別為：G、D、B、E、Y：14%，O：28%；(也可以不歸一,某符號(hào)出現(xiàn)次數(shù)即為權(quán)，如右下圖). 。100（近似） 7. 42。 。56 3. .4 28。 。 28。 。28 2. . 2. .2 。 。 14 。 。 . . 1 . .14 14 14 14 1 1 1 1 所以，得到編碼如下：G（000），D（001），B（100）

16、，E（101），Y（01），O（11）。第三部分 邏輯推理理論第六章 命題邏輯 6-1 判斷下列語(yǔ)句是否命題，簡(jiǎn)單命題或復(fù)合命題。（1）2月 17 號(hào)新學(xué)期開(kāi)始。（2）離散數(shù)學(xué)很重要。（3）離散數(shù)學(xué)難學(xué)嗎 ？（4）C 語(yǔ)言具有高級(jí)語(yǔ)言的簡(jiǎn)潔性和匯編語(yǔ)言的靈活性。（5）x + 5 大于 2 。（6）今天沒(méi)有下雨，也沒(méi)有太陽(yáng)，是陰天。題解與分析：該習(xí)題要求了解命題的概念。命題必須是具有確切結(jié)果的陳述句。若一個(gè)陳述句不能拆成兩個(gè)以上的陳述句，則這個(gè)陳述句所構(gòu)成的命題叫做簡(jiǎn)單命題或原子命題。自然，原子命題是一切復(fù)雜命題的組成單元。根據(jù)此原理判斷：（1），（2），（4），（6）是命題且是真命題；其中（4

17、），（6）是復(fù)合命題。6-2 將下列命題符號(hào)化.（1）2 是偶素?cái)?shù)。（2）小李不是不聰明，而是不好學(xué)。（3）明天考試英語(yǔ)或考數(shù)學(xué)。（兼容或）（4）你明天不去上海，就去北京。（排斥或）題解與分析：命題的符號(hào)化必須把握住一個(gè)概念：一個(gè)符號(hào)不能對(duì)一個(gè)復(fù)合命題符號(hào)化，而只能對(duì)一個(gè)簡(jiǎn)單命題符號(hào)化。而復(fù)合命題的符號(hào)化要借助于聯(lián)結(jié)詞的幫助。 小王不好學(xué)，自然 q 的真值為 0，而q 為 1?？偨Y(jié)果如下：（1）符號(hào)化為： p q。（2）符號(hào)化為：p q。（3）符號(hào)化為：p q。（4）符號(hào)化為：（p q）（p q）。6-3 用等值演算法求下列命題公式的主析取范式（1）（pq） q； （2）（pq） p）q； （

18、3）（pq） q。題解與分析：（1） 0； （2）（0，1，2，3）； （3）（1，3）。6-4 令 p：經(jīng)一塹；q：長(zhǎng)一智。命題只有經(jīng)一塹，才能長(zhǎng)一智符號(hào)化為 BA pq； B qp； C pq； D qp題解與分析：只有后面的論述為必要條件，所以為后件，不要管用甚么符號(hào)表示6-5 p：天氣好；q：我去游玩命題 ”除非天氣好，否則我不去游玩” 符號(hào)化為A pq； B qp； C pq； D qp題解與分析：除非與否則不配對(duì)，分別為后件與前件，也不要管用何符號(hào)表示6-6 將下列推理命題符號(hào)化，然后用不同方法判斷推理結(jié)果是否正確。如果今天下雨，則明天不上體育課。今天下雨了。所以，明天沒(méi)有上體育課。題解與分析：首先將原子命題符號(hào)化，然后，按題意將原子命題組織成公式。再用不同方法，例如用等值演算法判斷推理的正確與否。公式是重言式，所以，推理正確。方法 1：（pq）p）q 1；方法 2：將公式分成前提及結(jié)論。 前提：（pq），p； 結(jié)論：q； 證