離散生期末題集合論習(xí)題

1、第一章寫出方程 x2 2x 1 0 的根所的集合。下列命題中哪些是真的，哪些為假習(xí)題, An 且 A1 A2 L An A1 ，試證：3 設(shè)有n 個集合 A1, A2 ,LA1 A2 L An4.設(shè) S ,，試求2S ？設(shè) S 恰有 n 個元素，證明 2S 有2n 個元素。設(shè)A、B 是集合，證明:(A B) U B (AU B) B B 設(shè)A、B 是集合，試證 A B AB設(shè)A、B、C 是集合，證明：(AB)C A(BC)設(shè)A、B、C 為集合，證明 A (B UC) (A B) C設(shè)A，B，C 為集合，證明：(AU B) C (A C) U(B C)設(shè) A,B,C 為集合，證明：(AI B)

2、C (A C) I (B C)設(shè)A,B,C 都是集合，若 A U B A UC 且 A I設(shè)A,B,C 為集合，試證：B B IC ，試證 B=C。(A B) C (A B) (C B)設(shè) X Y Z ，證明 Z (Y X ) X U(Z Y )下列命題是否成立？（1） (A B) UC A (B C)AU(B C) (A U B) CA (B UC) (A U B) B16下列命題哪個為真？B B Ia)對任何集合 A,B,C，若 A IC ，則 A=C。設(shè)A,B,C 為任何集合，若 A U B A UC ，則 B=C。對任何集合 A,B， 2AUB 2A U2B 。d)對任何集合 A,B，

3、 2AI B 2A I2B 。對任何集合 A,B， 2AB 2A 2B 。對任何集合A,B， 2AB 2A 2B 。17設(shè) R,S,T 是任何三個集合，試證：（1） ST (S UT )(S I T ) ；（2） R(S I T ) (RS) I (RT ) ；（3） (RS) I (RT ) R(S UT ) (RS) U(RT ) ；（4） R U(ST ) (R US)(R UT )18設(shè) A 為任一集，B I 為任一集族（ I ），證明：A U(I B ) I ( A U B )II19填空：設(shè) A,B 是兩個集合。x A U B ；x A I B ；(c) x A B ；(d) x

4、AB ；20設(shè) A，B，C 為三個集合，下列集合表達(dá)式哪一個等于 A (B I（a） (A B) I (A C) ；（b） (A I B) (A I C)（c） (A B) U(A C) ；（d） (A U B) (A UC)（e） (A U B) I (A UC)C) ？21.設(shè) A,B,C 為集合，并且 A U B A UC ，則下列斷言哪個成立？B A I CB AC I（1） B C（2） A I（4） AC I A IBCCC（3） A IC 22設(shè) A,B,C 為任意集合，化簡( A I B I C) U( AC IB I C) U( A I BC IB I CC ) UC) U(

5、 A IB I CC )( AC I BC I C) U( A I BC I CC ) U( AC I23證明：（1） AB (A U B) I (AC U BC ) ；（2） (AB)C (A I B) U(AC I BC ) ；（3） (AB)C (AC U B) I (A U BC )24設(shè) M1, M2 ,L 和 N1, N2 ,L是集合 S 的子集的兩個序列，對i j,i, j 1, 2,L，有n1Q M ,Q M I ( U M )C , n 2,3,LNi I Nj 。令11nnk。試證：k 1nNn Q)。i125設(shè) X 是一個非空集合， An X , An1 An , n 1

6、, 2,3,L試證： n ，有A U( A) U I AA cInmm1m。mn mn 是任一集合，證明： S,T,W 2V 有 S T W 當(dāng)且僅且 ST SW 且6設(shè) VS W 。27設(shè) A1, A2 ,L為一集序列，記 A 為這樣的元素的全體形成的集合： x A 當(dāng)且僅當(dāng)在序列 A1, A2 ,L中有無窮多項 An 含有 x 。集合 A 稱為集序列 A1, A2 ,L 的上極限，記為lim An Alim AnA , A ,LAn，即 n。又記 為這樣的元素全體形成的集合；序列中只有有限12lim An AA , A ,LA項不含有這樣的元素。稱 為序列的下極限，并記n。證明；12 li

