電大《離散數(shù)學(xué)》模擬試題及答案

1、電大離散考試模擬試卷及答案一、填空題1 設(shè)集合 A,B ，其中 A 1,2,3, B= 1,2,則 A - B _ 。(A)-(B) _ .2. 設(shè)有限集合A,|A| = n, 則 | (A ×A)| = _.3. 設(shè)集合 A = a, b, B = 1, 2,則從 A 到 B 的所有映射是 _, 其中雙射的是_.4. 已知命題公式 G (PQ)R，則 G 的主析取范式是_.5.設(shè) G 是完全二叉樹，G 有 7 個(gè)點(diǎn)，其中4 個(gè)葉點(diǎn)，則G 的總度數(shù)為 _ ，分枝點(diǎn)數(shù)為 _.6 設(shè) A 、 B 為兩個(gè)集合 , A= 1,2,4,B = 3,4,則從 AB _ 。AB _ 。 A B _

2、 .7. 設(shè) R 是集合 A 上的等價(jià)關(guān)系，則R 所具有的關(guān)系的三個(gè)特性是_,_, _.8. 設(shè)命題公式G(P(Q R) ，則使公式G 為真的解釋有_ ，_,_.9. 設(shè)集合 A 1,2,3,4, A上的關(guān)系R1 = (1,4),(2,3),(3,2), R1 = (2,1),(3,2),(4,3),則R1 R2 = _,R 2 R1 =_,2R1 =_.10. 設(shè)有限集A, B ， |A| = m, |B| = n, 則| | (AB)| = _.11 設(shè) A,B,R 是三個(gè)集合，其中R 是實(shí)數(shù)集， A = x | -1 x 1, xR, B = x | 0 x < 2,xR, 則 A

3、-B = _ , B-A = _ ,A B = _ , .13. 設(shè)集合 A 2, 3, 4, 5, 6 ， R 是 A 上的整除，則R 以集合形式 (列舉法 )記為_(kāi) .14. 設(shè)一階邏輯公式G =xP(x)xQ(x) ，則 G 的前束范式是_.1 / 815.設(shè) G 是具有 8 個(gè)頂點(diǎn)的樹，則G 中增加 _條邊才能把G 變成完全圖。16. 設(shè)謂詞的定義域?yàn)?a, b, 將表達(dá)式xR(x) xS(x) 中量詞消除，寫成與之對(duì)應(yīng)的命題公式是 _.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

