离散数学(第五版)清华大学出版社第4章习题解答(2)

1° 若f:A→B是实数区间上的初等函数，为了求ranf 首先要找到f的单调区间。针对f的每个单调区间求出f的该区音的最小和最大值，从而确定f在这个区间的局部值域。ranf 就是所有局部值域的并集。对于分段的初等函数也可以采用这种方法处理。

2° 若f是用列元素的方法给出的，那么ranf就是所有有序对的第二元素构成的集合。

本题中只有f1是定义于实数区间上的初等函数。易见，指数函数的图像是严格单调上升的，并且所有的函数值都大于0。从而知道f1是单射的，但不是满射的。对于f2，由

f2(1) = f2(?1) = 1可知，它不是单射的。但ranf2=N，所以，它是满射的。f3既不是单射的，也不是满射的，因为f3(3)= f3(0)=0,且f3={0,1,2}.f4是 53

单射的，但不是满射的。因为m≠n时,必有≠,但<1,1>?ranf4. 4.9 A：③； B：①； C：⑦； D：⑤； E：⑨

分析 1）先求出T的特征函数χT ={,,}，它是从S到{0,1}的函数。而Ss中的函数是从{a,b,c}到{a,b,c}的函数，这就是说该函数应包含 3个有序对，有序对的第一元素是a,b,c，而第二元素应该从a,b,c中选取（可以重复选取）。不难年出只有①满足要求。

（2）等价关系R对应的划分就是商集S/R。检查R的表达式，如果∈R，那么 x,y 就在同一个等价类。不难看出 S 中的元素被划分成两个等价类：{a,b},{c}，因而对应的划分有2个划分块。

考虑自然映射g:S→S/R它将,S 中的元素所在的等价类，即将 a 映到[a]={a,b}，将b映到[b]={a,b}，将c映到[c]={c}，将g写成集合表达式就是 g={,,}.

通常的自然映射是满射的，但不一定是单射的，除非等价关系为恒等关系，这时每个等价类只含有一个元素，不同元素的等价类也不同，g就成为双射函数了。 4.11 (1)

R={<1,1>,<1,2>,<1,3>,<1,4>,<1,5>,<1,6>,<2,2>,<2,4>,<2,6>, <3,3>,<3,6><4,4>,<5,5>,<6,6>}. (2)

