2016離散復(fù)習(xí)練習(xí)題

1、e41db6edf618ea416b441a78acbb2409.pdf （四）一、判斷題（每題1分，共10分）1.在命運(yùn)題邏輯中，任何命題公式的主合取范式都是存在的，并且是惟一的。 （ ）2. 011是公式的成真賦值 ( )3. ( )4. （ ）5.三種重要的二元關(guān)系是等價(jià)關(guān)系、偏序關(guān)系和函數(shù)關(guān)系，它們的共同特點(diǎn)是都具有自反性 。 ( )6. 設(shè)F,R都是二元關(guān)系,則(F·R)-1=F-1·R-1。( )7.設(shè)n是任意一個(gè)正整數(shù),則一定存在階是n的群. ( )8. 布爾代數(shù)是有界格,也是分配格. ( )9.無(wú)向完全圖（n>2）一定是哈密頓圖 ( )10.階數(shù)至少是

2、2 樹(shù)的每一條邊都是橋,因而它的邊連通度是1. （ ）二、空題（每小題分，共分） 1. 謂詞公式x(P(x,y) tQ(t,z)R(x,y,t)中量詞的轄域是_。2.設(shè)F(x):x是人，H(x,y):x與y一樣高，在一階邏輯中，命題“人都不一樣高”的符號(hào)化形式為_(kāi) _。 3.從公式分類(lèi)角度來(lái)看，它為_(kāi)式。 4.設(shè)R=<1,1>,<1,2>,<2,3>，則R的對(duì)稱(chēng)閉包是 。 5.設(shè)A,B是集合，6.<，是模6加群， 則它的生成元是 。24= 7整數(shù)加群<Z,+>是循環(huán)群，其生成元是和。8.設(shè)是偏序集,如果_ _, 則稱(chēng)是(偏序)格。9.一棵二

3、叉樹(shù)先序遍歷得ABDECF，中序遍歷得DBEACF,則后序遍歷的結(jié)果是_。 10. r=5,當(dāng)s= 時(shí)，完全二部圖才可能存在完美匹配。 。 三、計(jì)算題（1-4題每題8分；5-6題每題10分，共52分）1.R1=<1,2>,<2,1>,<2,3>,<3,2>,R2=<2,2>,<2,3>,<3,1>求：(1) R1-1 (2) R1·R2 (3)R22 (4)t(R1)(傳遞閉包)2設(shè)G=，G上的運(yùn)算是矩陣乘法。已知G構(gòu)成群。（1）指出個(gè)元素的階；（2）找出G的全部子群；（3）在同構(gòu)的意義下G是4階循環(huán)

4、群還是Klein四元群？3.(1)在一棵有2個(gè)2度頂點(diǎn)，4個(gè)3度頂點(diǎn)，其余頂點(diǎn)都是樹(shù)葉的無(wú)向樹(shù)中應(yīng)該有幾片樹(shù)葉？(2)畫(huà)出兩棵非同構(gòu)的滿(mǎn)足上述條件的無(wú)向樹(shù)。4.設(shè)<A,R>為一個(gè)偏序集，其中，A=1，2，3，4，6，9，24，54,R是A上的整除關(guān)系。（1）畫(huà)出的哈斯圖； （2）求A的極大元和極小元； （3）求B=4,6的上確界和下確界。5.求公式的主和取范式(化成M1M2M3的形式)。畫(huà)一棵帶權(quán)為2，2，2，3，3，4，5，8的最優(yōu)二叉樹(shù)T，并計(jì)算它的權(quán)W（T）。四、證明題（每小題6分，共18分）1.前提： 結(jié)論: 2.定理（子群判別法1)設(shè)H是群<G，>的非空子集，

5、則HG當(dāng)且僅當(dāng)(1)a，bH， abH；(2)aH，a1H。利用上述定理證明：設(shè)H是群<G，>的非空有限子集。若H關(guān)于封閉，則H是G的子群。3.用數(shù)學(xué)歸納法證明n階無(wú)向樹(shù)T有n-1邊。（五）一、選擇題（每小題 2分，共 20 分。請(qǐng)將答案填在下面的表格內(nèi)）1、從集合分類(lèi)的角度看,命題公式可分為(   )  A.永真式、矛盾式          B. 永真式、可滿(mǎn)足式、矛盾式 C. 可滿(mǎn)足式、矛盾式     

