第四章关系.ppt

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

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

2、与与B B的的笛笛卡卡尔尔积积，简简称称为为卡卡氏氏积，记为积，记为ABAB。注注：a a）设）设 ，故故的子集个数：的子集个数：b b）推广：称）推广：称为为A A1 1,A,A2 2,.,A,.,An n的笛卡尔积。特别的，记的笛卡尔积。特别的，记为为A A的的n n次幂，且有次幂，且有例例 （1 1）A=aA=a，bb，B=cB=c，dd，求求ABAB和和BA BA。(2)A=(2)A=a,b,Ba,b,B=1,2,C=c,=1,2,C=c,求求(AB)C(AB)C和和A(BC)A(BC)。解（解（1 1）AB=aAB=a，bcbc，d=ad=c，ad，bc，bd BA=c BA=c，d

3、ada，b=cb=a，cb，da，db（2 2）AB=aAB=a，b1b1，22=a=1，a2，b1，b2。（ABAB）C=aC=1，cc，a2，cc，b1，cc，b2，cc BC=1BC=1，2c=12c=c，2c。AA（BCBC）=a=a，1c，aa，2c，bb，1c，bb，2c。2.2.笛卡儿积的性质笛卡儿积的性质 1)1)对任意集合对任意集合A A，有，有AA=，A=A=。2)2)笛卡尔积不满足交换律，即一般的，当笛卡尔积不满足交换律，即一般的，当A A，B B且且A AB B时，时，AAB BBBA A。3)3)笛卡尔积不满足结合律，即一般的，当笛卡尔积不满足结合律，即一般的，当A,

4、B,CA,B,C时，时，(AAB)B)CC A(BCA(BC)。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）（4 4）（）（ABAB）C=C=（ACAC）（BCBC）2.2.定义定义 设设S S是是A A到到B B上的二元关系，称上的二元关系，称 x

5、x y(yy(y B Bxy S)S)为为S S的定义域，记作的定义域，记作D(S).D(S).称称 y y x x（xAxAxSyS）为为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上的二元关系（或上的二元关系（或A A上的关系）。上的关系）。第二节第二节 二元关系二元关系一、概念一、概念二、三种特殊关系：二、三种特殊关系：1.A1.A上的关系：上的关

6、系：I IA A=a=a a a A A，称为，称为A A上的恒上的恒等关系。等关系。2.A2.A到到B B上的全关系：上的全关系：AB=aAB=b aAbBaAbB 3.A3.A到到B B上的空关系上的空关系。三、关系的表示三、关系的表示1 1、集合形式、集合形式2 2、关系图形式（关系表示法）、关系图形式（关系表示法）1)1)将将A A，B B中元素称为结点，画为中元素称为结点，画为 ；2)2)若若aRbR，画从，画从a a到到b b的有向弧；的有向弧；3)3)对对A A上的关系上的关系R R，若，若aRaR，画，画a a点的自回路。点的自回路。将涉及到二元关系将涉及到二元关系R R的集合

7、元素及序偶按以上规的集合元素及序偶按以上规定画出图，称为定画出图，称为R R的关系图。的关系图。注注：1)1)空关系：只有结点。空关系：只有结点。2)2)全关系：全关系：AB:AAB:A的每个结点到的每个结点到B B的任一结点均有有向弧。的任一结点均有有向弧。A A2 2:每个结点均有自回路，且任意两个不同结每个结点均有自回路，且任意两个不同结点均有有向弧。点均有有向弧。3)3)恒等关系恒等关系I IA A：只有每个结点均有自回路。：只有每个结点均有自回路。解解 R R的关系图，如图所示：的关系图，如图所示：例例 A=1,2,3,4A=1,2,3,4，B=5,6,7B=5,6,7，R=R=，作

8、出作出R R的关系图。的关系图。解解 A A上的关系图如图所示。上的关系图如图所示。例例 设设A=1A=1，2 2，3 3，44，R=1R=2，22，33，41。画出画出A A上的关系图。上的关系图。3 3、关系的矩阵表示、关系的矩阵表示 设设A=aA=a1 1,a,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)恒等关系：恒等关系：一

9、、关系的基本运算一、关系的基本运算 例例 设设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-A，A A。第三节第三节 关系的运算关系的运算解解 A=1A=1，13，15，22，24，31，33，35，42，44，51，53，55 B B=4=1，52AB=1AB=1，13，15，22，24，31，33，35，41，42，44，51，52，53，55AB=AB=A A-B=1B=1，13，15，22，24，31，3