7、m An U I Aklim An I U Ak（1） n2） nn1 k n；（。n1 k nlim An lim Ann28證明： nlim An lim Ann。n29設(shè) A a,b,c, B e, f , g, h,C x, y, z。求 A B, B A, AC, A2 B 。設(shè) A,B 為集合，試證：ABBA 的充要條件是下列三個條件至少一個成立：（1） A ；（2） B ；（3） A B 。設(shè) A,B,C,D 為任四個集合，證明：(AI B)(C I D) (AC) I (B D)設(shè) E1, E2 , E3 , E4 為任意集合，試證：(E1 E2 ) (E3 E4 ) (E1

8、E3 ) E2 ) U(E1 (E2 E4 )設(shè) A X , B Y ，試證： (A B)C (AC B) U( A BC ) U( AC BC )設(shè) A,B,C 為集合，證明：A(BC) (A B)(AC)設(shè) A,B 為集合，下列命題哪些為真？（1） (x, y) A B x A且 y B（2） (x, y) A B x A或 y B（3） 2AB 2A 2B若 AC BC ，則 A B 。若 AC B C,C ，則 A B 。設(shè) A 有 m 個元素，B 有 n 個元素，則 AB 是多少個序?qū)M成的？AB 有多少個不同的子集？設(shè) A,B 為集合， B ，試證：若 ABBB，則 A=B。某班學(xué)

9、生中有 45正在學(xué)德文，65正在學(xué)法文。問此班中至少有百分之幾的學(xué)生正同時學(xué)德文和法文？求 1 到 250 之間不能被 2，3，5，7 中任一數(shù)整除的數(shù)的個數(shù)。AB2240設(shè) A,B 是兩個有限集，試求 ?41 少？寫 n 封信，n 個信封，把 n 封信放入到 n 個信封中，求全部裝錯的概率是多42畢業(yè)舞會上，小伙子與姑娘跳舞，已知每個小伙子至少與一個姑娘跳過舞，但未能與所有姑娘跳過。同樣地，每個姑娘也至少與一個小伙子跳舞，但也未能與所有的小伙子跳過舞。證明：在所有參加舞會的小伙與姑娘中，必可找到兩個小伙子和兩個姑娘，這兩個小伙子中的每一個只與這兩個姑娘中的一個跳過舞，而這兩個姑娘中的每一個也

10、只與這兩個小伙中的一個跳過舞。第二章 習(xí) 題 nA m, B1.設(shè)A，B 是有窮集，AB（1）計算（2）從 A 到A 有多少個雙射？1) X共有( X2.設(shè)X 是一個有窮集合，證明：從 X 到X 的部分個。3.證明：從一個邊長為 1 的等邊三角形中任意選 5 個點，那么這 5 個點中必有 2 個點，它們之間的距離至多為 1/2，而任意 10 個點中必有 2 個點其距離至多是 1/3。4.證明在 52 個整數(shù)中，必有兩個整數(shù)，使這兩個整數(shù)之和或差能被 100 整除。: X Y ， C, D Y ，證明 f 1(C D) f 1(D)5.設(shè) f設(shè) f : X Y, A,B X，證明6.f (AU

11、B) f (A) U f (B)（1）（2） f (AI B) f (A) I f (B)f (A) f (B) f (A B)（3）7.設(shè) : X Y, A X , B Y 。以下四個小題中，每個小題均有四個命題，這四個命f題有且僅有一個正確，請找出正確的那個。f (x) f (A) ，則 x 未必在A 中f (x) f (A) ，則 x Af (x) f (A) ，則 xA（1）（a）若若若f (x) f (A) ，則 x Ac（d）若) B) B) A) A) B) Bc) A（2）（a）（c）（3）（a）（c）（b）（d）（b）（d）上面三個均不對（b） f (B) a） f ( A)

