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

《《離散數(shù)學(xué)》試題及答案.doc》由會員分享，可在線閱讀，更多相關(guān)《《離散數(shù)學(xué)》試題及答案.doc（13頁珍藏版）》請?jiān)谘b配圖網(wǎng)上搜索。

《離散數(shù)學(xué)》試題及答案 一、填空題 1 設(shè)集合A,B，其中A＝{1,2,3}, B= {1,2}, 則A - B＝ {3} ; r(A) - r(B)＝ {3},{1,3},{2,3},{1,2,3}} . 2. 設(shè)有限集合A, |A| = n, 則 |r(A×A)| = . 3. 設(shè)集合A = {a, b}, B = {1, 2}, 則從A到B的所有映射是a1= {(a,1), (b,1)}, a2= {(a,2), (b,2)},a3= {(a,1), (b,2)}, a4= {(a,2), (b,1)}, 其中雙射的是 a3, a4 . 4. 已知命題公式G＝?(P?Q)∧R，則G的主析取范式是 (P∧?Q∧R) 5.設(shè)G是完全二叉樹，G有7個點(diǎn)，其中4個葉點(diǎn)，則G的總度數(shù)為 12 ，分枝點(diǎn)數(shù)為 3 . 6 設(shè)A、B為兩個集合, A= {1,2,4}, B = {3,4}, 則從A?B＝ {4} ; AèB＝{1,2,3,4}; A－B＝ {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è)集合A＝{1,2,3,4}, A上的關(guān)系R1 = {(1,4),(2,3),(3,2)}, R2 = {(2,1),(3,2),(4,3)}, 則 R1·R2 = {(1,3),(2,2),(3,1)} , R2·R1 = {(2,4),(3,3),(4,2)} _ R12 = {(2,2),(3,3). 10. 設(shè)有限集A, B，|A| = m, |B| = n, 則| |r(A′B)| = . 11 設(shè)A,B,R是三個集合，其中R是實(shí)數(shù)集，A = {x | -1≤x≤1, x?R}, B = {x | 0≤x < 2, x?R},則A-B = -1<=x<0 , B-A = {x | 1 < x < 2, x?R} , A∩B = {x | 0≤x≤1, x?R} , . 13. 設(shè)集合A＝{2, 3, 4, 5, 6}，R是A上的整除關(guān)系，則R以集合形式(列舉法)記為 {(2, 2),(2, 4),(2, 6),(3, 3),(3, 6),(4, 4),(5, 5),(6, 6)} . 14. 設(shè)一階邏輯公式G = "xP(x)?$xQ(x)，則G的前束范式是 $x(?P(x)∨Q(x)) . 15.設(shè)G是具有8個頂點(diǎn)的樹，則G中增加 21 條邊才能把G變成完全圖。(完全圖的邊數(shù)，樹的邊數(shù)為n-1) 16. 設(shè)謂詞的定義域?yàn)閧a, b},將表達(dá)式"xR(x)→$xS(x)中量詞消除 ，寫成與之對應(yīng)的命題公式是_ (R(a)∧R(b))→(S(a)∨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){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)對稱性 (D)反對稱性 1 2 3 4 5 6 3 設(shè)半序集(A,≤)關(guān)系≤的哈斯圖如下所示，若A的子集B = {2,3,4,5},則元素6為B的( B )。 (A)下界 (B)上界 (C)最小上界 (D)以上答案都不對 4 下列語句中，( B )是命題。 (A)請把門關(guān)上 (B)地球外的星球上也有人 (C)x + 5 > 6 (D)下午有會嗎？ 5 設(shè)I是如下一個解釋：D＝{a,b}, 則在解釋I下取真值為1的公式是( D ). (A)$x"yP(x,y) (B)"x"yP(x,y) (C)"xP(x,x) (D)"x$yP(x,y). 6. 若供選擇答案中的數(shù)值表示一個簡單圖中各個頂點(diǎn)的度，能畫出圖的是( 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＝?(P?Q)，H＝P?(Q??P)，則G與H的關(guān)系是( A )。 (A)GTH (B)HTG (C)G＝H (D)以上都不是. 9 設(shè)A, B為集合，當(dāng)( D )時A－B＝B. (A)A＝B (B)AíB (C)BíA (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){a}?{a,b,c} (B){a}í{a,b,c} (C)??{a,b,c} (D){a,b}?{a,b,c} 12 命題"xG(x)取真值1的充分必要條件是( A ). (A) 對任意x，G(x)都取真值1. (B)有一個x0，使G(x0)取真值1. (C)有某些x，使G(x0)取真值1. (D)以上答案都不對. 13. 設(shè)G是連通平面圖，有5個頂點(diǎn)，6個面，則G的邊數(shù)是( A ). (A) 9條 (B) 5條 (C) 6條 (D) 11條. 14. 設(shè)G是5個頂點(diǎn)的完全圖，則從G中刪去( A )條邊可以得到樹. (A)6 (B)5 (C)10 (D)4. 15. 設(shè)圖G的相鄰矩陣為，則G的頂點(diǎn)數(shù)與邊數(shù)分別為( D ). (A)4, 5 (B)5, 6 (C)4, 10 (D)5, 8. 三、計(jì)算證明題 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的最大元，最小元，極大元，極小元。 解：（1） （2） B無上界，也無最小上界。下界1, 3; 最大下界是3 （3） A無最大元，最小元是1，極大元8, 12, 9; 極小元是1 2. 設(shè)集合A＝{1, 2, 3, 4}，A上的關(guān)系R＝{(x,y) | x, y?A 且 x 3 y}, 求 (1) 畫出R的關(guān)系圖； (2) 寫出R的關(guān)系矩陣. 解：（1） （2） 3. 設(shè)R是實(shí)數(shù)集合，s,t,j是R上的三個映射，s(x) = x+3, t(x) = 2x, j(x) ＝ x/4,試求復(fù)合映射s?t，s?s, s?j, j?t，s?j?t. 解： (1)s?t＝s(t(x))＝t(x)+3＝2x+3＝2x+3. (2)s?s＝s(s(x))＝s(x)+3＝(x+3)+3＝x+6, (3)s?j＝s(j(x))＝j(luò)(x)+3＝x/4+3, (4)j?t＝j(luò)(t(x))＝t(x)/4＝2x/4 = x/2, (5)s?j?t＝s?(j?t)＝j(luò)?t+3＝2x/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 (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è)集合A＝{1, 2, 4, 6, 8, 12}，R為A上整除關(guān)系。 (1) 畫出半序集(A,R)的哈斯圖； (2) 寫出A的最大元，最小元，極大元，極小元； (3) 寫出A的子集B = {4, 6, 8, 12}的上界，下界，最小上界，最大下界. 解：(1) (2)無最大元，最小元1，極大元8, 12; 極小元是1. (3) B無上界，無最小上界。下界1, 2; 最大下界2. 6. 設(shè)命題公式G = ?(P→Q)∨(Q∧(?P→R)), 求G的主析取范式。 解： G = ?(P→Q)∨(Q∧(?P→R)) = ?(?P∨Q)∨(Q∧(P∨R)) = (P∧?Q)∨(Q∧(P∨R)) = (P∧?Q)∨(Q∧P)∨(Q∧R) = (P∧?Q∧R)∨(P∧?Q∧?R)∨(P∧Q∧R)∨(P∧Q∧?R)∨(P∧Q∧R)∨(?P∧Q∧R) = (P∧?Q∧R)∨(P∧?Q∧?R)∨(P∧Q∧R)∨(P∧Q∧?R)∨(?P∧Q∧R) = m3∨m4∨m5∨m6∨m7 = S(3, 4, 5, 6, 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) = ($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)＝R∪IA＝{(a,b), (b,a), (b,c), (c,d), (a,a), (b,b), (c,c), (d,d)}, s(R)＝R∪R－1＝{(a,b), (b,a), (b,c), (c,b) (c,d), (d,c)}, t(R)＝R∪R2∪R3∪R4＝{(a,a), (a,b), (a,c), (a,d), (b,a), (b,b), (b,c), (b,d), (c,d)}； (2)關(guān)系圖: 11. 通過求主析取范式判斷下列命題公式是否等價： (1) G = (P∧Q)∨(?P∧Q∧R) (2) H = (P∨(Q∧R))∧(Q∨(?P∧R)) 解： G＝(P∧Q)∨(?P∧Q∧R) ＝(P∧Q∧?R)∨(P∧Q∧R)∨(?P∧Q∧R) ＝m6∨m7∨m3 ＝? (3, 6, 7) H = (P∨(Q∧R))∧(Q∨(?P∧R)) ＝(P∧Q)∨(Q∧R))∨(?P∧Q∧R) ＝(P∧Q∧?R)∨(P∧Q∧R)∨(?P∧Q∧R)∨(P∧Q∧R)∨(?P∧Q∧R) ＝(P∧Q∧?R)∨(?P∧Q∧R)∨(P∧Q∧R) ＝m6∨m3∨m7 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) 計(jì)算R?S, R∪S, R－1, S－1?R－1. 解： (1) (2)R?S＝{(a, b),(c, d)}, R∪S＝{(a, a),(a, b),(a, c),(b, c),(b, d),(c, d),(d, d)}, R－1＝{(a, a),(c, a),(c, b),(d, c)}, S－1?R－1＝{(b, a),(d, c)}. 四、證明題 1. 利用形式演繹法證明：{P→Q, R→S, P∨R}蘊(yùn)涵Q∨S。 解： (1) P∨R P (2) ?R→P Q(1) (3) P→Q P (4) ?R→Q Q(2)(3) (5) ?Q→R Q(4) (6) R→S P (7) ?Q→S Q(5)(6) (8) Q∨S Q(7) 2. 設(shè)A,B為任意集合，證明：(A-B)-C = A-(B∪C). 解： (A-B)-C = 3. (本題10分)利用形式演繹法證明：{?A∨B, ?C→?B, C→D}蘊(yùn)涵A→D。 解： (1) A D(附加) (2) ?A∨B P (3) B Q(1)(2) (4) ?C→?B 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) 所以 {?A∨B, ?C→?B, C→D}蘊(yùn)涵A→D. 4. (本題10分)A, B為兩個任意集合，求證： A－(A∩B) = (A∪B)－B . 解： 4. A－(A∩B) = 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. . 3. a1= {(a,1), (b,1)}, a2= {(a,2), (b,2)},a3= {(a,1), (b,2)}, a4= {(a,2), (b,1)}; a3, a4. 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, x?R}; {x | 1 < x < 2, x?R}; {x | 0≤x≤1, x?R}. 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 三、計(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) 3. (1)s?t＝s(t(x))＝t(x)+3＝2x+3＝2x+3. (2)s?s＝s(s(x))＝s(x)+3＝(x+3)+3＝x+6, (3)s?j＝s(j(x))＝j(luò)(x)+3＝x/4+3, (4)j?t＝j(luò)(t(x))＝t(x)/4＝2x/4 = x/2, (5)s?j?t＝s?(j?t)＝j(luò)?t+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)) = (0∨1)∧(0∨1) = 1∧1 = 1. 5. (1) (2) 無最大元，最小元1，極大元8, 12; 極小元是1. (3) B無上界，無最小上界。下界1, 2; 最大下界2. 6. G = ?(P→Q)∨(Q∧(?P→R)) = ?(?P∨Q)∨(Q∧(P∨R)) = (P∧?Q)∨(Q∧(P∨R)) = (P∧?Q)∨(Q∧P)∨(Q∧R) = (P∧?Q∧R)∨(P∧?Q∧?R)∨(P∧Q∧R)∨(P∧Q∧?R)∨(P∧Q∧R)∨(?P∧Q∧R) = (P∧?Q∧R)∨(P∧?Q∧?R)∨(P∧Q∧R)∨(P∧Q∧?R)∨(?P∧Q∧R) = m3∨m4∨m5∨m6∨m7 = S(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) = ($x?P(x)∧"y?Q(y))∨"zR(z) = $x"y"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)＝R∪R－1＝{(a,b), (b,a), (b,c), (c,b) (c,d), (d,c)}, t(R)＝R∪R2∪R3∪R4＝{(a,a), (a,b), (a,c), (a,d), (b,a), (b,b), (b,c), (b,d), (c,d)}； (2)關(guān)系圖: 11. G＝(P∧Q)∨(?P∧Q∧R) ＝(P∧Q∧?R)∨(P∧Q∧R)∨(?P∧Q∧R) ＝m6∨m7∨m3 ＝? (3, 6, 7) H = (P∨(Q∧R))∧(Q∨(?P∧R)) ＝(P∧Q)∨(Q∧R))∨(?P∧Q∧R) ＝(P∧Q∧?R)∨(P∧Q∧R)∨(?P∧Q∧R)∨(P∧Q∧R)∨(?P∧Q∧R) ＝(P∧Q∧?R)∨(?P∧Q∧R)∨(P∧Q∧R) ＝m6∨m3∨m7 ＝? (3, 6, 7) G,H的主析取范式相同，所以G = H. 13. (1) (2)R?S＝{(a, b),(c, d)}, R∪S＝{(a, a),(a, b),(a, c),(b, c),(b, d),(c, d),(d, d)}, R－1＝{(a, a),(c, a),(c, b),(d, c)}, S－1?R－1＝{(b, a),(d, c)}. 四 證明題 1. 證明：{P→Q, R→S, P∨R}蘊(yùn)涵Q∨S (1) P∨R P (2) ?R→P Q(1) (3) P→Q P (4) ?R→Q Q(2)(3) (5) ?Q→R Q(4) (6) R→S P (7) ?Q→S Q(5)(6) (8) Q∨S Q(7) 2. 證明：(A-B)-C = (A∩~B)∩~C = A∩(~B∩~C) = A∩~(B∪C) = A-(B∪C) 3. 證明：{?A∨B, ?C→?B, C→D}蘊(yùn)涵A→D (1) A D(附加) (2) ?A∨B P (3) B Q(1)(2) (4) ?C→?B 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) 所以 {?A∨B, ?C→?B, C→D}蘊(yùn)涵A→D. 5. 證明：A－(A∩B) = 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. 第 13 頁 共 13 頁