《第四章二元关系精选PPT.ppt》由会员分享，可在线阅读，更多相关《第四章二元关系精选PPT.ppt（162页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第四章二元关系第1页，此课件共162页哦第四章第四章 二元关系二元关系4.14.1关系的基本概念关系的基本概念4.24.2关系的性质关系的性质4.34.3关系的表示关系的表示4.44.4关系的运算关系的运算4.54.5特殊关系特殊关系第2页，此课件共162页哦4.1关系的基本概念关系的基本概念 定义：任一序偶的集合确定一个二元关系定义：任一序偶的集合确定一个二元关系R，R中任一序偶中任一序偶 可记作可记作 R或或xRy，称为，称为x与与y有关系有关系R。否则，记作。否则，记作 或或 例例 R1=|xy,x和和y是实数是实数一、关系的定义一、关系的定义第3页，此课件共162页哦一、关系的定义一、
2、关系的定义定义：令定义：令X和和Y是任意两个集合，直积是任意两个集合，直积XY的的子集子集R称作称作X到到Y的关系。的关系。XY有两个平凡子集有两个平凡子集若若，则称，则称R为为X到到Y空关系空关系若若R=XY，则称，则称R为为X到到Y的全域关系的全域关系当当X=Y时，关系时，关系R是直积是直积XX的子集，称的子集，称R为为X上的二元关系。上的二元关系。IX=|xX称为称为X上的恒等关系。上的恒等关系。第4页，此课件共162页哦一、关系的定义一、关系的定义例：设集合例：设集合A=a,b,B=2,5,8则则令令则则均是由均是由A到到B的关系。的关系。同理，同理，则则是由是由B到到A的关系。的关系
3、。同理，同理，则则是由是由B到到B的关系。的关系。第5页，此课件共162页哦一、关系的定义一、关系的定义例：设集合例：设集合A=2,3,5,9，试给出集合，试给出集合A上的上的小于或等于关系，大于或等于关系。小于或等于关系，大于或等于关系。解：令集合解：令集合A上的小于或等于关系为上的小于或等于关系为R1，大于或等于关系为大于或等于关系为R2，根据定义有：，根据定义有：第6页，此课件共162页哦一、关系的定义一、关系的定义定义：设定义：设 且且 为为n个任意集合，个任意集合，(a)称称R为为间的间的n元关系；元关系；(b)若若n=2，则称，则称R为为A1到到A2的二元关系；的二元关系；(c)若
4、若，则称，则称R为空关系；若为空关系；若，则，则称称R为全关系为全关系；(d)若若，则称，则称R为为A上的上的n元关系元关系。第7页，此课件共162页哦一、关系的定义一、关系的定义例：令例：令 则称则称R1是是N上的一元关系，上的一元关系，R2是是N上的二元上的二元关系，关系，R3是是N上的三元关系。上的三元关系。如无特殊指定，如无特殊指定，“关系关系”概指二元关系。概指二元关系。第8页，此课件共162页哦二、关系的相等二、关系的相等 定义：设定义：设R1为为X到到Y上的二上的二元关系，元关系，R2为为A到到B上的二上的二元关系，如果：元关系，如果：（1 1）X=A （2 2）Y=B（3 3）
5、把）把R1和和R2作为集合看，作为集合看，R1=R2。则称则称二二元关系元关系R1和和R2相等，记作相等，记作R1=R2第9页，此课件共162页哦二、关系的相等二、关系的相等例：设例：设R1为从为从Z到到I+的二元关系，的二元关系，R2和和R3都都是是I上的二元关系上的二元关系从集合的观点来看，从集合的观点来看，R1=R2=R3。但是就二元关系来说，但是就二元关系来说，R2=R3，不等于，不等于R1。第10页，此课件共162页哦三、关系的定义域和值域三、关系的定义域和值域关系关系R(从从A到到B的关系的关系)的的定义域定义域(简称为简称为域域)定义定义为：为：关系关系R的的值域值域定义定义为：
6、为：显然，有显然，有第11页，此课件共162页哦三、关系的定义域和值域三、关系的定义域和值域例：设例：设A=2,3,5,B=2,6,7,8,9，由，由A到到B的关系的关系R定义为：当且仅当定义为：当且仅当a整除整除b时，有时，有aRb。可得可得:D(R)=2,3R(R)=2,6,8,9AB第12页，此课件共162页哦第四章第四章 二元关系二元关系4.14.1关系的基本概念关系的基本概念4.24.2关系的性质关系的性质4.34.3关系的表示关系的表示4.44.4关系的运算关系的运算4.54.5特殊关系特殊关系第13页，此课件共162页哦4.2关系的性质关系的性质定义：定义：设设R为为A上的二元关
7、系上的二元关系(1)若对每个若对每个，皆有，皆有，则称，则称R为自为自反的。用式子来表述即是：反的。用式子来表述即是：R是自反的是自反的(2)若对每个若对每个，皆有，皆有，则称，则称R为为反自反的。用式子来表述即是：反自反的。用式子来表述即是：R是反自反的是反自反的 第14页，此课件共162页哦4.2关系的性质关系的性质(3)对任意的对任意的，若，若则则，就称，就称R为对称的。用式子来表述即是：为对称的。用式子来表述即是：R是对称的是对称的(4)对任意的对任意的，若，若且且，则则x=y，就称，就称R为反对称的。用式子来表述即是：为反对称的。用式子来表述即是：R是反对称的是反对称的 第15页，此
8、课件共162页哦4.2关系的性质关系的性质(5)对任意的对任意的，若，若且且则则，就称，就称R为可传递的。用式子来表述即是：为可传递的。用式子来表述即是：R是可传递的是可传递的第16页，此课件共162页哦4.2关系的性质关系的性质例例1：考虑自然数集合上的普通相等关系考虑自然数集合上的普通相等关系“=”，大于关系，大于关系“”和大于等于关系和大于等于关系“”具有的性质。具有的性质。解：解：(1)“=”关系是自反的、对称的、反对称的、可关系是自反的、对称的、反对称的、可传递的；传递的；(2)“”关系是反自反的、反对称的、可传递的；关系是反自反的、反对称的、可传递的；(3)“”关系是自反的、反对称
9、的、可传递的。关系是自反的、反对称的、可传递的。第17页，此课件共162页哦例例:A=1,2,3,A:A=1,2,3,A上的关系上的关系:R R1 1=R R2 2=R R3 3=R R4 4=判断以上关系各有哪些性质。判断以上关系各有哪些性质。解：解：(1)(1)既不是自反又不是反自反，是对既不是自反又不是反自反，是对称的，不是传递的。称的，不是传递的。(2)(2)反自反的，反对称的，传递的。反自反的，反对称的，传递的。第18页，此课件共162页哦(3)(3)既不是自反又不是反自反的，既是对称既不是自反又不是反自反的，既是对称又是反对称的，传递的。又是反对称的，传递的。(4)(4)是自反的，
10、既不是对称又不是反对称的，是自反的，既不是对称又不是反对称的，不是传递的。不是传递的。自反与反自反不交，存在既不是自反又不自反与反自反不交，存在既不是自反又不是反自反的关系。是反自反的关系。对称与反对称相交，存在既是对称又是反对称与反对称相交，存在既是对称又是反对称的关系，也存在既不是对称也不是反对称的关系，也存在既不是对称也不是反对称的关系。对称的关系。第19页，此课件共162页哦4.2关系的性质关系的性质例例2：空集上的二元关系的性质。空集上的二元关系的性质。对称的、反对称的、反自反的、可传递的对称的、反对称的、反自反的、可传递的第20页，此课件共162页哦集合的压缩和开拓集合的压缩和开拓
11、 定义：设定义：设R为集合为集合A上的二元关系且上的二元关系且 ，则称则称S上的二元关系上的二元关系 为为R在在S上的压上的压缩，记为缩，记为 ，并称，并称R为为 在在A上的开拓。上的开拓。第21页，此课件共162页哦集合的压缩和开拓集合的压缩和开拓定理：设定理：设R为为A的二元关系且的二元关系且，那么：，那么：(1)若若R是自反的，则是自反的，则也是自反的；也是自反的；(2)若若R是反自反的，则是反自反的，则也是反自反的；也是反自反的；(3)若若R是对称的，则是对称的，则也是对称的；也是对称的；(4)若若R是反对称的，则是反对称的，则也是反对称的；也是反对称的；(5)若若R是可传递的，则是可
12、传递的，则也是可传递的；也是可传递的；第22页，此课件共162页哦第四章第四章 二元关系二元关系4.14.1关系的基本概念关系的基本概念4.24.2关系的性质关系的性质4.34.3关系的表示关系的表示4.44.4关系的运算关系的运算4.54.5特殊关系特殊关系第23页，此课件共162页哦4.3关系的表示关系的表示 定义：设定义：设A和和B为任意的非空有限集，为任意的非空有限集，R为任意一个从为任意一个从A到到B的二元关系。以的二元关系。以 中的每个元素为结点对每中的每个元素为结点对每个个 皆画一条从皆画一条从x到到y的有向边，的有向边，这样得到的一个图称为关系这样得到的一个图称为关系R的关系图
13、。的关系图。一、关系图一、关系图例：例：A=1,2,4;B=3,5,6;关系关系R=,A124B356第24页，此课件共162页哦一、关系图一、关系图例：设例：设A=2,3,4,5,6,B=6,7,8,12，从，从A到到B的二元关系的二元关系R为为画出其关系图。画出其关系图。解：先求出解：先求出R第25页，此课件共162页哦一、关系图一、关系图 对称关系对称关系 反对称关系反对称关系第26页，此课件共162页哦一、关系图一、关系图如果关系图中每个结点上都有环，则如果关系图中每个结点上都有环，则R是是自反的；自反的；如果关系图中每个结点上都没有环，则如果关系图中每个结点上都没有环，则R是反自反的
14、；是反自反的；如果关系图中两顶点间有边，必是一对方如果关系图中两顶点间有边，必是一对方向相反的边向相反的边，则，则R是对称的；是对称的；如果关系图中两顶点间有边，必是一条有如果关系图中两顶点间有边，必是一条有向边向边,则则R是反对称的；是反对称的；如果关系图中顶点如果关系图中顶点xi到到xj有边，有边，xj到到xk有边，有边，则则xi到到xk必有边，则必有边，则R是可传递的。是可传递的。第27页，此课件共162页哦例例:判断下图中的关系分别具有哪些性质。判断下图中的关系分别具有哪些性质。第28页，此课件共162页哦二、关系矩阵二、关系矩阵定义：定义：给定两个有限集合给定两个有限集合X=x1,x
15、2,xm和和Y=y1,y2,yn，R是从是从X到到Y的二元关系，如果有：的二元关系，如果有：则称则称rijmn是是R的关系矩阵，记作的关系矩阵，记作MR。第29页，此课件共162页哦二、关系矩阵二、关系矩阵例：设例：设A=1,2,3,B=a,b,c,R是是A到到B的二元的二元关系，并且关系，并且，试画出，试画出R的的关系图，给出关系矩阵。关系图，给出关系矩阵。第30页，此课件共162页哦二、关系矩阵二、关系矩阵。例：设例：设A=1,2,3,4,R为定义在为定义在A上的二元关系，上的二元关系，R=,，写出关系矩阵。，写出关系矩阵。第31页，此课件共162页哦二、关系矩阵二、关系矩阵如果关系矩阵主
16、对角线上的记入值全为如果关系矩阵主对角线上的记入值全为1，则，则R是自反的；是自反的；如果主对角线上的记入值全为如果主对角线上的记入值全为0，则，则R是反是反自反的；自反的；如果矩阵关于主对角线是对称的，则如果矩阵关于主对角线是对称的，则R是是对称的；对称的；如果矩阵关于主对角线是反对称的，如果矩阵关于主对角线是反对称的，(亦即亦即rij=1时则一定有时则一定有rji=0),则则R是反对称的；是反对称的；第32页，此课件共162页哦二、关系矩阵二、关系矩阵如果对于任意的如果对于任意的i,j,k,rij=1并且并且rjk=1时一定时一定有有rik=1 ，则，则R是可传递的；是可传递的；如果存在如
17、果存在i,j,k,rij=1并且并且rjk=1时，有时，有rik 不等不等于于1 ，则，则R是不可传递的；是不可传递的；第33页，此课件共162页哦第四章第四章 二元关系二元关系4.14.1关系的基本概念关系的基本概念4.24.2关系的性质关系的性质4.34.3关系的表示关系的表示4.44.4关系的运算关系的运算4.54.5特殊关系特殊关系第34页，此课件共162页哦4.4关系的运算关系的运算 注意：由于关系也是特殊的集合，因此集合注意：由于关系也是特殊的集合，因此集合的运算也适用于关系中。的运算也适用于关系中。设设R1和和R2是从是从A到到B的二元关系，那么的二元关系，那么 也是从也是从A到
18、到B的二元关系，的二元关系，它们分别被称为二元关系它们分别被称为二元关系R1和和R2的交、并、的交、并、差分和对称差分。差分和对称差分。第35页，此课件共162页哦4.4关系的运算关系的运算例：设集合例：设集合A=a,b,c，B=d,e，定义，定义A到到B的二元的二元关系关系R1=,R2=,则则第36页，此课件共162页哦4.4关系的运算关系的运算4.4.14.4.1关系的合成关系的合成4.4.24.4.2关系的求逆运算关系的求逆运算4.4.34.4.3关系的闭包运算关系的闭包运算第37页，此课件共162页哦4.4.1关系的合成关系的合成 定义定义：设：设R是从是从X到到Y的关系，的关系，S是
19、从是从Y到到Z的的关系，于是可用关系，于是可用R S表示从表示从X到到Z的关系，通的关系，通常称它是常称它是R和和S的合成关系，用式子表示即的合成关系，用式子表示即是：是：第38页，此课件共162页哦例：给定关系例：给定关系R和和S，并且，并且则则第39页，此课件共162页哦关系的合成关系的合成注意：设是注意：设是R从集合从集合X到集合到集合Y的关系，的关系，S是是从集合从集合Y到集合到集合Z的关系，于是有：的关系，于是有：如果如果R关系的值域与关系的值域与S关系的定义域的交集是关系的定义域的交集是个空集，则合成关系个空集，则合成关系R S也是个空关系；也是个空关系；对于合成关系对于合成关系R
20、 S来说，它的定义域是集合来说，它的定义域是集合X的子集，而它的值域则是的子集，而它的值域则是Z的子集，事实上，的子集，事实上，它的定义域是关系它的定义域是关系R的定义域的子集，它的值的定义域的子集，它的值域是关系域是关系S的值域的子集。的值域的子集。第40页，此课件共162页哦试求试求R和和S的合成关系，并给出合成关系的关的合成关系，并给出合成关系的关系矩阵。系矩阵。解解:例：例：给定集合给定集合X=1,2,3,4，Y=2,3,4和和Z=1,2,3。设。设R是从是从X到到Y的关系，并且的关系，并且S是从是从Y到到Z的关系，并且的关系，并且R和和S给定成：给定成：第41页，此课件共162页哦关
21、系的合成关系的合成第42页，此课件共162页哦合成关系的矩阵表达合成关系的矩阵表达设集合设集合X=x1,x2,xm,Y=y1,y2,yn,Z=z1,z2,zp,R是从是从X到到Y的关系，的关系，S是从是从Y到到Z的关系，的关系，MR和和MS第第i行第行第j列的元素分别是列的元素分别是aij和和bij，它们是，它们是0或者或者1。则合成关系。则合成关系关系矩阵上的关系矩阵上的元素为元素为定义布尔运算：定义布尔运算：0+0=0，1+0=0+1=1+1=111=1，01=10=00=0对两个关系矩阵求其合成时，其运算法则与一般矩阵的乘法对两个关系矩阵求其合成时，其运算法则与一般矩阵的乘法是相同的，但
22、其中的加法运算和乘法运算应改为布尔加和布是相同的，但其中的加法运算和乘法运算应改为布尔加和布尔乘。尔乘。第43页，此课件共162页哦合成关系的矩阵表达和图解合成关系的矩阵表达和图解例：求合成关系例：求合成关系的关系矩阵的关系矩阵第44页，此课件共162页哦关系的合成关系的合成定理：给定集合定理：给定集合X,Y,Z和和W，设，设R1是从是从 X到到Y的关系，的关系，R2和和R3是是Y到到Z的关系，的关系，R4是从是从Z到到W的关系，于是有：的关系，于是有：第45页，此课件共162页哦关系的合成关系的合成证明：任取元素证明：任取元素当且仅当存在当且仅当存在某一个某一个能使能使和和第46页，此课件共
23、162页哦证明：任取元素证明：任取元素当且仅当当且仅当存在某一个存在某一个能使能使和和关系的合成关系的合成第47页，此课件共162页哦关系的合成关系的合成 合成运算是对关系的二元运算，使用这种运合成运算是对关系的二元运算，使用这种运算，能够由两个关系生成一个新的关系，算，能够由两个关系生成一个新的关系，对于这个新的关系又可进行合成运算，从对于这个新的关系又可进行合成运算，从而生成其它关系。而生成其它关系。定理：设定理：设R1是从是从X到到Y的关系，的关系，R2是从是从Y到到Z的关的关系，系，R3是从是从Z到到W的关系，于是有的关系，于是有第48页，此课件共162页哦关系的合成关系的合成第49页
24、，此课件共162页哦关系的幂关系的幂定义：给定集合定义：给定集合X，R是是X中的二元关系。设中的二元关系。设，于是，于是R的的n次幂次幂Rn可定义成可定义成(a)R0是集合是集合X中的恒等关系中的恒等关系IX，亦即，亦即(b)第50页，此课件共162页哦关系的幂关系的幂定理：给定集合定理：给定集合X，R是是X中的二元关系。设中的二元关系。设，于是可有，于是可有例：给定集合例：给定集合X=a,b,c，R1,R2,R3,R4是是X中的关系，并给定中的关系，并给定给出这些关系的各次幂给出这些关系的各次幂第51页，此课件共162页哦关系的幂关系的幂解：解：第52页，此课件共162页哦关系的幂关系的幂定
25、理：设定理：设X是含有是含有n个元素的有限集合，个元素的有限集合，R是是X中的二元关系。于是存在这样的中的二元关系。于是存在这样的s和和t，能使，能使，证明：集合证明：集合X中的每一个二元关系都是中的每一个二元关系都是的子集，的子集，X有有n个元素，个元素，有有n2个元素，个元素，有有个元个元素，每一个元素都是素，每一个元素都是的一个子集，也是一的一个子集，也是一种二元关系，因而，在种二元关系，因而，在X中有中有个不同的二元关系。个不同的二元关系。所以，不同的二元关系所以，不同的二元关系R的幂不会多于个的幂不会多于个。但。但是序列是序列中有中有项，因项，因此这些的方幂中至少有两个是相等的。证毕
26、。此这些的方幂中至少有两个是相等的。证毕。第53页，此课件共162页哦4.4关系的运算关系的运算4.4.14.4.1关系的合成关系的合成4.4.24.4.2关系的求逆运算关系的求逆运算4.4.34.4.3关系的闭包运算关系的闭包运算第54页，此课件共162页哦4.4.2关系的求逆运算关系的求逆运算定义：设定义：设R是从是从X到到Y的关系，将的关系，将R中每一序中每一序偶元素次序互换得到的集合称为偶元素次序互换得到的集合称为R的逆关系，的逆关系，记作记作Rc，即，即Rc=|R例：设集合例：设集合X=1,2,3,4,Y=a,b,c,R是集合是集合X到到Y二元关系，二元关系，R=则则Rc=逆关系的关
27、系矩阵：原关系矩阵转置逆关系的关系矩阵：原关系矩阵转置逆关系的关系图：原关系图中颠倒弧线上箭逆关系的关系图：原关系图中颠倒弧线上箭头的方向。头的方向。第55页，此课件共162页哦关系的求逆运算关系的求逆运算定理：给定集合定理：给定集合X和和Y，R、R1、R2是从是从X到到Y的关系，于是有：的关系，于是有：第56页，此课件共162页哦(a)(Rc)c=R证明：设证明：设是是R的任意元素。的任意元素。于是于是所以有所以有(Rc)c=R。关系的求逆运算关系的求逆运算第57页，此课件共162页哦(b)(R1R2)c=R1cR2c证明：证明：关系的求逆运算关系的求逆运算得证得证第58页，此课件共162页
28、哦关系的求逆运算关系的求逆运算证明：证明：得证。得证。第59页，此课件共162页哦证明：因为证明：因为，于是有，于是有关系的求逆运算关系的求逆运算得证。得证。第60页，此课件共162页哦合成关系的求逆运算合成关系的求逆运算定理：设定理：设R是从集合是从集合X到到Y的关系。的关系。S是从集合是从集合Y到到Z的关系。于是有的关系。于是有(RS)c=ScRc证明：对于任何证明：对于任何(RS)c利用关系矩阵也可以理解，利用关系矩阵也可以理解，的转置和的转置和是一样的。是一样的。第61页，此课件共162页哦合成关系的求逆运算合成关系的求逆运算例：给定关系矩阵例：给定关系矩阵MR和和MS。则：则：第62
29、页，此课件共162页哦定理：设定理：设R是集合是集合X中的关系，中的关系，a)R自反的，当且仅当自反的，当且仅当IX Rb)R反自反的，当且仅当反自反的，当且仅当IXR=c)R是对称的，当且仅当是对称的，当且仅当 R=Rcd)R是反对称的，当且仅当是反对称的，当且仅当 RRc IX e)R是可传递的，当且仅当是可传递的，当且仅当RR R利用关系的运算判定关系的性质利用关系的运算判定关系的性质第63页，此课件共162页哦即即R Rc；证明证明:c)(充分性充分性)若若R=Rc则则即即R是对称的。是对称的。(必要性必要性)设设R是对称的，那么对任何是对称的，那么对任何对任何对任何即即RcR必要性证
30、明完毕。必要性证明完毕。第64页，此课件共162页哦关系运算对性质的影响关系运算对性质的影响自反自反性性反自反自反反对称对称性性反对反对称称可传递可传递RC R1 R2 R1R2 R1-R2 R1 R2 第65页，此课件共162页哦4.4关系的运算关系的运算4.4.14.4.1关系的合成关系的合成4.4.24.4.2关系的求逆运算关系的求逆运算4.4.34.4.3关系的闭包运算关系的闭包运算第66页，此课件共162页哦4.4.3关系的闭包运算关系的闭包运算闭包的定义：给定集合闭包的定义：给定集合X，R是是X中的二元关中的二元关系。如果有另一个关系系。如果有另一个关系满足满足（1）是自反的是自反
31、的(对称的、可传递的对称的、可传递的)；（2）（3）对于任何自反的）对于任何自反的(对称的、可传递的对称的、可传递的)关系关系，如果，如果，则，则则称关系则称关系为为R的的自反的自反的(对称的，可传对称的，可传递的递的)闭包。闭包。并用并用r(R)表示的表示的R自反闭包，自反闭包，用用s(R)表示表示R的对称闭包，用的对称闭包，用t(R)表示表示R的的可传递闭包。可传递闭包。第67页，此课件共162页哦关系的闭包运算关系的闭包运算定理：给定集合定理：给定集合X，R是是X中的关系。于是可中的关系。于是可有有(a)当且仅当当且仅当，R才是自反的。才是自反的。(b)当且仅当当且仅当，R才是对称的。才
32、是对称的。(c)当且仅当当且仅当，R才是传递的。才是传递的。第68页，此课件共162页哦关系的闭包运算关系的闭包运算定理：定理：设设X是任意集合，是任意集合，R是是X中的二元关系，中的二元关系，IX是是X中的恒等关系。于是可有中的恒等关系。于是可有在整数集合中，小于关系在整数集合中，小于关系“”的自反闭包是的自反闭包是“”；恒等关系；恒等关系IX的自反闭包是的自反闭包是IX。不等。不等关系关系“”的自反闭包是全域关系；空关系的自反闭包是全域关系；空关系的自反闭包是恒等关系。的自反闭包是恒等关系。第69页，此课件共162页哦关系的闭包运算关系的闭包运算定理：给定集合定理：给定集合X，R是是X中的
33、二元关系。于是中的二元关系。于是可有可有 在整数集合中，小于关系在整数集合中，小于关系“”的对称闭包是不的对称闭包是不等关系等关系“”；小于或等于关系；小于或等于关系“”的对的对称闭包是全域关系；恒等关系称闭包是全域关系；恒等关系IX的对称闭包的对称闭包是是IX；不等关系；不等关系“”的对称闭包是不等关系的对称闭包是不等关系“”。第70页，此课件共162页哦关系的闭包运算关系的闭包运算定理：给定集合定理：给定集合X，R是是X中的二元关系。于是可中的二元关系。于是可有有第71页，此课件共162页哦例：设例：设A=a,b,c,R是是A上的二元关系，上的二元关系，R=求求r(R),s(R),t(R)
34、。解：解：r(R)=RIX=s(R)=RRC=t(R)=RR2 R3=RR2 R3=第72页，此课件共162页哦关系的闭包运算关系的闭包运算当当A是有限集时，是有限集时，A上只有有限个不同的关系，因上只有有限个不同的关系，因此，若此，若 ，则，则第73页，此课件共162页哦关系图求闭包关系图求闭包r(R)：在：在R的关系图中，把没有环的结点上加的关系图中，把没有环的结点上加上环，其它不变。上环，其它不变。S(R)：在：在R的关系图中，把单向边改为双向边，的关系图中，把单向边改为双向边，其它不变。其它不变。t(R)：在：在R的关系图中，对每个结点的关系图中，对每个结点x，分别，分别找出可以到达的
35、终点找出可以到达的终点y，若，若x到到y没有有向边，没有有向边，则添加一条有向边，直到添加完毕。则添加一条有向边，直到添加完毕。第74页，此课件共162页哦关系矩阵求闭包关系矩阵求闭包r(R)：s(R)：t(R)：第75页，此课件共162页哦WarshallWarshall算法算法（1 1）A A：=M=M；（2 2）i i：=1=1；（3 3）对所有）对所有j j，如果，如果Aj,i=1Aj,i=1，则对，则对k=1,2,n k=1,2,n Aj,k=Aj,k+Ai,k;Aj,k=Aj,k+Ai,k;（4 4）i i加加1 1；（5 5）如果）如果inin，则转到步骤（，则转到步骤（3 3）
36、，否则停止。），否则停止。第76页，此课件共162页哦例：设例：设A=a,b,c,R是是A上的二元关系，上的二元关系，R=求求t(R)。解：解：t(R)=RR2 R3=RR2 R3=第77页，此课件共162页哦关系的闭包运算关系的闭包运算定理：设定理：设X是集合，是集合，R是是X中的二元关系，于是中的二元关系，于是有有（1）如果）如果R是自反的，那么是自反的，那么s(R),t(R)也是自反的；也是自反的；（2）如果）如果R是对称的，那么是对称的，那么r(R),t(R)也是对称也是对称的；的；（3）如果）如果R是可传递的，那么是可传递的，那么r(R)也是可传递的也是可传递的。第78页，此课件共1
37、62页哦关系的闭包运算关系的闭包运算证明（证明（1）：若）：若R是自反的，则对于所有的是自反的，则对于所有的都有都有即即s(R),t(R)是自反的是自反的第79页，此课件共162页哦关系的闭包运算关系的闭包运算证明证明(2):若若R是对称的，是对称的，则对于任何则对于任何R都有都有R，则则RIX及及RIX，即即r(R)是对称的。是对称的。又因为又因为可知可知t(R)也是对称的，得证。也是对称的，得证。第80页，此课件共162页哦关系的闭包运算关系的闭包运算证明（证明（3）：若）：若R是可传递的，是可传递的，即当即当时有时有，假定存在，假定存在讨论四种情况讨论四种情况第81页，此课件共162页哦
38、关系的闭包运算关系的闭包运算定理：设定理：设X是集合，是集合，R是集合中的二元关系，于是有是集合中的二元关系，于是有证明：证明：第82页，此课件共162页哦关系的闭包运算关系的闭包运算证明（证明（b）：因为）：因为，而，而对于所有的对于所有的有有，以及，以及。根据这些关系式，可有根据这些关系式，可有于是于是第83页，此课件共162页哦关系的闭包运算关系的闭包运算证明（证明（c）：如果）：如果，则，则，根据对称闭包的定义，有根据对称闭包的定义，有。首先构成上式。首先构成上式两侧的可传递闭包，再依次构成两侧的对称闭包两侧的可传递闭包，再依次构成两侧的对称闭包,可以求得可以求得以及以及。而。而ts(
39、R)是对称的，是对称的，所以所以，从而有，从而有。第84页，此课件共162页哦关系的闭包运算关系的闭包运算注意：注意：（1）通常用）通常用R+表示表示R的可传递闭包的可传递闭包t(R)，并，并读作读作“R加加”。（2）通常用）通常用R*表示表示R的自反可传递闭包的自反可传递闭包tr(R)，并读作，并读作“R星星”。第85页，此课件共162页哦第四章第四章 二元关系二元关系4.14.1关系的基本概念关系的基本概念4.24.2关系的性质关系的性质4.34.3关系的表示关系的表示4.44.4关系的运算关系的运算4.54.5特殊关系特殊关系第86页，此课件共162页哦4.5特殊关系特殊关系4.5.14
40、.5.1集合的划分和覆盖集合的划分和覆盖4.5.24.5.2等价关系等价关系4.5.34.5.3相容关系相容关系4.5.44.5.4次序关系次序关系4.5.54.5.5偏序集合与哈斯图偏序集合与哈斯图第87页，此课件共162页哦4.5.1集合的划分和覆盖集合的划分和覆盖定义：给定非空集合定义：给定非空集合S，设非空集合，设非空集合A=A1,A2,An，如果有，如果有则称集合则称集合A是集合是集合S的覆盖。的覆盖。注意：集合的覆盖不唯一。注意：集合的覆盖不唯一。例如：例如：S=a,b,c，A=a,b,b,c，B=a,b,c，A和和B都是集合都是集合S的覆盖。的覆盖。第88页，此课件共162页哦集
41、合的划分和覆盖集合的划分和覆盖定义：给定非空集合定义：给定非空集合S，设非空集合，设非空集合A=A1,A2,An，如果有，如果有则称集合则称集合A是集合是集合S的一个划分。的一个划分。例如：例如：S=a,b,c，A=a,b,c，B=a,b,c，A和和B都是集合都是集合S的划分。的划分。第89页，此课件共162页哦集合的划分和覆盖集合的划分和覆盖划分中的元素划分中的元素Ai称为划分的称为划分的类类。划分的类的数目叫划分的划分的类的数目叫划分的秩秩。划分是覆盖的特定情况，即中元素互划分是覆盖的特定情况，即中元素互不相交的特定情况。不相交的特定情况。集合的划分不唯一。集合的划分不唯一。第90页，此课
42、件共162页哦集合的划分和覆盖集合的划分和覆盖例：设例：设S=1,2,3，考虑下列集合，考虑下列集合S的覆盖的覆盖S的覆盖的覆盖S的覆盖、划分，秩为的覆盖、划分，秩为2S的覆盖、划分，秩为的覆盖、划分，秩为1，最小划分，最小划分S的覆盖、划分，秩为的覆盖、划分，秩为3，最大划分，最大划分第91页，此课件共162页哦定义定义:若若AA1 1,A,A2 2,A,Ar r 与与BB1 1,B,B2 2,B,Bs s 是同一集合是同一集合A A的两种划分的两种划分,则其中所有则其中所有A Ai iBBj j 组成的集合，组成的集合，称为是原来两种划分的交叉划分。称为是原来两种划分的交叉划分。定理：定理
43、：AA1 1,A,A2 2,A,Ar r 与与BB1 1,B,B2 2,B,Bs s 是同一集合是同一集合A A的两种划分，则其交叉划分亦是原集合的的两种划分，则其交叉划分亦是原集合的一种划分。一种划分。第92页，此课件共162页哦定义定义:若若AA1 1,A,A2 2,A,Ar r 与与BB1 1,B,B2 2,B,Bs s 是同一集合是同一集合A A的两种划分的两种划分,若对每一个若对每一个A Ai i都有都有B Bj j使使A Ai i B Bj j，则，则AA1 1,A,A2 2,A,Ar r 称为是称为是BB1 1,B,B2 2,B,Bs s 的加细。的加细。定理：定理：任何两种划分
44、的交叉划分，都是原任何两种划分的交叉划分，都是原来各划分的一种加细。来各划分的一种加细。第93页，此课件共162页哦4.5特殊关系特殊关系4.5.14.5.1集合的划分和覆盖集合的划分和覆盖4.5.24.5.2等价关系等价关系4.5.34.5.3相容关系相容关系4.5.44.5.4次序关系次序关系4.5.54.5.5偏序集合与哈斯图偏序集合与哈斯图第94页，此课件共162页哦4.5.2等价关系等价关系定义：设定义：设X是任意集合是任意集合,R是集合中的二元关系。是集合中的二元关系。如果如果R是自反的、对称的和可传递的，是自反的、对称的和可传递的，则称则称R是等是等价关系。即满足以下几点：价关系
45、。即满足以下几点：如果如果R是集合是集合X中的等价关系，则中的等价关系，则R的域是集合的域是集合X自身，所以称自身，所以称R是定义于集合是定义于集合X中的关系。中的关系。第95页，此课件共162页哦4.5.2等价关系等价关系例如例如 数的相等关系是任何数集上的等价关系。数的相等关系是任何数集上的等价关系。又又例例如如一一群群人人的的集集合合中中姓姓氏氏相相同同的的关关系系也也是是等等价价关系。关系。但朋友关系不是等价关系，因为它不可传递。但朋友关系不是等价关系，因为它不可传递。第96页，此课件共162页哦等价关系等价关系例：给定集合例：给定集合X=1,2,7,7，R是是X中的二元关中的二元关系
46、，并且给定成系，并且给定成试证明试证明R是等价关系。是等价关系。解：解：R的关系矩阵如下：的关系矩阵如下：第97页，此课件共162页哦等价关系等价关系R的关系图如下：的关系图如下：第98页，此课件共162页哦等价关系等价关系注意：注意：上例是模数系统中模等价关系的特定情况。上例是模数系统中模等价关系的特定情况。设设R+是正整数集合，是正整数集合，m是个正整数。对于是个正整数。对于来说，可将来说，可将R定义成定义成。这里，这里，“x-y可被可被m整除整除”等价于命题等价于命题“当用当用m去去除除x和和y时，它们都有同样的余数时，它们都有同样的余数”。故关系。故关系R也也称为称为模模m同余关系同余
47、关系。第99页，此课件共162页哦等价关系等价关系定理：任何集合定理：任何集合中的模中的模m相等关系，是一个相等关系，是一个等价关系。等价关系。证明：要证明证明：要证明R是个等价关系，就必须证明是个等价关系，就必须证明R是自是自反的、对称的和可传递的。反的、对称的和可传递的。(1)对于任何对于任何来说，因为来说，因为x-x=0m，所以有，所以有。因此，模。因此，模m相等关系是自反的。相等关系是自反的。第100页，此课件共162页哦等价关系等价关系(2)对于任何对于任何来说，如果来说，如果，则存在某一个则存在某一个，能使，能使x-y=nm。于是可。于是可有有y-x=(-n)m，因此有，因此有，即
48、模，即模m相等关相等关系是对称的。系是对称的。(3)设设，和和。于是存。于是存在在，能使，能使和和。而。而，从而可有，从而可有，即模，即模m相等关系是可相等关系是可传递的。传递的。第101页，此课件共162页哦等价类等价类定义：设定义：设是集合是集合A上的等价关系，则上的等价关系，则A中等价中等价于元素于元素的所有元素组成的集合称为的所有元素组成的集合称为生成的等生成的等价类，用价类，用表示，即表示，即定义：设定义：设R是集合是集合A上的等价关系，若元素上的等价关系，若元素aRb，则，则称称a与与b等价，或称等价，或称b与与a等价。等价。第102页，此课件共162页哦等价类等价类例：设例：设X
49、=a,b,c,d，R是是X中的等价关系，并把中的等价关系，并把R给定成给定成则：则：第103页，此课件共162页哦等价类的性质等价类的性质1.1.对任意对任意,因为对于任意的因为对于任意的 X X,有有 ，所以，所以 设设X是一集合，是一集合，R是是X上的等价关系上的等价关系2 2.如果如果，则，则3.对于所有的对于所有的，或者，或者，或者，或者证明：分两种情况讨论证明：分两种情况讨论(1)xRy(2)xRy第104页，此课件共162页哦等价类的性质等价类的性质(1)xRy故故 。类似地可以证明类似地可以证明由上得由上得若若 ，则，则xRxRz z ，由由R R 的对称性有的对称性有zRxzR
50、x，又由又由R R的传递性有的传递性有zRyzRy ，因此，因此 (2)xRy假设假设 ,因此有因此有 且且 ，故故 于是由于是由xRzxRz,zRb，得，得xRyxRy，与，与xRy相矛盾相矛盾第105页，此课件共162页哦等价类的性质等价类的性质4.证明：假定证明：假定，对于某个，对于某个，有，有。由于。由于，会有，会有，因而，因而。设设，于是，于是因而因而证毕。证毕。第106页，此课件共162页哦等价类的性质等价类的性质例例设设A=a,b,c,d，A上的关系上的关系R是是A上的等价关系上的等价关系 同一个等价类中元素均相互等价。不同等价类中同一个等价类中元素均相互等价。不同等价类中的元素