第四章关系优秀PPT.ppt

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

1、第四章第四章 关系关系第一页，本课件共有85页一、有序对一、有序对 定定义义 由由两两个个固固定定次次序序的的个个体体x x，y y组组成成的的序序列列称称为为有有序序对对或或序序偶偶，记记为为xy，其其中中x x，y y分分别别称称为为序序偶偶的的第第一、二元素（或称第一、二分量）。一、二元素（或称第一、二分量）。第一节第一节 有序对与笛卡尔积有序对与笛卡尔积2 2、=当且仅当当且仅当a=u,b=v.a=u,b=v.注注：1 1、当、当abab时，时，.第二页，本课件共有85页二、二、笛卡儿积的概念笛卡儿积的概念 1.1.定定义义 给给定定集集合合A A和和B B，称称集集合合xy xAyB

2、xAyB为为A A与与B B的笛卡尔积，简称为卡氏积，记为的笛卡尔积，简称为卡氏积，记为ABAB。注注：a a）设）设 ，故故的子集个数：的子集个数：第三页，本课件共有85页 b b）推广：称）推广：称为为A A1 1,A,A2 2,.,A,.,An n的笛卡尔积。特别的，记的笛卡尔积。特别的，记为为A A的的n n次幂，且有次幂，且有第四页，本课件共有85页例例 （1 1）A=aA=a，bb，B=cB=c，dd，求，求ABAB和和BA BA。(2)A=a,b,B=1,2,C=c,(2)A=a,b,B=1,2,C=c,求求(AB)C(AB)C和和A(BC)A(BC)。解（解（1 1）AB=aA

3、B=a，bcbc，d=ad=c，ad，b c，bd BA=c BA=c，dada，b=cb=a，cb，d a，d b（2 2）AB=aAB=a，b1b1，22=a=1，a2，b1，b2。第五页，本课件共有85页（ABAB）C=aC=1，cc，a2，cc，b 1，cc，b2，cc BC=1BC=1，2c=12c=c，2c。A A（BCBC）=a=a，1c，aa，2c，b b，1c，b b，2c。第六页，本课件共有85页2.2.笛卡儿积的性质笛卡儿积的性质 1)1)对任意集合对任意集合A A，有，有AA=，A=A=。2)2)笛卡尔积不满足交换律，即一般的，当笛卡尔积不满足交换律，即一般的，当A A

4、，B B且且A AB B时，时，AAB BBBA A。3)3)笛卡尔积不满足结合律，即一般的，当笛卡尔积不满足结合律，即一般的，当A,B,CA,B,C时，时，(AAB)B)CC A(BCA(BC)。第七页，本课件共有85页5)5)设设A,B,C,DA,B,C,D为为四四个个非非空空集集合合，则则ABAB CDCD的的充充分分必必要要条条件是：件是：A A C C且且B B D D。4)4)笛卡尔积关于交、并满足分配律。笛卡尔积关于交、并满足分配律。（1 1）AA（BCBC）=（ABAB）（ACAC）（2 2）AA（BCBC）=（ABAB）（ACAC）（3 3）（）（ABAB）C=C=（ACAC

5、）（BCBC）（4 4）（）（ABAB）C=C=（ACAC）（BCBC）第八页，本课件共有85页2.2.定义定义 设设S S是是A A到到B B上的二元关系，称上的二元关系，称 x x y(yy(y BxBy S)S)为为S S的定义域，记作的定义域，记作D(S).D(S).称称yy x x（xAxxASyS）为为S S的值域，记作的值域，记作R(S)R(S)。1.1.定定义义 设设A A，B B是是两两个个集集合合，R R是是ABAB的的任任一一子子集集，则则称称R R为为从从A A到到B B的的一一个个二二元元关关系系，简简称称关关系系。特特别别当当A=BA=B时时，则则称称R R为为A

6、A上的二元关系（或上的二元关系（或A A上的关系）。上的关系）。第二节第二节 二元关系二元关系一、概念一、概念第九页，本课件共有85页二、三种特殊关系：二、三种特殊关系：1.A1.A上的关系：上的关系：I IA A=a=aa a AA，称为，称为A A上的恒等上的恒等关系。关系。2.A2.A到到B B上的全关系：上的全关系：AB=a AB=b aAbBaAbB3.A3.A到到B B上的空关系上的空关系。第十页，本课件共有85页三、关系的表示三、关系的表示1 1、集合形式、集合形式2 2、关系图形式（关系表示法）、关系图形式（关系表示法）1)1)将将A A，B B中元素称为结点，画为中元素称为结

