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

1、實用文檔標(biāo)準(zhǔn)文案一、填空題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. 設(shè)有限集合a, |a| = n, 則 |(aa)| = 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 (pq)r，則 g的主析取范式是(pq r) 5. 設(shè)g是完全二叉樹，g有 7 個點，其中4 個葉點，

2、則g的總度數(shù)為12，分枝點數(shù)為 3 . 6 設(shè) a、b為兩個集合 , a= 1,2,4, b = 3,4, 則從 a b 4 ; ab1,2,3,4; ab 1,2 . 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è)集合 a1,2,3,4, a上的關(guān)系 r1= (1,4),(2,3),(3,2), r2= (2,1),(3,2),(4,3), 則 r1r2 = (1,3),(2,2),(3,1) , r2r1 =

3、 (2,4),(3,3),(4,2) _r12 = (2,2),(3,3). 10. 設(shè)有限集 a, b ，|a| = m, |b| = n, 則| |(a b)| = nm2 . 11 設(shè) a,b,r 是三個集合，其中r是實數(shù)集， a = x | -1x1, xr, b = x | 0 x 2, xr, 則 a-b = -1=x0 , b-a = x | 1 x 6 (d)下午有會嗎？5 設(shè) i 是如下一個解釋：da,b, 0101b) p(b,a) p(b,b) p(a,),(aap則在解釋 i 下取真值為1 的公式是 ( d ). (a)xyp(x,y) (b)xyp(x,y) (c)x

4、p(x,x) (d)x yp(x,y). 6. 若供選擇答案中的數(shù)值表示一個簡單圖中各個頂點的度，能畫出圖的是( 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), hxp(x), 則一階邏輯公式gh是( c ). (a) 恒真的 (b)恒假的 (c)可滿足的 (d)前束范式 . 8設(shè)命題公式g(pq)，hp(qp)，則 g與 h的關(guān)系是 ( a )。(a)gh (b)hg (c)g h (d)以上都不是 . 9設(shè) a, b 為集合，當(dāng) (

5、 d )時 abb. (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 具有( b )。(a) 自反性(b) 傳遞性(c) 對稱性 (d)以上答案都不對11下列關(guān)于集合的表示中正確的為( b )。(a)aa,b,c (b)aa,b,c (c)a,b,c (d)a,ba,b,c 12 命題xg(x) 取真值 1 的充分必要條件是( a ). (a) 對任意 x，g(x) 都取真值1. (b)有一個 x0，使 g(x0) 取真值 1. (c) 有某些 x，使 g(x0) 取真值 1. (

6、d)以上答案都不對. 13. 設(shè) g是連通平面圖，有5 個頂點， 6 個面，則g的邊數(shù)是 ( a ). (a) 9條 (b) 5條 (c) 6條 (d) 11條. 14. 設(shè) g是 5 個頂點的完全圖，則從g中刪去 ( a )條邊可以得到樹. (a)6 (b)5 (c)10 (d)4. 1 2 3 4 5 6 實用文檔標(biāo)準(zhǔn)文案15. 設(shè)圖 g的相鄰矩陣為0110110101110110010111110，則 g的頂點數(shù)與邊數(shù)分別為( d ). (a)4, 5 (b)5, 6 (c)4, 10 (d)5, 8. 三、計算證明題1. 設(shè)集合 a1, 2, 3, 4, 6, 8, 9, 12，r為整

7、除關(guān)系。(1) 畫出半序集 (a,r) 的哈斯圖；(2) 寫出 a的子集 b = 3,6,9,12的上界，下界，最小上界，最大下界；(3) 寫出 a的最大元，最小元，極大元，極小元。解： （1）124836129（2） b無上界，也無最小上界。下界1, 3; 最大下界是3 （3） a無最大元，最小元是1，極大元8, 12, 9; 極小元是1 2.設(shè)集合 a1, 2, 3, 4，a上的關(guān)系r (x,y) | x, ya 且 x y, 求(1) 畫出 r的關(guān)系圖；(2) 寫出 r的關(guān)系矩陣 . 解： （1）1234（2）1000110011101111rm3.設(shè) r是實數(shù)集合，, ,是 r上的三個

8、映射，(x) = x+3, (x) = 2x, (x) x/4,試求復(fù)合映射?，?, ?, ?，?. 解： (1)? (x) (x)+3 2x+32x+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,實用文檔標(biāo)準(zhǔn)文案(5)? (?) ?+32x/4+3 x/2+3. 4. 設(shè) i 是如下一個解釋：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

9、 (b); (2)x y p (y, x). 解：(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) = (0 1) (0 1) = 1 1 = 1. 5. 設(shè)集合 a1, 2, 4, 6, 8, 12， r為 a上整除關(guān)系。(1) 畫出半序集 (a,r) 的哈斯圖；(2) 寫出 a的最大元，最小元，極大元，極小元；(3) 寫出 a的子集 b

10、= 4, 6, 8, 12的上界，下界，最小上界，最大下界. 解： (1) (2)無最大元，最小元1，極大元8, 12; 極小元是 1. (3) b 無上界，無最小上界。下界1, 2; 最大下界2.6. 設(shè)命題公式g = (pq)(q(pr), 求 g的主析取范式。解：實用文檔標(biāo)準(zhǔn)文案 g = (pq)(q(pr) = (pq)(q(pr) = (p q)(q(pr) = (p q)(qp)(qr) = (p q r)(pqr)(pqr)(pqr)(p q r) (pq r) = (p q r)(pqr)(pqr)(pqr)(p qr) = m3m4m5m6m7 = (3, 4, 5, 6,

11、7). 7. (9 分) 設(shè)一階邏輯公式：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) y q(y) zr(z) = xy 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

12、)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)系圖 : bacdr(r)bacds(r)bacdt(r)實用文檔標(biāo)準(zhǔn)文案11. 通過求主析取范式判斷下列命題公式是否等價：(1) g = (p q)(pq r) (2) h = (p (qr) (q(pr) 解：g (

13、pq) (pq r) (pq r)(pqr)(pqr) m6 m7m3 (3, 6, 7) h = (p (q r) (q(pr) (pq)(qr) (pqr) (pq r)(pqr)(pqr)(pqr)(p q r) (pq r)(pq r)(pqr) m6 m3m7 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)系矩陣；(2) 計算r?s, rs, r1, s1?r 1. 解： (1)000

14、0100001000101rm1000000011000010sm(2)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。實用文檔標(biāo)準(zhǔn)文案解：(1) prp (2) rpq(1) (3) pq p (4) rqq(2)(3) (5) qrq(4) (6) rsp (7) qsq(5)(6) (8) qs q(7) 2. 設(shè) a,b 為任意集

15、合，證明：(a-b)-c = a-(bc). 解：(a-b)-c =cba)()()()(cbacbacba3. ( 本題 10 分 )利用形式演繹法證明：ab, c b, c d蘊(yùn)涵 ad。解：(1) a d(附加 ) (2) ab p (3) b q(1)(2) (4) cb p (5) b c q(4) (6) c q(3)(5) (7) c d p (8) d q(6)(7) (9) a d d(1)(8) 所以 ab, cb, c d蘊(yùn)涵 ad.4. (本題 10 分)a, b為兩個任意集合，求證：a(ab) = (a b)b . 實用文檔標(biāo)準(zhǔn)文案解：4.a(a b) = a(ab)

16、 a(ab) (aa)(a b) (ab) (ab) ab 而 (a b)b = (a b) b = (a b)(b b) = (a b)= ab 所以： a(ab) = (a b)b. 參考答案一、填空題1. 3; 3,1,3,2,3,1,2,3. 2.22n.3.1= (a,1), (b,1), 2= (a,2), (b,2),3= (a,1), (b,2), 4= (a,2), (b,1); 3, 4.4.(pqr).實用文檔標(biāo)準(zhǔn)文案5.12, 3. 6.4, 1, 2, 3, 4, 1, 2. 7.自反性；對稱性；傳遞性.8.(1, 0, 0), (1, 0, 1), (1, 1, 0

17、).9.(1,3),(2,2),(3,1); (2,4),(3,3),(4,2); (2,2),(3,3).10. 2m n.11. x | -1x 0, xr; x | 1 x 2, xr; x | 0 x1, 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

18、. d. 6. c. 7. c. 8. a. 9. d. 10. b. 11. b. 13. a. 14. a. 15. d 三、計算證明題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) 1248361291234實用文檔標(biāo)準(zhǔn)文案(2)1000110011101111rm3. (1)?( (x) (x)+3 2x+32x+3. (2)?(x)

19、(x)+3 (x+3)+3 x+6, (3)?(x) (x)+3 x/4+3, (4)? (x) (x)/4 2x/4 = x/2,(5)? (?) ?+32x/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) = (0 1) (0 1) = 1 1 = 1. 5. (1) (2) 無 最 大元，最小元1，極大元8

20、, 12; 極小元是1. (3) b無上界，無最小上界。下界1, 2; 最大下界2. 6. g = (pq)(q(pr) = (pq)(q(pr) = (p q)(q(pr) = (p q)(qp)(qr) = (p q r)(pqr)(pqr)(pqr)(p q r) (pq r) 2416812實用文檔標(biāo)準(zhǔn)文案= (p q r)(pqr)(pqr)(pqr)(p qr) = m3m4m5m6m7 = (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

21、q(y) zr(z) = xy z(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) 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)(pqr)(pqr) m6 m7m3 (3, 6, 7) h = (p (q r) (q(pr) (pq)(qr) (pqr) (pq r)(pqr)(pqr)(pqr)(