离散数学(屈婉玲版)第四章部分答案

（2）设有序对与有序对<5,2x+y>相等，则 x=(D),y=(E).

供选择的答案

A、B、C：① x,y可任意选择1或2；② x=1,y=1；③ x=1,y=1 或 2；x=y=2；④ x=2,y=2；⑤ x=y=1或 x=y=2；⑥ x=1,y=2；⑦x=2,y=1。

 D、E：⑧ 3；⑨ 2；⑩-2。

答案： 

    A: ⑤

B: ③

C: ①

D: ⑧

E: ⑩

4.2设S=<1,2,3,4>,R为S上的关系，其关系矩阵是

   则（1）R的关系表达式是（A）。

     （2）domR=(B),ranR=(C).

     （3）RR中有（D）个有序对。 

     （4）Rˉ1的关系图中有（E）个环。

  供选择的答案

   A :①<1,1>,<1,2>,<1,4>,<4,1>,<4,3>；

      ②<1,1>,<1,4>,<2,1>,<4,1>,<3,4>；

B、C：③1，2，3，4；④1，2，4；⑤1，4⑥1，3，4。

D、E⑦1；⑧3；⑨6；⑩7。

答案： 

    A:②

B:③

C:⑤

D:⑩

E:⑦

4.3设R是由方程x+3y=12定义的正整数集Z+上的关系，即

            {＜x,y＞︳x,y∈Z+∧x+3y=12},

则     （1）R中有A个有序对。

       （2）dom=B。

        (3)R↑{2,3,4,6}=D。

        (4){3}在R下的像是D。

       （5）R。R的集合表达式是E。

供选择的答案

A:①2;②3;③4.

B、C、D、E:④{＜3，3＞}；⑤{＜3，3＞，＜6，2＞}；⑥{0，3，6，9，12}；⑦{3，6，9}；⑧{3}；⑨Ф；⑩3。

答案：A：②。分别是：＜3，3＞＜6，2＞＜9，1＞

      B：⑦。

      C：⑤。

D：⑧。

E: ④。

4.4  设S={1,2,3},图4-13给出了S上的5个关系，则它们]只具有以下性质：

R1是A, R2是B, R3是C, R4是D, R5是E。

供选择的答案

A,B,C,D,E:①自反的，对称的，传递的；②反自反的，反对称的；

③反自反的，反对称的，传递的；④自反的；⑤反对称的，传递的；

⑥什么性质也没有；⑦对称的；⑧反对称的；⑨反自反的，对称的；

⑩自反的，对称的，反对称的，传递的

 A:④  B:⑧                    C：⑨    D:⑤                               

 E: ⑩  

4．5 设Z+={x|x∈Z∧x>0},∏1, ∏2, ∏3是Z﹢的3个划分。

        ∏1={{x}|x∈Z﹢},

        ∏2={S1,S2},S为素数集，S2=Z-S1,

        ∏3={Z+},

     则  （1）3个划分中分块最多的是A,最少的是B.

          (2)划分∏1对应的是Z+上的C, ∏2对应的是Z+上的D, ∏3对应的是Z+上的E

   供选择的答案

A,B:①∏1;②∏2;③∏3.

C,D,E:④整除关系；⑤全域关系；⑥包含关系；⑦小于等于关系；⑧恒等关系；⑨含有两个等价类的等价关系；⑩以上关系都不是。

 答案 

A  ①

B  ③

C  ⑧

D  ⑨

E  ⑤

4.6 设S={1，2，…,10},≤是S上的整除关系,则的哈斯图是(A),其中最大元是(B),最小元是(C),最小上界是(D),最大下界是(E).

供选择的答案

A: ① 一棵树; ② 一条链;  ③ 以上都不对.

B、C、D、E: ④ ；⑤ 1；⑥ 10；⑦ 6，7，8，9，10；⑧ 6；⑨ 0；⑩ 不存在。

答案： 

    A: ③(树中无环,所以答案不是①)

B: ⑩

C: ⑤

D: ⑩

E: ⑤                                                        

4.7设:N→N,N为自然数集，且

则（0）=，.

供选择的答案

A、B、C、D、E：①无意义；②1；③{1}；④0；⑤{0}；⑥；∴⑦N；

⑧{1，3，5，…}；⑨{，1}；⑩ {2，4，6，…}.

解：（0）==0，∴A=④；

={0}，∴B=⑤；

={1}，∴C=③；

①无意义；

