《离散数学》习题集(8)

第三章 二元关系

3.1 基本概念

1. 用列举法表示下列A?B上的二元关系S：

(a) A?{0,1,2}，B?{0,2,4}，S?{?x,y?|x,y?AB}；

(b) A?{1,2,3,4,5}，B?{1,2,3}，S?{?x,y?|x?y2?x?A?y?B}。 2. 设A?{0,1,2,3,4}，试用列举法表达由下列谓词确定的A上的n元关系，如果是二元关

系，画出其关系图。 (a) P(x)?x?1； (b) P(x)?3?2； (c) P(x)?2?3； (d) P(x,y)?x?y?4；

(e) P(x,y)??k(x?ky?k?2)； (f) P(x,y,z)?x2?y?z。 3. 对下列关系R，求出关系矩阵MR：

(a) A?{1,2,3}，R?{?2,2?,?1,2?,?3,1?}； (b) A?{0,1,2,3}，R?{?x,y?|x?2?y?1}；

(c) A?{5,6,7,8}，B?{1,2,3}，R?{?x,y?|x?A?y?B?3?x?y?y}； (d) A?{0,1,2,3,4,5,6}，R?{?x,y?|x?y?x是质数}。 4. 对下列每一个N上关系R给出一归纳定义，用你的定义证明x?R。 (a) R?{?a,b?|a?b}，x??3,1?； (b) R?{?a,b?|a?2b}，x??6,3?； (c) R?{?a,b,c?|a?b?c}，x??1,1,2?。

第36页 共53页

5. 设A?{1,2,3,4}，R?{?1,2?,?2,4?,?3,3?}，S?{?1,3?,?2,4?,?4,2?}， (a) 求出RS，RS，R?S，R；

(b) 求出D(R)，R(R)，D(RS)，R(RS)。

6. 证明对任意集合A和A上的二元关系R和S，有

D(RS)?D(R)D(S)，R(R7. 设A是n个元素的集合，证明 (a) A上有2个一元关系； (b) A上有2个二元关系。

n2nS)?R(R)R(S)。

8. 设P1(x,y)?xy?0，P2(x,y)?|x?y|?4，P3(x,y)?x?y?10，

IP1(x,y)?x整除y，试确定由这些谓词所定义的整数集合上的二元关系是否具有以

下特性，将结果用Y(yes)和N(no)填入下表。

自反的 反自反的 对称的 反对称的 传递的 P1 P2 P3 P4 9. 确定整数集合I上的相等关系、?关系、?关系、全域关系、空关系具有哪些特性？试

将结果用类似于上题的表列出。

10. 设A?{1,2,3,4}，A上的下列关系是否可传递？如果不是可传递的，举出反例证明它，

然后找出一个具有最少序偶的关系R，使R包含原关系，并且是可传递的。 (a) R?{?1,1?}； (b) R?{?1,2?,?2,2?}；

(c) R?{?1,2?,?2,3?,?1,3?,?2,1?}；

第37页 共53页

(d) R?{?1,2?,?4,3?,?2,2?,?2,1?,?3,1?}。

11. (a) 找出一个非空的最小集合，并在其上定义一个既不是自反的，也不是反自反的关系；

(b) 找出一个非空的最小集合，并在其上定义一个既不是对称的，也不是反对称的关系； (c) 若(a)，(b)二题中允许用空集合，结果将怎样？

12. 考虑任意集合A上的二元关系的集合，如果某一集合运算施于关系后，所得关系仍具

有相同的性质，那么说一个关系的性质在该运算下是保持的。例如自反性质在二元运算并之下是保持的，因为两个自反关系的并是自反的。然而，自反性质在集合的求补运算下是不保持的，因为非空集合上的一个自反关系的绝对补不是一个自反关系。按照在指定的集合运算下给出的性质是否保持，填充下表。对每一非(N)的回答，给出反例。 自反的 反自反的 对称的 反对称的 传递的 2并R1 R2 交R1 R2 相对补R1?R2 绝对补A?A?R1 13. 在R平面上画出下述关系的图，确定对每一关系成立哪些性质。 (a) {?x,y?|x?y}；

(b) {?x,y?|x2?1?0?y?0}； (c) {?x,y?||x|?1?|y|?1}。

3.2 关系的合成

14. 设R1和R2是集合A?{a,b,c,d}上的关系，这里

R1?{?b,b?,?b,c?,?c,a?}，R2?{?b,a?,?c,d?,?c,a?,?d,c?}，

3求出R1R2，R2R1，R1R2R1，R12，R2。

第38页 共53页

15. 设R1和R2是集合A?{0,1,2,3}上的关系，这里

R1?{?i,j?|j?i?1?j?i/2}，R2?{?i,j?|i?j?2}，

3求出R1R2，R2R1，R1R2R1，R12，R2。

16. 证明：如果R是集合A上的空关系或全域关系，则R?R。

2R是如图3.3所示的A上的二元关系，17. 设A?{a,b,c,d,e,f,g}，试找出最小的整数m和n，使得m?n，且R?R。

18. 设R1和R2是集合A上的任意关系，证明或否定下列断言： (a) 如果R1和R2是自反的，那么R1R2是自反的； (b) 如果R1和R2是反自反的，那么R1R2是反自反的； (c) 如果R1和R2是对称的，那么R1R2是对称的； (d) 如果R1和R2是反对称的，那么R1R2是反对称的； (e) 如果R1和R2是传递的，那么R1R2是反传递的。

19. R1,R2,R3是集合A上的二元关系，试证明如果R1?R2，那么 (a) R1R3?R2R3； (b) R3R1?R3R2。

20. 设A?{1,2,3,4,5}，R?{?1,2?,?3,4?,?2,2?}，S?{?4,2?,?2,5?,?3,1?}，试求出MRS。

mn?0?021. 设A?{1,2,3,4}，MR???1??0

001000011??0?，求MRn，n?N。 ?0?0?3.3 关系上的闭包运算

22. 试证明如果关系R是自反的，那么R也是自反的；如果R是可传递的、反自反的、对

第39页 共53页

称的或反对称的，则R亦然。 23. 如果关系R是反对称的，则在关系RR的关系矩阵中有多少个非零记入值。

24. 设A?{a,b,c}，R和S是A上的二元关系，其关系矩阵是

?110??110?????MR??010?，MS??010?，

?001??011?????试求出MR,MS,MRS,MRR。

25. 设R是A?{1,2,3,4}上的二元关系，其关系矩阵是

?1?0MR???1??1000011110??1?， ?0?0?试求出(a) Mr(R)；(b) Ms(R)；(c) MR2,MR3,MR4和Mt(R)。 26. 设R1和R2是集合A上的关系，且R1?R2，证明下列各式 (a) r(R1)?r(R2)； (b) s(R1)?s(R2)； (c) t(R1)?t(R2)。

27. 设R1和R2是集合A上的关系，证明下列各式 (a) r(R1(b) s(R1(c) t(R1R2)?r(R1)r(R2)； R2)?s(R1)s(R2)； R2)?t(R1)t(R2)；

R2)?t(R1)t(R2)。

2(d) 用反例证明t(R128. 找出n个元素的集合A和A上的二元关系R，使R,R,可能吗？如有可能，试举出例子。

,Rn,Rn?1都是有区别的，这

29. (a) 用反例证明语句“如果R是传递的，那么s(R)也是传递的”为假；

第40页 共53页

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库《离散数学》习题集(8)在线全文阅读。