川大离散数学习题5.docVIP

习题 5 1. 设A={(a,b)|a,b∈N}.定义A上的一个二元关系R={（（a,b）,(c,d)）|ad=bc},证明:R是A上的等价关系.，R={（（a,b）,(c,d)）|ad=bc} ②对称性 设，则 即 ③传递性 设，则 ，则 2. 定义复数集合的子集合C1={a+bi|i2=-1,a、bR,a0}，在C1上定义关系S为：(a+bi)S(c+di)ac0。证明：S是C1上的一个等价关系，并给出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((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上的一个等价关系。 由于ac0，必须a(0,c(0且a和c同号，故S只有2个等价类，其一是[1]={a+bi|a0}，另一个是[-1]={a+bi|a0}，它们分别对应于复平面上右半部和左半部。 3. 集合A={1,2,3,4}的一个分划为S0={{1,2,4},{3}}，求由S0导出的A上的一个等价关系R. 设 4. 试确定在4个元素的集合上可以定义出的等价关系数目. 种。 5. 设R1和R2是非空集合A上的两个等价关系.试确定下列各个关系是否是A上的等价关系:如果是,加以证明;如果不是,举例说明： (1)R1R2；(2)R1R2；（3）r(R1-R2)；（4）R1R2 不是A上的等价关系 ②是A上的等价关系 ③ 是A上的等价关系 ④不是A上的等价关系 6. 设R是非空集合A上的一个二元关系,具有称性和传递性.证明:如果对每一个xA，存在yA使xRy，那么，R是A上的等价关系。 设Mn是全体n阶矩阵的集合.如果对矩阵A、BMn,存在可逆矩阵pMn使得 A=PBP-1,则记为AB(读为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,|)对应的Hasse图. 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图的异同. 10. 是否存在集合A上的一个关系R,它既是等价关系,又是偏序关系?证明或举例说明你的结论.、恒等关系IA都是等价关系和偏序关系。 11. 设R是集合A上的一个等价关系现在在等价类之间定义一个新关系S使得对R的任何等价类[a]和[b]满足[a]S[b] aRb,判别S是一个什么关系?R是等价关系，S是R等价类集合上的二元关系，且[a]S[b] ( aRb。 因为对R 的任2个等价类[a]和[b]，要么[a]=[b]，要么[a] ([b]= (，又aRb说明a和b在同一等价类中，因此，S={([a], [a]) | a (A}（等价类集合上的恒等关系）， 所以S满足自反性、对称性、反对称性、传递性， 所以S既是等价关系，又是偏序关系。 12. 设R是集合A上的一个二元关系.如果R是反自反的且是传递的,称R是A上的序关系. (1)举一个逆序关系的例子； (2)证明：逆序关系是反对称的，并进一步证明逆序关系的自反闭包是A上的偏序关系。 设R是集合A上的一个偏序关系，B是A的非空子集。证明：RBB是B上的偏序关系。，（的自反性） 显然 ii)反对称性，对 即，由R的反对称性， iii)传递性，对，设， 则，。 由R的传递性，，显然 14.对习题5.2的第1题,找出偏序集A的最大元和最小元,并确定它有多少个包含元素最多的全序子集.设A={a,b,c,d}。试构造关于偏序集2A，的一个全序集2A,使得是的拓扑排序。 2C,( ( {a} {b} {c} {a,b} {a,c} {b,c} {a,b,c}