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

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

3、叉樹先序遍歷得ABDECF，中序遍歷得DBEACF,則后序遍歷的結果是_。 10. r=5,當s= 時，完全二部圖才可能存在完美匹配。 。 三、計算題（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設G=，G上的運算是矩陣乘法。已知G構成群。（1）指出個元素的階；（2）找出G的全部子群；（3）在同構的意義下G是4階循環

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

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

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

7、0; D. 傳遞的5 設R為實數集，定義R上4個二元運算，不滿足結合律的是（ ）。A. f1(x,y)= x+y B. f2(x,y)=x-y C. f3(x,y)=xy  D. f4(x,y)=maxx,y 6、設<L,>是一個格，則它不滿足(   )A.交換律     B. 結合律   C. 吸收律      D. 消去律7、設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、下圖所示的二叉樹中序遍歷的結果是（    

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

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

11、6的上確界和下確界。、畫一棵帶權為1，1，1，3，3，5，8的最優二叉樹T，并計算它的權W（T）。得分閱卷人四、證明題（共 20分）1、（7分）前提： 結論: 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上的等價關系 (2)給出R確定的對A的劃分(分類).3、（6分）設是群, ,證明S是G的子群. （六）一、選擇題（每小題2分，共20分）1一個命題公式或一階邏輯公式的（ ）是不惟一的。A主析取范式 B主合取范式 C前束范式 D對偶式

12、2下列四個公式正確的是 A. B. C. D.3設集合A=a，b，c，d，e，偏序關系R的哈斯圖下圖所示，則元素的關系不正確的是（ ）。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的映射，其中f(a)=2,f(b)=4,f(c)=1,f(d)=3,f(e)=4,則f是（） A.雙射 B. 滿射 C. 單射 D. 不是單射也不是滿射6設A,B,C是三個非空集合,則( )是正確的. A. B. C. D. 7在下圖所示的哈斯圖中的偏序集不是格的是（ ）8下圖中,（ ）是歐拉圖。A

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

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