Question

离散数学证明题

设R是一个二元关系，设S={<a,b> |存在某个C，使<a,c>∈R且<c,b>∈R}，证明R是一个等价关系，则S也是一个等价关系。

Answer 1

http://hi.baidu.com/lca001/blog/item/89a860d9e1d2692732fa1cc6.html?timeStamp=1294986553953
证明由R是一个等价关系,故R是自反,对称和传递的.
对任意a∈X,由R是自反的,故<a,a>∈R, 由<a,a>∈R和<a,a>∈R得<a,a>∈S, 故S也是自反的;
如果<a,b>∈S,则存在c∈X,使<a,c>∈R且<c,b>∈R,由R是对称的,故<c,a>∈R,<b,c>∈R,由<b,c>∈R和<c,a>∈R,则<b,a>∈S,故S是对称的;
如果<a,b>∈S,<b,c>∈S,则存在d,e∈X有<a,d>∈R且<d,b>∈R, <b,e>∈R且<e,c>∈R,R是传递的,故由<a,d>∈R和<d,b>∈R得<a,b>∈R,由<b,e>∈R且<e,c>∈R得<b,c>∈R,再由<a,b>∈R和<b,c>∈R得<a,c>∈S,故S是传递的；
S是自反,对称和传递的,故S是一个等价关系.

实际上该题中的S恰是R的平方关系,故该题也可表示为:如果R是等价关系,则R2也是等价关系

Answer 2

设R是A上一个二元关系，

 

试证明若R是A上一个等价关系，则S也是A上的一个等价关系。

Answer 3

并且用归纳法去证明它的正确。 N个正方形 ！ 不是N个小块！ 如果是这数学最多是个小学奥数。。 (Think of a Hershey’s bar.)这个你