北京大學(xué)16秋季《離散數(shù)學(xué)》課程作業(yè)

1、精選優(yōu)質(zhì)文檔-傾情為你奉上 2016秋課件作業(yè) 第一部分 集合論第一章 集合的基本概念和運(yùn)算 1-1 設(shè)集合 A =2，3,4，5，1，下面命題為真是 （選擇題） A1 A； B2 A； C3 A； D3，2,1 A。1-2 A,B,C為任意集合，則他們的共同子集是 （選擇題） AC； BA； CB； 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è)集合 B = 4，3 Ø ， C = 4，3 Ø ，D = 3，4，Ø ，E = xx

2、 R 并且 x2 - 7x + 12 = 0，F(xiàn) = 4，Ø ，3，3，試問(wèn)：集合 B 與那個(gè)集合之間可用等號(hào)表示 （選擇題） A. C; B. D; C. E; D. F.1-5 用列元法表示下列集合：A = xx N 且 3x 3 （選擇題） A. N; B. Z; C. Q; D. Z+1-6 為何說(shuō)集合的確定具有任意性 ? (簡(jiǎn)答題)第二章 二元關(guān)系 2-1 給定 A =（3, 2，1），R 是 A 上的二元關(guān)系，其表達(dá)式如下： R = x，yx，y A 且 x y （綜合題）求：(1)domR =?; (2)ranR =?; (3)R 的性質(zhì)。 （4）商集 A/R =？ （

3、5）A 的劃分=？ （6）合成運(yùn)算（R 。R）=？ 2-2 設(shè) R 是正整數(shù)集合上的關(guān)系，由方程 x + 3y = 12 決定，即 R = x，yx，y Z+ 且 x + 3y = 12，試給出 dom（R 。R）。 （選擇題） A. 3； B. 3； C. 3，3； D.3，3。2-3 判斷下列映射 f 是否是 A 到 B 的函數(shù)； 以及函數(shù)的性質(zhì)。最后指出 f：AB 中的雙射函數(shù)。 （選擇題） （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 =

4、 N， f = x2 。（5）A = B = N， f = x + 1 。A.（1）和（2）； B.（2）和（3）； C.（3）和（4）； D.（4）和（5）2-4 設(shè)(x)x+1，(x)x-1 都是從實(shí)數(shù)集合到的函數(shù)，則。 Ax+1； Bx-1； Cx； Dx2。 2-5 關(guān)系型數(shù)據(jù)庫(kù)與關(guān)系與函數(shù)一章內(nèi)容有何聯(lián)系 ？（簡(jiǎn)答題）第三章 結(jié)構(gòu)代數(shù)(群論初步) (3-1)，(3-2)為選擇題3-1 給出集合及二元運(yùn)算，判斷是否代數(shù)系統(tǒng)，何種代數(shù)系統(tǒng) ？（1）S1 = 1，1/4,1/3,1/2,2，3，4，二元運(yùn)算 * 是普通乘法。 A不構(gòu)成代數(shù)系統(tǒng)； B只是代數(shù)系統(tǒng)。； C 半群； D群。（2）

5、S2 = a1，a2，an，ai R，i = 1，2，n ；二元運(yùn)算 。定義如下：對(duì)于所有 ai，aj S2，都有 ai 。aj = ai 。 A不構(gòu)成代數(shù)系統(tǒng)； B只是代數(shù)系統(tǒng)。； C 半群； D群。（3）S3 = 0，1，二元運(yùn)算 * 是普通乘法。 A不能構(gòu)成代數(shù)系統(tǒng)； B半群； C獨(dú)異點(diǎn)； D群。3-2 在自然數(shù)集合上，下列那種運(yùn)算是可結(jié)合的 Ax*y = max(x,y) ； Bx*y = 2x+y ；Cx*y = x2+y2 ； Dx*y =x-y.3-3 設(shè) Z 為整數(shù)集合，在 Z 上定義二元運(yùn)算 。，對(duì)于所有 x，y Z 都有 x 。y = x - y 試問(wèn)？在 Z 上二元運(yùn)算

