发布时间 : 2024/5/5 21:20:46 星期日 文章二元关系（离散数学）更新完毕开始阅读ac1e8650fd0a79563d1e72cd

第二章 二元关系

第二章 二元关系

习题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使得 ? (R1 ? R2) 当且仅当 有y ? B使得 ? R1 或 ? R2 当且仅当 有y ? B使得 ? R1 或有y ? B使得 ? R2 当且仅当 x ? dom (R1) 或 x ? dom (R2) 当且仅当 x ? dom (R1) ? dom (R2) 所以，dom (R1 ? R2) = dom (R1) ? dom (R2) 。 因为

若x ? ran (R1 ? R2)，则

有x ? A使得 ? (R1 ? R2) ； 有x ? A使得 ? R1 且 ? R2 ；

有x ? A使得 ? R1 且 有x ? A使得 ? R2 ； x ? ran (R1) 且 x ? ran (R2) ； x ? ran (R1) ? ran (R2) 。

所以，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，使得 ? A, ? A 且a ? b。 因为R是传递的，所以由 ? A且 ? A可知 ? A。 这与R反自反性质矛盾。

所以假设不成立。即R是反对称的。 11.

证明：因为R = { | x, y ? A 且 ? R} = {{{x}, {x, y}} | x, y ? A 且 ? R } 所以，? R = {{x}, {x, y} | x, y ? A 且 ? R }。 所以，?(?R) = {x | x ? A且有y ? A使得 ? R }?{y | y ? A且有x ? A使得?R }。 = dom R ? ran R 。 即：fld R = dom R ? ran R 。 12.

- 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，有 ? 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中的最大对称关系 ① 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>}

- 4 -