離散數(shù)學(xué)第五章集合及其運算習(xí)題答案PPT

1、習(xí)題四1.設(shè)設(shè)A=1,2,3,4,B=0,1,4,9,12.分別把下面定義的從集合分別把下面定義的從集合A到集到集合合B的二元關(guān)系的二元關(guān)系R用序偶的集合表示出來。用序偶的集合表示出來。(1) xRy x|y(1,0) ,(1,1),(1,4) ,(1,9) ,(1,12) ,(2,0) ,(2,4) ,(2,12) , (3,0) ,(3,9) ,(3,12) ,(4,0) ,(4,4) ,(4,12)(2) xRy x y(mod 3)(1,1), (1,4) , (3,0) , (3,9) , (3,12) , (4,1) , (4,4)(3) xRy y/x (y-x)/2(3,9),

2、 (3,12) , (4,9) , (4,12)4.設(shè)設(shè)A是含是含n個元素的集合，請問在個元素的集合，請問在A上可以定義出多少個二元上可以定義出多少個二元關(guān)系？關(guān)系？ 解解: 因為因為R是是A上的二元關(guān)系上的二元關(guān)系, R A A,于是于是R 2A A, 所以共所以共2n2個個二元關(guān)系二元關(guān)系.習(xí)題四 6設(shè)在整數(shù)集合上定義了如下關(guān)系：確定其滿足的性質(zhì)設(shè)在整數(shù)集合上定義了如下關(guān)系：確定其滿足的性質(zhì)自反性自反性反自反反自反性性對稱性對稱性反對稱反對稱性性傳遞性傳遞性xRy x | y 習(xí)題四 6設(shè)在整數(shù)集合上定義了如下關(guān)系：確定其滿足的性質(zhì)設(shè)在整數(shù)集合上定義了如下關(guān)系：確定其滿足的性質(zhì)自反性自反性

3、反自反反自反性性對稱性對稱性反對稱反對稱性性傳遞性傳遞性xRy x | y xRy xy(mod n) 習(xí)題四 6設(shè)在整數(shù)集合上定義了如下關(guān)系：確定其滿足的性質(zhì)設(shè)在整數(shù)集合上定義了如下關(guān)系：確定其滿足的性質(zhì)自反性自反性反自反反自反性性對稱性對稱性反對稱反對稱性性傳遞性傳遞性xRy x | y xRy xy(mod n) xRy xy0 習(xí)題四 6設(shè)在整數(shù)集合上定義了如下關(guān)系：確定其滿足的性質(zhì)設(shè)在整數(shù)集合上定義了如下關(guān)系：確定其滿足的性質(zhì)自反性自反性反自反反自反性性對稱性對稱性反對稱反對稱性性傳遞性傳遞性xRy x | y xRy xy(mod n) xRy xy0 xRy xy0 習(xí)題四 6設(shè)

4、在整數(shù)集合上定義了如下關(guān)系：確定其滿足的性質(zhì)設(shè)在整數(shù)集合上定義了如下關(guān)系：確定其滿足的性質(zhì)自反性自反性反自反反自反性性對稱性對稱性反對稱反對稱性性傳遞性傳遞性xRy x | y xRy xy(mod n) xRy xy0 xRy xy0 xRy x=y | |x-y|=1 習(xí)題四 6設(shè)在整數(shù)集合上定義了如下關(guān)系：確定其滿足的性質(zhì)設(shè)在整數(shù)集合上定義了如下關(guān)系：確定其滿足的性質(zhì)自反性自反性反自反反自反性性對稱性對稱性反對稱反對稱性性傳遞性傳遞性xRy x | y xRy xy(mod n) xRy xy0 xRy xy0 xRy x=y | |x-y|=1 xRy x2y2 習(xí)題四 7設(shè)設(shè)R是集合

