川大離散數(shù)學(xué)習(xí)題5

本文格式為Word版，下載可任意編輯——川大離散數(shù)學(xué)習(xí)題5

習(xí)題5

1.設(shè)

A={(a,b)|a,b∈N}.定義

A

上的一個二元關(guān)系

R={（（a,b）,(c,d)）|ad=bc},證明:R是A上的等價關(guān)系.證：?A???a,b?|a,b?N??，R={（（a,b）,(c,d)）|ad=bc}①自反性：由A的定義，ab?ba?a,b?N

??a,b?,?a,b???R

②對稱性設(shè)??a,b?,?c,d???R，則ad?bc即cb?da???c,d?,?a,b???R

③傳遞性設(shè)??a1,b1?,?c1d1???R，則a1d1?b1c1

??c1,d1?,?c2d2???R，則c1d2?d1c2

?a1d1d2?b1c1d2?b1d1c2??a1d2?b1c2

??a1,b1?,?c2,d2???R

2.定義復(fù)數(shù)集合的子集合C1={a+bi|i2=-1,a、b?R,a?0}，在C1上定義關(guān)系S為：(a+bi)S(c+di)?ac>0。證明：S是C1上的一個等價關(guān)系，并給出S的等價類的幾何說明。

證明:由于(a+bi)S(c+di)?ac>0(a,b?R,a?0,c?0)

r:?a?0,a2>0?(a+bi)S(a+bi)

s:(a+bi)S(c+di)?ac>0?ca>0?(c+di)S(a+bi)t:(a+bi)S(c+di)?(c+di)S(u+vi)?ac>0?cu>0

?au>0?(a+bi)S(u+vi)綜上，S是C1上的一個等價關(guān)系。由于ac>0，必需a?0,c?0且a和c同號，故S只有2個等價類，

其一是[1]={a+bi|a>0}，另一個是[-1]={a+bi|a

10.是否存在集合A上的一個關(guān)系R,它既是等價關(guān)系,又是偏序關(guān)系?證明或舉例說明你的結(jié)論.

解：集合A上的空關(guān)系?、恒等關(guān)系IA都是等價關(guān)系和偏序關(guān)系。

11.設(shè)R是集合A上的一個等價關(guān)系?，F(xiàn)在在等價類之間定義一個新關(guān)系S，使得對R的任何等價類[a]和[b]滿足[a]S[b]?aRb,判別S是一個什么關(guān)系?

解：由已知R是等價關(guān)系，S是R等價類集合上的二元關(guān)系，且[a]S[b]

?aRb。

由于對R的任2個等價類[a]和[b]，要么[a]=[b]，要么[a]?[b]=?，又aRb說明a和b在同一等價類中，因此，S={([a],[a])|a?A}（等價類集合上的恒等關(guān)系），所以S滿足自反性、對稱性、反對稱性、傳遞性，所以S既是等價關(guān)系，又是偏序關(guān)系。

12.設(shè)R是集合A上的一個二元關(guān)系.假使R是反自反的且是傳遞的,稱R是A上的逆序關(guān)系.(1)舉一個逆序關(guān)系的例子；

(2)證明：逆序關(guān)系是反對稱的，并進(jìn)一步證明逆序關(guān)系的自反閉包是A上的偏序關(guān)系。解：

（1）例如：A={A,B,C}R={(A,B),(B,C),(A,C)}

（2）證明:逆序關(guān)系是傳遞的，若對于兩個不同的x,y存在兩個關(guān)系

(x,y)和(y,x)，則必然存在關(guān)系（x,x），與逆序關(guān)系的反自反性相矛盾；

即若對于兩個不同的x,y不可能存在兩個關(guān)系(x,y)和

(y,x)，所以逆序關(guān)系是反對稱的。

逆序關(guān)系的自反閉包必然具有自反性，且對于兩個不同的

x,y不可能存在兩個關(guān)系(x,y)和(y,x)，則反對稱關(guān)系仍舊成立，又由于逆序關(guān)系具有傳遞性，R∪IA同樣具有傳遞性。

綜上，逆序關(guān)系的自反閉包符合偏序關(guān)系的定義，故其是

A上的偏序關(guān)系。

13.設(shè)R是集合A上的一個偏序關(guān)系，B是A的非空子集。證明：RB?B是B上的偏序關(guān)系。證：i）自反性，對?b?B?A,顯然?b,b??B?B???b,b??R，（R的自反性）

?b,b??R?B?B

ii)反對稱性，對?a,b?B,?a,b??R?B?B,?b,a??R?B?B

即?a,b??R,?b,a??R，由R的反對稱性，?a?b

iii)傳遞性，對?a,b,c?B，設(shè)?a,b??R?B?B,?b,c??R?B?B，則?a,b??R，?b,c??R。

由R的傳遞性，?a,c??R，顯然?a,c??B?B

??a,c??R?B?B

14.對習(xí)題5.2的第1題,找出偏序集A的最大元和最小元,并確定它有多少個包含元素最多的全序子集.解：（略）

A15.設(shè)A={a,b,c,d}。試構(gòu)造關(guān)于偏序集的一個全序集

使得?是?的拓?fù)渑判颉?/p>

解：A??a,b,c,d?

2A???,?a?,?b?,?c?,?d?,?a,b?,?a,c?,?a,d?,?b,c?,?b,d?,?c,d?,?a,b,c?,?a,b,d?,?b,c,d?,?a,c,d?,?a,b,c,d??