四章节二元关系ppt课件

1、1/564.1 4.1 二元关系及其表示法二元关系及其表示法4.1.1 4.1.1 序偶与笛卡尔积序偶与笛卡尔积定义定义4.14.1：由两个元素：由两个元素x x和和y y按一定的次序按一定的次序组成的二元组称为有序对或序偶组成的二元组称为有序对或序偶(Ordered)(Ordered)，记作，记作，其中，其中x x是它是它的第一元素，的第一元素，y y是它的第二元素。是它的第二元素。性质性质4.14.1：(1)(1)： = = 当且当且仅当仅当x=yx=y；(2)(2)： = =当且仅当当且仅当x=u, x=u, y=v;y=v;例如：平面上的坐标例如：平面上的坐标，x, y Rx, y R

2、； 等都是序偶。等都是序偶。2/56定义定义4.24.2：设：设A A，B B是两个集合，称集合是两个集合，称集合 为集合为集合A A与与B B的的笛卡尔积笛卡尔积(Descartes Product)(Descartes Product)。例：设例：设A=1,2A=1,2；B=a, bB=a, b那么那么A A B=B=，；B B A=A=，。性质性质4.24.2：(1). | A (1). | A B |=|A|B |=|A|B|(A, B|B|(A, B为有限集为有限集合合) )； (2). (2). ； (3). (3). 不适宜交换律，即不适宜交换律，即A AB BB BA(A(除非

3、除非A A，B= B= 或或A=B)A=B)； (4). (4). 不适宜结合律，不适宜结合律，(A(AB)B)C AC A(B(BC)(C)(除除非非 ) )； (5). (5). 对对和和运算满足分配律，运算满足分配律，|,ByAxyxBA AA， CBA 3/56证明：证明：(6). (6). ，且当，且当 或或 时，逆命题成立。时，逆命题成立。 A);(CA)(BAC)(BC),(AB)(AC)(BA),(CA)(BAC)(BC),(AB)(AC)(BAA)()(,)(,)(,)()()()(,CABAyxCAyxBAyxCyAxByAxCyByAxCByAxCBAyxDCBADBCA

4、 BA BA4/56定义定义4.34.3：一个有序：一个有序n(n2)n(n2)元组是一个有序对，元组是一个有序对，它的第一个元素为有序的它的第一个元素为有序的n-1n-1元组元组 ，第二个元素为，第二个元素为 ，记为，记为 即：即： ； 当且仅当当且仅当n n维空间中的点维空间中的点M M的坐标的坐标 为有序的为有序的n n元元组组 。定义定义4.44.4：设：设 为为n n个集合个集合(n 2)(n 2)，称集，称集合合 为为n n维卡氏积或维卡氏积或n n阶笛卡尔积，记作阶笛卡尔积，记作 ， 当当 时简记为时简记为 。121,naaanannaaaa,121nnnaaaaaaa,2112

5、1nnbbbaaa,2121nibaii, 2 , 1,),(21nxxxnxxx,21nAAA,21|,221121nnnAxAxAxxxxnAAA21nAAA21nA5/564.1.2 4.1.2 二元关系二元关系定义定义4.54.5：假设集合：假设集合F F中的全体元素为有序的中的全体元素为有序的n(n2)n(n2)元组，那么称元组，那么称F F为为n n元关系，特别地，当元关系，特别地，当n=2n=2时，称时，称F F为二元关系，简称关系。为二元关系，简称关系。对于二元关系对于二元关系F F，假设，假设 ，常记作，常记作 ，反，反之之 ；规定；规定 为为n n元空关系，也是二元空关系，

6、简元空关系，也是二元空关系，简称空关系。称空关系。定义定义4.64.6：设：设A A，B B为两集合，为两集合，A AB B的集合子集的集合子集R R称为称为A A到到B B的二元关系，特别地，当的二元关系，特别地，当A=BA=B时，称时，称R R为为A A上的上的二元关系。二元关系。例：例：A=a, bA=a, b，B=cB=c，那么，那么A AB B的子集有的子集有 ，, , ，Fyx ,xFyyFx 6/56A A到到B B上的全部二元关系；而上的全部二元关系；而 ，为为B B上的二上的二元关系。元关系。普通来说，假设普通来说，假设|A|=m|A|=m，|B|=n|B|=n，A A到到B

7、 B上的二元关系共上的二元关系共有有 个，个，A A上的共有上的共有 个二元关系；个二元关系；特殊的二元关系：特殊的二元关系： (1). (1). 空关系；空关系； (2). (2). 全域关系：全域关系： ； (3). (3). 恒等关系：恒等关系： 。 mn222mAAAyAxyxEA|,|,AxxxIA7/56定义定义4.74.7：设：设R R为二元关系，那么为二元关系，那么 (1). (1). 为为R R的定义域；的定义域； (2). (2). 为为R R的值域；的值域； (3). (3). 为为R R的域。的域。普通地，假设普通地，假设R R是是A A到到B B上的二元关系，那么有上

8、的二元关系，那么有 。 例例4-14-1：设：设A=1,2,3,4,5,6A=1,2,3,4,5,6，B=a, b, c, dB=a, b, c, d，那么那么R=R=，6, c，那么，那么domR=2,3,4,6domR=2,3,4,6，ranR=a, b, cranR=a, b, c。)(|xRyyxdomR)(|xRyxyranRranRdomRfldRBranRAdomR,8/564.1.2 4.1.2 关系的表示关系的表示1. 1. 集合表示法集合表示法 由于关系也是一种特殊的集合，所以可以用集合由于关系也是一种特殊的集合，所以可以用集合的两种根本的表示方法的两种根本的表示方法( (

9、枚举法，描画法枚举法，描画法) )来表示来表示关系；如：设关系；如：设A=2A=2，B=3B=3，那么，那么A A到到B B上的有关上的有关系系R=R=；集合；集合N N上的上的“小于等于关系：小于等于关系：R=|(x, y) N(x y) R=|(x, y) N(x y) 。2. 2. 关系图法关系图法定义定义4.84.8：设集合：设集合A= A= 到到B= B= 上的二元关系上的二元关系R R，以集合，以集合A A，B B中的元素为顶点，在中的元素为顶点，在图中用图中用“表示顶点，假设表示顶点，假设 那么可自顶点那么可自顶点 向顶点向顶点 引有向边引有向边 ，其箭头指向，其箭头指向 ，用这

10、，用这种方法画出的图称为关系图种方法画出的图称为关系图(Graph of Relation)(Graph of Relation)。nxxx,21nyyy,21jiRyxixjy),(jiyxjy9/56例例4-24-2：求集合：求集合A=1,2,3,4A=1,2,3,4的恒等关系，空关系，的恒等关系，空关系，全关系和小于关系的关系图。全关系和小于关系的关系图。3. 3. 关系矩阵关系矩阵定义定义4.94.9：设：设 ，那么，那么R R的关系矩阵的关系矩阵 为一为一m mn n矩阵，它的第矩阵，它的第i i，j j分量分量 只取只取0 0或或1 1，且，且,2121nmbbbBaaaABARR

11、MijrjijiijbRaRbar当且仅当当且仅当0110/561.1.关系的交，并，补，差运算关系的交，并，补，差运算定义定义4.104.10：设：设R R和和S S为为A A到到B B的二元关系，其并，交的二元关系，其并，交，补，差运算定义如下：，补，差运算定义如下：例例4-34-3：设：设A=1,2,3,4A=1,2,3,4，假设，假设R=|(x-y)/2R=|(x-y)/2是整数，是整数，x, y Ax, y A，S=|(x-y)/3S=|(x-y)/3是正整数是正整数，x, y Ax, y A，求，求RSRS，RSRS，S-RS-R，RR，R SR S。解：解：R=R=，|,|,|,

12、|,xRyyxRxSyxRyyxSRxSyxRyyxSRxSyxRyyxSR11/56S=S=， RS= RS=，；RS= RS= ； S-R= S= S-R= S=；R= AR= AA-R=A-R=，；R S=(RS)-(RS)= RS.R S=(RS)-(RS)= RS.关系的补运算是对全关系而言的；关系的补运算是对全关系而言的；关系的并，交，差，补的矩阵可用如下方法求取：关系的并，交，差，补的矩阵可用如下方法求取： SSSRSRSRSRSRSRSRMMMMMMMMMMMM,12/562.2.关系的逆运算关系的逆运算由于关系是序偶的集合，除了集合的普通运算外由于关系是序偶的集合，除了集合的

13、普通运算外，还有一些特有的运算。，还有一些特有的运算。定义定义4.114.11：设：设R R是是A A到到B B的关系，的关系，R R的逆关系或逆是的逆关系或逆是B B到到A A的关系，记为的关系，记为 ，定义为：，定义为：显然对恣意显然对恣意 ，有，有 ； 为为R R的关系矩阵，那么的关系矩阵，那么 . .例：例： ；A=a, b, c, dA=a, b, c, d，B=1,2,3B=1,2,3，R=R=，c, 2， = =，。1R|,1xRyxyRByAx ,xyRxRy1RMRRMM1 11,AAII1R13/56定理定理4.14.1：设：设R R和和S S都是都是A A到到B B上的二

14、元关系，那么上的二元关系，那么.)( ,).6(;,).5(;).(4(;)( ,)( ,).(3(;).(2(;).(1 (1111111111111111111ABBAdomRranRranRdomRSRSRSRSRSRSRSRSRRRRR 14/563.3.关系的复合运算关系的复合运算定义定义4.124.12：设：设R R，S S为二元关系，那么为二元关系，那么R R与与S S的复合的复合关系关系 定义为：定义为： ，其，其中中“ “ 为复合运算，为复合运算， 也记为也记为 。例：设例：设R R表示父子关系，那么表示父子关系，那么 表示祖孙关系表示祖孙关系。例例4-44-4：设集合：设集

15、合A=0,1,2,3,4A=0,1,2,3,4，R R，S S均为均为A A上的二上的二元关系，且元关系，且R=|x+y=4=R=|x+y=4=，S= =|y-S= =|y-x=1=x=1=，；求；求普通地，普通地，SR)(|,tSyxRttyxSRRR2R2RR)(SRR,S)(R,SSRRRSSRRSSR15/56定理定理4.24.2：设：设F F，G G，H H为恣意二元关系，那么为恣意二元关系，那么定理定理4.34.3：设：设R R为为A A上的关系，那么上的关系，那么定理定理4.44.4：设：设F F，G G，H H为恣意二元关系，那么为恣意二元关系，那么111).(2(),().(

16、1 (FGGFHGFHGF RRRIIRAA).2( ,).1 (.).(4(,)().3(,).(2(,)().1 (FHFGFHGHFGFHGFFHFGFHGHFGFHGF16/564.4.关系的幂运算关系的幂运算定义定义4.134.13：设：设R R是集合是集合A A上的二元关系，那么上的二元关系，那么R R的的n n次幂次幂 定义为：定义为：例例4-54-5：设：设A=0,1,2,3,4A=0,1,2,3,4，R=R=，。那么那么 = =，； = =，； = =，=nRRRRAxxxIRnnA10).2(,|,).1 (2R3R4R2R17/56定理定理4.54.5：设：设R R为为A

17、 A上的二元关系，上的二元关系，m m，n n为自然数，为自然数，那么那么证证(4)(4)：假设：假设n=0n=0时，那么有时，那么有 假设假设n=kn=k时，有时，有 ，那么，那么n=k+1n=k+1时时，有，有 命题成立。命题成立。定理定理4.64.6：设集合：设集合A A的基数为的基数为n n，R R是是A A上的二元关系上的二元关系，那么存在自然数，那么存在自然数i i，j j使得使得证明：我们知道，当证明：我们知道，当|A|=n|A|=n时，时，A A上的二元关系合上的二元关系合计计 个，令个，令k= k= ，因此在，因此在 这这k+1k+1个关个关11).1 (mnmnnnRRRR

18、RRR.)().(4( ,).(3( ,).2(11nnmnnmnmnmRRRRRRR AAnAIIRIR1101)()( ,)(11)()(kkRR111111111)()()()()()(kkkkkRRRRRRRR)20(2njijiRR22n22n1210,kRRRR18/56系中，至少有两个是一样的系中，至少有两个是一样的( (鸽巢原理鸽巢原理) )，即有，即有定理定理4.74.7：设：设A A是有限集合，且是有限集合，且|A|=n|A|=n，R R是是A A上的二上的二元关系，那么元关系，那么证明：显然证明：显然 ，下面证：，下面证： 。而而 ，为此，只需证明对恣意的，为此，只需证明

19、对恣意的knkn，有，有 即可。对恣意的即可。对恣意的 ，那么由，那么由“的定义知：存在的定义知：存在 ，使得：，使得：.),20(,2jinRRjiji使iniiiRR11 iiiniRR11iniiiRR11 iniiniiiRRR111inikRR1 kRba ,Aaaak121,),(,012110baaaRaaRaaRaakkk令19/56由于由于|A|=n|A|=n，所以由鸽巢原理；，所以由鸽巢原理；k+1k+1个元素个元素 中至少有两个元素一样，无妨设为中至少有两个元素一样，无妨设为 ，那，那么可么可在在 中删去中删去 后仍有后仍有由关系的复合运算得：由关系的复合运算得： ，其中

20、，其中 ，此时：假设，此时：假设 ，那么，那么 ；假设；假设 ，那么反复上述做法，最终总能找到，那么反复上述做法，最终总能找到 ，使，使得得 ，即有，即有 ，由此，由此有有 ，由，由k k的恣意性的恣意性 ， kaa,0)(jiaajiRaaRaaRaakk,12110RaaRaaRaajjiiii,1211RaaRaaRaaRaaRaakkjjii,1112110,0kkRaaba)(ijkknk iniRba1,nk nk kkRaaba ,0iniRba1,inikRR1 iniiiRR11 iniiiRR11 20/565 5：集合在关系下的像：集合在关系下的像定义定义4.144.14

21、：设：设R R为二元关系，为二元关系，A A是集合是集合(1)(1)：R R在在A A上的限制上的限制 定义为：定义为： (2)(2)：A A在在R R下的像下的像RARA定义为定义为RA=ran( )RA=ran( )。例：例：R=R=，那么，那么： Ra= Ra=，；Ra= ;Ra= ; Ra, a=R Ra, a=R； Ra=b,aRa=b,a；Ra,a=b,a,a,aRa,a=b,a,a,a；|,AxxRyyxARARAR,1aaaR;11aaRaR 21/56定理定理4.84.8：设：设F F为关系，为关系，A A，B B为集合，那么为集合，那么例例4-64-6：设：设 ，A=0,1

22、,2A=0,1,2，B=0,-1,-2B=0,-1,-2。(1)(1)求求RABRAB和和RARBRARB；(2)(2)求求RA-RBRA-RB和和RA-BRA-B。解解(1)(1)： RAB=R0=0 RAB=R0=0； RARB RARB =0,1,20,1,2 =0,1,2=0,1,20,1,2 =0,1,2； (2) (2)： RA-RB =0,1,2- 0,1,2= RA-RB =0,1,2- 0,1,2= ； RA-B=R1,2=1,2 RA-B=R1,2=1,2,)().4( ,)().3(,)().2( ,)().1 (BFAFBAFBFAFBAFBFAFBAFBFAFBAF|

23、,|,xyZyxyxR 22/56我们在研讨关系的性质时，可以假定关系是某一非我们在研讨关系的性质时，可以假定关系是某一非空集合上的二元关系，这一假设不失普通性。因空集合上的二元关系，这一假设不失普通性。因此任一此任一A A到到B B上的关系上的关系R R，即，即 ，而，而 ，所以关系，所以关系R R总可以看成是总可以看成是AB AB 上的关系，它与原关系上的关系，它与原关系R R具有完全一样的序具有完全一样的序偶，对它的讨论替代对偶，对它的讨论替代对R R的讨论无损于问题的本质的讨论无损于问题的本质1.1.关系的性质关系的性质定义定义4.154.15：设：设R R是是A A上的二元关系，即上

24、的二元关系，即 ，那，那么么(1)(1)假设假设 ，那么称，那么称R R是自反的是自反的(Reflexive)(Reflexive)；(2)(2)假设假设 ，那么称，那么称R R是反自反是反自反的的(Irreflexive)(Irreflexive)；BAR)()(BABABAAAR),(RxxAxx),(RxxAxx23/56(3)(3)假设假设 ，那么称，那么称R R是对是对称的称的(Symmetric)(Symmetric)(4)(4)假设假设 ，那么称，那么称R R是反对称的是反对称的(Antisymmetric)(Antisymmetric)(5)(5)假设假设 ，那么，那么称称R

25、R是传送的是传送的(Transitive)(Transitive)例例4-74-7：设：设A=a, b, c, dA=a, b, c, d(1):R=(1):R=，c, c，是自反的；是自反的；S=S=，是反自反的；是反自反的；T=,c, T=,c,既不是自反的也不是反自反的；既不是自反的也不是反自反的；),(yRxxRyAyxyx),(yxyRxxRyAyxyx),(xRzyRzxRyAzyxzyx24/56在关系图上：关系在关系图上：关系R R是自反的，当且仅当其关系图是自反的，当且仅当其关系图中的每个节点都有环，关系中的每个节点都有环，关系R R是反自反的，当且仅是反自反的，当且仅当其关

26、系图中的每个节点上都无环；当其关系图中的每个节点上都无环；在关系矩阵上：关系在关系矩阵上：关系R R是自反的，当且仅当其关系是自反的，当且仅当其关系矩阵的主对角线上全为矩阵的主对角线上全为1 1，关系，关系R R是反自反的，当是反自反的，当且仅当其关系矩阵的主对角线上全为且仅当其关系矩阵的主对角线上全为0 0。例例4-84-8：设：设A=a, b, cA=a, b, c称的。既是对称的，也是反对反对称的；既不是对称的，也不是是反对称的；是对称的；,)4(,)3(,)2(,) 1 (4321ccaaRaccabaaaRcaaaRaccaaaR25/56关系图上：关系关系图上：关系R R是对称的当

27、且仅当其关系图中，是对称的当且仅当其关系图中，任何一对节点之间，要么有方向相反的两条边，任何一对节点之间，要么有方向相反的两条边，要么无任何边；关系要么无任何边；关系R R是反对称的当且仅当其关系是反对称的当且仅当其关系图中，任何一对节点之间，至多有一条边；图中，任何一对节点之间，至多有一条边；关系矩阵上：关系关系矩阵上：关系R R是对称的当且仅当其关系矩阵是对称的当且仅当其关系矩阵是对称矩阵；关系是对称矩阵；关系R R是反对称的当且仅当其关系矩是反对称的当且仅当其关系矩阵为反对称矩阵。阵为反对称矩阵。例例4-94-9：设：设A=a, b, c, dA=a, b, c, d不是传递的。不是传递

28、的；是传递的；是传递的；,)4(,)3(,)2(,) 1 (4321dccacbbaRcbbaaaRbaRcacbbaaaR26/56关系图上：关系关系图上：关系R R是传送的当且仅当其关系图中，是传送的当且仅当其关系图中，任何三个节点任何三个节点x, y, z(x, y, z(可一样可一样) )之间，假设从之间，假设从x x到到y y，y y到到z z均有一条边，那么从均有一条边，那么从x x到到z z一定有一条边存一定有一条边存在；在；关系矩阵上：关系关系矩阵上：关系R R是传送当且仅当其关系矩阵中是传送当且仅当其关系矩阵中，对恣意，对恣意2.2.利用集合运算来判别关系的性质利用集合运算来

29、判别关系的性质定理定理4.94.9：设：设R R是集合是集合A A上的二元关系，那么上的二元关系，那么。则必有若1, 1, 1, 1 ,ikjkijrrrnkji.)5(;)4(;)3(;)2(;) 1 (11RRRRIRRRRRRIRRRIRAAA 传递的是反对称的是对称的是反自反的是自反的27/563.3.关系性质的保守性关系性质的保守性定理定理4.104.10：设：设R R，S S是是A A上的二元关系，那么上的二元关系，那么例例4-104-10：设：设R=R=， S=S=，是定义在是定义在A=a, b, A=a, b, cc上的两个二元关系。上的两个二元关系。传递。传递反对称；反对称对

30、称；对称反自反；反自反自反；自反SRRSRSRSRRSRSRSRSRRSRSRSRSRRSRSRSRSRRSR,)5(,)4(,) 3(,)2(,) 1 (1111128/56显然显然R R，S S是反自反的，反对称的，传送的，那么是反自反的，反对称的，传送的，那么 也是反自反的，反对称的，传送也是反自反的，反对称的，传送的；的； 也具备上述的一切性质；也具备上述的一切性质；(3)RS=, ,c, (3)RS=, ,b,仅是对称的和反自反的；仅是对称的和反自反的； 那么是传送那么是传送的和对称的。的和对称的。111,).1 (SRSR SR)2(,)4(abbabbaaSR29/56关系的限制

31、于扩展：对于任何一个具备某种性质关系的限制于扩展：对于任何一个具备某种性质( (如如自反、对称、传送自反、对称、传送) )的关系来说，在实际研讨与运的关系来说，在实际研讨与运用上都非常重要，但遗憾的是，许多我们要研讨用上都非常重要，但遗憾的是，许多我们要研讨的关系并不具有我们所希望的良好性质。因此，的关系并不具有我们所希望的良好性质。因此，我们往往要在给定的关系中删去一些或添加一些我们往往要在给定的关系中删去一些或添加一些元素，以改动原有关系的性质，即所谓的关系的元素，以改动原有关系的性质，即所谓的关系的限制与扩展。限制与扩展。关系的闭包那么是关系的扩展。关系的闭包那么是关系的扩展。定义定义4

32、.164.16：设：设R R是定义在是定义在A A上的二元关系，假设存在上的二元关系，假设存在满足：满足：(1) (1) 是自反的是自反的( (对称的或传送的对称的或传送的) )；(2).(2). ；(3)(3)对对R R的任何扩展的任何扩展 是自反的是自反的( (对称的对称的或传送的或传送的) )，那么，那么 。普通将。普通将R R的自反、对称的自反、对称、传送闭包记作、传送闭包记作r(R)r(R)，s(R)s(R)，t(R)t(R)。RRRRR RR 30/56例：定义在例：定义在N N上的上的“ 关系的自反闭包关系的自反闭包r(R)r(R)为为“，对称闭包对称闭包s(R)s(R)为为“，

33、传送闭包，传送闭包t(R)t(R)为为“ ；定义在定义在N N上的上的“= =关系的自反闭包关系的自反闭包r(R)r(R)为为“= =，对称闭，对称闭包包s(R)s(R)为为“= =，传送闭包，传送闭包t(R)t(R)为为“= =。例例4-114-11：设集合：设集合A=a, b, cA=a, b, c，R=R=，是定义在是定义在A A上的二元关系，求上的二元关系，求r(R)r(R)，s(R)s(R)，t(R)t(R)并画出并画出R R，r(R)r(R)，s(R)s(R)，t(R)t(R)的关系图，关系矩的关系图，关系矩阵。阵。解：解： r(R)=,; r(R)=,;s(R)=,;s(R)=,

34、;t(R)=,;t(R)=,;31/56利用关系图，关系矩阵求闭包的方法：利用关系图，关系矩阵求闭包的方法：(1).(1).求一个关系的自反闭包，即将图中一切的无求一个关系的自反闭包，即将图中一切的无环节点加上环，矩阵中的对角线上的值全定义为环节点加上环，矩阵中的对角线上的值全定义为1 1；(2).(2).求一个关系的对称闭包，那么在图中，任何求一个关系的对称闭包，那么在图中，任何一对节点之间，假设仅存在一条边，那么加一条一对节点之间，假设仅存在一条边，那么加一条反方向的边；矩阵中那么为：假设反方向的边；矩阵中那么为：假设 ，那，那么令么令 ，即，即 ；(3).(3).求一个关系的传送闭包，那

35、么在图中，对恣求一个关系的传送闭包，那么在图中，对恣意节点意节点a a，b b，c c，假设，假设a a到到b b有一条边，同时有一条边，同时b b到到c c也也有一条边，那么从有一条边，那么从a a到到c c必添加一条边必添加一条边( (当当a a到到c c无边无边时时) )，在矩阵中，假设，在矩阵中，假设 。)( 1jirij) 1( 1jijirr若1)(RRRsMMM）（若则令111, 1ikikjkijrrrr32/56定理定理4.114.11：设：设R R是是A A上的二元关系，那么上的二元关系，那么定理定理4.124.12：设：设R R是集合是集合A A上的关系，那么上的关系，那

36、么定理定理4.144.14：设：设R R是集合是集合A A上的关系，那么上的关系，那么iniiiARRtnARRtRRRsIRRRRr1110)(|,)(: )3(,)(: )2( ,)(: ) 1 (则若.)(: )3(,)(: )2(,)(: ) 1 (RRtRRRsRRRrR是传递的是对称的是自反的.)(: ) 3(,)(),(: )2(,)(),(: ) 1 (传递传递对称对称自反自反RrRRtRrRRtRsR33/56定义定义4.174.17：(1)(1)集合集合A A上的关系上的关系R R的自反对称闭包定的自反对称闭包定义为义为rs(R)=r(s(R); (2)rs(R)=r(s(

37、R); (2)集合集合A A上的关系上的关系R R的自反的自反传送闭包定义为传送闭包定义为rt(R)=r(t(R); (3)rt(R)=r(t(R); (3)集合集合A A上的关上的关系系R R的对称传送闭包定义为的对称传送闭包定义为st(R)=s(t(R);st(R)=s(t(R);类似的类似的，可有，可有sr(R)sr(R)，tr(R)tr(R)，ts(R)ts(R)。定理定理4.154.15：设：设R R是集合是集合A A上的关系，那么上的关系，那么)()().3(),()().2(),()().1 (RtsRstRtrRrtRsrRrs34/564.5.14.5.1：集合和划分：集合和

38、划分定义定义4.184.18：设：设A A是一个非空集合，是一个非空集合， 是是A A的恣意的恣意n n个非空子集，假设个非空子集，假设 满足：满足： 那么称集合那么称集合 为集合为集合A A的一个划的一个划分分(Partition)(Partition)，而，而 叫做这个划分的块叫做这个划分的块或类。或类。例如：例如：(1) (1) 构成集合构成集合U U的一个划分；的一个划分；(2) (2) 构成了构成了U U上的一个划上的一个划分。分。nAAA,21nAAA,21AAnjijiAAiniji 1).2( ;, 1,).1 (,)(21nAAAAnAAA,21,AA,21212121AAA

39、AAAAA35/564.5.24.5.2：等价关系：等价关系定义定义4.194.19：设：设R R为非空集合为非空集合A A上的关系，假设上的关系，假设R R是自是自反的，对称的，传送的，那么称反的，对称的，传送的，那么称R R为为A A上的等价关上的等价关系系(Equivalent Relation)(Equivalent Relation)。假设。假设 ，称，称x x等价于等价于y,y,记作记作xyxy。例：例：(1)(1)一群人，同姓，同年龄，同性别都是等价一群人，同姓，同年龄，同性别都是等价关系，朋友，同窗关系不是等价关系：不传送；关系，朋友，同窗关系不是等价关系：不传送；(2) (2

40、) 都是都是A A上的等价关系；上的等价关系；(3)(3)三角形三角形“类似，类似，“全等都是等价关系；全等都是等价关系；(4)(4)幂集上定义的幂集上定义的 关系，整数集上定义的关系，整数集上定义的不是不是等价关系，不对称。等价关系，不对称。Ryx ,AAIA,36/56例例4-124-12：设：设m m为正整数，整数集合上的关系为正整数，整数集合上的关系 证明关系证明关系R R是等价关系。是等价关系。 证：证：(1)(1)对恣意对恣意 ，有，有 R R自反；自反； (2)(2)对恣意对恣意 ，假设，假设 , ,那么那么 ，即，即R R对称；对称；(3)(3)对恣意对恣意 ，假设，假设 ，即

41、即 ，而，而 ，R R传传送送RR是是Z Z上的等价关系。上的等价关系。 )(mod,|,myxZyxyxRZxRxxmxx,)(modZyx,)(mod,myxRyx即Rxymxy,modZzyx,RzyRyx,zymyxmmzymyx|,|),(mod),(modRzxzxmzyyxzx,|),()(37/56调查关系调查关系R R和集合和集合Z Z；R R将将Z Z分成了如下分成了如下m m个子集：个子集：这这m m个子集特点是：同一个子集中的元素之间都有关个子集特点是：同一个子集中的元素之间都有关系系R R，不同子集的元素之间无关系，不同子集的元素之间无关系R R，每两个子集，每两个子

42、集无公共元素，而一切子集的并正好为无公共元素，而一切子集的并正好为Z Z，构成了，构成了Z Z的一个划分。的一个划分。14 , 13 , 12 , 1, 1, 1, 12, 23 , 22 , 2, 2 , 2, 22, 23, 13 , 12 , 1, 1 , 1, 12, 13,3 ,2 , 0 ,2,3,mmmmmmmmmmmmmmmmmmmmmmmm38/564.5.34.5.3：等价类与商集：等价类与商集定义定义4.204.20：设：设R R是非空集合是非空集合A A上的等价关系，对恣上的等价关系，对恣意意 ，称集合，称集合 为为x x关于关于R R的等的等价类价类(Equivale

43、nce Class)(Equivalence Class)，其中，其中x x称为称为 的生成的生成元，由于元，由于 中的任何两个元素中的任何两个元素a a，b b均相互等价，均相互等价，普通记作普通记作abab。例例4-134-13：设：设A=1,2,3,4,5,8A=1,2,3,4,5,8，思索，思索R R是是A A上的以上的以3 3为模的同余关系，求其等价类。为模的同余关系，求其等价类。解：从例解：从例4-124-12知，知，R R是一个等价关系，那么是一个等价关系，那么Ax|xRyAyyxRRxRxRR44 , 1 1 33 ,858 , 5 , 22RRRR39/56定理定理4.114

44、.11：设：设R R为非空集合为非空集合A A上的等价关系，那么上的等价关系，那么证：证：(1) (1) ，R R是等价关系，那么是等价关系，那么R R自反，因此自反，因此即即(2)(2).).4(;,).3(;,).2(; ,).1 (AxyxyRxAyxyxxRyAyxxAxRAxRRRRR 则则AxRxx , RRxxxRxzRzxxzz,RRRRyxyzxzRzyRyzRyxRxz,40/56同理：同理：(3)(3)假设假设 ，那么存在，那么存在 ，即：即：定义定义4.214.21：设：设R R是集合是集合A A上的等价关系，由上的等价关系，由R R确定的确定的一切等价类的集合，称为集

45、合一切等价类的集合，称为集合A A上关于上关于R R的商集的商集(Quotient Set)(Quotient Set)，记为，记为A/RA/R，即，即RRRRyxxy RRyxRRyzxz矛盾与yRxRyxRzyRzx,AxxAxxAxxxxxxRxxAxxAxAxAxxRAxRAxRAxRAxRRAxR, ,)4(即|/AxxRAR41/56定理定理4.124.12：设：设R R是非空集合是非空集合A A上的等价关系，那么上的等价关系，那么A A上的关于上的关于R R的商集的商集A/RA/R是是A A的一个划分，称之为由的一个划分，称之为由R R导出的等价划分。导出的等价划分。证：由定理证

46、：由定理4.114.11知，命题成立。知，命题成立。定理定理4.134.13：设：设(A)(A)是非空集合是非空集合A A的一个划分，那的一个划分，那么么A A上的关系上的关系 是是A A上的等价关系，称之为由上的等价关系，称之为由(A)(A)所导出的等价所导出的等价关系。关系。证明：证明：(1) (1) 为为A A的一个划分，的一个划分， 使得使得 ，即，即x x和和x x同属于同属于(A)(A)的一个划分块，的一个划分块， RR是自反的；是自反的；)(,|,的一个划分块同属于AyxAyxyxR)(,AAx)(AAiiAx42/56(2) (2) ，那么，那么x x和和y y同属于同属于(A

47、)(A)的的一个划分块，即一个划分块，即y y和和x x同属于一个划分块，同属于一个划分块， ，R R是对称的；是对称的；(3) (3) ，那么，那么x x，y y同同属于属于(A)(A)的一个划分块的一个划分块 ，y y，z z同属于同属于(A)(A)的的一个划分块一个划分块 ， ，而由于不同划分块的，而由于不同划分块的交集为空，交集为空， ，即，即x x和和z z属于同一划分块，属于同一划分块， RR是传送的；是传送的；RR为等价关系。为等价关系。假设设假设设 ，那么，那么RyxAyx,若Rxy,RzyRyxAzyx,若iAjAjiAAyjiAA ,)(21mAAAA212211)()()

48、(imimmAAAAAAAR43/56有定理有定理4.12,4.134.12,4.13知，集合知，集合A A上的等价关系与集合上的等价关系与集合A A的划分是一一对应的，因此可以说：划分与等价的划分是一一对应的，因此可以说：划分与等价关系这两个不同的概念本质上是一样的，即是同关系这两个不同的概念本质上是一样的，即是同一个概念的两种不同的表达方式。一个概念的两种不同的表达方式。例例4-144-14：设：设A=1,2,3A=1,2,3，求，求A A上的一切等价关系。上的一切等价关系。解：先求解：先求A A的划分：只需一个划分块的划分为的划分：只需一个划分块的划分为1,2,31,2,3；具有；具有2

49、 2个划分块的划分为个划分块的划分为 1 1，2,32,3， 2 2，1,31,3， 3 3，1,21,2，具有，具有3 3个划分块的划分为个划分块的划分为 1 1，22，33；相应的等价关系为：相应的等价关系为： 12345AIRAAR2 , 3,3 , 2,21AAAIRIRIR543,1 , 2,2 , 1,1 , 3,3 , 144/56例例4-154-15：设：设R R是集合是集合A A上的一个关系，对恣意上的一个关系，对恣意a a，b b，c Ac A，假设，假设 那么称那么称R R为为A A上的循环关系。试证明上的循环关系。试证明R R是是A A上的一个上的一个等价关系的充要条件

50、是等价关系的充要条件是R R是循环关系和自反关系。是循环关系和自反关系。证明：必要性：假设证明：必要性：假设R R是等价关系；是等价关系；(1)R(1)R等价等价=R=R自反自反(2) (2) ，R R等价等价RR对对称称 ，即，即R R是循环是循环关系；关系；充分性：假设充分性：假设R R自反且循环：自反且循环：(1)(1)自反性显然；自反性显然；(2) (2) ，R R是自反，得是自反，得 ，因，因R R是循环是循环的的 ，即，即R R是对称的；是对称的；RcbRcaRba,，则有且RcaRbaAcba,若RcbRcaRab,R,传递，而Aba ,Raa ,RabRba,则若45/56(3

51、) (3) ，那么由，那么由R R对对称得称得 ，由，由R R循环，循环， 得得 ， R R是传送的；是传送的；RR等价。等价。RcbRbaAcba,，若Rab ,Rab ,Rcb ,Rca ,46/56在一些研讨中，需求把研讨的对象排出次序，因此在一些研讨中，需求把研讨的对象排出次序，因此，集合的元素之间还有一种重要关系，称为，集合的元素之间还有一种重要关系，称为“先后先后次序关系，即偏序关系。次序关系，即偏序关系。定义定义4.214.21：(1)(1)设设R R为非空集合为非空集合A A上的关系，假设上的关系，假设R R是是自反的，反对称的，传送的，那么称自反的，反对称的，传送的，那么称R

52、 R为为A A上的偏上的偏序关系序关系(Partial Order relation)(Partial Order relation)。记作。记作“, ,读作读作“小于等于；小于等于； (2) (2)设设R R为非空集合为非空集合A A上的关系上的关系，假设，假设R R是反自反的，反对称的，传送的，那么称是反自反的，反对称的，传送的，那么称R R为为A A上的拟序关系上的拟序关系(Quasi Order relation)(Quasi Order relation)。记。记作作“ 表示，读作表示，读作“大于。大于。1147/56例：例：(1)(1)集合集合A A上的幂集上的幂集(A)(A)上定

53、义的上定义的“ 和和“ 分别是偏序关系和拟序关系；分别是偏序关系和拟序关系；(2)(2)实数集合实数集合R R上定义的数的上定义的数的“小于等于关系，小于等于关系，“小小于关系，分别是偏序关系和拟序关系；于关系，分别是偏序关系和拟序关系；(3)(3)自然数集合自然数集合N N上定义的上定义的“整除关系，也是一个偏整除关系，也是一个偏序集合。序集合。定义定义4.224.22：设：设是一个偏序集，对是一个偏序集，对 ，x x yy或或y xy x，那么称，那么称x x与与y y是可比的是可比的(Comparable),(Comparable),假设假设x x与与y y是可比的，是可比的，xyxy，

54、且不存在，且不存在 ，使得，使得xyzxyz，那么称，那么称y y覆盖覆盖(Overlay)x(Overlay)x。Ayx ,Az48/56例：例：(1)(1)集合集合A=aA=a，b b，cc，那么偏序集，那么偏序集(A), 中，中，aa与与aa，bb是可比的；是可比的； a a与与bb，cc是是不可比的；不可比的； a a，bb覆盖覆盖aa； a a，b b，cc不覆盖不覆盖aa。(2)(2)偏序集偏序集RR，对，对 ，x x与与y y都是可比的都是可比的，但，但x x不覆盖不覆盖y y，y y也不覆盖也不覆盖x x。(3)(3)偏序集偏序集ZZ，对，对 ，x x与与y y都是可比的都是可

55、比的，x x覆盖覆盖x-1x-1。(4)(4)偏序集偏序集N|中，中，2 2与与3 3不是可比的，不是可比的，2 2与与6 6是可是可比的，并且比的，并且6 6覆盖覆盖2,22,2与与8 8可比，但可比，但8 8不覆盖不覆盖2 2。Ayx ,Ayx ,49/564.6.24.6.2：偏序集的哈斯图：偏序集的哈斯图由于偏序关系本身具有自反，反对称，传送的性由于偏序关系本身具有自反，反对称，传送的性质，在用关系图来描画偏序关系且不引起混淆，质，在用关系图来描画偏序关系且不引起混淆，可以对其进展简化，得到的图叫做偏序图或哈斯可以对其进展简化，得到的图叫做偏序图或哈斯图图(Hasse)(Hasse)。

56、哈斯图的作图方法如下：哈斯图的作图方法如下：(1):(1):用小圆圈或点表示用小圆圈或点表示A A中的元素，省掉关系图中中的元素，省掉关系图中的一切环的一切环( (因自反性因自反性) )；(2):(2):对对 ，假设，假设xyxy那么将那么将x x画在画在y y的下方，的下方，可省掉关系图中一切边的箭头；可省掉关系图中一切边的箭头；(3):(3):对对 ，假设，假设y y覆盖覆盖x x，那么在，那么在x x与与y y之间连之间连条线，否那么无线相连。条线，否那么无线相连。Ayx ,Ayx ,50/56按按(1)(1)，(2)(2)，(3)(3)所作成的图称为哈斯图。所作成的图称为哈斯图。例例4-164-16：设：设A=2,3,6,12,24,36A=2,3,6,12,24,36，“是是A A上的整上的整除关系，画出其普通关系图和哈斯图。除关系