等价关系与等价类.ppt

等价关系与等价类.ppt

ID:51171319

大小:296.50 KB

页数:24页

时间:2020-03-19

等价关系与等价类.ppt_第1页
等价关系与等价类.ppt_第2页
等价关系与等价类.ppt_第3页
等价关系与等价类.ppt_第4页
等价关系与等价类.ppt_第5页
资源描述:

《等价关系与等价类.ppt》由会员上传分享,免费在线阅读,更多相关内容在教育资源-天天文库

1、3-10等价关系与等价类离散数学复习自反性(reflexive)定义:设R为定义在集合A上的二元关系,如果对于每个x∈A,都有∈R,即xRx,则称二元关系R是自反的。对称性(symmetric)定义:设R为定义在集合A上的二元关系,如果对于每个x,y∈A,每当∈R,就有∈R,则称集合A上关系R是对称的。传递性(transitive)定义:设R为定义在集合A上的二元关系,如果对于任意x,y,z∈A,每当∈R且∈R,就有∈R,称关系R在A上是传递的。R1是对称的。R2是自反

2、的、对称的、传递的。等价关系与等价类的基本概念1等价关系的基本性质2主要内容商集与集合的划分33一、定义定义1:设R为定义在集合A上的一个关系,若R是自反的,对称的和传递的,则称R为集合A上的等价关系。例如平面上三角形集合中,三角形的相似关系;同学集合A={a,b,c,d,e,f,g},A中的关系R:住在同一宿舍;同性关系。例1设T={1,2,3,4},R={<1,1>,<1,4>,<4,1>,<4,4>,<2,2>,<2,3>,<3,2>,<3,3>}。验证R是集合T上的等价关系。例2设A={1,2,…,8},如下定义A上的关

3、系R:R={

4、x,yA且x≡y(mod3)}证明R为A上的等价关系。证明:xA,因为x-x=0=0×3,所以∈R;x,yA,若x-y=3t(t为整数),则有:y-x=-3t,即∈R;x,y,zA,若x-y=3t,y-z=3s,则有:x-z=3(t+s),即∈R.关系图如下图所示.等价类定义2:设R为集合A上的等价关系,对任意a∈A,集合[a]R={x

5、x∈A,∈R}称为元素a关于R的等价类。例2可求出三个不同的等价类[1]R=[4]R=[7]R={1,4,7}[2]

6、R=[5]R=[8]R={2,5,8}[3]R=[6]R={3,6}定义3:集合A上的等价关系R,其等价类集合{[a]R

7、a∈A}称作A关于R的商集(quotientset)。记作A/R(1)a∈[a]R(2)定理1:设给定集合A上的等价关系R,对于a,b∈A,若∈R,iff[a]R=[b]R。二、性质(3)设R为集合A上的等价关系,则任意a,b∈A,若R,则证明设集合A上的一个等价关系R,则[a]R是A的一个子集,则所有这样的子集可做成商集A/R1、A/R={[a]R

8、a∈A}中, ∪[a]R=A2、对任意

9、a∈A,都有aRa,即a∈[a]R,即A中的每一个元素都属于一个分块。3、A的每个元素只能属于一个分块反证设a∈[b]R,a∈[c]R,且[b]R≠[c]R,则bRa,cRa成立,所以有aRc,所以bRc,即[b]R=[c]R所以A/R是A上对应于R的一个划分。定理2:集合A上的等价关系R,决定了A的一个划分,该划分就是商集A/R。三商集与集合的划分证明:设集合A的一个划分S={S1,S2…Sm},现定义一个关系:aRb当且仅当a,b在同一个分块中。则R是一个等价关系。①、a与a在同一个分块中,则有aRa,即自反性②、a与b在同

10、一个分块中,则b与a在同一个分块中,即若aRb,有bRa,故R是对称的。③、a与b在同一个分块中,b与c在同一个分块中,而由划分的定义b只能属于且属于一个分块,故a与c必在同一分块中,即若有aRb,bRc则必有aRc,即传递性成立。所以R是一个等价关系。S=A/R定理3集合A的一个划分确定A的元素间的一个等价关系。说明等价关系——等价类——商集——划分A上的等价关系与A的划分是一一对应的。R1={a,b}x{a,b}={}R2={c}x{c}={}R3={d,e}x{d,e}={

11、}R=R1∪R2∪R3例3 A={a,b,c,d,e},S={{a,b},{c},{d,e}},求由S确定的R。例4设A={a,b,c,d,e},R={〈a,a〉,〈a,b〉,〈a,c〉,〈b,b〉,〈b,a〉,〈b,c〉,〈c,c〉,〈c,a〉,〈c,b〉,〈d,d〉,〈d,e〉,〈e,e〉,〈e,d〉},其有向图如图所示,则R诱导的划分S={{a,b,c},{d,e}}.反之,若A的划分S={{a,b,c},{d,e}},则所诱导的等价关系R={a,b,c}×{a,b,c}∪{d,e}

12、×{d,e}={〈a,a〉,〈a,b〉,〈a,c〉,〈b,b〉,〈b,a〉,〈b,c〉,〈c,c〉,〈c,a〉,〈c,b〉,〈d,d〉,〈d,e〉,〈e,e〉,〈e,d〉}证明必要性:A/R1={[a]R1

13、a∈A},A/R2={[a]R2

14、a∈A}R1=R2,

当前文档最多预览五页,下载文档查看全文

此文档下载收益归作者所有

当前文档最多预览五页,下载文档查看全文
温馨提示:
1. 部分包含数学公式或PPT动画的文件,查看预览时可能会显示错乱或异常,文件下载后无此问题,请放心下载。
2. 本文档由用户上传,版权归属用户,天天文库负责整理代发布。如果您对本文档版权有争议请及时联系客服。
3. 下载前请仔细阅读文档内容,确认文档内容符合您的需求后进行下载,若出现内容与标题不符可向本站投诉处理。
4. 下载文档时可能由于网络波动等原因无法下载或下载错误,付费完成后未能成功下载的用户请联系客服处理。