第四章二元关系优秀PPT.ppt

《第四章二元关系优秀PPT.ppt》由会员分享，可在线阅读，更多相关《第四章二元关系优秀PPT.ppt（162页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第四章二元关系第一页，本课件共有162页第四章第四章 二元关系二元关系4.14.1关系的基本概念关系的基本概念4.24.2关系的性质关系的性质4.34.3关系的表示关系的表示4.44.4关系的运算关系的运算4.54.5特殊关系特殊关系第二页，本课件共有162页4.1关系的基本概念关系的基本概念 定义：任一序偶的集合确定一个二元关系定义：任一序偶的集合确定一个二元关系R，R中任一序偶中任一序偶 可记作可记作 R或或xRy，称为，称为x与与y有关系有关系R。否则，记作。否则，记作 或或 例例 R1=|xy,x和和y是实数是实数一、关系的定义一、关系的定义第三页，本课件共有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上的恒等关系。上的恒等关系。第四页，本课件共有162页一、关系的定义一、关系的定义例：设集合例：设集合A=a,b,B=2,5,8则则令令则则均是由均是由A到到B的关系。的关系。同理，同理，则则是由是由B到到A的关系。的关系

3、。同理，同理，则则是由是由B到到B的关系。的关系。第五页，本课件共有162页一、关系的定义一、关系的定义例：设集合例：设集合A=2,3,5,9，试给出集合，试给出集合A上的上的小于或等于关系，大于或等于关系。小于或等于关系，大于或等于关系。解：令集合解：令集合A上的小于或等于关系为上的小于或等于关系为R1，大于或等于关系为大于或等于关系为R2，根据定义有：，根据定义有：第六页，本课件共有162页一、关系的定义一、关系的定义定义：设定义：设 且且 为为n个任意集合，个任意集合，(a)称称R为为间的间的n元关系；元关系；(b)若若n=2，则称，则称R为为A1到到A2的二元关系；的二元关系；(c)若

4、若，则称，则称R为空关系；若为空关系；若，则，则称称R为全关系为全关系；(d)若若，则称，则称R为为A上的上的n元关系元关系。第七页，本课件共有162页一、关系的定义一、关系的定义例：令例：令 则称则称R1是是N上的一元关系，上的一元关系，R2是是N上的二元上的二元关系，关系，R3是是N上的三元关系。上的三元关系。如无特殊指定，如无特殊指定，“关系关系”概指二元关系。概指二元关系。第八页，本课件共有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第九页，本课件共有162页二、关系的相等二、关系的相等例：设例：设R1为从为从Z到到I+的二元关系，的二元关系，R2和和R3都都是是I上的二元关系上的二元关系从集合的观点来看，从集合的观点来看，R1=R2=R3。但是就二元关系来说，但是就二元关系来说，R2=R3，不等于，不等于R1。第十页，本课件共有162页三、关系的定义域和值域三、关系的定义域和值域关系关系R(从从A到到B的关系的关系)的的定义域定义域(简称为简称为域域)定义定义为：为：关系关系R的的值域值域定义定义为：为

6、：显然，有显然，有第十一页，本课件共有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第十二页，本课件共有162页第四章第四章 二元关系二元关系4.14.1关系的基本概念关系的基本概念4.24.2关系的性质关系的性质4.34.3关系的表示关系的表示4.44.4关系的运算关系的运算4.54.5特殊关系特殊关系第十三页，本课件共有162页4.2关系的性质关系的性质定义：定义：设设R为为A上的二元关系

7、上的二元关系(1)若对每个若对每个，皆有，皆有，则称，则称R为为自反的。用式子来表述即是：自反的。用式子来表述即是：R是自反的是自反的(2)若对每个若对每个，皆有，皆有，则称，则称R为反自反的。用式子来表述即是：为反自反的。用式子来表述即是：R是反自反的是反自反的 第十四页，本课件共有162页4.2关系的性质关系的性质(3)对任意的对任意的，若，若则则，就，就称称R为对称的。用式子来表述即是：为对称的。用式子来表述即是：R是对称的是对称的(4)对任意的对任意的，若，若且且，则则x=y，就称，就称R为反对称的。用式子来表述即是：为反对称的。用式子来表述即是：R是反对称的是反对称的 第十五页，本课