7、点，画为 ；2)2)若若aRbR，画从，画从a a到到b b的有向弧；的有向弧；3)3)对对A A上的关系上的关系R R，若，若aRaR，画，画a a点的自回路。点的自回路。将涉及到二元关系将涉及到二元关系R R的集合元素及序偶按以上规定的集合元素及序偶按以上规定画出图，称为画出图，称为R R的关系图。的关系图。第十一页，本课件共有85页 注注：1)1)空关系：只有结点。空关系：只有结点。2)2)全关系：全关系：AB:A AB:A的每个结点到的每个结点到B B的任一结点均有有向弧。的任一结点均有有向弧。A A2 2:每个结点均有自回路，且任意两个不同结每个结点均有自回路，且任意两个不同结点均有

8、有向弧。点均有有向弧。3)3)恒等关系恒等关系I IA A：只有每个结点均有自回路。：只有每个结点均有自回路。第十二页，本课件共有85页解解 R R的关系图，如图所示：的关系图，如图所示：例例 A=1,2,3,4 A=1,2,3,4，B=5,6,7B=5,6,7，R=R=，作出，作出R R的关系图。的关系图。第十三页，本课件共有85页解解 A A上的关系图如图所示。上的关系图如图所示。例例 设设A=1A=1，2 2，3 3，44，R=1R=2，22，33，41。画出。画出A A上的关系图。上的关系图。第十四页，本课件共有85页3 3、关系的矩阵表示、关系的矩阵表示 设设A=aA=a1 1,a,

9、a2 2,a,am m,B=b,B=b1 1,b,b2 2,b,bn n,R,R为为A A到到B B上的上的二元关系，称矩阵二元关系，称矩阵M MR R=(m=(mijij)mnmn为为R R的关系矩阵，其中的关系矩阵，其中 注注：1)1)空关系：空关系：M M空空=0=0；2)2)全关系：全关系：3)3)恒等关系：恒等关系：第十五页，本课件共有85页一、关系的基本运算一、关系的基本运算 例例 设设X=1X=1，2 2，3 3，4 4，55，若若A=xA=y x x与与y y的的差差能能被被2 2整整除除，B=xB=y x x与与y y的的差差为为正正且且能能被被3 3整整除除，求求ABAB，

10、ABAB，A-BA-B，B-AB-A，A A。第三节第三节 关系的运算关系的运算解解 A=1 A=1，13，15，22，2 4，31，33，35，42，4 4，51，53，55 B=4 B=1，52第十六页，本课件共有85页AB=1AB=1，13，15，22，24，3 1，33，35，41，42，4 4，51，52，53，55AB=AB=A-B=1A-B=1，13，15，22，24，3 1，33，35，42，44，5 1，53，55第十七页，本课件共有85页B-A=4B-A=1，52A=XA=X2 2-A-A =1 =2，14，21，23，25，3 2，34，41，43，45，5 2，54 注

11、注：A A到到B B上的关系的交并差补运算结果仍为上的关系的交并差补运算结果仍为A A到到B B上的上的关系。关系。第十八页，本课件共有85页二、关系的特殊运算二、关系的特殊运算 1.1.定义定义 设设R,SR,S分别是集合分别是集合A A到到B,BB,B到到C C上的二元关系，则上的二元关系，则R RS S称为称为R R和和S S的复合关系，表示为的复合关系，表示为R RS=S=xAzCxAzC y(yBRS)y(yBRS)A:A:复合运算（复合关系）复合运算（复合关系）第十九页，本课件共有85页例例 A=1,2,3,4,B=3,5,7,C=1,2,3,A=1,2,3,4,B=3,5,7,C

12、=1,2,3,R=R=，S=S=，.R RS=2S=2，43。如图所示：如图所示：第二十页，本课件共有85页 注注：a)a)复合运算不满足交换律，即复合运算不满足交换律，即R RS SR RS Sb)b)推推广广 设设R R是是从从A A上上的的关关系系,n,n为为整整数数,关关系系R R的的n n次次幂幂定义如下：定义如下：（1 1）R R0 0=x=xxA=IxA=IA A；（2 2）R Rn+1n+1=R=Rn nR R。从关系从关系R R的的n n次幂定义，可得出下面的结论：次幂定义，可得出下面的结论：（1 1）R Rn+mn+m=R=Rn nR Rm m；（2 2）（）（R Rn n

13、）m m=R=Rnmnm。第二十一页，本课件共有85页定理定理 设设R,SR,S分别是从分别是从A A到到B B，B B到到C C的关系，其中的关系，其中A=aA=a1 1,a,a2 2,a,am m，B=bB=b1 1,b,b2 2,b,bn n，C=cC=c1 1,c,c2 2,c,ct t，而，而M MR R,M,MS S和和M MR RS S分别为关系分别为关系R,SR,S和和R RS S的关系矩阵，则有的关系矩阵，则有 M MR RS S=M=MR RMMS S其中其中为矩阵的乘法，而元素运算为布尔运算。为矩阵的乘法，而元素运算为布尔运算。2 2、复合运算与关系矩阵、复合运算与关系矩