10、3，35，42，44，51，53，55B-A=4B-A=1，52A=XA=X2 2-A-A =1 =2，14，21，23，25，32，34，41，43，45，52，54 注注：A A到到B B上的关系的交并差补运算结果仍为上的关系的交并差补运算结果仍为A A到到B B上的上的关系。关系。二、关系的特殊运算二、关系的特殊运算 1.1.定义定义 设设R,SR,S分别是集合分别是集合A A到到B,BB,B到到C C上的二元关系，上的二元关系，则则R RS S称为称为R R和和S S的复合关系，表示为的复合关系，表示为R RS=S=xAzCxAzC y(yBy(yBRRS)S)A:A:复合运算（复合关

11、系）复合运算（复合关系）例例 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 RS=2S=2，43。如图所示：如图所示：注注：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次幂定义，可得出下面的结论：次幂定义，可得出下面

12、的结论：（1 1）R Rn+mn+m=R Rn nR Rm m；（2 2）（）（R Rn n）m m=R Rnmnm。定理定理 设设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其中其中为矩阵的乘法，而元素运算为布尔运算。为矩阵的乘法，而元

13、素运算为布尔运算。2 2、复合运算与关系矩阵、复合运算与关系矩阵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,B,B B到到C,CC,C到到D D的关系，则有

14、的关系，则有R R(S(ST)=(RT)=(RS)S)T T。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)特殊关系的逆关系说明：特殊关系的逆关系说明：(1)(1)（R R-1-1）-1-1

15、=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、逆运算的性质、逆运算的性质有限集合上关系运算的矩阵形式小结有限集合上关系运算的矩阵形式小结1 1、并运算、并运算定理定理1 1：设：设R,SR,S均为有限集合均为有限集合A A到到B B上的二元

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

17、尔乘法。2 2、H H乘法满足以下性质：乘法满足以下性质：b b）分配律：）分配律：c c）结合律：）结合律：d d）其中其中e e）a a）交换律：）交换律：3 3、补运算、补运算定理定理3 3：设：设R R为有限集合为有限集合A A，B B上的二元关系，则上的二元关系，则其中其中“”为矩阵的余运算：为矩阵的余运算：。4 4、差运算、差运算定理定理4 4：设：设R R，S S都为都为A A到到B B上的二元关系，则上的二元关系，则.5 5、逆运算、逆运算定理定理5 5：设：设R R为有限集合为有限集合A A到到B B上的二元关系，则上的二元关系，则。6 6、复合运算、复合运算定理定理6 6：

18、设：设R R，S S分别为有限集合分别为有限集合A A，B B和和B B，C C上的二元上的二元关系，则关系，则其中其中“”为常规矩阵乘法，元素间的乘法和加法分为常规矩阵乘法，元素间的乘法和加法分别为布尔乘法和布尔加法运算。别为布尔乘法和布尔加法运算。定定义义 设设R R是是集集合合A A上上的的二二元元关关系系，如如果果对对于于每每个个x x A A，都有都有 R R，则称二元关系则称二元关系R R是自反的。是自反的。第四节第四节 关系的性质关系的性质一、自反性和反自反性一、自反性和反自反性 1 1、自反性、自反性【注注】R R在在A A上是自反的上是自反的 I IA A R RM MR R

19、主对角线元素均为主对角线元素均为1 1。R R的关系图中任意结点均有自回路。的关系图中任意结点均有自回路。定义定义 设设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的关系图中每个结点都无自回路。的关系图中每个结点都无自回路。定定义义 设设R R是是集集合合A A上上的的二二元元关关系系，若若对对任任意意xRyR，就有就有y

20、RxR，则称二元关系则称二元关系R R是对称的。是对称的。二、对称性和反对称性二、对称性和反对称性 1 1、对称性、对称性【注注】R R在在A A上是对称的上是对称的 R R-1-1=R=RM MR RM MR R。R R的关系图中任意不同结点间的有向弧要么的关系图中任意不同结点间的有向弧要么成对出现要么没有。成对出现要么没有。定义定义 设设R R是集合是集合A A上的二元关系，若上的二元关系，若 R,R,则则x=yx=y或或yx R,R,称二元关系称二元关系R R是反对称的。是反对称的。2 2、反对称性、反对称性【注注】R R在在A A上是反对称的上是反对称的 若若 ，RR，则，则x=yx=

