离散数学析_第3章集合与关系——特殊关系.ppt

《离散数学析_第3章集合与关系——特殊关系.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、离散数学计算机学院05八月2021第三部分特殊关系第3章集合与关系内容提要偏序关系2等价关系1判定下列关系具有哪些性质1、在全体中国人所组成的集合上定义的“同姓”关系；2、对任何非空集合A，A上的全关系；3、三角形的“相似关系”、“全等关系”；解：都具有自反性，对称性和传递性；等价关系3.9等价关系定义3.9.1设R是定义在非空集合A上的关系，如果R是自反的、对称的、传递的，则称R为A上的等价关系。由定义3.9.1知：（1）关系R是等价关系当且仅当R同时具备自反性、对称性和传递性；（2）关系R不是等价关系当且仅当R不具备自反性或对称性或传递性。判断是否等价关系(A是某班

2、学生):R1={

3、x,yAx与y同年生}R2={

4、x,yAx与y同姓}R3={

5、x,yAx的年龄不比y小}R4={

6、x,yAx与y选修同门课程}R5={

7、x,yAx的体重比y重}例3.9.1例：设有一个整数集Z上的关系R：R={

8、x-y可被3整除}证明R是Z上等价关系。证①对每个xZ,x-x可被3整除，所以是自反的。②对于x,yZ,如果x-y能被3整除，则y-x也能被3整除所以是对称的。③对于x,yZ,如果有x-y，y-z均能被3整除，则x-z=(x-y)+(y-z)亦能被3整除，所以是

9、传递的。综合起来，R是Z上等价关系。例：设A={1，2，…，8}如下定义A上的关系：R={

10、x,yAxy(mod3)}。解：R={<1,1>,<1,4>，<4,4>，<4,7>,<1,7>,<2,2>,<2,5>,<2,8>,<3,3>,<3,6>，<4,1>，<5,2>,<5,5>,<5,8>,<6,3>，<6,6>，<7,1>,<7,4>,<7,7>,<8,2>,<8,5>,<8,8>}R满足自反、对称和传递，所以，R是等价关系。R的关系图为：以n为模的同余关系(CongruenceRelation)R称为Z上以n为模的同余关系。R将Z分成了如下n个子

11、集：[0]={…,-3n,-2n,-n,0,n,2n,3n,…}[1]={…,-3n+1,-2n+1,-n+1,1,n+1,2n+1,3n+1,…}[2]={…,-3n+2,-2n+2,-n+2,2,n+2,2n+2,3n+2,…}…[n-1]={…,-2n-1,-n-1,-1,n-1,2n-1,3n-1,4n-1,…}说明这n个Z的子集具有如下特点：1、在同一个子集中的元素之间都有关系R；2、不同子集的元素之间没有关系R；3、不同子集的交集是空集；4、所有这些子集的并集就构成集合Z。称为集合Z的一个划分3.9.2集合的划分定义3.9.2给定非空集合A，设有集合S={S1

12、,S2,S3...Sm}。如果满足SiA且Si≠Φ，i＝1,2,...,m；Si∩Sj＝Φ，i≠j，i,j＝1,2,...,m；则集合S称作集合A的一个划分(Partition)，而S1,S2,...Sm叫做这个划分的块(Block)或类(Class)。设A={1,2,3,4,5},给定如下集合：={{1，2，3}，{3,4，5}}；={{1}，{2，3}，{4，5}}；={，{1，2，3}，{4，5}}；={{1，2，3}，{5}}；={{1}，{2}，{3}，{4}，{5}}。，是A的划分，其它都不是。3.9.3等价类与商集定义3.9.3设R是非空集合A上的等价关

13、系，对任意x∈A，称集合[x]R＝{y

14、y∈A∧∈R}为x关于R的等价类(equivalenceclass)，或叫作由x生成的一个R等价类，其中x称为[x]R的生成元(或叫代表元)。由定义3.9.3可以看出：（1）等价类产生的前提是A上的关系R必须是等价关系；（2）A中所有与x有关系R的元素y构成了[x]R；（3）A中任意一个元素一定对应一个由它生成的等价类；（4）R具有自反性意味着对x∈A，[x]R≠Φ；（5）R具有对称性意味着对任意x，y∈A，若有y∈[x]R，则一定有x∈[y]R。例3.9.3设A={0,1,2,4,5,8,10}，R是A上的以4为模的同

15、余关系。求（1）R的所有等价类；（2）画出R的关系图。解:(1)[1]R＝{1,5,9}＝[5]R＝[9]R；[2]R={2}；[4]R＝{0,4,8}=[0]R＝[8]R。2159159定理3.9.1设R是非空集合A上的等价关系，则有下面的结论成立：1)对xA，[x]R≠Φ；2)对x,y∈A，a)如果y∈[x]R，则有[x]R=[y]R，b)如果y[x]R，则有[x]R∩[y]R＝Φ。3)＝A；定理3.9.1的证明2)对任意x,y∈A，若y∈[x]R，则∈R。a)对z∈[x]R，则有：∈R，又