(完整版)《離散數(shù)學(xué)》試題及答案解析,推薦文檔

1、WORD 整理版一、填空題1 設(shè)集合 A,B，其中 A 1,2,3, B= 1,2,則 A - B _;(A)- (B) _ .2.設(shè)有限集合 A, |A| = n,則 |(A×A)| = _.3.設(shè)集合 A = a, b, B = 1, 2,則從 A 到 B 的所有映射是 _,其中雙射的是 _.4. 已知命題公式 G (P Q)R，則 G的主析取范式是 _.6 設(shè) A、 B為兩個集合 , A= 1,2,4, B = 3,4,則從 AB _;AB _;A B _ .7.設(shè) R 是集合 A 上的等價關(guān)系， 則 R所具有的關(guān)系的三個特性是 _,_, _.8.設(shè)命題公式 G (P(Q R)

2、 ，則使公式 G為真的解釋有 _ ，_, _.9.設(shè)集合 A 1,2,3,4,A上的關(guān)系 R1 = (1,4),(2,3),(3,2),R2 = (2,1),(3,2),(4,3),則 R ?R = _,R?R =_,1221R12 =_.10.設(shè)有限集 A, B， |A|= m, |B| = n,則| |(A B)| = _.11設(shè) A,B,R 是三個集合，其中 R 是實數(shù)集， A = x | -1 x 1, x R, B = x | 0 x <2, xR, 則 A-B = _ , B-A = _ ,A B = _ , .13. 設(shè)集合 A 2, 3, 4, 5, 6 ，R 是 A 上

3、的整除，則 R 以集合形式 ( 列舉法 ) 記為 _ .14.設(shè)一階邏輯公式G =xP(x)xQ(x) ，則 G的前束范式是_.16. 設(shè)謂詞的定義域為 a, b, 將表達式 xR(x) xS(x) 中量詞消除，寫成與之對應(yīng)的命題公式是_.17.設(shè)集合 A 1, 2, 3, 4， A 上的二元關(guān)系R (1,1),(1,2),(2,3), S(1,3),(2,3),(3,2)。則 RS專業(yè)資料學(xué)習(xí)參考WORD 整理版_,2_.R二、選擇題1設(shè)集合 A=2,a,3,4， B = a,3,4,1， E 為全集，則下列命題正確的是 ( ) 。(A)2 A (B)aA (C)aB E (D)a,1,3,

4、4B.2設(shè)集合 A=1,2,3,A上的關(guān)系R (1,1),(2,2),(2,3),(3,2),(3,3)，則 R 不具備().(A) 自反性(B) 傳遞性(C) 對稱性(D) 反對稱性3 設(shè)半序集 (A, ) 關(guān)系 的哈斯圖如下所示，若 A 的子集 B = 2,3,4,5, ( ) 。(A) 下界(B) 上界(C) 最小上界(D)以上答案都不對4下列語句中，()是命題。(A) 請把門關(guān)上(B)地球外的星球上也有人(C)x + 5 > 6(D)下午有會嗎？P(a, a) P(a,b) P(b,a) P(b,b)5 設(shè) I 是如下一個解釋：Da,b,1010則元素 6為 B的653 421則

5、在解釋 I 下取真值為1 的公式是 ().(A) x yP(x,y) (B)x yP(x,y)(C)xP(x,x) (D)xyP(x,y).6.若供選擇答案中的數(shù)值表示一個簡單圖中各個頂點的度，能畫出圖的是( ).(A)(1,2,2,3,4,5) (B)(1,2,3,4,5,5) (C)(1,1,1,2,3)(D)(2,3,3,4,5,6).7.設(shè) G、 H是一階邏輯公式，P 是一個謂詞， G xP(x), H xP(x), 則一階邏輯公式 G H是( ).(A) 恒真的(B) 恒假的(C)可滿足的(D)前束范式 .8 設(shè)命題公式G (PQ)， HP (QP)，則 G與 H的關(guān)系是 ( )。(

6、A)GH(B)HG(C)G H(D)以上都不是 .9設(shè) A, B 為集合，當(dāng)( )時 A BB.(A)A B(B)AB(C)BA(D)A B .10設(shè)集合 A = 1,2,3,4,A 上的關(guān)系 R (1,1),(2,3),(2,4),(3,4),則R具有( ) 。(A) 自反性(B) 傳遞性(C) 對稱性(D)以上答案都不對11下列關(guān)于集合的表示中正確的為( )。(A)aa,b,c(B)aa,b,c(C)a,b,c(D)a,ba,b,c12命題xG(x) 取真值1 的充分必要條件是 ().(A)對任意 x，G(x) 都取真值 1.(B)有一個 x ，使 G(x ) 取真值 1.00(C) 有某

7、些 x，使 G(x 0) 取真值 1. (D) 以上答案都不對 .13.設(shè) G是連通平面圖，有5 個頂點， 6 個面，則G的邊數(shù)是 ( ).(A) 9條 (B)5條(C) 6條(D) 11條 .0111115.10100設(shè)圖 G的相鄰矩陣為101，則 G的頂點數(shù)與邊數(shù)分別為 ( ).111010110110(A)4, 5(B)5, 6(C)4, 10(D)5, 8.三、計算證明題專業(yè)資料學(xué)習(xí)參考WORD 整理版1. 設(shè)集合 A 1, 2, 3, 4, 6, 8, 9, 12， R 為整除關(guān)系。(1) 畫出半序集 (A,R) 的哈斯圖；(2) 寫出 A 的子集 B = 3,6,9,12的上界，下

8、界，最小上界，最大下界；(3) 寫出 A 的最大元，最小元，極大元，極小元。2.設(shè)集合 A 1, 2, 3, 4， A 上的關(guān)系R (x,y) | x, yA 且 xy,求(1) 畫出 R的關(guān)系圖；(2) 寫出 R的關(guān)系矩陣 .3.設(shè) R 是實數(shù)集合，,是 R 上的三個映射，(x) = x+3,(x) = 2x,(x) x/4,試求復(fù)合映射?，?,?,?，?.4. 設(shè) I 是如下一個解釋： D = 2, 3,abf (2)f(3)P(2, 2)P(2, 3)P(3, 2)P(3, 3)32320011試求 (1)(,f(a) (,f( );P aP bb(2) x y P ( y, x).5.

9、設(shè)集合 A 1, 2, 4, 6, 8, 12， R為 A 上整除關(guān)系。(1) 畫出半序集 (A,R) 的哈斯圖；(2) 寫出 A 的最大元，最小元，極大元，極小元；(3)寫出 A 的子集 B = 4, 6, 8, 12的上界，下界，最小上界，最大下界.6.設(shè)命題公式 G = (P Q) (Q (P R), 求 G的主析取范式。7. (9 分 ) 設(shè)一階邏輯公式：G= (xP( x) yQ( y) xR( x) ，把 G化成前束范式 .9.設(shè) R 是集合 A = a, b,c, d.R是 A 上的二元關(guān)系 , R = (a,b), (b,a), (b,c), (c,d),(1)求出 r(R),

10、 s(R), t(R)；(2)畫出 r(R), s(R), t(R)的關(guān)系圖 .11. 通過求主析取范式判斷下列命題公式是否等價：(1) G = (P Q)(PQR)(2) H = (P (Q R) (Q (P R)13.設(shè) R和 S 是集合 A a, b, c, d 上的關(guān)系，其中R ( a, a),( a, c),( b, c),( c, d),S ( a,b),( b, c),( b, d),( d, d).(1) 試寫出 R和 S 的關(guān)系矩陣；(2) 計算 ?, , 1, 1? 1.RSR SRSR四、證明題參考答案一、填空題1. 3; 3,1,3,2,3,1,2,3.專業(yè)資料學(xué)習(xí)參考

11、WORD 整理版2. 2n 2 .3.= (a,1), (b,1),= ( ,2), (b,2),= (a,1), (b,2),= ( ,2), (b,1);12343,4.4. (P Q R).5. 12, 3.6. 4, 1, 2, 3, 4, 1, 2.7. 自反性；對稱性；傳遞性 .8. (1, 0, 0), (1, 0, 1), (1, 1, 0).9. (1,3),(2,2),(3,1); (2,4),(3,3),(4,2); (2,2),(3,3).10. 2m n.11. x | -1 x < 0, xR; x | 1 < x < 2, xR; x | 0 x

12、 1, xR.12. 12; 6.13. (2, 2),(2, 4),(2, 6),(3, 3),(3, 6),(4, 4),(5, 5),(6, 6).14.x(P(x) Q(x).15. 21.16. (R(a) R(b) (S(a) S(b).17. (1, 3),(2, 2); (1, 1),(1, 2),(1, 3).二、選擇題1. C. 2. D. 3. B. 4. B.5. D. 6. C. 7. C.8. A. 9. D. 10. B. 11. B.13.A. 14. A.15. D三、計算證明題1.128(1)694231(2) B無上界，也無最小上界。下界1, 3; 最大下

13、界是 3.(3) A無最大元，最小元是1，極大元 8, 12, 90+;極小元是 1.2. R = (1,1),(2,1),(2,2),(3,1),(3,2),(3,3),(4,1),(4,2),(4,3),(4,4).(1)14專業(yè)資料學(xué)習(xí)參考23WORD 整理版1000(2)1100M R110111113. (1)? ( (x) (x)+3 2x+3 2x+3.(2) ? ( (x) (x)+3 (x+3)+3 x+6,(3)? (x)(x)+3 x/4+3,(4)? (x) (x)/4 2x/4 = x/2,(5)?(?) ? +3 2x/4+3 x/2+3.4. (1)P( a,f

14、(a) P( b, f (b) = P(3, f (3) P(2, f (2)=P(3, 2)P(2,3)= 1 0= 0.(2)x y P( y,x) = x ( P (2, x) P (3,x)= ( P(2, 2)P (3, 2) ( P (2, 3) P (3, 3)= (0 1) (0 1)= 1 1= 1.5.(1)812462(2)無 最 大元，最小元1，極大元 8, 12;極小元是 1.(3) B 無上1界，無最小上界。下界 1, 2;最大下界 2.6. G =(P Q) (Q ( P R)= ( P Q)(Q (P R)專業(yè)資料學(xué)習(xí)參考WORD 整理版= (P Q) (Q (

15、P R)= (P Q) (Q P) (Q R)= (P Q R) (PQR) (P Q R) (P QR)(P Q R) (P QR)= (P Q R) (PQR) (P Q R) (P QR)(P Q R)= m3 m4m5 m6 m7 =(3, 4, 5, 6, 7).7. G= ( xP( x) yQ( y) xR( x) = ( xP( x) yQ( y) xR( x)= (xP( x) yQ( y) xR( x)= (xP( x) y Q( y) zR( z)=xy z(P( x) Q( y) R( z)9. (1) r(R) R I A(a,b), (b,a), (b,c), (c

16、,d), (a,a), (b,b), (c,c), (d,d), s(R) R R1 (a,b), (b,a), (b,c), (c,b) (c,d), (d,c),t(R) R R2 R3R4 (a,a),(a,b),(a,c),(a,d),(b,a),(b,b),(b,c),(b,d),(c,d)；(2) 關(guān)系圖 :adadadbcbcbcr(R)s(R)t(R)11. G(PQ)( PQR) (P Q R) (P Q R)( P Q R) m6 m7 m3 (3, 6, 7)H = (P (Q R) (Q (PR) (P Q) (QR) ( PQ R) (P QR) (P Q R)(P

17、Q R) (P QR) (P QR) (P Q R) ( PQ R) (P Q R) m6 m3 m7 (3, 6, 7)專業(yè)資料學(xué)習(xí)參考WORD 整理版G,H 的主析取范式相同，所以G = H.101001000010001113. (1) M R001M S0000000000001(2)R?S (a,),(c,),bd (a,a),(a,b),(a,c),(b,c),(,),(c,d),(d, ),R Sb dd1 (a,),(c,a),(c,b),( ,c),Rad 11 (b,a),(d,c).S?R四證明題2.設(shè) A,B 為任意集合，證明：(A-B)-C = A-(B C).3. (本題 10 分 ) 利用形式演繹法證明：A B,C B, C D蘊涵 A D。4. ( 本題 10 分 )A, B 為兩個任意集合，求證：A(AB) = (A B)B .1. 利用形式演繹法證明： P Q, RS, P R 蘊涵 Q S。1. 證明： P Q, R S, PR 蘊涵 QS(1)P RP(2)Q(1)R P(3)P QP(4)Q(2)(3)R Q(5)Q(4)Q R(6)PR S(7)QSQ(5)(6)(8)Q(7)Q S2.證明： (A-B)-C = (A B) C= A (B C)= A(B