内容发布更新时间 : 2024/9/27 15:20:41星期一 下面是文章的全部内容请认真阅读。

对称性: ?,∈A×A,

R?x+v=y+u?u+y=v+x?R【2分】 传递性: ?,,∈A×A,

R∧R?x+v=y+u∧u+t=v+s?x+t=y+s?R【2分】 因此R是A×A上的等价关系.

(2)根据R的定义, R?x+v=y+u?x－y=u－v, 因此

[]R={|∈A×A∧u－v=x－y},【2分】 所以R引起的划分如下: { { <1,1>,<2,2>,<3,3>,<4,4>},

{<1,2>,<2,3>,<3,4>}, {<2,1>,<3,2>,<4,3>}, {<1,3>,<2,4>}, {<3,1>,<4,2>}, {<1, 4>},

{<4,1>} }【2分】

9 设R, S是A={1,2,3,4}上的等价关系, 其关系矩阵分别为 【本题合计5分】

?1?1MR???0??0100??10??100?01MS???01010???001??00, 00??10?10??01?.

求包含R与S的最小的等价关系.

分析: 设包含R与S的最小等价关系为T，则RT, ST, 所以RS T. 而T是等价关系，根据等价关系的定义，T应该具有自反性、对称性和传递性。由于R与S是等价关系，具有上述三个性质，由第四节关系运算与关系性质的关系知，RS具有自反性、对称性，但不一定有传递性。为此，需要使RS有传递性。又题目要求T是包含RS的最小等价关系，所以，T应是包含RS且具有传递性的最小关系，从而由传递闭包的定义，T应是RS的传递闭包，即T=t(RS)。如此，只需求出MT=Mt(RS)即可。

?1?1求解过程：MR???0??0100??1??100?0，MS???0010???001??0000??110?，

110??001?所以MR?S?1?1?MR?MS???0??0?1?1???1??0100??110?（?指对应元素逻辑或），【2分】 ?110?001?110??110?。【3分】

110??001?故由Warshall算法，MT?Mt(R?S)

10 设R是集合A上的等价关系, |A|=n, |R|=r, |A/R|=t, 证明: rt≥n. 【本题合计5分】 证 设A/R={B1,B2,…,Bt}, |B1|=x1, |B2|=x2,…, |Bt|=xt, 显然有1 xin, xi∈N, 1it. 由于A/R是A的划分, 因此

x1+x2+…+xt = n, (1). 【1分】

根据Bi是等价类, 对任意s,t∈Bi, 有∈R, 从而

222

x1+x2+…+xt = r, (2) 【2分】 根据算术-均方根均值不等式有

2

x1?x2???xt?2x12?x2???xt2

t代入(1)(2)可得 rt t n2

, 得证. 2分】

【