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

第二章 二元关系

(4) 自反的、传递的； (5) 无； (6) 对称的；

(7) 自反的、反对称的、传递的； (8) 对称的； (9) 对称的； (10) 反对称的； (11) 自反的、反对称的； (12) 反对称的、传递的。 4.

b) A上共有2c) A上共有2d) A上共有2n2?n个不相同的自反关系； 个不相同的反自反关系； 个不相同的对称关系；

n2?n2n2?nn2?n2e) A上共有2?3f)

nn个不相同的反对称关系；

A上共有2个不相同的既是对称的又是反对称的关系；

习题2.3

1. 最多能有n(A) 个元素为1。 2. 证明：

i) R ? R-1为A上包含R的最小对称关系 ① R ? R ? R-1。所以，R?R-1包含R。

② 因为对于任意 ? R ? R-1，有 ? R或 ? R-1。 若 ? R，则 ? R-1；若 ? R-1，则 ? R。 因此， ? R ? R-1。所以，R?R-1为A上的对称关系。 ③ 设R?为任意的A上包含R的对称关系，则

对于任意 ? R ? R-1，有 ? R或 ? R-1。 若 ? R，由于R?包含R，所以 ? R?； 若 ? R-1，则 ? R，由于R?包含R，所以 ? R?，而R?对称，所以 ? R?。 因此，总有 ? R?。所以，R ? R-1 ? R?。

由①②③可知，R ? R-1为A上包含R的最小对称关系。

ii) R ? R-1为A上包含在R中的最大对称关系

- 13 -

第二章 二元关系

① R ? R-1 ? R。所以，R ? R-1包含在R中。

② 因为对于任意 ? R ? R-1，有 ? R且 ? R-1。 ? R，所以 ? R-1； ? R-1，所以 ? R。 因此， ? R ? R-1。所以，R ? R-1为A上的对称关系。 ③ 设R?为任意的A上包含在R中的对称关系，则

对于任意 ? R?，由于R?包含在R中，所以 ? R；

又由于R?对称，所以 ? R?，而R?包含在R中，所以 ? R，因此， ? R-1； 因此，总有 ? R ? R-1。所以，R ? R?R-1。

由①②③可知，R ? R-1为A上包含在R中的最大对称关系。

习题2.4

1.

R2 ? R1 = {}； R1 ? R2 = {, }； R12 = {, , }； R22 = {, }；

2. m = 1, n = 16。

4. A = {1, 2, 3}

令R1 = {<1, 2>, <1, 3>}；R2 = {<2, 2>}；R3 = {<3, 2>}；则 R1 ? ( R2 ? R3 ) = ?；( R1 ? R2 ) ? ( R1 ? R3 ) = {<1, 3>}； 所以，R1 ? ( R2 ? R3 ) ? ( R1 ? R2 ) ? ( R1 ? R3 ) 。

令R2 = {<2, 2>}；R3 = {<2, 3>}；R4 = {<2, 1>, <3, 1>}；则 ( R2 ? R3 ) ? R4 = ?；( R2 ? R4 ) ? ( R3 ? R4 ) = {<2, 1>}； 所以，( R2 ? R3 ) ? R4 ? ( R2 ? R4 ) ? ( R3 ? R4 ) ； 5.

a) 正确。 b) 不正确。令A = {1, 2}，则R1 = {<1, 2>}, R2 = {<2, 1>}都是反自反的，但R1 ? R2 ={<1, 1>}

不是反自反的。

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

9. 证明：

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。

- 14 -

第二章 二元关系

f)

则当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>}，则

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)

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

- 15 -

第二章 二元关系

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

3. A上共有2

n2?n2个不相同的相容关系。

习题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)

半序；

半序、全序、良序； 无；（不是反对称的） 无；（不是传递的）

- 16 -