《第四章关系优秀课件.ppt》由会员分享，可在线阅读，更多相关《第四章关系优秀课件.ppt（85页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第四章第四章 关系关系第1页，本讲稿共85页一、有序对一、有序对 定定义义 由由两两个个固固定定次次序序的的个个体体x x，y y组组成成的的序序列列称称为为有有序序对对或或序序偶偶，记记为为xy，其其中中x x，y y分分别别称称为为序序偶偶的的第第一一、二二元元素（或称第一、二分量）。素（或称第一、二分量）。第一节第一节 有序对与笛卡尔积有序对与笛卡尔积2 2、=当且仅当当且仅当a=u,b=v.a=u,b=v.注注：1 1、当、当abab时，时，.第2页，本讲稿共85页二、二、笛卡儿积的概念笛卡儿积的概念 1.1.定定义义 给给定定集集合合A A和和B B，称称集集合合xy xAyBxAy
2、B为为A A与与B B的笛卡尔积，简称为卡氏积，记为的笛卡尔积，简称为卡氏积，记为ABAB。注注：a a）设）设 ，故故的子集个数：的子集个数：第3页，本讲稿共85页 b b）推广：称）推广：称为为A A1 1,A,A2 2,.,A,.,An n的笛卡尔积。特别的，记的笛卡尔积。特别的，记为为A A的的n n次幂，且有次幂，且有第4页，本讲稿共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=aAB=a，b
3、cbc，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。第5页，本讲稿共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。第6页，本讲稿共85页2.2.笛卡儿积的性质笛卡儿积的性质 1)1)对任意集合对任意集合A A，有，有AA=，A=A=。2)2)笛卡尔积不满足交换律，即一般的，当笛卡尔积不满足交换律，即一般的，当A A，B B且且A
4、 AB B时，时，AAB BBBA A。3)3)笛卡尔积不满足结合律，即一般的，当笛卡尔积不满足结合律，即一般的，当A,B,CA,B,C时，时，(AAB)B)CC A(BCA(BC)。第7页，本讲稿共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）（BCBC）（
5、4 4）（）（ABAB）C=C=（ACAC）（BCBC）第8页，本讲稿共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 A上的二元关系（或
6、上的二元关系（或A A上的关系）。上的关系）。第二节第二节 二元关系二元关系一、概念一、概念第9页，本讲稿共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上的空关系上的空关系。第10页，本讲稿共85页三、关系的表示三、关系的表示1 1、集合形式、集合形式2 2、关系图形式（关系表示法）、关系图形式（关系表示法）1)1)将将A A，B B中元素称为结点，画为中元素称为结点，画为 ；2)2)
7、若若aRbR，画从，画从a a到到b b的有向弧；的有向弧；3)3)对对A A上的关系上的关系R R，若，若aRaR，画，画a a点的自回路。点的自回路。将涉及到二元关系将涉及到二元关系R R的集合元素及序偶按以上规定画的集合元素及序偶按以上规定画出图，称为出图，称为R R的关系图。的关系图。第11页，本讲稿共85页 注注：1)1)空关系：只有结点。空关系：只有结点。2)2)全关系：全关系：AB:A AB:A的每个结点到的每个结点到B B的任一结点均有有向弧。的任一结点均有有向弧。A A2 2:每个结点均有自回路，且任意两个不同结点均有每个结点均有自回路，且任意两个不同结点均有有向弧。有向弧。
8、3)3)恒等关系恒等关系I IA A：只有每个结点均有自回路。：只有每个结点均有自回路。第12页，本讲稿共85页解解 R R的关系图，如图所示：的关系图，如图所示：例例 A=1,2,3,4 A=1,2,3,4，B=5,6,7B=5,6,7，R=R=，作出，作出R R的关系图。的关系图。第13页，本讲稿共85页解解 A A上的关系图如图所示。上的关系图如图所示。例例 设设A=1A=1，2 2，3 3，44，R=1R=2，22，33，41。画出。画出A A上的关系图。上的关系图。第14页，本讲稿共85页3 3、关系的矩阵表示、关系的矩阵表示 设设A=aA=a1 1,a,a2 2,a,am m,B=
9、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)恒等关系：恒等关系：第15页，本讲稿共85页一、关系的基本运算一、关系的基本运算 例例 设设X=1X=1，2 2，3 3，4 4，55，若若A=xA=yx x与与y y的的差差能能被被2 2整整除除，B=xB=y x x与与y y的的差差为为正正且且能能被被3 3整整除除，求求ABAB，ABAB，A-BA-B，B-AB
10、-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第16页，本讲稿共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第17页，本讲稿共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 注注：A A到到B B上的关系的交并差
11、补运算结果仍为上的关系的交并差补运算结果仍为A A到到B B上的关上的关系。系。第18页，本讲稿共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:复合运算（复合关系）复合运算（复合关系）第19页，本讲稿共85页例例 A=1,2,3,4,B=3,5,7,C=1,2,3,A=1,2,3,4,B=3,5,7,C=1,2,3,R=R=，S=S=，.R
12、RS=2S=2，43。如图所示：如图所示：第20页，本讲稿共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）m m=R=Rnmnm。第21页，本讲稿
13、共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、复合运算与关系矩阵、复合运算与关系矩阵第22页，本讲稿共85页b)b)复合运算关于
14、并满足分配律，即复合运算关于并满足分配律，即(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)=(RT)=(RS)S)T T。第23页，本讲稿共85页
15、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)特殊关系的逆关系说明：特殊关系的逆关系说明：第24页，本讲稿共85页(1)(1)（R R-1-1）-1-1=R=R(2)(R(2)(RS)S)-
16、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、逆运算的性质、逆运算的性质第25页，本讲稿共85页有限集合上关系运算的矩阵形式小结有限集合上关系运算的矩阵形式小结1 1、并运算、并运算定理定理1 1：设：设R,SR,S均为有限集合均为有限集合A A到到B B上的二元关系，则上的二
17、元关系，则其中矩阵加法为常规矩阵加法，元素间的加法为布尔加其中矩阵加法为常规矩阵加法，元素间的加法为布尔加法。法。推论：设推论：设R Ri i(i=1,2,(i=1,2,k),k)均为有限集合均为有限集合A A到到B B上的二元关上的二元关系，则系，则第26页，本讲稿共85页2 2、交运算、交运算定理定理2 2：设：设R,SR,S均为有限集合均为有限集合A A到到B B上的二元关系，则上的二元关系，则其中其中“”为为H H乘法（对应相乘）乘法（对应相乘）,元素间的乘法为布尔乘法。元素间的乘法为布尔乘法。【注】：【注】：1 1、H H乘法一般定义：乘法一般定义：其中元素间的乘法为布尔乘法。其中元
18、素间的乘法为布尔乘法。第27页，本讲稿共85页2 2、H H乘法满足以下性质：乘法满足以下性质：b b）分配律：）分配律：c c）结合律：）结合律：d d）其中其中e e）a a）交换律：）交换律：第28页，本讲稿共85页3 3、补运算、补运算定理定理3 3：设：设R R为有限集合为有限集合A A，B B上的二元关系，则上的二元关系，则其中其中“”为矩阵的余运算：为矩阵的余运算：。4 4、差运算、差运算定理定理4 4：设：设R R，S S都为都为A A到到B B上的二元关系，则上的二元关系，则.第29页，本讲稿共85页5 5、逆运算、逆运算定理定理5 5：设：设R R为有限集合为有限集合A A
19、到到B B上的二元关系，则上的二元关系，则。6 6、复合运算、复合运算定理定理6 6：设：设R R，S S分别为有限集合分别为有限集合A A，B B和和B B，C C上的二元关上的二元关系，则系，则其中其中“”为常规矩阵乘法，元素间的乘法和加法分别为布为常规矩阵乘法，元素间的乘法和加法分别为布尔乘法和布尔加法运算。尔乘法和布尔加法运算。第30页，本讲稿共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的关系图中任意结点均有自回路。的关系图中任意结点均有自回路。第31页，本讲稿共85页定义定义 设设R R是集合是集合A A上的二元关系，如果对于每个上的二元关系，如果对于每个x x A A，都有都有 R R，则称二元关系，则称二元关系R R是反自反的。是反自反的。2 2、反自反性、反自反性【注】【注】R R在在A A上是反自反的上是反自反的 I IA ARR M MR R主对角线元素均为主对角线元素均为0 0。R R的关系图中每个结点
21、都无自回路。的关系图中每个结点都无自回路。第32页，本讲稿共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的关系图中任意不同结点间的有向弧要么成对的关系图中任意不同结点间的有向弧要么成对出现要么没有。出现要么没有。第33页，本讲稿共85页定义定义 设设R R是集合是集合A A上的二元关系，若上的二元关系，若R,
22、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的关系图中不同结点间若有有向弧，则只有一条。的关系图中不同结点间若有有向弧，则只有一条。第34页，本讲稿共85页定义定义 设设R R是集合是集合A A上的二元关系，若上的二元关系，若xy，yRzR，就有，就有xRzR则称二元关系则称二元关系R R在在A A上是传递的。上是传递的。3 3、传递性、
23、传递性例例1 1：设：设A A为集合，为集合，A A上的二元关系为上的二元关系为R R，证明：，证明：2 2、R R是传递的是传递的。1 1、R R是反对称的是反对称的第35页，本讲稿共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的的自自反反的的（对对称称的的、传传递递的的）关关系系R R，都有，都有R R R R。则称关系则称关系R R为为R R的自反（对称、传递）
24、闭包。的自反（对称、传递）闭包。第五节第五节 关系的闭包关系的闭包一、关系闭包的概念一、关系闭包的概念第36页，本讲稿共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.r(R)=R.b)Rb)R是对称的是对称的s(R)=R.s(R)=R.c)Rc)R是传递的是传递的t
25、(R)=R.t(R)=R.第37页，本讲稿共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 st（R R）。）。第38页，本讲稿共85页定理定理 设设R R是集合是集合A A上的二元关系，则上的二元
26、关系，则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、公式法、公式法第39页，本讲稿共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,d)求：求：r(R),s(R),t(R)r(R),s(R),t(R)2 2、关系图法、关系图法1)1)在在R R的
27、关系图中将没有自回路的节点添加自回路，即得的关系图中将没有自回路的节点添加自回路，即得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(R)t(R)的关系图。的关系图。第40页，本讲稿共85页3 3、关系矩阵法、关系矩阵法定理定理 设设R R为有限
28、集合为有限集合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第41页，本讲稿共85页定义定义 设设R R是非空集合是非空集合A A上的二元关系，如果上的二元关系，如果R R是自反的、是自反的、对称的和传递的，则称对称的和传递的，则称R R是集合是集合A A上的等价关系上的等价关系.例例 (1)(1)设设集集合合A=aA=a，b b，c c，dd，R=aR=a，ad，da，dd，bb，bc，cb
29、，c c 第六节第六节 等价关系与划分等价关系与划分一、概念一、概念(2)(2)数学对象的相等数学对象的相等第42页，本讲稿共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)R，则，则(b,c)R(b,c)R第43页，本讲稿共85页定定义义 设设R R是是非非空空集集合合A A上上的的等等价价关
30、关系系，对对于于任任何何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。第44页，本讲稿共85页【注】等价类的性质：设【注】等价类的性质：设R R是非空集合是非空集合A A上的等价关系，上的等价关系，则则(1)(1)对任意对任意aA,aaA,a是是A A的非空子集；的非空子集；(2)(2)对任意对任意a,bA
31、,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第45页，本讲稿共85页定义定义 设设R R是集合是集合A A上的等价关系上的等价关系,等价类集合等价类集合aaR R aAaA称作称作A A关于关于R R的商集，记作的商集，记作A/RA/R。2 2、商集、商集【注】：【注】：1)1)等价定义：设等价定义：设R R是非空集合是非空集合A A上的等价关系，以上的等价关系，以R R的的不交等价类为元素的集合叫做不交等价类为元素的集合叫做A A在在R R下的商集。下的商
32、集。2)A/R2)A/R(A)(A)3)3)设设R,SR,S均为集合均为集合A A上的等价关系，则上的等价关系，则A/R=A/SA/R=A/S当且仅当且仅当当R=SR=S。第46页，本讲稿共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 1AA2 2AAm m=A=A则则称称A=AA=A1 1，A A2 2，A Am m 为为集集合合A A的的一一个个划划分分，而而A A1 1
33、，A A2 2，A Am m称为这个划分的块。称为这个划分的块。3 3、集合的划分、集合的划分第47页，本讲稿共85页1)1)设设R R是非空集合是非空集合A A上的等价关系，上的等价关系，A/R A/R即为即为A A的一个划分。的一个划分。2)2)集合集合A A的一个划分确定的一个划分确定A A上的一个等价关系。上的一个等价关系。【注】：集合【注】：集合A A的划分与其上的等价关系的联系的划分与其上的等价关系的联系第48页，本讲稿共85页定定义义 设设R R是是集集合合A A上上的的关关系系，若若R R是是自自反反的的、反反对对称称的的和和传传递递的的，则则称称R R是是A A上上的的偏偏序
34、序关关系系，记记为为“”。序序偶偶A 称作偏序集。称作偏序集。第七节第七节 偏序关系偏序关系一、概念一、概念1)1)集合的包含关系集合的包含关系2)2)实数间的实数间的“”关系关系3)3)集合集合A A上的恒等关系上的恒等关系I IA A4)Z4)Z+中中元元素素间间的的整整除除关关系系，R=x,yR=x,yZ Z+,x,x整整除除yy第49页，本讲稿共85页二、偏序集的哈斯图二、偏序集的哈斯图偏序关系关系图的一种简化偏序关系关系图的一种简化1 1、由、由R R是自反的，从而去掉是自反的，从而去掉R R关系图中每个结点上的自关系图中每个结点上的自回路；回路；2 2、由、由R R是反对称的，从而
35、若是反对称的，从而若a a到到b b有有向弧，则去掉弧上的方有有向弧，则去掉弧上的方向，将向，将b b画在画在a a的上方；的上方；3 3、由、由R R是传递的，则若是传递的，则若a a到到b b，b b到到c c均有有向弧，则去掉均有有向弧，则去掉a a到到c c的有向弧；的有向弧；完成上述删除过程，即得偏序集的哈斯图。完成上述删除过程，即得偏序集的哈斯图。第50页，本讲稿共85页【注】：对具体偏序集合【注】：对具体偏序集合(A,R)(A,R)，总结画哈斯图的一般步骤：，总结画哈斯图的一般步骤：1)1)将偏序关系将偏序关系R R列举表示成列举表示成R=RR=R1 1IIA A，其中，其中2)
36、2)若若(a,b),(b,c)R(a,b),(b,c)R1 1,则去掉则去掉(a,c)(a,c)，完成所有如此删除过程。，完成所有如此删除过程。3)3)对对R R1 1中剩余元素按规则作图，即得哈斯图。中剩余元素按规则作图，即得哈斯图。第51页，本讲稿共85页三、偏序集上的特殊元素三、偏序集上的特殊元素1 1、极小元，极大元、极小元，极大元定定义义 设设A 是是偏偏序序集集，B B是是A A的的子子集集，对对bBbB，若若不不存存在在xBxB，使使x x b b且且b b x x（x x b b），则则称称b b为为B B的的极极大大元元（极极小元）。小元）。【注】：【注】：1)1)子集子集B
37、 B的极小的极小(大大)元，必须在元，必须在B B中。中。2)2)哈斯图中的孤立点既是极小元，又是极大元。哈斯图中的孤立点既是极小元，又是极大元。第52页，本讲稿共85页（3）对于非空有穷偏序集来说，一定存在极大（小）元，有）对于非空有穷偏序集来说，一定存在极大（小）元，有时甚至是多个，凡是在哈斯图中向上（下）路径的每一个终时甚至是多个，凡是在哈斯图中向上（下）路径的每一个终点都是一个极大（小）元。点都是一个极大（小）元。第53页，本讲稿共85页定定义义 设设A 是是偏偏序序集集，B B是是A A的的子子集集，b b B B，若若B B中中任任何何元元素素x x，都都满满足足x x b b（b
38、 b x x），则则称称b b为为B 的的最最大大元元（最小元）。（最小元）。2 2、最小元，最大元、最小元，最大元【注】：子集的最小元和最大元若存在，则必唯一。【注】：子集的最小元和最大元若存在，则必唯一。第54页，本讲稿共85页3 3、界与确界、界与确界定定义义 设设A 是是偏偏序序集集，B B是是A A的的子子集集，a a A A，若若B B中中任任何何元元素素x x，都都满满足足x x a a（a a x x），则则称称a a为为B 的的上上界界（下下界）。界）。设设a a是是B B的一个上界（下界），则对任一上界（下界）的一个上界（下界），则对任一上界（下界）y y，均有，均有a a
39、 y y（y y a a），则称），则称a a为为B B的上确界（下确界）。的上确界（下确界）。第55页，本讲稿共85页【注】：【注】：1)B1)B的上下界若存在，则在的上下界若存在，则在A A中，此与极元、最元中，此与极元、最元情况不同。情况不同。2)2)下确界即最大下界，上确界即最小上界。下确界即最大下界，上确界即最小上界。第56页，本讲稿共85页小结：小结：（1 1）偏序集的子集）偏序集的子集B B的最大元、最小元、极大元、极的最大元、最小元、极大元、极小元若有则必在小元若有则必在B B中，而中，而B B的上下界不一定在的上下界不一定在B B中。中。（2 2）最大元、最小元不一定存在，极
40、大元、极小元必）最大元、最小元不一定存在，极大元、极小元必存在。存在。（3 3）若有上下界，不一定存在上下确界。）若有上下界，不一定存在上下确界。第57页，本讲稿共85页定义定义4.26 设R是集合A上的一个关系，如果R是反自反的和传递的，则称R是A上的一个拟序关系。一般用符号“”表示拟序关系。定理定理4.29 设R是集合A上的拟序关系，则R是反对称的。第58页，本讲稿共85页4.8 偏序关系4.8.2 哈斯图 定义定义4.27 设R是集合A上的偏序关系，如果x，yA，R，xy且在A中不存在z，使得R、R，则称元素y盖住元素x。定理定理4.30 设R是集合A上的关系，则有1）如果R是一个拟序关
41、系，则R的自反闭包r（R）=RIA是一个偏序关系。2）如果R是一个偏序关系，则R-IA是一个拟序关系。第59页，本讲稿共85页例4.33 设A=a，b，c，R是A幂集上的包含关系，则R是偏序关系，画出R的哈斯图。解 R的哈斯图如图4.15所示所示。第60页，本讲稿共85页4.8 偏序关系4.8.3 全序关系 定义定义4.28 设是偏序集合，B是A的子集，如果B中任意两个元素都是有关系的，则称子集B为链。定义定义4.29 设是偏序集合，B是A的子集，如果B中任意两个元素都是没有关系的，则称子集B为反链。第61页，本讲稿共85页定定理理4.31 4.31 设是偏序集合，且B是A的子集，若B有最大（
42、最小）元，则必是唯一的。定义定义4.334.33 设是偏序集合，且B是A的子集，如果有某一个元素aA，使得B中任何元素x，都满足xa，则称a为子集B的上界。同理，对于aA，如果任意元素xB，都有ax成立，则称a为子集B的下界。第62页，本讲稿共85页定义定义4.34 设是偏序集合，且B是A的子集，元素a是集合B的任意上界，如果对于B的所有上界x都有ax，则称a为B的最小上界（上确界），记作LUB（B）。同理，b为集合B的任意下界，若对B的所有下界y都有yb，则称b为子集B的最大下界（下确界），记作GLB（B）。第63页，本讲稿共85页4.8 偏序关系4.8.4 良序关系 定义定义4.35 设是
43、偏序集合，如果A的每一个非空子集都存在最小元，则这种偏序集称为良序集。定理定理4.32 每个良序集合一定是全序集合。定理定理4.33 每个有限的全序集合一定是良序集合。第64页，本讲稿共85页4.7 相容关系4.7.1 相容关系 定义定义4.20 设R是集合A上的一个二元关系，如果R是自反的、对称的，则称R是相容关系。定义定义4.21 设R是集合A上的一个相容关系，C是A的子集，如果对于C中任意两个元素x，y，有R，称C是相容关系R产生的相容类。定义定义4.22 设R是集合A上的一个相容关系，不能真包含在任何其它相容类中的相容类，称作最大相容类，记作CR。定理定理4.26 设R是有限集A上的相
44、容关系，C是一个相容类，那么一定存在一个最大相容类CR，使得CCR。第65页，本讲稿共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完全覆盖。第66页，本讲稿共85页定理定理4.274.27 给定集合A的覆盖A1，A2，An，由它确定的关系R=A1A1A2A2AnAn是A上的相容关系。定理定理4.284.28 集合A上相容关系R与完全覆盖存在一一对应。第
45、67页，本讲稿共85页例4.27 设A=a，b，c，d，e，f，R为A上的相容关系，其图形表示如图所示。求R的完全覆盖。第68页，本讲稿共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。第69页，本讲稿共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=。第70页，本讲稿共85页4.4
46、关系的性质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。第71页，本讲稿共85页4.4 关系的性质4.4.4 关系性质的判定 1自反性的判定方法 定理定理4.9 设R是A上的二元关系，则R在A上是自反的当且仅当IA R。证明 先证必要性。任取，由于R在A上是自反的，则有IAx，yAx=yR从而证明了IA R。再证充分性。任取xA，有xA IAR因此，R在A上是自反的。第72页，本讲稿共85页4.4 关系的性质4.4.4
47、关系性质的判定 1自反性的判定方法R的关系矩阵为：第73页，本讲稿共85页4.4 关系的性质4.4.4 关系性质的判定 1自反性的判定方法R的关系图为：第74页，本讲稿共85页4.4 关系的性质4.4.4 关系性质的判定 2反自反性的判定方法 定理定理4.10 设R是A上的二元关系，则R在A上是反自反的当且仅当IAR=。例4.15 设集合A=a，b，c，d，A上的二元关系R=，讨论R的性质，写出R的关系矩阵，画出R的关系图。解 由于，R，即IAR=，所以R是反自反的。第75页，本讲稿共85页4.4 关系的性质4.4.4 关系性质的判定 2反自反性的判定方法 R的关系矩阵为：第76页，本讲稿共8
48、5页4.4 关系的性质4.4.4 关系性质的判定 2反自反性的判定方法 R的关系图为：第77页，本讲稿共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的关系矩阵，画出R的关系图。解 因为R，所以R不是自反的。由于R，即IAR，所以R不是反自反的。R1=，R=R1，由上面的定理可知，关系R是对称的。第78页，本讲稿共85页4.4 关系的性质4.4.4 关系性质的判定 3对称性的判定方法R的关系矩阵为：第79页，本
49、讲稿共85页4.4 关系的性质4.4.4 关系性质的判定 3对称性的判定方法R的关系图为：第80页，本讲稿共85页4.4 关系的性质4.4.4 关系性质的判定 4反对称性的判定方法 定理定理4.124.12 设R是A上的二元关系，则R在A上是反对称的当且仅当RR1IA。：例4.17 设集合A=a，b，c，d，A上的二元关系R=，讨论R的性质，写出R的关系矩阵，画出R的关系图。解 因为R，所以R不是自反的。由于R，即IA R，所以R不是反自反的。因为R1=，RR1，所以关系R不是对称的。RR1=IA），由上面的定理可知，R是反对称的。R的关系矩阵为：第81页，本讲稿共85页4.4 关系的性质4.
50、4.4 关系性质的判定 4反对称性的判定方法 R的关系矩阵为：第82页，本讲稿共85页4反对称性的判定方法 R的关系图如图4.8所示：第83页，本讲稿共85页定理定理4.3 设A，B，C，D为四个非空集合，则ABCD的充分必要条件是：AC且BD。定理定理4.134.13 设R是A上的二元关系，则R在A上是传递的当且仅当 RR R。定理定理4.144.14 设集合A=a1，a2，an，R是A上的二元关系，R的关系矩阵为MR，令M=MRMR，则R在A上是传递的当且仅当矩阵M的第i行，第j列元素为1时，MR的第i行，第j列元素必为1。5传递性的判定方法第84页，本讲稿共85页本章小结 本本章章首首先