離散數(shù)學(xué) 劉任任 課后答案 習(xí)題2

1、習(xí) 題 二1.確定下列二元關(guān)系：（1）（2） 解：(1) (2) 2. 請(qǐng)分別給出滿足下列要求的二元關(guān)系的例子：（1）既是自反的，又是反自反的；（2）既不是自反的，又不是反自反的；（3）既是對(duì)稱的，又是反對(duì)稱的；（4）既不是對(duì)稱的，又不是反對(duì)稱的. 解：設(shè)是定義在集合上的二元關(guān)系。(1) 令，則，于是既是自反又是反自反的；(2) 令，于是既不是自反又不是反自反的；(3) 令，于是既是對(duì)稱又是反對(duì)稱的；(4) 令，于是既不是對(duì)稱又不是反對(duì)稱的。3. 設(shè)集合有個(gè)元素，試問：（1）共有多少種定義在上的不同的二元關(guān)系？（2）共有多少種定義在上的不同的自反關(guān)系？（3）共有多少種定義在上的不同的反自反關(guān)系

2、？（4）共有多少種定義在上的不同的對(duì)稱關(guān)系？（5）共有多少種定義在上的不同的反對(duì)稱關(guān)系？解：設(shè)，于是(1) 共有種定義在上的不同的二元關(guān)系；(2) 共有種定義在上的不同的自反關(guān)系；(3) 共有種定義在上的不同的反自反關(guān)系；(4) 共有 種定義在上的不同的對(duì)稱關(guān)系；(5) 共有種定義在上的不同的反對(duì)稱關(guān)系，其中，。4. 請(qǐng)分別描述自反關(guān)系，反自反關(guān)系，對(duì)稱關(guān)系和反對(duì)稱關(guān)系的關(guān)系矩陣以及關(guān)系圖的特征.解：(1) 自反關(guān)系矩陣的主對(duì)角線上元素全為1；而關(guān)系圖中每個(gè)結(jié)點(diǎn)上都有圈。(2) 反自反關(guān)系矩陣的主對(duì)角線上元素全為0; 而關(guān)系圖中每個(gè)結(jié)點(diǎn)上均無圈。(3) 對(duì)稱關(guān)系矩陣為對(duì)稱矩陣; 而關(guān)系圖中任何

3、兩個(gè)結(jié)點(diǎn)之間的有向弧是成對(duì)出現(xiàn)的, 方向相反。(4) 反對(duì)稱關(guān)系矩陣的元素滿足：當(dāng)時(shí)，。5設(shè)，試求及.解： 。6. 試舉出使成立的二元關(guān)系的實(shí)例. 解：設(shè),于是, 有, 因此, 從而, 。又，因此，從而, 。7. 設(shè)和是集合上的二元關(guān)系. 下面的說法正確嗎?請(qǐng)說出理由. （1）若和是自反的，則也是自反的；（2）若和是反自反的，則也是反自反的；（3）若和是對(duì)稱的，則也是對(duì)稱的；（4）若和是反對(duì)稱的，則也是反對(duì)稱的；（5）若和是傳遞的，則也是傳遞的解：(1) 正確。因?yàn)閷?duì)任意，有，所以。故是自反的。(2) 錯(cuò)誤。例如，設(shè)，且，于是。故不是自反的。(3) 錯(cuò)誤。例如，設(shè)對(duì)稱關(guān)系。于是，但。故不是對(duì)稱

4、的。(4) 錯(cuò)誤。例如，設(shè)反對(duì)稱關(guān)系。于是，。故不是反對(duì)稱的。(5) 錯(cuò)誤。例如，設(shè)傳遞關(guān)系。于是， ，但因?yàn)?，所以，?設(shè)和是集合上的二元關(guān)系，試證明：（1）；（2）；（3）并舉出使時(shí)使的實(shí)例. 解：(1) (2) (3) 由定義， 于是，。 下證對(duì)任意，有。任取，不妨設(shè)。于是，存在 使得從而， 。舉例說明“”成立。設(shè)，于是，。9設(shè)和是集合上的二元關(guān)系，試證明：（1）；（2）；（3）并請(qǐng)給出時(shí)使和的實(shí)例. 解：設(shè)是集合上的二元關(guān)系。注意到，于是，(1) = = = =(2) , ,。任取，(i) 若 則 且 從而， ；(ii) 若 則 即 從而， 且 于是， 故 。舉例說明“”成立。設(shè)，于是

