離散數(shù)學(xué)模擬題答(李占魁)重點程度5顆星

3/3一、單項選擇題（每題２分,共２0分）１、令p:天下雨；q:上班。將命題'’若天下雨,則不上班’’符號化為[D]Ａ。p→q;Ｂ．ｑ→ｐ；Ｃ．p∧ｑ；Ｄ．q→﹁p2、任何命題公式都至少有ｒ個主范式。[B］A．r=1;B。ｒ=2；Ｃ.r=3;D.r=4。３、命題公式Ａ＝p∧﹁ｐ→q的主析取范式為[C］A.A=∑(0，1,2）。B.A=∑（0，2，3）。C．A=∑（０,1，2,3）.D.A＝∑（1，2,3）。4、命題公式A=﹁q的主析取范式為A〈=〉［D］１;B．０;C.∑(1）。;D。∑(0）.5、給出公式Q∧﹃Q的主合取范式。[Ｂ］A．1；B．Π（０，1).;C.Π(0）.;D．Π（1）..6、下列公式中哪個是關(guān)于p，q的主合取范式[A］Ａ．p∨q；Ｂ．﹃p∧q；C．ｐ∧﹃q；D。﹃p∨ｐ。７、公式彐xF(ｘ）→彐yＧ(y）的類型是［C］A.永真式;B．永假式；C．可滿足式；D。不是一階邏輯公式.8、因為公式中有命題變項，所以命題公式［C］Ａ．一定不是命題；B。一定是命題；C．不一定是命題；D.以上都不是.9、域為整數(shù)，公式xy（x–ｙ〈ｘ＋y)是［Ｂ]Ａ。真命題；B。假命題;C．不是命題；Ｄ.ABＣ都不是。1０、公式﹃(F（ｘ）→（yＧ（ｘ，y）→Ｆ（x））的類型是［B］A．永真式；Ｂ．永假式;C．非永真可滿足式；D.不是謂詞公式。二、判斷下列各題的是非(題中，ｍ，ｎ分別為邊，頂點數(shù).每題２分，共1４分)。1、任何無向圖都有一棵生成樹。[非］2、無向圖G（n，m）中,若邊m大于等于頂點ｎ，則圖中必有圈［］３、無向連通圖G(m,n)的每一條邊都可以成為他的某一生成樹的樹枝。［非]4、不含平行邊的無向圖必定為簡單圖[非］５、無向連通圖G（m，ｎ）的某一生成樹T中必有關(guān)系ｍ＝n—１.[非］6、1９個頂點的2—元正則樹有（１9）片樹葉。［非］7、１0階無向連通圖G的邊數(shù)為m，則其生成樹的樹枝數(shù)為9[］三、在一階邏輯中將下面命題符號化（10分）１、所有兔子比某些烏龜跑得快。x（Ｆ（x)→彐ｙ(Ｇ（y)∧H（x，y）））。令F(x)：x是兔子；G（ｙ）:y是烏龜；Ｈ（x，ｙ）：ｘ比ｙ跑得快。2、并非所有兔子比某些烏龜跑得快。﹃x（F（ｘ）→彐y（G(ｙ）∧H（ｘ,ｙ)））。彐x﹃(F(x）→彐ｙ（Ｇ（ｙ）∧H（ｘ，ｙ）)）。彐x（Ｆ（x）∧y﹃(G(y）∧H（x,y))）。彐x(F（x）∧y（﹃G（y）∨﹃H（x,ｙ）)）。彐x（Ｆ（ｘ）∧y（Ｇ（ｙ）→﹃H(x，y）））。令F（ｘ):ｘ是兔子;Ｇ(ｙ）:y是烏龜;Ｈ（x，ｙ）：ｘ比y跑得快.3、張三愛他的兒子.ａ：張三；Ｆ（x,y）:x愛y；f（x）=x的兒子；F(af（a)).四、填空題(每題２分，共１６分)1、二元完全正則樹Ｔ有k層高,則該樹最多有（２ｋ+１－1)頂點。２、三元正則樹的葉子總數(shù)ｔ必須是大于等于3的奇數(shù).3、無向圖G有生成樹的充分必要條件是連通。4、１2階無向簡單圖G中有４個奇數(shù)度頂點，其補圖中必有（8）個奇數(shù)度頂點.5、無向圖Ｇ每個頂點的度數(shù)都是3，則圖G必有偶數(shù)個頂點。6、任何連通圖G中,邊數(shù)m不一定大于頂點數(shù)ｎ．7、一棵樹中有i個頂點的度數(shù)為i(i=2，…k）,其余頂點都是樹葉。問樹葉多少片？樹葉數(shù)x=Σｉ（i-2）i+2，(i=2，３,……ｋ)。當(dāng)k=4時，問樹葉多少片?x=(0+3+8）+2[1３］ｉ個頂點的度數(shù)為i（ｉ=２，…k），意思是，這棵樹有2個度數(shù)為２的頂點,3個度數(shù)為３的頂點，。.．。..，有i個度數(shù)為i的頂點.用握手定理列方程，ｘ就出來了８、一個有5個連通分支的森林G,至少加（４）個新邊就使其成為無向樹。．五、最佳前綴碼(２0分)1。給出傳輸GＯODBＹＥ的二元最佳前綴碼。每個字母出現(xiàn)頻率分為:Ｇ、D、Ｂ、E、Y：14%,O：2８%；。1０0（近似)42。。5628。。2８。。28。。14。.１41４1414所以,得到編碼如下：G(０00），D(00１）,Ｂ（1００），E(101)，Y（01），O（11)。2．給出傳輸ＧOＯDBYＥ的二元最佳前綴碼。（不歸一化）．3.給出傳輸GOODBYＥ的三元最佳前綴碼。(講解正則化條件）7.。。３２.0.。...BYEGＤ六、證明題（