haihongyuan.com
海量文库 文档专家
全站搜索:
您现在的位置:首页 > 幼儿教育 > 幼儿读物幼儿读物

23关系

发布时间:2014-03-08 19:29:15  

教师:田检





1. 等价关系 定义:设R是非空集合A上的二元关系,如果关系R同 时具有自反性、对称性和传递性,则称R是A上的 等价关系。
①关系图法 若一个关系的关系图是由完全关系子图组成,则该关系是 一个等价关系。 结点个数分别为1,2,3,4的完全关系图如下:

②关系矩阵判别法 1)关系矩阵判别法 ⅰ)若一关系矩阵的主对角线上的元素都为1,且是以主 对角线对称的矩阵,则该关系是自反和对称的。 ⅱ)采用前面介绍的可传递关系矩阵判别法,判别关系是 传递的。 2)关系矩阵变换法 将关系矩阵的x行和y行的位置对调,x列和y列的位置 对调,所得矩阵等价于原关系矩阵(相当于集合中的两个 元素互换位置,原关系不变)。经变换后若矩阵变为可分 成多个独立的完全关系子矩阵且主对角线上的元素都为1, 则该关系为等价关系。

?1 ?0 MR ? ? ?0 ? ?1

1? 2 , 4 列对调 1 1 0? ? 1 1 0? ? ? 0 0 1? 0 0

?1 ?0 ? ?0 ? ?1

1 0 0? ? 0 1 1? 0 1 1? ? 1 0 0?

?1 2,4 行对调 ? 1 ? ? ?0 ? ?0

1 0 0? 1 0 0? ? 0 1 1? ? 0 1 1?

故关系R为等价关系。

例如集合A={0,1,2,3,4,5,6},R为集合A上的模3同余关系,即, R ? {? x, y ?| x, y ? A ? x ?Ry (mod 3)} 试利用关系图和关系矩阵分别验证 为等价关系。 解:根据题意: R={<0,0>,<0,3>,<0,6>,<1,1>,<1,4>,<2,2>,<2,5>,<3,0>,<3.3>, <3,6>,<4,1>,<4,4>,<5,2>,<5,5>,<6,0>,<6,3>,<6,6>} 1)R的关系图如下,该关系图由两个二阶完全关系子图和一 个三阶完全关系子图组成,所以R是一个等价关系。

2)R的关系矩阵如下
?1 ?0 ? ?0 ? MR ? ? 1 ?0 ? ?0 ?1 ? 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0

?1 ?1 ? 3, 7行对调 ?1 ? ? ?0 3, 7列对调 ?0 ? ?0 ?0 ?

1 1 1 1 1 1 0 0 0 0 0 0 0 0

?1 ?1 1? ? 0? ? 4 行对调 ?0 0? 2, ? ? ? ?0 1? 4列对调 ?0 0? 2, ? ? 0? ?0 ?1 1? ? ? 0 0 0 0? 0 0 0 0? ? 0 0 0 0? ? 1 1 0 0? 1 1 0 0? ? 0 0 1 1? 0 0 1 1? ?

1 0 0 0 0 1? 1 0 0 0 0 1? ? 0 1 0 0 1 0? ? 0 0 1 1 0 0? 0 0 1 1 0 0? ? 0 1 0 0 1 0? 1 0 0 0 0 1? ?

所以该关系是 等价关系

例:设整数集I上的关系 R ? {? x, y ?| ( x ? y ) 3 ? I },试 证明R是I上的等价关系。 证明: 1)对于任意元素x∈I ,因为(x-x)/3∈I,所以 <x,x> ∈R 因此R具有自反性。 2)对于任意<x,y> ∈R,则(x-y)/3∈I, 故(y-x)/3∈I 所以<y,x> ∈R ,R具有对称性。 3)如果<x,y> ∈R 而且<y,z> ∈R ,则 (x-y)/3∈I, (y-z)/3∈I (x-z)/3=(x-y)/3+(y-z)/3∈I 所以<x,z>∈R ,则R具有传递性。 因此R是I上的等价关系。

定义:设R是非空集合A上的等价关系,x∈A, A中凡与 x等价的元

