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

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?0?MR??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)也是传递的”为假；

(b) 举一实例证明即使R是一有限集，st(R)和ts(R)也可以不相等。

第26页 共53页

30. 设R是集合A上的关系，证明下列各式 (a) (R?)??R?； (b) RR?R?RR； (c) (R?)??R?。

???3.4 次序关系

31. 设集合A?{a,b,c,d,e}上的关系R为

{?b,a?,?c,a?,?d,a?,?d,a?,?d,c?,?e,a?,?e,c?}IA

(a) 作出关系R的哈斯图和有向图；

(b) 求出A的最小元素和最大元素，如果不存在，请指出； (c) 求出A的极小元素和极大元素；

(d) 求出子集{b,c,d}，{c,d,e}和{a,b,c}的上界和下界，再指出这些子集的最小上界

和最大下界，如果存在的话。

32. 对下述每一条件，构造有限集和无限集的例子各一个： (a) 非空偏序集合，其中某些子集没有最大元素；

(b) 非空偏序集合，其中有一子集存在最大下界，但没有最小元素； (c) 非空偏序集合，其中有一子集存在上界，但没有最小下界。 33. 下述4个集合偏序集合、拟序集合、线序集合、良序集合？ (a) ??(N),??； (b) ??(N),??； (c) ??({a}),??； (d) ??(?),??。

34. 对集合I?I分别构造一良序和一拟序。 35. 证明下列断言：

(a) 如果R是拟序，那么R也是拟序； (b) 如果R是偏序，那么R也是偏序；

第27页 共53页

(c) 如果R是线序，那么R也是线序；

(d) 存在一集合S和S上的关系R，使?S,R?是良序集合，但?S,R?不是。 36. 设R是集合S上的关系，S?是S的子集，定义S?上的关系R?如下：

R??R(S??S?)，

确定下述每一断言是真还是假。

(a) 如果R在S上是传递的，那么R?在S?上是传递的； (b) 如果R是S的偏序，那么R?是S?上的偏序； (c) 如果R是S的拟序，那么R?是S?上的拟序； (d) 如果R是S的线序，那么R?是S?上的线序； (e) 如果R是S的良序，那么R?是S?上的良序。 37. (a) 证明R是一拟序当且仅当R(b) 证明R是一偏序当且仅当R38. 证明下述断言：

(a) 对任意线序集合，每一子集的极小元素是最小元素，每一极大元素是最大元素； (b) 一线序集合的每一非空有限子集有一最小和最大元素。

39. 设?A,??是非空有限线序集合，|A|?2，R是A?A上的关系，根据R的不同定义，

指出?A?A,R?是拟序集合、偏序集合、线序集合、良序集合，还是其他集合？ 对任意?a1,b1?,?a2,b2??A?A，

(a) ?a1,b1?R?a2,b2??a1?a2?b1?b2；

(b) ?a1,b1?R?a2,b2??a1?a2?a1?a2?b1?b2； (c) ?a1,b1?R?a2,b2??a1?a2； (d) ?a1,b1?R?a2,b2??a1?a2。 40. 设??{a,b,c}，规定a?b?c，

(a) 求出??,词典序?中下列各串的直接后继者和直接前驱者，如果它们存在的话： (i) x?abc； (ii) y?abaa； (iii) z?bb；

第28页 共53页

?R??，且R?R?； R?E，且R?R?。

(b) 对???,标准序?，重复上一题。

3.5 等价关系

41. 设R是A上的等价关系，将A的元素按R的等价类顺序排列，则等价关系的关系矩阵

MR有何特征？

42. 证明集合A上的全域关系A?A是等价关系。 43. 假设A是含n各元素的有限集合（n?N），问 (a) 有多少个元素在A上的最大等价关系中？ (b) A上的最大等价关系的秩是什么？ (c) 有多少个元素在A上的最小等价关系中？ (d) A上的最小等价关系的秩是什么？ 44. 设R和R?是集合A上的等价关系， (a) 证明RR?是集合A上的等价关系；

R?不一定是集合A上的等价关系，要尽可能小地选取集合A。

(b) 用例子证明R45. 设R1和R2是非空集合A上的等价关系，确定下述各式，哪些是A上的等价关系，对不

是的举例说明。 (a) A?A?R1； (b)R1?R2； (c)R12；

(d)r(R1?R2)（R1?R2的自反闭包）； (e) R1R2。

46. R是整数集合I上的等价关系，将R中的每一序偶?x,y?标在I?I笛卡儿平面上，

所得图形有何特点？

47. 应用上题结论说明下述I集合上的二元关系是否是等价关系，对不是的说明为什么，并

找出R诱导的等价关系。 (a) R??；

(b) R?{?a,b?|(a?0?b?0)?(a?0?b?0)}；

第29页 共53页

(c) R?{?a,b?|(a?0?b?0)?(a?0?b?0)}；

(d) R?{?a,b?|?x(x?I?10x?a?10(x?1)?10x?b?10(x?1))}； (e) R?{?a,b?|a整除b}。

Ra，48. R是集合A上的二元关系，对于所有的a,b,c?A，如果aRb,bRc，则c那么称R是循环的，试证明R是自反的和循环的当且仅当R是一等价关系。

49. 下述论证一位着每一对称的何传递的关系是一等价关系。设R是一对称的何传递关系， (i) 因为R是对称的，如果?x,y??R，那么?y,x??R；

(ii) 因为R是传递的，如果?y,x??R??x,y??R，那么?x,x??R，所以R是自

反的。这得出R是一等价关系。 这个论证有什么错误？

50. 设A?{a,b,c}，求出A的所有划分；设A的所有划分构成的集合是P，画出

?P,细分?的哈斯图。

51. 设A?{a,b,c,d}，?1是A的划分，?1?{{a,b,c},{d}}。 (a) 列出?1诱导出的等价关系的序偶；

(b) 对划分?2?{{a},{b},{c},{d}}，?2?{{a,b,c,d}}，做同样工作； (c) 画出偏序集合?{?1,?2,?3},细分?的哈斯图。

52. 设?1和?2是非空集合A的划分，说明下列各式哪些是A的划分，哪些可能是A的划分，

哪些不是A的划分？ (a) ?1(b) ?1?2； ?2；

(c) ?1??2； (d) (?1(?2??1))?2。

,Am}是集合A的划分，若AiB??，i?1,2,,m，试证明

53. 设{A1,A2,第30页 共53页

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