14、阵第二十二页，本课件共有85页b)b)复合运算关于并满足分配律，即复合运算关于并满足分配律，即(1)R(1)R(ST)=R(ST)=RSRSRT T(2)(RS)(2)(RS)T=RT=RTSTST T复合运算关于交满足下面两式成立：复合运算关于交满足下面两式成立：(3)R(3)R(ST)(ST)R RSRSRT T(4)(RS)(4)(RS)T T R RTSTST T3 3、复合运算的性质、复合运算的性质a)a)复合运算满足结合律，即设复合运算满足结合律，即设R,S,TR,S,T分别是从分别是从A A到到B,BB,B到到C,CC,C到到D D的关系，则有的关系，则有R R(S(ST)=(R

15、T)=(RS)S)T T。第二十三页，本课件共有85页1 1、定定义义 设设R R是是A A到到B B的的二二元元关关系系，如如果果将将R R中中每每个个序序偶偶的的第第一一元元素素和和第第二二元元素素的的顺顺序序互互换换，所所得得到到的的集集合合称称为为R R的的逆关系，记为逆关系，记为R R-1-1，即，即R R-1-1=y=x xRyRB.B.逆运算逆运算 注注：1)R1)R关系图中有向弧的方向反向就得关系图中有向弧的方向反向就得R R-1-1的关系图。的关系图。2)2)关系矩阵：关系矩阵：3)3)特殊关系的逆关系说明：特殊关系的逆关系说明：第二十四页，本课件共有85页(1)(1)（R

