離散數(shù)學(xué)第五章集合及其運(yùn)算習(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用序偶的集合表示出來(lái)。用序偶的集合表示出來(lái)。(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個(gè)元素的集合，請(qǐng)問(wèn)在個(gè)元素的集合，請(qǐng)問(wèn)在A上可以定義出多少個(gè)二元上可以定義出多少個(gè)二元關(guān)系？關(guān)系？ 解解: 因?yàn)橐驗(yàn)镽是是A上的二元關(guān)系上的二元關(guān)系, R A A,于是于是R 2A A, 所以共所以共2n2個(gè)個(gè)二元關(guān)系二元關(guān)系.習(xí)題四 6設(shè)在整數(shù)集合上定義了如下關(guān)系：確定其滿(mǎn)足的性質(zhì)設(shè)在整數(shù)集合上定義了如下關(guān)系：確定其滿(mǎn)足的性質(zhì)自反性自反性反自反反自反性性對(duì)稱(chēng)性對(duì)稱(chēng)性反對(duì)稱(chēng)反對(duì)稱(chēng)性性傳遞性傳遞性xRy x | y 習(xí)題四 6設(shè)在整數(shù)集合上定義了如下關(guān)系：確定其滿(mǎn)足的性質(zhì)設(shè)在整數(shù)集合上定義了如下關(guān)系：確定其滿(mǎn)足的性質(zhì)自反性自反性

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

4、在整數(shù)集合上定義了如下關(guān)系：確定其滿(mǎn)足的性質(zhì)設(shè)在整數(shù)集合上定義了如下關(guān)系：確定其滿(mǎn)足的性質(zhì)自反性自反性反自反反自反性性對(duì)稱(chēng)性對(duì)稱(chēng)性反對(duì)稱(chēng)反對(duì)稱(chēng)性性傳遞性傳遞性xRy x | y xRy xy(mod n) xRy xy0 xRy xy0 xRy x=y | |x-y|=1 習(xí)題四 6設(shè)在整數(shù)集合上定義了如下關(guān)系：確定其滿(mǎn)足的性質(zhì)設(shè)在整數(shù)集合上定義了如下關(guān)系：確定其滿(mǎn)足的性質(zhì)自反性自反性反自反反自反性性對(duì)稱(chēng)性對(duì)稱(chēng)性反對(duì)稱(chēng)反對(duì)稱(chēng)性性傳遞性傳遞性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、上的一個(gè)二元關(guān)系，是集合上的一個(gè)二元關(guān)系， xRy yRz xRz ,稱(chēng)稱(chēng)R是是A上的上的一個(gè)反傳遞關(guān)系。試舉一個(gè)實(shí)際的反傳遞關(guān)系的例子。一個(gè)反傳遞關(guān)系。試舉一個(gè)實(shí)際的反傳遞關(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) 不是反傳遞不是反傳遞傳遞和反傳遞不是絕對(duì)互相排斥傳遞和反傳遞不是絕對(duì)互相排斥實(shí)際中，如實(shí)際中，如“父

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

7、和S都是集合都是集合A上的二元關(guān)系，它們經(jīng)過(guò)關(guān)系運(yùn)算后得到上的二元關(guān)系，它們經(jīng)過(guò)關(guān)系運(yùn)算后得到A上的一個(gè)上的一個(gè)新關(guān)系。判別當(dāng)新關(guān)系。判別當(dāng)R和和S 同時(shí)具有表中某種指定性質(zhì)時(shí)，經(jīng)過(guò)指定的運(yùn)算同時(shí)具有表中某種指定性質(zhì)時(shí)，經(jīng)過(guò)指定的運(yùn)算后所得新關(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、性自反性 反自反性反自反性 對(duì)稱(chēng)性對(duì)稱(chēng)性 反對(duì)稱(chēng)性反對(duì)稱(chēng)性 傳遞性傳遞性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ò)關(guān)系運(yùn)算后得到上的二元關(guān)系，它們經(jīng)過(guò)關(guān)系運(yùn)算后得到A上的一個(gè)上的一個(gè)新關(guān)系。判別當(dāng)新關(guān)系。判別當(dāng)R和和S 同時(shí)具有表中某種指定性質(zhì)時(shí)，經(jīng)過(guò)指定的運(yùn)算同時(shí)具有表中某種指定性質(zhì)時(shí)，經(jīng)過(guò)指定的運(yùn)算后所得新關(guān)系是否也仍保持這種性質(zhì)：后所得新關(guān)系是否也仍保持這種性質(zhì)： 自反性自反性 反自反性反自反性 對(duì)稱(chēng)性對(duì)稱(chēng)性

9、反對(duì)稱(chēng)性反對(duì)稱(chēng)性 傳遞性傳遞性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ò)關(guān)系運(yùn)算后得到上的二元關(guān)系，它們經(jīng)過(guò)關(guān)系運(yùn)算后得到A上的一個(gè)上的一個(gè)新關(guān)系。判別當(dāng)新關(guān)系。判別當(dāng)R和和S 同時(shí)具有表中某種指定性質(zhì)時(shí)，經(jīng)過(guò)指定的運(yùn)算同時(shí)具有表中某種指定性質(zhì)時(shí)，經(jīng)過(guò)指定的運(yùn)算后所得新關(guān)系是否也仍保持這種性質(zhì)：后所得新關(guān)系是否也仍保持這種性質(zhì)： 自反性自反性 反自反性反自反性 對(duì)稱(chēng)性對(duì)稱(chēng)性 反對(duì)稱(chēng)性反對(duì)稱(chēng)

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ò)關(guān)系運(yùn)算后得到上的二元關(guān)系，它們經(jīng)過(guò)關(guān)系運(yùn)算后得到A上的一個(gè)上的一個(gè)新關(guān)系。判別當(dāng)新關(guān)系。判別當(dāng)R和和S 同時(shí)具有表中某種指定性質(zhì)時(shí)，經(jīng)過(guò)指定的運(yùn)算同時(shí)具有表中某種指定性質(zhì)時(shí)，經(jīng)過(guò)指定的運(yùn)算后所得新關(guān)系是否也仍保持這種性質(zhì)：后所得新關(guān)系是否也仍保持這種性質(zhì)： 自反性自反性 反自反性反自反性 對(duì)稱(chēng)性對(duì)稱(chēng)性 反對(duì)稱(chēng)性反對(duì)稱(chēng)性 傳遞性傳遞性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ò)關(guān)系運(yùn)算后得到上的二元關(guān)系，它們經(jīng)過(guò)關(guān)系運(yùn)算后得到A上的一個(gè)上的一個(gè)新關(guān)系。判別當(dāng)新關(guān)系。判別當(dāng)R和和S 同時(shí)具有表中某種指定性質(zhì)時(shí)，經(jīng)過(guò)指定的運(yùn)算同時(shí)具有表中某種指定性質(zhì)時(shí)，經(jīng)過(guò)指定的運(yùn)算后所得新關(guān)系是否也仍保持這種性質(zhì)：后所得新關(guān)系是否也仍保持這種性質(zhì)： 自反性自反性 反自反性反自反性 對(duì)稱(chēng)性對(duì)稱(chēng)性 反對(duì)稱(chēng)性反對(duì)稱(chēng)性 傳遞性傳遞性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ò)關(guān)系運(yùn)算后得到上的二元關(guān)系，它們經(jīng)過(guò)關(guān)系運(yùn)算后得到A上的一個(gè)上的一個(gè)新關(guān)系。判別當(dāng)新關(guān)系。判別當(dāng)R和和S 同時(shí)具有表中某種指定性質(zhì)時(shí)，經(jīng)過(guò)指定的運(yùn)算同時(shí)具有表中某種指定性質(zhì)時(shí)，經(jīng)過(guò)指定的運(yùn)算后所得新關(guān)系是否也仍保持這種性質(zhì)：后所得新關(guān)系是否也仍保持這種性質(zhì)： 自反性自反性 反自反性反自反性 對(duì)稱(chēng)性對(duì)稱(chēng)性 反對(duì)稱(chēng)性反

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