=N，∴E=⑦.

4.8  设R、Z、N分别表示实数、整数和自然数集，下面定义函数f1、f2、f3、f4。试确定它们的性质。

f1: R→R，f(x)=2x,

f2: Z→N，f(x)=|x|.

f3: N→N，f(x)=(x)mod3,x除以3的余数，

f4: N→N×N，f(n)=。

则f1是A，f2是B，f3是C，f4是D，f4（{5}）=E。

供选择的答案

A、B、C、D：①、满射不单射；②、单射不满射；③、双射；④、不单射也不满射；⑤、以上性质都不对。

E：⑥、6；⑦、5；⑧、<5,6>;⑨、{<5,6>};⑩、以上答案都不对。

解：

f1是②、单射不满射；f2是①、满射不单射；f3是④、不单射也不满射；f4是②、单射不满射；f4（{5}）=⑨、{<5,6>}。

4.9 设f :R→R，f(x)=   x²  ，    x≥3,                                           

-2 , x<3;

 g:R→R，g(x)=x+2,                                                     

则 f〇g(x)=A,g〇f(x)=B, g〇f: R→R是 C,f-1是 D,g-1是E.              

供选答案::

A\\B:   (x+2)² ,  x≥3,           ②   x²+2 ，  x≥3,                   

-2 , x<3; -2 , x<3;

         (x+2)² ,  x≥1,               x²+2 ，  x≥3,                 

    ③                           ④                                   

-2 , x<1; 0 , x<3;

C: ⑤ 单射不满射；⑥ 满射不单射；⑦ 不单射也不满射；⑧ 双射。

D、E：⑨ 不是反函数; ⑩ 是反函数。                              

解：A=③   B=④   C=⑦   D=⑨   E=⑩                     

4.10  （1）设S={a,b,c},则集合T={a,b}的特征函数是（A），属于 §（S上S）的函数是（B）。

      （2）在S上定义等价关系R=Is∪{< a,b >,< b, a>},那么该等价关系对应的划分中有(C)个划分.作自然映射g:S→S/R,那么g的表达式是(D). g(b)=(E).

供选择的答案

A、B、D：① {,,};② {} ; ③{,,};

④ {,,};⑤ {,,}.

C:⑥ 1;⑦ 2;⑧ 3.

E:⑨ {a,b};⑩ {b}.

答案： 

    A: ③

B: ①

C: ⑦

D: ⑤

E: ⑨    

4.11 设S={1，2，……，6}，下面各式定义的R都是在S上的关系，分别列出

R的元素。

R = { |x, y ∈s ∧ x | y}.

  解：由题意可知R是整除关系， 

      所以答案如下：

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 = {< x , y > | x , y ∈ S ∧ x是y的倍数}.

   解:  由题意可知：

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 = {< x, y> | x , y ∈S ∧ ( x - y )²=  ∈ S }.

  解: 由题意可知：

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,4>,<5,6>,<6,4>,<6,5>}.

( 4 ) R = {< x , y > | x , y ∈S ∧ x / y是素数 }

解：由题意可知：

R={<1,1>,<2,1>,<2,2>,<3,1>,<3,3>,<4,2>,<4,4>,<5,1>,<5,5>,

<6,1>,<6,2>,<6,3>,<6,6>}.

4.13    S={a，b，c，d}，R1、R2为S上的关系，

      R1={，，}

       R2={，，，}

         求R1。R2、R2。R1、R12和R23.

         解:设R1的关系矩阵为M1，R2的关系矩阵为M2，

                 则

此题答案正确，只是写法不对，应改为：

4．14R的关系图如图4-14所示，试给出r（R）、s（R）、t（R）的关系图。 

 A     B     C     D       E       图4-14

解：r（R）：  a      b      c     d       e   

s（R）：  a        b        c        d        e 

t（R）：   a          b           c          d          e

4.16 画出下列集合关于整除关系的哈斯图。

（1）{1，2，3，4，6，8，12，24}。

（2）{1，2，……，9}

并指出它的极小元、最小元、极大元、最大元。

解：

（1）

            24  

8

12

4

6

2

3

        1

极小元、最小元：1

极大元、最大元：24

（2）

8

4

6

2               

5                        9

          7                    3

1  

      极小元、最小元：1

      极大元：5，6，7，8，9

      最大元：无

4.19设 f , g , h∈N , 且有

                 0   n为偶数

f (n)=n+1  ， g(n)=2n  ，h(n)=    

