《等价关系和划分.ppt》由会员分享，可在线阅读，更多相关《等价关系和划分.ppt（20页珍藏版）》请在三一办公上搜索。
1、2023年10月17日星期二,南京信息工程大学数理学院,2,第三章 二元关系,3.1 基本概念3.2 关系的合成3.3 关系上的闭包运算3.4 次序关系3.5 等价关系和划分,2023年10月17日星期二,南京信息工程大学数理学院,3,第3-5讲 等价关系和划分,1.等价关系2.划分3.划分的积与和4.第3-5讲 作业,2023年10月17日星期二,南京信息工程大学数理学院,4,等价关系是最重要、最常见的二元关系之一。它有良好的性质。在计算机科学和计算机技术、信息科学和信息工程中都有广泛的应用。定义1 设RAA，如果R是自反的、对称的和传递的，则称R是A上的等价关系。设R是等价关系，若x,yR
2、，称x等价于y。例如：三角形的相似关系是等价关系 等价关系的特性 关系矩阵：主对角线全为1且是对称矩阵；关系图：每一个结点上都有自回路；每两个不同结点间或没有弧线连接，或有成对弧出现。,1、等价关系,2023年10月17日星期二,南京信息工程大学数理学院,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上的等价关系。,2023年10月17日星期二,南
3、京信息工程大学数理学院,6,在R的关系图中每一个结点上都有自回路；每两个不同结点间如果有边，一定有方向相反的两条边。所以R是自反的和对称的。与前面一样，也可以用二元关系传递性的定义证明R是传递的。故R是A上的等价关系。注：等价关系R的关系图被分为三个互不连通的部分。每部分中的结点两两都有关系，不同部分中的任意两个结点则没有关系。,2023年10月17日星期二,南京信息工程大学数理学院,7,定义2 设x和y是两个整数，k是一个正整数，若x，y用k除的余数相等，就称x和y模k同余，也称x和y模k等价。记为 x y(mod k)设x(y)用k除的商为t1(t2)，余数为a1(a2)，数学上将x(y)
4、表示成为：x=kt1a1，t1I，a1I 且 0a1k。y=kt2a2，t2I，a2I 且 0a2k。若x，y用k除的余数相等，x-y=k(t1-t2)，t1-t2I。即x-y可以被k整除。所以，x和y模k同余还可以描述为：x-y可以被k整除。,2023年10月17日星期二,南京信息工程大学数理学院,8,例2 设R=x,y xI yI x y（mod k）是整数集合I上的二元关系。证明R是等价关系。证明：设a,b,c是任意的整数。因为 a-a=k0，所以 aa mod k，a,aR。故R是自反的。若a,bR，a b mod k，a-b=kt，tI，b-a=-(a-b)=k(t)，tI，ba m
5、od k，b,aR。故R是对称的。若a,bR且b,cR，a-b=kt1，t1I，b-c=kt2，t2 I，a-c=(a-b)+(b-c)=kt1+kt2=k(t1+t2)，t1+t2I，a,cR，故R是传递的。所以R是整数集合I上的等价关系。,2023年10月17日星期二,南京信息工程大学数理学院,9,定义3 设R是A上的等价关系，xA，集合y yAxRy 叫做x形成的R等价类。记为 xR 在例1中，等价关系R等价类为：1R=2R=1,2，3R=4R=3,4，5R=5。在R的关系图中，三个互不连通的部分，每一部分中的所有结点构成一个等价类。上述模3等价关系的等价类叫模3等价类，模3等价类有以下
6、三个：0R=，6，3，0，3，6，1R=，5，2，1，4，7，2R=，4，1，2，5，8，定理1 设 R是X上的等价关系，xX，则有 xRX xxR,2023年10月17日星期二,南京信息工程大学数理学院,10,注：等价关系的任何等价类是该等价关系前域(或陪域)的子集。例如，模3等价类是整数集合的子集：0RI，1RI，2RI。任何等价类是非空集合。x形成的R等价类xR至少有一个元素x。例如，在模3等价类中，00R，11R，22R。定理2 设R是X上的等价关系，对于X的任意元素a和b，aRb 的充分必要条件是aR=bR 证明：设aRb，下证 aR=bR caR，aRc，由R的对称性有cRa，由条
7、件aRb和R的传递性得cRb，再根据R的对称性有bRc，cbR，故aRbR。类似地可以证明 bRaR。这就证明了aR=bR。设 aR=bR，下证aRb。由定理1知aaR，因为aR=bR，所以abR，bRa，由R的对称性有aRb。,2023年10月17日星期二,南京信息工程大学数理学院,11,定义4 设A是非空集合，=S1，S2，Sm，Si，i=1,m，且满足：Si，SiA S1S2Sm=A则称是A的一个覆盖。定义5 设A是非空集合，=S1，S2，Sm，Si，i=1,m，是A的一个覆盖，满足SiSj=，ij，则称是A的一个划分。称Si，i=1,m，是A的划分块。定义中的“SiSj=，ij”是指中
8、的元素两两互不相交。,2、划分,2023年10月17日星期二,南京信息工程大学数理学院,12,例3 设 A=a,b,c，以下是A的子集构成的集合：S=a,b,b,c Q=a,a,b,a,c D=a,b,c G=a,b,c E=a,b,c F=a,a,c 试确定哪些集合是A的覆盖？哪些集合是A的划分？哪些集合既不是覆盖，也不是划分？解：S和Q是A的覆盖，但不是划分；D、G和E是A的覆盖，也是划分；F不是A的覆盖，也不是划分。,2023年10月17日星期二,南京信息工程大学数理学院,13,集合G=a,b,c是单元素集，它有一个元素a,b,c。对单元素集a,b,c，认为它的元素的并集就是a,b,c，
9、同时也认为它的元素是两两互不相交的。所以集合G=a,b,c是A的划分。在A的所有划分中基数最大的划分叫做A的最大划分，基数最小的划分叫做A的最小划分。在例3中，E是A的最大划分，G是A的最小划分。,2023年10月17日星期二,南京信息工程大学数理学院,14,例4 设A=1,2,3，试确定A的所有划分。解：有一个划分块的划分是：1,2,3 有两个划分块的划分是：1,2,3 2,1,3 3,1,2 有三个划分块的划分是：1,2,3 图3.9是A的所有划分的示意图。(a)表示有一个划分块的划分1,2,3。(b)、(c)和(d)表示有两个划分块的划分1,2,3、2,1,3和3,1,2。(e)表示有三
10、个划分块的划分1,2,3。,2023年10月17日星期二,南京信息工程大学数理学院,15,定理3 设 R是X上的等价关系，X关于R的商集X/R是X 的一个划分。,定义6 设R是X上的等价关系，R的所有等价类组成的集合xRxX叫做X关于R的商集。记为X/R。,在例1中，等价关系R 有三个等价类：1R=2R=1,2，3R=4R=3,4，5R=5，A关于R的商集 A/R=1R，2R，5R=1,2，3,4，5,模3等价关系R的等价类有以下三个：0R，1R和2R，由它确定的整数集合I关于R的商集I/R=0R，1R，2R,2023年10月17日星期二,南京信息工程大学数理学院,16,定理4 设S=S1，S
11、2，Sm是X的一个划分，R=x,y|x和y在同一个划分块中，则R是X上的等价关系。证明：设xX=S1S2Sm，因为S是X的一个划分，所以存在惟一的划分块SjS，使xSj，于是有x,xR，即R是自反的。设x,yR，x和y在某个划分块Sj中，则y和x也在划分块Sj中，所以y,xR，即R是对称的。设x,yRy,zRx和y在Si中且y和z在Sj中 ySiSj，因为S是X的一个划分，其中元素两两互不相交，故必有Si=Sjx和z在Sj中x,zR，即R是传递的。将定理4中的等价关系R叫做划分S导出的等价关系。划分S导出的等价关系R也可以表示为：R=(S1S1)(S2S2)(SmSm),2023年10月17日
12、星期二,南京信息工程大学数理学院,17,例5 设X=1,2,3,4，X的划分S=1，2,3，4，试写出S导出的等价关系R。解：R=1,1,2,2,2,3,3,2,3,3,4,4=112,32,344可以验证R是X上的等价关系。定理5 设R，S是集合X上的等价关系，则R=S当且仅当 X/R=X/S 证明：设R=S，证明X/R=X/S。先证 xX，xR=xS axRxRaxSaaxS，所以xRxS。类似地可以证明 xS xR，这就证明了xR=xS。,2023年10月17日星期二,南京信息工程大学数理学院,18,再证 X/R=X/S。xRX/R，xR=xSX/S，即xRX/S，所以X/RX/S。类似
13、地可以证明X/SX/R，于是X/R=X/S。设X/R=X/S，证明R=S。因为X/R=X/S，aRX/R，必存在cSX/S，使aR=cS a,bRaRbbaRbaRaaR bcSacS cSbcSabSccSa(因为S是对称的)bSa(因为S是传递的)aSb(因为S是对称的)a,bS 所以R S。类似地可以证明S R，于是R=S。,2023年10月17日星期二,南京信息工程大学数理学院,19,例6 设X=1,2,3，写出集合X上的所有等价关系。解：先写出集合X上的所有划分，它们是：S1=1,2,3，S2=1,2,3，S3=1,3,2 S4=2,3,1,S5=1,2,3 对应的等价关系为：R1=1,2,31,2,3=XX R2=1,21,233=1,1,1,2,2,1,2,2,3,3 R3=1,31,322=1,1,1,3,3,1,3,3,2,2 R4=2,32,311=2,2,2,3,3,2,3,3,1,1 R5=112233=1,1,2,2,3,3=IX,2023年10月17日星期二,南京信息工程大学数理学院,20,Thank you very much!,谢谢您的光临，再见！,
