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

?111???关系矩阵 M???110??100? ??(2) A?{1,2,3,4,5},B?{1,2,3},??{(a,b)|a?b2} 解:??{(1,1),(4,2)} 关系矩阵M?= ?10? ?00?00 ??01 ?00?

义域和值域 (1) ??{(i,j)|i?j} 解:图略

0??0?0??0?0??5、设A?{1,2,3,4,5,6},对下列每一种情形,构造A上的关系图,并确定?的定

??{(1,1),(2,2),(3,3),(4,4),(5,5),(6,6)} 定义域D??A,R??A

(2) ??{(i,j)|i整除j}

解:??{(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)}

定义域D??A,R??A

(3) ??{(i,j)|i是j的倍数}

解: ??{(1,1),(2,2),(3,3),(4,4),(5,5),(6,6),(2,1),(3,1)

(4) ??{(i,j)|i?j}

?解: ?{(6,5),(6,4),(6,3),(6,2),(6,1)(5,4),(5,3),(5,2),(5,1)

(4,3),(4,2),(4,1)

(3,2),(3,1)

(2,1)}定义域D??{6,5,4,3,2},R??{5,4,3,2,1}

(5) ??{(i,j)|i?j}

13

(4,1),(5,1),(6,1),(4,2),(6,2),(6,3)}定义域D??A,R??A

解:定义域D??{5,4,3,2,1},R??{6,5,4,3,2}

??{(1,2),(1,3),(1,4),(1,5),(1,6),(2,3),(2,4),(2,5),(2,6)(3,4),(3,5),(3,6),(4,5),(4,6),(5,6)}(6) ??{(i,j)|i?j,ij?10}

解:? ?{(1,1),(1,2),(1,3),(1,4),(1,5),(1,6),(2,1),(2,2),(2,3) (2,4),(3,1),(3,2),(3,3),(4,1),(4,2),(5,1),(6,1)}定义域D??{6,5,4,3,2,1},R??{6,5,4,3,2,1}

(7) ??{(i,j)|i?j,(i?j)2?A}

解: ??{(1,1),(1,2),(1,3),(2,1),(2,2),(2,3),(2,4),(3,1)

(8) ??{(i,j)|i/j是素数}

解:??{(2,1),(3,1),(5,1),(4,2),(6,3),(6,2)} 定义域D??{2,3,4,5,6},R??{1,2,3}

6、设?1?{(1,2),(2,4),(3,3)}和?2?{(1,3),(2,4),(4,2)},试求出?1??2,?1??2,D?2RRD?1, D ( ?1 ? ? , ? 1 , ? 和 R ( ?1 ? ?2 ), 并证明:D(?1??2)=D?1?D?2 2)2?R? 2 R(?1??2)?R?1(3,2),(3,3),(3,4),(3,5),(4,2),(4,3),(4,4),(4,5)(4,6),(5,3),(5,4),(5,5),(5,6),(6,4),(6,5),(6,6)}定义域D??A,R??A

解:?1??2?{(1,2),(2,4),(3,3),(1,3),(4,2)}

?1??2?{(2,4)}

D?1?{1,2,3},D?2?{1,2,4},R?1?{2,4,3},R?2?{3,4,2} D(?1??2)?{1,2,3,4} R(?1??2)?{4}

证明:D(?1??2)=D?1?D?2

设x?D(?1??2),则必存在y,使得(x,y)??1??2,所以(x,y)??1或者

(x,y)??2,x?D?1或者x?D?2,因此,即x?D?1?D?2,所以D(?1??2)?D?1?D?2;

反之,设x?D?1?D?2,则x?D?1或者x?D?2,所以存在y1,使得(x,y1)14

??1,或者存在y2,使得(x,y2)??2,由并集的定义知,(x,y1)??1??2,或者

(x,y2)??1??2,总之有x?D?1??2,故D?1?D?2?D(?1??2)。

证明:R(?1??2)?R?1?R?2

设y?R?1??2,则必存在x,使得(x,y)??1,(x,y)??2,因此b?R?1且

b?R?2,由交集的定义b?R?1?R?1,故R(?1??2)?R?1?R?2。

A1和A2是分别具有基数n1和n2的有限集,7、试问有多少个A1到A2的不同关系? 答:A1?A2的所有子集都是A1到A2的一个关系,所以共有2

8、找出集合A?{a1,a2,?,an}上普遍关系和恒等关系的关系矩阵和关系图的特征。

