1、一、填空題1設集合 A,B，其中 A 1,2,3, B= 1,2,則 A-B 3;(A) -(B)3,1,3,2,3,1,2,3.2.設有限集合 A, |A| = n,則 |(A×A)| =2n 2.3.設集合 A= ,b, B = 1, 2,則從 A 到 B 的所有映射是1= (,1), (,1),2=aab(a,2), (b,2),3= (,1), (,2),4= (,2), (,1),其中雙射的是3,abab4 .4.已知命題公式 G (PQ) R，則 G的主析取范式是(P Q R)5. 設 G是完全二叉樹， G有 7 個點，其中 4 個葉點，則 G的總度數為12，分枝點數為3

2、.6 設 A、B 為兩個集合 , A= 1,2,4,B = 3,4,則從 AB 4; AB1,2,3,4 ;A B 1,2.7. 設 R是集合 A上的等價關系，則R 所具有的關系的三個特性是自反性 ,對稱性傳遞性 .8.設命題公式 G(P (Q R) ，則使公式 G為真的解釋有(1, 0, 0),(1, 0, 1),(1, 1, 0)9.設集合 A 1,2,3,4,A上的關系12R = (1,4),(2,3),(3,2),R = (2,1),(3,2),(4,3),則 R1 R2=(1,3),(2,2),(3,1), R2R1=(2,4),(3,3),(4,2) _12=(2,2),(3,3)

3、.R10.設有限集 A, B ， |A| = m, |B| = n,則 | |(AB)| =2m n.11設 A,B,R 是三個集合，其中 R 是實數集， A = x | -1 x1, xR, B = x | 0 x <2, xR, 則 A-B =-1<=x<0, B-A =x | 1 < x < 2, xR,A B = x | 0 x 1, xR, .13. 設集合 A 2, 3, 4, 5, 6，R 是 A 上的整除關系，則 R 以集合形式 ( 列舉法 ) 記為(2, 2),(2, 4),(2, 6),(3, 3),(3, 6),(4, 4),(5, 5),(

4、6, 6).14.設一階邏輯公式G =xP(x)xQ(x) ，則 G的前束范式是x(P(x) Q(x).15. 設 G是具有8 個頂點的樹，則G中增加 21條邊才能把 G變成完全圖。 ( 完全圖的邊數 n(n 1)，樹的邊數為 n-1)216.設謂詞的定義域為 a, b, 將表達式xR(x) xS(x) 中量詞消除，寫成與之對應的命題公式是 _(R(a) R(b) (S(a) S(b)_.17.設集合 A 1, 2, 3, 4， A 上的二元關系R (1,1),(1,2),(2,3), S(1,3),(2,3),(3,2)。則 RS(1, 3),(2, 2),R2 (1, 1),(1, 2),

5、(1, 3).二、選擇題1設集合 A=2,a,3,4， B = a,3,4,1， E 為全集，則下列命題正確的是 ( C ) 。(A)2A(B)aA(C)aB E(D)a,1,3,4B.2設集合 A=1,2,3,A上的關系R (1,1),(2,2),(2,3),(3,2),(3,3)，則 R 不具備(D).(A) 自反性(B) 傳遞性(C) 對稱性(D) 反對稱性3 設半序集 (A, ) 關系的哈斯圖如下所示，若 A 的子集 B = 2,3,4,5, (B) 。(A) 下界(B) 上界(C) 最小上界(D)以上答案都不對4 下列語句中， ( B ) 是命題。(A) 請把門關上(B)地球外的星球

6、上也有人(C)x + 5 > 6(D)下午有會嗎？P(a, a) P(a,b) P(b,a) P(b, b)5 設 I 是如下一個解釋：D a,b,則元素 6為 B的653 4211010則在解釋 I 下取真值為1的公式是 ( D ).(A) x yP(x,y) (B)x yP(x,y)(C)xP(x,x)(D)x yP(x,y).6.若供選擇答案中的數值表示一個簡單圖中各個頂點的度，能畫出圖的是(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.設 G、H 是一階邏輯公式， P 是一個謂詞， G

7、xP(x), HxP(x), 則一階邏輯公式 G H是( C).(A) 恒真的(B)恒假的(C)可滿足的(D)前束范式 .8 設命題公式G(PQ)， H P(QP) ，則 G與 H的關系是 ( A )。(A)GH(B)HG(C)G H(D)以上都不是 .9設 A,B為集合，當 (D )時 AB B.(A)A B(B)AB(C)BA(D)A B .10設集合 A = 1,2,3,4, A上的關系 R (1,1),(2,3),(2,4),(3,4),則 R具有( B)。(A) 自反性(B) 傳遞性(C) 對稱性(D)以上答案都不對11下列關于集合的表示中正確的為( B)。(A)aa,b,c (B)

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

9、別為 ( D ).111010110110(A)4, 5(B)5, 6(C)4, 10(D)5, 8.三、計算證明題1. 設集合A1, 2, 3, 4, 6, 8, 9, 12， R 為整除關系。(1) 畫出半序集 (A,R) 的哈斯圖；(2) 寫出 A 的子集 B = 3,6,9,12的上界，下界，最小上界，最大下界；(3) 寫出 A 的最大元，最小元，極大元，極小元。解：（ 1）128694231（ 2） B 無上界，也無最小上界。下界1, 3; 最大下界是 3（ 3） A 無最大元，最小元是1，極大元 8, 12, 9;極小元是 12. 設集合 A 1, 2, 3, 4， A 上的關系

10、R (x,y) | x, yA 且 xy, 求(1)畫出 R的關系圖；(2)寫出 R的關系矩陣 .141000231100解：（ 1）（2） MR110111113.設 R 是實數集合，,試求復合映射?，解：,是 R 上的三個映射，?,?,?，(x) = x+3, ? ? .(x)= 2x,(x)x/4,(1) ? ( (x) (x)+3 2x+3 2x+3.(2)?(x)(x)+3(x+3)+3 x+6,(3)?(x)(x)+3x/4+3,(4)?(x)(x)/42x/4 = x/2,(5)? ?(? ) ? +3 2x/4+3 x/2+3.4.設 I 是如下一個解釋： D = 2, 3,a

11、bf (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)xy P ( y,x).解：(1) P( a, f ( a)P( b,f ( b) =P(3,f (3) P(2,f (2)=(3, 2) (2,3)PP= 1 0= 0.(2)xy 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.設集合 A1, 2, 4, 6, 8, 12， R為 A 上整除關系。(1)

12、 畫出半序集 (A,R) 的哈斯圖；(2) 寫出 A 的最大元，最小元，極大元，極小元；(3) 寫出 A 的子集 B = 4, 6, 8, 12的上界，下界，最小上界，最大下界.解： (1)(2)無最大元，最小元 1，極大元 8, 12;極小元是 1.(3)B 無上界，無最小上界。下界1, 2;最大下界 2.6. 設命題公式G =(P Q) (Q(P R),求 G的主析取范式。解：G =(P Q) (Q (PR)= ( P Q)(Q (P R)= (P Q) (Q (P R)= (P Q) (Q P) (Q R)= (P QR)(P Q R)(PQR)(P Q R)(PQR)( PQR)= (

13、PQ R) (P QR) (P Q R) (P QR) (P QR)= m3 m4m5 m6 m7 =(3, 4, 5, 6, 7).7. (9 分) 設一階邏輯公式：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) yQ( y)zR( z)=xyz(P( x) Q( y)R( z)9. 設 R 是集合 A = a, b,c, d. R是 A 上的二元關系 , R = (a,b), (b,a), (b,c), (c,

14、d),(1)求出 r(R), s(R), t(R)；(2)畫出 r(R), s(R), t(R)的關系圖 .解：（ 1）r(R) R I A (a,b), (b,a), (b,c), (c,d), (a,a), (b,b), (c,c), (d,d),s(R) R R1 (a,b), (b,a), (b,c), (c,b) (c,d), (d,c),t(R) R R2 R3R4 (a,a),(a,b), (a,c),(a,d),(b,a) , (b,b),(b,c), (b,d),(c,d) ；(2) 關系圖 :adadadbcbcbcr(R)s(R)t(R)11. 通過求主析取范式判斷下列命

15、題公式是否等價：(1) G = (P Q) (PQ R)(2) H = (P (Q R) (Q (P R)解：G(PQ) (PQR) (P Q R) (P QR) ( P Q R) m6 m7 m3 (3, 6, 7)H = (P (Q R) (Q(PR) (P Q) (QR) ( P Q R) (P Q R) (P QR) ( P Q R) (P QR) ( P Q R) (P QR) (P Q R) (P Q R) m6 m3 m7G,H 的主析取范式相同，所以G = H.13.設 R和 S 是集合 A a, b, c, d 上的關系，其中R ( a, a),( a, c),( b, c)

16、,( c, d),S ( a,b),( b, c),( b, d),( d, d).(1) 試寫出 R和 S 的關系矩陣；(2) 計算 R?S, R S, R1, S1?R1.解：10100100(1) MR0010M S00110001000000000001(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, RS, P R 蘊涵 Q S。解：(1)

17、RPP(2)R PQ(1)(3)PQP(4)R QQ(2)(3)(5)Q RQ(4)(6)RSP(7)Q SQ(5)(6)(8) Q SQ(7)2. 設A,B為任意集合，證明：(A-B)-C = A-(B C).解：(A-B)-C =( AB)CA(BC)A (B C) A(BC)3. ( 本題 10 分 ) 利用形式演繹法證明：AB,CB, C D蘊涵 A D。解：(1)AD(附加 )(2)A BP(3)BQ(1)(2)(4)C BP(5)B CQ(4)(6)CQ(3)(5)(7)C DP(8)DQ(6)(7)(9)A DD(1)(8)所以 A B,C B, C D蘊涵 A D.4. ( 本

18、題 10 分)A, B為兩個任意集合，求證：A(AB) = (AB)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(AB) = (AB)B.參考答案一、填空題1. 3; 3,1,3,2,3,1,2,3.22.2n .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

19、, 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).m n10. 2 .11. x | -1 x < 0, xR; x | 1 < x < 2, xR; 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).

20、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.128(1)694231(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)142310001100

21、(2) MR110111113. (1)? (x) (x)+3 2x+3 2x+3.(2)?(x)(x)+3(x+3)+3 x+6,(3)?(x)(x)+3x/4+3,(4)?(x)(x)/42x/4 = x/2,(5)?(?) ?+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

22、 1= 1.5.(1)812462(2)無 最 大元，最小元1，極大元 8, 12;極小元是 1.(3) B無上1界，無最小上界。下界 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 QR)(P Q R)(PQR)(P Q R)(PQR)( PQR)= (P Q R) (P QR) (P Q R) (P QR) (P QR)= m3 mm m m =(3, 4, 5, 6, 7).45677.=() ()()GxP xyQ yxR x=(xP( x) yQ( y) xR( x)= (xP( x) yQ( y) xR( x)= (x P( x) y Q( y) zR( z)=xy z(P( x) Q( y) R( z)9. (1) r(R) R I A(a,b), (b,a), (b,c), (c,d), (a,a), (b,b), (c,c), (d,d),s(R) R R1 (a,b), (b,a), (b,c), (c,b) (c,d), (d,c),234t(R) R R R R (a,a),(a,b),(a,c),(a,d),(b,a),(b,b),(b,c),(b,d),(c,d)；(2) 關系圖 :adadadbcbcbcr(R)s(R)t(R