8、件共有162页4.2关系的性质关系的性质(5)对任意的对任意的，若，若且且则则，就称，就称R为可传递的。用式子来表述即是：为可传递的。用式子来表述即是：R是可传递的是可传递的第十六页，本课件共有162页4.2关系的性质关系的性质例例1：考虑自然数集合上的普通相等关系考虑自然数集合上的普通相等关系“=”，大于关系，大于关系“”和大于等于关系和大于等于关系“”具有的性质。具有的性质。解：解：(1)“=”关系是自反的、对称的、反对称的、关系是自反的、对称的、反对称的、可传递的；可传递的；(2)“”关系是反自反的、反对称的、可传递的；关系是反自反的、反对称的、可传递的；(3)“”关系是自反的、反对称的

9、、可传递的。关系是自反的、反对称的、可传递的。第十七页，本课件共有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)反自反的，反对称的，传递的。反自反的，反对称的，传递的。第十八页，本课件共有162页(3)(3)既不是自反又不是反自反的，既是对称既不是自反又不是反自反的，既是对称又是反对称的，传递的。又是反对称的，传递的。(4)(4)是自反的，既

10、不是对称又不是反对称的，是自反的，既不是对称又不是反对称的，不是传递的。不是传递的。自反与反自反不交，存在既不是自反又不自反与反自反不交，存在既不是自反又不是反自反的关系。是反自反的关系。对称与反对称相交，存在既是对称又是反对称与反对称相交，存在既是对称又是反对称的关系，也存在既不是对称也不是反对称的关系，也存在既不是对称也不是反对称的关系。对称的关系。第十九页，本课件共有162页4.2关系的性质关系的性质例例2：空集上的二元关系的性质。空集上的二元关系的性质。对称的、反对称的、反自反的、可传递对称的、反对称的、反自反的、可传递的的第二十页，本课件共有162页集合的压缩和开拓集合的压缩和开拓

11、定义：设定义：设R为集合为集合A上的二元关系且上的二元关系且 ，则称则称S上的二元关系上的二元关系 为为R在在S上的压上的压缩，记为缩，记为 ，并称，并称R为为 在在A上的开拓。上的开拓。第二十一页，本课件共有162页集合的压缩和开拓集合的压缩和开拓定理：设定理：设R为为A的二元关系且的二元关系且，那么：，那么：(1)若若R是自反的，则是自反的，则也是自反的；也是自反的；(2)若若R是反自反的，则是反自反的，则也是反自反的；也是反自反的；(3)若若R是对称的，则是对称的，则也是对称的；也是对称的；(4)若若R是反对称的，则是反对称的，则也是反对称的；也是反对称的；(5)若若R是可传递的，则是可

12、传递的，则也是可传递的；也是可传递的；第二十二页，本课件共有162页第四章第四章 二元关系二元关系4.14.1关系的基本概念关系的基本概念4.24.2关系的性质关系的性质4.34.3关系的表示关系的表示4.44.4关系的运算关系的运算4.54.5特殊关系特殊关系第二十三页，本课件共有162页4.3关系的表示关系的表示 定义：设定义：设A和和B为任意的非空有限集，为任意的非空有限集，R为任意一个从为任意一个从A到到B的二元关系。以的二元关系。以 中的每个元素为结点对中的每个元素为结点对每个每个 皆画一条从皆画一条从x到到y的有向边，的有向边，这样得到的一个图称为关系这样得到的一个图称为关系R的关

13、系图。的关系图。一、关系图一、关系图例：例：A=1,2,4;B=3,5,6;关系关系R=,A124B356第二十四页，本课件共有162页一、关系图一、关系图例：设例：设A=2,3,4,5,6,B=6,7,8,12，从，从A到到B的二元关系的二元关系R为为画出其关系图。画出其关系图。解：先求出解：先求出R第二十五页，本课件共有162页一、关系图一、关系图 对称关系对称关系 反对称关系反对称关系第二十六页，本课件共有162页一、关系图一、关系图如果关系图中每个结点上都有环，则如果关系图中每个结点上都有环，则R是是自反的；自反的；如果关系图中每个结点上都没有环，则如果关系图中每个结点上都没有环，则R

14、是反自反的；是反自反的；如果关系图中两顶点间有边，必是一对方如果关系图中两顶点间有边，必是一对方向相反的边向相反的边，则，则R是对称的；是对称的；如果关系图中两顶点间有边，必是一条有如果关系图中两顶点间有边，必是一条有向边向边,则则R是反对称的；是反对称的；如果关系图中顶点如果关系图中顶点xi到到xj有边，有边，xj到到xk有边，有边，则则xi到到xk必有边，则必有边，则R是可传递的。是可传递的。第二十七页，本课件共有162页例例:判断下图中的关系分别具有哪些性质。判断下图中的关系分别具有哪些性质。第二十八页，本课件共有162页二、关系矩阵二、关系矩阵定义：定义：给定两个有限集合给定两个有限集

