1、復習題一、填空題(請將每空的正確答案寫在答題紙相應位置處，答在試卷上不得分。每小題2分，共18分。)1. 設p, q為真命題，r, s為假命題，則復合命題(p r" (-q-； s)的真值為2令F x : x是人，G x : x喜歡吃米飯。在一階邏輯中，命題“不是所有的人都喜歡 吃米飯.”的符號化形式為。3. 已知命題公式A中含三個命題變項p,q, r，則極大項M4的公式是。4. 在1到500之間的整數(包含1與500)中，既不被5整除、也不被6整除的數有 個。5. 設 A=a,b,c , R =： a,c , ：a,b ,則 R 的傳遞閉包 t(R)=。6. 設G=：V,E 是一個

2、連通的平面圖，G共有v個結點，e條邊和r個面，則結點、邊 和面的關系為(歐拉定理)。7 .在整數加群:Z, - 中，3° =。8. 設Z為整數集，-a,bZ, aQb =a b -1, -a，Z, a的逆元a二。9. 300與168的最大公約數是 。每小題 2分，共20分。)()?！镜?頁 共3頁】C . (P Q) > P D . (P Q) > Q二、單項選擇題(從下列各題四個備選答案中選出一個正確答案，并將其代號寫在答題 紙相應位置處。答案錯選或未選者，該題不得分1.下列命題公式中，是永真公式的是A. Q > (P Q) B . P > (P Q)2.關

3、于謂詞公式-x-y(F(x,y) G(y,z)xH(x,y)，下面的描述中錯誤的是()A .-x 的轄域是-y(F(x, y) G(y, z)C. x是該謂詞公式的約束變元3 . 5階無向完全圖的邊數為()A. 5 B . 10 C .4 .有向圖G如右圖所示，在G中， 從V1到V3長度為3的通路有() 條。.1 C .是強連通圖。.x的轄域是H (x, y).z是該謂詞公式的約束變元A. 05.下列圖中,A.V2V3B .6 .在一棵樹中有7片樹葉, 度結點。A. 13個3度結點,C個4O157. 對于集合A二0,1, 2，9,10,不封閉的二元運算是()A . x y = max x, y

4、B. x y = min x, y8. 下列各圖中（）是歐拉圖設 G = ： e, a, a，,aB.是 12階循環(huán)群,則G的生成元有（）個A. 2B.3C. 4D.510. 3的模5逆等于（)。A. 1B.2C. 3D.4三、計算題（每小題各8 分,共40分。）9.111 .求命題公式-（p； q） （q （- p； r）的主析取范式2 .設集合 A =a,b,c,d,e上二元關系定義為 R = ： a, a，: a,b ，: a,c ，: a,d .,：a,e,:b,b : b,c : b,e ，: c, c ，: c, e , ： d,d ，: d ,e , ： e, e ，驗證:A,

5、R -是偏序集，并畫 出哈斯圖。3. 求下列帶權圖的最小生成樹，畫出最小生成樹，并求其權值。4. 求樹葉的權分別為2，3，9，18，23和29的最優(yōu)2叉樹T,并求樹權 W（T）5. 求解遞推方程：an 4an 4 4an = 0, a0 =0,=1。四、證明題（12分。）設A二1,2,3,4，在A A上定義二元關系R，一 ：u, v , ： x, y A A，: u, v R ： x, y 二 u y 二 x v，（1）證明R是A A上的等價關系；（2）求商集A A/R。五、應用題（10分）符號化下列命題，并在自然推理系統(tǒng) P中用邏輯推理確定誰是作案者。 營業(yè)員A或B盜竊了金項鏈。 若A作案，

6、則作案時間不在營業(yè)時間。 若B提供 的證據正確，則貨柜未上鎖。若B提供的證據不正確，則作案時間發(fā)生在營業(yè)時間。貨 柜上了鎖。參考答案一、填空題1. 0 (或 F)2 .一 -x(F(x)； Q(x)(或 x(F(x) Q(x) 3 .一 p q r4. 333 5 . : a,c , ： a, b 6 . v_e r=2 7 . -6 8 . 2-a 9 . 12二、單項選擇題1. C 2 . D 3 . B 4 . D 5 . A 6 . A 7 . D 8 . B 9 . C 10 . B三、計算題(每小題各8分，共40分。)1. 解：主析取范式為：_(p > q) (q (一 pr

7、)：=(一 Pq)(q (p r)：=(p- q)(pq)(qr)=(p- q(r- r)(pq(r- r)(q r(p_ p)二(p-qr)(p - q- r)(p qr) (pq - r)( p q r)=m3mumsme my2. 解：R所對應的關系矩陣為11111、111111、10110101101M(R)=001012M (R )=00101=M (R)0001100011,00001i00001由關系矩陣可知，對角線上所有元素全為 1,故R自反；rj - rj-< 1，故R反對稱; 由此可計算出R2對應的矩陣。由以上矩陣可知R傳遞。所以，R是偏序關系。對應的哈斯圖如下圖所示

8、。3 .解：所求該圖的最小生成樹如下圖所示3該最小生成樹的權值之和W( t) =2+1+1+2+3+4=134 解：所求的最優(yōu)2叉樹如下圖所示該最優(yōu)2叉樹的權為W(t)=2 X 4+3X 4+9X 3+18X 2+23X 2+29X 2=1875解：其特征方程為：x2 4x 0，其特征根是：x1 x2 - -2通解為：an=(G * Qn)L(2)n代入初值得到：c, =0, -2c1 -2C2 =11解得：C| = 0, c2 =-一2所以，原遞推方程的解為：an - -一 nL(-2)n O2四、證明題(12分。)證明：(1) 由于 ：:u,v R：x, y ：= u y=xv：= u-v

9、=x-y 自反性： P VX, y>，有 C x, y>AxA二 x y=x y二 ex yR<x y 羽 即R是A上的自反關系； 對稱性：一 ：x, y ： u,v ,有:：x, y R ： u, v 二 xy 二 u v：= u v 二 xyu ： u, v R x, y ，即 R是 A上的對稱關系； 傳遞性：一 ：x, y：u,v：s,t ,有:：x, y R ： u, v : u, v R ： s,t x - y = u - v u - v = s -t二 x _ y = s _t =： x, y R ： s, t故R是A上的傳遞關系。由、(2)、(3)可知R是A上的

10、等價關系。(2) A A上的等價類為：<1,4 <1,4 ：1,3 *：1,32,4 :：1,2 二1,2 , ：2,3 , ：3,4 :：1,1 十 1,1 2,2 3,34,4 ：2,1 <2,1, : 3,2 , ：4,3 ：3,1 =：3,1：4,2 ：4,1 二：4,1 所以，A A/R= ：1,4 ., <1,3：2,4 , :：: 1, 2 , ：2,3 , ： 3,4 , :：: 1,1 .,:2, 2 , : 3, 3 , ：4, 4 , : 2,1, ： 3, 2 , ： 4, 3 , : 3,1 , ： 4, 2 , : 4,1 五、應用題（10分）解：設簡單命題p： A作案盜竊金項鏈。q： B作案盜竊金項鏈。r:作案發(fā)生在營業(yè)時間s: B提供的證據正確。t：貨柜上了鎖前提：p q, p r