好文档 - 专业文书写作范文服务资料分享网站

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

天下 分享 时间: 加入收藏 我要投稿 点赞

精品文档

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

10. 证明:

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。 则当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 。 m) 若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) 2.

正确; 正确; 不正确;(不自反) 不正确;(不自反) 不正确;(不一定对称) 正确。

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

3. A上共有

个不相同的相容关系。

习题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) 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}无最大元。 中的非空子集(0, 1)由下确界0,但无最小元。 书上例4中的非空子集{4}有上界8和12,但无上确界。 归纳法。 归纳法。

.

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

精品文档d)不正确。令A={1,2,3},则R1={,},R2={,}都是反对称的,但R1?R2={,}不是反对称的。e)不正确。令A={1,2,3},则R1={,,},R2={<2
推荐度:
点击下载文档文档为doc格式
5d9la67lt71xep036fj71ujtp7zr5k019hs
领取福利

微信扫码领取福利

微信扫码分享