发布时间 : 星期六 文章最新洪帆《离散数学基础》(第三版)课后习题答案更新完毕开始阅读
精品文档
自反的、非对称的、反对称的、可传递的
25、图2-11给出了{1,2,3}上的两个关系的关系图，这些关系是等价的吗？ 答：
(a) (b)
答：图(a)表示的关系??{(1,1),(2,2),(3,3),(1,2),(2,1),(1,3),(3,1)}具有自反性，对称性，但是不具有传递性，因为有(2,1),(1,3)??，但是(2,3)??，因此不是等价关系。
图(b)表示的关系??{(1,1),(2,2),(3,3),(1,2),(2,1)}，具有自反性，对称性，传递性，因此是等价关系。
26、在N上的关系?定义为当且仅当ni/nj可以用形式2m表示时，有ni?nj，这里m是任意整数： (1)证明?是等价关系
证明：对?n?N，n/n?1?20，因此n?n，所以关系?具有自反性。
对i,j?N，若i?j，即存在m，使得i/j?2m，则有j/i?2?m，因此有j?i。所以关系?具有对称性。
对i,j,k?N，若i?j，且j?k，即存在m1,m2，使得i/j?2m1，j/k?2m2，则i/k?2m1?m2，因此有i?k，所以关系?具有传递性。 综上可得关系?是等价关系。 (2) 找出?的所有等价类
答：
[1]??{1,2,4,8,16,}?{2k,k?0,1,2,3,4,}
[3]??{3,6,12,24,}?{3?2k,k?0,1,2,3,4,}
[5]??{5,10,20,40,}?{5?2k,k?0,1,2,3,4,}
N???{[1]?,[3]?,[5]?,,[2k?1]?}
27、有人说，集合A上的关系?，如果是对称的且可传递的，则它也是自反的，
精品文档
精品文档
其理由是，从ai?aj，由对称性得aj?ai，再由可传递性便得ai?ai。
答：这种说法是错误的。例如，A?{1,2,3}，??{(1,2),(2,1),(1,1)}，显然?是对称的，且?是可传递的，但是它不是自反的。
28、设有集合A和A上的关系?，对于所有的ai,aj,ak?A，若由ai?aj和aj?ak可推得ak?ai，则称关系?是循环的，试证明当且仅当?是等价关系时，?是自反且循环的。 证明：先证充分性
若?是等价关系，则?是自反的，对称的，可传递的。对于所有的ai,aj,ak?A，若ai?aj且aj?ak，则ai?ak，由对称性则有ak?ai，因此关系?是循环的。 再证必要性
若对于所有的ai,aj,ak?A，若有ai?aj，又由自反性，有aj?aj，则由?是循环的，可得aj?ai成立，即?具有对称性。
若对于所有的ai,aj,ak?A，若由ai?aj和aj?ak，由?是循环的有ak?ai，由对称性可得ai?ak，因此?具有可传递性。 又由?是自反的，则?是等价的。
A29、设?1和?2是A上的等价关系，试证明：当且仅当??中的每一等价类都包含1A于??的某一等价类中时，有?1??2。 2证明：先证充分性
AA设??中的每一个等价类都包含于对任一(ai,aj)??1，有??2的某一个等价类中，1ai?1aj，因此ai?[ai]?1,aj?[ai]?1。又由假设必有某元素b?A存在，使得[ai]?1?[b]?2，因此有ai?[b]?2，aj?[b]?2，所以(ai,aj)??2，故有?1??2。
再证必要性：
A设?1??2，并设[ai]?1是??中任一等价类，对任一x?[ai]?1，有ai?1x，即1(ai,x)??1，由假设(ai,x)??2，即x?[ai]?2，故有[ai]?1?[ai]?2。
30、已知?1和?2是集合A上分别有秩r1和r2的等价关系，试证明?1??2也是A上的等价关系，它的秩最多为r1r2，再证明?1??2不一定是A上的等价关系。 证明：由交集的定义?1??2?{(a,b)|(a,b)??1且(a,b)??2}
对于?a?A，因为?1,?2都是自反的，所以(a,a)??1，且(a,a)??2，因为
(a,a)??1??2，所以?1??2是自反的。
对于?a,b?A，若(a,b)??1??2，则(a,b)??1，(a,b)??2，由?1和?2的对称性知(b,a)??1，且(b,a)??2，因而有(b,a)??1??2，故?1??2是对称的。
精品文档
精品文档
对于?a,b,c?A，若(a,b)??1??2，(b,c)??1??2，则有(a,b)??1，(b,c)??1，
(a,b)??2，(b,c)??2，由?1,?2的传递性知(a,c)??1，(a,c)??2，因而(a,c)??1??2，故?1??2是可传递的。所以?1??2也是A上的等价关系。
对于?1??2，由并集的定义知?1??2?{(a,b)|(a,b)??1或者(a,b)??2} 对于?a?A，因为?1是自反的，所以(a,a)??1，因而(a,a)??1??2，所以?1??2是自反的。对于?a,b?A，若(a,b)??1??2，则(a,b)??1或者(a,b)??2，由于
?1和?2都是对称的，因此有(b,a)??1或者(b,a)??2，因而有(b,a)??1??2，故?1??2也是对称的。
对于任意的a,b,c?A，若(a,b)??1??2，(b,c)??1??2，则(a,b)??1或者
(a,b)??2；(b,c)??1或者(b,c)??2，因为(a,b)和(b,c)不一定能同时属于?1，
也不一定能同时属于?2，所以无法推出(a,c)??1或者(a,c)??2，因而也就无法推出(a,c)??1??2，这说明?1??2的可传递性不一定能成立，因此推不出
?1??2是A上的等价关系。
,(1,3),(3,1)}反例：设A?{1,2,，3A上的关系?1?{(1,1),(2,2),(3,3)，
?2?{(1,1),(2,2),(3,3),(1,2),(2,1)}，显然?1和?2均是等价关系。
?1??2?{(1,1),(2,2),(3,3),(1,3),(3,1),(1,2),(2,1)}，这里?1??2是自反的，对称的，但是不可传递的。
31、设?1是集合A上的一个关系，?2?{(a,b)|存在c,使(a,c)??1且(c,b)??1}。试证明：若?1是一个等价关系，则?2也是一个等价关系。
证明：因为?1是自反的，因此对?a?A，有(a,a)??1，由(a,a)??1，因此有(a,a)??2，故?2是自反的。
对于任意的a,b?A，若(a,b)??2，则必有元素c?A，使得(a,c)??1且
(c,b)??1，由?1的对称性又有(b,c)??1且(c,a)??1，因而有(b,a)??2，故?2是
对称的。
对任意的a,b,c?A，若(a,b)??2，(b,c)??2，则必有元素d,e?A，使得：
(a,d)??1,(d,b)??1 (b,e)??1,(e,c)??1
由?1的可传递性，又有(a,b)??1，(b,c)??2，于是又有(a,c)??2，故?2是可传递的。
由上得证?2是一个等价关系。
32、设A是由4个元素组成的集合，试问在A上可以定义多少个不同的等价关系？
精品文档
精品文档
答：根据等价关系与分划一一对应，将A分划为一块：有一种方法，将A分划为
1两块：2+2方式有1/2C42种，1+3方式有C4种
将A分划为三块：只能是1+1+2方式，有C42种 将A分划为四块：有一种方法
因此集合A上不同等价关系的个数为15种。
33、设?1和?2是集合A上的等价关系，下列各式哪些是A上的等价关系？为什么？ (1)(A?A)??1
答：不是等价关系，因为不具有自反性 (2) ?1??2
答：不是等价关系，因为不具有自反性 (3) ?12
答：是等价关系，证明如下：?1是自反的，?12显然也是自反的。若(a,b)??12，则有复合关系的定义，存在c?A，使得(a,c)??1，(c,b)??1，由?1的对称性有
(c,a)??1，(b,c)??1，由复合关系的定义有(b,a)??12，因此?12是对称的。若(a,b),(b,c)??12，由复合关系的定义，? d?A,(a,d)??1,(d,b)??1?e?A,(b,e)??1,(e,c)??1
d ) ??由对称性， ( d , a ) ? ? 1,( b , ? 1 ( b ,a ) ? ? 1 ，
(e,b)??1,(c,e)??1?(c,b)??1
所以(c,a)??12，由?12的对称性，(a,c)??12，因此?12具有传递性。因此?12是A上的等价关系。 (4)r(?1??2)
?2?{(1,1),(2,2),(3,3),(2,3),(3,2)}，答：不一定是A上的等价关系。例如A?{1,2,3}，?1为A上的普遍关系，则r(?1??2)?{(1,1),(2,2),(3,3),(1,2),(2,1),(1,3),(3,1)}不具有传递性，因为(2,1),(1,3)?r(?1??2)，但是(2,3)?r(?1??2)。
34、对于下列集合中的’整除’关系，画出次序图： (1) {1,2,3,4,6,8,12,24} 答：
精品文档