離散數(shù)學(xué)試題(十五套)

1、087ynu 離散數(shù)學(xué)試題與答案試卷一一、填空20% ( 每小題 2 分）1設(shè)A x | ( xN)且( x5), B x | xE 且 x7 （ N：自然數(shù)集，E+ 正 偶2A ，B,C 表示三個(gè)集合，文圖中陰影部分的集合表達(dá)式為。ABC3設(shè) P，Q 的真值為0,R， S 的真值為1，則(P(Q(RP )( RS) 的真值 =.4公式 ( PR)(SR)P 的主合取范式為。5若解釋I 的論域 D 僅包含一個(gè)元素，則xP( x)xP( x)在 I 下真值為。6設(shè) A= 1， 2， 3， 4 ，A 上關(guān)系圖為則R2 =7設(shè) A=a ， b，c， d ，其上偏序關(guān)系R 的哈斯圖為則R=。8圖的補(bǔ)圖

2、為。數(shù)）則AB。.9 設(shè) A=a ， b，c,d，A 上二元運(yùn)算如下:*abcdaabcdbbcdaccdabddabc那么代數(shù)系統(tǒng) 的幺元是逆元分別為,有逆元的元素為。10下圖所示的偏序集中,是格的為。，它們的二、選擇20 （每小題2 分)1、下列是真命題的有(）A a a;B , ;C,；D 。2、下列集合中相等的有（)A 4， 3；B ,3， 4；C 4 ， 3，3 ； D3 ， 4 。 3、設(shè) A= 1， 2，3 ,則 A 上的二元關(guān)系有(）個(gè)。A 23 ；B 32;C3 32 223;D。4、設(shè) R，S 是集合 A 上的關(guān)系 ,則下列說法正確的是（）A 若 R,S 是自反的，則 RS

3、是自反的；B 若 R,S 是反自反的，則 RS 是反自反的；C若 R,S 是對(duì)稱的，則 RS是對(duì)稱的；D 若 R,S 是 傳 遞 的 , 則 RS是傳遞的。5、設(shè) A= 1， 2，3， 4，P（ A) （ A 的冪集 )上規(guī)定二元系如下Rs,t| s, tp( A)(| s | t | 則 P（A ） / R=(）A A ;B P(A)；C 1 ， 1， 2 ， 1，2， 3 , 1,2，3， 4 ; D , 2 ， 2 ， 3 ， 2，3,4 ， A 07、下列函數(shù)是雙射的為(）A f : IE ,f (x ） = 2x；B f : NNN,f (n) = ;C f ：RI ,f (x ）

4、= x ；D f :IN，f (x)=x | 。（注： I整數(shù)集 ,E偶數(shù)集 , N自然數(shù)集 ,R實(shí)數(shù)集）8、圖中 從 v1 到 v 3 長(zhǎng)度為 3 的通路有（）條。A 0；B 3.1；C2;D9、下圖中既不是Eular 圖,也不是Hamilton 圖的圖是（)6、設(shè) A=, 1 ， 1，3 ， 1,2 ， 3 則 A 上包含關(guān)系“”的哈斯圖為（)10、在一棵樹中有7 片樹葉， 3 個(gè) 3 度結(jié)點(diǎn) ,其余都是4 度結(jié)點(diǎn)則該樹有（） 個(gè) 4 度結(jié)點(diǎn)。A 1； B 2；C 3；D 4 。三、證明26%、 R 是集合 X 上的一個(gè)自反關(guān)系,求證： R 是對(duì)稱和傳遞的，當(dāng)且僅當(dāng) a, b 和 a ,

5、c在 R 中有。 b ， c在 R 中.（ 8 分）、 f 和 g 都是群 G1 ，到G2， * 的同態(tài)映射,證明是的一個(gè)子群 .其中 C= x | xG1且f ( x)g(x)(8 分)、 G=（ V= v，|E =e ） 是每一個(gè)面至少由k（k3)條邊圍成的連e通平面圖，則分）k(v k2)2， 由此證明彼得森圖（Peterson)圖是非平面圖.（ 11四、邏輯推演16%用 CP 規(guī)則證明下題(每小題8 分）1、 A2、Bx(P(x)CD, D Q( x)EFxP (x)AFxQ (x)五、計(jì)算18%1、設(shè)集合A=a ，b,c，d 上的關(guān)系R=a , b ， , b, c ， c ， d

6、用矩陣運(yùn)算求出R 的傳遞閉包t (R） .（ 9 分）2、如下圖所示的賦權(quán)圖表示某七個(gè)城市v1, v2 , v7 及預(yù)先算出它們之間的一些直接通信線路造價(jià)， 試給出一個(gè)設(shè)計(jì)方案，使得各城市之間能夠通信而且總造價(jià)最小。（分 )試卷一答案：一、填空20%（每小題2 分)1、 0,1,2，3,4， 6 ； 2、 ( BC)A； 3、 1；4、 (PSR)(PSR) ；5、1;6、1，1, 1,.3， ， 2， 4 ； 7、 a.b，a,c， c， dIA； 8、9 、 a ； a ， b , c ,d ； a , d ，c ， d ； 10、c；二、選擇20%（每小題2 分)題目1234567891

7、0答案CDB、CCADCADBA三、證明26% 1、 證：“”a, b, cX若, R由R對(duì)稱性知, c, aR ,由 R 傳遞性得R“”若R , R 有R任 意a,bX ， 因R 若 RR所以 R 是對(duì)稱的。若 R ， R則Rb, cRR即 R 是傳遞的。2 、 證a, bC，有f (a)g(a),f (b)g (b)，又1f (b 1)f 1(b) ,g(b 1 )g 1(b)f (b 1)f1(b)g 1 (b)g(b 1 )1f (a b)f (a) * f1 (b)g(a)*g(b 1 )g(a b)a b 1C3、 證： C , 是 G1 , 的子群。r2ed (Fi )rkr2e

8、 設(shè)G 有r個(gè) 面 , 則i 1, 即k。 而ver2 故2verve2ek 即 得ek (v k2)2。(8 分)ek(v2)彼得森圖為k5, e15, v10 ，這樣k2不成立 ,所以彼得森圖非平面圖。（ 3 分）二、 邏輯推演16%1、 證明： AP（附加前提） ABT I ABCDP CDT I DT I DE DEFT I P FT I AFCP2、證明xP( x)P（附加前提） P(c)USx(P( x)Q(x)P P(c) Q( c)Q(c)UST IxQ (x)xP (x)xQ( x)UG CP三 、 計(jì)算18%1、 解:0100101010100101M R00010000M

9、 R2，M RM R00000000M R3M R4M R2M R010110100000000010100101000000001111，M R3M RM t ( R)M RM R2M R3M R4111100010000t （ R）=a ，a , a ，b ， a , c ， ， b , a ， b ,b ， b , c 。 , ， c , d 2 、 解：用庫斯克 (Kruskal ）算法求產(chǎn)生的最優(yōu)樹。算法略.結(jié)果如圖：樹 權(quán) C（ T)=23+1+4+9+3+17=57即為總造價(jià) .試卷二試題與答案一、填空20%（每小題 2 分)1、 P：你努力， Q：你失敗?！俺悄闩Γ駝t你將

10、失敗”的翻y 譯為;“雖然你努力了,但還是失敗了”的翻譯為。2、論域 D= 1， 2，指定謂詞PP (1,1)P （ 1，2）P (2,1）P （ 2,2)則公式TTFFx yP( y, x) 真 值為。2、 設(shè) S=a 1 ， a2 ， ,a8 ，B i 是 S 的子集，則由B 31 所表達(dá)的子集是3 、 設(shè)A=2 ， 3,4 ， 5 ， 6 上 的 二 元 關(guān) 系 Rx, y| xyx是質(zhì)數(shù) , 則（列舉法）。R 的關(guān)系矩陣M R=。5、設(shè) A=1 ，2,3, 則 A 上既不是對(duì)稱的又不是反對(duì)稱的關(guān)系R=A 上既是對(duì)稱的又是反對(duì)稱的關(guān)系R=。6、設(shè)代數(shù)系統(tǒng), 其中 A=a ， b， c ,

11、9、n 個(gè)結(jié)點(diǎn)的無向完全圖K n 的邊數(shù)為，歐拉圖的充要條件是。10、公式 ( P(PQ )(PQ)R 的根樹表示為。R=；abcaabcbbbc則 幺元 是; 是 否 有 冪 等cccb性；是否有對(duì)稱性。7、4 階群必是8、下面偏序格是分配格的是群或。群。二、選擇20%（每小題 2 分）1、在下述公式中是重言式為()A ( PQ)( PQ) ;B (PQ)(PQ)(QP) ；C(PQ)Q ；D P( PQ) 。2、命題公式(PQ)(QP)中極小項(xiàng)的個(gè)數(shù)為（)，成真賦值的個(gè)數(shù)為（)。SA 0；B 1；C2；D 3 。3、設(shè) S,1, 1,2 ， 則2有（)個(gè)元素。A 3;B 6;C 7；D 8

