第二章 二元关系
第二章 二元关系
习题2.1
1. a) b) 2.
R = {<0, 0>, <0, 2>, <2, 0>, <2, 2>} R = {<1, 1>, <4, 2>}
R1 ? R2 = {<1, 2>, <2, 4>, <3, 3>, <1, 3>, <4, 2>} R1 ? R2 = {<2, 4>} 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> }；
- 1 -
第二章 二元关系
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不一定传递。 7.
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 = {
- 2 -
第二章 二元关系
证明：因为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.
a) A上共有2b) A上共有2c) A上共有2n2?n个不相同的自反关系； 个不相同的反自反关系； 个不相同的对称关系；
n2?n2n2?nn2?n2d) A上共有2?3nn个不相同的反对称关系；
e) A上共有2个不相同的既是对称的又是反对称的关系；
习题2.3
1. 最多能有n(A) 个元素为1。 2. 证明：
- 3 -
第二章 二元关系
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>}
- 4 -