16、R-1-1）-1-1=R=R(2)(R(2)(RS)S)-1-1=S=S-1-1R R-1-1(3)(RS)(3)(RS)-1-1=R=R-1-1SS-1-1(4)(RS)(4)(RS)-1-1=R=R-1-1SS-1-1(5)(5)(R)R)-1-1=(R(R-1-1)(6)(R-S)(6)(R-S)-1-1=R=R-1-1-S-S-1-1(7)(7)若若R R S S中，则中，则R R-1-1 S S-1-1。2 2、逆运算的性质、逆运算的性质第二十五页，本课件共有85页有限集合上关系运算的矩阵形式小结有限集合上关系运算的矩阵形式小结1 1、并运算、并运算定理定理1 1：设：设R,SR,S

17、均为有限集合均为有限集合A A到到B B上的二元关系，则上的二元关系，则其中矩阵加法为常规矩阵加法，元素间的加法为布尔加其中矩阵加法为常规矩阵加法，元素间的加法为布尔加法。法。推论：设推论：设R Ri i(i=1,2,(i=1,2,k),k)均为有限集合均为有限集合A A到到B B上的二元上的二元关系，则关系，则第二十六页，本课件共有85页2 2、交运算、交运算定理定理2 2：设：设R,SR,S均为有限集合均为有限集合A A到到B B上的二元关系，则上的二元关系，则其中其中“”为为H H乘法（对应相乘）乘法（对应相乘）,元素间的乘法为布尔乘法。元素间的乘法为布尔乘法。【注】：【注】：1 1、H

18、 H乘法一般定义：乘法一般定义：其中元素间的乘法为布尔乘法。其中元素间的乘法为布尔乘法。第二十七页，本课件共有85页2 2、H H乘法满足以下性质：乘法满足以下性质：b b）分配律：）分配律：c c）结合律：）结合律：d d）其中其中e e）a a）交换律：）交换律：第二十八页，本课件共有85页3 3、补运算、补运算定理定理3 3：设：设R R为有限集合为有限集合A A，B B上的二元关系，则上的二元关系，则其中其中“”为矩阵的余运算：为矩阵的余运算：。4 4、差运算、差运算定理定理4 4：设：设R R，S S都为都为A A到到B B上的二元关系，则上的二元关系，则.第二十九页，本课件共有85

19、页5 5、逆运算、逆运算定理定理5 5：设：设R R为有限集合为有限集合A A到到B B上的二元关系，则上的二元关系，则。6 6、复合运算、复合运算定理定理6 6：设：设R R，S S分别为有限集合分别为有限集合A A，B B和和B B，C C上的二元上的二元关系，则关系，则其中其中“”为常规矩阵乘法，元素间的乘法和加法分别为为常规矩阵乘法，元素间的乘法和加法分别为布尔乘法和布尔加法运算。布尔乘法和布尔加法运算。第三十页，本课件共有85页定定义义 设设R R是是集集合合A A上上的的二二元元关关系系，如如果果对对于于每每个个x x A A，都都有有 R R，则称二元关系，则称二元关系R R是自

20、反的。是自反的。第四节第四节 关系的性质关系的性质一、自反性和反自反性一、自反性和反自反性 1 1、自反性、自反性【注】【注】R R在在A A上是自反的上是自反的 I IA A R RM MR R主对角线元素均为主对角线元素均为1 1。R R的关系图中任意结点均有自回路。的关系图中任意结点均有自回路。第三十一页，本课件共有85页定义定义 设设R R是集合是集合A A上的二元关系，如果对于每个上的二元关系，如果对于每个x x A A，都，都有有 R R，则称二元关系，则称二元关系R R是反自反的。是反自反的。2 2、反自反性、反自反性【注】【注】R R在在A A上是反自反的上是反自反的 I IA

21、 ARR M MR R主对角线元素均为主对角线元素均为0 0。R R的关系图中每个结点都无自回路。的关系图中每个结点都无自回路。第三十二页，本课件共有85页定定义义 设设R R是是集集合合A A上上的的二二元元关关系系，若若对对任任意意xRyR，就就有有yRxR，则称二元关系，则称二元关系R R是对称的。是对称的。二、对称性和反对称性二、对称性和反对称性 1 1、对称性、对称性【注】【注】R R在在A A上是对称的上是对称的 R R-1-1=R=RM MR RM MR R。R R的关系图中任意不同结点间的有向弧要么成的关系图中任意不同结点间的有向弧要么成对出现要么没有。对出现要么没有。第三十三

22、页，本课件共有85页定义定义 设设R R是集合是集合A A上的二元关系，若上的二元关系，若R,R,则则x=yx=y或或yx R,R,称二元关系称二元关系R R是反对称的。是反对称的。2 2、反对称性、反对称性【注】【注】R R在在A A上是反对称的上是反对称的 若若，RR，则，则x=yx=y。M MR R元素中若元素中若a aijij=1(i=1(ij),j),则则a ajiji=0=0。R R的关系图中不同结点间若有有向弧，则只有的关系图中不同结点间若有有向弧，则只有一条。一条。第三十四页，本课件共有85页定义定义 设设R R是集合是集合A A上的二元关系，若上的二元关系，若xy，yRzR，

23、就有，就有xRzR则称二元关系则称二元关系R R在在A A上是传递的。上是传递的。3 3、传递性、传递性例例1 1：设：设A A为集合，为集合，A A上的二元关系为上的二元关系为R R，证明：，证明：2 2、R R是传递的是传递的。1 1、R R是反对称的是反对称的第三十五页，本课件共有85页1 1、定定义义 设设R R是是集集合合A A上上的的关关系系，若若A A上上的的另另一一关关系系R R满足：满足：（1 1）R R是自反的（对称的、传递的）；是自反的（对称的、传递的）；（2 2）R R R R；（3 3）对对于于A A上上任任何何包包含含R R的的自自反反的的（对对称称的的、传传递递的

24、的）关系关系R R，都有，都有R R R R。则称关系则称关系R R为为R R的自反（对称、传递）闭包。的自反（对称、传递）闭包。第五节第五节 关系的闭包关系的闭包一、关系闭包的概念一、关系闭包的概念第三十六页，本课件共有85页【注】：【注】：a.a.闭包闭包R R是包含是包含R R的具有自反（对称，传递）性的具有自反（对称，传递）性质的最小关系。质的最小关系。b.b.记号记号:自反闭包自反闭包r(R);r(R);对称闭包对称闭包s(R);s(R);传递闭包传递闭包t(R).t(R).2 2、性质、性质1)1)设设R R是是A A上的关系，则上的关系，则a)Ra)R是自反的是自反的r(R)=R

25、.r(R)=R.b)Rb)R是对称的是对称的s(R)=R.s(R)=R.c)Rc)R是传递的是传递的t(R)=R.t(R)=R.第三十七页，本课件共有85页2)2)设设R R，S S是非空集合是非空集合A A上的关系，且上的关系，且R R S S，则，则a a）r r（R R）r r（R R）；）；b b）s s（R R）s s（R R）；）；c c）t t（R R）t t（R R）。）。3)3)设设R R是非空集合是非空集合A A上的关系，则上的关系，则a a）rsrs（R R）=sr=sr（R R）；）；b b）rtrt（R R）=tr=tr（R R）；）；c c）tsts（R R）st