1   n为奇数

求 fof , gof  ,fog , hog , goh , 和 fogoh 。

解

   由题意可知所求的复合函数都是从N到N的函数，且满足

 fof(n)=f(f(n))= f(n+1)= (n+1)+1=n+2 

gof(n)=g(f(n))= g(n+1)= 2(n+1)=2n+2

fog(n)=f(g(n))= f(2n)=2n+1

hog(n)=h(g(n))= h(2n)=0

goh(n)=g(h(n))=   0   n为偶数

                    2      n为奇数

1   n为偶数

fogoh=f(g(h(n)))= 

3   n为奇数         

4.20 设f ： R×R→R×R , f ()=< x+y , x-y >, 求f 的反函数。

    解：设: 

则

而

        所以  

解得

            所以

4.21设f,gNN,,N为自然数集，且 

        x+1,   x=0,1,2,3               x/2,    x为偶数，

f(x)=    0,     x=4,           g(x)=    

        x,     x5,                   3，    x为奇数.

求gf并讨论它的性质（是否为单射或满射）。

设A={0，1，2}，求gf（A）。

解：（1）

       （x+1）/2,x=1,3,

gf(x)=    0,       x=4,

        x/2,     x为偶数且x6,

        3,      x=0,2及大于等于5的奇数。

gf不是单射，因为gf（6）= gf（5）=3.

gf是满射，因为gf能取到自然数集的任何数。

  （2）gf（0）=g（1）=3.

gf（1）=g（2）=1.

gf (2)=g(3)=3.

所以gf（A）={3,1}

4.22设A={0，1，2}，B={0，1}，

求P（A）和BA

构造一个从P（A）到BA的双射函数。

解：(1)P（A）={，{0}，{1}，{2}，{0，1}，{0，2}，{1，2}，{0，1，2}}

BA={f1,f2,……f8}

其中 f1={<0,0>,<1,0>,<2,0>}

f2={<0,0>,<1,0>,<2,1>}

f3={<0,0>,<1,1><2,0>}

f4={<0,0>,<1,1>,<2,1>}

f5={<0.1>,<1,0>,<2,0>}

f6={<0,1>,<1,0>,<2,1>}

f7={<0,1>,<1,1>,<2,0>}

f8={<0,1>,<1,1>,<2,1>}

(2)设该双射函数为F

F={<, f1>,<{0}, f2>,<{1}, f3>,<{2}, f4>,<{0，1}, f5>,<{0，2}, f6>,<{1，2}，f7>,<{0，1，2}, f8>}

做的不错，只是题目抄错了。正确答案是

4.22设A={a，b}，B={0，1}，

求P（A）和BA

构造一个从P（A）到BA的双射函数。

解：(1)P（A）={，{a}，{b}，{a，b}}

BA={f1,f2,……f4}

其中 f1={,}

f2={,}

f3={,}

f4={,}

 (2)设该双射函数为F

F={<, f1>,<{a}, f2>,<{b}, f3>,<{a,b}, f4>}

N/R1={{x}|xN} , N/R2={{所有的奇数},{所有的偶数}},   N/R3={[0],[1],[2]}

([0]={x|x=3kkN},[1]={x|x=3k+1kN},[2]={x|x=3k+2kN},)

4.25对下列函数f、g及集合A、B，计算f ◦ g、f ◦ g（A）和f ◦ g(B)，并说明f ◦ g是否为单射或满射

(1)   f : R→R，f(x)= - 

     g: N→N, g(x)= 

   A={2,4,6,8,10},B={0,1}.

 (2) f : Z→R，f(x)= 

            g:Z→Z, g(x)= 

   A=N,B={2K|k∈N}.

解：

  （1）

f ◦ g(x)＝f(g(x))= f()==-x   dom(f ◦ g)=N

由于f(g(0))=0, f(g(1))=0 ,所以f ◦ g不是单射.

显然对实数2.5,不存在自然数x,使得f(g(x))=2.5,所以f ◦ g也不是满射。

f ◦ g（A）={2,12,30,56,90}    

f ◦ g（B）={0}

  (2)

     f ◦ g(x)= f(g(x))= =             dom(f ◦ g)=Z

由于f(g(-1))=0, f(g(1))=e ,所以f ◦ g不是单射.

显然对实数,不存在自然数x,使得f(g(x))=,所以f ◦ g也不是满射。

f ◦ g（A）={|}  

f ◦ g（B）={|}