川大离散数学习题5

习题 5

1. 设

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

A

上的一个二元关系

R={（（a,b）,(c,d)）|ad=bc},证明:R是A上的等价关系. 证：?A???a,b?|a,b?N??，R={（（a,b）,(c,d)）|ad=bc} ①自反性：由A的定义，ab?ba?a,b?N

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

②对称性 设??a,b?,?c,d???R，则ad?bc 即 cb?da???c,d?,?a,b???R

③传递性 设??a1,b1?,?c1d1???R，则a1d1?b1c1

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

?a1d1d2?b1c1d2?b1d1c2??a1d2?b1c2

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

2. 定义复数集合的子集合C1={a+bi|i2=-1,a、b?R,a?0}，在C1上定义关系S为：(a+bi)S(c+di)?ac>0。证明：S是C1上的一个等价关系，并给出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上的一个等价关系。 由于ac>0，必须a?0,c?0且a和c同号，故S只有2个等价类，

其一是[1]={a+bi|a>0}，另一个是[-1]={a+bi|a<0}，它们分别对应于复平面上右半部和左半部。

3. 集合A={1,2,3,4}的一个分划为S0={{1,2,4},{3}}，求由S0导出的A上的一个等价关系R.

解：?A??1,2,3,4,?, S0???1,2,4?,?3??

1,2,3,4?,设A1??A2??3?

?1，?1，?2，?2，?4，?4，?4，?3，?R???1，1?，2?，4??2，1?，2?，4?，1?，2?，4?，3??

4. 试确定在4个元素的集合上可以定义出的等价关系数目. 解： ∵每个集合的划分就可以确定一个等价关系

∴集合有多少个划分就可以确定多少个等价关系

C?C?C?C?15种。 444443215. 设R1和R2是非空集合A上的两个等价关系.试确定下列各个关系是否是A上的等价关系:如果是,加以证明;如果不是,举例说明： (1)R1R2；(2)R1R2；（3）r(R1-R2)；（4）R1R2 解：

①R1?R2不是A上的等价关系 ②R1?R2是A上的等价关系 ③r?R1?R2? 是A上的等价关系 ④R1oR2不是A上的等价关系

6. 设R是非空集合A上的一个二元关系,具有对称性和传递性.证明:

如果对每一个x?A，存在y?A使xRy，那么，R是A上的等价关系。 证明：

由题可知，对于每一个x，都存在y使xRy，则非空集合A上所有的元素都存在关系（x,y），

又因为R具有对称性，则对于所有的x，R中也必然存在（y,x） 又因为R具有传递性，则对于所有的x,R中也必然存在（x,x）,即R具有自反性

综上，据等价关系定义，R是A上的等价关系

7. 设Mn是全体n阶矩阵的集合.如果对矩阵A、B?Mn,存在可逆矩阵p?Mn使得 A=PBP-1,则记为A∪B(读为A相似于B).证明： ∪是Mn上的等价关系. 证明:

r:设E是单位矩阵,则?A,A=EAE-1?A~A

s:A~B?A=PBP-1?P-1AP=B?B=P-1A(P-1)-1?B~A t:A~B?B~C?A=PBP-1?B=QCQ-1

? A=P(QCQ-1)P-1?A=(PQ)C(PQ)-1?A~C 所以~是Mn上的等价关系.

8. 设A是由54的正因子构成的集合,\表示整除.作出偏序集

A={1，2，3，6，9，18，27，54}

COVER(|)={(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,1} L1={54,18,9,3,1} L1={54,18,6,3,1} L1={54,18,6,2,1}

9. 设A={a,b,c},画出偏序集<2A, ?)对应的Hasse图.试比较本题与上题Hasse图的异同. 解：A??a,b,c?

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

{a,b,c} {a,b} {a,c} {a} ? C

{b} {b,c} {c} <2,?>

10. 是否存在集合A上的一个关系R,它既是等价关系,又是偏序关系?证明或举例说明你的结论.

解：集合A上的空关系?、恒等关系IA都是等价关系和偏序关系。