《等价关系与等价类》PPT课件

《《等价关系与等价类》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、、传递的。摘要：等价关系是一种特殊的二元关系,体现了关系的自反、对称和传递的性质,在计算机科学中有重要的应用。网格技术是近年来兴起的一种前沿信息技术,是一种信息社会的网络基础设施,它将互联网上的所有资源互通,更好地实现网络资源共享。网格服务是网格环境中资源的抽象和封装,它遵守网格服务规范,依据服务描述动态创建的WebService。本文基于等价关系的理论,提出了等价网格服务关系的概念以及资源的划分问题,为服务匹配、服务组合和服务协同的研究提供了理论的支持。等价关系在网络技术中的应用理论研究潍坊学院学报刘海慧等价关系与等价类的基本概念1等价

3、关系的基本性质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上的关系R:R={

4、x,yA且x≡y（mod3)}证明R

5、为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

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

7、3:集合A上的等价关系R，其等价类集合{[a]R

8、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

9、a∈A}中,∪[a]R=A2、对任意a∈A，都有aRa，即a∈[a]R，即A中的每一个元素都属于一个分块。3、A的每个元

10、素只能属于一个分块反证设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在同一个分块中，则b与a在同一个分块中，即若aRb，有bRa，故R是对称的。③、a与b在同一个分块

11、中，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}={}R=R1∪R2∪R3例3A={a,b,c,d,e}，S＝{{a

12、,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〉