15、合X=x1,x2,xm和和Y=y1,y2,yn，R是从是从X到到Y的二元关系，如果有：的二元关系，如果有：则称则称rijmn是是R的关系矩阵，记作的关系矩阵，记作MR。第二十九页，本课件共有162页二、关系矩阵二、关系矩阵例：设例：设A=1,2,3,B=a,b,c,R是是A到到B的二元的二元关系，并且关系，并且，试画出，试画出R的的关系图，给出关系矩阵。关系图，给出关系矩阵。第三十页，本课件共有162页二、关系矩阵二、关系矩阵。例：设例：设A=1,2,3,4,R为定义在为定义在A上的二元关系，上的二元关系，R=,，写出关系矩阵。，写出关系矩阵。第三十一页，本课件共有162页二、关系矩阵二、关系

16、矩阵如果关系矩阵主对角线上的记入值全为如果关系矩阵主对角线上的记入值全为1，则，则R是自反的；是自反的；如果主对角线上的记入值全为如果主对角线上的记入值全为0，则，则R是反是反自反的；自反的；如果矩阵关于主对角线是对称的，则如果矩阵关于主对角线是对称的，则R是是对称的；对称的；如果矩阵关于主对角线是反对称的，如果矩阵关于主对角线是反对称的，(亦即亦即rij=1时则一定有时则一定有rji=0),则则R是反对称的；是反对称的；第三十二页，本课件共有162页二、关系矩阵二、关系矩阵如果对于任意的如果对于任意的i,j,k,rij=1并且并且rjk=1时一定时一定有有rik=1 ，则，则R是可传递的；是

17、可传递的；如果存在如果存在i,j,k,rij=1并且并且rjk=1时，有时，有rik 不等不等于于1 ，则，则R是不可传递的；是不可传递的；第三十三页，本课件共有162页第四章第四章 二元关系二元关系4.14.1关系的基本概念关系的基本概念4.24.2关系的性质关系的性质4.34.3关系的表示关系的表示4.44.4关系的运算关系的运算4.54.5特殊关系特殊关系第三十四页，本课件共有162页4.4关系的运算关系的运算 注意：由于关系也是特殊的集合，因此集合注意：由于关系也是特殊的集合，因此集合的运算也适用于关系中。的运算也适用于关系中。设设R1和和R2是从是从A到到B的二元关系，那么的二元关系

18、，那么 也是从也是从A到到B的二元关系，的二元关系，它们分别被称为二元关系它们分别被称为二元关系R1和和R2的交、并、的交、并、差分和对称差分。差分和对称差分。第三十五页，本课件共有162页4.4关系的运算关系的运算例：设集合例：设集合A=a,b,c，B=d,e，定义，定义A到到B的的二元关系二元关系R1=,R2=,则则第三十六页，本课件共有162页4.4关系的运算关系的运算4.4.14.4.1关系的合成关系的合成4.4.24.4.2关系的求逆运算关系的求逆运算4.4.34.4.3关系的闭包运算关系的闭包运算第三十七页，本课件共有162页4.4.1关系的合成关系的合成 定义定义：设：设R是从是

19、从X到到Y的关系，的关系，S是从是从Y到到Z的的关系，于是可用关系，于是可用R S表示从表示从X到到Z的关系，通的关系，通常称它是常称它是R和和S的合成关系，用式子表示即的合成关系，用式子表示即是：是：第三十八页，本课件共有162页例：给定关系例：给定关系R和和S，并且，并且则则第三十九页，本课件共有162页关系的合成关系的合成注意：设是注意：设是R从集合从集合X到集合到集合Y的关系，的关系，S是是从集合从集合Y到集合到集合Z的关系，于是有：的关系，于是有：如果如果R关系的值域与关系的值域与S关系的定义域的交集是关系的定义域的交集是个空集，则合成关系个空集，则合成关系R S也是个空关系；也是个

