《離散數(shù)學(xué)》試題及答案解析

1、一、填空題1 設(shè)集合 A,B ，其中 A 1,2,3, B= 1,2,則 A - B _3_;(A) - (B) _3,1,3,2,3,1,2,3_ .2.2. 設(shè)有限集合 A, |A| = n, 則 | (A ×A)| = _ 2n23.設(shè)集合 A = a, b, B = 1, 2, 則從 A 到 B 的所有映射是 _ 1 = ( a,1), (b,1),2 = ( a,2),(b,2), 3= ( a,1), (b,2), 4= ( a,2), ( b,1);_,其中雙射的是 _ 3, 4._4.已知命題公式 G (P Q)R，則 G 的主析取范式是_(P QR)_.5.設(shè) G

2、是完全二叉樹， G 有 7 個點，其中4 個葉點，則 G 的總度數(shù)為 _12_ ，分枝點數(shù)為 _3_.6 設(shè) A 、B 為兩個集合 , A= 1,2,4, B = 3,4,則從 A B _4_;AB _1, 2, 3, 4_;A B _1, 2_ .3.7. 設(shè) R 是集合 A 上的等價關(guān)系，則 R 所具有的關(guān)系的三個特性是 _自反性；對稱性；傳遞性 _.8. 設(shè)命題公式 G (P (Q R)，則使公式 G 為真的解釋有 _(1, 0, 0)_ ， _(1, 0, 1)_, _(1, 1, 0)_.9.設(shè)集合 A 1,2,3,4, A 上的關(guān)系 R1 = (1,4),(2,3),(3,2),

3、R 1 = (2,1),(3,2),(4,3), 則R1R2 = _(1,3),(2,2),(3,1)_,R2R1 =_(2,4),(3,3),(4,2)_,R12 =_(2,2),(3,3)_.4. 10. 設(shè)有限集 A, B ， |A| = m, |B| = n, 則 | | (A B)| = _2 m n_.11 設(shè)A,B,R是三個集合， 其中R 是實數(shù)集， A = x | -1x 1, xR, B = x | 0 x < 2, xR,則A-B = _x | -1 x < 0, xR_ , B-A = _x | 1 < x < 2, xR_ ,AB =_x | 0

4、 x 1, xR_ , .5. 13. 設(shè)集合 A 2, 3, 4, 5, 6 ，R 是 A 上的整除，則 R 以集合形式 (列舉法 )記為 _(2, 2),(2,4),(2, 6),(3, 3),(3, 6),(4, 4),(5, 5),(6, 6)_ .6.14. 設(shè)一階邏輯公式 G = xP(x)xQ(x) ，則 G 的前束范式是 _ x( P(x)Q(x)_.15.設(shè) G 是具有 8 個頂點的樹，則 G 中增加 _21_條邊才能把 G 變成完全圖。16.設(shè)謂詞的定義域為 a, b, 將表達(dá)式xR(x) xS(x) 中量詞消除，寫成與之對應(yīng)的命題公式是 _(R(a) R(b) (S(a)

5、 S(b)_.17. 設(shè)集合 A 1, 2, 3, 4 ， A 上的二元關(guān)系R (1,1),(1,2),(2,3), S (1,3),(2,3),(3,2) 。則R S _(1, 3),(2, 2)_,R2 _(1, 1),(1, 2),(1, 3)._.二、選擇題1設(shè)集合 A=2,a,3,4， B = a,3,4,1， E 為全集，則下列命題正確的是(C)。(A)2A(B)aA(C)aBE(D)a,1,3,4B.2設(shè)集合 A=1,2,3,A上的關(guān)系R (1,1),(2,2),(2,3),(3,2),(3,3)，則 R 不具備 ( D).(A) 自反性(B) 傳遞性(C)對稱性(D) 反對稱性

6、3設(shè)半序集 (A, )關(guān)系的哈斯圖如下所示，若A 的子集 B = 2,3,4,5, 則元素(B )。(A) 下界(B) 上界(C) 最小上界(D) 以上答案都不對4下列語句中， (B)是命題。(A) 請把門關(guān)上(B) 地球外的星球上也有人3(C)x + 5 > 6(D) 下午有會嗎？P( a, a) P(a, b) P(b, a) P(b, b)5 設(shè) I 是如下一個解釋：D a,b,1010則在解釋 I 下取真值為1 的公式是 ( D).6為B的65421(A) x yP(x,y)(B) x yP(x,y)(C) xP(x,x)(D)x yP(x,y).6.若供選擇答案中的數(shù)值表示一個

7、簡單圖中各個頂點的度，能畫出圖的是(C).(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是(C).(A) 恒真的(B) 恒假的(C)可滿足的(D)前束范式 .8設(shè)命題公式G (PQ)，H P (QP)，則 G與 H 的關(guān)系是 (A )。(A)G H(B)HG(C)G H(D) 以上都不是 .9設(shè) A,B 為集合，當(dāng) (D)時 AB B.(A)A B(B)AB(C)B A(D)A B .10設(shè)集合 A= 1

8、,2,3,4, A上的關(guān)系 R (1,1),(2,3),(2,4),(3,4),則 R具有(B)。(A) 自反性(B) 傳遞性(C)對稱性(D)以上答案都不對11下列關(guān)于集合的表示中正確的為( B)。(A)a a,b,c(B)a a,b,c (C)a,b,c(D)a,b a,b,c12命題 xG(x) 取真值 1 的充分必要條件是 ().(A) 對任意 x， G(x) 都取真值 1. (B) 有一個 x0，使 G(x 0 )取真值 1.(C) 有某些 x，使 G(x 0)取真值 1. (D) 以上答案都不對 .13.設(shè) G 是連通平面圖，有5 個頂點， 6 個面，則 G 的邊數(shù)是 ( A ).

9、(A)9 條(B)5 條(C)6 條(D) 11 條.14.設(shè) G 是 5 個頂點的完全圖，則從G中刪去( A)條邊可以得到樹 .(A)6(B)5(C)10(D)4.0111115.設(shè)圖 G 的相鄰矩陣為10100 ，則 G 的頂點數(shù)與邊數(shù)分別為 ( D ).110111010110110(A)4, 5(B)5, 6(C)4, 10(D)5, 8.三、計算證明題1.設(shè)集合 A 1, 2, 3, 4, 6, 8, 9, 12 ， R 為整除關(guān)系。(1) 畫出半序集 (A,R) 的哈斯圖；(2) 寫出 A 的子集 B = 3,6,9,12 的上界，下界，最小上界，最大下界；(3) 寫出 A 的最大

10、元，最小元，極大元，極小元。12869423(1)1(2) B 無上界，也無最小上界。下界1, 3; 最大下界是3.(3) A 無最大元，最小元是 1，極大元 8, 12, 90+; 極小元是 1.2.設(shè)集合 A 1, 2, 3, 4 ， A 上的關(guān)系R (x,y) | x, yA 且 xy,求(1) 畫出 R 的關(guān)系圖；(2) 寫出 R 的關(guān)系矩陣 .R = (1,1),(2,1),(2,2),(3,1),(3,2),(3,3),(4,1),(4,2),(4,3),(4,4).(1)14231000(2)MR1100111011113.設(shè) R 是實數(shù)集合，, , 是 R 上的三個映射，(x)

11、 = x+3,(x) = 2x,(x) x/4, 試求復(fù)合映射?，?,?,?，?.(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. 設(shè) I 是如下一個解釋： D = 2, 3,abf (2)f (3)P(2, 2)P(2,3)P(3,2)P(3, 3)32320011試求(1) P(a, f (a) P(b, f (b);(2) x y P (y, x).(1)

12、 P(a, f (a) P(b, f (b) = P(3, f (3) P(2, f (2) = P(3, 2) P(2, 3)=10 = 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)= (01) (0 1)= 1 1= 1.5. 設(shè)集合 A 1, 2, 4, 6, 8, 12 ， R 為 A 上整除關(guān)系。(1) 畫出半序集 (A,R) 的哈斯圖；(2) 寫出 A 的最大元，最小元，極大元，極小元；(3) 寫出 A 的子集 B = 4, 6, 8, 12 的上界，下界，最小上界，最大

13、下界.1)8124621(2) 無最大元，最小元 1，極大元 8, 12; 極小元是 1.(3) B 無上界，無最小上界。下界1, 2; 最大下界 2.6. 設(shè)命題公式G =(P Q) (Q(PR), 求 G 的主析取范式。G =(P Q) (Q (PR)=(P Q) (Q (P R)= (PQ)(Q (PR)= (PQ)(Q P) (Q R)= (PQ R) (PQR)(P Q R) (P QR) (P QR) (P Q R)= (PQ R) (PQR)(P Q R) (P QR) (PQ R)= m3 m4 m5 m6 m7 =(3, 4, 5, 6, 7).7. (9 分 )設(shè)一階邏輯公

14、式：G = (xP(x) yQ(y)xR(x)，把 G 化成前束范式.G = (xP(x)yQ(y) xR(x)= ( xP(x) yQ(y) xR(x)= (xP(x)yQ(y)xR(x)= ( xP(x)yQ(y)zR(z)=xyz(P(x)Q(y) R(z)9. 設(shè) R 是集合 A = a, b, c, d. R是 A 上的二元關(guān)系 , R = (a,b), (b,a), (b,c), (c,d),(1) 求出 r(R), s(R), t(R) ；(2) 畫出 r(R), s(R), t(R) 的關(guān)系圖 .(1) r(R) R IA (a,b), (b,a), (b,c), (c,d),

15、 (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) RR2 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. 通過求主析取范式判斷下列命題公式是否等價：(1) G = (PQ)( PQR)(2) H = (P (Q R) (Q (P R)G (PQ) (P Q R) (P Q R) (P QR) ( P Q R) m6 m7

16、 m3 (3, 6, 7)H = (P (QR) (Q ( P R) (P Q) (QR) ( P Q R) (P Q R) (P QR) ( P Q R) (P QR) ( P Q R) (P Q R) ( PQR) (P Q R) m6 m3 m7 (3, 6, 7)G,H 的主析取范式相同，所以G = H.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)系矩陣；111(2) 計算 R?S, RS, R, S?R

17、.10100100(1)MR001000110001M S000000000001(2)R?S ( a, b),(c, d),R S ( a, a),(a, b),(a, c),(b, c),(b, d),(c, d),( d, d), 1R ( a, a),(c, a),(c, b),(d, c), 1 1S?R ( b, a),(d, c).四、證明題1. 利用形式演繹法證明： P Q, RS, PR 蘊涵 Q S。證明： P Q, RS, P R 蘊涵 QS(1) P RP(2)R PQ(1)(3)P QP(4)R QQ(2)(3)(5)Q RQ(4)(6)R SP(7)Q SQ(5)(

18、6)(8)Q SQ(7)2. 設(shè) A,B 為任意集合，證明：(A-B)-C = A-(BC).證明： (A-B)-C = (A B) C= A(BC)= A(BC)= A-(B C)3. (本題 10 分 )利用形式演繹法證明： A B,C B,CD 蘊涵 A D。證明： AB,C B, CD 蘊涵 AD(1)AD(附加)(2)A BP(3)BQ(1)(2)(4)C BP(5)B CQ(4)(6)CQ(3)(5)(7)C DP(8)DQ(6)(7)(9)A DD(1)(8)所以 AB,C B, C D 蘊涵 A D.4. (本題 10 分 )A, B 為兩個任意集合，求證：A(A B) = (

19、A B)B .4. 證明： A (AB)= A(A B)A (A B) (A A) (A B) (A B) (A B)A B而 (A B)B= (A B) B= (A B) (B B)= (A B)= A B所以： A(A B) = (A B)B.參考答案一、填空題1.3;3,1,3,2,3,1,2,3.2. 2n2 .7.1= ( a,1), ( b,1),2= ( a,2), (b,2),3= ( a,1), (b,2),4= ( a,2), ( b,1);3,4.8.(PQ R).9. 12, 3.10. 4, 1, 2, 3, 4, 1, 2.11. 自反性；對稱性；傳遞性 .12.

20、(1, 0, 0), (1, 0, 1), (1, 1, 0).13. (1,3),(2,2),(3,1); (2,4),(3,3),(4,2); (2,2),(3,3).14. 2m n.15. x | -1 x < 0, xR; x | 1 < x < 2, xR; x | 0 x 1, xR.16. 12; 6.17. (2, 2),(2, 4),(2, 6),(3, 3),(3, 6),(4, 4),(5, 5),(6, 6).18.x(P(x) Q(x).19. 21.20. (R(a) R(b) (S(a) S(b).21. (1, 3),(2, 2); (1,

21、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.812(1)469231(2) B 無上界，也無最小上界。下界1, 3; 最大下界是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)14231000(2)MR1100111011113.(1) ? (x) (x)+3 2x+3 2x+3.

22、(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 (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)= (01) (0 1)= 1 1= 1.5. (1)812462(2

23、)無 最 大元，最小元 1，極大元8, 12;極小元是 1.(3)B 無上1界，無最小上界。下界1, 2;最大下界 2.6. G = (PQ) (Q ( P R)= ( P Q) (Q (P R)= (P Q)(Q (PR)= (P Q)(Q P) (Q R)= (PQ R) (PQR)(P Q R) (P QR) (P QR) (P Q R)= (PQ R) (PQR)(P Q R) (P QR) (PQ R)= m3 m4 m5 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)yQ(y)zR(z)=xyz(P(x)Q(y) R(z)9. (1) r(R) R IA (a,b), (b,a), (b,c), (c,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) RR2 R3R4 (a,a), (a,b), (a,c), (a,d), (b,a), (b,b), (b,c), (b,d), (c,d)；(2) 關(guān)系圖 :adadadbcbcbcr(R