《离散数学》习题集

(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页

{A1B,A2B,,AmB}是AB的划分。

,?k是A上划分序列,使?i?1真细分?i,找

54. 设A是n个元素的有限集,假设?1,?2,出最大可能的序列长度。

55. 设A?I,定义A上的R1,R2,R3如下:

aR1b?a?b(mod3),aR2b?a?b(mod5),aR3b?a?b(mod6),

(a) 对偏序集合?{A/R1,A/R2,A/R3},细分?画出哈斯图; (b) 描述一下各式所诱导的等价关系,它们的秩是什么?

A/R1A/R2,A/R1A/R3,A/R1?A/R2,A/R1?A/R3。

56. 设Rj表示I上模j等价,设Rk表示I上模k等价, (a) 证明I/Rk细分I/Rj当且仅当k是j的整数倍; (b) 描述划分I/Rk?I/Rj; (c) 描述划分I/RkI/Rj。 57. 证明如果?1细分?2,那么?1?2??1和?1??2??2。

58. 设P表示非空集合A的所有划分的集合,考虑偏序集合?P,细分?,设?1和?2是P的

成员, (a) 证明?1?2是集合{?1,?2}的最大下界;

(b) 证明?1??2是集合{?1,?2}的最小上界。

59. 设R是集合A上的二元关系,如果R是自反的和对称的,则称R是相容关系。设

A?{316,347,204,678},R?{?x,y?|x?A?y?A?x和y有相同的数字},

(a) R是相容关系吗? (b) 画出R的关系图。

(c) 所有等价关系都是相容关系吗?

(d) 相容关系的关系图和等价关系的关系图有何不同?

第31页 共53页

补充习题:

1设A={a,b},B={1,2},求A上的恒等关系IA和A到B的全域关系A×B。 2设A={a1,a2,a3,a4},B={b1,b2,b3},R是A到B的二元关系,定义为:

R={,,,,,,} 写出R的关系矩阵。

3设A={1,2,3,4},R是A的二元关系,定义为:

R={<1,1>,<1,2>,<2,1>,<3,2>,<3,1>,<4,3>,<4,2>,<4,1>} 写出A上二元关系R的关系矩阵。

4设X={1,2,3,4},X上的二元关系H和S定义如下:

x?y是整数} 2x?yS={ |是正整数}

3H={ |

试求H∪S,H∩S,~H,S-H。

5X={1,2,3,4,5},X上的二元关系R和S定义如下:

R={<1,2>,<3,4>,<2,2} S={<4,2>,<2,5>,<3,1>,<1,3>}

试求R°S,S°R,R°(S°R),(R°S)°R,R°R,S°S,R°R°R 。 6A={ 1,2,3,4},A上的二元关系R定义如下:

R={<1,2>,<2,1>,<2,3>,<3,4>} 求二元关系R的各次幂。

7A={1,2,3,4,5},A上的二元关系R和S定义如下:

R={<1,2>,<2,2>,<3,4>} S={<1,3>,<2,5>,<3,1>,<4,2>} 试求MR °

S和

MR ° MS,它们是否相等 ?

8设X={1,2,3,4},Y={a,b,c},X到Y二元关系

R={<1,a>,<2,b>,<4,c>},

⑴试求RC,写出MR和MRC,验证MRC=MRT

⑵画出R和RC的关系图,验证将R关系图中的弧线的箭头反置可得到RC关系图。 9设R是实数集合,

第32页 共53页

联系客服:779662525#qq.com(#替换为@)