5、上的一個二元關(guān)系，是集合上的一個二元關(guān)系， xRy yRz xRz ,稱稱R是是A上的上的一個反傳遞關(guān)系。試舉一個實際的反傳遞關(guān)系的例子。一個反傳遞關(guān)系。試舉一個實際的反傳遞關(guān)系的例子。解：解：例如：設(shè)例如：設(shè)A=a, b, c, d 則則 R1=(a, b), (b, d), (d, c) 反傳遞反傳遞 R2=(a, b), (a, c), (d, b) 反傳遞、傳遞反傳遞、傳遞 R3 =(a, a), (a, b), (b, c) 不是反傳遞不是反傳遞 R4 =(a, a), (b, c) 不是反傳遞不是反傳遞傳遞和反傳遞不是絕對互相排斥傳遞和反傳遞不是絕對互相排斥實際中，如實際中，如“父

6、子關(guān)系父子關(guān)系”， “X=Y+1”關(guān)系等。關(guān)系等。習(xí)題四 9判定滿足下述每一種條件的關(guān)系是否存在，如果存在，舉例判定滿足下述每一種條件的關(guān)系是否存在，如果存在，舉例說明。說明。（1）既自反又反自反。）既自反又反自反。答：不存在答：不存在（2）既對稱又反對稱。）既對稱又反對稱。答：存在，例如答：存在，例如IA（3）既傳遞又反傳遞。）既傳遞又反傳遞。答：存在答：存在（4）既自反、反對稱、又傳遞。）既自反、反對稱、又傳遞。答：存在，例如正整數(shù)集合上的整除關(guān)系。答：存在，例如正整數(shù)集合上的整除關(guān)系。習(xí)題四 8 自反性自反性 反自反性反自反性 對稱性對稱性 反對稱性反對稱性 傳遞性傳遞性R S 設(shè)設(shè)R和

7、和S都是集合都是集合A上的二元關(guān)系，它們經(jīng)過關(guān)系運算后得到上的二元關(guān)系，它們經(jīng)過關(guān)系運算后得到A上的一個上的一個新關(guān)系。判別當(dāng)新關(guān)系。判別當(dāng)R和和S 同時具有表中某種指定性質(zhì)時，經(jīng)過指定的運算同時具有表中某種指定性質(zhì)時，經(jīng)過指定的運算后所得新關(guān)系是否也仍保持這種性質(zhì)：后所得新關(guān)系是否也仍保持這種性質(zhì)：(a,b) R S(a,b) R (a,b) S (b,a) R (b,a) S(b,a) R S或者由或者由R S= (R S)-1得證得證(a,b) R S(a,b) R (a,b) S (b,a) R (b,a) S(b,a) R S或者由或者由(R S) (R S)-1 IA得證得證 自反

8、性自反性 反自反性反自反性 對稱性對稱性 反對稱性反對稱性 傳遞性傳遞性R S (a,b) R S (b,c) R S (a,b) R (a,b) S (b,c) R (b,c) S (a,c) R (a,c) S(a,c) R S習(xí)題四 8設(shè)設(shè)R和和S都是集合都是集合A上的二元關(guān)系，它們經(jīng)過關(guān)系運算后得到上的二元關(guān)系，它們經(jīng)過關(guān)系運算后得到A上的一個上的一個新關(guān)系。判別當(dāng)新關(guān)系。判別當(dāng)R和和S 同時具有表中某種指定性質(zhì)時，經(jīng)過指定的運算同時具有表中某種指定性質(zhì)時，經(jīng)過指定的運算后所得新關(guān)系是否也仍保持這種性質(zhì)：后所得新關(guān)系是否也仍保持這種性質(zhì)： 自反性自反性 反自反性反自反性 對稱性對稱性

