3-10等价关系与等价类.ppt

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是自反的 对称的 传递的 摘要 等价关系是一种特殊的二元关系 体现了关系的自反 对称和传递的性质 在计算机科学中有重要的应用 网格技术是近年来兴起的一种前沿信息技术 是一种信息社会的网络基础设施 它将互联网上的所有资源互通 更好地实现网络资源共享 网格服务是网格环境中资源的抽象和封装 它遵守网格服务规范 依据服务描述动态创建的WebService 本文基于等价关系的理论 提出了等价网格服务关系的概念以及资源的划分问题 为服务匹配 服务组合和服务协同的研究提供了理论的支持 等价关系在网络技术中的应用理论研究 潍坊学院学报刘海慧 主要内容 一 定义 定义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 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 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 定义3 集合A上的等价关系R 其等价类集合 a R 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 a A 中 a R A2 对任意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在同一个分块中 则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 R R1 R2 R3 例3A 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 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 a A A R2 a R2 a A R1 R2 对任意a A 有 a R1 x x A aR1x x x A aR2x a R2所以有 a R1 a A a R2 a A 即有A R1 A R2充分性 反之设 a R1 a A a R2 a A 对任意 a R1 A R1则有 c R2 A R2 使得 a R1 c R2所