21、y。M MR R元素中若元素中若a aijij=1(i=1(ij),j),则则a ajiji=0=0。R R的关系图中不同结点间若有有向弧，则只的关系图中不同结点间若有有向弧，则只有一条。有一条。定义定义 设设R R是集合是集合A A上的二元关系，若上的二元关系，若xy，yRzR，就有就有xRzR则称二元关系则称二元关系R R在在A A上是传递的。上是传递的。3 3、传递性、传递性例例1 1：设：设A A为集合，为集合，A A上的二元关系为上的二元关系为R R，证明：，证明：2 2、R R是传递的是传递的。1 1、R R是反对称的是反对称的1 1、定定义义 设设R R是是集集合合A A上上的的

22、关关系系，若若A A上上的的另另一一关关系系RR满足：满足：（1 1）RR是自反的（对称的、传递的）；是自反的（对称的、传递的）；（2 2）RR R R；（3 3）对对于于A A上上任任何何包包含含R R的的自自反反的的（对对称称的的、传传递递的的）关系关系RR，都有，都有RR RR。则称关系则称关系RR为为R R的自反（对称、传递）闭包。的自反（对称、传递）闭包。第五节第五节 关系的闭包关系的闭包一、关系闭包的概念一、关系闭包的概念【注注】：a.a.闭包闭包RR是包含是包含R R的具有自反（对称，传的具有自反（对称，传递）性质的最小关系。递）性质的最小关系。b.b.记号记号:自反闭包自反闭包

23、r(Rr(R););对称闭包对称闭包s(Rs(R););传递闭包传递闭包t(Rt(R).).2 2、性质、性质1)1)设设R R是是A A上的关系，则上的关系，则a)Ra)R是自反的是自反的r(Rr(R)=R.)=R.b)Rb)R是对称的是对称的s(Rs(R)=R.)=R.c)Rc)R是传递的是传递的t(Rt(R)=R.)=R.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上的

24、关系，则上的关系，则a a）rsrs（R R）=srsr（R R）；）；b b）rtrt（R R）=trtr（R R）；）；c c）tsts（R R）stst（R R）。）。定理定理 设设R R是集合是集合A A上的二元关系，则上的二元关系，则r r（R R）=RI=RIA A，s s（R R）=RR=RR11,t t（R R）=RR=RR2 2RR3 3特别的，若特别的，若A An n，则，则t t（R R）=RR=RR2 2RR3 3R Rn n二、关系闭包的求法二、关系闭包的求法1 1、公式法、公式法例例 设设A=A=a,b,c,d,Aa,b,c,d,A上关系上关系R=(R=(a,a),

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

26、弧，则添均有有向弧，则添加加a a到到c c的有向弧，逐一添加即得的有向弧，逐一添加即得t(Rt(R)的关系图。的关系图。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定义定义 设设R R是非空集合是非空集合A A上的二元关系，如果上的二元关系，如果R R是自反的、是自反的、对称的和传递的，则称对称的和传递的，则称R R是集

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

28、,c)R，则，则(b,c)Rb,c)R定定义义 设设R R是是非非空空集集合合A A上上的的等等价价关关系系，对对于于任任何何aAaA，集集合合aaR R=x=x xAxA且且aRxR称称为为元元素素a a形形成成的的关于关于R R的等价类。的等价类。二、集合的划分二、集合的划分1 1、等价类、等价类例例 A=1A=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。【注注】等价类的性质：设等价类的性质：设R R是非空集合是非空集合A A上的等价关系，上的等价关系，则则(1)(1)对任意对任意aA,aa

29、A,a 是是A A的非空子集；的非空子集；(2)(2)对任意对任意a,bAa,bA,若若(a,b)Ra,b)R,则则a=b;a=b;(3)(3)对任意对任意a,bAa,bA,若若(a,b)Ra,b)R,则则 abab=;(4)(4)a=Aa=A定义定义 设设R R是集合是集合A A上的等价关系上的等价关系,等价类集合等价类集合aaR R aAaA称作称作A A关于关于R R的商集，记作的商集，记作A/RA/R。2 2、商集、商集【注注】：1)1)等价定义：设等价定义：设R R是非空集合是非空集合A A上的等价关系，上的等价关系，以以R R的不交等价类为元素的集合叫做的不交等价类为元素的集合叫做

30、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。定定义义 设设A A是是一一个个集集合合，A A1 1，A A2 2，A Am m是是它它的的非非空空子子集，如果它满足下列条件：集，如果它满足下列条件：（1 1）A Ai iAAj j=，i i j j ，i,ji,j=1,2,m=1,2,m（2 2）A A1 1AA2 2AAm m=A=A则则称称A=AA=A1 1，A A2 2，A Am m 为为集集合合A A的的一一个个划划分分，而而A

