南京大学：《离散数学》课程教学资源（PPT课件讲稿）Lecture 12 等价关系与偏序关系

1 等价关系与偏序关系

等价关系与偏序关系 1

回顾 口问题1：关系具有哪些重要性质？ 口自反性、对称性/反对称性、传递性 ▣问题2：如果计算关系的闭包？ a 自反闭包(R=RUIA、对称闭包s(R=RUR1、传递闭 包的Warshal算法

 问题1：关系具有哪些重要性质？  自反性、对称性/反对称性、传递性  问题2：如果计算关系的闭包？  自反闭包r(R) = RIA 、对称闭包s(R) = RR-1 、传递闭 包的Warshall算法 回顾

本节提要 3 口1：等价关系与等价类 口2：偏序关系、偏序集、偏序格

本节提要  1：等价关系与等价类  2：偏序关系、偏序集、偏序格 3

等价关系 口满足性质：自反、对称、传递。 “等于”关系的推广 口例子 口模3同余关系：RC ZxZ,xRy当且仅当 x-y 是整数。 3 口RcxN,xRy iff存在正整数kl,使得x=。 ■自反：若x是任意自然数，当然k=; ■对称：若有k以使x=；也就有k使=x, ■传递：若有k以使x=；并有m,n,使=；则有x如=ml

等价关系  满足性质：自反、对称、传递。  “等于”关系的推广  例子  模3同余关系: RZZ，xRy 当且仅当 是整数。  RNN，xRy iff 存在正整数k,l，使得x k=y l 。 ◼ 自反: 若x是任意自然数，当然x k=x k ; ◼ 对称：若有k,l, 使x k=y l；也就有l,k, 使y l=x k； ◼ 传递：若有k,l, 使x k=y l；并有m, n, 使y n=z m；则有 x kn=z ml 3 x − y

等价类 口R是非空集合A上的等价关系，x∈A,等价类 [☒R={U川EA∧xR 口每个等价类是A的一个非空子集。 口例：模3同余关系：R二xZ,xRy当且仅当 -y 是整数。 口3个等价类：[0]={…，-6，-3,0,3,6,9，…} [1]={…,-5,-2,1,4,7,…}; [2]={…,-4,-1,2,5,8,11,…}

等价类  R是非空 集合A上的等 价关系，xA，等价 类 [x]R={y| yA  xRy}  每个等价类是A的一个非空子集。  例：模3同余关系: RZZ，xRy 当且仅当 是整数。  ３个等价类： [0]={…, -6, -3, 0, 3, 6, 9, …}; [1]={…, -5, -2, 1, 4, 7, …}; [2]={…, -4, -1, 2, 5, 8, 11, …} 3 x − y