14、系，它們經(jīng)過(guò)關(guān)系運(yùn)算后得到上的二元關(guān)系，它們經(jīng)過(guò)關(guān)系運(yùn)算后得到A上的一個(gè)上的一個(gè)新關(guān)系。判別當(dāng)新關(guān)系。判別當(dāng)R和和S 同時(shí)具有表中某種指定性質(zhì)時(shí)，經(jīng)過(guò)指定的運(yùn)算同時(shí)具有表中某種指定性質(zhì)時(shí)，經(jīng)過(guò)指定的運(yùn)算后所得新關(guān)系是否也仍保持這種性質(zhì)：后所得新關(guān)系是否也仍保持這種性質(zhì)：設(shè)設(shè)R是集合是集合A上的一個(gè)二元關(guān)系。證明：上的一個(gè)二元關(guān)系。證明：（1）R是自反的是自反的 IA R證明：當(dāng)證明：當(dāng)R是自反時(shí)，任取是自反時(shí)，任取(x,x) IA,必有必有(x,x) R IA R當(dāng)當(dāng)IA R時(shí)，時(shí)，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= 時(shí)時(shí), R中無(wú)中無(wú)(x, x)序偶，序偶，故故反自反。反自反。（3）R是對(duì)稱(chēng)的是對(duì)稱(chēng)的R = R-1證明證明: 當(dāng)當(dāng)R是對(duì)稱(chēng)的，任是對(duì)稱(chēng)的，任(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 ，則對(duì)任何，則對(duì)任何(x, y) R, 必有必有(y, x) R-1 R ，故故R對(duì)稱(chēng)對(duì)稱(chēng)習(xí)題四 10設(shè)設(shè)R是集合是集合A上的一個(gè)二元關(guān)系。證明：上的一個(gè)二

16、元關(guān)系。證明：（4） R是反對(duì)稱(chēng)的是反對(duì)稱(chēng)的R R-1 IA證明：當(dāng)證明：當(dāng)R是反對(duì)稱(chēng)時(shí)，任取是反對(duì)稱(chēng)時(shí)，任取(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時(shí)，如果時(shí)，如果 x y,則則(x, y) R (x, y) R-1 ，即，即(x, y) R (y, x) R R是反對(duì)稱(chēng)的。是反對(duì)稱(chēng)的。（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時(shí)時(shí), 任取任取(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對(duì)應(yīng)的關(guān)系圖如圖，求對(duì)應(yīng)的關(guān)系圖如圖，求使使Rm= Rn的最小正整數(shù)的最小正整數(shù)m和和n (m0。證明。證明S是是C1上上的一個(gè)等價(jià)關(guān)系，并給出的一個(gè)等價(jià)關(guān)系，并給出S的等價(jià)類(lèi)的幾何說(shuō)明。的等價(jià)類(lèi)的幾何說(shuō)明。證明證明: 因?yàn)橐驗(yàn)?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上的一個(gè)等價(jià)關(guān)系。上的一個(gè)等價(jià)關(guān)系。由于由于ac0，必須，必須a 0, c0且a和和c同號(hào)，故同號(hào)，故S只有只有2個(gè)等價(jià)類(lèi)，個(gè)等價(jià)類(lèi)，其一是其一是1=a+bi | a0，另一個(gè)是，另一個(gè)是-1=a+bi | a0，它們，它們分別對(duì)應(yīng)于復(fù)平面上右半部和左半部。分別對(duì)應(yīng)于復(fù)平面上右半部和左半部。習(xí)題五 4. 試確定在試確定在4個(gè)元素的集合上可以定義出的等價(jià)關(guān)系數(shù)目。個(gè)元素的集合上可以定義出的等價(jià)關(guān)系數(shù)目。解：解：A=a,b,c,d可產(chǎn)生

19、的分劃如下：可產(chǎn)生的分劃如下：含一個(gè)等價(jià)類(lèi)含一個(gè)等價(jià)類(lèi) S1=a,b,c,d含二個(gè)等價(jià)類(lèi)含二個(gè)等價(jià)類(lèi)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 含三個(gè)等價(jià)類(lèi)含三個(gè)等價(jià)類(lèi), 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,含四個(gè)等價(jià)類(lèi)含四個(gè)等價(jià)類(lèi): S15=a,b,c,d 所以共個(gè)所以共個(gè)習(xí)題五 7. 設(shè)設(shè)Mn是全體是全體n階矩陣的集

20、合階矩陣的集合.如果對(duì)矩陣如果對(duì)矩陣A,B M,存在可逆矩存在可逆矩陣陣P M使得使得A=PBP-1,則記為則記為AB. 證明證明: 是是Mn上的等價(jià)上的等價(jià)關(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上的等價(jià)關(guān)系上的等價(jià)關(guān)系. 習(xí)題五 8.設(shè)設(shè)A是由是由54的正因子構(gòu)成的集合的正因子構(gòu)成的集合,”|”表示整除表示整除.作出偏序集作出偏序集對(duì)應(yīng)的

21、對(duì)應(yīng)的Hasse圖圖.找出最大元最小元找出最大元最小元,求有多少個(gè)包含元素最多的全序子集求有多少個(gè)包含元素最多的全序子集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個(gè)包含元素最多的全序子集個(gè)包含元素最多的全序子集: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 ,畫(huà)出偏序集對(duì)應(yīng)的Hasse圖圖.a,b,ca,ba,cb,cabc習(xí)題五 11.設(shè)設(shè)R是集合是集合A上的一個(gè)等價(jià)關(guān)系，上的一個(gè)等價(jià)關(guān)系， 現(xiàn)在在等價(jià)類(lèi)之間定義現(xiàn)在在等價(jià)類(lèi)之間定義一個(gè)新關(guān)系一個(gè)新關(guān)系S使得對(duì)使得對(duì)R的任何等價(jià)類(lèi)的任何等價(jià)類(lèi)a和和b滿(mǎn)足滿(mǎn)足aSb aRb，判別，判別S是一個(gè)什么關(guān)系？是一個(gè)什么關(guān)系？解：由已知解：由已知R是等價(jià)關(guān)系，是等價(jià)關(guān)系，S是是R等價(jià)類(lèi)集合上的二元關(guān)