素组成的集合记为[x]R, [x]R ={y | y∈A∧<x,y> ∈R},称为x关于R生成的等 价类。简称为等价类。 例 设R是整数集I上模4的等价关系,求I上不同等价 类。 解:R={<x,y>|x=y(mod 4)} I上关于模4的等价类有:[0]R,[1]R,[2]R,[3]R。 [0]R ={……-8,-4,0,4,8,……} [1]R ={……-7,-3,1,5,9,……} [2]R ={……-6,-2,2,6,10,…..} [3]R ={……-5,-1,3,7,11,…..}

定理4-8 设R是非空集合A上的等价关系,则有: (1)对于任意x∈A, x关于R生成的等价类[x]R≠? (2)满足等价关系的元素构成的等价类相等,即 ?x?y(x,y∈A ∧ <x,y>∈R→ [x]R = [y]R) (3)不满足等价关系的元素构成的等价类的交为空集。 即?x?y(x,y∈A ∧ <x,y>? R→ [x]R∩ [y]R=? )

(4)设R是A上的等价关系,则等价类集合{[x]R|x∈A}是 A的一个划分。

补 充
集合的覆盖 定义: 若把一个集合S分成若干非空子集 A1 , A2 ,? , An , 使得S的每个元素至少属于一个子集,则这个子集的全体称 为S的一个覆盖。 即集合 A1 , A2 ,? , An 若 (1) Ai ? ? ( i ? 1,2,?, n) (2) Ai ? S ( i ? 1,2,?, n) (3) n A ? S

?
i ?1

i