20、空关系；对于合成关系对于合成关系R S来说，它的定义域是集合来说，它的定义域是集合X的子集，而它的值域则是的子集，而它的值域则是Z的子集，事实上，的子集，事实上，它的定义域是关系它的定义域是关系R的定义域的子集，它的值的定义域的子集，它的值域是关系域是关系S的值域的子集。的值域的子集。第四十页，本课件共有162页试求试求R和和S的合成关系，并给出合成关系的关的合成关系，并给出合成关系的关系矩阵。系矩阵。解解:例：例：给定集合给定集合X=1,2,3,4，Y=2,3,4和和Z=1,2,3。设。设R是从是从X到到Y的关系，并且的关系，并且S是是从从Y到到Z的关系，并且的关系，并且R和和S给定成：给定

21、成：第四十一页，本课件共有162页关系的合成关系的合成第四十二页，本课件共有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、其运算法则与一般矩阵的乘法是相同的，但其中的加法运算和乘法运算应改为布尔加和布是相同的，但其中的加法运算和乘法运算应改为布尔加和布尔乘。尔乘。第四十三页，本课件共有162页合成关系的矩阵表达和图解合成关系的矩阵表达和图解例：求合成关系例：求合成关系的关系矩阵的关系矩阵第四十四页，本课件共有162页关系的合成关系的合成定理：给定集合定理：给定集合X,Y,Z和和W，设，设R1是从是从 X到到Y的关系，的关系，R2和和R3是是Y到到Z的关系，的关系，R4是从是从Z到到W的关系，于是有：的关系，于是有：第四十五页，本课件共有162页关系的合成关系的合成证明：任取元素证明：任取元素当且仅当存当且仅当存在

23、某一个在某一个能使能使和和第四十六页，本课件共有162页证明：任取元素证明：任取元素当且仅当当且仅当存在某一个存在某一个能使能使和和关系的合成关系的合成第四十七页，本课件共有162页关系的合成关系的合成 合成运算是对关系的二元运算，使用这种合成运算是对关系的二元运算，使用这种运算，能够由两个关系生成一个新的关系，运算，能够由两个关系生成一个新的关系，对于这个新的关系又可进行合成运算，从对于这个新的关系又可进行合成运算，从而生成其它关系。而生成其它关系。定理：设定理：设R1是从是从X到到Y的关系，的关系，R2是从是从Y到到Z的的关系，关系，R3是从是从Z到到W的关系，于是有的关系，于是有第四十八

24、页，本课件共有162页关系的合成关系的合成第四十九页，本课件共有162页关系的幂关系的幂定义：给定集合定义：给定集合X，R是是X中的二元关系。设中的二元关系。设，于是，于是R的的n次幂次幂Rn可定义成可定义成(a)R0是集合是集合X中的恒等关系中的恒等关系IX，亦即，亦即(b)第五十页，本课件共有162页关系的幂关系的幂定理：给定集合定理：给定集合X，R是是X中的二元关系。设中的二元关系。设，于是可有，于是可有例：给定集合例：给定集合X=a,b,c，R1,R2,R3,R4是是X中的关系，并给定中的关系，并给定给出这些关系的各次幂给出这些关系的各次幂第五十一页，本课件共有162页关系的幂关系的幂

25、解：解：第五十二页，本课件共有162页关系的幂关系的幂定理：设定理：设X是含有是含有n个元素的有限集合，个元素的有限集合，R是是X中的二元关系。于是存在这样的中的二元关系。于是存在这样的s和和t，能使能使，证明：集合证明：集合X中的每一个二元关系都是中的每一个二元关系都是的子的子集，集，X有有n个元素，个元素，有有n2个元素，个元素，有有个元素，每一个元素都是个元素，每一个元素都是的一个子集，也的一个子集，也是一种二元关系，因而，在是一种二元关系，因而，在X中有中有个不同的二个不同的二元关系。所以，不同的二元关系元关系。所以，不同的二元关系R的幂不会多于个的幂不会多于个。但是序列。但是序列中有

26、中有项，因此这些的方幂中至少有两个是相等的。证项，因此这些的方幂中至少有两个是相等的。证毕。毕。第五十三页，本课件共有162页4.4关系的运算关系的运算4.4.14.4.1关系的合成关系的合成4.4.24.4.2关系的求逆运算关系的求逆运算4.4.34.4.3关系的闭包运算关系的闭包运算第五十四页，本课件共有162页4.4.2关系的求逆运算关系的求逆运算定义：设定义：设R是从是从X到到Y的关系，将的关系，将R中每一序中每一序偶元素次序互换得到的集合称为偶元素次序互换得到的集合称为R的逆关系，的逆关系，记作记作Rc，即，即Rc=|R例：设集合例：设集合X=1,2,3,4,Y=a,b,c,R是集合

