《等价关系和划分》PPT课件.ppt

《《等价关系和划分》PPT课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、08九月2021南京信息工程大学数理学院2第三章二元关系3.1基本概念3.2关系的合成3.3关系上的闭包运算3.4次序关系3.5等价关系和划分08九月2021南京信息工程大学数理学院3第3-5讲等价关系和划分1.等价关系2.划分3.划分的积与和4.第3-5讲作业08九月2021南京信息工程大学数理学院4等价关系是最重要、最常见的二元关系之一。它有良好的性质。在计算机科学和计算机技术、信息科学和信息工程中都有广泛的应用。定义1设RA×A，如果R是自反的、对称的和传递的，则称R是A上的等价关系。设R是等价关系，若x,yR，称x等价于y。例如：三角形的相似关系是等价关系等价关系的特性关

2、系矩阵：主对角线全为1且是对称矩阵；关系图：每一个结点上都有自回路；每两个不同结点间或没有弧线连接，或有成对弧出现。1、等价关系08九月2021南京信息工程大学数理学院5例1设A=1,2,3,4,5，R是A上的二元关系，R=1,1,1,2,2,1,2,2,3,3,3,4,4,3,4,4,5,5，证明R是A上的等价关系。证明：写出R的关系矩阵MR如下：MR的主对角线全为1且是对称阵，所以R是自反的和对称的；还可以用二元关系传递性的定义证明R是传递的。故R是A上的等价关系。08九月2021南京信息工程大学数理学院6在R的关系图中每一个结点上都有自回

3、路；每两个不同结点间如果有边，一定有方向相反的两条边。所以R是自反的和对称的。与前面一样，也可以用二元关系传递性的定义证明R是传递的。故R是A上的等价关系。注：等价关系R的关系图被分为三个互不连通的部分。每部分中的结点两两都有关系，不同部分中的任意两个结点则没有关系。08九月2021南京信息工程大学数理学院7定义2设x和y是两个整数，k是一个正整数，若x，y用k除的余数相等，就称x和y模k同余，也称x和y模k等价。记为x≡y(modk)设x(y)用k除的商为t1(t2)，余数为a1(a2)，数学上将x(y)表示成为：x=k×t1＋a1，t1I，a1I且0≤a1＜k。y=k×t2＋a2

4、，t2I，a2I且0≤a2＜k。若x，y用k除的余数相等，x-y=k×(t1-t2)，t1-t2I。即x-y可以被k整除。所以，x和y模k同余还可以描述为：x-y可以被k整除。08九月2021南京信息工程大学数理学院8例2设R=x,yxI∧yI∧x≡y（modk）是整数集合I上的二元关系。证明R是等价关系。证明：设a,b,c是任意的整数。⑴因为a-a=k×0，所以a≡amodk，a,aR。故R是自反的。⑵若a,bR，a≡bmodk，a-b=k×t，tI，b-a=-(a-b)=k×(–t)，–tI，b≡amodk，b,aR。故R是对称的。⑶若a,

5、bR且b,cR，a-b=k×t1，t1I，b-c=k×t2，t2I，a-c=(a-b)+(b-c)=k×t1+k×t2=k×(t1+t2)，t1+t2I，a,cR，故R是传递的。所以R是整数集合I上的等价关系。08九月2021南京信息工程大学数理学院9定义3设R是A上的等价关系，xA，集合yyA∧xRy叫做x形成的R等价类。记为[x]R在例1中，等价关系R等价类为：[1]R=[2]R=1,2，[3]R=[4]R=3,4，[5]R=5。在R的关系图中，三个互不连通的部分，每一部分中的所有结点构成一个等价类。上述模3等价关系的等价类叫模3等价类，

6、模3等价类有以下三个：[0]R=…，–6，–3，0，3，6，…[1]R=…，–5，–2，1，4，7，…[2]R=…，–4，–1，2，5，8，…定理1设R是X上的等价关系，xX，则有⑴[x]RX⑵x[x]R08九月2021南京信息工程大学数理学院10注：等价关系的任何等价类是该等价关系前域(或陪域)的子集。例如，模3等价类是整数集合的子集：[0]RI，[1]RI，[2]RI。任何等价类是非空集合。x形成的R等价类[x]R至少有一个元素x。例如，在模3等价类中，0[0]R，1[1]R，2[2]R。定理2设R是X上的等价关系，对于X的任意元素a和b，aRb的充分

7、必要条件是[a]R=[b]R证明：设aRb，下证[a]R=[b]Rc[a]R，aRc，由R的对称性有cRa，由条件aRb和R的传递性得cRb，再根据R的对称性有bRc，c[b]R，故[a]R[b]R。类似地可以证明[b]R[a]R。这就证明了[a]R=[b]R。设[a]R=[b]R，下证aRb。由定理1知a[a]R，因为[a]R=[b]R，所以a[b]R，bRa，由R的对称性有aRb。08九月2021南京信息工程大学数理