9、反對稱性反對稱性 傳遞性傳遞性R S R S 例如例如A=0, 1R=(0,1), S=(1,0)R S =(0,1), (1,0)例如例如A=0, 1R=(0,1), S=(1,0)R S =(0,1), (1,0)習(xí)題四 8設(shè)設(shè)R和和S都是集合都是集合A上的二元關(guān)系，它們經(jīng)過關(guān)系運算后得到上的二元關(guān)系，它們經(jīng)過關(guān)系運算后得到A上的一個上的一個新關(guān)系。判別當(dāng)新關(guān)系。判別當(dāng)R和和S 同時具有表中某種指定性質(zhì)時，經(jīng)過指定的運算同時具有表中某種指定性質(zhì)時，經(jīng)過指定的運算后所得新關(guān)系是否也仍保持這種性質(zhì)：后所得新關(guān)系是否也仍保持這種性質(zhì)： 自反性自反性 反自反性反自反性 對稱性對稱性 反對稱性反對稱

10、性 傳遞性傳遞性R S R S R-S 例如例如A=0, 1R=(0,1), (1,2), (0,2), S=(0,2)R-S =(0,1), (1,2)習(xí)題四 8設(shè)設(shè)R和和S都是集合都是集合A上的二元關(guān)系，它們經(jīng)過關(guān)系運算后得到上的二元關(guān)系，它們經(jīng)過關(guān)系運算后得到A上的一個上的一個新關(guān)系。判別當(dāng)新關(guān)系。判別當(dāng)R和和S 同時具有表中某種指定性質(zhì)時，經(jīng)過指定的運算同時具有表中某種指定性質(zhì)時，經(jīng)過指定的運算后所得新關(guān)系是否也仍保持這種性質(zhì)：后所得新關(guān)系是否也仍保持這種性質(zhì)： 自反性自反性 反自反性反自反性 對稱性對稱性 反對稱性反對稱性 傳遞性傳遞性R S R S R-S RS 例如例如A=0,

11、1R=(0,1), S=(1,0)RS =(0,0)例如例如A=0, 1R=(0,0), S=(0,1), (1,0)RS =(0,1)習(xí)題四 8設(shè)設(shè)R和和S都是集合都是集合A上的二元關(guān)系，它們經(jīng)過關(guān)系運算后得到上的二元關(guān)系，它們經(jīng)過關(guān)系運算后得到A上的一個上的一個新關(guān)系。判別當(dāng)新關(guān)系。判別當(dāng)R和和S 同時具有表中某種指定性質(zhì)時，經(jīng)過指定的運算同時具有表中某種指定性質(zhì)時，經(jīng)過指定的運算后所得新關(guān)系是否也仍保持這種性質(zhì)：后所得新關(guān)系是否也仍保持這種性質(zhì)： 自反性自反性 反自反性反自反性 對稱性對稱性 反對稱性反對稱性 傳遞性傳遞性R S R S R-S RS 例如例如A=0, 1R=(0,1),

12、 (1,1)S=(1,0), (1,1)RS =(0,0),(0,1), (1,0), (1,1)例如例如A=0, 1, 2, 3, 4R=(0,1), (2,3)S=(1,2), (3,4)RS =(0,2),(2,4)習(xí)題四 8設(shè)設(shè)R和和S都是集合都是集合A上的二元關(guān)系，它們經(jīng)過關(guān)系運算后得到上的二元關(guān)系，它們經(jīng)過關(guān)系運算后得到A上的一個上的一個新關(guān)系。判別當(dāng)新關(guān)系。判別當(dāng)R和和S 同時具有表中某種指定性質(zhì)時，經(jīng)過指定的運算同時具有表中某種指定性質(zhì)時，經(jīng)過指定的運算后所得新關(guān)系是否也仍保持這種性質(zhì)：后所得新關(guān)系是否也仍保持這種性質(zhì)： 自反性自反性 反自反性反自反性 對稱性對稱性 反對稱性反

