《离散数学—11等价关系习题解答》由会员分享，可在线阅读，更多相关《离散数学—11等价关系习题解答（14页珍藏版）》请在金锄头文库上搜索。
1、习题解答 （等价关系）习题1：如果关系R和S是自 反的,对称的和可传递的,证 明RS也是自反、对称和可 传递的。证明 设R和S是X上的自反关 系。 1）对任意xX, 有R和S, 所以RS, 即RS在X上是自反的。2）对任意RS, 有R且S, 因为R和S是对称的, 故必有R且S 。即RS, 所以RS在X上是对称的。3）对任意 RS, RS 则有R且S 和R且S 因为R和S是传递的, 故R,S, 即RS, 所以RS在X上是传递的。习题2：设R是集合X上的一 个自反关系,求证：R是对称 和传递的,当且仅当 和在R之中,并有 R。证明 设R是集合X上的一个自 反关系,如果R是X上对称和传 递的,则当任
2、意a,b,cX, 若有R且R 则 R且R 故得 R反之,由 R,R,必有R, 则对任意a,bX, 若R， 因R是集合X上的一个自反关 系，有R, 则得到R, 故R是对称的。若R且R, 则RR, 所以 R,即R是可传递的。例题3：设 A1,A2,AK是集合A的 一个划分,我们定义A上的一 个二元关系R,使R 当且仅当 a和b在这个划分 的同一块中。证明R是自反 、对称和传递的。证明 设对任意aA,则必 存在Ai,使aAi ,因a 与a必 可看作在同一块中,故有 R。即R是自反的。设a,bA,若有 R,则a 与b必在同一 块中,故b 与a亦在同一块中 ,R。即R是对称的 。设a,b,cA,若有 RR,则必 i, 使得aAi bAi ,且必 j,使bAj cAj,这样i = j。 因为若i j ,则bAiAj 。故AiAj,这与Ai, Aj 是A的划分块矛盾。由此得 a,b,c均属同一分块Ai,因此 R,即R是传递的。例题4： 设R是集合A上的一 个自反,对称和传递的关系, 若A1,A2,AK是集合A 的子集的集合,当i j 时 ,Ai Aj,使得a和b在同一个子 集中,
