第四章二元关系

1、1/574.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, y=v;x=u, y=v;例如：平面上的坐标例如：平面上的坐标，x, y Rx, y R；

2、等都是序偶。等都是序偶。2/57定义定义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=，b, 1，。性质性质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/57证明：证明：(6). (6). ，且当，且当 或或 时，逆命题成立。时，逆命题成立。 A);(CA)(BAC)(BC),(AB)(AC)(BA),(CA)(BAC)(BC),(AB)(AC)(BAA)()(,)(,)(,)()()()(,CABAyxCAyxBAyxCyAxByAxCyByAxCByAxCBAyxDCBADBCA

4、 BA BA4/57定义定义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,21121n

5、nbbbaaa,2121nibaii, 2 , 1,),(21nxxxnxxx,21nAAA,21|,221121nnnAxAxAxxxxnAAA21nAAA21nA5/574.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/57A A到到B B上的全部二元关系；而上的全部二元关系；而 ，为为B B上的二上的二元关系。元关系。一般来说，若一般来说，若|A|=m|A|=m，|B|=n|B|=n，A A到到B B上的二元关系共上的二元关

7、系共有有 个，个，A A上的共有上的共有 个二元关系；个二元关系；特殊的二元关系：特殊的二元关系： (1). (1). 空关系；空关系； (2). (2). 全域关系：全域关系： ； (3). (3). 恒等关系：恒等关系： 。 mn222mAAAyAxyxEA|,|,AxxxIA7/57定义定义4.74.7：设设R R为二元关系，则为二元关系，则 (1). (1). 为为R R的定义域；的定义域； (2). (2). 为为R R的值域；的值域； (3). (3). 为为R R的域。的域。一般地，若一般地，若R R是是A A到到B B上的二元关系，则有上的二元关系，则有 。 例例4-14-1：

8、设设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，那么，那么domRdomR=2,3,4,6=2,3,4,6，ranRranR=a, b, c=a, b, c。)(|xRyyxdomR)(|xRyxyranRranRdomRfldRBranRAdomR,8/574.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中的元素为顶点，在中的元素为顶点，在图中用图中用“”表示顶点，若表示顶点，若 则可自顶点则可自顶点 向向顶点顶点 引有向边引有向边 ，其箭头指向，其箭头指向 ，用这种，用这种方法画出的图称为关系图方法画出的图称为关系图(G

10、raph of Relation)(Graph of Relation)。nxxx,21nyyy,21jiRyxixjy),(jiyxjy9/57例例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，且，且,2121nmbbbBaaaABARRMijrjijiijbRaRbar当且仅当当且仅当0110/5

11、71.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=，|,|,|,|,xRyyxRxSyxRyyxSRxSyxRyyxSRxSyxRy

12、yxSR11/57S=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/572.2.关系的逆运算关系的逆运算由于关系是序偶的集合，除了集合的一般运算外，由于关系是序偶的集合，除了集合的一般运算外，还有一些特有的运算。还有一些特有的运算。定义定义4.1

13、14.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=， =，2, b，。1R|,1xRyxyRByAx ,xyRxRy1RMRRMM1 11,AAII1R13/57定理定理4.14.1：设设R R和和S S都是都是A A到到B B上的二元关系，那么上的二元关系，那么.)( ,).6(;,).5(;).(4(;)(

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

15、二元关系，且元关系，且R=|R=|x+yx+y=4=4=，S= =|y-S= =|y-x=1=x=1=，；求；求一般地，一般地，SR)(|,tSyxRttyxSRRR2R2RR)(SRR,S)(R,SSRRRSSRRSSR15/57定理定理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(),().(1 (FGGFHGFHGF RRRIIRAA).2( ,).1 (.).(4(,)().3(,).(2(,

16、)().1 (FHFGFHGHFGFHGFFHFGFHGHFGFHGF16/574.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/57定理定理4.54.5：设设R R为为A A上的二元关系，上的二元关系，m m，n n为自然数，为自然数，则则证证(4)(4)：若：若n=0n=0时，则有时，则有

17、假设假设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 (mnmnnnRRRRRRR.)().(4( ,).(3( ,).2(11nnmnnmnmnmRRRRRRR AAnAIIRIR1101)()( ,)(11)()(

18、kkRR111111111)()()()()()(kkkkkRRRRRRRR)20(2njijiRR22n22n1210,kRRRR18/57系中，至少有两个是相同的系中，至少有两个是相同的( (鸽巢原理鸽巢原理) )，即有，即有定理定理4.74.7：设设A A是有限集合，且是有限集合，且|A|=n|A|=n，R R是是A A上的二上的二元关系，则元关系，则证明：显然证明：显然 ，下面证：，下面证： 。而而 ，为此，只要证明对任意的，为此，只要证明对任意的knkn，有，有 即可。对任意的即可。对任意的 ，则由，则由“”“”的定义知：存在的定义知：存在 ，使得：，使得：.),20(,2jinRR

19、jiji使iniiiRR11 iiiniRR11iniiiRR11 iniiniiiRRR111inikRR1 kRba ,Aaaak121,),(,012110baaaRaaRaaRaakkk令19/57由于由于|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/575 5：集合在关系下的像：集合在关系下的像定义定义4.144.14：设设R R为二元关系，为二元关系，A A是集合是集合(1)(1)：R R在在A A上的限制上的限制 定义为：定义为： (2)(2)：A A在在R R下的像下的像RAR

21、A定义为定义为RA=ran( )RA=ran( )。例：例：R=R=，则：，则： R Ra=a=，；R Ra= ;a= ; R Ra, a=Ra, a=R； Ra=b,aRa=b,a；Ra,a=b,a,a,aRa,a=b,a,a,a；|,AxxRyyxARARAR,1aaaR;11aaRaR 21/57定理定理4.84.8：设设F F为关系，为关系，A A，B B为集合，则为集合，则例例4-64-6：设设 ，A=0,1,2A=0,1,2，B=0,-1,-2B=0,-1,-2。(1)(1)求求RABRAB和和RARBRARB；(2)(2)求求RA-RBRA-RB和和RA-BRA-B。解解(1)(

22、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|,|,xyZyxyxR 22/57我们在研究关系的性质时，可以假定关系是某一非我们在研究关系的性质时，可以假定关系是某一非空集合上的二元关系，这一假设不失一般性。因空集合上的二元

23、关系，这一假设不失一般性。因此任一此任一A A到到B B上的关系上的关系R R，即，即 ，而，而 ，所以关系，所以关系R R总可以看成是总可以看成是A AB B 上的关系，它与原关系上的关系，它与原关系R R具有完全相同的序具有完全相同的序偶，对它的讨论代替对偶，对它的讨论代替对R R的讨论无损于问题的本质的讨论无损于问题的本质1.1.关系的性质关系的性质定义定义4.154.15：设设R R是是A A上的二元关系，即上的二元关系，即 ，则，则(1)(1)若若 ，则称，则称R R是自反的是自反的(Reflexive)(Reflexive)；(2)(2)若若 ，则称，则称R R是反自反的是反自反的

24、( (IrreflexiveIrreflexive) )；BAR)()(BABABAAAR),(RxxAxx),(RxxAxx23/57(3)(3)若若 ，则称，则称R R是对称的是对称的(Symmetric)(Symmetric)(4)(4)若若 ，则称，则称R R是是反对称的反对称的( (AntisymmetricAntisymmetric) )(5)(5)若若 ，则称，则称R R是传递的是传递的(Transitive)(Transitive)例例4-74-7：设设A=a, b, c, dA=a, b, c, d(1):R=(1):R=，c, c，是自反的；是自反的；S=S=，是反自反的；

25、是反自反的；T=,c, T=,c,既不是自反的也不是反自反的；既不是自反的也不是反自反的；),(yRxxRyAyxyx),(yxyRxxRyAyxyx),(xRzyRzxRyAzyxzyx24/57在关系图上：关系在关系图上：关系R R是自反的，当且仅当其关系图是自反的，当且仅当其关系图中的每个节点都有环，关系中的每个节点都有环，关系R R是反自反的，当且仅是反自反的，当且仅当其关系图中的每个节点上都无环；当其关系图中的每个节点上都无环；在关系矩阵上：关系在关系矩阵上：关系R R是自反的，当且仅当其关系是自反的，当且仅当其关系矩阵的主对角线上全为矩阵的主对角线上全为1 1，关系，关系R R是反

26、自反的，当是反自反的，当且仅当其关系矩阵的主对角线上全为且仅当其关系矩阵的主对角线上全为0 0。例例4-84-8：设设A=a, b, cA=a, b, c称的。既是对称的，也是反对反对称的；既不是对称的，也不是是反对称的；是对称的；,)4(,) 3(,)2(,) 1 (4321ccaaRaccabaaaRcaaaRaccaaaR25/57关系图上：关系关系图上：关系R R是对称的当且仅当其关系图中，是对称的当且仅当其关系图中，任何一对节点之间，要么有方向相反的两条边，任何一对节点之间，要么有方向相反的两条边，要么无任何边；关系要么无任何边；关系R R是反对称的当且仅当其关系是反对称的当且仅当其

27、关系图中，任何一对节点之间，至多有一条边；图中，任何一对节点之间，至多有一条边；关系矩阵上：关系关系矩阵上：关系R R是对称的当且仅当其关系矩阵是对称的当且仅当其关系矩阵是对称矩阵；关系是对称矩阵；关系R R是反对称的当且仅当其关系矩是反对称的当且仅当其关系矩阵为反对称矩阵。阵为反对称矩阵。例例4-94-9：设设A=a, b, c, dA=a, b, c, d不是传递的。不是传递的；是传递的；是传递的；,)4(,)3(,)2(,) 1 (4321dccacbbaRcbbaaaRbaRcacbbaaaR26/57关系图上：关系关系图上：关系R R是传递的当且仅当其关系图中，是传递的当且仅当其关系

28、图中，任何三个节点任何三个节点x, y, z(x, y, z(可相同可相同) )之间，若从之间，若从x x到到y y，y y到到z z均有一条边，则从均有一条边，则从x x到到z z一定有一条边存在；一定有一条边存在；关系矩阵上：关系关系矩阵上：关系R R是传递当且仅当其关系矩阵中是传递当且仅当其关系矩阵中，对任意，对任意2.2.利用集合运算来判断关系的性质利用集合运算来判断关系的性质定理定理4.94.9：设设R R是集合是集合A A上的二元关系，则上的二元关系，则。则必有若1, 1, 1, 1 ,ikjkijrrrnkji.)5(;)4(;)3(;)2(;) 1 (11RRRRIRRRRRR

29、IRRRIRAAA 传递的是反对称的是对称的是反自反的是自反的27/573.3.关系性质的保守性关系性质的保守性定理定理4.104.10：设设R R，S S是是A A上的二元关系，则上的二元关系，则例例4-104-10：设设R=R=， S=S=，是定义在是定义在A=a, b, A=a, b, cc上的两个二元关系。上的两个二元关系。传递。传递反对称；反对称对称；对称反自反；反自反自反；自反SRRSRSRSRRSRSRSRSRRSRSRSRSRRSRSRSRSRRSR,)5(,)4(,) 3(,)2(,) 1 (1111128/57显然显然R R，S S是反自反的，反对称的，传递的，则是反自反的

30、，反对称的，传递的，则 也是反自反的，反对称的，传递也是反自反的，反对称的，传递的；的； 也具备上述的一切性质；也具备上述的一切性质；(3)RS=, ,c, (3)RS=, ,b,仅是对称的和反自反的；仅是对称的和反自反的； 则是传递的则是传递的和对称的。和对称的。111,).1 (SRSR SR)2(,)4(abbabbaaSR29/57关系的限制与扩充：对于任何一个具备某种性质关系的限制与扩充：对于任何一个具备某种性质( (如如自反、对称、传递自反、对称、传递) )的关系来说，在理论研究与应的关系来说，在理论研究与应用上都十分重要，但遗憾的是，许多我们要研究用上都十分重要，但遗憾的是，许多

31、我们要研究的关系并不具有我们所希望的良好性质。因此，的关系并不具有我们所希望的良好性质。因此，我们往往要在给定的关系中删去一些或添加一些我们往往要在给定的关系中删去一些或添加一些元素，以改变原有关系的性质，即所谓的关系的元素，以改变原有关系的性质，即所谓的关系的限制与扩充。限制与扩充。关系的闭包则是关系的扩充。关系的闭包则是关系的扩充。定义定义4.164.16：设设R R是定义在是定义在A A上的二元关系，若存在上的二元关系，若存在满足满足：(1) (1) 是自反的是自反的( (对称的或传递的对称的或传递的) )；(2).(2). ；(3)(3)对对R R的任何扩充的任何扩充 是自反的是自反的

32、( (对称的对称的或传递的或传递的) )，则，则 。一般将。一般将R R的自反、对称、的自反、对称、传递闭包记作传递闭包记作r(R)r(R)，s(R)s(R)，t(R)t(R)。RRRRR RR 30/57例：定义在例：定义在N N上的上的“ ”关系的自反闭包关系的自反闭包r(R)r(R)为为“”“”，对称闭包，对称闭包s(R)s(R)为为“”“”，传递闭包，传递闭包t(R)t(R)为为“ ”；定义在定义在N N上的上的“= =”关系的自反闭包关系的自反闭包r(R)r(R)为为“= =”，对称，对称闭包闭包s(R)s(R)为为“= =”，传递闭包，传递闭包t(R)t(R)为为“= =”。例例4

33、-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)=,;t(R)=,;t(R)=,;31/57利用关系图，关系矩阵求闭包的方法：利用关系图，关系矩阵求闭包的方法：(1).(1).求一个关系的自反闭包，即将图中所有的无环求一个关系的自反闭包，即将图中所有的无环节点加上环，矩阵中的对角线上的值全定

34、义为节点加上环，矩阵中的对角线上的值全定义为1 1；(2).(2).求一个关系的对称闭包，则在图中，任何一对求一个关系的对称闭包，则在图中，任何一对节点之间，若仅存在一条边，则加一条反方向的节点之间，若仅存在一条边，则加一条反方向的边；矩阵中则为：若边；矩阵中则为：若 ，则令，则令 ，即，即 ；(3).(3).求一个关系的传递闭包，则在图中，对任意节求一个关系的传递闭包，则在图中，对任意节点点a a，b b，c c，若，若a a到到b b有一条边，同时有一条边，同时b b到到c c也有一条也有一条边，则从边，则从a a到到c c必增加一条边必增加一条边( (当当a a到到c c无边时无边时)

35、)，在，在矩阵中，若矩阵中，若 。)( 1jirij) 1( 1jijirr若1)(RRRsMMM）（若则令111, 1ikikjkijrrrr32/57定理定理4.114.11：设设R R是是A A上的二元关系，则上的二元关系，则定理定理4.124.12：设设R R是集合是集合A A上的关系，则上的关系，则定理定理4.144.14：设设R R是集合是集合A A上的关系，则上的关系，则iniiiARRtnARRtRRRsIRRRRr1110)(|,)(: )3(,)(: )2( ,)(: ) 1 (则若.)(: )3(,)(: )2(,)(: ) 1 (RRtRRRsRRRrR是传递的是对称的

36、是自反的.)(: ) 3(,)(),(: )2(,)(),(: ) 1 (传递传递对称对称自反自反RrRRtRrRRtRsR33/57定义定义4.174.17：(1)(1)集合集合A A上的关系上的关系R R的自反对称闭包定的自反对称闭包定义为义为rsrs(R)=r(s(R); (2)(R)=r(s(R); (2)集合集合A A上的关系上的关系R R的自反的自反传递闭包定义为传递闭包定义为rtrt(R)=r(t(R); (3)(R)=r(t(R); (3)集合集合A A上的关上的关系系R R的对称传递闭包定义为的对称传递闭包定义为stst(R)=s(t(R);(R)=s(t(R);类似的类似的

37、，可有，可有srsr(R)(R)，trtr(R)(R)，tsts(R)(R)。定理定理4.154.15：设设R R是集合是集合A A上的关系，则上的关系，则)()().3(),()().2(),()().1 (RtsRstRtrRrtRsrRrs34/574.5.14.5.1：集合和划分：集合和划分定义定义4.184.18：设设A A是一个非空集合，是一个非空集合， 是是A A的任意的任意n n个非空子集，如果个非空子集，如果 满足：满足： 则称集合则称集合 为集合为集合A A的一个划分的一个划分(Partition)(Partition)，而，而 叫做这个划分的块或叫做这个划分的块或类。类。

38、例如：例如：(1) (1) 构成集合构成集合U U的一个划分；的一个划分；(2) (2) 构成了构成了U U上的一个划上的一个划分。分。nAAA,21nAAA,21AAnjijiAAiniji 1).2( ;, 1,).1 (,)(21nAAAAnAAA,21,AA,21212121AAAAAAAA35/574.5.24.5.2：等价关系：等价关系定义定义4.194.19：设设R R为非空集合为非空集合A A上的关系，如果上的关系，如果R R是自是自反的，对称的，传递的，则称反的，对称的，传递的，则称R R为为A A上的等价关系上的等价关系(Equivalent Relation)(Equiv

39、alent Relation)。若。若 ，称，称x x等价等价于于y,y,记作记作xyxy。例：例：(1)(1)一群人，同姓，同年龄，同性别都是等价关一群人，同姓，同年龄，同性别都是等价关系，朋友，同学关系不是等价关系：不传递；系，朋友，同学关系不是等价关系：不传递；(2)(2) 都是都是A A上的等价关系；上的等价关系；(3)(3)三角形三角形“相似相似”，“全等全等”都是等价关系；都是等价关系；(4)(4)幂集上定义的幂集上定义的 关系，整数集上定义的关系，整数集上定义的不是不是等价关系，不对称。等价关系，不对称。Ryx ,AAIA,36/57例例4-124-12：设设m m为正整数，整数

40、集合上的关系为正整数，整数集合上的关系 证明关系证明关系R R是等价关系。是等价关系。 证：证：(1)(1)对任意对任意 ，有，有 R R自反；自反； (2)(2)对任意对任意 ，若，若 , ,则则 ，即，即R R对称；对称；(3)(3)对任意对任意 ，若，若 ，即，即 ，而，而 ，R R传递传递R R是是Z Z上的等价关系。上的等价关系。 )(mod,|,myxZyxyxRZxRxxmxx,)(modZyx,)(mod,myxRyx即Rxymxy,modZzyx,RzyRyx,zymyxmmzymyx|,|),(mod),(modRzxzxmzyyxzx,|),()(37/57考察关系考察关

41、系R R和集合和集合Z Z；R R将将Z Z分成了如下分成了如下m m个子集：个子集：这这m m个子集特点是：同一个子集中的元素之间都有关个子集特点是：同一个子集中的元素之间都有关系系R R，不同子集的元素之间无关系，不同子集的元素之间无关系R R，每两个子集，每两个子集无公共元素，而所有子集的并正好为无公共元素，而所有子集的并正好为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,mmmmmmmmm

42、mmmmmmmmmmmmmmm38/574.5.34.5.3：等价类与商集：等价类与商集定义定义4.204.20：设设R R是非空集合是非空集合A A上的等价关系，对任上的等价关系，对任意意 ，称集合，称集合 为为x x关于关于R R的等的等价类价类(Equivalence 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

43、 3为模的同余关系，求其等价类。为模的同余关系，求其等价类。解：从例解：从例4-124-12知，知，R R是一个等价关系，则是一个等价关系，则Ax|xRyAyyxRRxRxRR44 , 1 1 33 ,858 , 5 , 22RRRR39/57定理定理4.114.11：设设R R为非空集合为非空集合A A上的等价关系，则上的等价关系，则证：证：(1) (1) ，R R是等价关系，则是等价关系，则R R自反，因此自反，因此即即(2)(2).).4(;,).3(;,).2(; ,).1 (AxyxyRxAyxyxxRyAyxxAxRAxRRRRR 则则AxRxx , RRxxxRxzRzxxzz,

44、RRRRyxyzxzRzyRyzRyxRxz,40/57同理：同理：(3)(3)若若 ，则存在，则存在 ，即：，即：定义定义4.214.21：设设R R是集合是集合A A上的等价关系，由上的等价关系，由R R确定的确定的一切等价类的集合，称为集合一切等价类的集合，称为集合A A上关于上关于R R的商集的商集(Quotient Set)(Quotient Set)，记为，记为A/RA/R，即，即RRRRyxxy RRyxRRyzxz矛盾与yRxRyxRzyRzx,AxxAxxAxxxxxxRxxAxxAxAxAxxRAxRAxRAxRAxRRAxR, ,)4(即|/AxxRAR41/57定理定理

45、4.124.12：设设R R是非空集合是非空集合A A上的等价关系，则上的等价关系，则A A上上的关于的关于R R的商集的商集A/RA/R是是A A的一个划分，称之为由的一个划分，称之为由R R导导出的等价划分。出的等价划分。证：由定理证：由定理4.114.11知，命题成立。知，命题成立。定理定理4.134.13：设设(A)(A)是非空集合是非空集合A A的一个划分，则的一个划分，则A A上的关系上的关系 是是A A上的等价关系，称之为由上的等价关系，称之为由(A)(A)所导出的等价所导出的等价关系。关系。证明：证明：(1) (1) 为为A A的一个划分，的一个划分， 使得使得 ，即，即x x

46、和和x x同属于同属于(A)(A)的一个划分块，的一个划分块， R R是自反的；是自反的；)(,|,的一个划分块同属于AyxAyxyxR)(,AAx)(AAiiAx42/57(2) (2) ，则，则x x和和y y同属于同属于(A)(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属于

47、同一划分块，属于同一划分块， R R是传递的；是传递的；R R为等价关系。为等价关系。若设若设 ，则，则RyxAyx,若Rxy,RzyRyxAzyx,若iAjAjiAAyjiAA ,)(21mAAAA212211)()()(imimmAAAAAAAR43/57有定理有定理4.12,4.134.12,4.13知，集合知，集合A A上的等价关系与集合上的等价关系与集合A A的划分是一一对应的，因此可以说：划分与等价的划分是一一对应的，因此可以说：划分与等价关系这两个不同的概念本质上是相同的，即是同关系这两个不同的概念本质上是相同的，即是同一个概念的两种不同的表达方式。一个概念的两种不同的表达方式。

48、例例4-144-14：设设A=1,2,3A=1,2,3，求，求A A上的所有等价关系。上的所有等价关系。解：先求解：先求A A的划分：只有一个划分块的划分为的划分：只有一个划分块的划分为1,2,31,2,3；具有；具有2 2个划分块的划分为个划分块的划分为 11，2,32,3， 22，1,31,3， 33，1,21,2，具有，具有3 3个划分块的划分为个划分块的划分为 11，22，33；相应的等价关系为：相应的等价关系为： 12345AIRAAR2 , 3,3 , 2,21AAAIRIRIR543,1 , 2,2 , 1,1 , 3,3 , 144/57例例4-154-15：设设R R是集合是

49、集合A A上的一个关系，对任意上的一个关系，对任意a a，b b，c Ac A，若，若 那么称那么称R R为为A A上的循环关系。试证明上的循环关系。试证明R R是是A A上的一个上的一个等价关系的充要条件是等价关系的充要条件是R R是循环关系和自反关系。是循环关系和自反关系。证明：必要性：若证明：必要性：若R R是等价关系；是等价关系；(1)R(1)R等价等价=R=R自反自反(2) (2) ，R R等价等价R R对称对称 ，即，即R R是循环关是循环关系；系；充分性：若充分性：若R R自反且循环自反且循环：(1)(1)自反性显然；自反性显然；(2) (2) ，R R是自反，得是自反，得 ，因

50、，因R R是循环的是循环的 ，即，即R R是对称的；是对称的；RcbRcaRba,，则有且RcaRbaAcba,若RcbRcaRab,R,传递，而Aba ,Raa ,RabRba,则若45/57(3) (3) ，则由，则由R R对称对称得得 ，由，由R R循环，循环， ， R R是传递的；是传递的；RR等价。等价。RcbRbaAcba,，若Rab ,Rab ,Rcb ,Rca ,46/57在一些研究中，需要把研究的对象排出次序，因此在一些研究中，需要把研究的对象排出次序，因此，集合的元素之间还有一种重要关系，称为，集合的元素之间还有一种重要关系，称为“先先后次序后次序”关系，即偏序关系。关系，

51、即偏序关系。定义定义4.214.21：(1)(1)设设R R为非空集合为非空集合A A上的关系，如果上的关系，如果R R是自反的，反对称的，传递的，则称是自反的，反对称的，传递的，则称R R为为A A上的偏上的偏序关系序关系(Partial Order relation)(Partial Order relation)。记作。记作“”“”, ,读作读作“小于等于小于等于”； (2) (2)设设R R为非空集合为非空集合A A上的关上的关系，如果系，如果R R是反自反的，反对称的，传递的，则称是反自反的，反对称的，传递的，则称R R为为A A上的拟序关系上的拟序关系(Quasi Order re

52、lation)(Quasi Order relation)。记。记作作“ ”表示，读作表示，读作“大于大于”。1147/57例：例：(1)(1)集合集合A A上的幂集上的幂集(A)(A)上定义的上定义的“ ”“ ”和和“ “ ”分别是偏序关系和拟序关系；分别是偏序关系和拟序关系；(2)(2)实数集合实数集合R R上定义的数的上定义的数的“小于等于小于等于”关系，关系，“小于小于”关系，分别是偏序关系和拟序关系；关系，分别是偏序关系和拟序关系；(3)(3)自然数集合自然数集合N N上定义的上定义的“整除整除”关系，也是一个关系，也是一个偏序集合。偏序集合。定义定义4.224.22：设设是一个偏序

53、集，对是一个偏序集，对 ，x yx y或或y xy x，则称，则称x x与与y y是可比的是可比的(Comparable),(Comparable),若若x x与与y y是可比的，是可比的，xyxy，且不存在，且不存在 ，使得，使得xzyxzy，则称，则称y y覆盖覆盖( (Overlay)xOverlay)x。Ayx ,Az48/57例：例：(1)(1)集合集合A=aA=a，b b，cc，则偏序集，则偏序集 中中，aa与与aa，bb是可比的；是可比的； a a与与bb，cc是不可比是不可比的；的； a a，bb覆盖覆盖aa； a a，b b，cc不覆盖不覆盖aa。(2)(2)偏序集偏序集RR

54、，对，对 ，x x与与y y都是可比的都是可比的，但，但x x不覆盖不覆盖y y，y y也不覆盖也不覆盖x x。(3)(3)偏序集偏序集ZZ，对，对 ，x x与与y y都是可比的都是可比的，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/574.6.24.6.2：偏序集的哈斯图：偏序集的哈斯图由于偏序关系本身具有自反，反对称，传递的性质由于偏序关系本身具有自反，反对称，传递的性质，在用关系图来

55、描述偏序关系且不引起混淆，可，在用关系图来描述偏序关系且不引起混淆，可以对其进行简化，得到的图叫做偏序图或哈斯图以对其进行简化，得到的图叫做偏序图或哈斯图( (HasseHasse) )。哈斯图的作图方法如下：哈斯图的作图方法如下：(1):(1):用小圆圈或点表示用小圆圈或点表示A A中的元素，省掉关系图中中的元素，省掉关系图中的所有环的所有环( (因自反性因自反性) )；(2):(2):对对 ，若，若xyxy则将则将x x画在画在y y的下方，可省的下方，可省掉关系图中所有边的箭头；掉关系图中所有边的箭头；(3):(3):对对 ，若，若y y覆盖覆盖x x，则在，则在x x与与y y之间连条

56、线之间连条线，否则无线相连。，否则无线相连。Ayx ,Ayx ,50/57按按(1)(1)，(2)(2)，(3)(3)所作成的图称为哈斯图。所作成的图称为哈斯图。例例4-164-16：设设A=2,3,6,12,24,36A=2,3,6,12,24,36，“”“”是是A A上的上的整除关系，画出其一般关系图和哈斯图。整除关系，画出其一般关系图和哈斯图。例例4-174-17：设集合设集合A=aA=a，B=aB=a，bb，C=aC=a，b b，cc分别画出集合分别画出集合A A，B B，C C之幂集上定义的之幂集上定义的“ ”“ ”的哈的哈斯图。斯图。51/574.6.34.6.3：偏序集中的特殊元素：偏序集中的特殊元素定义定义4.234.23：设设为偏序集，为偏序集，最小元与极小元不一样，最小元是最小元与极小元不一样，最小元是B B中最小的元素中最小的元素，它与，它与B B中其它元素都是可比的，而极小元不一定中其它元素都是可比的，而极小元不一定与与B B中的元素都可比，只要没有比它小的元素，它中的元素都可比，只要没有比它小的元素，它就是极小元；就是极小元；对于有穷集，极小元一定存在，但最小元不一定对于有穷集，极小元一定存在，但最小元不一定存在；存在；ByAB,的极大元。为成立，则称若的极小元；为成立，则称若的最大元；为成