26、st（R R）。）。第三十八页，本课件共有85页定理定理 设设R R是集合是集合A A上的二元关系，则上的二元关系，则r r（R R）=RI=RIA A，s s（R R）=RR=RR1 1,t t（R R）=RR=RR2 2RR3 3特别的，若特别的，若A An n，则，则t t（R R）=RR=RR2 2RR3 3RRn n二、关系闭包的求法二、关系闭包的求法1 1、公式法、公式法第三十九页，本课件共有85页例例 设设A=a,b,c,d,AA=a,b,c,d,A上关系上关系R=(a,a),(a,b),(b,b),(b,c),(c,d)R=(a,a),(a,b),(b,b),(b,c),(c,

27、d)求：求：r(R),s(R),t(R)r(R),s(R),t(R)2 2、关系图法、关系图法1)1)在在R R的关系图中将没有自回路的节点添加自回路，的关系图中将没有自回路的节点添加自回路，即得即得r(R)r(R)的关系图。的关系图。2)2)在在R R的关系图中将只有一条有向弧的两个不同节的关系图中将只有一条有向弧的两个不同节点间添加另一方向的有向弧，即得点间添加另一方向的有向弧，即得s(R)s(R)的关系图。的关系图。3)3)在在R R的关系图中若的关系图中若a a到到b b，b b到到c c均有有向弧，则添加均有有向弧，则添加a a到到c c的有向弧，逐一添加即得的有向弧，逐一添加即得t

28、(R)t(R)的关系图。的关系图。第四十页，本课件共有85页3 3、关系矩阵法、关系矩阵法定理定理 设设R R为有限集合为有限集合A A上的关系，上的关系，A An,n,则则(1)M(1)Mr(R)r(R)=M=MR R+I+In n(2)M(2)Ms(R)s(R)=M=MR R+M+MR R(1)M(1)Mt(R)t(R)=M=MR R+M+MR R2 2+M+MR Rn n第四十一页，本课件共有85页定义定义 设设R R是非空集合是非空集合A A上的二元关系，如果上的二元关系，如果R R是自反的、是自反的、对称的和传递的，则称对称的和传递的，则称R R是集合是集合A A上的等价关系上的等价

29、关系.例例 (1)(1)设设集集合合A=aA=a，b b，c c，dd，R=aR=a，ad，da，dd，bb，bc，cb，c c 第六节第六节 等价关系与划分等价关系与划分一、概念一、概念(2)(2)数学对象的相等数学对象的相等第四十二页，本课件共有85页(3)(3)集合上的恒等关系及全关系集合上的恒等关系及全关系(4)(4)整数集合整数集合Z Z上的模上的模n n同余关系同余关系(5)(5)直线间的平行关系直线间的平行关系例例 设设R R是集合是集合A A上的自反关系。上的自反关系。证明：证明：R R是等价关系充要条件是：是等价关系充要条件是：若若(a,b),(b,c)R(a,b),(b,c

30、)R，则，则(b,c)R(b,c)R第四十三页，本课件共有85页定定义义 设设R R是是非非空空集集合合A A上上的的等等价价关关系系，对对于于任任何何aAaA，集集合合aaR R=x=x xAxA且且aRxR称称为为元元素素a a形形成成的的关关于于R R的等价类。的等价类。二、集合的划分二、集合的划分1 1、等价类、等价类例例 A=1 A=1，2 2，3 3，4 4，55上的关系上的关系R R为为R=1R=1，12，21，13，31，22，23，32，33，44，45，54，55。第四十四页，本课件共有85页【注】等价类的性质：设【注】等价类的性质：设R R是非空集合是非空集合A A上的等

31、价关系，上的等价关系，则则(1)(1)对任意对任意aA,aaA,a是是A A的非空子集；的非空子集；(2)(2)对任意对任意a,bA,a,bA,若若(a,b)R,(a,b)R,则则a=b;a=b;(3)(3)对任意对任意a,bA,a,bA,若若(a,b)R,(a,b)R,则则ab=ab=;(4)(4)a=Aa=A第四十五页，本课件共有85页定义定义 设设R R是集合是集合A A上的等价关系上的等价关系,等价类集合等价类集合aaR R aAaA称作称作A A关于关于R R的商集，记作的商集，记作A/RA/R。2 2、商集、商集【注】：【注】：1)1)等价定义：设等价定义：设R R是非空集合是非空

32、集合A A上的等价关系，上的等价关系，以以R R的不交等价类为元素的集合叫做的不交等价类为元素的集合叫做A A在在R R下的商集。下的商集。2)A/R2)A/R(A)(A)3)3)设设R,SR,S均为集合均为集合A A上的等价关系，则上的等价关系，则A/R=A/SA/R=A/S当且仅当且仅当当R=SR=S。第四十六页，本课件共有85页定定义义 设设A A是是一一个个集集合合，A A1 1，A A2 2，A Am m是是它它的的非非空空子子集集，如果它满足下列条件：如果它满足下列条件：（1 1）A Ai iAAj j=，i i j j，i,j=1,2,i,j=1,2,m,m（2 2）A A1 1

