国防科大版离散数学习题答案

精品文档

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>}不是传递的。

10. 证明：

a) 对于任意k ? N，因为Rs = Rt ，所以Rs+k = Rs ?Rk = Rt ?Rk = Rt+k 。 b) 用关于k的归纳法证明。 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 。 m) 若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>}，则

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.

正确； 正确； 不正确；（不自反） 不正确；（不自反） 不正确；（不一定对称） 正确。

R的所有极大相容类为：{x1, x2, x3}，{x1, x3, x6}，{x3, x4, x5}，{x3, x5, x6}。

3. A上共有

个不相同的相容关系。

习题2.7

1.

a) 不正确；（不自反） b) 不正确；（不自反） c) 不正确；（不自反） d) 不正确；（不传递，< -1, 0 > ? R, < 0, 1 > ? R, 但<-1, 1> ? R） e) 不正确；（不对称） f) 不正确；（不对称） g) 不正确；（不传递） h) 正确； i) 不正确。（不自反，i = 10k时， ? R）

2. 不对。

应加上条件：对于任意x?A，总存在y?A使得 ? R。 3.

证明：

① 已知条件：若 ? R， ? R，则 ? R。

先证对称性：若 ? R，则由于R自反，所以 ? R，由上式有 ? R。 所以R对称。

再证传递性：若 ? R， ? R，则因为R对称，所以 ? R。由已知条件，因为 ? R且 ? R，所以 ? R。 所以R传递。 因此，R时等价关系。

② 已知条件：R是等价关系。 若 ? R， ? R，则因为R对称，所以 ? R。又由于R传递，所以， ?R。

.

精品文档

因此，若 ? 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}无最大元。 中的非空子集(0, 1)由下确界0，但无最小元。 书上例4中的非空子集{4}有上界8和12，但无上确界。 归纳法。 归纳法。

.