川大离散数学习题.pdf

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

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

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

3、ad=bc},证明:R是A上的等价关系.证：Aa,b

4、a,bN，R={（（a,b）,(c,d)）

5、ad=bc}①自反性：由A的定义，abbaa,bNa,b,a,bR②对称性设a,b,c,dR，则adbc即cbdac,d,a,bR③传递性设a,b,cdR，则adbc11111111c,d,cdR，则cddc11221212add

6、bcdbdcadbc1121121121212a,b,c,dR11222.定义复数集合的子集合C={a+bi

7、i2=-1,a、bR,a0}，在C上定11义关系S为：(a+bi)S(c+di)ac>0。证明：S是C上的一个等价关1系，并给出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+

8、di)S(u+vi)ac>0cu>0au>0(a+bi)S(u+vi)综上，S是C上的一个等价关系。1由于ac>0，必须a0,c0且a和c同号，故S只有2个等价类，其一是[1]={a+bi

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

10、a<0}，它们分别对应于复平面上右半部和左半部。3.集合A={1,2,3,4}的一个分划为S={{1,2,4},{3}}，求由S导出00的A上的一个等价关系R.解：A1,2,3,4,,S1,2,4,30设A1,2,3,4,A312R1，1，1，

11、2，1，42，1，2，2，2，4，4，1，4，2，4，4，3，34.试确定在4个元素的集合上可以定义出的等价关系数目.解：∵每个集合的划分就可以确定一个等价关系∴集合有多少个划分就可以确定多少个等价关系4321CCCC15种。44445.设R和R是非空集合A上的两个等价关系.试确定下列各个关系12是否是A上的等价关系:如果是,加以证明;如果不是,举例说明：(1)RUR；(2)RIR；（3）r(R-R)；（4）RoR12121212解：①RR不是A上的等价关系12②RR是A上的等价

12、关系12③rRR是A上的等价关系12④RoR不是A上的等价关系126.设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.设M是全体n阶矩阵的集合.如果对矩阵A、BM,存在可逆

13、矩阵nnpM使得A=PBP-1,则记为A∪B(读为A相似于B).证明：∪是M上的nn等价关系.证明: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-1)P-1A=(PQ)C(PQ)-1A~C所以~是Mn上的等价关系.8.设A是由54的正因子构成的集合,"

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

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

16、)={(

17、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,

18、b,c}{a,b}{a,c}{b,c}{a}{b}{c}<2C,>10.是否存在集合A上的一个关系R,它既是等价关系,又是偏序关系?证明或举例说明你的结论.解：集合A上的空关系、恒等关系I都是等价关系和偏序关系。A11.设R是集合A上的一个等价关系。现在在等价类之间定义