6、0;  D. 永真式、可滿(mǎn)足式 2、設(shè)B不含有x，等值于 (   )A.   B. C.   D.3、設(shè)S,T,M是集合，下列結(jié)論正確的是（     ）A如果ST=SM，則T=M B如果S-T=，則S=TC D4、設(shè)R是集合A上的偏序關(guān)系，則R不一定是(   )A.自反的     B. 對(duì)稱(chēng)的   C. 反對(duì)稱(chēng)的    

7、0; D. 傳遞的5 設(shè)R為實(shí)數(shù)集，定義R上4個(gè)二元運(yùn)算，不滿(mǎn)足結(jié)合律的是（ ）。A. f1(x,y)= x+y B. f2(x,y)=x-y C. f3(x,y)=xy  D. f4(x,y)=maxx,y 6、設(shè)<L,>是一個(gè)格，則它不滿(mǎn)足(   )A.交換律     B. 結(jié)合律   C. 吸收律      D. 消去律7、設(shè)A=1,2,則群的單位元和零元是(   )A. 與A 

8、     B.   A 與  C. 1與    D. 1與A 8、下列編碼是前綴碼的是(    ).A.1,11,101  B.1,001,0011 C. 1,01,001,000  D.0,00,0009、下圖中既是歐拉圖又是哈密頓圖的是（     ） A B C D 10、下圖所示的二叉樹(shù)中序遍歷的結(jié)果是（    

9、 ）Aabcde Bedcba Cbdeca Dbadce二、填空題（每題3分，共24分）1、含3個(gè)命題變項(xiàng)的命題公式的主合取范式為,則它的主析取范式為 。()2、，模4加群， 則3是 階元，33= ，3的逆元是 。 3、設(shè)V=<Z,+>,其中“+”是普通加法。，令1(x)=x, 2(x)=-x,3(x)=x+5, 4(x)=2x，其中有 個(gè)自同構(gòu).4、設(shè)是集合A=1，2，3，4,5,6上的一個(gè)置換，則把它表示成不相交的輪換的積是 。4、已知n階無(wú)向簡(jiǎn)單圖G有m條邊，則G的補(bǔ)圖有 條邊。5、一個(gè)有向圖是強(qiáng)連通的充分必要條件是 。7、已知n階無(wú)向圖G中有m條邊，各頂點(diǎn)的度數(shù)均為3。又

10、已知2n-3=m，則m= .8、在下圖中從A點(diǎn)開(kāi)始，用普里姆算法構(gòu)造最小生成樹(shù)，加入生成樹(shù)的第三條邊是 （ ）。三、計(jì)算題（每題9分，共 36分）1、已知命題公式，(1) 構(gòu)造真值表。 (2) 求主析取范式(要求通過(guò)等值演算推出)。2、R1=<1,2>,<1,3>,<2,3>, R2=<2,2>,<2,3>,<3,4>,求： (1) （） () 求 、設(shè)<A,R>為一個(gè)偏序集，其中，A=1，2，3，4，6，9，12，24,R是A上的整除關(guān)系。（1）畫(huà)R出的哈斯圖； （2）求A的極大元和極小元； （3）求B=4,

11、6的上確界和下確界。、畫(huà)一棵帶權(quán)為1，1，1，3，3，5，8的最優(yōu)二叉樹(shù)T，并計(jì)算它的權(quán)W（T）。得分閱卷人四、證明題（共 20分）1、（7分）前提： 結(jié)論: 2、（7分）A=(0,0),(0,1),(1,0),(1,3),(2,2),(2,3),(3,1),R=<(a,b),(c,d)>| (a,b),(c,d)A且a+b=c+d .(1)證明：R是A上的等價(jià)關(guān)系 (2)給出R確定的對(duì)A的劃分(分類(lèi)).3、（6分）設(shè)是群, ,證明S是G的子群. （六）一、選擇題（每小題2分，共20分）1一個(gè)命題公式或一階邏輯公式的（ ）是不惟一的。A主析取范式 B主合取范式 C前束范式 D對(duì)偶式