6、。能否構(gòu)成代數(shù)系統(tǒng)，何種代數(shù)系統(tǒng)？為什麼 ？（綜合題） 第二部分 圖論方法第四章 圖 以下三題分別為： 選擇題 是非題 填空題4-1 10 個(gè)頂點(diǎn)的簡(jiǎn)單圖G中有4個(gè)奇度頂點(diǎn)，問(wèn) G 的補(bǔ)圖中有 r 個(gè)偶數(shù)度頂點(diǎn)。 Ar =10 ； Br = 6； Cr = 4； Dr = 9。4-2 是非判斷：無(wú)向圖G中有10條邊,4個(gè)3度頂點(diǎn),其余頂點(diǎn)度數(shù)全是2,共有 8 個(gè)頂點(diǎn)。 4-3 填空補(bǔ)缺：1條邊的圖 G 中，所有頂點(diǎn)的度數(shù)之和為 。第五章 樹(shù) 5-1 概述無(wú)向圖與無(wú)向樹(shù)的關(guān)系。 （簡(jiǎn)答題）5-2 握手定理的應(yīng)用（指無(wú)向樹(shù)） （計(jì)算題）（1）在一棵樹(shù)中有 7 片樹(shù)葉，3個(gè)3 度頂點(diǎn)，其余都是4 度

7、頂點(diǎn)，共幾個(gè)頂點(diǎn) （2）一棵樹(shù)有兩個(gè) 4 度頂點(diǎn)，3 個(gè) 3 度頂點(diǎn)，其余都是樹(shù)葉，問(wèn)有幾片葉 5-3 用 Huffman 算法求帶權(quán)為 1，2，3，5，7，8 的樹(shù)葉的最優(yōu) 2 元樹(shù) T。（填空題）試問(wèn)：T 的權(quán) W（T）= ( )；樹(shù)高 ( ) 層。 5-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 5-5 11 階無(wú)向連通圖 G 中有 17 條邊，其任一棵生成樹(shù) T 中必有6條樹(shù)枝 5-6 二元正則樹(shù)

8、有奇數(shù)個(gè)頂點(diǎn)。 5-7 通信中 a，b，c，d，e，f,g,h 出現(xiàn)的頻率分別為 25%;20%;20%.15%,10%,5%,4%,1%; 試完成下列要求。 （綜合題） 1、最優(yōu)二元樹(shù) T； 2、二元樹(shù)的權(quán) W（T）= ； 3、每個(gè)字母的碼字； 第三部分 邏輯推理理論第六章 命題邏輯 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)有太

9、陽(yáng)，是陰天。 （ ）命題6-2 將下列命題符號(hào)化. （填空題）（1）2 是偶素?cái)?shù)。 （2）小李不是不聰明，而是不好學(xué)。 （3）明天考試英語(yǔ)或考數(shù)學(xué)。（兼容或） 6-3 用等值演算法求下列命題公式的主析取范式，并由此指出該公式的類(lèi)型（1）（pq） q （計(jì)算題） （2）（pq） p）q （計(jì)算題） （3）（pq） q （計(jì)算題）6-4 令 p：經(jīng)一塹；q：長(zhǎng)一智。命題只有經(jīng)一塹，才能長(zhǎng)一智符號(hào)化為 A pq； B qp； C pq； D qp6-5 p：天氣好；q：我去游玩命題 ”如果天氣好，則我去游玩” 符號(hào)化為 A pq； B qp； C pq； D qp6-6 將下列推理命題符號(hào)化，然后用

10、不同方法判斷推理結(jié)果是否正確。（綜合題）如果今天不下雨，則明天上體育課。今天沒(méi)有下雨。所以，明天上體育課。題解與分析：首先將原子命題符號(hào)化，然后，按題意將原子命題組織成公式。再用不同方法，例如用等值演算法判斷推理的正確與否。公式是重言式，所以，推理正確。方法 1：等值演算法(略)方法 2: 主范式法(略);方法 3: 真值表法(略);方法 4：構(gòu)造證明法,如下: （1）將原子命題符號(hào)化： （2）按題意構(gòu)成前提： （3）按題意構(gòu)成結(jié)論： （4）證明： 第七章 謂詞邏輯 7-1 在謂詞邏輯中用 0 元謂詞將下列命題符號(hào)化 （填空題）（1）1 不是素?cái)?shù)。 。 （2）如果 2 3，則 2 5。 。 7-2 填空題：設(shè)域?yàn)檎麛?shù)集合 Z，命題xy彐z（x-y = z）的真值為 7-3 在謂詞邏輯中將下列命題符號(hào)化 （填空題）人固有一死。 。 7-4 一階邏輯與命題邏