答:A上的普遍关系??A2的关系矩阵是全1矩阵,而恒等关系的关系矩阵是单位矩阵。

9、下列是集合A?{0,1,2,3}上的关系:?1?{(i,j)|j?i?1或者j?i/2},

#(A1?A2)个不同的关系。

?2?{(i,j)|i?j?2},试确定如下的复合关系:

(1)?1??2 (2)?2??1 (3)?1??2??1 (4)?13 解:(1)?1?{(0,1),(1,2),(2,3),(0,0),(2,1)},?2?{(2,0),(3,1)}

?1??2?{(1,0),(2,1)}

(2)?2??1?{(2,1),(2,0),(3,1)} (3)?1??2??1?{(1,1),(1,0),(2,2)} (4)?12?{(0,2),(1,3),(1,1),(0,1),(0,0),(2,2)} ?13?{(0,3),(0,1),(1,2),(0,2),(0,0),(0,1),(2,3),(2,1)}

10、 设?1,?2,?3是集合A上的关系,试证明:如果?1??2,则有: (1)?1??3??2??3 (2)?3??1??3??2 (3)?1??2

证明:(1)对?(x,y)??1??3,由复合关系的定义,?z?A,使得,(x,z)??1,

(z,y)??3,因为?1??2,所以(x,z)??2,所以(x,y)??2??3,所以

~~?1??3??2??3

(x,z)??3,(z,y)??1,(2)对?(x,y)??3??1,由复合关系的定义,使得,?z?A,

因为?1??2,所以(z,y)??2,所以(x,y)??3??2,所以?3??1??3??2。

~(3)对?(x,y)??1,有(y,x)??1,因为?1??2,所以(y,x)??2,所以(x,y)??2,

15

~也即?1??2。

~~?1??2?{(1,3),(1,4),(3,3)}求一个基数最小的关系,11、给定?1?{(0,1),(1,2),(3,4)},

使满足?2的条件。一般地说,若给定?1和?1??2,?2能被唯一的确定吗?基数最小的?2能被唯一确定吗?

答:?2?{(2,3),(2,4),(4,3)}。一般地说,若给定?1和?1??2,?2不能被唯一的确定。基数最小的?2也不能被唯一确定。

12、给定集合A1,A2,A3,设?1是由A1到A2得关系,?2和?3是由A2到A3得关系,试证明:

(1)?1?(?2??3)=(?1??2)?(?1??3)

证明:根据并集和复合关系的定义,?1?(?2??3)和(?1??2)?(?1??3)都是

A1到A3上的关系,下只需要证明它们由完全相同的序偶组成。

设(a,c)??1?(?2??3),必存在b?A2,使得(a,b)??1,(b,c)??2??3,所以有(b,c)??2或者(b,c)??3,所以有(a,c)??1??2或者(a,c)??1??3,也即

(a,c)?(?1??2)?(?1??3),也即?1?(?2??3)?(?1??2)?(?1??3);反之,若(a,c)?(?1??2)?(?1??3),也即(a,c)?(?1??2)或者(a,c)?(?1??3),若(a,c)?(b,c)??2??3,(?1??2),(b,c)??2,则存在b?A2,使得(a,b)??1,则(a,b)??1,

则(a,c)??1?(?2??3),若(a,c)?(?1??3)同理可得,因此有(?1??2)?(?1??3)??1?(?2??3)。则?1?(?2??3)=(?1??2)?(?1??3)。 (2)?1?(?2??3)?(?1??2)?(?1??3)

证明:设(a,c)??1?(?2??3),则存在b?A2,使得,(a,b)??1,(b,c)??2??3,则(b,c)??2,且(b,c)??3,所以(a,c)??1??2,且(a,c)??1??3,即

(a,c)?(?1??2)?(?1??3),所以?1?(?2??3)?(?1??2)?(?1??3)。

13、给定??{(i,j)|i,j?I,j?i?1},?n是什么?

答:I?{?,?3,?2,?1,0,1,2,3,?},??{?,(?2,?1),(?1,0),(0,1),(1,2),(2,3),(3,4),?}

?2?{?,(?3,?1),(?2,0),(0,2),(1,3),(2,4),(3,5),?},则?n?{(i,j)|i,j?I,j?i?n}

14、对第9题中的关系,构造关系矩阵 (1)M?1 (2)M?1

解:?1?{(0,1),(1,2),(2,3),(0,0),(2,1)} ?2?{(2,0),(3,1)}

M?2?0?0???1??0000??000?000??100??1?0?M?1??0?16 ?0100??010?101??000?