离散-关系-.ppt

《离散-关系-.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第四章关系第三节关系类型一、等价关系集合中的各个元素总是具有某些有用的性质，时常不是把这些元素作为单一的个体，逐个地对待它们；而是按它们所具有的性质进行分类，并根据这些性质处理它们，或者是使用它们。在处理实际问题时，可以不去考察那些不感兴趣的性质，而专注于感兴趣的某些性质。凡是具有同样性质的元素，可以看成是不可区分的或相互等价的，也称它们之间存在等价关系。第三节关系类型一、等价关系定义：设R是集合A上的二元关系，若R是自反的、对称的和可传递的，则称R是A上的等价关系。若R，或者xRy，称x等价y，记做x~y

2、等价关系因为R是自反的，因此R的关系图中每个结点都有有向环因为R是对称的，因此R的关系图中的有向弧都是成对出现，即若有从a到b的弧，必定有从b到a的弧(任意两个结点间或没有弧连接，或有成对的弧出现)。因为R是传递的，因此若有从a到b的弧以及从b到c的弧，必定有从a到c的弧等价关系例4.3.1同学集合A={a,b,c,d,e,f}，A中的关系R是“住在同一个房间”。问：R是等价关系吗？答：是。1)任何一个人都和自己住在同一房间，因此R是自反的2)若x和y住在同一房间（即xRy），则y和x也住在同一房间（即yRx），因此R是对

3、称的3)若x和y住在同一房间(xRy)，并且y和z住在同一房间(yRz)，则x和z住在同一房间(xRz)，因此R是传递的等价关系假设a和b住在同一房间，d和e和f住在同一房间，c住一间。则R={,,,,,,,,,,,,,}关系图为：abcefd等价关系整数集合Z中的相等关系、在全集U所有子集的集合中的相等关系，以及命题演算中的命题集合的关系等都是等价关系空集上的任意二元关系R是

4、等价关系等价关系定义：设m是一个正整数，a和b都是整数，若存在某整数k，使得a-b=km，则称a与b是模m等价，记为ab(modm)m叫作等价的模数等价关系定理：模m等价是任何集合AZ上的等价关系。证明：如果A=，那么模m等价是A上的等价关系。若A≠，设任意a,b,cA，将模m等价记为R1)因为a–a=0·m，因此R是自反的2)假设有aRb，则存在一个整数k，使得a-b=k·m，则b-a=-k·m，所以有bRa，所以R是对称的3)假设有aRb和bRc，则存在整数p和q，使得a-b=p·m，b-c=q·m，所以a

5、-c=(a-b)+(b-c)=(p+q)·m因此R是传递的综上所述，R是自反的、对称的和传递的，所以它是等价关系。等价类定义：设R是非空集合A上的等价关系，对于任意aA，令[a]R={x

6、xA∧aRx}称[a]R是a关于R的等价类，简称a的等价类，简记为[a]。称a为[a]R的表示元素。（[a]R称为元素a形成的R的等价类）若等价类个数有限，则R的不同等价类的个数叫作R的秩。对于任意aA，[a]R非空，因为a[a]R按照R等价类的定义，是由集合A中与a有等价关系R的所有元素，构成集合[a]R。常用[a]代替[a]R

7、因此，任给集合A及其上的等价关系R，必可写出A上各个元素的等价类等价类例4.3.2设A={a,b,c,d,e,f},R={,,,,,,,,,,,,,}，则等价关系R的关系图是：abcefd等价关系R的等价类如下：[a]R=[b]R={a,b}，[c]R={c}[d]R=[e]R=[f]R={d,e,f}等价关系R的秩是3等价类例4.3.3若R是整数集合Z上的模4等价关系，则等价类有：[

8、0]R={…,-8,-4,0,4,8,…}=[4]R=[-4]R=……[1]R={…,-7,-3,1,5,9,…}=[5]R=[-3]R=……[2]R={…,-6,-2,2,6,10,…}=[6]R=[-2]R=……[3]R={…,-5,-1,3,7,11,…}=[7]R=[-1]R=……每个等价类中的元素互相等价。若R是整数集合Z上的模2等价关系，则等价类有[0]R={…,-4,-2,0,2,4,…}=[2]R=[-2]R=……[1]R={…,-3,-1,1,3,5,…}=[3]R=[-1]R=……等价类定理1：设R是

9、非空集合A上的等价关系，对于任意a,bAaRb[a]=[b]证明：1)若[a]=[b]，则a[a]=[b]，所以bRa，根据R的对称性，可知有：aRb2)若aRb，对于任意x[a]，有aRx，所以也有xRa根据R的传递性，可知有xRb；根据R的对称性，可知有bRx则x[b]，所以[a][b]