31、 A1 1，A A2 2，A Am m称为这个划分的块。称为这个划分的块。3 3、集合的划分、集合的划分1)1)设设R R是是非非空空集集合合A A上上的的等等价价关关系系，A/RA/R即即为为A A的的一一个个划分。划分。2)2)集合集合A A的一个划分确定的一个划分确定A A上的一个等价关系。上的一个等价关系。【注注】：集合：集合A A的划分与其上的等价关系的联系的划分与其上的等价关系的联系定定义义 设设R R是是集集合合A A上上的的关关系系，若若R R是是自自反反的的、反反对对称称的的和和传传递递的的，则则称称R R是是A A上上的的偏偏序序关关系系，记记为为“”。序偶序偶A 称作偏序

32、集。称作偏序集。第七节第七节 偏序关系偏序关系一、概念一、概念1)1)集合的包含关系集合的包含关系2)2)实数间的实数间的“”“”关系关系3)3)集合集合A A上的恒等关系上的恒等关系I IA A4)Z4)Z+中中元元素素间间的的整整除除关关系系，R=R=x,yx,yZ Z+,x,x整整除除yy二、偏序集的哈斯图二、偏序集的哈斯图偏序关系关系图的一种简化偏序关系关系图的一种简化1 1、由、由R R是自反的，从而去掉是自反的，从而去掉R R关系图中每个结点上的关系图中每个结点上的自回路；自回路；2 2、由、由R R是反对称的，从而若是反对称的，从而若a a到到b b有有向弧，则去掉弧有有向弧，则

33、去掉弧上的方向，将上的方向，将b b画在画在a a的上方；的上方；3 3、由、由R R是传递的，则若是传递的，则若a a到到b b，b b到到c c均有有向弧，则去均有有向弧，则去掉掉a a到到c c的有向弧；的有向弧；完成上述删除过程，即得偏序集的哈斯图。完成上述删除过程，即得偏序集的哈斯图。【注注】：对具体偏序集合：对具体偏序集合(A,R)(A,R)，总结画哈斯图的一，总结画哈斯图的一般步骤：般步骤：1)1)将偏序关系将偏序关系R R列举表示成列举表示成R=RR=R1 1IIA A，其中，其中2)2)若若(a,b),(b,c)R(a,b),(b,c)R1 1,则去掉则去掉(a,ca,c)，

34、完成所有如此删，完成所有如此删除过程。除过程。3)3)对对R R1 1中剩余元素按规则作图，即得哈斯图。中剩余元素按规则作图，即得哈斯图。三、偏序集上的特殊元素三、偏序集上的特殊元素1 1、极小元，极大元、极小元，极大元定定义义 设设A 是是偏偏序序集集，B B是是A A的的子子集集，对对bBbB，若若不不存存在在x xB 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)哈斯图中的孤立点既是极小元，又是极大元。哈斯图中的孤立点

35、既是极小元，又是极大元。（3）对于非空有穷偏序集来说，一定存在极大（小）对于非空有穷偏序集来说，一定存在极大（小）元，有时甚至是多个，凡是在哈斯图中向上（下）元，有时甚至是多个，凡是在哈斯图中向上（下）路径的每一个终点都是一个极大（小）元。路径的每一个终点都是一个极大（小）元。定定义义 设设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、最小元，最大元、最小元，最大元【注注】：子集的最小元和最大元若存在，则必唯一。：子集的

36、最小元和最大元若存在，则必唯一。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 y y （y y a a ），则称），则称a a为为B B的上确界（下确的上确界（下确界）。界）。【注注】：1)B1)B的上下界若存在，则在的上下界若存在，则在A A中，此与极元、中，此与极元、最

37、元情况不同。最元情况不同。2)2)下确界即最大下界，上确界即最小上界。下确界即最大下界，上确界即最小上界。小结：小结：（1 1）偏序集的子集）偏序集的子集B B的最大元、最小元、极大元、的最大元、最小元、极大元、极小元若有则必在极小元若有则必在B B中，而中，而B B的上下界不一定在的上下界不一定在B B中。中。（2 2）最大元、最小元不一定存在，极大元、极小）最大元、最小元不一定存在，极大元、极小元必存在。元必存在。（3 3）若有上下界，不一定存在上下确界。）若有上下界，不一定存在上下确界。定义定义4.26 设R是集合A上的一个关系，如果R是反自反的和传递的，则称R是A上的一个拟序关系。一般

