(完整word版)離散數(shù)學(xué)試卷及答案(1)

1、2066628238.doc1、填空 20% (每小題 2 分)1 設(shè)A x|(x N)且(x 5), B x|x E 且 x 7(N:自然數(shù)集，E+正偶數(shù))則A B _。2. A , B , C 表示三個(gè)集合，文圖中陰影部分的集合表達(dá)式為3.設(shè) P, Q 的真值為0，R, S 的真值為 1，則(P (Q (R P) (R S)的真值=_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 的哈斯圖為4公式(P R) (S R)P的主合取范式為2

2、066628238.doc2則 R=2066628238.doc39.設(shè) A=a , b, c, d , A 上二元運(yùn)算如下:*abcdaabcdbbcdaccdabddabc那么代數(shù)系統(tǒng)A , *的幺元是，有逆兀的兀素為分別為o10 下圖所示的偏序集中，是格的為 _，它們的逆元、選擇 20% （每小題 2 分）1、下列是真命題的有（A aa；)B ， ；C. ，；2、下列集合中相等的有（A 4 , 3; B. D ),3, 4 ; C. 4 ,。,3, 3; D .3 , 4。3、設(shè) A=1 , 2, 3，則 A 上的二元關(guān)系有（）個(gè)。2066628238.doc3。4A.23； B.32；

3、 C.23 3； D.32 24、設(shè) R, S 是集合 A 上的關(guān)系，則下列說法正確的是（）5、設(shè) A=1 , 2, 3, 4 , P (A) ( A 的幕集)上規(guī)定二元系如下R s,t |s,t p(A) (|s| |t|則 P (A) / R=()A . A ; B. P(A) ; C. 1 , 1 , 2 , 1 , 2, 3 , 1 ,D . , 2 , 2 , 3 , 2 , 3, 4 , A6、設(shè) A=, 1 , 1 , 3, 1 , 2 , 3則 A 上包含關(guān)系“廣、1,2.31/ 1,31- 1,3)z/Ill(A(B)C7、 下列函數(shù)是雙射的為（)A . f : IE , f

4、 (x) = 2x ;B . f : NN N,f (n) = （注：I整數(shù)集，E偶數(shù)集，N 自然數(shù)集,D)9、下圖中既不是 Eular 圖，也不是 Hamilton 圖的圖是（&圖A .0;）條。A .若 R, S 是自反的，B .若 R，S 是反自反的,C .若 R, S 是對稱的，D.若 R, S 是傳遞的，則R S是自反的；則R S是反自反的;則R S是對稱的；則R S是傳遞的。2 , 3 , 4;的哈斯圖為（）2066628238.doc5A . 1; B. 2; C. 3; D. 4。三、證明 26%1、 R 是集合 X 上的一個(gè)自反關(guān)系，求證：R 是對稱和傳遞的，當(dāng)且僅當(dāng)

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

6、）。（ 9 分）點(diǎn)。B)CP)7 片樹葉，3 個(gè) 3 度結(jié)點(diǎn)，其余都是 4 度結(jié)點(diǎn)則該樹有（）個(gè) 4 度結(jié)2、x(P(x) Q(x) xP(x)xQ(x)用矩陣運(yùn)算求出2066628238.doc62、如下圖所示的賦權(quán)圖表示某七個(gè)城市Vi,V2, ,V及預(yù)先算出它們之間的一些直接通信線路造價(jià)，試給出一個(gè)設(shè)計(jì)方案，使得各城市之間能夠通信而且總造價(jià)最小。一、填空 20% (每空 2 分)1、2(X+1)； 2、 a,a , a,b , a,c , c,c , b,a , c,a ； 3、 2,1 ,3,1 ,5,1 ,4,2 ,6,2 ,6,3;_4、反對稱性、反自反性；4、 ,2, 2, ,2,

7、 2; 5、1;6、(P Q R) ( P Q R) (P Q R); 7、任意 x,如果X是素?cái)?shù)則存在個(gè) y, y 是奇數(shù)且 y 整除X； 8、Xy z u( P(x,z) P(y, z) Q(x, y,u)。選擇 20% （每小題 2 分）題目12345678910答案CCCCABDADC三、證明 16%（每小題 8 分）1、1AP （附加前提）2A BTI(9分)v5訂 巴2066628238.doc73A BCDP2066628238.doc82066628238.doc9C DT1DT1D ET1DE FPFT1A FCP2、xP(x) xQ(x)( x)P(x)xQ(x)本題可證x

8、(P(x) Q(x)( xP(x)xQ(x)(xP(x)P （附加前提）x( P(x)TEP(a)ESx(P(x) Q(x)PP(a) Q(a)USQ(a)T1xQ(x)EG(xP(x)xQ(x)CP四、14%證明：（1）自反性：x, yX,由于 x yx yx,y,x, yRR 自反（2） 對稱性：x1, y1X,x2, y2X當(dāng)xi, yi,X2, y2R 時(shí)即 x1y2x2y1也即 x2y1故x22,x1,y1RR 有對稱性1、Xi目22066628238.doc10(3)傳遞性：x1,y1XJX2 ”2Xx3,y3當(dāng)x1,y17x2,y2R 且x2,y2,x3,y3R 時(shí)即X1y2X2

9、y1X2y3X3y2(2)X1y2X2y3X2y1X3y2即:X1y3X3y1故1JX3,乂RR 有傳遞性由（1) (2)(3)知：R 是 X 上的先等價(jià)關(guān)系。010010101、MR關(guān)系圖00010000101001012、MR2MRMRR000000000 10 110 10MR3MR2MR0000000010100101MR4MR3MR00000000Mt(R)MRMR2MR3MR4MR2MR5MR3, MR6MR4,11111111000100002066628238.doc112、X/R=1 ,2R五、10%t (R)= , , , , , , , 2066628238.doc12六

10、、20%f g x, y | x domf x domg y f(x) y1、(1) x, y | x domf domg y f (x)g(x)令 h f gdomf g domh x | x domf domg, f (x)g(x)(2)h x, y | x domf domg y h(x) f (x)g(x)對 x domh 若有 y!, y2使得y1h(x) f (x) g(x) , y2h(x) f(x) g(x)由于 f (或 g)是函數(shù)，有 yiy 即 x domh 有唯一 y 使得 yf g 也是函數(shù)。2、證明：若 f 有一左逆 g ,則對 t T g f(t) t故 g f 是入射，所以 f 是入射。f 是入射，f :TS 定義如下：s f