洪帆《离散数学基础》(第三版)课后习题答案(6)

是全序 (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}上的四个偏序关系图。画出每一个的次序图，并指出其中哪些是全序，哪些是良序 答：

26

(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)} 是全序也是良序

27

(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具有自反性和对称性。

28

第3章 函数

1. 以下关系中哪一个构成函数？ (1) {(n1,n2)|n1,n2?N,n1?n2?10}

答：不构成函数。象的唯一性不能满足，因为(1,2),(1,3)都属于这个集合。而12,13等这样的数在N中无像，所以象的存在性也不能满足。 (2) {(n1,n2)|n1,n2?N,n2?小于n1的素数的个数} 答：是函数，象的唯一性和存在性都能满足。

2. 设A?2U?2U，B?2U，给定由A到B的关系： f?{(( U}SS,1?S|1S,?1,2)S2)S2f是函数吗？若是的话，f的值域Rf?2U吗？为什么？

答：f是函数。f的值域Rf?2U。因为对?C?2U，则C?U，则对(C,C)，

C?C?C，因此象C的像源为(C,C)。

3. 下列集合能够定义函数吗？如果能，试指出它们的定义域和值域？ (1) {(1,(2,3)),(2,(3,4)),(3,(1,4)),(4,(1,4))}

答：能定义函数。Df?{1,2,3,4}，Rf?{(2,3),(3,4),(1,4)} (2) {(1,(2,3)),(2,(3,4)),(3,(3,2))}

答：能定义函数。Df?{1,2,3}，Rf?{(2,3),(3,4),(3,2)} (3) {(1,(2,3)),(2,(3,4)),(1,(2,4))}

答：不能定义函数。因为有一对多的情况。 (4) {(1,(2,3)),(2,(2,3)),(3,(2,3))}

答：能定义函数。Df?{1,2,3}，Rf?{(2,3)}

4. 设函数f:A?B,S?A，等式f(A)?f(S)?f(A?S)成立吗？为什么？ 答：不成立。因为f(A)?f(S)?f(A?S)成立，但是f(A?S)?f(A)?f(S)不成立。下面证明f(A)?f(S)?f(A?S)。

设b?f(A)?f(S)，则b?f(A)且b?f(S)，所以必存在a?A使f(a)?b。由于所以a?S，于是a?A?S，因此b?f(A?S)，故fAb?f(S)，()f?S()f?A(S)?f(A?S)?f(A)?f(S)不成立，反例如下：

。

设A?{a1,a2,a3,a4}，S?{a2,a3}，则A?S?{a1,a4}，函数f:A?B的定义为：

f?{(a1,b1),(a2,b1),(a3,b2),(a4,b3)}。显然f(A)?{b,2b,3b，}f(S)?{b1,b2}，1f(A?S)?{b1,b3}，f(A)?f(S)?{b3}，f(A?S)?f(A)?f(S)。由上可知

f(A)?f(S)?f(A?S)不成立。

29

5 设有函数f:A?B，试证明等式f(A?B)?f(A)?f(B)，等式?Cf(A?B)?f(A)? f(成立吗？为什么？B)证明：设c?f(A)?f(B)，则c?f(A)或者c?f(B)。若c?f(A)，则存在a?A使得f(a)?c，因此有a?A?B，所以c?f(A?B)。若c?f(B)，类似地，有

c?f(A?B)，故f(A)?f(B)?f(A?B)。

反之，若c?f(A?B)，则存在b?A?B，使得f(b)?c。由并集的定义b?A或者b?B，因此c?f(A)或者c?f(B)，于是c?f(f(A?B)?f(A)?A)?f(，B)故

。由上得证f(Bf(A?B)?f(A)?f(B)。

f(A?B)?f(A)?f(B)不成立，因为f(A?B)?f(A)?f(B)，反之不成立。

证明：设c?f(A?B)，则存在a?A?B使得f(a)?c。因为a?A且a?B，所以c?f(A)且c?f(B)，因此c?f(A)?f(B)，故f(A?B)?f(A)?f(B)。 反例如下：

设A?B?{a,b,e,d}，其中A?{a,e,d}，B?{b,e}，C?{c1,c2,c3}，函数于是：A?B?{e}，f:A?B?C定义为f(a)?f(b)?c1，f(e)?c2，f(d)?c3，

f(A?B)?{c2}，f(A)?{c1,c2,c3}，f(B)?{c1,c2}，f(A)?f(B)?{c1,c2}，这里元素c1?f(A)?f(B)，但是c1?f(A?B)。

6. 设有函数f:A?B和g:B?C，使得g?f是一个内射，且f是满射。证明g是一个内射。举出一个例子说明，若f不是满射，则g不一定是内射。 证明：任取b1,b2?B，并设b1?b2。因为f是满射，所以必有a1,a2?A，使得

f(a1)?b1，f(a2)?b2，根据函数象的唯一性的条件，由b1?b2可得a1?a2。又因为g是由B到C的函数，所以有c1,c2?C，使得g(b1)?c1，。于是根据复合函数的定义，得：

g?f(1a)?g(1b)?，1cg?f(a2)?g(b2)?c2

因为g?f是内射，所以由a1?a2，可知c1?c2。此即g(b1)?g(b2)，故g是内射。 例子：

图3-1

30

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库洪帆《离散数学基础》(第三版)课后习题答案(6)在线全文阅读。