12、2下列四個(gè)公式正確的是 A. B. C. D.3設(shè)集合A=a，b，c，d，e，偏序關(guān)系R的哈斯圖下圖所示，則元素的關(guān)系不正確的是（ ）。A B C D4已知A,B是集合A=15，B=10，AB=20，則AB=（ ）A10 B5 C20 D135X=a，b，c，d，e，Y=1，2，3，4，f從X到Y(jié)的映射，其中f(a)=2,f(b)=4,f(c)=1,f(d)=3,f(e)=4,則f是（） A.雙射 B. 滿(mǎn)射 C. 單射 D. 不是單射也不是滿(mǎn)射6設(shè)A,B,C是三個(gè)非空集合,則( )是正確的. A. B. C. D. 7在下圖所示的哈斯圖中的偏序集不是格的是（ ）8下圖中,（ ）是歐拉圖。A

13、B C D9.關(guān)于無(wú)向樹(shù)的描述,不正確的是( ).A. 無(wú)向樹(shù)是連通圖、沒(méi)有回路,每個(gè)邊都是橋；B. 無(wú)向樹(shù)是連通圖、邊數(shù)比頂點(diǎn)數(shù)少,任意兩個(gè)頂點(diǎn)的路徑是惟一的；C. 無(wú)向樹(shù)是連通圖、沒(méi)有回路,每個(gè)頂點(diǎn)都是割點(diǎn)；D. 無(wú)向樹(shù)是連通圖、沒(méi)有回路，每條邊都是割邊。10.關(guān)于含有n片樹(shù)葉的最優(yōu)二叉樹(shù)描述,不正確的是( ).A. 含有n片樹(shù)葉的最優(yōu)二叉樹(shù)每個(gè)分支點(diǎn)都有兩個(gè)孩子；B. 含有n片樹(shù)葉的最優(yōu)二叉樹(shù)分支點(diǎn)的個(gè)數(shù)是n-1；C.W(T)等于個(gè)分支點(diǎn)的權(quán)重（構(gòu)造最優(yōu)二叉樹(shù)時(shí)產(chǎn)生）之和；D. 在權(quán)重一定的前提下，含有n片樹(shù)葉的最優(yōu)二叉樹(shù)是惟一的。二、計(jì)算題（每小題10分，共40分）1.(1)求的主析取

14、范式；(2)根據(jù)主析取范式直接寫(xiě)出主合取范式； (3)根據(jù)主析取范式直接寫(xiě)出真值表。2.設(shè)集合A=a，b，c，d，A上的關(guān)系R=<a,a>,<a,b>,<b,a>,<c,d>,<d,c> 求：（1）畫(huà)出R的關(guān)系圖； （2）求出R的傳遞閉包tr(R) ； (3) tr(R)中再添加一些元素后得D(R)，若使D(R)是等價(jià)關(guān)系，則tr(R)中再添哪些元素后得D(R)?3.(1)下圖的最下生成樹(shù)；(2)求該圖的點(diǎn)連通度和邊連通度；(3)求A到B的最短路徑的長(zhǎng)度。 A B4.(10分)對(duì)于下有向圖,(1) 寫(xiě)出度序列和出度序列；(2) 寫(xiě)出鄰接矩陣A，第一行元素之和的含義是什么？(3) 求,據(jù)此說(shuō)明從A到A的長(zhǎng)度為4的回路用多少？三、證明題1 設(shè)A是正整數(shù)集合，在上定義二元關(guān)系R如下：當(dāng)且僅當(dāng),證明：R為等價(jià)關(guān)系。2. 設(shè)R為實(shí)數(shù)集，+為普通加法，·為普通乘法，<R，*>是一個(gè)代數(shù)系統(tǒng)，*是