离散数学作业6_集合与关系答案.doc

《离散数学作业6_集合与关系答案.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、离散数学作业作业6——等价关系1.设R和S均为A上的等价关系，确定下列各式，哪些是A上的等价关系？如果是，证明之；否则，举反例说明。（1）R∩S（2）R∪S（3）r(R-S)（4）R-S（5）R◦S（6）R2解：(1),(6)正确，其余错误。2.R是集合A上的二元关系，"a,b,c,若aRb,且bRc,有cRb,则称R是循环关系。证明R是自反和循环的，当且仅当R是一等价关系。分析:需要证明两部分:(1)已知R是自反和循环的，证明:R是一等价关系(2)已知R是一等价关系,证明R是自反和循环的.证明：（1）

2、先证必要性。只需要证明R是对陈的和传递的。任取(x,y)∈R。因为R是自反的，所以(y,y)∈R。由R是循环的可得(y,x)∈R，即R是对陈的。任取(x,y)，(y,z)∈R。因R是循环的，所以(z,x)∈R。由R对称性得(x,z)∈R，即R是传递的。（2）证充分性。只需要证明R是循环的。任取(x,y)，(y,z)∈R，下证(z,x)∈R。由于R是传递的，所以(x,z)∈R。又由R是对称的得(z,x)∈R。所以R是循环的。3.设

3、A

4、=n，在A上可以确定多少个不同的等价关系？解：2n!/((n+1)n!

5、n!)4.给定集合S={1,2,3,4,5}，找出S上的等价关系R，此关系R能够产生划分{{1，2}，{3}，{4，5}}，并画出关系图。解：5.设A={1，2，3，4，5}。R是集合A上的二元关系，其关系矩阵如下图所示。求包含R的最小等价关系和该等价关系所确定的划分。分析:可以证明tsr(R)是包含R的最小等价关系.解：包含R的最小等价关系的矩阵表示如下：上述等价关系确定的划分为{{1},{2,4},{3,5}}.6.自学华氏(WalShall)算法，写出算法的基本概念、基本步骤和一个求解传递闭包的具

6、体实例，并可清晰讲解算法整体实现过程。7.（选做题）设R与S是A上的等价关系，证明：（1）RS是A上的等价关系，iffRS=SR；（2）R∪S是A上的等价关系，ifRSS且SRR.分析:iff是ifandonlyif的缩写,是当且仅当的意思.证明：（1）先证必要性。任取(x,z)∈RS，则存在y使得xRy,ySz。因为R与S是A上的等价关系，所以R与S是对陈的，即yRx,zSy,所以(z,x)∈SR。因此，RSSR。任取(x,z)∈SR，则存在y使得xSy,yRz。由R与S是对陈的得ySx,zRy，即(

7、z,x)∈RS。又因为RS是对陈的，所以(x,z)∈RS，即SRRS。综上RS=SR，必要性得证，下面证充分性。因为IAR，IAS，所以IARS，即RS是自反的。任取(x,z)∈RS，则存在y使得xRy,ySz。由R与S是对陈的得yRx,zSy，即(z,x)∈SR。因为RS=SR，所以(z,x)∈RS，即RS是对陈的。因为所以RS是传递的。综上，RS是等价关系，充分性得证。（2）因为IAR，IAS，所以IAR∪S，即R∪S是自反的。由得，R∪S是对陈的。由得R∪S是传递的。综上，R∪S是等价关系。