27、是集合X到到Y二元关系，二元关系，R=则则Rc=逆关系的关系矩阵：原关系矩阵转置逆关系的关系矩阵：原关系矩阵转置逆关系的关系图：原关系图中颠倒弧线上箭逆关系的关系图：原关系图中颠倒弧线上箭头的方向。头的方向。第五十五页，本课件共有162页关系的求逆运算关系的求逆运算定理：给定集合定理：给定集合X和和Y，R、R1、R2是从是从X到到Y的关系，于是有：的关系，于是有：第五十六页，本课件共有162页(a)(Rc)c=R证明：设证明：设是是R的任意元素。的任意元素。于是于是所以有所以有(Rc)c=R。关系的求逆运算关系的求逆运算第五十七页，本课件共有162页(b)(R1R2)c=R1cR2c证明：证明

28、：关系的求逆运算关系的求逆运算得证得证第五十八页，本课件共有162页关系的求逆运算关系的求逆运算证明：证明：得证。得证。第五十九页，本课件共有162页证明：因为证明：因为，于是有，于是有关系的求逆运算关系的求逆运算得证。得证。第六十页，本课件共有162页合成关系的求逆运算合成关系的求逆运算定理：设定理：设R是从集合是从集合X到到Y的关系。的关系。S是从集合是从集合Y到到Z的关系。于是有的关系。于是有(RS)c=ScRc证明：对于任何证明：对于任何(RS)c利用关系矩阵也可以理解，利用关系矩阵也可以理解，的转置和的转置和是一样的。是一样的。第六十一页，本课件共有162页合成关系的求逆运算合成关系

29、的求逆运算例：给定关系矩阵例：给定关系矩阵MR和和MS。则：则：第六十二页，本课件共有162页定理：设定理：设R是集合是集合X中的关系，中的关系，a)R自反的，当且仅当自反的，当且仅当IX Rb)R反自反的，当且仅当反自反的，当且仅当IXR=c)R是对称的，当且仅当是对称的，当且仅当 R=Rcd)R是反对称的，当且仅当是反对称的，当且仅当 RRc IX e)R是可传递的，当且仅当是可传递的，当且仅当RR R利用关系的运算判定关系的性质利用关系的运算判定关系的性质第六十三页，本课件共有162页即即R Rc；证明证明:c)(充分性充分性)若若R=Rc则则即即R是对称的。是对称的。(必要性必要性)设

30、设R是对称的，那么对任何是对称的，那么对任何对任何对任何即即RcR必要性证明完毕。必要性证明完毕。第六十四页，本课件共有162页关系运算对性质的影响关系运算对性质的影响自反自反性性反自反自反反对称对称性性反对反对称称可传递可传递RC R1 R2 R1R2 R1-R2 R1 R2 第六十五页，本课件共有162页4.4关系的运算关系的运算4.4.14.4.1关系的合成关系的合成4.4.24.4.2关系的求逆运算关系的求逆运算4.4.34.4.3关系的闭包运算关系的闭包运算第六十六页，本课件共有162页4.4.3关系的闭包运算关系的闭包运算闭包的定义：给定集合闭包的定义：给定集合X，R是是X中的二元

31、关系。中的二元关系。如果有另一个关系如果有另一个关系满足满足（1）是自反的是自反的(对称的、可传递的对称的、可传递的)；（2）（3）对于任何自反的）对于任何自反的(对称的、可传递的对称的、可传递的)关关系系，如果，如果，则，则则称关系则称关系为为R的的自反的自反的(对称的，可传对称的，可传递的递的)闭包。闭包。并用并用r(R)表示的表示的R自反闭包，自反闭包，用用s(R)表示表示R的对称闭包，用的对称闭包，用t(R)表示表示R的的可传递闭包。可传递闭包。第六十七页，本课件共有162页关系的闭包运算关系的闭包运算定理：给定集合定理：给定集合X，R是是X中的关系。于是可有中的关系。于是可有(a)当