12、 .4 、 設(shè) S 1,2, 3 ，定義 SS上的等價(jià)關(guān)系Ra,b,c, d|a,bSS,c, dSS, adbc則由R 產(chǎn)生的 SS上一個(gè)劃分共有(）個(gè)分塊。A 4；B 5；C 6；D 9 。5、設(shè) S 1,2, 3 ， S 上關(guān)系 R 的關(guān)系圖為則 R 具 有（）性質(zhì)。A 自反性、對(duì)稱性、傳遞性;B 反自反性、反對(duì)稱性； C反自反性、反對(duì)稱性、傳遞性；D自反性.6、設(shè),為普通加法和乘法，則（）S,是域。A S x | xab3 ,a,bQS x | x2n ,a,bZS x | x2 n1,nZS x | xZx0= N。7、下面偏序集（)能構(gòu)成格。8、在如下的有向圖中，從V 1 到 V

13、4 長(zhǎng)度為 3 的道路有 (）條。A 1;B 2;C 3；D 4 。9、在如下各圖中(）歐拉圖。設(shè) R 是實(shí)數(shù)集合 ,“”為普通乘法，則代數(shù)系統(tǒng)R , 是(） .A 群 ;B獨(dú)異點(diǎn)；C半群.三、證明461、 設(shè) R 是 A 上一個(gè)二元關(guān)系，10、Sa, b| (a, bA)(對(duì)于某一個(gè) cA, 有a, cR且c, bR) 試 證明若 R 是 A 上一個(gè)等價(jià)關(guān)系，則S 也是 A 上的一個(gè)等價(jià)關(guān)系。 （ 9 分）2、 用邏輯推理證明：所有的舞蹈者都很有風(fēng)度，王華是個(gè)學(xué)生且是個(gè)舞蹈者。因此有些學(xué)生很有風(fēng)度。（ 11 分)3 、 若f : AB 是從A到B的函數(shù) , 定義一個(gè)函數(shù)g : B2 A 對(duì)任

14、意bB 有g(shù)(b) x | ( x(f ( x)b)，證明 :若 f 是 A 到 B 的滿射 ,則 g 是從 B 到2 A的單射。（ 10 分）4、 若無向圖G 中只有兩個(gè)奇數(shù)度結(jié)點(diǎn),則這兩個(gè)結(jié)點(diǎn)一定連通。（ 8 分）5 、 設(shè) G 是 具有n 個(gè)結(jié)點(diǎn)的無向簡(jiǎn)單圖，其邊數(shù)Hamilton 圖（ 8 分）四、計(jì)算14m1 ( n 21)( n2)2,則G 是1、 設(shè)Z6，+6是一個(gè)群 ,這里 +6 是模 6 加法， Z6= 0 ， 1 ，2， 3,4 ， 5,試求出 Z6 ,+6的所有子群及其相應(yīng)左陪集。（ 7 分）2、 權(quán)數(shù) 1,4， 9， 16,25,36， 49， 64， 81， 100

15、構(gòu)造一棵最優(yōu)二叉樹.(7 分)試卷二答案：一 、 填空20% （每小題2 分）1、PQ ； PQ 2 、T3 、B31B00011111 a4 , a5 , a6 , a7 , a84、 R= 2,2 ，2,3,2,6, ，3， 3 ,3， 4， 3,5 ， 3， 6,4,5， 4,6 ，,5， 4, ，5,6 ；2， 1 ； R=1， 1,2,2,3,35、R= 1,2,1,3 ，11111111110001111111000006、 a；否；有7、Klein四元群；循環(huán)群8、B9、1 n(n21)；圖中無奇度結(jié)點(diǎn)且連通10 、二、選擇20（每小題2 分)題目12345678910答案B 、

16、DD ； DDBDABBBB 、C三、證明46%1、(9 分）（ 1）S 自反的aA ，由 R 自反，(a, aR)(a, aR) ,a, aS（ 2）S 對(duì)稱的a, bAa, bS(a, cR)(c,bR)S 定義(a, cR)(c, bR)R 對(duì)稱b, aSR 傳遞（ 3）S 傳遞的a, b, cAa, bSb, cS(a, dR)(d , bR)(b, eR)(e, cR)(a, bR)(b, cR)R 傳遞a, cSS定義由（ 1)、（ 2）、(3)得； S 是等價(jià)關(guān)系 .2、11 分證明：設(shè)P(x）： x 是個(gè)舞蹈者；Q（ x) ： x 很有風(fēng)度；S（x ）： x 是個(gè)學(xué)生；a：王華

17、上述句子符號(hào)化為：前提 :x(P( x)Q(x)、 S( a)P(a)結(jié)論：x(S( x)Q(x) 3 分 S( a)P(a)Px(P( x)Q(x)P P( a) P( a) Q(a). S( a) S( a)Q(a)Q(a)US T IT I T IT Ix(S(x)Q(x)EG 11 分、 0 分證明:b1, b2B , (b1b2 )f 滿 射a1 ,a2A使f (a1 )b1, f(a2 )b2 , 且f (a1)f (a2 ), 由于f是函數(shù) ,a1a2又 g(b1) x | (x(f ( x)b1),g(b2 ) x| ( x(f (x)b2 )a1g(b1), a2g(b2 )

18、但 a1g(b2 ), a2g(b1 )g(b1 )g(b2 )由b1, b2任意性知,4、8 分g為單射 。證明: 設(shè) G 中兩奇數(shù)度結(jié)點(diǎn)分別為u 和 v，若u， v 不連通，則G 至少有兩個(gè)連通分支 G1、 G2 ,使得 u 和 v 分別屬于G1 和 G2，于是 G1 和 G2 中各含有1 個(gè)奇數(shù)度結(jié)點(diǎn) ,這與圖論基本定理矛盾，因而u,v 一定連通。5、8 分證明：證 G 中任何兩結(jié)點(diǎn)之和不小于n.反證法： 若存在兩結(jié)點(diǎn)u,v不相鄰且d (u)d (v)n1 ,令 V1 u, v ,則 G-V 1 是mn 2個(gè) 結(jié) 點(diǎn) 的 簡(jiǎn) 單 圖 ， 它 的 邊 數(shù)121 (n2)(n3)1(n1)(

19、 n2)具 有m2(n1), 可 得2,這與 G1=G-V 1 為 n-2 個(gè)結(jié)點(diǎn)為簡(jiǎn)單圖的題設(shè)矛盾，因而G 中任何兩個(gè)相鄰的結(jié)點(diǎn)度數(shù)和不少于n。所 以 G 為 Hamilton 圖 。四、計(jì)算14%d 1 、 7 分解：子群有 ； ； Z 6,+ 6 0 的左陪集：0, 1 ； 2 ， 3 ； 4 ， 5 0 ， 3 的左陪集： 0 ， 3; 1， 4 ； 2， 5 0 ，2 ， 4 的左陪集： 0 ， 2， 4 ；1 ， 3 ， 5 Z6 的左陪集： Z 6 。2 、 7 分試卷三試題與答案一、填空 20% （每空 2 分）1、 設(shè) f， g 是自然數(shù)集N 上的函數(shù)xN ,f (x)x1

20、,g(x)2 x ，則 fg ( x)。2、 設(shè) A= a,b，c ， A 上二元關(guān)系R= , a ， b , a， c , ， 則 s（ R）=.3、 A=1,2 ，3， 4,5，6 ， A 上二元關(guān)系Tx, y| xy 是素?cái)?shù)，則用列舉法T=；T 的關(guān)系圖為；T 具有性質(zhì) .4、 集合A, 2, 2 的冪集2 A =。5、 P,Q真值為0 ；R,S 真值為 1。則 wff ( P(RS)( P(RS) 的真值為。6 、 wff( PQ)R)R的主合取范式為。7、設(shè)P(x）：x 是素?cái)?shù)，E（ x）：x 是偶數(shù)， O(x) ：x 是奇數(shù)N （ x,y) ：x 可以整數(shù)y。則謂詞wffx(P(

21、x)y(O( y)N ( y, x)的自然語言是。8、 謂詞wffxy(z( P( x, z)P( y, z)uQ (x,y, u)的前束范式為。二、選擇 20 （每小題2 分)1、 下述命題公式中，是重言式的為（)。A 、 ( pq)( pq) ；B、 ( pq)( pq )(qp ) ;C、( pq)q ；D、 ( pp)q 。2 、 wff( pq)r 的主析取范式中含極小項(xiàng)的個(gè)數(shù)為（）。A 、2；B 、 3；C、5；D、0；E 、 8 。3、 給定推理x(F ( x)G(x)P F ( y)G( y)USxF( x)P F ( y) G( y)EST IxG (x) x( F ( x)

22、G( x)xG( x)UG 推理過程中錯(cuò)在（）。A 、 - ；B 、 - ;C、 - ;D、 ;E、 - 4、 設(shè) S1= 1，2， 8，9，S2=2， 4， 6，8,S3=1 ，3,5,7， 9 ， S4 = 3，4，5 ，S5 =3， 5，在條件XS1 且 XS3 下 X 與（）集合相等。A 、 X=S 2 或 S5 ；B 、X=S 4 或 S5；C、X=S 1， S2 或 S4；D、X 與 S1， S5 中任何集合都不等.5、 設(shè)R和S是P上的關(guān)系，P是所有人的集合,Rx, y| x, yPx是y的父親，Sx, y| x, yPx是y的母親 則 S 1R表示關(guān)系(）.A 、B 、x, y

23、x, y| x, y| x, yPx是y的丈夫 ;Px是y的孫子或?qū)O女 ；C、；D 、x, y| x, yPx是y的祖父或祖母 .;6、 下面函數(shù)（)是單射而非滿射。A 、 f : RR,f ( x)x22 x1B 、 f : ZR,f ( x)ln x ;C 、 f : RZ,f (x) x, x表示不大于 x的最大整數(shù) ；D 、 f : RR,f( x)2x1。其中 R 為實(shí)數(shù)集， Z 為整數(shù)集， R+， Z+分別表示正實(shí)數(shù)與正整數(shù)集. 7、 設(shè) S= 1， 2， 3 ,R 為 S 上的關(guān)系，其關(guān)系圖為則 R 具 有（)的性質(zhì)。A 、 自反、對(duì)稱、傳遞;B、什么性質(zhì)也沒有；C、反自反、反對(duì)

24、稱、傳遞；D 、自反、對(duì)稱、反對(duì)稱、傳遞。8 、 設(shè) S,1 , 1,2，則有（）S 。A 、 1,2； B、 1， 2 ；C、1；D 、 2。9 、 設(shè) A= 1 ,2 ， 3 ， 則 A 上 有（）個(gè)二元關(guān)系。A 、23; B、 32; C、223；D 、322。10、全體小項(xiàng)合取式為（）。A 、可滿足式；B、矛盾式 ; C、永真式 ; D 、A ， B， C 都有可能。三、用 CP 規(guī)則證明16 （每小題8 分）1、 ABCD , DEFAF2、x(P( x)Q(x)xP(x)xQ( x)四、（ 14）集 合 X= ，3,4, 5 ， 6, ,R= ,x 2,y2 x1+y2 = x 2

25、+y 1。1、 證明 R 是 X 上的等價(jià)關(guān)系。(10 分）2、 求出 X 關(guān)于 R 的商集。 (4 分）五、（ 10%）設(shè)集合 A= a，b ， c ， d 上 關(guān)系R= , ， c ,d 要求1、寫出 R 的關(guān)系矩陣和關(guān)系圖.（ 4 分）2、用矩陣運(yùn)算求出R 的傳遞閉包 .（ 6 分）六、(20 ）1、（ 10 分）設(shè) f 和 g 是函數(shù) ,證明 fg 也是函數(shù)。2、（ 10 分）設(shè)函數(shù)入射函數(shù)。答案：g : STf : TS ，證明f : TS 有一左逆函數(shù)當(dāng)且僅當(dāng)f 是五 、 填空20%( 每空 2 分）1 、 2(x+1) ； 2 、 a, a,a , b,a ,c,c , c,b

26、,a,c , a ;3 、2,1,4、3,1,5,1,4,2,6,2,6,3;反對(duì)稱性、反自反性；4、,2, 2, ,2, 2；5、 1;6 、 (PQR)(PQ( PQR) ； 7、任意x，如果x 是素?cái)?shù)則存在一個(gè)y ，y 是奇數(shù)且y 整 除 x ；8 、六 、 選擇20 (每小題2 分）xyz u(P( x, z)P( y, z)Q( x, y,u ) .題目12345678910答案CCCCABDADC七、證明16%( 每小題8 分)1、 AP（附加前提） ABT I ABCDP CDT I DT I DE DEFT I P FT I AFCP2、xP( x)xQ (x)(x) P(x)

27、xQ( x)本題可證x( P( x)Q( x)(xP (x)xQ(x)(x(xP( x)P(x)P（附加前提） T EP(a)x(P( x)Q(x)ES P P( a) Q( a)Q( a)US T IxQ( x)EG(xP( x)xQ(x)CP八 、 14%（ 1）證明：1、自反性 :x, yX ,由于xyxyx, y2、對(duì)稱性：,x, yRx1, y1X ,R自反x2 , y2X當(dāng)x1, y1,x2, y2R 時(shí) 即x1y2x2y1 也即x2y1x1y2故x2 , y2,x1, y1RR有對(duì)稱性3、傳遞性：x1, y1X ,x2, y2Xx3 , y3X當(dāng)即x1 x2x1, y1y2 y3

28、,x2 , y2x2y1x3y2R 且(1)( 2)x2 , y2,x3, y3R時(shí)(1)(2)x1y2x2即 x1y3y3x2x3y1y1x3y2故x1, y1,x3, y3RR有傳遞性由(1 ）（ 2)（ 3）知 :R 是 X 上的先等價(jià)關(guān)系。2、 X/R= 九 、 10%1 ,2 R 0100101000010000M R1010010100000000010110100000000010100101000000001、；關(guān)系圖M R22、M RM RM R3M R2M RM R4M R3M RM R 2M R5M R3, M R6M R4 ,M t ( R)M RM R2M R3M R

29、41111111100010000t （ R)= a , a ， a , b ， a , c ， , , b ， c . ， ，c , d 。六、20fgx, y| xdomfxdomgyf ( x)yg ( x)1、（ 1）令hfx, y| xgdomfdomgyf ( x)g(x)domfgdomh x | xdomfdomg,f (x)g( x)(2） hx, y| xdomfdomgyh(x)f ( x)g( x)對(duì)xdomh若有y1, y2使得y1h(x)f ( x)g( x) ,y2h( x)f ( x)g(x)由于f (或g)是函數(shù),有y1y2 即xdomh 有唯一y使得yh(

30、x)fg也是函數(shù) 。2、證明： 若f有一左逆 g,則對(duì)tTgf (t )t故 gf是入射, 所以f 是入射 . f是入射,f : TS定義如下 :sf (T ),由 f入射,| tT,使f (t)s此時(shí)令g(s)t , 若sf (T)令g(s)cT則對(duì)sS, g(s)只有一個(gè)值t 或 c且若f(t )s則gf(t )g(s)t ,故g 是f的左逆元即若f入射, 必能構(gòu)造函數(shù) g,試卷四試題與答案使g為f左逆函數(shù) 。一、填空10 （每小題2 分）1、 若 P， Q，為二命題，PQ 真值為 0 當(dāng)且僅當(dāng).2、 命題“對(duì)于任意給定的正實(shí)數(shù)，都存在比它大的實(shí)數(shù)”令F（ x):x為實(shí)數(shù)，L( x, y)

31、 : xy則命題的邏輯謂詞公式為。3、 謂詞合式公式xP (x)xQ( x)的前束范式為。4、 將量詞轄域中出現(xiàn)的和指導(dǎo)變?cè)粨Q為另一變?cè)?hào)，公式其余的部分不變，這種方法稱為換名規(guī)則。5、 設(shè) x 是謂詞合式公式A 的一個(gè)客體變?cè)?，A 的論域?yàn)镈， A(x ）關(guān)于y 是自由的， 則ES。二、選擇25 (每小題2。 5 分）1、 下列語句是命題的有（)。A 、 明年中秋節(jié)的晚上是晴天；B、 x被稱為存在量詞消去規(guī)則，記為y0 ；C、 xy0 當(dāng)且僅當(dāng)x 和 y 都大于 0；D、我正在說謊.2、 下列各命題中真值為真的命題有（).A 、 2+2=4 當(dāng)且僅當(dāng)3 是奇數(shù)； B、2+2=4 當(dāng)且僅當(dāng)

32、3 不是奇數(shù) ; C、2+2 4 當(dāng)且僅當(dāng)3 是奇數(shù) ; D、 2+2 4 當(dāng)且僅當(dāng)3 不是奇數(shù)；3、 下列符號(hào)串是合式公式的有()A 、 PQ ;B、 PPQ ； C、 (PQ)( PQ) ;D 、(PQ) 。4、 下列等價(jià)式成立的有(）。A 、 PQQP ； B、 P( PR)R ;C、P(PQ)Q ；D、 P(QR)( PQ)R 。5 、 若A1, A2An 和 B 為 wff ， 且 A1A2AnB 則（） .A 、稱 A1A2An 為 B 的前件；B、稱 B 為A1, A2An 的有效結(jié)論C、當(dāng)且僅當(dāng)A1A2AnBF；D、當(dāng)且僅當(dāng)A1A2AnBF 。6、 A,B 為二合式公式，且AB

33、 ，則（)。A 、 AC、 AB 為重言式；B 、B ；D 、A*B*A*B*；E 、 AB 為重言式。7、 “人總是要死的 謂詞公式表示為（）。(論域?yàn)槿倐€(gè)體域）M(x) ：x 是人； Mortal （ x)： x 是要死的。A 、 M ( x)Mortal( x) ；B、M ( x)Mortal( x)C、x(M ( x)Mortal( x) ;D 、x( M ( x)Mortal(x)8、 公式 Ax( P( x)Q( x) 的解釋 I 為：個(gè)體域D= 2 ，P（ x)：x3, Q（ x）：x=4則 A 的真值為（）。A 、1；B、 0；C、可滿足式；D、無法判定。9、 下列等價(jià)關(guān)系正

34、確的是（)。A 、x( P(x)B、x( P( x)C、x( P( x)D、x( P( x)Q( x)Q( x) Q)Q)xP (x)xP( x)xP(x)xP (x)xQ( x) ；xQ (x) ； Q ；Q .10、 下列推理步驟錯(cuò)在(） .x( F (x)G( x)P F ( y)G ( y)USxF ( x)P F ( y) G( y)ES T IxG( x)EGA 、； B 、； C、 ;D、三、邏輯判斷30%1、 用等值演算法和真值表法判斷公式型。 (10 分）A( P(QP)( PQ) 的類2、 下列問題，若成立請(qǐng)證明，若不成立請(qǐng)舉出反例：（ 10 分）已知 ACBC ， 問 A

35、B 成立嗎？已知AB ，問 AB 成立嗎 ?3、 如果廠方拒絕增加工資,那么罷工就不會(huì)停止,除非罷工超過一年并且工廠撤換了廠長(zhǎng).問：若廠方拒絕增加工資,面罷工剛開始,罷工是否能夠停止。 （ 10 分）四、計(jì)算10%1、 設(shè)命題 A 1， A2 的真值為1， A3， A 4 真值為 0，求命題( A1( A2( A3A1)( A2A4 ) 的真值。（ 5 分）2、 利用主析取范式，求公式( PQ)QR的類型。（5 分）五、謂詞邏輯推理15%符號(hào)化語句：“有些人喜歡所有的花，但是人們不喜歡雜草，那么花不是雜草. 并推證其結(jié)論。六、證明 :(10 ）設(shè)論域 D= a ， b , c，求證：答案：xA

36、( x)xB( x)x( A(x)B( x) 。十 、 填空10（每小題2 分）1、P 真值為1,Q 的真值為0； 2 、x(F ( x)L( x,0)y(F ( y)L( y, x)； 3 、x(P( x)Q( x) ； 4、約束變?cè)?;5、xA( x)A( y) ， y 為 D 的某些元素。題目12345678910十一、選擇25% （每小題2。5 分）答案A,CA,DC，DA,DB,CA ， B， C， D,ECAB(4）十二、邏輯判斷30% 1、（ 1)等值演算法A( PQ)(QP )( PQ)( PQ)( PQ)T（ 2） 真值表法PQPQQP( PQ)(QP)PQA11111111

37、00100101100010011111所以 A 為重言式。2、(1）不成立。若取 CT則ATTBTT 有 ACBCT但 A 與 B 不一定等價(jià) ,可為任意不等價(jià)的公式。(2) 成 立 。 證明：AB充要條件ABTT即 ： 所 以 A(A(BA)BTB)( (A故ABA)( AB 。( AB)( B( BA)AB3、解：設(shè)P：廠方拒絕增加工資；Q：罷工停止；R 罷工超壺過一年；R：撤換廠長(zhǎng)前提 : P P(RS) ( RS)Q) ,P,Q)R結(jié)論：QP PP(RS)QT IRPRS(RS)T I T EQT I罷工不會(huì)停止是有效結(jié)論。四、計(jì)算10（ 1）解：(1(10(10)0)11(11)(

38、1(10)111（ 2）( PQ)QR(P( PQ)(QR)P(QR)QQRF它無成真賦值，所以為矛盾式。五、謂詞邏輯推理15%解： M ( x) : x是人;F ( x) : x是花;G(x) : x是雜草;H ( x, y) : x喜歡yx(M(x)y( F ( y)H ( x, y)x(M( x)y(G( y)H ( x, y)x(F ( x)證明：G( x)x(M M (a) M (a)(x)y( F ( y)y( F ( y)HH ( x,(a, y)y)PES T Iy( F ( y)x(M ( x) M (a)y(G( y)H (a, y)y(G( y)y(G( y)H ( a,

39、 y)H ( x, y)H (a, y)T I PUST Iy( H (a, y)G( y)T E F (z) H (a, z) F ( z)x( F ( x)H ( a, z)G( z)G( z)G(x)US US T I UG 十三、證 明 10%xA( x)( A(a)xB(x) B( a)( A(a)( A(a)A(b) B(b )A(c) ( A(a)( B(a)B( c)B(b)B(c)( A(b)( A(c)( A(a)B(a)B(a )B( a)( A(b)( A(c)( A(b)B(b)B(b)B(b )( A(b)( A(c)( A(c)B(c)B(c) B(c)x( A(

40、 x)B(x)試卷五試題與答案一、填空15%( 每空 3 分)1、設(shè) G 為 9 階無向圖， 每個(gè)結(jié)點(diǎn)度數(shù)不是5 就是 6，則 G 中至少有個(gè) 5 度結(jié)點(diǎn)。2、n 階完全圖， Kn 的點(diǎn)數(shù) X (K n）=。3、有向圖中從 v 1 到 v2 長(zhǎng)度為 2 的通路有條。4、設(shè) R， +， 是代數(shù)系統(tǒng)，如果R， + 是交換群 R, 是半群則稱 R， +， 為環(huán)。5、設(shè) L, 是代數(shù)系統(tǒng) ,則 L, 滿足冪等律，即對(duì)aL 有。二、選擇15 （每小題3 分)1、 下面四組數(shù)能構(gòu)成無向簡(jiǎn)單圖的度數(shù)列的有()。A 、（ 2,2，2， 2， 2）；B、（ 1， 1， 2， 2，3）；C、 (1， 1， 2，

41、2， 2）；D、（ 0， 1,3,3， 3）。 2、 下圖中是哈密頓圖的為(）。3、 如果一個(gè)有向圖D 是強(qiáng)連通圖，則D 是歐拉圖，這個(gè)命題的真值為（）A 、真;B 、假。4、 下列偏序集（）能構(gòu)成格。s5 、 設(shè)1,1, 2,21, 3,31, 44,為普通乘法，則S, 是（） .A 、代數(shù)系統(tǒng)；B 、半群；C、群；D 、都不是。三、證明48 1、（ 10%)在至少有2 個(gè)人的人群中，至少有2 個(gè)人，他們有相同的朋友數(shù)。2、（ 8%）若圖 G 中恰有兩個(gè)奇數(shù)度頂點(diǎn)，則這兩個(gè)頂點(diǎn)是連通的。3、（ 8%）證明在6 個(gè)結(jié)點(diǎn)12 條邊的連通平面簡(jiǎn)單圖中, 每個(gè)面的面數(shù)都是3.4、(10）證明循環(huán)群的

42、同態(tài)像必是循環(huán)群。5、(12）設(shè) B,0 ,1 是布爾代數(shù)，定義運(yùn)算* 為 a * b(ab)(ab) ，求證 B,* 是阿貝爾群。四、計(jì)算22 1、在二叉樹中1） 求帶權(quán)為2,3， 5， 7， 8 的最優(yōu)二叉樹T.（ 5 分）2） 求 T 對(duì)應(yīng)的二元前綴碼。 （5 分）2、 下圖所示帶權(quán)圖中最優(yōu)投遞路線并求出投遞路線長(zhǎng)度(郵局在 D 點(diǎn)） .答案：一、填空（ 15%）每空 3 分1、6； 2、n； 3、 2； 4、+對(duì)分配且對(duì)+分配均成立；5、 aaa 且 aaa .二、選擇（ 15% ）每小題 3 分題目12345答案A,BB ，DBCD三、證明（ 48）1、（ 10 分）證明：用n 個(gè)

43、頂點(diǎn)v1， vn 表示n 個(gè)人，構(gòu)成頂點(diǎn)集V=v 1， v n ，設(shè)E uv | u, vV, 且u,v是朋友（uv），無向圖G=（ V ，E）現(xiàn)證 G 中至少有兩個(gè)結(jié)點(diǎn)度數(shù)相同。事實(shí)上 ,(1）若 G 中孤立點(diǎn)個(gè)數(shù)大于等于2，結(jié)論成立 .（2） 若 G 中有一個(gè)孤立點(diǎn)，則G 中的至少有3 個(gè)頂點(diǎn)，既不考慮孤立點(diǎn)。設(shè)G 中每個(gè)結(jié)點(diǎn)度數(shù)均大于等于1,又因?yàn)镚 為簡(jiǎn)單圖，所以每個(gè)頂點(diǎn)度數(shù)都小于等于n-1，由于G 中 n 頂點(diǎn)其度數(shù)取值只能是1， 2,， n-1，由鴿巢原理,必然至少有兩個(gè)結(jié)點(diǎn)度數(shù)是相同的。2、（ 8 分)證: 設(shè) G 中兩個(gè)奇數(shù)度結(jié)點(diǎn)分別為u,v.若 u， v 不連通則至少有兩個(gè)連

44、通分支G1、G2,使得 u， v 分別屬于G1 和 G2。于是 G1 與 G2 中各含有一個(gè)奇數(shù)度結(jié)點(diǎn),與握手定理矛盾。因而 u， v 必連通。3（ 8 分）證： n=6 ，m=12歐拉公式n m+f=2 知 f=2 n+m=2-6 12=8由圖論基本定理知： 每個(gè)面用3 條邊圍成。deg(F )2m24 ，而 deg(Fi )3 ，所以必有deg(Fi )3，即4(10 分） 證:設(shè)循環(huán)群A ，的生成元為a,同態(tài)映射為f, 同態(tài)像為 f(A ）,*, 于是an , amA都有f (anam )f (an ) *f (am )對(duì) n=1 有f ( a)f (a)n=2,有f (a2 )f (a

45、 a)f ( a) *f (a)( f (a) 2若 n=k 1 時(shí)有f ( ak 1 )( f (a) k 1對(duì) n=k 時(shí) ，f (ak )f (ak 1 a)f (ak1) *f (a)( f (a) k 1 *f (a)( f (a) k這表明， f（ A) 中每一個(gè)元素均可表示為5、證：( f (a) n ，所以 f（A ）， 為 f(a ） 生成的循環(huán)群。（ 1）交換律 :a,bB 有a * b( ab)(ab)(ba )(ba)b * a（ 2）結(jié)合律：a, b,cB 有(a * c( ab)(ab ) * c( ab)(ab)c)( ab)(ab )c(abcabc)( a(

46、ab)cabcabcabc而:abc(aabcbabcaabba acabc bcabcb )ca * (b * c)a * ( bc)(bc)( a(bc)(bc)( a(bc)(bc)a(bab(bc)abcabcabcabcabc(a * ca * (b * c)（ 3）幺：aB 有a * 0( a0)( a0)a0a0* a( 0a)(0a)0aa0是 B，*幺元。（ 4）逆：aBa * a( aa)(aa)000a是a的逆元 。綜上所述： B ， * 是阿貝爾群 .四、計(jì)算（ 22% ）1、（ 10 分）（1） (5 分)由 Huffman 方法，得最佳二叉樹為:（2）（ 5 分）最

47、佳前綴碼為:000， 001,01， 10， 11 2、（ 12 分）圖中奇數(shù)點(diǎn)為E、F ，d（E)=3,d(F ）=3，d（ E,F）=28 p=EGF復(fù)制道路 EG、GF，得圖 G ，則 G 是歐拉圖。由 D 開始找一條歐拉回路 :DEGFGEBACBDCFD 。道路長(zhǎng)度為：35+8+20+20+8+40+30+50+19+6+12+10+23=281。試卷六試題與答案一、填空15 （每小題3 分）1、 n 階完全圖結(jié)點(diǎn)v 的度數(shù) d（ v) =。2、 設(shè) n 階圖 G 中有 m 條邊，每個(gè)結(jié)點(diǎn)的度數(shù)不是k 的是 k+1 ，若 G 中有 Nk 個(gè) k 度頂點(diǎn),Nk+1 個(gè) k+1 度頂點(diǎn)，

48、則N k =.3、 算式(a(b * d)( e*f ) 的二叉樹表示為。4、 如圖給出格L，則 e 的補(bǔ)元是。5 、 一 組 學(xué) 生 ， 用 二 二 扳 腕 子 比 賽 法 來 測(cè) 定 臂 力 的 大 小 , 則 幺 元是。二、選擇15 （每小題3 分）1、設(shè) S= 0，1,2,3 ,為小于等于關(guān)系，則S，是（）。A 、群;B、環(huán)； C、域； D、格。2、設(shè) a， b ，c，* 為代數(shù)系統(tǒng)，運(yùn)算如下：abcaabcbbac則零元為 (） .ccccA 、a；B 、b；C、 c;D 、沒有。3、如右圖相對(duì)于完全圖K 5 的補(bǔ)圖為（)。4、一棵無向樹T 有 7 片樹葉， 3 個(gè) 3 度頂點(diǎn)，其余

49、頂點(diǎn)均為4 度。則 T 有（）4 度結(jié)點(diǎn)。A 、1；B、2；C、 3；D、 4。5、設(shè) A,+ ，是代數(shù)系統(tǒng),其中 +，為普通加法和乘法，則A= （）時(shí)， A ，+, 是整環(huán)。A 、 x | x2n, nZ ;B 、 x | x2 n1 , nZ ;C、 x | x0, 且xZ ;D、 x | xab4 5,a ,bR .三、證明50n 2m1、設(shè) G 是（ n,m）簡(jiǎn)單二部圖，則4。（10 分）m2、設(shè) G 為具有 n 個(gè)結(jié)點(diǎn)的簡(jiǎn)單圖,且1 (n21)( n2)，則 G 是連通圖。 (10 分）3、記“開”為1，“關(guān) 為 0，反映電路規(guī)律的代數(shù)系統(tǒng)0,1 ， +， 的加法運(yùn)算和乘法運(yùn)算。如下

50、：+0101001000110101證明它是一個(gè)環(huán)，并且是一個(gè)域。（ 14 分)4 、 L , 是一代數(shù)格， “”為自然偏序，則L ，是偏序格。 （ 16 分）四、 10設(shè) E(x1, x2 , x3 )( x1x2 )( x2x3 )( x 2x3 ) 是布爾代數(shù) 0,1, 上的一個(gè)布爾表達(dá)式，試寫出E( x1 , x2 , x3 ) 的析取范式和合取范式（10 分）五、 10%如下圖所示的賦權(quán)圖表示某七個(gè)城市v1,v2 , v7 及預(yù)先算出它們之間的一些直接通信成路造價(jià)（單位：萬元），試給出一個(gè)設(shè)計(jì)方案，使得各城市之間既能夠通信又使總造價(jià)最小。答案：一、填空15 (每小題 3 分）1、 n

51、 1； 2、n（ k+1)-2m;3 、如右圖；4 、0 ； 5、臂力小者二、選擇15（每小題3 分)題目12345三、證明50答案DCAAD（ 1）證：設(shè) G=（ V ， E） VXY , Xn1, Yn2, n1n2n2nn 2m對(duì)完全二部圖有nn1n2n1 (nn1)1n1nn22n( n1)24n當(dāng)12時(shí)，完全二部圖(n , m)的邊數(shù) m 有最大值4 n 2故對(duì)任意簡(jiǎn)單二部圖( n , m) 有 m4 .（ 2）證:反證法：若G 不連通，不妨設(shè)G 可分成兩個(gè)連通分支G1、G2，假設(shè) G1 和G2 的頂點(diǎn)數(shù)分別為n1 和 n2，顯然 n1n2nn11n21n1n1n2n1mn1(n11

52、)2n2 (n21)2(n1)(n1n22)2( n1)( n2)2與假設(shè)矛盾 .所以 G 連通。（ 3）（ 1） 0 ， 1 ， +， 是環(huán) 0， 1 ，+ 是交換群乘:由“ +”運(yùn)算表知其封閉性。由于運(yùn)算表的對(duì)稱性知:+運(yùn)算可交換。群: （ 0+0） +0=0+ （0+0 ） =0 ；（ 0+0 ） +1=0+ （ 0+1） =1;（0+1 ） +0=0+ （ 1+0 ）=1 ; (0+1 ） +1=0+ （ 1+1 ）=0；（1+1 ） +1=1+(1+1 ） =0結(jié)合律成立。幺：幺元為0。逆： 0， 1 逆元均為其本身。 0， 1 ,是半群乘：由“運(yùn)算表知封閉群: （ 0 0） 0=0

53、 （ 0 0）=0 ；（ 00) 1=0 （ 0 1） = 0；（ 0 1) 0=0（ 10） =0 ; （ 01) 1=0 （ 1 1） =0； (1 1） 1=1（ 1 1） =0 。對(duì) +的分配律x, y 0,10（ x+y ）=0=0+0= （ 0 x)+(0 y);1（ x+y ）當(dāng) x=y(x+y ）=0則1 ( x00y)1 0011(1 0)(1 1)(1 0)(1 1)(1 x)(1 y)；當(dāng) xy ( xy1 )則10(1 1)(1 0)1 (xy)1 1101(1 0)(1 1)(1 x)(1 y)所以x, y, z 0,1 均 有 z (xy)( z x)( zy)同理

54、可證：( xy) z(xz)( yz)所以對(duì) + 是可分配的 .由得， 0,1,+ ， 是環(huán)。 (2） 0 ， 1 ，+,是域因?yàn)?0 ， 1， +， 是有限環(huán) ,故只需證明是整環(huán)即可。乘交環(huán) : 由乘法運(yùn)算表的對(duì)稱性知，乘法可交換。含幺環(huán)：乘法的幺元是1無零因子：1 1=1 0因此 0,1 ， +, 是整環(huán) ,故它是域。4、證：（ 1 )“”是偏序關(guān)系， 自然偏序a,bLaba反自反性：由代數(shù)格冪等關(guān)系: aaaaa。反對(duì)稱性：a, bL若ab , b即： aa,bb ，則aababba傳遞性：ab , bc 則:ac(ab)cab即abaa(bc)結(jié)合律abbaaacc即bcbb即aba(

55、2）x, yL在 L 中存在 x，y的下（上）確界設(shè) x, y事實(shí)上：L 則: x x( xyinfy)( xx, yx)yxyxyx 同理可證 : xyy若 x ，y 有另一下界c，則 c( xy)(cx)ycyccxyxy 是x， y 最大下界，即xyinfx, y同理可證上確界情況.四、 14%解:函數(shù)表為：x1x2x3E( x1 , x2 , x3 )00000011010001111000101111011111E( x1, x2 , x3)( x1x 2(x1x3)(x1x2x3 )x2( x1x3 )( x1x2x3 )x2x3 )析取范式：合取范式：E( x1, x2 , x3

56、)( x1x2x3 )(x1x2x3)( x1x2x3 )五、 10解：用庫斯克 (Kruskal ）算法求產(chǎn)生的最優(yōu)樹。算法為：w(v1, v7 )1w(v7, v2 )4w(v7, v3 )9w(v3 , v4 )3 w(v4, v5 )17 w(v1, v6 )23 結(jié)果如圖：選 e1 選e2 選e3 選e選e選ev1v7 v7 v2 v7v3 v3v4v4 v5 v1v6樹權(quán) C(T)=23+1+4+9+3+17=57 （萬元）即為總造價(jià)試卷七試題與答案一、填空 15% （每小題 3 分）任何 (n,m)圖 G = (V,E ）， 邊與頂點(diǎn)數(shù)的關(guān)系是。當(dāng) n 為時(shí), 非平凡無向完全圖K

57、n 是歐拉圖 .已知一棵無向樹T 有三個(gè) 3 頂點(diǎn)，一個(gè)2 度頂點(diǎn) , 其余的都是1 度頂點(diǎn)， 則 T 中有個(gè) 1 度頂點(diǎn)。n 階完全圖Kn 的點(diǎn)色數(shù)X(KN)=。一組學(xué)生，用兩兩扳腕子比賽來測(cè)定臂力大小，則幺元是。二、選擇 15% （每小題3 分）1、下面四組數(shù)能構(gòu)成無向圖的度數(shù)列的有（)。A 、 2,3,4， 5， 6， 7；B、 1,2 ， 2,3 ， 4；2、圖的鄰接矩陣為（）。A.G1=(V1， E1),其中 V 1=a ，b,c,d， e,E 1= ab,be ， eb,ae ， de;B.G2=(V2， E2) 其中 V2=V1,E 2= a，b，b， c, c， a，a,d ，

58、d,a ，d,e ；C.G=(V3,E 3) ，其中 V3=V1,E 3= ab,be ， ed，cc ；D.G=（ V4， E4） , 其中 V4=V1,E 4= （ a， a） , （a,b),（ b， c ），（ e， c） ,(e,d）。4、下列圖中是歐拉圖的有（)。C、 2,1,1,1,2；D、 3 ， 3， 5，6， 0。1000111101000100010111110011010111011111110111011000 ;B、1111 ； C、1000 ； D 、10005、 G(2S ,) ，其中 S1,2,3 ,為集合對(duì)稱差運(yùn)算，則方程 1,2x1,3 的解為（）。A 、

59、 2,3;B 、1,2,3 ；C、 1,3;D、。A、。3、下列幾個(gè)圖是簡(jiǎn)單圖的有(）。三、證 明 341、 證明：在至少有2 個(gè)人的人群中,至少有2 個(gè)人，他的有相同的朋友數(shù)。（ 8 分）2、 若圖 G 中恰有兩個(gè)奇數(shù)頂點(diǎn)，則這兩個(gè)頂點(diǎn)是連通的。（ 8 分）3、 證明：在6 個(gè)結(jié)點(diǎn) 12 條邊的連通平面簡(jiǎn)單圖中,每個(gè)面的面度都是3.（ 8 分）4、 證明循環(huán)群的同態(tài)像必是循環(huán)群。(10 分）四、中國(guó)郵遞員問題13%求帶權(quán)圖G 中的最優(yōu)投遞路線。郵局在v 1 點(diǎn)。五、根樹的應(yīng)用 13 5、 7： 5在通訊中 ,八進(jìn)制數(shù)字出現(xiàn)的頻率如下：0:30% 、1：20%、2:15% 、3：10、 4：

60、10、 5：5、 6：求傳輸它們最佳前綴碼（寫出求解過程）。六、10*eababeeababaaeabbbbabeaababbae答案 :設(shè) B 4= e ，a ， b , ab ，運(yùn)算 * 如下表 ,則B 4,是一個(gè)群（稱作Klein 四元群十四、填空15 (每小題 3 分）1、 vd(v)V2m； 2、奇數(shù)； 3、5； 4、 n；5、臂力小者十五、選擇15（每小題3 分）題目12345答案BCBBA十六、證明341、（ 10 分) 證明：用n 個(gè)頂點(diǎn)v1， ,vn 表示n 個(gè)人,構(gòu)成頂點(diǎn)集V= v 1, ,vn，設(shè)E uv | u, vV, 且u,v是朋友（uv），無向圖G=（ V ， E