33、AA2 2AAm m=A=A则则称称A=AA=A1 1，A A2 2，A Am m 为为集集合合A A的的一一个个划划分分，而而A A1 1，A A2 2，A Am m称为这个划分的块。称为这个划分的块。3 3、集合的划分、集合的划分第四十七页，本课件共有85页1)1)设设R R是是非非空空集集合合A A上上的的等等价价关关系系，A/RA/R即即为为A A的的一一个个划分。划分。2)2)集合集合A A的一个划分确定的一个划分确定A A上的一个等价关系。上的一个等价关系。【注】：集合【注】：集合A A的划分与其上的等价关系的联系的划分与其上的等价关系的联系第四十八页，本课件共有85页定定义义 设

34、设R R是是集集合合A A上上的的关关系系，若若R R是是自自反反的的、反反对对称称的的和和传传递递的的，则则称称R R是是A A上上的的偏偏序序关关系系，记记为为“”。序序偶偶A 称称作偏序集。作偏序集。第七节第七节 偏序关系偏序关系一、概念一、概念1)1)集合的包含关系集合的包含关系2)2)实数间的实数间的“”关系关系3)3)集合集合A A上的恒等关系上的恒等关系I IA A4)Z4)Z+中元素间的整除关系，中元素间的整除关系，R=x,yR=x,yZ Z+,x,x整除整除yy第四十九页，本课件共有85页二、偏序集的哈斯图二、偏序集的哈斯图偏序关系关系图的一种简化偏序关系关系图的一种简化1

35、1、由、由R R是自反的，从而去掉是自反的，从而去掉R R关系图中每个结点上的自关系图中每个结点上的自回路；回路；2 2、由、由R R是反对称的，从而若是反对称的，从而若a a到到b b有有向弧，则去掉弧上的有有向弧，则去掉弧上的方向，将方向，将b b画在画在a a的上方；的上方；3 3、由、由R R是传递的，则若是传递的，则若a a到到b b，b b到到c c均有有向弧，则去均有有向弧，则去掉掉a a到到c c的有向弧；的有向弧；完成上述删除过程，即得偏序集的哈斯图。完成上述删除过程，即得偏序集的哈斯图。第五十页，本课件共有85页【注】：对具体偏序集合【注】：对具体偏序集合(A,R)(A,R

36、)，总结画哈斯图的一般，总结画哈斯图的一般步骤：步骤：1)1)将偏序关系将偏序关系R R列举表示成列举表示成R=RR=R1 1IIA A，其中，其中2)2)若若(a,b),(b,c)R(a,b),(b,c)R1 1,则去掉则去掉(a,c)(a,c)，完成所有如此删除，完成所有如此删除过程。过程。3)3)对对R R1 1中剩余元素按规则作图，即得哈斯图。中剩余元素按规则作图，即得哈斯图。第五十一页，本课件共有85页三、偏序集上的特殊元素三、偏序集上的特殊元素1 1、极小元，极大元、极小元，极大元定定义义 设设A 是是偏偏序序集集，B B是是A A的的子子集集，对对bBbB，若若不不存存在在xBx

37、B，使使x x b b且且b b x x（x x b b），则则称称b b为为B B的的极极大大元（极小元）。元（极小元）。【注】：【注】：1)1)子集子集B B的极小的极小(大大)元，必须在元，必须在B B中。中。2)2)哈斯图中的孤立点既是极小元，又是极大元。哈斯图中的孤立点既是极小元，又是极大元。第五十二页，本课件共有85页（3）对于非空有穷偏序集来说，一定存在极大（小）对于非空有穷偏序集来说，一定存在极大（小）元，有时甚至是多个，凡是在哈斯图中向上（下）路元，有时甚至是多个，凡是在哈斯图中向上（下）路径的每一个终点都是一个极大（小）元。径的每一个终点都是一个极大（小）元。第五十三页，本

38、课件共有85页定定义义 设设A 是是偏偏序序集集，B B是是A A的的子子集集，b b B B，若若B B中中任任何何元元素素x x，都都满满足足x x b b（b b x x），则则称称b b为为B 的的最最大元（最小元）。大元（最小元）。2 2、最小元，最大元、最小元，最大元【注】：子集的最小元和最大元若存在，则必唯一。【注】：子集的最小元和最大元若存在，则必唯一。第五十四页，本课件共有85页3 3、界与确界、界与确界定定义义 设设A 是是偏偏序序集集，B B是是A A的的子子集集，a a A A，若若B B中中任任何何元元素素x x，都都满满足足x x a a（a a x x），则则称称