32、且仅当当且仅当，R才是自反的。才是自反的。(b)当且仅当当且仅当，R才是对称的。才是对称的。(c)当且仅当当且仅当，R才是传递的。才是传递的。第六十八页，本课件共有162页关系的闭包运算关系的闭包运算定理：定理：设设X是任意集合，是任意集合，R是是X中的二元关系，中的二元关系，IX是是X中的恒等关系。于是可有中的恒等关系。于是可有在整数集合中，小于关系在整数集合中，小于关系“”的自反闭包是的自反闭包是“”；恒等关系；恒等关系IX的自反闭包是的自反闭包是IX。不等。不等关系关系“”的自反闭包是全域关系；空关系的自反闭包是全域关系；空关系的自反闭包是恒等关系。的自反闭包是恒等关系。第六十九页，本课

33、件共有162页关系的闭包运算关系的闭包运算定理：给定集合定理：给定集合X，R是是X中的二元关系。于是中的二元关系。于是可有可有 在整数集合中，小于关系在整数集合中，小于关系“”的对称闭包是不的对称闭包是不等关系等关系“”；小于或等于关系；小于或等于关系“”的对的对称闭包是全域关系；恒等关系称闭包是全域关系；恒等关系IX的对称闭包的对称闭包是是IX；不等关系；不等关系“”的对称闭包是不等关系的对称闭包是不等关系“”。第七十页，本课件共有162页关系的闭包运算关系的闭包运算定理：给定集合定理：给定集合X，R是是X中的二元关系。于是中的二元关系。于是可有可有第七十一页，本课件共有162页例：设例：设

34、A=a,b,c,R是是A上的二元关系，上的二元关系，R=求求r(R),s(R),t(R)。解：解：r(R)=RIX=s(R)=RRC=t(R)=RR2 R3=RR2 R3=第七十二页，本课件共有162页关系的闭包运算关系的闭包运算当当A是有限集时，是有限集时，A上只有有限个不同的关系，上只有有限个不同的关系，因此，若因此，若 ，则，则第七十三页，本课件共有162页关系图求闭包关系图求闭包r(R)：在：在R的关系图中，把没有环的结点上加的关系图中，把没有环的结点上加上环，其它不变。上环，其它不变。S(R)：在：在R的关系图中，把单向边改为双向边，的关系图中，把单向边改为双向边，其它不变。其它不变

35、。t(R)：在：在R的关系图中，对每个结点的关系图中，对每个结点x，分别，分别找出可以到达的终点找出可以到达的终点y，若，若x到到y没有有向边，没有有向边，则添加一条有向边，直到添加完毕。则添加一条有向边，直到添加完毕。第七十四页，本课件共有162页关系矩阵求闭包关系矩阵求闭包r(R)：s(R)：t(R)：第七十五页，本课件共有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,

36、k;（4 4）i i加加1 1；（5 5）如果）如果inin，则转到步骤（，则转到步骤（3 3），否则停止。），否则停止。第七十六页，本课件共有162页例：设例：设A=a,b,c,R是是A上的二元关系，上的二元关系，R=求求t(R)。解：解：t(R)=RR2 R3=RR2 R3=第七十七页，本课件共有162页关系的闭包运算关系的闭包运算定理：设定理：设X是集合，是集合，R是是X中的二元关系，于中的二元关系，于是有是有（1）如果）如果R是自反的，那么是自反的，那么s(R),t(R)也是自反也是自反的；的；（2）如果）如果R是对称的，那么是对称的，那么r(R),t(R)也是对称也是对称的；的；（3

37、）如果）如果R是可传递的，那么是可传递的，那么r(R)也是可传递也是可传递的的。第七十八页，本课件共有162页关系的闭包运算关系的闭包运算证明（证明（1）：若）：若R是自反的，则对于所有的是自反的，则对于所有的都有都有即即s(R),t(R)是自反的是自反的第七十九页，本课件共有162页关系的闭包运算关系的闭包运算证明证明(2):若若R是对称的，是对称的，则对于任何则对于任何R都有都有R，则则RIX及及RIX，即即r(R)是对称的。是对称的。又因为又因为可知可知t(R)也是对称的，得证。也是对称的，得证。第八十页，本课件共有162页关系的闭包运算关系的闭包运算证明（证明（3）：若）：若R是可传递

38、的，是可传递的，即当即当时有时有，假定存在，假定存在讨论四种情况讨论四种情况第八十一页，本课件共有162页关系的闭包运算关系的闭包运算定理：设定理：设X是集合，是集合，R是集合中的二元关系，于是有是集合中的二元关系，于是有证明：证明：第八十二页，本课件共有162页关系的闭包运算关系的闭包运算证明（证明（b）：因为）：因为，而，而对于所有的对于所有的有有，以及，以及。根据这些关系式，可有根据这些关系式，可有于是于是第八十三页，本课件共有162页关系的闭包运算关系的闭包运算证明（证明（c）：如果）：如果，则，则，根据对称闭包的定义，有根据对称闭包的定义，有。首先构成上式两侧。首先构成上式两侧的可传

