最新洪帆《离散数学基础》(第三版)课后习题答案 联系客服

发布时间 : 星期五 文章最新洪帆《离散数学基础》(第三版)课后习题答案更新完毕开始阅读

精品文档

(2) {1,2,3,4,5,6,7,8,9,10,11,12} 答:

35、对于下列集合,画出偏序关系’整除’的次序图,并指出哪些是全序 (1){2,6,24} 答: 是全序 (2){3,5,15} 答: 非全序 (3){1,2,3,6,12} 答: 非全序 (4){2,4,8,16} 答:

精品文档

精品文档

是全序 (5) {3,9,27,54} 答: 是全序

36、如果?是集合A中的偏序关系,且B?A,试证明:??(B?B)是B上的偏序关系。

证明:对任意的a?B,必有(a,a)?B?B,又因为a?A及?的自反性,所以

(a,a)??,因此(a,a)???(B?B),故??(B?B)是自反的。

对任意的a,b?B,若(a,b)???(B?B),且(b,a)???(B?B),则有(a,b)??,且(b,a)??,由?的反对称性,有a?b,因此??(B?B)是反对称的。 对任意的a,b,c?B,若(a,b)???(B?B),(b,c)???(B?B),则(a,b)??,且

(b,c)??,由?的可传递性必有(a,c)??,由B?B的定义,(a,c)?B?B,于是(a,c)???(B?B),因此??(B?B)是可传递的,由上得证??(B?B)是B上的

偏序关系。

37、 给出一个集合A的例子,使得包含关系?是幂集2A上的一个全序。 答:A?{1,2,3},2A?{?,{1},{2},{3},{1,2},{2,3},{1,3},{1,2,3}}

2A上的关系??{?,{1},{1,2},{1,2,3}}。

38、给出一个关系,使它既是某一集合上的偏序关系又是等价关系

答:A?{1,2,3},??{(1,1),(2,2),(3,3)},显然?具有自反性,对称性,可传递性,还具有反对称性,因此既是A上的;偏序关系,也是等价关系。

39、图2-12表示{1,2,3,4}上的四个偏序关系图。画出每一个的次序图,并指出其中哪些是全序,哪些是良序 答:

精品文档

精品文档

(a)

??{(1,1),(2,2),(3,3),(4,4),(1,2),(3,2),(3,1),(3,4),(1,4)} 不是全序,也不是良序

(b)

??{(1,1),(2,2),(3,3),(4,4),(1,3),(2,3),(1,4),(2,4)}不是全序也不是良序

(c)

??{(1,1),(2,2),(3,3),(4,4),(3,1),(1,2),(3,2),(1,4),(3,4),(4,2)} 是全序也是良序

精品文档

精品文档

(d)

??{(1,1),(2,2),(3,3),(4,4),(3,1),(4,3),(4,1),(4,2)}非全序,也不是良序。

40、 一个集合上的自反和对称关的关系称为相容关系

(1) 设A是人的集合,?是集合A上的关系,定义为当且仅当a是b的朋友时,有a?b,试证明?是A上的相容关系。

证明:对?a?A,因为任何的人都是自己的朋友,也就是有a?a,因此?具有自反性,若a?b,也就是a是b的朋友,那么一定有b是a的朋友,则有b?a,因此?是对称的,因此?是A上的相容关系。

(2) ?是正整数集N上的关系,当且仅当两个正整数n1和n2中有相同的数字时,

n1?n2 ,试证明?是一个相容关系;

证明:显然,对?n?N,有n?n,因此?具有自反性;若n1?n2,则表示n1和n2中有相同的数字,因此n2和n1也有相同的数字,因此n2?n1。所以?具有对称性,所以?是N上的一个相容关系。 (3) 再举出一个相容关系的例子

答:等价关系都是相容关系,反之则不成立。

(4) 设?1和?2是A上的两个相容关系,?1??2是相容关系吗??1??2是相容关系吗?

答:?1??2和?1??2都是相容关系,前题30中证明了若?1和?2是A上的等价关系,则?1??2也是等价关系,而?1??2具有自反性和对称性。

精品文档