離散數(shù)學(xué)課件作業(yè)

1、 離散數(shù)學(xué)課件作業(yè) 第一部分 集合論第一章 集合的基本概念和運(yùn)算 1-1 設(shè)集合 A =1，2，a，4，3，下面命題為真是 A2 A； B1 A； C5 A； D2 A。1-2 A,B為任意集合，則他們的共同子集是 AA； BB； CAB； D Ø 。 1-3 設(shè) S = N，Z，Q，R，判斷下列命題是否成立 ？（1） N Q，Q S，則 N S （2）-1 Z，Z S， 則 -1 S 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，&

2、#216; ，3，3，試問哪兩個(gè)集合之間可用等號表示 ？1-5 用列元法表示下列集合（1）A = xx N 且 x2 9 （2）A = xx N 且 3x 3 第二章 二元關(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ì)。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）。 2-3 判斷下列映射 f 是否是

3、 A 到 B 的函數(shù)；并對其中的 f：AB 指出他的性質(zhì)，即是否單射、滿射和雙射，并說明為什么。 （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 = B = N， f = x + 1 。2-4 設(shè) A =1，2，3，4，A 上的二元關(guān)系 R =x，y（x-y）能被3整除，則自然映射 g：AA/R使 g(1) = A1,2； B1,3； C1,4； D1。2-5 設(shè) A =1，2，3，則商集A/IA = A3； B

4、2； C1； D1，2，3。2-6設(shè)(x)x+1，(x)x-1 都是從實(shí)數(shù)集合到的函數(shù)，則。 Ax+1； Bx-1； Cx； Dx2。 第三章 結(jié)構(gòu)代數(shù)(群論初步)3-1 給出集合及二元運(yùn)算，闡述是否代數(shù)系統(tǒng)，何種代數(shù)系統(tǒng) ？（1）S1 = 1，1/4,1/3,1/2,2，3，4，二元運(yùn)算 * 是普通乘法。（2）S2 = a1，a2，an，ai R，i = 1，2，n ；二元運(yùn)算 。定義如下：對于所有 ai，aj S2，都有 ai 。aj = ai 。（3）S3 = 0，1，二元運(yùn)算 * 是普通乘法。3-2 在自然數(shù)集合上，下列那種運(yùn)算是可結(jié)合的 Ax*y = max(x,y) ； Bx*y

5、= 2x+y ；Cx*y = x2+y2 ； Dx*y =x-y.3-3 設(shè) Z 為整數(shù)集合，在 Z 上定義二元運(yùn)算 。，對于所有 x，y Z 都有 x 。y = x + y ，試問Z，。能否構(gòu)成群，為什麼 ？ 第二部分 圖論方法第四章 圖 4-1 10 個(gè)頂點(diǎn)的簡單圖 G 中有 4 個(gè)奇度頂點(diǎn)，問 G 的補(bǔ)圖中有幾個(gè)偶數(shù)度頂點(diǎn) ？4-2 是非判斷：無向圖G中有10條邊,4個(gè)3度頂點(diǎn),其余頂點(diǎn)度數(shù)全是2,共有 8 個(gè)頂點(diǎn). 4-3 填空補(bǔ)缺：1條邊的圖 G 中，所有頂點(diǎn)的度數(shù)之和為 第五章 樹5-1 握手定理的應(yīng)用（指無向樹）（1）在一棵樹中有 7 片樹葉，3 個(gè) 3 度頂點(diǎn)，其余都是 4 度

6、頂點(diǎn)，問有( )個(gè)？（2）一棵樹有兩個(gè) 4 度頂點(diǎn)，3 個(gè) 3 度頂點(diǎn)，其余都是樹葉，問有( )片？5-2 一棵樹中有 i 個(gè)頂點(diǎn)的度數(shù)為 i（i=2，k），其余頂點(diǎn)都是樹葉(即一度頂點(diǎn))，問樹葉多少片？設(shè)有x片,則 x=5-3 求最優(yōu) 2 元樹：用 Huffman 算法求帶權(quán)為 1，2，3，5，7，8 的最優(yōu) 2 元樹 T。試問：（1） T 的權(quán) W（T）？ （2）樹高幾層 ？ 5-4 以下給出的符號串集合中，那些是前綴碼？將結(jié)果填入 內(nèi). B1 = 0，10，110，1111 B2 = 1，01，001，000 B3 = a，b，c，aa，ac，aba，abb，abc B4 = 1，11，

7、101，001，0011 5-5(是非判斷題)11階無向連通圖G中17條邊，其任一棵生成樹 T 中必有6條樹枝 5-6(是非判斷題)二元正則樹有奇數(shù)個(gè)頂點(diǎn)。 5-7 在某次通信中 a，b，c，d，e 出現(xiàn)的頻率分別為 5%;10%;20%;30%;35%. 求傳輸他們的最佳前綴碼。 1、最優(yōu)二元樹 T； 2.每個(gè)字母的碼字；第三部分 邏輯推理理論第六章 命題邏輯 6-1 判斷下列語句是否命題，簡單命題或復(fù)合命題。（1）2月 17 號新學(xué)期開始。 （2）離散數(shù)學(xué)很重要。 （3）離散數(shù)學(xué)難學(xué)嗎 ？ （4）C 語言具有高級語言的簡潔性和匯編語言的靈活性。 （5）x + 5 大于 2 。 （6）今天沒

8、有下雨，也沒有太陽，是陰天。 6-2 將下列命題符號化.（1）2 是偶素?cái)?shù)。（2）小李不是不聰明，而是不好學(xué)。（3）明天考試英語或考數(shù)學(xué)。（兼容或）（4）你明天不去上海，就去北京。（排斥或）6-3 分別用等值演算法,真值表法,主析取范式法,判斷下列命題公式的類型.（1）（pq） q； （2）（pq） p）q； （3）（pq） q。以下兩題(6-4;6-5)為選擇題,將正確者填入 內(nèi).6-4 令 p：經(jīng)一塹；q：長一智。命題只有經(jīng)一塹，才能長一智符號化為 A pq； B qp； C pq； D qp6-5 p：天氣好；q：我去游玩命題 ”如果天氣好，則我去游玩” 符號化為 A pq； B qp； C pq； D qp6-6 證明題:用不同方法(必須有構(gòu)造證明法)判斷推理結(jié)果是否正確。如果今天下雨，則明天不上體育課。今天下雨了。所以，明天沒有上體育課。 第七章 謂詞邏輯 7-1 在謂詞邏輯中用 0 元謂詞將下列命題符號化（1）這臺機(jī)器不能用。（2）如果 2 3，則 2 5。7-2 填空補(bǔ)缺題：設(shè)域?yàn)檎麛?shù)集合，命題xy彐z（x-y=z）的真值為（）7-3 在謂詞邏輯中將下列命題符號化（1）有的馬比所有的牛跑得慢。（2）人固有