精品文档
dom R1 = {1, 2, 3} dom R2 = {1, 2, 4} ran R1 = {2, 3, 4} ran R2 = {2, 3, 4} dom (R1 ? R2) = {1, 2, 3, 4} ran (R1 ? R2) = {4}
3. 证明：（根据定义域和值域的定义进行证明） 因为
x ? dom (R1 ? R2) 当且仅当 有y ? B使得
若x ? ran (R1 ? R2)，则
有x ? A使得
有x ? A使得
所以，ran (R1 ? R2) ? ran (R1) ? ran (R2) 。
4.
L = {<1, 2>, <1, 3>, <1, 6>, <2, 3>, <2, 6>, <3, 6> }；
D = {<1, 1>, <1, 2>, <1, 3>, <1, 6>, <2, 2>, <2, 6>, <3, 3>, <3, 6>, <6, 6> }； L ? D = { <1, 2>, <1, 3>, <1, 6>, <2, 6>, <3, 6> }。 5.
a) ?上的空关系?；
b) 集合 {1, 2 } 上的二元关系 { <1, 1> }； c) 集合 {1, 2 } 上的二元关系 { <1, 1> } ；
d) 集合 {1, 2, 3 } 上的二元关系 { <1, 2>, <2, 1>, <1, 3> } ； 6.
若R, S自反， 则R ? S , R ? S自反，R – S , R ? S必不自反。 若R, S反自反， 则R ? S , R ? S , R – S , R ? S反自反。 若R, S对称， 则R ? S , R ? S , R – S , R ? S对称。
若R, S反对称， 则R ? S , R – S反对称，R ? S , R ? S不一定反对称。
.
精品文档
若R, S传递， 则R ? S传递，, R – S , R ? S , R ? S不一定传递。 8.
a) S是对称的、传递的； b) S是自反的、对称的； c) S是反对称的、传递的；
d) S是反自反的、反对称的、传递的； 8.
n ( Am ) = nm ； n (?( Am ) ) = 2nm ；
nm因为R ? Am，所以A上共有2个m元关系。
10.
证明： 用反证法。
假设R不是反对称的，即 存在a, b ? A，使得
所以假设不成立。即R是反对称的。 11.
证明：因为R = {
证明：因为dom R ? fld R = ? ( ? R )，ran R ? fld R = ? ( ? R )， 所以，R ? dom R ? ran R ? ? ( ? R ) ? ? ( ? R ) 。
习题2.2
1.
R是自反的、对称的、传递的。 2.
(1) 自反的；
(2) 反对称的、传递的； (3) 自反的、对称的、传递的；
.
精品文档
(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)
n个不相同的反对称关系；
A上共有2n个不相同的既是对称的又是反对称的关系；
习题2.3
1. 最多能有n(A) 个元素为1。 2. 证明：
i) R ? R-1为A上包含R的最小对称关系 ① R ? R ? R-1。所以，R?R-1包含R。
② 因为对于任意
对于任意
由①②③可知，R ? R-1为A上包含R的最小对称关系。
ii) R ? R-1为A上包含在R中的最大对称关系
.
精品文档
① R ? R-1 ? R。所以，R ? R-1包含在R中。
② 因为对于任意
对于任意
又由于R?对称，所以
由①②③可知，R ? R-1为A上包含在R中的最大对称关系。
习题2.4
1.
R2 ? R1 = {
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。
.
精品文档
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)
.
正确； 正确； 不正确；（不自反） 不正确；（不自反） 不正确；（不一定对称） 正确。
国防科大版离散数学习题答案