R={<1,1>,<2,1>,<2,2>,<3,1>,<3,3>,<4,1>,<4,2>,<4,4>,<5,1>, <5,5>,<6,1><6,2>,<6,3>,<`6,6>}.

(3) R={<1,2>,<1,3>,<2,1>,<2,3>,<2,4>,<3,1>,<3,2>,<3,4>,<3,5> , <4,2>,<4,3><4,5>,<4,6>,<5,3>,<5,6>,<6,4>,<6,5>}.] 54

4.12 对称性 4.13 R1oR2={}, R2oR1={,}, R2={,,}, 1

R3={,,}, 2 4.14 图4.7

分析 根据闭包的计算公式

r(R)=RUR0,s(R)=RUR?1,t(R)=RUR2UL 可以得到由关系图求闭包的方法.

设G是R的关系图,G的结点记为x1,x2,L,xn,r(R),s(R),t(R)的关系图分别记作Gr,Gs和Gt.

为求Gr,先将图G 的结点和边拷贝到Gr中缺少环的结点都加上环就得到了r(R)的关系图.

为求Gs,也须将图G 拷贝到Gs,然后检查Gs的每一对结点xi和xj(i≠ j).如果在xi和xj之间只存在一条单向的边,就在这两个结点间加上一条方向相反的边.当Gs中所有的单向边都变成双向边以后就得到了s(R)的关系图.

最后拷虑Gt.首先将图 G 拷贝到Gt,然后从x1开始依次检查x1,x2,L,xn.在 55

检查结点xi(i=1,2,L,n时，要找出从xi出发经过有限步（至少1步，至多n步）) 可达的所结点（包括xi自己在内）。如果从xi到这种结点之间缺少边，就把这条边加到G 中，当n个结点全部处理完毕，就得到t(R)的关系图。 t

以本题为例，依次检查结点a,b,c,d从a出发可达b,.c,d,e四个结点，所以图Gt中应该加上a→c,a→d和的边。从b出发可达c,d,e三个结点，所以，图Gt中应该加上b→d的边。从c出发可达c和d，在Gt中应该加上边c→c，即通过c的环，类似地分析可以知道，在Gt中还应该加上过d的环。 4．15 若S不是单元集，则P(S)?{?}不构成S的划分。

4．16 在图4.8（1）中极小元、最小元是1，极大元、最大元是24，在图4.8(2)中极小元、最小元是1，极大元是5，6，7，8，9，没有最大元。 4．17 （1）不能； （2）能； （3）不能。

分析 函数和关系的区别在于它们的对应法则。在关系R的表达式中，如果∈R，就说x对应到y，对于二元关系R，这种对应可以是一对一的，多对一的和一对多的。这里的一对多指的是一个x对应到多个y，但是对于函数，则不允许这种一对多的对应。至于单射函数，不但不允许一对多，也不允许多对一，只能存在一对一的对应。为了判别一个关系是否为函数，就要检查关系的对应中是否存在一对多的情况。如本题中的（1）式，<1,2>和<1,1>同时在关系中出现，因此不是函数。又如（3）式，<1,1>和<1,-1>也同时在关系中出现，破坏了函数定义。

4．18 当R=IS时满足要求。 56

4．19 fof,gof,fog,hog,fogoh∈NN，且 fof(n)=n+2.go f(n)=2n+2, fog(n)=2n+1.hog(n)=0, goh=?0 n为偶数 ?2 n为奇数, ?

?1 n为偶数 fogoh(n)=? ?3 n为奇数.

分析 注意合成的正确表示方法。表示f和g合成的方法有两种： 1°说明fog是从哪个集合到个集合的函数，然后给出fog(x)的计算公式。

2° 给出fog的集合表达式。

本题中的结果都采用了第一种表示方法，先说明地果函数是从N到N的函数，然后分别给出函数值的计算公式。也可以彩用第二种方法，如 fof ={|n∈N},

fogoh={,z|x,y∈N且x为偶数,y为奇数}.

但是，如果写成fo f =n+2就错了，因为fo f是函数，是有序对的集合，与函数值fof(n)是根本不同的两回事，不能混为一谈。 4．20 f?1:R×R→R×R, ?1x+y x?y

f ()=< 2 , 2 >.

分析 首先由f的双射性确定f?1一定存在，然后通过f的定义求出反函数的对应法则。设f将对应到。根据f的定义有 =?x+y=u∧x?y=v ?2x=u+v∧2y=u?v?x=u+v∧y=u?v. 22

因而反函数的对应法则是对应到 u+v,u?v 。 22

4．21 （1） 如下列出gof的对应关系 57

x0 1 2 3 4 5 6 7 8… f(x) 1 2 3 4 0 5 6 7 8… g(f(x)) 3 1 3 2 0 3 3 3 4… 从而得到 gof:N→N ?

?3 x=0,2或大于等于5的奇数 ?1 x=1 gof(x)=?2 x=3 ?

?x x≥6且x为偶数 ?2

?0 x=4 ?

gof是满射的，但不是单射的。 （2） gof({0,1,2})={1,3}.

4．22 （1）P(A)={?,{a},{b},{a,b}}, BA={f,f ,f ,f },其中 1 2 3 4

f1={,{b,0>, f2 ={}, f2={,{b,0>, f4={}, （2）令f:P(A)→BA，且

f(?)= f1,f({a})= f2,f({b})= f3,f({a,b})= f4

分析 对于任意集合A，都可以构造从P(A)到{0,1}A的双射函数，任取A的子集B∈P(A),B的特征函数χB:A→{0,1}定义为 ?1 x∈B χ (x)=? B0 x∈A?B ?

不同的子集的特征函数也不同，因此，令 ?:P(A)→{0,1}A ?(B)=χB

?是P(A)到{0,1}A的双射，在本题的实例中的?是?(?)= f,?({a})= f , 13 58

?({b})= f2,?({a,b})= f4. 4．23 （1） f:A→B,f(x)=2x （2） f:A→B,f(x)=sinx .

分析 给定集合A，B，如何构造从A到B的双射？一般可采用下面的方法处理。 1° 若A，B都是有穷集合，可以先用列元素的方法表示A，B，然后顺序将A中的元素与B中的元素建立对应，如习题4.22.