川大离散数学习题5

《川大离散数学习题5》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、习题51.设A={(a,b)

2、a,b∈N}.定义A上的一个二元关系R={（（a,b）,(c,d)）

3、ad=bc},证明:R是A上的等价关系.证：，R={（（a,b）,(c,d)）

4、ad=bc}①自反性：由A的定义，②对称性设，则即③传递性设，则，则2.定义复数集合的子集合C1={a+bi

5、i2=-1,a、bR,a0}，在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)

6、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

7、a>0}，另一个是[-1]={a+bi

8、a<0}，它们分别对应于复平面上右半部和左半部。3.集合A={1,2,3,4}的一个分划为S0={{1,2,4},{3}}，求由S0导出的A上的一个等价关系R.解：设4.试确定在4个元素的集合上可以定义出的

9、等价关系数目.解：∵每个集合的划分就可以确定一个等价关系∴集合有多少个划分就可以确定多少个等价关系种。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上的等价关系。证明：由题可知，对于每一个x，都存在y使xRy，则非空集合

10、A上所有的元素都存在关系（x,y），又因为R具有对称性，则对于所有的x，R中也必然存在（y,x）又因为R具有传递性，则对于所有的x,R中也必然存在（x,x）,即R具有自反性综上，据等价关系定义，R是A上的等价关系7.设Mn是全体n阶矩阵的集合.如果对矩阵A、BMn,存在可逆矩阵pMn使得A=PBP-1,则记为A∪B(读为A相似于B).证明：∪是Mn上的等价关系.证明:r:设E是单位矩阵,则"A,A=EAE-1ÛA~As:A~BÛA=PBP-1ÛP-1AP=BÛB=P-1A(P-1)-1ÛB~At:A~BÙB~CÛA=PBP-1ÙB=QCQ-1ÛA=P(QCQ

11、-1)P-1ÛA=(PQ)C(PQ)-1ÛA~C所以~是Mn上的等价关系.8.设A是由54的正因子构成的集合,"

12、"表示整除.作出偏序集

13、)对应的Hasse图.解：A={1，2，3，6，9，18，27，54}COVER(

14、)={(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,

15、b,c},画出偏序集<2A,)对应的Hasse图.试比较本题与上题Hasse图的异同.解：<2C,Í>F{a}{b}{c}{a,b}{a,c}{b,c}{a,b,c}10.是否存在集合A上的一个关系R,它既是等价关系,又是偏序关系?证明或举例说明你的结论.解：集合A上的空关系、恒等关系IA都是等价关系和偏序关系。11.设R是集合A上的一个等价关系。现在在等价类之间定义一个新关系S，使得对R的任何等价类[a]和[b]满足[a]S[b]aRb,判别S是一个什么关系?解：由已知R是等价关系，S是R等价类集合上的二元关系，且[a]S[b]ÛaRb。因为对R的任2个等

16、价类[a]和[b]，要么[a]=[b]，要么[a]Ç[b]=Æ，又aRb说明a和b在同一等价类中，因此，S={([a],[a])

17、aÎA}（等价类集合上的恒等关系），所以S满足自反性、对称性、反对称性、传递性，所以S既是等价关系，又是偏序关系。12.设R是集合A上的一个二元关系.如果R是反自反的且是传递的,称R是A上的逆序关系.(1)举一个逆序关系的例子；(2)证明：逆序关系是反对称的，并进一步证明逆序关系的自反闭包是A上的偏序关系。解：（1）例如：A={A,B,C}R={(A,B),(B,C),(A,C)}（2）证明:逆序关系是传递的，若对于两个不同的x,

18、y存在两个关系(x,y)和(y,x)，则必然存在关系