電大《離散數(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=(PQR,則G的主析取范式是_ _.5.設(shè)G是完全二叉樹,G有7個點,其中4個葉點,則G的總度數(shù)為_,分枝點數(shù)為_.6設(shè)A、B為兩個集合, A= 1,2,4, B = 3,4, 則從AB=_; AB=_;A-B=_ .7. 設(shè)R是集合A上的等價關(guān)系,則R所具有的關(guān)系的三個特性是_

2、, _, _.8. 設(shè)命題公式G=(P(QR,則使公式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, 則R1R2 = _,R2R1 =_,R12 =_.10. 設(shè)有限集A, B,|A| = m, |B| = n, 則| |(AB| = _.11設(shè)A,B,R是三個集合,其中R是實數(shù)集,A = x | -1x1, xR, B = x | 0x < 2, xR,則A-B = _ , B-A = _ ,AB = _ , .13.設(shè)集合A=2, 3, 4, 5, 6,R是A上的整除,則R以

3、集合形式(列舉法記為_ _.14. 設(shè)一階邏輯公式G = xP(xxQ(x,則G的前束范式是_ _.15.設(shè)G是具有8個頂點的樹,則G中增加_條邊才能把G變成完全圖。16. 設(shè)謂詞的定義域為a, b,將表達(dá)式xR(xxS(x中量詞消除,寫成與之對應(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。則RS=_,R2=_.二、選擇題1設(shè)集合A=2,a,3,4,B = a,3,4,1,E為全集,則下列命題正確的是( 。(A2A (BaA (CaBE (Da,1,3,4B.2設(shè)集合A=1,2,3,A上的關(guān)系R=(

4、1,1,(2,2,(2,3,(3,2,(3,3,則R不具備( .(A自反性(B傳遞性(C對稱性(D反對稱性3 設(shè)半序集(A,關(guān)系的哈斯圖如下所示,若A的子集B = 2,3,4,5,則元素6為B的( 。(A下界(B上界(C最小上界(D以上答案都不對4下列語句中,( 是命題。(A請把門關(guān)上(B地球外的星球上也有人(Cx + 5 > 6 (D下午有會嗎?5設(shè)I是如下一個解釋:D=a,b,11bP(b,aP(b,bP(a,(aaP則在解釋I下取真值為1的公式是( .(AxyP(x,y (BxyP(x,y (CxP(x,x (DxyP(x,y.6. 若供選擇答案中的數(shù)值表示一個簡單圖中各個頂點的度

5、,能畫出圖的是( .(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,則一階邏輯公式GH 是( .(A恒真的(B恒假的(C可滿足的(D前束范式.8設(shè)命題公式G=(PQ,H=P(QP,則G與H的關(guān)系是( 。(AGH (BHG (CG=H (D以上都不是.9設(shè)A, B為集合,當(dāng)( 時A-B=B.(AA=B (BAB (CBA (DA=B=.10 設(shè)集合A = 1,2,3,4, A上的關(guān)系R=(1,1,(2,3,(2,4,(3,4, 則R具有( 。(A自反性(B

6、傳遞性(C對稱性(D以上答案都不對11下列關(guān)于集合的表示中正確的為( 。(Aaa,b,c (Baa,b,c (Ca,b,c (Da,ba,b,c12命題xG(x取真值1的充分必要條件是( .(A對任意x,G(x都取真值1. (B有一個x0,使G(x0取真值1.(C有某些x,使G(x0取真值1. (D以上答案都不對.13. 設(shè)G是連通平面圖,有5個頂點,6個面,則G的邊數(shù)是( .(A 9條(B 5條(C 6條(D 11條.14. 設(shè)G是5個頂點的完全圖,則從G中刪去( 條邊可以得到樹.(A6 (B5 (C10 (D4. 15. 設(shè)圖G 的相鄰矩陣為011011010111011001011111

7、0,則G 的頂點數(shù)與邊數(shù)分別為( .(A4, 5 (B5, 6 (C4, 10 (D5, 8.三、計算證明題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, y A 且 x y, 求(1 畫出R 的關(guān)系圖; (2 寫出R 的關(guān)系矩陣.3. 設(shè)R 是實數(shù)集合,是R 上的三個映射,(x = x+3, (x = 2x, (x = x/

8、4,試求復(fù)合映射, , ,. 4. 設(shè)I 是如下一個解釋:D = 2, 3,a b f (2 f (3 P (2, 2 P (2, 3 P (3, 2 P (3, 3 323211試求 (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 (P R, 求G 的主析取范式。7. (9

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. 通過求主析取范式判斷下列命題公式是否等價:(1 G = (P Q(P Q R(2 H = (P (Q R(Q (P R13. 設(shè)R 和S 是集合A =a , b , c , d 上的關(guān)系,其中R =(a , a ,(a , c ,(b , c ,(c , d ,S =(a , b ,(b

10、 , c ,(b , d ,(d , d . (1 試寫出R 和S 的關(guān)系矩陣; (2 計算R S , R S , R -1, S -1R -1.四、證明題1. 利用形式演繹法證明:PQ, RS, PR蘊(yùn)涵QS。2. 設(shè)A,B為任意集合,證明:(A-B-C = A-(BC.3. (本題10分利用形式演繹法證明:AB, CB, CD蘊(yùn)涵AD。4. (本題10分A, B為兩個任意集合,求證:A-(AB = (AB-B .參考答案一、填空題1. 3; 3,1,3,2,3,1,2,3.2n.2.23.1= (a,1, (b,1, 2= (a,2, (b,2,3= (a,1, (b,2, 4= (a,2

11、, (b,1; 3, 4.4.(PQR.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.2mn.11.x | -1x < 0, xR; x | 1 < x < 2, xR; x | 0x1, xR.12.12; 6.13.(2, 2,(2, 4,(2, 6,(3, 3,(3, 6,(4, 4,(5, 5,(6, 6.14.x(P(xQ(x.15.21.16.(R(aR(b(S(aS(

12、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三、計算證明題 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 (21000110011101111R M =3. (1=(x=(x+3=2

13、x+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. (1 P (a , f (a P (b , f (b = P (3, f (3P (2, f (2 = P (3, 2P (2, 3 = 10= 0.(2 x y P (y , x = x (P (2, x P (3, x = (P (2, 2P (3, 2(P (2, 3P (3, 3 = (01 = 1= 1.5. (1(2 無最大元，最小元 1，極大元 8, 12; 極小元是 1. (3 B 無上

14、界，無最小上界。下界 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(xyQ(yxR(x = ¬(xP(xyQ(yxR(x = (&#

15、172;xP(x¬yQ(yxR(x = (x¬P(xy¬Q(yzR(z = xyz(¬P(x¬Q(yR(z 9. (1 r(RRIA(a,b, (b,a, (b,c, (c,d, (a,a, (b,b, (c,c, (d,d, s(RRR 1(a,b, (b,a, (b,c, (c,b (c,d, (d,c, t(RRR2R3R4(a,a, (a,b, (a,c, (a,d, (b,a, (b,b, (b,c, (b,d, (c,d； (2關(guān)系圖: a b r(R d a b d a b t(R d c c s(R c 11. G(PQ(

16、72;PQR (PQ¬R(PQR(¬PQR m6m7m3 6 (3, 6, 7 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. 1 0 (1 M R = 0 0 0 1 0 0 1 0 0 0 1 0 0 0 0 0 MS = 0 0 1 0 0 0 1 1 0 0 0 0 0 1 (2RS(a, b,(c, d, RS(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 1R 1(b, a,(d, c. 四 證明題 1. 證明：PQ, RS, PR蘊(yùn)涵 QS (1 PR (2 ¬RP (3 PQ (4 ¬RQ (5 ¬QR (6 RS (7 ¬QS (8 QS P Q(1 P Q(2(3 Q(4 P Q(5(6 Q(7 2. 證明：(A-B-C = (ABC = A(BC = A(BC = A-(BC 7 3. 證明：¬