发布时间 : 星期六 文章最新洪帆《离散数学基础》(第三版)课后习题答案更新完毕开始阅读
精品文档
(3) M?2??1
解：?2??1?{(2,1),(2,0),(3,1)}
使得?k??t。
M?2??1?0?0???1??0000??000?100??100?15、设A是有n个元素的有限集，?是A上的关系，试证明必存在两个正整数k,t，证明：因为?是A上的关系，所以对于任意正整数r，?r也是A上的关系，另一方面，因为#(A)?n，所以#(A?A)?n2，#(2A?A)?2#(A?A)?2n，也即A上只有
22n个不同的关系，因此在关系?,?2,?3,?,?2,?2
2n2n2?12中必有两个是相同的，也
即存在两个正整数k,t，使得?k??t，其中1?k?t?2n?1。
16、设?1是由A到B的关系，?2是由B到C的关系，试证明?1??2??2??1。 证明：由题设知道?1??2和?2??1都是由C到A的关系，因此只要证明它们由完全相同的序偶组成。设(c,a)??1??2，则(a,c)??1??2，因此必存在元素b?B，
~~~~使得(a,b)??1，(b,c)??2，所以(b,a)??1，(c,b)??2，所以(c,a)??2??1。反之，设(c,a)??2??1，则必存在元素b??B，使得(c,b?)??2，(b?,a)??1，所
~以(a,b?)??1，(b?,c)??2，所以(a,c)??1??2，所以(c,a)??1??2，所以
~~~~~~~~~~~?1??2??2??1。
17、（1）设?1和?2是由A到B的关系，问?1??2??1??2成立吗？ 答：成立
~一定是自反的吗？ （2）设?是集合A上的关系，如果?是自反的，则?~~~~~~答：是的。证明：若?是自反的，则对所有的a?A，有(a,a)??，则一定有
~，则?~也是自反的。 (a,a)??~也是对称的吗？ 答：是的。 （3）若?是对称的，则?~也是可传递的吗？答：是的 （4）若?是可传递的，则?证明：若?是可传递的，由定义可知，若(x,y)??，则一定有(x,z)??，(y,z)??，
~，~，(z,y)??~，一定有(z,x)??~也是由逆关系的定义，也即，若(y,x)??，则?可传递的。
18、图2-9给出了集合{1,2,3,4,5,6}上的关系?的关系图，试画出关系?5和?8的图，并利用关系图求出关系?的传递闭包。 解：
精品文档
精品文档
图2-9
关系??{(1,3),(1,5),(2,5),(4,5),(5,4),(6,3),(6,6)}
?2?{(1,4),(2,4),(4,4),(5,5),(6,3),(6,6)} ?3?{(1,5),(2,5),(4,5),(5,4),(6,3),(6,6)}
?4?{(1,4),(2,4),(4,4),(5,5),(6,3),(6,6)} 因为?4??2，所以?5??3，?8??2
23传递闭包。????????
19、试证明：若?是基数为n的集合A上的一个关系，则?的传递闭包为
????i
i?1??ini?n证明：由定义????，要证明?????，因为?????i，所以只要证明
i?1?i?inini?设(a,b)???，则必存在正整数k，使得(a,b)??k，若k?n，?????即可。
i?1?ii?1i?1i?1i?1则(a,b)???，若k?n，则在A中必存在k?1个元素ai1,ai2,?,aik?1，使得：
i?1i?1nii?1 a?ai1,ai1?ai2,?,aik?1?b
因为k?n，所以在a,ai1,ai2,?,aik?1,b这k?1个元素中必有两个元素air?ait（0?r?t?k，记a为ai0，记b为aik），因此下述关系
a?ai1,?,air?1?air,air?ait?1,?,aik?1?b
成立，这表明a?kb，k1?k?(t?r),k1?k。若k1?n，用类似的方法又可找到
ik2?k1，使a?k2b,?，最后必可找到一正整h，使a?hb且h?n，因此(a,b)? ? ? ，
n故 ? ? ? ? ? 。
i?1i?1?inii?1
20、下列关系中哪一个是自反的、对称的、反对称的或者可传递的？ （1）当且仅当|i1?i2|?10(i1,i2?I)时，有i1?i2；
答：是自反的，对称的，非可传递的，例如13?9，9?1，但13?1不成立。 （2）当且仅当n1n2?8(n1,n2?N)时，有n1?n2；
答：非自反的，因为1?1不成立，但1?N。对称的，非可传递的，因为1?10，10?2，但是1?2不成立。
（3）当且仅当r1?|r2|(r1,r2?R)时，有r1?r2。
答：自反的，非对称的，非可传递的，因为5?(?8)，?8?1，但是5?1不成立。
精品文档
精品文档
21、设?1和?2是集合A上的任意两个关系，判断下列命题是否正确，并说明理由：
（1）若?1和?2是自反的，则?1??2也是自反的；
答：正确。因为?1和?2是自反的，因此对任意a?A，有a?1a,a?2a，因此a?1?2a，所以?1??2也是自反的。
（2）若?1和?2是非自反的，则?1??2也是非自反的；
答：错误；例如A?{a,b,c}，?1?{(a,a),(b,b),(c,a)}，?2?{(a,a),(b,b),(a,c)}，
?1和?2都是非自反的，但是?1??2?{(a,a),(b,b),(c,c)}是自反的。
（3）若?1和?2是对称的，则?1??2也是对称的；
答：错误，设A?{a,b,c}，?1?{(a,b),(b,a)}，?2?{(a,c),(c,a)}，显然?1和?2是对称的，但是?1??2?{(b,c)}是非对称的。 （4）若?1和?2是反对称的，则?1??2也是反对称的；
答：错误，设A?{a,b,c}，?1?{(a,b),(c,c)}，?2?{(b,c),(c,a)}，显然?1和?2是反对称的，但是?1??2?{(a,c),(c,a)}不是对称的。 （5）若?1和?2是可传递的，则?1??2也是可传递的；
答：错误，设A?{a,b,c}，?1?{(a,b),(b,c),(a,c)}，?2?{(b,c),(c,a),(b,a)}，显然?1?2是可传递的，但是?1??2?{(a,c),(a,a),(b,a)}却是不可传递的。
22、证明若?是对称的，则对任何整数k?1，?k也是对称的。
证明：数学归纳法，当k?2时，若(a,b)??2，则根据复合关系的定义，存在元素c，使得(a,c)??,(c,b)??，因为?是对称的，所以(c,a)??,(b,c)??，所以
(b,a)??2，因此?2是对称的，假设当n?k时成立，则当n?k?1时，若(a,b)??k?1，则存在元素c1，使得(a,c1)??k,(c1,b)??，因为?和?k是对称的，
因此(c1,a)??k,(b,c1)??，所以(b,a)??k?1，因此：
n?k?1 时成立，即得证。
23、已知A?{1,2,3,4}和定义在A上的关系??{(1,2),(4,3),(2,2),(2,1),(3,1)}，试证明?不是可传递的。求出一个关系?1??，使得?1是可传递的，你能求出另一个关系?2??也是可传递的嘛？
答：证明：?显然不是可传递的，因为(1,2)??，(2,1)??，但是(1,1)??。
?1?{(1,2),(4,3),(2,2),(2,1),(3,1),(1,1),(4,1),(4,2)}，能找出另一个关系。
?1?{(1,2),(4,3),(2,2),(2,1),(3,1),(1,1),(4,1),(4,2),(3,3)}。
精品文档
精品文档
24、图2-10表示在{1,2,3}上的12个关系的关系图。试对每一个这样的图，确定其表示的关系是自反的还是非自反的；是对称，非对称还是反对称；是可传递的还是不可传递的？ 答：
精品文档
自反的、对称的，非反对称的、可传递的
非自反的、非对称的、反对称的、可传递的
自反的、非对称的、非反对称的，非可传递的