13、對稱性 傳遞性傳遞性R S R S R-S RS R 習(xí)題四 8設(shè)設(shè)R和和S都是集合都是集合A上的二元關(guān)系，它們經(jīng)過關(guān)系運算后得到上的二元關(guān)系，它們經(jīng)過關(guān)系運算后得到A上的一個上的一個新關(guān)系。判別當(dāng)新關(guān)系。判別當(dāng)R和和S 同時具有表中某種指定性質(zhì)時，經(jīng)過指定的運算同時具有表中某種指定性質(zhì)時，經(jīng)過指定的運算后所得新關(guān)系是否也仍保持這種性質(zhì)：后所得新關(guān)系是否也仍保持這種性質(zhì)：例如例如A=a, b,c若若R= (a,a),(b,c) 自反性自反性 反自反性反自反性 對稱性對稱性 反對稱性反對稱性 傳遞性傳遞性R S R S R-S RS R R-1 習(xí)題四 8設(shè)設(shè)R和和S都是集合都是集合A上的二元關(guān)

14、系，它們經(jīng)過關(guān)系運算后得到上的二元關(guān)系，它們經(jīng)過關(guān)系運算后得到A上的一個上的一個新關(guān)系。判別當(dāng)新關(guān)系。判別當(dāng)R和和S 同時具有表中某種指定性質(zhì)時，經(jīng)過指定的運算同時具有表中某種指定性質(zhì)時，經(jīng)過指定的運算后所得新關(guān)系是否也仍保持這種性質(zhì)：后所得新關(guān)系是否也仍保持這種性質(zhì)：設(shè)設(shè)R是集合是集合A上的一個二元關(guān)系。證明：上的一個二元關(guān)系。證明：（1）R是自反的是自反的 IA R證明：當(dāng)證明：當(dāng)R是自反時，任取是自反時，任取(x,x) IA,必有必有(x,x) R IA R當(dāng)當(dāng)IA R時，時，R= IA R，故，故R含有所有含有所有(x,x) 序偶，故自反。序偶，故自反。（2） R是反自反的是反自反的

15、R IA= 證明證明: 當(dāng)當(dāng)R是反自反的，任何是反自反的，任何(x, y) R, 必有必有xy, 故R IA= ;當(dāng)當(dāng)R IA= 時時, R中無中無(x, x)序偶，序偶，故故反自反。反自反。（3）R是對稱的是對稱的R = R-1證明證明: 當(dāng)當(dāng)R是對稱的，任是對稱的，任(x, y) R, 必有必有(y, x) R，即，即(y, x) R-1 ，必有，必有(x, y) R-1, 故故R = R-1當(dāng)當(dāng)R = R-1的，的， R=R R-1 ，則對任何，則對任何(x, y) R, 必有必有(y, x) R-1 R ，故故R對稱對稱習(xí)題四 10設(shè)設(shè)R是集合是集合A上的一個二元關(guān)系。證明：上的一個二

16、元關(guān)系。證明：（4） R是反對稱的是反對稱的R R-1 IA證明：當(dāng)證明：當(dāng)R是反對稱時，任取是反對稱時，任取(x, y) R R-1 ，則，則(x, y) R (x, y) R-1 (x, y) R (y, x) R x=y，所以，所以R R-1 IA當(dāng)當(dāng)R R-1 IA時，如果時，如果 x y,則則(x, y) R (x, y) R-1 ，即，即(x, y) R (y, x) R R是反對稱的。是反對稱的。（5） R是傳遞的是傳遞的 R2 R證明證明: 當(dāng)當(dāng)R是傳遞的，取是傳遞的，取(x, z) R2, 即即( y)(x, y) R (y, z) R ，于是，于是(x, z) R R2 R