5、，而，因此，。（3）證明：因?yàn)橛衷O(shè) A= 1, 2, 3 , ，于是， 而，故 .10有人說，“如果集合上的二元關(guān)系是對(duì)稱和傳遞的，則必是自反的. 因此，等價(jià)關(guān)系定義中的自反性可以去掉”. 并給出如下證明，如果，由的對(duì)稱性有，再由的傳遞性知，且，即是自反的. 你的看法如何?解：說法不正確。 對(duì)任意, 對(duì)稱性并不要求一定有， 因此也就不一定有<y, x>。于是 <x , x>R。11設(shè)是集合上的自反關(guān)系. 試證明是等價(jià)關(guān)系當(dāng)且僅當(dāng)若，則. 解：設(shè)R是等價(jià)關(guān)系。若 <x, y>, <x, z>R , 則由R的對(duì)稱性知, <y, x>R。再

6、由R的傳遞性有<y, z>R。反之, 假設(shè)只要<x, y>, <x, z>R, 就有<y, z>R。(1) 對(duì)稱性。 設(shè)< x, y >R，由自反性有<x, x>R。于是<y, x>R。(2) 傳遞性。 設(shè)<x, y>, <y, z>R。 由對(duì)稱性有<y, x>R, 再由假設(shè)有<x, z>R。12設(shè)和都是集合上的等價(jià)關(guān)系，試證明當(dāng)且僅當(dāng). 證明：設(shè) , 則顯然 。反之, 設(shè)。若 , 則不妨設(shè)<x , y> 但<x , y> .于是 , .由

7、劃分之定義得知 , 矛盾.。故。13設(shè)是定義在整數(shù)集Z上的模5同余關(guān)系，求Z/R. 解：設(shè) R= <y , x>| xy(mod 5).于是0 =-15,-10,-5,0,5,10,151 =-14,-9,-4,1,6,11,16,2 =-13,-8,-3,2,7,12,17,3 =-12,-7,-2,3,8,13,18,4 =-11,-6,-1,4,9,14,19,A/R = 0 ,1 ,2 ,3 ,4 .14設(shè)和是集合的兩個(gè)劃分，令試證明也是的一個(gè)劃分. 證明: .(1) 由S 定義知, ;(2) 任取和, 1<=i ,j<=r, 1<=j,m<=s .

8、 (3) 故 S 是的一個(gè)劃分.15定義在4個(gè)元素的集合之上的等價(jià)關(guān)系共有多少個(gè)？若呢？解：設(shè)A=1,2,3,4,則A上的等價(jià)關(guān)系數(shù)目即A上的劃分的數(shù)目共有15個(gè).(1) 最大劃分 1, 2, 3 ,4 (2) 最小劃分 1 ,2, 3 ,4(3) 將A分成兩個(gè)集合S=, , 共有兩種可能：(i) | = | ，共有種, 即1, 2 , 3, 4, 1, 3, 2, 4, 1, 4, 2, 3。(ii) | = 1, | =3, 共種, 即1, 2,3,4, 2, 1,3,4, 3, 1,2,4, 4,1,2,3(4) 將A分成三個(gè)集合, 則恰有一個(gè)集合為2個(gè)元素,故共有種分法，即1, 2,

9、3, 4, 1, 3, 2 ,4, 1, 4, 2 ,3, 2, 3, 1, 4, 2,4, 1, 3, 3,4, 1, 2設(shè) 表示可k元集合A上的全部等價(jià)關(guān)系數(shù)目, 則16設(shè)，偏序關(guān)系為整除. 試分別畫出，以及的Hasse圖. 12解： 15 54 6 3 5 2 3 27 9 1 3 <A1,> <A2, > <A3, >x1x2x3x4x5圖2.317設(shè)的Hasse圖如圖2. 3所示：（1）求的最大（?。┰?，極大（小）元；（2）分別求和的上（下）界，上（下）確界. 解：(1) 最大元x1, 無最小元;(2) 上界 下界 上確界 下確界x2, x3, x

10、4 x1 x4 x1 x4x3, x4, x5 x1,x3 無 x3 無x1, x2, x3 x1 x4 x1 x418請(qǐng)分別舉出滿足下列條件的偏序集的實(shí)例：（1）為全序集，但的某些非空子集無最小元；（2）不是全序集，的某些非空子集無最大元；（3）的某些非空子集有下確界，但該子集無最小元；（4）的某些非空子集有上界，但該子集無上確界解：(1) <Z ,> 為全序集, Z 整數(shù)集,但<,>無最小元 , 其中=;(2)題16中的<A1, >,子集3 ,5無最大元;(3) 題16中的<A2, >,子集2,3,6有下確界但無最小界;(4) 子集a,b,e有上界d, e,但無上確界。19試證明：每一個(gè)有限的全序集必是良序集. 證明：設(shè)<A, >為全序集, 且|A| = n。任取 ,因B中的任意兩個(gè)元素x, y均有x<=y或者y<=x。因此, B中必有最小元a.故<A, >為良序集。20設(shè)為偏序集. 試證明的每個(gè)非空有限子集至少有一個(gè)極小元和極大元. 證明：設(shè)B是A的