4、S _,R2 _.二、選擇題1 設(shè)集合 A=2,a,3,4， B = a,3,4,1，E 為全集，則下列命題正確的是()。(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 不具備 ().(A) 自反性(B) 傳遞性(C)對(duì)稱性(D) 反 對(duì) 稱性3設(shè)半序集 (A, )關(guān)系的哈斯圖如下所示，若A的子集 B = 2,3,4,5, 則元素()。(A) 下界(B) 上界(C) 最小上界(D) 以上答案都不對(duì)4下列語(yǔ)句中， ( ) 是命題。(A) 請(qǐng)把門關(guān)上(B) 地球外的星球上也有人3(

5、C)x + 5 > 6 (D) 下午有會(huì)嗎？5設(shè) I 是如下一個(gè)解釋：P(a, a) P(a, b)P(b, a) P(b, b)D a,b,01016為B的65421則在解釋 I 下取真值為1 的公式是 ().(A)xyP(x,y)(B)xyP(x,y)(C)xP(x,x)(D)x yP(x,y).6. 若供選擇答案中的數(shù)值表示一個(gè)簡(jiǎn)單圖中各個(gè)頂點(diǎn)的度，能畫出圖的是().(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),

6、則一階邏輯公式 G H 是( ).(A) 恒真的(B) 恒假的(C) 可滿足的(D)前束范式 .8 設(shè)命題公式G(PQ)， H P(QP)，則 G 與 H 的關(guān)系是 ()。(A)GH(B)HG(C)G H(D) 以上都不是 .9 設(shè) A, B 為集合，當(dāng) ()時(shí) 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 具有 () 。(A) 自反性(B) 傳遞性(C)對(duì)稱性(D) 以上答案都不對(duì)11 下列關(guān)于集合的表示中正確的為() 。(A)aa,b,c (B)aa,b,c(C)a,b,

7、c(D)a,ba,b,c12 命題xG(x) 取真值 1 的充分必要條件是().(A) 對(duì)任意 x， G(x) 都取真值1.(B) 有一個(gè) x0，使 G(x 0)取真值 1.(C)有某些 x，使 G(x 0)取真值 1.(D) 以上答案都不對(duì).13. 設(shè) G 是連通平面圖，有5 個(gè)頂點(diǎn)， 6 個(gè)面，則 G 的邊數(shù)是 ().(A)9 條(B)5 條(C)6 條(D)11 條 .14. 設(shè) G 是 5 個(gè)頂點(diǎn)的完全圖，則從G 中刪去 ()條邊可以得到樹.2 / 8(A)6(B)5(C)10(D)4.0111115. 設(shè)圖 G 的相鄰矩陣為101001101，則 G 的頂點(diǎn)數(shù)與邊數(shù)分別為 ( ).1

8、1010110110(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 的最大元，最小元，極大元，極小元。2.設(shè)集合 A 1, 2, 3, 4 ， A 上的關(guān)系 R(x,y) | x, yA 且 xy, 求(1) 畫出 R 的關(guān)系圖；(2) 寫出 R 的關(guān)系矩陣 .3.設(shè) R 是實(shí)數(shù)集合，, , 是 R 上的三個(gè)映射，(x) = x+3,(x) =

9、 2x,(x) x/4, 試求復(fù)合映射 ?， ?,?,?，?.4.設(shè) I 是如下一個(gè)解釋： 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).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 的上界，下界，最小上界，最大下界.6. 設(shè)命題公式G =(P Q) (Q

10、(P R), 求 G 的主析取范式。7. (9 分)設(shè)一階邏輯公式：G = (xP(x) yQ( y)xR(x)，把 G 化成前束范式.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)系圖 .11. 通過(guò)求主析取范式判斷下列命題公式是否等價(jià)：(1) G = (PQ)(PQR)(2) H = (P (Q R) (Q (P R)13. 設(shè) R 和 S 是集合 A a, b, c, d 上的關(guān)系，其中R

11、( a, a),(a, c),(b, c),(c, d),S ( a, b),(b, c),(b, d),(d, d).(1) 試寫出 R 和 S 的關(guān)系矩陣；3 / 8111(2) 計(jì)算 R?S, RS, R, S?R.四、證明題1. 利用形式演繹法證明： P Q, R S, P R 蘊(yùn)涵 QS。2. 設(shè) A,B 為任意集合，證明：(A-B)-C = A-(B C).3. (本題 10 分 )利用形式演繹法證明：A B,CB, C D 蘊(yùn)涵 A D。4. (本題 10 分 )A, B 為兩個(gè)任意集合，求證：A(A B) = (A B)B .參考答案一、填空題1. 3 。 3,1,3,2,3,

12、1,2,3.2. 2n2 .3.1= ( a,1), ( b,1),2= ( a,2), (b,2),3= ( a,1), (b,2),4= ( a,2), ( b,1) 。3,4.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, xR 。 x | 1 < x < 2, xR 。

13、 x | 0 x 1, 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. D. 6. C. 7. C.8. A. 9. D. 10. B. 11. B.13. A. 14. A.15. D4 / 8三、計(jì)算證明題1.12869(1)4231(2) B 無(wú)上界，也無(wú)

14、最小上界。下界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)142310001100(2) M R111011113. (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.

15、(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 15 / 8= 1.5. (1)812462(2) 無(wú) 最 大(3) B 無(wú)上1元，最小元1，極大元8, 12。 極小元是1.界，無(wú)最小上界。下界1, 2。 最大下界2.6. G =(PQ) (Q (P R)= ( P Q) (Q (P R)= (P Q) (Q(P

16、 R)= (P Q) (QP) (QR)= (P Q R) (P Q R) (P Q R) (PQ R)(P Q R) ( P QR)= (PQ R) (PQR) (P Q R)(P QR) (P Q R)= m 3 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), (

17、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)6 / 811. G (P Q) ( P Q R) (P Q R) (P QR) ( P Q R) m6 m7 m3 (3, 6, 7)H = (P (QR) (Q ( P R) (P Q) (QR) ( P Q R) (P Q R) (P QR) ( P

18、 Q R) (P QR) ( P Q R) (P Q R) ( PQR) (P Q R) m6 m3 m7 (3, 6, 7)G,H 的主析取范式相同，所以G = H.101001000010001113. (1) M R001M S0000000000001(2)R?S ( a, b),(c, d),R S ( a, a),(a, b),(a, c),(b, c),(b, d),(c, d),( d, d),1 ( a, a),(c, a),(c, b),(d, c),R1( b, a),(d, c).S1?R四 證明題1. 證明： PQ, R S, P R 蘊(yùn)涵 Q S(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)(6)(8)Q SQ(7)7 / 82. 證明： (A-