38、用符号“”表示拟序关系。定理定理4.29 设R是集合A上的拟序关系，则R是反对称的。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是一个拟序关系，则R的自反闭包r（R）=RIA是一个偏序关系。2）如果R是一个偏序关系，则R-IA是一个拟序关系。例4.33 设A=a，b，c，R是A幂集上的包含关系，则R是偏序关系，画出R的哈斯图。解 R的哈斯图如图4.15所示所示。4.8 偏序关系4.8.3 全序关系 定义定义4.28 设是偏序集合，B

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

40、LUB（B）。同理，b为集合B的任意下界，若对B的所有下界y都有yb，则称b为子集B的最大下界（下确界），记作GLB（B）。4.8 偏序关系4.8.4 良序关系 定义定义4.35 设是偏序集合，如果A的每一个非空子集都存在最小元，则这种偏序集称为良序集。定理定理4.32 每个良序集合一定是全序集合。定理定理4.33 每个有限的全序集合一定是良序集合。4.7 相容关系4.7.1 相容关系 定义定义4.20 设R是集合A上的一个二元关系，如果R是自反的、对称的，则称R是相容关系。定义定义4.21 设R是集合A上的一个相容关系，C是A的子集，如果对于C中任意两个元素x，y，有R，称C是相容关系R产生

41、的相容类。定义定义4.22 设R是集合A上的一个相容关系，不能真包含在任何其它相容类中的相容类，称作最大相容类，记作CR。定理定理4.26 设R是有限集A上的相容关系，C是一个相容类，那么一定存在一个最大相容类CR，使得CCR。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完全覆盖。定理定理4.274.27 给定集合A的覆盖A1，A2，An，由它确定的关系R=

42、A1A1A2A2AnAn是A上的相容关系。定理定理4.284.28 集合A上相容关系R与完全覆盖存在一一对应。例4.27 设A=a，b，c，d，e，f，R为A上的相容关系，其图形表示如图所示。求R的完全覆盖。例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。（2）设R，S都是A上的关系，A=1，2，3，4。R=，S=，即S为A上的恒等关系，则RS=SR=R。如图所示：（3）设R是A上的关系，S为A上的空关系，即S=，则RS=

43、SR=。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。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上是自反的。4.4 关系的性质4.4.4 关系性质的判定 1自反性的判定方

44、法R的关系矩阵为：4.4 关系的性质4.4.4 关系性质的判定 1自反性的判定方法R的关系图为：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是反自反的。4.4 关系的性质4.4.4 关系性质的判定 2反自反性的判定方法 R的关系矩阵为：4.4 关系的性质4.4.4 关系性质的判定 2反自反性的判定方法 R的关系图为：4.4 关系的性质4.4.4 关系性质的判

45、定 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是对称的。4.4 关系的性质4.4.4 关系性质的判定 3对称性的判定方法R的关系矩阵为：4.4 关系的性质4.4.4 关系性质的判定 3对称性的判定方法R的关系图为：4.4 关系的性质4.4.4 关系性质的判定 4反对称性的判定方法 定理定理4.124.12 设R是A上的二元

46、关系，则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的关系矩阵为：4.4 关系的性质4.4.4 关系性质的判定 4反对称性的判定方法 R的关系矩阵为：4反对称性的判定方法 R的关系图如图4.8所示：定理定理4.3 设A，B，C，D为四个非空集合，则ABCD的充分必要条件是：AC且BD。定理定理4.134.13 设R是A上的二元关系，则

47、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传递性的判定方法本章小结 本本章章首首先先给给出出了了笛笛卡卡儿儿积积的的定定义义，在在此此基基础础上上定定义义了了关关系系的的概概念念、给给出出了了关关系系的的表表示示方方法法和和运运算算、同同时时还还说说明明了了关关系系复复合合、闭闭包包、性性质质及及在在关关系系图图、关关系系矩矩阵阵上上的的表表示示。关关系系的的传传递递闭闭包包计计算算较较为为复复杂杂，本本章章给给出出了了求求有有限限集集合合上上的的二二元元关关系系的的传传递递闭闭包包的的有有效效算算法法，即即WarshallWarshall算算法法。在在本本章章中中还还介介绍绍了了两两类类重重要要的关系：等价关系和偏序关系。的关系：等价关系和偏序关系。