【集合论】等价关系 ( 等价关系概念 | 等价关系示例 | 等价关系与闭包 )
文章目录 一、等价关系二、等价关系示例三、等价关系与闭包示例 一、等价关系 等价关系概念 : A A A 集合是非空集合 , A ≠ ∅ A \not= \varnothing A
admin
文章目录
一、等价关系二、等价关系示例三、等价关系与闭包示例
一、等价关系
等价关系概念 :
A
A
A 集合是非空集合 ,
A
≠
∅
A \not= \varnothing
A=∅ , 并且
R
R
R 关系是
A
A
A 集合上的二元关系 ,
R
⊆
A
×
A
R \subseteq A\times A
R⊆A×A ;
如果
R
R
R 关系是 自反 , 对称 , 传递 的 , 那么称
R
R
R 关系是 等价关系 ;
二、等价关系示例
1. 关系
1
1
1 :
x
x
x 与
y
y
y 年龄相同 ;
自反 :
x
x
x 与
x
x
x 年龄相同 ; 自反 成立 ;对称 :
x
x
x 与
y
y
y 年龄相同 ,
y
y
y 与
x
x
x 年龄相同 ; 对称 成立 ;传递 :
x
x
x 与
y
y
y 年龄相同 ,
y
y
y 与
z
z
z 年龄相同 ,
x
x
x 与
z
z
z 年龄相同 ; 传递 成立 ;等价关系 : 该关系是 自反 , 对称 , 传递 的 , 因此该关系 是等价关系 ;
由上边可以看出 , 等价关系是用于分类的 , 同一年出生的人可以划分到一个等价类中 ;
2. 关系
2
2
2 :
x
x
x 与
y
y
y 姓氏相同 ;
自反 :
x
x
x 与
x
x
x 姓氏相同 ; 自反 成立 ;对称 :
x
x
x 与
y
y
y 姓氏相同 ,
y
y
y 与
x
x
x 姓氏相同 ; 对称 成立 ;传递 :
x
x
x 与
y
y
y 姓氏相同 ,
y
y
y 与
z
z
z 姓氏相同 ,
x
x
x 与
z
z
z 姓氏相同 ; 传递 成立 ;等价关系 : 该关系是 自反 , 对称 , 传递 的 , 因此该关系 是等价关系 ;
3. 关系
3
3
3 :
x
x
x 年龄大于等于
y
y
y ;
自反 :
x
x
x 年龄大于等于
x
x
x ; 自反 成立 ;对称 :
x
x
x 年龄大于等于
y
y
y ,
y
y
y 年龄大于等于
x
x
x ; 对称 不成立 ;传递 :
x
x
x 年龄大于等于
y
y
y ,
y
y
y 年龄大于等于
z
z
z ,
x
x
x 年龄大于等于
z
z
z ; 传递 成立 ;等价关系 : 该关系是 自反 , 传递 的 , 不是对称的 , 因此该关系 不是等价关系 ;
4. 关系
4
4
4 :
x
x
x 与
y
y
y 选修同一门课程 ;
自反 :
x
x
x 与
x
x
x 选修同一门课程 ; 自反 成立 ;对称 :
x
x
x 与
y
y
y 选修同一门课程 ,
y
y
y 与
x
x
x 选修同一门课程 ; 对称 成立 ;传递 :
x
x
x 与
y
y
y 选修同一门课程 ,
y
y
y 与
z
z
z 选修同一门课程 ,
x
x
x 与
z
z
z 选修同一门课程 ; 上述情况不一定成立 ,
x
,
y
x,y
x,y 可能同时选修音乐 ,
y
,
z
y,z
y,z 同时选修历史 ,
x
,
z
x,z
x,z 没有选修相同的课程 ; 传递 不成立 ;等价关系 : 该关系是 自反 , 对称 的 , 不是传递的 , 因此该关系 不是等价关系 ;
5. 关系
5
5
5 :
x
x
x 体重大于
y
y
y ;
自反 :
x
x
x 体重大于
x
x
x ; 自反 不成立 ;对称 :
x
x
x 体重大于
y
y
y ,
y
y
y 体重大于
x
x
x ; 对称 不成立 ;传递 :
x
x
x 体重大于
y
y
y ,
y
y
y 体重大于
z
z
z ,
x
x
x 体重大于
z
z
z ; 传递 成立 ;等价关系 : 该关系是 传递 的 , 不是 自反 , 对称 的 , 因此该关系 不是等价关系 ;
三、等价关系与闭包示例
A
A
A 集合是非空集合 ,
A
≠
∅
A \not= \varnothing
A=∅ , 并且
R
R
R 关系是
A
A
A 集合上的二元关系 ,
R
⊆
A
×
A
R \subseteq A\times A
R⊆A×A ;
对
R
R
R 关系求三种闭包 , 有
6
6
6 种不同的顺序 , 讨论这些求闭包结果的性质 ;
6
6
6 种求闭包的性质 :
r
t
s
(
R
)
rts(R)
rts(R) : 先求对称闭包 , 再求传递闭包 , 最后求自反闭包 ;
t
r
s
(
R
)
trs(R)
trs(R) : 先求对称闭包 , 再求自反闭包 , 最后求传递闭包 ;
t
s
r
(
R
)
tsr(R)
tsr(R) : 先求自反闭包 , 再求对称闭包 , 最后求传递闭包 ;
r
s
t
(
R
)
rst(R)
rst(R) : 先求传递闭包 , 再求对称闭包 , 最后求自反闭包 ;
s
r
t
(
R
)
srt(R)
srt(R) : 先求传递闭包 , 再求自反闭包 , 最后求对称闭包 ;
s
t
r
(
R
)
str(R)
str(R) : 先求自反闭包 , 再求传递闭包 , 最后求对称闭包 ;
参考 : 【集合论】关系闭包 ( 关系闭包求法 | 关系图求闭包 | 关系矩阵求闭包 | 闭包运算与关系性质 | 闭包复合运算 ) 五、闭包复合运算
r
s
(
R
)
=
s
r
(
R
)
rs(R) = sr(R)
rs(R)=sr(R) : 对称闭包 与 自反闭包 的复合运算 , 无论顺序如何 , 先求哪个都一样 ;
r
t
(
R
)
=
t
r
(
R
)
rt(R) = tr(R)
rt(R)=tr(R) : 传递闭包 与 自反闭包 的复合运算 , 无论顺序如何 , 先求哪个都一样 ;
s
t
(
R
)
⊆
t
s
(
R
)
st(R) \subseteq ts(R)
st(R)⊆ts(R) : 传递闭包 与 对称闭包 的符合运算 , 顺序不同 , 其计算结果不同 ;
因此这里分为两大类
① 先求传递闭包 , 再求对称闭包② 先求对称闭包 , 再求传递闭包
先求对称闭包 , 再求传递闭包 :
r
t
s
(
R
)
rts(R)
rts(R) : 先求对称闭包 , 再求传递闭包 , 最后求自反闭包 ;
t
r
s
(
R
)
trs(R)
trs(R) : 先求对称闭包 , 再求自反闭包 , 最后求传递闭包 ;
t
s
r
(
R
)
tsr(R)
tsr(R) : 先求自反闭包 , 再求对称闭包 , 最后求传递闭包 ;
固定 ts 运算的顺序 , 先 t 后 s , r 运算可以放在任意位置 ;
自反与其它两个闭包运算没有冲突 , 在任意位置都可以 ;
对称与传递 , 后求的传递 , 因此其结果是传递的 ;
上述三个顺序产生的结果是 自反 , 对称 , 传递 的 , 其满足等价关系 , 结果是 等价闭包 ;
先求对传递包 , 再求对称闭包 :
r
s
t
(
R
)
rst(R)
rst(R) : 先求传递闭包 , 再求对称闭包 , 最后求自反闭包 ;
s
r
t
(
R
)
srt(R)
srt(R) : 先求传递闭包 , 再求自反闭包 , 最后求对称闭包 ;
s
t
r
(
R
)
str(R)
str(R) : 先求自反闭包 , 再求传递闭包 , 最后求对称闭包 ;
固定 st 运算的顺序 , 先 s ( 对称闭包 ) 后 t ( 传递闭包 ) , r ( 对称闭包 ) 运算可以放在任意位置 ;
自反与其它两个闭包运算没有冲突 , 在任意位置都可以 ;
对称与传递 , 先求的传递 , 然后求对称 , 对称会破坏传递 , 因此其结果不是传递的 ;
上述三个顺序产生的结果是 自反 , 对称 , 不传递 的 , 其不满足等价关系 ;
r
t
s
(
R
)
=
t
r
s
(
R
)
=
=
t
s
r
(
R
)
rts(R)=trs(R)==tsr(R)
rts(R)=trs(R)==tsr(R)
r
s
t
(
R
)
=
s
r
t
(
R
)
=
s
t
r
(
R
)
rst(R) = srt(R) = str(R)
rst(R)=srt(R)=str(R)自反成立成立对称成立成立传递成立不成立等价关系成立 ( 该闭包称为等价闭包 )不成立