12、 （4）（若 y Y ,則f 1(y) x若 y Y ,則f 1(y) x: X Y, A X , 則( f (A)c f (Ac ) 成立嗎？8.設(shè) f9.設(shè)X 是一個無窮集合， : X Y 。證明：存在X 的一個真子集E 使得f (E) E 。f: A B ，證明T 2B ，都有 f ( f 1(T ) T I f (A)10.設(shè) f11.設(shè) X a,b, c,Y 0,1, Z 2,3, f : X Y, f (a) f (b) 0 ，f (c) 1; g :Y ， g(0) 2, g(1) 3 ，試求 g o f。54 15， 12332412342511 452 , , ,113 ，求

13、12.設(shè)。1 22 112 1 79 82931465678523413.將置換 分解成對換的乘積。14.設(shè) 是任一 n 次置換，試證： 與 1 的奇偶性相同。第三章 習(xí) 題1.給出一個既不是自反的又不是反自反的二元關(guān)系？2.是否存在一個同時不滿足自反性，對稱性稱性，傳遞性和反自反性的二元關(guān)系？3.設(shè)R，S 是X 上的二元關(guān)系，下列命題哪些成立：若 R 與S 是自反的，則 R US, R I S 分別也是自反的。若R 與S 是對稱的，則 R US, R I S 分別對稱的若R 與S 是傳遞的，則 R I S 也是傳遞的若R 與S 不是自反的，則 R U S 也不是自反的若R 與S 是反自反的，

14、則 R US, R I S 也是反自反的若 R 是自反的，則 Rc 也是反自反的。若R 與S 是傳遞的，則 RS 是傳遞的：真真真假真真假4.設(shè)R、S 是X 上的二元關(guān)系。證明：（1） (R1)1 R ；（2） (R US)1 R1 US 1（3） (R I S)1 R1 IS 1 ；（4）若 R S ，則 R1 S 1設(shè)R 是X 上的二元關(guān)系，證明： R U R1 是對稱的二元關(guān)系。有人說：“若 R 是 X 上的二元關(guān)系，只要 R 是對稱的和傳遞的，則 R 必是自反的?！彼淖C明如下：若 xRy，則由 R 的對稱性便知有 yRx。于是由 xRy 和 yRx 以及R 的傳遞性即得 xRx。所以

15、，R 是自反的。他的推論錯在什么地方？這個結(jié)論是否對呢？“父子“關(guān)系的平方是什么關(guān)系？8.設(shè)X=1,2,3,4,R=(1,2),(2,2),(3,4),S=(2,3),(3,1),(4,2)試求： R oS, S oR, R2, S 2, R o(S oR),(R oS) oR 。9.設(shè)R 與S 為X 上的任兩個集合，下列命題哪些為真？a）若R,S 都是自反的，則 R oS 也是自反的。 b）若R,S 都是對稱的，則 R oS 也是對稱的。 c）若R,S 都是反自反的，則 R oS 也是反自反的。d）若R,S 都是稱的，則 R oS 也是稱的。e）若R,S 都是傳遞的，則 R oS 也是傳遞的

16、。10.設(shè)R1 是A 到B，R2 和R3 是B 到C 的二元關(guān)系，則一般情況下R1 o(R2 R3 ) (R1 oR2 ) (R1 oR3 ) 。 但有人聲稱等號成立，他的證明如下：設(shè)(a, c) R1 o(R2 R3 ) ，則b X ，使得(a,b) R1 且(b, c) R2 R3 。于是(b, c) R2 且(b, c) R3 。從而 (a, c) R1 oR2 且(b, c) R1 gR3 ，所以(a, c) (R1 oR2 ) (R1 oR3 ) ，即R1 o( R2 R3 ) (R1o R2 ) (R1o R3 。)同理可證相反的包含關(guān)系成立，故等式成立，這個證明錯在什么地方？設(shè)

17、R，S 是X 上的滿足 R oS S oR 的對稱關(guān)系，證明 R oS S oR .設(shè)R 為X 上的對稱關(guān)系，證明： n N, Rn 是對稱關(guān)系。13.設(shè) R1, R2 , R 3 ,L是 X 上的二元關(guān)系的一個無窮序列，則當(dāng)每個 Ri 是對稱關(guān)系時，URii1還是對稱的嗎？14.設(shè)R 是X 上的二元關(guān)系，試證（1）(R ) R ,(2)(R*)* R*, (3)R oR* R* oR R ,(4)(R )* (R*) R 。15.設(shè)X（a,b,c,d,e），R（a,b），（b,c），（c,d），（d,e）試求 R 和 R 。16.設(shè)R,S 為X 上的二元關(guān)系，試證：（1） (R US) R

18、US （2） (R US) R US舉例說明 s(t(R) 與t(s(R) 確定不相等。是否可以定義二元關(guān)系的反自反閉包與二元關(guān)系的稱閉包？為什么？是否存在 X（X=n）上的一個二元關(guān)系 R 使得 R, R2 ,L , Rn 兩兩不相等。證明：若 R 是對稱的，則 R也是對稱的。設(shè) R1, R2 是X 上的二元關(guān)系，證明：（1） r(R1 U R2 ) r(R1) Ur(R2 )（2） S(R1 U R2 ) s(R1) Us(R2 )（3） t(R1 U R2 ) t(R1) Ut(R2 ) 18 確定了2635456277 34X 1, 2L,81, 822. 由置換: i, j X ,i 上的一個關(guān)系j 當(dāng)且僅當(dāng) i 與 j 在 的循環(huán)分解式中的同一循環(huán)置換中，證明： 是 X 上的等價關(guān)系，求 X / 。23.給出 X1，2，3，4上兩個等價關(guān)系 R 與S，使得 R oS 不是等價關(guān)系。24.設(shè)X 是一個集合， n ，試求：X（1）X 上自反二元關(guān)系的個數(shù)；（2）X 上反自反二元關(guān)系的個