39、a a为为B 的的上上界界（下界）。（下界）。设设a a是是B B的一个上界（下界），则对任一上界（下界）的一个上界（下界），则对任一上界（下界）y y，均有，均有a a y y（y y a a），则称），则称a a为为B B的上确界（下确界）。的上确界（下确界）。第五十五页，本课件共有85页【注】：【注】：1)B1)B的上下界若存在，则在的上下界若存在，则在A A中，此与极元、最中，此与极元、最元情况不同。元情况不同。2)2)下确界即最大下界，上确界即最小上界。下确界即最大下界，上确界即最小上界。第五十六页，本课件共有85页小结：小结：（1 1）偏序集的子集）偏序集的子集B B的最大元、最小

40、元、极大元、极的最大元、最小元、极大元、极小元若有则必在小元若有则必在B B中，而中，而B B的上下界不一定在的上下界不一定在B B中。中。（2 2）最大元、最小元不一定存在，极大元、极小元）最大元、最小元不一定存在，极大元、极小元必存在。必存在。（3 3）若有上下界，不一定存在上下确界。）若有上下界，不一定存在上下确界。第五十七页，本课件共有85页定义定义4.26 设R是集合A上的一个关系，如果R是反自反的和传递的，则称R是A上的一个拟序关系。一般用符号“”表示拟序关系。定理定理4.29 设R是集合A上的拟序关系，则R是反对称的。第五十八页，本课件共有85页4.8 偏序关系4.8.2 哈斯图

41、 定义定义4.27 设R是集合A上的偏序关系，如果x，yA，R，xy且在A中不存在z，使得R、R，则称元素y盖住元素x。定理定理4.30 设R是集合A上的关系，则有1）如果R是一个拟序关系，则R的自反闭包r（R）=RIA是一个偏序关系。2）如果R是一个偏序关系，则R-IA是一个拟序关系。第五十九页，本课件共有85页例4.33 设A=a，b，c，R是A幂集上的包含关系，则R是偏序关系，画出R的哈斯图。解 R的哈斯图如图4.15所示所示。第六十页，本课件共有85页4.8 偏序关系4.8.3 全序关系 定义定义4.28 设是偏序集合，B是A的子集，如果B中任意两个元素都是有关系的，则称子集B为链。定

42、义定义4.29 设是偏序集合，B是A的子集，如果B中任意两个元素都是没有关系的，则称子集B为反链。第六十一页，本课件共有85页定定理理4.31 4.31 设是偏序集合，且B是A的子集，若B有最大（最小）元，则必是唯一的。定义定义4.334.33 设是偏序集合，且B是A的子集，如果有某一个元素aA，使得B中任何元素x，都满足xa，则称a为子集B的上界。同理，对于aA，如果任意元素xB，都有ax成立，则称a为子集B的下界。第六十二页，本课件共有85页定义定义4.34 设是偏序集合，且B是A的子集，元素a是集合B的任意上界，如果对于B的所有上界x都有ax，则称a为B的最小上界（上确界），记作LUB（

43、B）。同理，b为集合B的任意下界，若对B的所有下界y都有yb，则称b为子集B的最大下界（下确界），记作GLB（B）。第六十三页，本课件共有85页4.8 偏序关系4.8.4 良序关系 定义定义4.35 设是偏序集合，如果A的每一个非空子集都存在最小元，则这种偏序集称为良序集。定理定理4.32 每个良序集合一定是全序集合。定理定理4.33 每个有限的全序集合一定是良序集合。第六十四页，本课件共有85页4.7 相容关系4.7.1 相容关系 定义定义4.20 设R是集合A上的一个二元关系，如果R是自反的、对称的，则称R是相容关系。定义定义4.21 设R是集合A上的一个相容关系，C是A的子集，如果对于C

44、中任意两个元素x，y，有R，称C是相容关系R产生的相容类。定义定义4.22 设R是集合A上的一个相容关系，不能真包含在任何其它相容类中的相容类，称作最大相容类，记作CR。定理定理4.26 设R是有限集A上的相容关系，C是一个相容类，那么一定存在一个最大相容类CR，使得CCR。第六十五页，本课件共有85页4.7.2 覆盖 定义定义4.23 设A是集合，A1，A2，An都是A的非空子集，令S=A1，A2，An，如果A1A2An=A，则称S为A的覆盖。定义定义4.244.24 设S=A1，A2，An是集合A的覆盖，且对于S中任意元素Ai，不存在S中的其它元素Aj，使得AiAj，则称S为A完全覆盖。第

