第二章 二元关系
不是反自反的。
c) 不正确。令A = {1, 2, 3}，则R1 = {<1, 2>, <2, 1>}, R2 = {<2, 3>, <3, 2>}都是对称的，但
R1 ? R2 = {<1, 3>}不是对称的。
d) 不正确。令A = {1, 2, 3}，则R1 = {<1, 2>, <3, 1>}, R2 = {<2, 3>, <1, 1>}都是反对称的，
但R1 ? R2 = {<1, 3>, <3, 1>}不是反对称的。
e) 不正确。令A = {1, 2, 3}，则R1 = {<1, 2>, <3, 1>, <3, 2>}, R2 = {<2, 3>, <1, 1>}都是传递
的，但R1 ? R2 = {<1, 3>, <3, 1>, <3, 3>}不是传递的。
8. 证明：
a) 对于任意k ? N，因为Rs = Rt ，所以Rs+k = Rs ?Rk = Rt ?Rk = Rt+k 。 b) 用关于k的归纳法证明。 c)
i)
当k=0时，
Rs+i = Rs+i。所以命题成立。
ii) 假设当k=m时命题成立，即Rs + mp + i = Rs + i。 则当k=m+1时，因为Rs + (m+1) p + i=Rs + p + mp+ i=Rt + mp + i=Rt ?Rmp+i =Rs ?Rmp+i =Rs + mp + i。 由归纳假设，Rs + (m+1) p + i = Rs + mp + i = Rs + i。
由i) ii)可知对于任意k, i ? N，均有Rs + kp + i = Rs + i 。 若k ? t-1，则Rk ? {R0, R1, …, Rt-1}；
若k ? t，则k = s + (t-s)q + r，即k = s + pq + r；（其中，q? N, 0 ? r < t-s = p） 此时，由b)可知Rk = Rs + pq + r = Rs + r ? {R0, R1, …, Rt-1}。 所以，若k ? N，则Rk ? {R0, R1, …, Rt-1}。
习题2.5
2.
使t (R1 ? R2) ? t ( R1 ) ? t ( R2 ) 的R1 和R2 的具体实例如下： A = {1, 2}，R1 = {<1, 2>}，R1 = {<2, 1>}；
则t ( R1 ) = R1 ，t ( R2 ) = R2 ，t (R1 ? R2) = {<1, 2>, <2, 1>, <1, 1>, <2, 2>}， 故真包含。 4.
b) 使s (R1 ? R2) ? s ( R1 ) ? s ( R2 ) 的R1 和R2 的具体实例如下： A = {1, 2}，R1 = {<1, 2>}，R1 = {<2, 1>}；
则s ( R1 ) = s ( R2 ) = {<1, 2>, <2, 1>}，s (R1 ? R2) = s(?) = ?。 故真包含：s (R1 ? R2) ? s ( R1 ) ? s ( R2 )。
b) 使t (R1 ? R2) ? t ( R1 ) ? t ( R2 ) 的R1 和R2 的具体实例如下： A = {1, 2, 3}，R1 = {<1, 2>, <2, 1>}，R1 = {<1, 3>, <3, 1>}；
则t ( R1 ) = {<1, 2>, <2, 1>, <1, 1>, <2, 2>}，t ( R2 ) = {<1, 3>, <3, 1>, <1, 1>, <3, 3>}， t (R1 ? R2) = s(?) = ?。
故真包含：t (R1 ? R2) ? t ( R1 ) ? t ( R2 )。
6. 令A = {1, 2}，R = {<1, 2>}，则
- 5 -
第二章 二元关系
ts(R) = t ({<1, 2>, <2, 1>}) = {<1, 2>, <2, 1>, <1, 1>, <2, 2>} st(R) = s ({<1, 2>}) = {<1, 2>, <2, 1>} 所以，st(R) ? ts(R)。
习题2.6
1. a) b) c) d) e) f) 2. 3.
正确； 正确； 不正确；（不自反） 不正确；（不自反） 不正确；（不一定对称） 正确。
R的所有极大相容类为：{x1, x2, x3}，{x1, x3, x6}，{x3, x4, x5}，{x3, x5, x6}。
n2?n2A上共有2个不相同的相容关系。
习题2.7
1.
a) 不正确；（不自反） b) 不正确；（不自反） c) 不正确；（不自反） d) 不正确；（不传递，< -1, 0 > ? R, < 0, 1 > ? R, 但<-1, 1> ? R） e) 不正确；（不对称） f) 不正确；（不对称） g) 不正确；（不传递） h) 正确； i) 不正确。（不自反，i = 10k时，
2. 不对。
应加上条件：对于任意x?A，总存在y?A使得
证明：
① 已知条件：若
先证对称性：若
再证传递性：若
- 6 -
第二章 二元关系
所以R传递。 因此，R时等价关系。
② 已知条件：R是等价关系。 若
习题2.8
1. a) b) c) d) e) f) g) h) 4. a) b) 6. a) b) c)
半序；
半序、全序、良序； 无；（不是反对称的） 无；（不是传递的） 半序； 无；（不是传递的） 无；（不是传递的） 拟序。
设R是集合A上的二元关系，证明：
R是A上的半序，当且仅当R ? R-1 = IIA且R = R*。 自反、反对称 ___________ _______传递 R是A上的拟序，当且仅当R ? R-1 = ? 且R = R+。 反自反 ___________ _______传递
断言中为真的有：x4Rx1, x1Rx1。 P的最小元：无；P的最大元：x1 ；
P的极小元：x4和x5；P的极大元：x1 。
{x2, x3, x4}的上界：x1；下界：x4；上确界：x1；下确界：x4。 {x3, x4, x5}的上界：x1, x3；下界：无；上确界：x3；下确界：无。 {x1, x2, x3}的上界：x1；下界：x4；上确界：x1；下确界：x4。
7. a) b) c) d) 8. 9.
< I, ? >中的非空子集I无最小元。 < I+, |>（“|”为整除关系）中的非空子集{x | x >4}无最大元。
- 7 -