发布时间 : 星期五 文章二元关系(离散数学)更新完毕开始阅读
第二章 二元关系
不是反自反的。
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>}不是传递的。
8. 证明:
a) 对于任意k ? N,因为Rs = Rt ,所以Rs+k = Rs ?Rk = Rt ?Rk = Rt+k 。 b) 用关于k的归纳法证明。 c)
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 。 若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>},则
- 5 -
第二章 二元关系
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. 3.
正确; 正确; 不正确;(不自反) 不正确;(不自反) 不正确;(不一定对称) 正确。
R的所有极大相容类为:{x1, x2, x3},{x1, x3, x6},{x3, x4, x5},{x3, x5, x6}。
n2?n2A上共有2个不相同的相容关系。
习题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, ? R,则 ? R。
先证对称性:若 ? R,则由于R自反,所以 ? R,由上式有 ? R。 所以R对称。
再证传递性:若 ? R, ? R,则因为R对称,所以 ? R。由已知条件,因为 ? R且 ? R,所以 ? R。
- 6 -
第二章 二元关系
所以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}无最大元。
- 7 -