离散数学—11等价关系习题解答.ppt

《离散数学—11等价关系习题解答.ppt》由会员分享，可在线阅读，更多相关《离散数学—11等价关系习题解答.ppt（14页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、习题解答习题解答（等价关系）（等价关系）习题习题1 1：如果关系如果关系R R和和S S是自是自反的反的,对称的和可传递的对称的和可传递的,证证明明RSRS也是自反、对称和可也是自反、对称和可传递的。传递的。证明证明 设设R R和和S S是是X X上的自反关上的自反关系。系。1 1）对）对任意任意xX,X,有有RR和和S,S,所以所以RSRS,即即RSRS在在X X上是自反的。上是自反的。2 2）对任意）对任意RSRS,有有RR且且S,S,因为因为R R和和S S是对称的是对称的,故必有故必有R且且S。即即 RSy,xRS,所以所以RSRS在在X X上是对称的。上是对称的。3 3）对任意）对任

2、意RS,RS则有则有R且且S和和R且且S S因为因为R R和和S S是传递的是传递的,故故R,S,即即RSRS,所以所以RSRS在在X X上是传递的。上是传递的。习题习题2 2：设设R R是集合是集合X X上的一上的一个自反关系个自反关系,求证：求证：R R是对称是对称和传递的和传递的,当且仅当当且仅当 a,b和和 a,c在在R R之中之中,并有并有 Rb,cR。证明证明 设设R R是集合是集合X X上的一个自上的一个自反关系反关系,如果如果R R是是X X上对称和传上对称和传递的递的,则当任意则当任意a,b,cX,a,b,cX,若有若有 Ra,bR且且 Ra,cR则则 Rb,aR且且 Ra,

3、cR故得故得 Rb,cR 反之反之,由由 R,R,a,bR,R,必有必有 R,b,cR,则对任意则对任意a,bX,a,bX,若若 Ra,bR，因因R R是集合是集合X X上的一个自反关上的一个自反关系，有系，有 R,a,a R,则得到则得到 R,b,a R,故故R R是对称的。是对称的。若若 Ra,bR且且 R,b,cR,则则 RR,b,a RR,所以所以 R,a,cR,即即R R是可传递的。是可传递的。例题例题3 3：设：设 A A1 1,A,A2 2,A,AK K 是集合是集合A A的的一个划分一个划分,我们定义我们定义A A上的一上的一个二元关系个二元关系R,R,使使 R a,bR 当且

4、仅当当且仅当 a a和和b b在这个划分在这个划分的同一块中。证明的同一块中。证明R R是自反、是自反、对称和传递的。对称和传递的。证明证明 设对任意设对任意aA,aA,则必则必存在存在A Ai i,使使aAaAi i,因因a a 与与a a必必可看作在同一块中可看作在同一块中,故有故有 Ra,a R。即即R R是自反的。是自反的。设设a,bA,a,bA,若有若有 R,a,bR,则则a a 与与b b必在同一必在同一块中块中,故故b b 与与a a亦在同一块中亦在同一块中,Rb,a R。即即R R是对称的。是对称的。设设a,b,cA,a,b,cA,若有若有 RR,a,bRR,则必则必 i,i,

5、使得使得aAaAi i bA bAi i,且必且必 j,j,使使bbA Aj j c cA Aj j,这样这样i i=j=j。因为若因为若i j,i j,则则bAbAi iA Aj j。故故A Ai iA Aj j,这与这与A Ai i,A Aj j是是A A的划分块矛盾。由此得的划分块矛盾。由此得a,b,ca,b,c均属同一分块均属同一分块A Ai i,因此因此 R,a,cR,即即R R是传递的。是传递的。例题例题4 4：设设R R是集合是集合A A上的一上的一个自反个自反,对称和传递的关系对称和传递的关系,若若 A A1 1,A,A2 2,A,AK K 是集合是集合A A的子集的集合的子集的集合,当当i j i j 时时,A Ai i A Aj j,使得使得a a和和b b在同一个子在同一个子集中集中,