《离散数学 第2版 教学课件 ppt 作者 王元元 离散第28讲 闭包及等价关系》由会员分享，可在线阅读，更多相关《离散数学 第2版 教学课件 ppt 作者 王元元 离散第28讲 闭包及等价关系（18页珍藏版）》请在金锄头文库上搜索。
1、,计算机专业基础课程,授课人：王元元 单位：计算机理论教研室,理工大学指挥自动化学院,PowerPoint Template_Sub,二元关系,等价关系,序关系,闭包与等价关系,离散数学第28讲,Page 168 to 174,-4-,第28讲 等价关系,关系特性闭包,对本不具备某种特性的关系做最“经济”的扩充，使其具有这种特性。 定义：R是集合A上的二元关系，若R满足下列条件，则称R为R的自反闭包（对称闭包、传递闭包）： （1）R自反（对称、传递） （2）RR （3）对任意A上关系S，若S满足（1）（2），则R S R的自反闭包：r(R) R的对称闭包：s(R) R的传递闭包：t(R),-5
2、-,第28讲 等价关系,举例,设A=1, 2, 3, 4，R是A上的关系 R=, , 求R的自反、对称、传递闭包,t(R) =, , , , , ,r(R) =, , , , , , ,s(R) =, , , , , ,-6-,第28讲 等价关系,关系特性闭包,定理：设R为集合A上的二元关系 r(R) = s(R) =,EAR,RR,a) (RR) = RR = RR = RR RR对称 b) R RR c) 若有S满足以上两个条件，则对任意R，由R，R S知S，又因为S对称，所以S。 由此，得R S，所以RR S 综上，s(R) = RR,-7-,第28讲 等价关系,关系特性闭包,定理：设R
3、为集合A上的二元关系 t(R) =,a) R b) 设 ， ，则存在正整数i，j，使得Ri，Rj，所以 Ri Rj = Ri+j，从而 。所以传递。 c) 若有S满足以上两个条件，则只需证明对任一正整数n，均有Rn S。设Rn，则存在u1，u2，un=yA，使得xRu1，u1Ru2，un-1Run。因为R S，所以xSu1,u1Su2,un-1Sun，又因为S传递，所以S。Rn S得证。从而 S。 综上，t(R) =,-8-,第28讲 等价关系,说明,若R为A上的二元关系，且|A| = n，则t(R) = 由闭包的最小性可知R自反（对称、传递）当且仅当R = r(R) （R = s(R)、R
4、= t(R)）,-9-,第28讲 等价关系,关系特性闭包,定理：设R为集合A上二元关系 若R自反，则s(R)、t(R)均自反 若R对称，则r(R)、t(R)均对称 若R传递，则r(R)传递, R对称 R = R r(R) = (EAR) = EAR = EAR= r(R) r(R)对称 又 对任意自然数n，(Rn) = (R) n = Rn Rn对称 t(R) = 对称,-10-,第28讲 等价关系,关系特性闭包,定理：若R为A上的二元关系，那么 rs(R) = sr(R) rt(R) = tr(R) st(R) ts(R),-11-,第28讲 等价关系,引言,设A是以理工大学所有学生为元素的
5、集合，R是A上的二元关系，且对任意a，bA，R a和b在同一学员队中,1、自己和自己总在同一班中，所以对R中任一元素x，都有 R,2、如果 R，表明x和y在一个学员队中，那么y和x也在一个学员队中，得到 R,3、如果 R，x和y在一个学员队中；且 R ，y和z也在一个学员队中，那么x和z也在一个学员队中，得到 R,自反性,对称性,传递性,根据关系R，可将集合A划分成多个子集： 1、在一个子集中的学生都在一个学员队中； 2、任一个学生都在且仅在一个子集中； 3、没有一个学生属于两个子集；,-12-,第28讲 等价关系,等价关系 (equivalent relation),定义：如果集合A上的关系
6、R满足自反性、对称性、传递性，则称R为等价关系,设R是整数集上的关系，并对任意整数a，b，aRb当且仅当a = b或者a = b 设是26个英文字母的集合，R是*上的二元关系，并且对任意a，b*，aRb当且仅当l(a) = l(b)，其中l(x)是串x的长度 整数集合上的“模k相等关系=k”（k为正整数），其中=k定义为x =k y 当且仅当k | (xy) 对任意集合A，A上的相等关系EA、全关系AA,-13-,第28讲 等价关系,等价类(equivalent class),定义： 设R为集合A上的等价关系，对每一aA，如下定义的aR（或简记为a）叫做a的等价类，a称为aR的代表元素 aR
7、= x | xAxRa,设R是整数集上的关系，并对任意整数a，b，aRb当且仅当a = b或者a = b。一个整数a对应的等价类为aR = a, a 对于模4相等关系，共有4个不同的等价类： 0 = , 12, 8, 4, 0, 4, 8, 12, 1 = , 11, 7, 3, 1, 5, 9, 13, 2 = , 10, 6, 2, 2, 6, 10, 14, 3 = , 9, 5, 1, 3, 7, 11, 15, ,-14-,第28讲 等价关系,等价类,对任何集合A， EA有|A|个不同的等价类，每个等价类都是单元素集； 对任何集合A，AA只有一个等价类A； 对每一元素aA，任何A上的
8、等价关系R，aR，因为R自反，恒有aa R； 同一等价类可以有不同的代表元素，即不同的元素可能有相同的等价类,-15-,第28讲 等价关系,等价类的性质,定理：设R是集合A上的等价关系，对任意a，bA，aRb当且仅当aR = bR,对于模4相等关系， 0=4=8= 1=5=9= 2=6=10= 3=7=11=,证明：假设aRb，证明a = b。 假设ca，即cRa，因为aRb，且R传递，所以cRb，即cb。所以a b； 假设cb，即cRb。因为aRb，且R对称，所以bRa。又因为R传递，所以cRa，即ca。所以b a。 综上，a = b。,证明：假设a = b ，证明aRb 。 aa，即ab，
9、所以aRb,-16-,第28讲 等价关系,等价类的性质,定理：设R是集合A上的等价关系，对任意a，bA，或者aR=bR，或者aRbR,证明：设aRbR，证明a = b。 因为ab，所以必存在某个元素c，满足ca，且cb， 所以有cRa，cRb。根据R的对称性，有aRc，cRb；又根据R的传递性，得aRb。 所以得到a = b,PQ P Q,-17-,第28讲 等价关系,等价类的性质,定理：设R是集合A上的等价关系，对任意a，bA，下面三个命题等价： （1）aRb （2）a = b （3）ab,对于模4相等关系，共有4个不同的等价类： 0 = , 12, 8, 4, 0, 4, 8, 12, 1 = , 11, 7, 3, 1, 5, 9, 13, 2 = , 10, 6, 2, 2, 6, 10, 14, 3 = , 9, 5, 1, 3, 7, 11, 15, ,-18-,第28讲 等价关系,本讲小结,主要内容 关系特性闭包的概念 关系特性闭包的求取、性质 等价关系的定义：自反、对称、传递 等价类的概念及性质 作业 P184 18(2)(4)、25、30、32,