39、递闭包，再依次构成两侧的对称闭包的可传递闭包，再依次构成两侧的对称闭包,可以求可以求得得以及以及。而。而ts(R)是对称的，是对称的，所以所以，从而有，从而有。第八十四页，本课件共有162页关系的闭包运算关系的闭包运算注意：注意：（1）通常用）通常用R+表示表示R的可传递闭包的可传递闭包t(R)，并，并读作读作“R加加”。（2）通常用）通常用R*表示表示R的自反可传递闭包的自反可传递闭包tr(R)，并读作，并读作“R星星”。第八十五页，本课件共有162页第四章第四章 二元关系二元关系4.14.1关系的基本概念关系的基本概念4.24.2关系的性质关系的性质4.34.3关系的表示关系的表示4.44

40、.4关系的运算关系的运算4.54.5特殊关系特殊关系第八十六页，本课件共有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偏序集合与哈斯图偏序集合与哈斯图第八十七页，本课件共有162页4.5.1集合的划分和覆盖集合的划分和覆盖定义：给定非空集合定义：给定非空集合S，设非空集合，设非空集合A=A1,A2,An，如果有，如果有则称集合则称集合A是集合是集合S的覆盖。的覆盖。注意：集合的覆盖不唯一。注意：集合的覆盖不唯一。例如：例如：S=a

41、,b,c，A=a,b,b,c，B=a,b,c，A和和B都是集合都是集合S的覆盖。的覆盖。第八十八页，本课件共有162页集合的划分和覆盖集合的划分和覆盖定义：给定非空集合定义：给定非空集合S，设非空集合，设非空集合A=A1,A2,An，如果有，如果有则称集合则称集合A是集合是集合S的一个划分。的一个划分。例如：例如：S=a,b,c，A=a,b,c，B=a,b,c，A和和B都是集合都是集合S的划分。的划分。第八十九页，本课件共有162页集合的划分和覆盖集合的划分和覆盖划分中的元素划分中的元素Ai称为划分的称为划分的类类。划分的类的数目叫划分的划分的类的数目叫划分的秩秩。划分是覆盖的特定情况，即中元

42、素划分是覆盖的特定情况，即中元素互不相交的特定情况。互不相交的特定情况。集合的划分不唯一。集合的划分不唯一。第九十页，本课件共有162页集合的划分和覆盖集合的划分和覆盖例：设例：设S=1,2,3，考虑下列集合，考虑下列集合S的覆盖的覆盖S的覆盖的覆盖S的覆盖、划分，秩为的覆盖、划分，秩为2S的覆盖、划分，秩为的覆盖、划分，秩为1，最小划分，最小划分S的覆盖、划分，秩为的覆盖、划分，秩为3，最大划分，最大划分第九十一页，本课件共有162页定义定义:若若AA1 1,A,A2 2,A,Ar r 与与BB1 1,B,B2 2,B,Bs s 是同一集是同一集合合A A的两种划分的两种划分,则其中所有则其

43、中所有A Ai iBBj j 组成的组成的集合，称为是原来两种划分的交叉划分。集合，称为是原来两种划分的交叉划分。定理：定理：AA1 1,A,A2 2,A,Ar r 与与BB1 1,B,B2 2,B,Bs s 是同一集合是同一集合A A的两种划分，则其交叉划分亦是原集合的的两种划分，则其交叉划分亦是原集合的一种划分。一种划分。第九十二页，本课件共有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

44、 1,A,A2 2,A,Ar r 称为是称为是BB1 1,B,B2 2,B,Bs s 的加的加细。细。定理：定理：任何两种划分的交叉划分，都是原来任何两种划分的交叉划分，都是原来各划分的一种加细。各划分的一种加细。第九十三页，本课件共有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偏序集合与哈斯图偏序集合与哈斯图第九十四页，本课件共有162页4.5.2等价关系等价关系定义：设定义：设X是任意集合是任意集合,R是集合中的二元关系。是集

