习题解答等价关系ppt课件

1、习题解答习题解答等价关系等价关系习题习题1 1：假设关系：假设关系R R和和S S是自是自反的反的, ,对称的和可传送的对称的和可传送的, ,证证明明RSRS也是自反、对称和可也是自反、对称和可传送的。传送的。证明证明 设设R R和和S S是是X X上的自反关上的自反关系。系。1 1对恣意对恣意xX,xX,有有RR和和S,S,所以所以RS,RS,即即RSRS在在X X上是自反的。上是自反的。2 2对恣意对恣意RS,RS,有有RR且且S,S,由于由于R R和和S S是对称的是对称的, ,故必有故必有RR且且 y,x SS。即。即RS,RS,所以所以RSRS在在X X上是对称的。上是对称的。3 3

2、对恣意对恣意RS, RSRS, RS那么有那么有RR且且SS和和RR且且SS由于由于R R和和S S是传送的是传送的, ,故故R,S,R,S,即即RS,RS,所以所以RSRS在在X X上是传送的。上是传送的。 习题习题2 2：设：设R R是集合是集合X X上的一上的一个自反关系个自反关系, ,求证：求证：R R是对称是对称和传送的和传送的, ,当且仅当当且仅当和和在在R R之中之中, ,并有并有RR。证明证明 设设R R是集合是集合X X上的一个自上的一个自反关系反关系, ,假设假设R R是是X X上对称和传上对称和传送的送的, ,那么当恣意那么当恣意a,b,cX,a,b,cX,假设有假设有R

3、R且且RR那么那么 R R且且RR故得故得 R R 反之反之, ,由由R,R,R,R,必有必有R,R,那么对恣意那么对恣意a,bX,a,bX,假设假设RR，因因R R是集合是集合X X上的一个自反关上的一个自反关系，有系，有R,R,那么得到那么得到R,R,故故R R是对称的。是对称的。假设假设RR且且R,R,那么那么R RR,b,cR,所以所以R,R,即即R R是可传送的。是可传送的。 例题例题3 3：设：设 A1,A2,AKA1,A2,AK是集合是集合A A的一个划分的一个划分, ,我们定义我们定义A A上的上的一个二元关系一个二元关系R,R,使使R R 当且仅当当且仅当 a a和和b b在

4、这个划分在这个划分的同一块中。证明的同一块中。证明R R是自反、是自反、对称和传送的。对称和传送的。证明证明 设对恣意设对恣意aA,aA,那么那么必存在必存在Ai,Ai,使使aAi ,aAi ,因因a a 与与a a必可看作在同一块中必可看作在同一块中, ,故有故有RR。即。即R R是自反的。是自反的。 设设a,bA,a,bA,假设有假设有R,R,那么那么a a 与与b b必在同必在同一块中一块中, ,故故b b 与与a a亦在同一块亦在同一块中中,R,R。即。即R R是对称是对称的。的。 设设a,b,cA,a,b,cA,假设有假设有RR,RR,那么那么必必i,i,使得使得aAi bAi ,aAi bAi ,且必且必 j,j,使使bAj cAj,bAj cAj,这这样样i = ji = j。由于假设由于假设i j ,i j ,那么那么bAiAjbAiAj。故。故AiAjAiAj, ,这与这与Ai, AjAi, Aj是是A A的划分块矛的划分块矛盾。由此得盾。由此得a,b,ca,b,c均属同一均属同一分块分块Ai,Ai,因此因此R,R,即即R R是传送的。是传送的。 例题例题4 4： 设设R R是集合是集合A A上的一上的一个自反个自反, ,对称和传送的关系对称和传送的关系, ,假设假设A1,A2,AKA1,A2,AK是