45、六十六页，本课件共有85页定理定理4.274.27 给定集合A的覆盖A1，A2，An，由它确定的关系R=A1A1A2A2AnAn是A上的相容关系。定理定理4.284.28 集合A上相容关系R与完全覆盖存在一一对应。第六十七页，本课件共有85页例4.27 设A=a，b，c，d，e，f，R为A上的相容关系，其图形表示如图所示。求R的完全覆盖。第六十八页，本课件共有85页例4.27 设A=a，b，c，d，e，f，R为A上的相容关系，其图形表示如图所示。求R的完全覆盖。解 由图可知，R产生的最大相容类为：a，b，f，a，d，e，c，f。所以R确定的完全覆盖S=a，b，f，a，d，e，c，f。第六十九页

46、，本课件共有85页（2）设R，S都是A上的关系，A=1，2，3，4。R=，S=，即S为A上的恒等关系，则RS=SR=R。如图所示：（3）设R是A上的关系，S为A上的空关系，即S=，则RS=SR=。第七十页，本课件共有85页4.4 关系的性质4.4.3 传递性 例4.13 设A=a，b，c，R，S，T是A上的二元关系，其中R=，S=，T=说明R，S，T是否为A上的传递关系。解 根据传递性的定义知，R和T是A上的传递关系，S不是A上的传递关系，因为R，R，但R。第七十一页，本课件共有85页4.4 关系的性质4.4.4 关系性质的判定 1自反性的判定方法 定理定理4.9 设R是A上的二元关系，则R在

47、A上是自反的当且仅当IA R。证明 先证必要性。任取，由于R在A上是自反的，则有IAx，yAx=yR从而证明了IA R。再证充分性。任取xA，有xA IAR因此，R在A上是自反的。第七十二页，本课件共有85页4.4 关系的性质4.4.4 关系性质的判定 1自反性的判定方法R的关系矩阵为：第七十三页，本课件共有85页4.4 关系的性质4.4.4 关系性质的判定 1自反性的判定方法R的关系图为：第七十四页，本课件共有85页4.4 关系的性质4.4.4 关系性质的判定 2反自反性的判定方法 定理定理4.10 设R是A上的二元关系，则R在A上是反自反的当且仅当IAR=。例4.15 设集合A=a，b，c

48、，d，A上的二元关系R=，讨论R的性质，写出R的关系矩阵，画出R的关系图。解 由于，R，即IAR=，所以R是反自反的。第七十五页，本课件共有85页4.4 关系的性质4.4.4 关系性质的判定 2反自反性的判定方法 R的关系矩阵为：第七十六页，本课件共有85页4.4 关系的性质4.4.4 关系性质的判定 2反自反性的判定方法 R的关系图为：第七十七页，本课件共有85页4.4 关系的性质4.4.4 关系性质的判定 3对称性的判定方法定理定理4.114.11 设R是A上的二元关系，则R在A上是对称的当且仅当R=R1。例4.16 设集合A=a，b，c，d，A上的二元关系R=，讨论R的性质，写出R的关系

49、矩阵，画出R的关系图。解 因为R，所以R不是自反的。由于R，即IAR，所以R不是反自反的。R1=，R=R1，由上面的定理可知，关系R是对称的。第七十八页，本课件共有85页4.4 关系的性质4.4.4 关系性质的判定 3对称性的判定方法R的关系矩阵为：第七十九页，本课件共有85页4.4 关系的性质4.4.4 关系性质的判定 3对称性的判定方法R的关系图为：第八十页，本课件共有85页4.4 关系的性质4.4.4 关系性质的判定 4反对称性的判定方法 定理定理4.124.12 设R是A上的二元关系，则R在A上是反对称的当且仅当RR1IA。：例4.17 设集合A=a，b，c，d，A上的二元关系R=，讨

50、论R的性质，写出R的关系矩阵，画出R的关系图。解 因为R，所以R不是自反的。由于R，即IA R，所以R不是反自反的。因为R1=，RR1，所以关系R不是对称的。RR1=IA），由上面的定理可知，R是反对称的。R的关系矩阵为：第八十一页，本课件共有85页4.4 关系的性质4.4.4 关系性质的判定 4反对称性的判定方法 R的关系矩阵为：第八十二页，本课件共有85页4反对称性的判定方法 R的关系图如图4.8所示：第八十三页，本课件共有85页定理定理4.3 设A，B，C，D为四个非空集合，则ABCD的充分必要条件是：AC且BD。定理定理4.134.13 设R是A上的二元关系，则R在A上是传递的当且仅当