離散數(shù)學(xué)精彩試題及問題詳解

1、實(shí)用文檔 標(biāo)準(zhǔn)文案 一、填空題 1 設(shè)集合A,B，其中A1,2,3, B= 1,2, 則A - B_3_; ?(A) - ?(B) 2,3_ . 2. 2. 設(shè)有限集合A, |A| = n, 則 |?(A×A)| = _22n 3. 設(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是完全二叉樹，G有7個(gè)點(diǎn)，

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

3、3),(2,2),(3,1)_,R2?R1 =_(2,4),(3,3),(4,2)_ _, R12 =_(2,2),(3,3)_. 4. 10. 設(shè)有限集A, B，|A| = m, |B| = n, 則| |?(A?B)| = _2m?n_. 11 設(shè)A,B,R是三個(gè)集合，其中R是實(shí)數(shù)集，A = x | -1x1, x?R, B = x | 0x < 2, x?R,則A-B = _x | -1x < 0, x?R_ , B-A = _x | 1 < x < 2, x?R_ , AB = _x | 0x1, x?R_ , . 5. 13. 設(shè)集合A2, 3, 4, 5,

4、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è)頂點(diǎn)的樹，則G中增加_21_條邊才能把G變成完全圖。 16. 設(shè)謂詞的定義域?yàn)閍, b,將表達(dá)式?xR(x)?xS(x)中量詞消除，寫成與之對(duì)應(yīng)的命題公式是_(R(a)R(b)(S(a)S(b)_. 實(shí)用文檔 標(biāo)準(zhǔn)文案 17. 設(shè)集合A1, 2, 3, 4，A上的二元關(guān)系R(1,1),(1,2),(2,

5、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)2?A (B)a?A (C)?a?B?E (D)a,1,3,4?B. 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)對(duì)稱性 (D)反對(duì)稱性 3 設(shè)半序集(A,)關(guān)系的哈斯圖如下所示，若A的子集B = 2,3,4,5,則元素6為B的(

6、B )。 (A)下界 (B)上界 (C)最小上界 (D)以上答案都不對(duì) 4 下列語句中，( B )是命題。 (A)請(qǐng)把門關(guān)上 (B)地球外的星球上也有人 (C)x + 5 > 6 (D)下午有會(huì)嗎？ 5 設(shè)I是如下一個(gè)解釋：D a,b, 0 1 0 1b) P(b,a) P(b,b) P(a,),(aaP 則在解釋I下取真值為1的公式是( D ). (A)?x?yP(x,y) (B)?x?yP(x,y) (C)?xP(x,x) (D)?x?yP(x,y). 6. 若供選擇答案中的數(shù)值表示一個(gè)簡單圖中各個(gè)頂點(diǎn)的度，能畫出圖的是( C ). (A)(1,2,2,3,4,5) (B)(1,2,

7、3,4,5,5) (C)(1,1,1,2,3) (D)(2,3,3,4,5,6). 7. 設(shè)G、H是一階邏輯公式，P是一個(gè)謂詞，G?xP(x), H?xP(x),則一階邏輯公式G?H是( C ). (A)恒真的 (B)恒假的 (C)可滿足的 (D)前束范式. 8 設(shè)命題公式G?(P?Q)，HP?(Q?P)，則G與H的關(guān)系是( A )。 (A)G?H (B)H?G (C)GH (D)以上都不是. 9 設(shè)A, B為集合，當(dāng)( D )時(shí)ABB. (A)AB (B)A?B (C)B?A (D)AB?. 10 設(shè)集合A = 1,2,3,4, A上的關(guān)系R(1,1),(2,3),(2,4),(3,4),

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

9、去( A )條邊可以得到樹. (A)6 (B)5 (C)10 (D)4. 15. 設(shè)圖G的相鄰矩陣為?0110110101110110010111110，則G的頂點(diǎn)數(shù)與邊數(shù)分別為( D ). 1 2 3 4 5 6 實(shí)用文檔 標(biāo)準(zhǔn)文案 (A)4, 5 (B)5, 6 (C)4, 10 (D)5, 8. 三、計(jì)算證明題 1.設(shè)集合A1, 2, 3, 4, 6, 8, 9, 12，R為整除關(guān)系。 (1) 畫出半序集(A,R)的哈斯圖； (2) 寫出A的子集B = 3,6,9,12的上界，下界，最小上界，最大下界； (3) 寫出A的最大元，最小元，極大元，極小元。 (1) 124836129 (2)

10、 B無上界，也無最小上界。下界1, 3; 最大下界是3. (3) A無最大元，最小元是1，極大元8, 12, 90+; 極小元是1. 2. 設(shè)集合A1, 2, 3, 4，A上的關(guān)系R(x,y) | x, y?A 且 x ? y, 求 (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) (2)1000110011101111RM? 3. 設(shè)R是實(shí)數(shù)集合，?,?,?是R上的三個(gè)映射，?(x) = x+3, ?(x) = 2x, ?(x) x/4,試求復(fù)合映射?

11、，?, ?, ?，?. (1)?(?(x)?(x)+32x+32x+3. (2)?(?(x)?(x)+3(x+3)+3x+6, (3)?(?(x)?(x)+3x/4+3, (4)?(?(x)?(x)/42x/4 = x/2, (5)?(?)?+32x/4+3x/2+3. 1 2 3 4 實(shí)用文檔 標(biāo)準(zhǔn)文案 4. 設(shè)I是如下一個(gè)解釋：D = 2, 3, a b f (2) f (3) P(2, 2) P(2, 3) P(3, 2) P(3, 3) 3 2 3 2 0 0 1 1 試求 (1) P(a, f (a)P(b, f (b); (2) ?x?y P (y, x). (1) P(a, f

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

13、元1，極大元8, 12; 極小元是1. (3) B無上界，無最小上界。下界1, 2; 最大下界2. 6. 設(shè)命題公式G = ?(PQ)(Q(?PR), 求G的主析取范式。 G = ?(PQ)(Q(?PR) = ?(?PQ)(Q(PR) 2416812實(shí)用文檔 標(biāo)準(zhǔn)文案 = (P?Q)(Q(PR) = (P?Q)(QP)(QR) = (P?QR)(P?Q?R)(PQR)(PQ?R)(PQR)(?PQR) = (P?QR)(P?Q?R)(PQR)(PQ?R)(?PQR) = m3m4m5m6m7 = ?(3, 4, 5, 6, 7). 7. (9分)設(shè)一階邏輯公式：G = (?xP(x)?yQ(y

14、)?xR(x)，把G化成前束范式. G = (?xP(x)?yQ(y)?xR(x) = ?(?xP(x)?yQ(y)?xR(x) = (?xP(x)?yQ(y)?xR(x) = (?x?P(x)?y?Q(y)?zR(z) = ?x?y?z(?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)RIA(a,b), (b,a), (b,c), (c,d), (a,a),

15、(b,b), (c,c), (d,d), s(R)RR1(a,b), (b,a), (b,c), (c,b) (c,d), (d,c), t(R)RR2R3R4(a,a), (a,b), (a,c), (a,d), (b,a), (b,b), (b,c), (b,d), (c,d)； (2)關(guān)系圖: 11. 通過求主析取范式判斷下列命題公式是否等價(jià)： (1) G = (PQ)(?PQR) (2) H = (P(QR)(Q(?PR) G(PQ)(?PQR) (PQ?R)(PQR)(?PQR) m6m7m3 bacdr(R)bacds(R)bacdt(R) 實(shí)用文檔 標(biāo)準(zhǔn)文案 ? (3, 6, 7

16、) H = (P(QR)(Q(?PR) (PQ)(QR)(?PQR) (PQ?R)(PQR)(?PQR)(PQR)(?PQR) (PQ?R)(?PQR)(PQR) m6m3m7 ? (3, 6, 7) G,H的主析取范式相同，所以G = H. 13. 設(shè)R和S是集合Aa, 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) 計(jì)算R?S, RS, R1, S1?R1. (1)?0000100001000101RM ?1000000011000010SM (2)

17、R?S(a, b),(c, d), RS(a, a),(a, b),(a, c),(b, c),(b, d),(c, d),(d, d), R1(a, a),(c, a),(c, b),(d, c), S1?R1(b, a),(d, c). 四、證明題 1. 利用形式演繹法證明：PQ, RS, PR蘊(yùn)涵QS。 證明：PQ, RS, PR蘊(yùn)涵QS (1) PR P (2) ?RP Q(1) (3) PQ P (4) ?RQ Q(2)(3) (5) ?QR Q(4) (6) RS P 實(shí)用文檔 標(biāo)準(zhǔn)文案 (7) ?QS Q(5)(6) (8) QS Q(7) 2. 設(shè)A,B為任意集合，證明：(A-

18、B)-C = A-(BC). 證明：(A-B)-C = (AB)C = A(BC) = A(BC) = A-(BC) 3. (本題10分)利用形式演繹法證明：?AB, ?C?B, CD蘊(yùn)涵AD。 證明：?AB, ?C?B, CD蘊(yùn)涵AD (1) A D(附加) (2) ?AB P (3) B Q(1)(2) (4) ?C?B P (5) BC Q(4) (6) C Q(3)(5) (7) CD P (8) D Q(6)(7) (9) AD D(1)(8) 所以 ?AB, ?C?B, CD蘊(yùn)涵AD. 4. (本題10分)A, B為兩個(gè)任意集合，求證： A(AB) = (AB)B . 4. 證明：

19、A(AB) = A(AB) A(AB) (AA)(AB) ?(AB) (AB) 實(shí)用文檔 標(biāo)準(zhǔn)文案 AB 而 (AB)B = (AB)B = (AB)(BB) = (AB)? = AB 所以：A(AB) = (AB)B. 參考答案 一、填空題 1. 3; 2,3. 2. 22n. 7. ?1= (a,1), (b,1), ?2= (a,2), (b,2),?3= (a,1), (b,2), ?4= (a,2), (b,1); ?3, ?4. 8. (P?QR). 9. 12, 3. 10. 4, 1, 2, 3, 4, 1, 2. 11. 自反性；對(duì)稱性；傳遞性. 12. (1, 0, 0),

20、 (1, 0, 1), (1, 1, 0). 實(shí)用文檔 標(biāo)準(zhǔn)文案 13. (1,3),(2,2),(3,1); (2,4),(3,3),(4,2); (2,2),(3,3). 14. 2m?n. 15. x | -1x < 0, x?R; x | 1 < x < 2, x?R; x | 0x1, x?R. 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,

21、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 三、計(jì)算證明題 1. (1) (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) (2)1000110011101111RM? 3

22、. (1)?(?(x)?(x)+32x+32x+3. (2)?(?(x)?(x)+3(x+3)+3x+6, 124836129 1 2 3 4 實(shí)用文檔 標(biāo)準(zhǔn)文案 (3)?(?(x)?(x)+3x/4+3, (4)?(?(x)?(x)/42x/4 = x/2, (5)?(?)?+32x/4+3x/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) = 10 = 0. (2) ?x?y P (y, x) = ?x (P (2, x)P (3, x) = (P (2, 2)P (3, 2)(P (2, 3

23、)P (3, 3) = (01)(01) = 11 = 1. 5. (1) (2) 無最大元，最小元1，極大元8, 12; 極小元是1. (3) B無上界，無最小上界。下界1, 2; 最大下界2. 6. G = ?(PQ)(Q(?PR) = ?(?PQ)(Q(PR) = (P?Q)(Q(PR) = (P?Q)(QP)(QR) = (P?QR)(P?Q?R)(PQR)(PQ?R)(PQR)(?PQR) = (P?QR)(P?Q?R)(PQR)(PQ?R)(?PQR) = m3m4m5m6m7 = ?(3, 4, 5, 6, 7). 7. G = (?xP(x)?yQ(y)?xR(x) = ?(?

24、xP(x)?yQ(y)?xR(x) = (?xP(x)?yQ(y)?xR(x) = (?x?P(x)?y?Q(y)?zR(z) 2416812 實(shí)用文檔 標(biāo)準(zhǔn)文案 = ?x?y?z(?P(x)?Q(y)R(z) 9. (1) r(R)RIA(a,b), (b,a), (b,c), (c,d), (a,a), (b,b), (c,c), (d,d), s(R)RR1(a,b), (b,a), (b,c), (c,b) (c,d), (d,c), t(R)RR2R3R4(a,a), (a,b), (a,c), (a,d), (b,a), (b,b), (b,c), (b,d), (c,d)； (2)關(guān)系圖: 11. G(PQ)(?PQR) (PQ?R