45、合中的二元关系。如果如果R是自反的、对称的和可传递的，是自反的、对称的和可传递的，则称则称R是是等价关系。即满足以下几点：等价关系。即满足以下几点：如果如果R是集合是集合X中的等价关系，则中的等价关系，则R的域是集合的域是集合X自身，所以称自身，所以称R是定义于集合是定义于集合X中的关系。中的关系。第九十五页，本课件共有162页4.5.2等价关系等价关系例如例如 数的相等关系是任何数集上的等价关系。数的相等关系是任何数集上的等价关系。又又例例如如一一群群人人的的集集合合中中姓姓氏氏相相同同的的关关系系也也是是等等价价关系。关系。但朋友关系不是等价关系，因为它不可传递。但朋友关系不是等价关系，因

46、为它不可传递。第九十六页，本课件共有162页等价关系等价关系例：给定集合例：给定集合X=1,2,7,7，R是是X中的二元关中的二元关系，并且给定成系，并且给定成试证明试证明R是等价关系。是等价关系。解：解：R的关系矩阵如下：的关系矩阵如下：第九十七页，本课件共有162页等价关系等价关系R的关系图如下：的关系图如下：第九十八页，本课件共有162页等价关系等价关系注意：注意：上例是模数系统中模等价关系的特定情况。上例是模数系统中模等价关系的特定情况。设设R+是正整数集合，是正整数集合，m是个正整数。对于是个正整数。对于来说，可将来说，可将R定义成定义成。这里，这里，“x-y可被可被m整除整除”等价

47、于命题等价于命题“当用当用m去除去除x和和y时，它们都有同样的余数时，它们都有同样的余数”。故关系。故关系R也称为也称为模模m同余关系同余关系。第九十九页，本课件共有162页等价关系等价关系定理：任何集合定理：任何集合中的模中的模m相等关系，是一相等关系，是一个等价关系。个等价关系。证明：要证明证明：要证明R是个等价关系，就必须证明是个等价关系，就必须证明R是自是自反的、对称的和可传递的。反的、对称的和可传递的。(1)对于任何对于任何来说，因为来说，因为x-x=0m，所以有，所以有。因此，模。因此，模m相等关系是自反的。相等关系是自反的。第一百页，本课件共有162页等价关系等价关系(2)对于任

48、何对于任何来说，如果来说，如果，则，则存在某一个存在某一个，能使，能使x-y=nm。于是可有。于是可有y-x=(-n)m，因此有，因此有，即模，即模m相等关相等关系是对称的。系是对称的。(3)设设，和和。于是存在。于是存在，能使，能使和和。而。而，从而可有，从而可有，即模，即模m相等关系是可传相等关系是可传递的。递的。第一百零一页，本课件共有162页等价类等价类定义：设定义：设是集合是集合A上的等价关系，则上的等价关系，则A中等价中等价于元素于元素的所有元素组成的集合称为的所有元素组成的集合称为生成的等生成的等价类，用价类，用表示，即表示，即定义：设定义：设R是集合是集合A上的等价关系，若元素

49、上的等价关系，若元素aRb，则称，则称a与与b等价，或称等价，或称b与与a等价。等价。第一百零二页，本课件共有162页等价类等价类例：设例：设X=a,b,c,d，R是是X中的等价关系，并把中的等价关系，并把R给定成给定成则：则：第一百零三页，本课件共有162页等价类的性质等价类的性质1.1.对任意对任意,因为对于任意的因为对于任意的 X X,有有 ，所以，所以 设设X是一集合，是一集合，R是是X上的等价关系上的等价关系2 2.如果如果，则，则3.对于所有的对于所有的，或者，或者，或者，或者证明：分两种情况讨论证明：分两种情况讨论(1)xRy(2)xRy第一百零四页，本课件共有162页等价类的性

50、质等价类的性质(1)xRy故故 。类似地可以证明类似地可以证明由上得由上得若若 ，则，则xRxRz z ，由由R R 的对称性有的对称性有zRxzRx，又由又由R R的传递性有的传递性有zRyzRy ，因此，因此 (2)xRy假设假设 ,因此有因此有 且且 ，故故 于是由于是由xRzxRz,zRb，得，得xRyxRy，与，与xRy相矛盾相矛盾第一百零五页，本课件共有162页等价类的性质等价类的性质4.证明：假定证明：假定，对于某个，对于某个，有，有。由于由于，会有，会有，因而，因而。设设，于是，于是因而因而证毕。证毕。第一百零六页，本课件共有162页等价类的性质等价类的性质例例设设A=a,b,