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

(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的图,并利用关系图求出关系?的传递闭包。 解:

17

图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不成立。

18

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)}。

19

24、图2-10表示在{1,2,3}上的12个关系的关系图。试对每一个这样的图,确定其表示的关系是自反的还是非自反的;是对称,非对称还是反对称;是可传递的还是不可传递的? 答:

自反的、非对称的、非反对称的,非可传递的

自反的、对称的,非反对称的、可传递的

非自反的、非对称的、反对称的、可传递的

20