则 A1 , A2 ,? , An 是S的一个覆盖。 2},A 3 ? {3, 4, 5}, 例如 S ? {1,2,3,4,5,6}, 集合A1 ? {1},A 2 ? {1,
A4 ? {1, 2, 3, 6}



?A
i ?1

4

i

是S的一个覆盖。

集合的划分 定义 如果集合 A 是S的一个覆盖,其中 A ? { A1 , A2 ,?, An } 当 i ? j时Ai ? A j ? ? , 则称A是S的一个划分。Ai 为划分块。 当A为有限集时 A ? { A1, A2, A3,..., An},| A |? n ,称n为A的秩 (Rank),当A为无限时,其秩也无限。 例如: S ? {1, 2, 3, 4, 5, 6},A ? {{1, 3}, {2, 4, 6}, {5}} , A是S的一个划分,其秩为3。

如图给出了A的一个划分 :

?A1 , A2 , A3 , A4 , A5 , A6 ? ?=
A6 A5

?的一个划分块
A1 A2
A3

A4

证明(4):

等价类集合是A的一个划分

由性质(1)可知任一等价关系的等价类[x]R ≠? ;

由性质(2)可知[x]R∩ [y]R =? ;
? 只须证明 A ? ? [ x ]R

?[ x]R ? A,
对于任意x∈A
x ? [ x ]R ? ? [ x ]R
x? A

x? A

? ? [ x ]R ? A
x? A

即 A ? ? [ x ]R
x? A

? ? [ x ]R ? A
x? A

所以,{[x]R | x∈A}构成A的一个划分。

定义:由A上的等价关系R的等价类组成A的一个划 分,称为A上由R所导出的等价划分{[x]R | x∈A} 也称为A对R的商集,记为: A/R={[x]R | x∈A}

例题1 :已知A ? ?1,2,3,4,5?, R是A上的关系 , R ? {? 1,1 ? , ? 1,2 ? , ? 2,1 ? , ? 2,2 ? , ? 3 , 3 ? , ? 3 , 5 ? , ? 4 ,4 ? , ? 5 , 3 ? , ? 5 ,5 ? } 判断R是否为等价关系 ; 若是 , 求A对R的商集。

1

3

解 : R具有自反性、 对称性和传递性,

4 2
5

所以 R是等价关系,

其等价类为?1, 2?? , 4?? , 3, 5?。

所以A / R ? ?[1]R , [3]R , [4]R ? 。


题 2 : 若等价关系R的等价类为?1,2?, ?3,4,5? , 求关系R。 ?1,2? ? 1,1 ?, ? 1,2 ?, ? 2,1 ?, ? 2,2 ?

?3,4,5?

? 3,3 ? , ? 3,4 ? , ? 3,5 ? , ? 4,3 ? , ? 4,4 ? , ? 4,5 ? , ? 5,3 ? , ? 5,4 ? , ? 5,5 ?

解 : R ? {? 1,1 ? , ? 1,2 ? , ? 2,1 ? , ? 2,2 ? , ? 3,3 ? , ? 3,4 ? , ? 3,5 ? , ? 4,3 ? , ? 4,4 ? , ? 4,5 ? , ? 5,3 ? , ? 5,4 ? , ? 5,5 ? }

练习1 :已知A ? ?a , b, c , d ? ,R1 , R2 是A上的关系, ? ? a , a ? , ? a , b ? , ? b, a ? , ? b, b ? ,? R1 ? ? ? ?? c , c ? , ? c , d ? , ? d , c ? , ? d , d ? ? ?? a , b ? , ? b, a ? , ? a , c ? , ? c , a ? , ? R2 ? ? ? ? ? b, c ? , ? c , b ? , ? a , a ? , ? b, b ? , ? c , c ? ? 判断它们是否为等价关 系; 若是 , 写出其所有等价类

练习2 : 若等价关系R的等价类为?s, n?, ?m , p, t ?, ?q? , 试用列举法写出关系R

4.5.2 相容关系 定义:设R是集合X上的二元关系,若R是自反的 和对称的,则称R是X上的相容关系。 显然,如果一个关系是等价关系,它必定 是相容关系。

例3

设集合A={216,243,357,648}.定义A上的

关系R ={〈x,y〉|x,y∈A,且x与y中至少有一个相同

数字}, 则 R 是A上的一个相容关系。但 R 不是等价关系。

令a=216,b=243, c= 357,d= 648,则 R 可表示为

R ? {? a, a? , ? a, b? , ? a, d ? , ? b, b? , ? b, a? , ? b, c? , ? b, d ? , ? c, b? , ? c, c? , ? d , a? , ? d , b? , ? d , d ? }

定义:设R是集合X上的一个相容关系,若集 合A是集合X的一个子集且其中的任两个元 素间都具有关系R,而X-A中的任一个元素 都不能和A中的所有元素具有关系R,则称 A是集合X的一个极大相容类。

上例中的极大相容类为 : {b, c},{a, b, d }

定义:设R是给定集合X上的一个相容关系,则由R 所产生的所有极大相容类所构成的集合,称为集 合X的完全覆盖。

定理4.5.3 集合A上的相容关系与完全覆盖 存在一一对应关系。

4.5.3 偏序关系 定义 设R是非空集合A上的二元关系,如果关系R同 时具有自反性、反对称性和传递性,则称R是A上 的偏序关系,记作≤。读作“小于等于”。集合A 和A 上的一个偏序关系一起称为一个偏序集, 用<A, ≤>表示。 例如 整数集I上的整除关系R。当a,b∈I,a能整除b 时 ,<a,b>∈R,容易验证R是I上的偏序关系。 例 验证集合A={1,2,3} 的幂集P(A)上的包含关系?是 一个偏序关系。

利用偏序关系的性质可以用简化了的关系图形 象地表示一个偏序集,这种图称为哈斯图。哈斯图 可以从一般的关系图按以下的要求简化得到: ①由于偏序关系是自反的,偏序关系图各结点上 不再画自

回路。 ②由于偏序关系是反对称的,则关系图中如果两 个不同结点之间有有向弧,一定是单向,且箭头的 方向相同。因此,偏序关系图上省略每条有向弧的 箭头。 ③由于偏序关系是传递的,若<a,b>∈R, <b,c>∈R,则<a,c>∈R。在哈斯图中省略从结点a 到c的有向弧。

例4 设集合A={1,2,3,4,6,12}上的整除关系R,试画 出偏序关系R的哈斯图。
12 4 6

2 1

3

例5 偏序集< P(A), ? >,A={a,b,c}
试画出哈斯图。
解:由于 P ( A) ? {?, {a}, {b}, {c}, {a, b}, {a, c}, {b, c}, {a, b, c}} 所以

R? ? {? ? , ? ? , ? {a }, {a } ? , ? {b}, {b} ? , ? {c }, {c } ? , ? {a , b}, {a , b} ? , ? {a , c }, {a , c } ? , ? {b, c }, {b, c } ? , ? {a , b, c }, {a , b, c } ? , ? ? , {a } ? , ? ? , {b} ? , ? ? , {c } ? , ? {a }, {a , b} ? , ? {a }, {a , c } ? , ? {b}, {a , b} ? , ? {b}, {b, c } ? , ? {c }, {a , c } ? , ? {c }, {b, c } ? , ? {a , b}, {a , b, c } ? , ? {a , c }, {a , b, c } ? , ? {b, c }, {a , b, c } ? , ? ? , {a , b} ? , ? ? , {a , c } ? , ? ? , {b, c } ? , ? {a }, {a , b, c } ? , ? {b}, {a , b, c } ? , ? {c }, {a , b, c } ? }

例6 设A={2,3,6,12,24,36},A上的整除关系是一偏
序关系,其哈斯图如下:

B ? A,a ? B 定义4-26 设 ? A, ?? 为偏序集, , (1)若 ?x( x ? B ? a ? x ) 成立,则称a是B的最小元, (2)若 ?x( x ? B ? x ? a ) 成立,则称a是B的最大元, (3)若 ??y( y ? B ? y ? a) 成立,则称a是B的极小元, (4)若 成立,则称a是B的极大元, ??x( x ? B ? a ? x)

由定义4-26知,最小元与极小元是两个不同的概念, 他们的区别如下: (1)最小元是B中最小的元素,它与B中其他元素都 可比;而极小元不一定与B中其他元素都可比, 只要没有比它小的元素,它就是极小元; (2)对于有穷集合B,一定存在极小元,但不一定存 在最小元。 (3)对于有穷集合B,如果存在最小元,它一定是惟 一的;而极小元可以有多个。 (4)对于有穷集合B,如果只有一个极小元,则它一 定是B的最小元。 最大元与极大元也有同样的区别。

例7. 设A={a,b,c},对于偏序集 P( A), ?
集合
P( A)

极大元 {a,b,c}

极小元

?
{a }

最大元 最小元 {a,b,c} ? 无 {a,b} 无 {a }

{{a},{b},{c}} {a}, {b}, {c} {a}, {b}, {c} {{a},{a,b}}

{a,b}

例8 在例6中取B={6,12},C={2,3,6},则
集合 A
{6,12} {2,3,6}

极大元 24,36
12

极小元 2,3
6

最大元 无 12 6

最小元 无 6 无

6

2,3

定义: 设 ? A, ?? 为偏序集,B ? A , y? A, (1)若 ?x( x ? B ? x ? y ) 成立,则称y是B的上界, (2)若 ?x( x ? B ? y ? x ) 成立,则称y是B的下界, (3)令C={y|y为B的上界},则称C的最小元为B的最 小上界或上确界。 (4)令D={y|

y为B的下界},则称D的最大元为B的最 大下界或下确界。

例9. 设A={a,b,c},对于偏序集 P( A), ? ,
集合
P( A)

上界 {a,b,c} {a,b,c}

下界

{{a},{b},{c}}

? ?
{a},

上确界 {a,b,c} {a,b,c}

下确界

?
?
{a}

{{a},{a,b}}

{a,b}, {a,b,c}

?

{a,b}

例10 在例6中取B={12,24,36},C={2,3,6},则
集合 A
{12,24,36} {2,3,6}

上界 none
none

下界 none
2,3,6,12

上确界 none none
6 12 none

下确界 none 12
none 6 12

6,12,24,36 12,24,36 none

none 2,3,6 2,3,6,12

{6,12} {24,36}

通过以上例子可以看出界有以下性质: (1)一个集合可能没有上界或下界,若有,则 不一定唯一,并且它们可能在B中,也可能在B 外; (2)一个集合若有上下确界,必定是唯一的, 并且若是B的最大(小)元素,则它必是B的上 (下)确界。

练习
设偏序集<A,?>如下图所示,求 A 的极小元、最小 元、极大元、最大元. 设 B={b,c,d}, 求 B 的下界、 上界、下确界、上确界. 极小元:a, b, c, g; 极大元:a, f, h; 没有最小元与最大元. B的下界和下确界都 不存在, 上界有d 和 f, 上确界为 d.

课 后 作 业
P117: 4.16(2)


网站首页网站地图 站长统计
All rights reserved Powered by 海文库
copyright ©right 2010-2011。
文档资料库内容来自网络,如有侵犯请联系客服。zhit326@126.com