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

《離散數(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是完全二叉樹(shù)，G有7個(gè)點(diǎn)，其中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}; A－B＝ {1,2} . 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è)集合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是三個(gè)集合，其中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個(gè)頂點(diǎn)的樹(shù)，則G中增加 21 條邊才能把G變成完全圖。(完全圖的邊數(shù)，樹(shù)的邊數(shù)為n-1) 16. 設(shè)謂詞的定義域?yàn)閧a, b},將表達(dá)式"xR(x)→$xS(x)中量詞消除 ，寫成與之對(duì)應(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)對(duì)稱性 (D)反對(duì)稱性 1 2 3 4 5 6 3 設(shè)半序集(A,≤)關(guān)系≤的哈斯圖如下所示，若A的子集B = {2,3,4,5},則元素6為B的( B )。 (A)下界 (B)上界 (C)最小上界 (D)以上答案都不對(duì) 4 下列語(yǔ)句中，( B )是命題。 (A)請(qǐng)把門關(guān)上 (B)地球外的星球上也有人 (C)x + 5 > 6 (D)下午有會(huì)嗎？ 5 設(shè)I是如下一個(gè)解釋：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ù)值表示一個(gè)簡(jiǎn)單圖中各個(gè)頂點(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è)謂詞，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)GÞH (B)HÞG (C)G＝H (D)以上都不是. 9 設(shè)A, B為集合，當(dāng)( D )時(shí)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)對(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 ). (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中刪去( A )條邊可以得到樹(shù). (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無(wú)上界，也無(wú)最小上界。下界1, 3; 最大下界是3 （3） A無(wú)最大元，最小元是1，極大元8, 12, 9; 極小元是1 2. 設(shè)集合A＝{1, 2, 3, 4}，A上的關(guān)系R＝{(x,y) | x, yÎA 且 x ³ y}, 求 (1) 畫出R的關(guān)系圖； (2) 寫出R的關(guān)系矩陣. 解：（1） （2） 3. 設(shè)R是實(shí)數(shù)集合，s,t,j是R上的三個(gè)映射，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是如下一個(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 (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)無(wú)最大元，最小元1，極大元8, 12; 極小元是1. (3) B無(wú)上界，無(wú)最小上界。下界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. 通過(guò)求主析取范式判斷下列命題公式是否等價(jià)： (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為兩個(gè)任意集合，求證： 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. 自反性；對(duì)稱性；傳遞性. 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無(wú)上界，也無(wú)最小上界。下界1, 3; 最大下界是3. (3) A無(wú)最大元，最小元是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) 無(wú)最大元，最小元1，極大元8, 12; 極小元是1. (3) B無(wú)上界，無(wú)最小上界。下界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 頁(yè) 共 13 頁(yè)