发布时间 : 星期五 文章最新洪帆《离散数学基础》(第三版)课后习题答案更新完毕开始阅读
精品文档
?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}
精品文档
(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)精品文档
精品文档
??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，
精品文档
~精品文档
也即?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)}
?0? 0?M?2??1??0精品文档
000??000?000??100??1?0?M?1??0??0100??010?101??000?