17、當(dāng)當(dāng)R2 R時時, 任取任取(x, y), (y, z) R, 則則(x, z) R2 R，故，故R傳遞。傳遞。 習(xí)題四 10 設(shè)設(shè) A=a,b,c,d,e,f,g,h, A上的二元關(guān)系上的二元關(guān)系R對應(yīng)的關(guān)系圖如圖，求對應(yīng)的關(guān)系圖如圖，求使使Rm= Rn的最小正整數(shù)的最小正整數(shù)m和和n (m0。證明。證明S是是C1上上的一個等價關(guān)系，并給出的一個等價關(guān)系，并給出S的等價類的幾何說明。的等價類的幾何說明。證明證明: 因為因為(a+bi)S(c+di) ac0 (a,b R,a 0, c 0)r: a 0, a20 (a+bi)S (a+bi) s: (a+bi)S(c+di) ac0 ca0

18、(c+di)S (a+bi)t: (a+bi)S(c+di) (c+di)S(u+vi) ac0 cu0 au0 (a+bi)S(u+vi) 綜上，綜上，S是是C1上的一個等價關(guān)系。上的一個等價關(guān)系。由于由于ac0，必須，必須a 0, c0且a和和c同號，故同號，故S只有只有2個等價類，個等價類，其一是其一是1=a+bi | a0，另一個是，另一個是-1=a+bi | a0，它們，它們分別對應(yīng)于復(fù)平面上右半部和左半部。分別對應(yīng)于復(fù)平面上右半部和左半部。習(xí)題五 4. 試確定在試確定在4個元素的集合上可以定義出的等價關(guān)系數(shù)目。個元素的集合上可以定義出的等價關(guān)系數(shù)目。解：解：A=a,b,c,d可產(chǎn)生

19、的分劃如下：可產(chǎn)生的分劃如下：含一個等價類含一個等價類 S1=a,b,c,d含二個等價類含二個等價類1-3型型: S2=a,b,c,d, S3=b,a,c,d , S4=c,a,b,d S5=d,a,b,c2-2型型: S6=a,b,c,d, S7=a,c,b,d, S8=a,d,b,c 含三個等價類含三個等價類, 1-1-2型型:S9=a,b,c,d, S10=a,c,b,d, S11=a,d,b,c, S12=b,c,a,d, S13=b,d,a,c, S14=c,d,a,b,含四個等價類含四個等價類: S15=a,b,c,d 所以共個所以共個習(xí)題五 7. 設(shè)設(shè)Mn是全體是全體n階矩陣的集

20、合階矩陣的集合.如果對矩陣如果對矩陣A,B M,存在可逆矩存在可逆矩陣陣P M使得使得A=PBP-1,則記為則記為AB. 證明證明: 是是Mn上的等價上的等價關(guān)系關(guān)系.證明證明: r: 設(shè)設(shè)E是單位矩陣是單位矩陣, 則則 A, A=EAE-1 AA s: AB A=PBP-1 P-1AP=B B=P-1A(P-1)-1 BA t: AB BC A=PBP-1 B=QCQ-1 A=P(QCQ-1)P-1 A=(PQ)C(PQ)-1 AC所以所以是是Mn上的等價關(guān)系上的等價關(guān)系. 習(xí)題五 8.設(shè)設(shè)A是由是由54的正因子構(gòu)成的集合的正因子構(gòu)成的集合,”|”表示整除表示整除.作出偏序集作出偏序集對應(yīng)的

21、對應(yīng)的Hasse圖圖.找出最大元最小元找出最大元最小元,求有多少個包含元素最多的全序子集求有多少個包含元素最多的全序子集A=1，2，3，6，9，18，27，54COVER(|)=(1,2), (1,3), (2,6), (3,6), (3,9), (6,18), (9,18), (9,27), (18,54), (27,54)最大元：最大元：54最小元：最小元：1有有4個包含元素最多的全序子集個包含元素最多的全序子集:L1=54,27,9,3,1L1=54,18,9,3,1L1=54,18,6,3,1L1=54,18,6,2,118263927541習(xí)題五 9.設(shè)A=a,b,c ,畫出偏序集對應(yīng)的Hasse圖圖.a,b,ca,ba,cb,cabc習(xí)題五 11.設(shè)設(shè)R是集合是集合A上的一個等價關(guān)系，上的一個等價關(guān)系， 現(xiàn)在在等價類之間定義現(xiàn)在在等價類之間定義一個新關(guān)系一個新關(guān)系S使得對使得對R的任何等價類的任何等價類a和和b滿足滿足aSb aRb，判別，判別S是一個什么關(guān)系？是一個什么關(guān)系？解：由已知解：由已知R是等價關(guān)系，是等價關(guān)系，S是是R等價類集合上的二元關(guān)