【教学课件】第四章二元关系.ppt

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

1、1/57第四章第四章 二元关系二元关系4.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

2、 R；等都是序偶。等都是序偶。2/574.1 二元关系及其表示法二元关系及其表示法定义定义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 B=A B=，；B A=B A=，b,1，。性质性质4.24.2：(1).|A B|=|A|B|(A,B(1).|A B|=|A|B|(A,B为有限为有限集合集合)；(2).(2).；(3).(3).不适合交换律，即不适合交换律，即AB BA(AB B

3、A(除非除非A A，B=B=或或A=B)A=B)；(4).(4).不适合结合律，不适合结合律，(AB)C A(BC)(AB)C A(BC)(除除非非 )；(5).(5).对对和和运算满足分配律，运算满足分配律，3/574.1 二元关系及其表示法二元关系及其表示法证明：证明：(6).(6).，且当，且当 或或 时，逆命题成立。时，逆命题成立。4/574.1 二元关系及其表示法二元关系及其表示法定义定义4.34.3：一个有序一个有序n(n2)n(n2)元组是一个有序对，它元组是一个有序对，它的第一个元素为有序的的第一个元素为有序的n-1n-1元组元组 ，第二个元素为，第二个元素为 ，记为，记为 即

4、：即：；当且仅当当且仅当n n维空间中的点维空间中的点M M的坐标的坐标 为有序的为有序的n n元组元组 。定义定义4.44.4：设设 为为n n个集合个集合(n 2)(n 2)，称集合，称集合 为为n n维卡氏积或维卡氏积或n n阶笛卡尔积，记作阶笛卡尔积，记作 ，当当 时简记为时简记为 。5/574.1 二元关系及其表示法二元关系及其表示法4.1.2 4.1.2 二元关系二元关系定义定义4.54.5：若集合若集合F F中的全体元素为有序的中的全体元素为有序的n(n2)n(n2)元组，则称元组，则称F F为为n n元关系，特别地，当元关系，特别地，当n=2n=2时，称时，称F F为二元关系，

5、简称关系。为二元关系，简称关系。对于二元关系对于二元关系F F，若，若 ，常记作，常记作 ，反之，反之 ；规定；规定 为为n n元空关系，也是二元空关系，简称元空关系，也是二元空关系，简称空关系。空关系。定义定义4.64.6：设设A A，B B为两集合，为两集合，ABAB的集合子集的集合子集R R称为称为A A到到B B的二元关系，特别地，当的二元关系，特别地，当A=BA=B时，称时，称R R为为A A上的上的二元关系。二元关系。例：例：A=a,bA=a,b，B=cB=c，则，则ABAB的子集有的子集有 ，a,c，,，6/574.1 二元关系及其表示法二元关系及其表示法A A到到B B上的全部

6、二元关系；而上的全部二元关系；而 ，为为B B上的二上的二元关系。元关系。一般来说，若一般来说，若|A|=m|A|=m，|B|=n|B|=n，A A到到B B上的二元关系共有上的二元关系共有 个，个，A A上的共有上的共有 个二元关系；个二元关系；特殊的二元关系：特殊的二元关系：(1).(1).空关系；空关系；(2).(2).全域关系：全域关系：；(3).(3).恒等关系：恒等关系：。7/574.1 二元关系及其表示法二元关系及其表示法定义定义4.74.7：设设R R为二元关系，则为二元关系，则 (1).(1).为为R R的定义域；的定义域；(2).(2).为为R R的值域；的值域；(3).(

7、3).为为R R的域。的域。一般地，若一般地，若R R是是A A到到B B上的二元关系，则有上的二元关系，则有 。例例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=，那么，那么domR=2,3,4,6domR=2,3,4,6，ranR=a,b,cranR=a,b,c。8/574.1 二元关系及其表示法二元关系及其表示法4.1.2 4.1.2 关系的表示关系的表示1.1.集合表示法集合表示法 由于关系也是一种特殊的集合，所以可以用集合由于关系也是一种特殊的集合，所以可以用集合的两种基本的表示方法的两种基本的表示方法(枚

8、举法，描述法枚举法，描述法)来表示来表示关系；如：设关系；如：设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中的元素为顶点，在中的元素为顶点，在图中用图中用“”表示顶点，若表示顶点，若 则可自顶点则可自顶点 向向顶点顶点 引有向边引有向边 ，其箭头指向，其箭头指向 ，用这种，用这种方法画出的图称为关系图方法画出

9、的图称为关系图(Graph of Relation)(Graph of Relation)。9/574.1 二元关系及其表示法二元关系及其表示法例例4-24-2：求集合求集合A=1,2,3,4A=1,2,3,4的恒等关系，空关系，的恒等关系，空关系，全关系和小于关系的关系图。全关系和小于关系的关系图。3.3.关系矩阵关系矩阵定义定义4.94.9：设设 ，那么，那么R R的关系矩阵的关系矩阵 为一为一mnmn矩阵，它的第矩阵，它的第i i，j j分量分量 只取只取0 0或或1 1，且，且10/574.2 关系的运算关系的运算1.1.关系的交，并，补，差运算关系的交，并，补，差运算定义定义4.10

10、4.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=，11/574.2 关系的运算关系的运算S=S=，RS=RS=，；RS=RS=；S-R=S=S-R=S=；R=AA-R=R=AA-R=，；R S=(RS)-(RS)

11、=RS.R S=(RS)-(RS)=RS.关系的补运算是对全关系而言的；关系的补运算是对全关系而言的；关系的并，交，差，补的矩阵可用如下方法求取：关系的并，交，差，补的矩阵可用如下方法求取：12/574.2 关系的运算关系的运算2.2.关系的逆运算关系的逆运算由于关系是序偶的集合，除了集合的一般运算外，由于关系是序偶的集合，除了集合的一般运算外，还有一些特有的运算。还有一些特有的运算。定义定义4.114.11：设设R R是是A A到到B B的关系，的关系，R R的逆关系或逆是的逆关系或逆是B B到到A A的关系，记为的关系，记为 ，定义为：，定义为：显然对任意显然对任意 ，有，有 ；为为R R

12、的关系矩阵，则的关系矩阵，则 .例：例：；A=a,b,c,dA=a,b,c,d，B=1,2,3B=1,2,3，R=R=，=，2,b，。13/574.2 关系的运算关系的运算定理定理4.14.1：设设R R和和S S都是都是A A到到B B上的二元关系，那么上的二元关系，那么14/574.2 关系的运算关系的运算3.3.关系的复合运算关系的复合运算定义定义4.124.12：设设R R，S S为二元关系，则为二元关系，则R R与与S S的复合关系的复合关系 定义为：定义为：，其中，其中“”“”为复合运算，为复合运算，也记为也记为 。例：设例：设R R表示父子关系，则表示父子关系，则 表示祖孙关系。

13、表示祖孙关系。例例4-44-4：设集合设集合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=，；求；求一般地，一般地，15/574.2 关系的运算关系的运算定理定理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为任意二元关系，则为任意二元关系，则16/574.2 关系的运算关系的运算4.4.关系的幂运算关系的幂运算定义定义

14、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=，。则则 =，；=，；=，=17/574.2 关系的运算关系的运算定理定理4.54.5：设设R R为为A 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

15、上的二元关系，上的二元关系，那么存在自然数那么存在自然数i i，j j使得使得证明：我们知道，当证明：我们知道，当|A|=n|A|=n时，时，A A上的二元关系共计上的二元关系共计 个，令个，令k=k=，因此在，因此在 这这k+1k+1个关个关18/574.2 关系的运算关系的运算系中，至少有两个是相同的系中，至少有两个是相同的(鸽巢原理鸽巢原理)，即有，即有定理定理4.74.7：设设A A是有限集合，且是有限集合，且|A|=n|A|=n，R R是是A A上的二上的二元关系，则元关系，则证明：显然证明：显然 ，下面证：，下面证：。而而 ，为此，只要证明对任意的，为此，只要证明对任意的knkn，

16、有，有 即可。对任意的即可。对任意的 ，则由，则由“”“”的定义知：存在的定义知：存在 ，使得：，使得：19/574.2 关系的运算关系的运算由于由于|A|=n|A|=n，所以由鸽巢原理；，所以由鸽巢原理；k+1k+1个元素个元素 中至少有两个元素相同，不妨设为中至少有两个元素相同，不妨设为 ，则可，则可在在 中删去中删去 后仍有后仍有由关系的复合运算得：由关系的复合运算得：，其中，其中 ，此时：若，此时：若 ，则，则 ；若；若 ，则重复上述做法，最终总能找到，则重复上述做法，最终总能找到 ，使，使得得 ，即有，即有 ，由此，由此有有 ，由，由k k的任意性的任意性 ，20/574.2 关系的

17、运算关系的运算5 5：集合在关系下的像：集合在关系下的像定义定义4.144.14：设设R R为二元关系，为二元关系，A A是集合是集合(1)(1)：R R在在A A上的限制上的限制 定义为：定义为：(2)(2)：A A在在R R下的像下的像RARA定义为定义为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；21/574.2 关系的运算关系的运算定理定理4.84.8：设设F F为关系，为关系，A A，B B为集合，则为集合，则例例4-64-6：

18、设设 ，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)(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,222/574.3 关系的性质关系的性质我们在研究关系的性质时，可以假定关系是某一非我们在研究关系的性质时，可以假定关系是某一非空集合

19、上的二元关系，这一假设不失一般性。因空集合上的二元关系，这一假设不失一般性。因此任一此任一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)

20、(2)若若 ，则称，则称R R是反自反的是反自反的(Irreflexive)(Irreflexive)；23/574.3 关系的性质关系的性质(3)(3)若若 ，则称，则称R R是对称的是对称的(Symmetric)(Symmetric)(4)(4)若若 ，则称，则称R R是反是反对称的对称的(Antisymmetric)(Antisymmetric)(5)(5)若若 ，则称，则称R R是是传递的传递的(Transitive)(Transitive)例例4-74-7：设设A=a,b,c,dA=a,b,c,d(1):R=(1):R=，是自反的；是自反的；S=S=，是反自反的；是反自反的；T=,c

21、,T=,c,既不是自反的也不是反自反的；既不是自反的也不是反自反的；24/574.3 关系的性质关系的性质在关系图上：关系在关系图上：关系R R是自反的，当且仅当其关系图是自反的，当且仅当其关系图中的每个节点都有环，关系中的每个节点都有环，关系R R是反自反的，当且仅是反自反的，当且仅当其关系图中的每个节点上都无环；当其关系图中的每个节点上都无环；在关系矩阵上：关系在关系矩阵上：关系R R是自反的，当且仅当其关系是自反的，当且仅当其关系矩阵的主对角线上全为矩阵的主对角线上全为1 1，关系，关系R R是反自反的，当是反自反的，当且仅当其关系矩阵的主对角线上全为且仅当其关系矩阵的主对角线上全为0

22、0。例例4-84-8：设设A=a,b,cA=a,b,c25/574.3 关系的性质关系的性质关系图上：关系关系图上：关系R R是对称的当且仅当其关系图中，是对称的当且仅当其关系图中，任何一对节点之间，要么有方向相反的两条边，任何一对节点之间，要么有方向相反的两条边，要么无任何边；关系要么无任何边；关系R R是反对称的当且仅当其关系是反对称的当且仅当其关系图中，任何一对节点之间，至多有一条边；图中，任何一对节点之间，至多有一条边；关系矩阵上：关系关系矩阵上：关系R R是对称的当且仅当其关系矩阵是对称的当且仅当其关系矩阵是对称矩阵；关系是对称矩阵；关系R R是反对称的当且仅当其关系矩是反对称的当且

23、仅当其关系矩阵为反对称矩阵。阵为反对称矩阵。例例4-94-9：设设A=a,b,c,dA=a,b,c,d26/574.3 关系的性质关系的性质关系图上：关系关系图上：关系R R是传递的当且仅当其关系图中，是传递的当且仅当其关系图中，任何三个节点任何三个节点x,y,z(x,y,z(可相同可相同)之间，若从之间，若从x x到到y y，y y到到z z均有一条边，则从均有一条边，则从x x到到z z一定有一条边存在；一定有一条边存在；关系矩阵上：关系关系矩阵上：关系R R是传递当且仅当其关系矩阵中，是传递当且仅当其关系矩阵中，对任意对任意2.2.利用集合运算来判断关系的性质利用集合运算来判断关系的性质

24、定理定理4.94.9：设设R R是集合是集合A A上的二元关系，则上的二元关系，则27/574.3 关系的性质关系的性质3.3.关系性质的保守性关系性质的保守性定理定理4.104.10：设设R R，S S是是A A上的二元关系，则上的二元关系，则例例4-104-10：设设R=R=，S=S=，是定义在是定义在A=a,b,A=a,b,cc上的两个二元关系。上的两个二元关系。28/574.3 关系的性质关系的性质显然显然R R，S S是反自反的，反对称的，传递的，则是反自反的，反对称的，传递的，则 也是反自反的，反对称的，传递的；也是反自反的，反对称的，传递的；也具备上述的一切性质；也具备上述的一切

25、性质；(3)RS=,c,(3)RS=,b,仅是对称的和反自反的；仅是对称的和反自反的；则是传递的则是传递的和对称的。和对称的。29/574.4 关系的闭包关系的闭包关系的限制与扩充：对于任何一个具备某种性质关系的限制与扩充：对于任何一个具备某种性质(如如自反、对称、传递自反、对称、传递)的关系来说，在理论研究与应的关系来说，在理论研究与应用上都十分重要，但遗憾的是，许多我们要研究用上都十分重要，但遗憾的是，许多我们要研究的关系并不具有我们所希望的良好性质。因此，的关系并不具有我们所希望的良好性质。因此，我们往往要在给定的关系中删去一些或添加一些我们往往要在给定的关系中删去一些或添加一些元素，以

26、改变原有关系的性质，即所谓的关系的元素，以改变原有关系的性质，即所谓的关系的限制与扩充。限制与扩充。关系的闭包则是关系的扩充。关系的闭包则是关系的扩充。定义定义4.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)。30/574.4 关系的闭包关

27、系的闭包例：定义在例：定义在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-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

28、)s(R)，t(R)t(R)的关系图，关系矩的关系图，关系矩阵。阵。解：解：r(R)=,;r(R)=,;s(R)=,;s(R)=,;t(R)=,;t(R)=,;31/574.4 关系的闭包关系的闭包利用关系图，关系矩阵求闭包的方法：利用关系图，关系矩阵求闭包的方法：(1).(1).求一个关系的自反闭包，即将图中所有的无环求一个关系的自反闭包，即将图中所有的无环节点加上环，矩阵中的对角线上的值全定义为节点加上环，矩阵中的对角线上的值全定义为1 1；(2).(2).求一个关系的对称闭包，则在图中，任何一对求一个关系的对称闭包，则在图中，任何一对节点之间，若仅存在一条边，则加一条反方向的节点之间，若

29、仅存在一条边，则加一条反方向的边；矩阵中则为：若边；矩阵中则为：若 ，则令，则令 ，即，即 ；(3).(3).求一个关系的传递闭包，则在图中，对任意节求一个关系的传递闭包，则在图中，对任意节点点a a，b b，c c，若，若a a到到b b有一条边，同时有一条边，同时b b到到c c也有一条也有一条边，则从边，则从a a到到c c必增加一条边必增加一条边(当当a a到到c c无边时无边时)，在，在矩阵中，若矩阵中，若 。32/574.4 关系的闭包关系的闭包定理定理4.114.11：设设R R是是A A上的二元关系，则上的二元关系，则定理定理4.124.12：设设R R是集合是集合A A上的关

30、系，则上的关系，则定理定理4.144.14：设设R R是集合是集合A A上的关系，则上的关系，则33/574.4 关系的闭包关系的闭包定义定义4.174.17：(1)(1)集合集合A A上的关系上的关系R R的自反对称闭包定的自反对称闭包定义为义为rs(R)=r(s(R);(2)rs(R)=r(s(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);类似的，类似的，可有

31、可有sr(R)sr(R)，tr(R)tr(R)，ts(R)ts(R)。定理定理4.154.15：设设R R是集合是集合A A上的关系，则上的关系，则34/574.5 等价关系与划分等价关系与划分：集合和划分：集合和划分定义定义4.184.18：设设A A是一个非空集合，是一个非空集合，是是A A的的任意任意n n个非空子集，如果个非空子集，如果 满足：满足：则称集合则称集合 为集合为集合A A的一个划分的一个划分(Partition)(Partition)，而，而 叫做这个划分的块或叫做这个划分的块或类。类。例如：例如：(1)(1)构成集合构成集合U U的一个划分；的一个划分；(2)(2)构成

32、了构成了U U上的一个划分。上的一个划分。35/574.5 等价关系与划分等价关系与划分：等价关系：等价关系定义定义4.194.19：设设R R为非空集合为非空集合A A上的关系，如果上的关系，如果R R是自是自反的，对称的，传递的，则称反的，对称的，传递的，则称R R为为A A上的等价关系上的等价关系(Equivalent Relation)(Equivalent Relation)。若。若 ，称，称x x等价等价于于y,y,记作记作xyxy。例：例：(1)(1)一群人，同姓，同年龄，同性别都是等价关一群人，同姓，同年龄，同性别都是等价关系，朋友，同学关系不是等价关系：不传递；系，朋友，同学

33、关系不是等价关系：不传递；(2)(2)都是都是A A上的等价关系；上的等价关系；(3)(3)三角形三角形“相似相似”，“全等全等”都是等价关系；都是等价关系；(4)(4)幂集上定义的幂集上定义的 关系，整数集上定义的关系，整数集上定义的不是等不是等价关系，不对称。价关系，不对称。36/574.5 等价关系与划分等价关系与划分例例4-124-12：设设m m为正整数，整数集合上的关系为正整数，整数集合上的关系 证明关系证明关系R R是等价关系。是等价关系。证：证：(1)(1)对任意对任意 ，有，有 R R自反；自反；(2)(2)对任意对任意 ，若，若 ,则则 ，即，即R R对称；对称；(3)(3

34、)对任意对任意 ，若，若 ，即，即 ，而，而 ，R R传递传递R R是是Z Z上的等价关系。上的等价关系。37/574.5 等价关系与划分等价关系与划分考察关系考察关系R R和集合和集合Z Z；R R将将Z Z分成了如下分成了如下m m个子集：个子集：这这m m个子集特点是：同一个子集中的元素之间都有关个子集特点是：同一个子集中的元素之间都有关系系R R，不同子集的元素之间无关系，不同子集的元素之间无关系R R，每两个子集，每两个子集无公共元素，而所有子集的并正好为无公共元素，而所有子集的并正好为Z Z，构成了，构成了Z Z的一个划分。的一个划分。38/574.5 等价关系与划分等价关系与划分

35、：等价类与商集：等价类与商集定义定义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 3为为模的同余关系，求其等价类。模的同余关系，求其等价类。

36、解：从例解：从例4-124-12知，知，R R是一个等价关系，则是一个等价关系，则39/574.5 等价关系与划分等价关系与划分定理定理4.114.11：设设R R为非空集合为非空集合A A上的等价关系，则上的等价关系，则证：证：(1)(1)，R R是等价关系，则是等价关系，则R R自反，因此自反，因此即即(2)(2)40/574.5 等价关系与划分等价关系与划分同理：同理：(3)(3)若若 ，则存在，则存在 ，即：，即：定义定义4.214.21：设设R R是集合是集合A A上的等价关系，由上的等价关系，由R R确定的确定的一切等价类的集合，称为集合一切等价类的集合，称为集合A A上关于上关于

37、R R的商集的商集(Quotient Set)(Quotient Set)，记为，记为A/RA/R，即，即41/574.5 等价关系与划分等价关系与划分定理定理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上的等价关系，称之为

38、由上的等价关系，称之为由(A)(A)所导出的等价关所导出的等价关系。系。证明：证明：(1)(1)为为A A的一个划分，的一个划分，使得使得 ，即，即x x和和x x同属于同属于(A)(A)的一个划分块，的一个划分块，R R是自反的；是自反的；42/574.5 等价关系与划分等价关系与划分(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)的一个的一个划分块

39、划分块 ，而由于不同划分块的交集，而由于不同划分块的交集为空，为空，即，即x x和和z z属于同一划分块，属于同一划分块，R R是是传递的；传递的；R R为等价关系。为等价关系。若设若设 ，则，则43/574.5 等价关系与划分等价关系与划分有定理有定理4.12,4.134.12,4.13知，集合知，集合A A上的等价关系与集合上的等价关系与集合A A的划分是一一对应的，因此可以说：划分与等价的划分是一一对应的，因此可以说：划分与等价关系这两个不同的概念本质上是相同的，即是同关系这两个不同的概念本质上是相同的，即是同一个概念的两种不同的表达方式。一个概念的两种不同的表达方式。例例4-144-1

40、4：设设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；相应的等价关系为：相应的等价关系为：44/574.5 等价关系与划分等价关系与划分例例4-154-15：设设R R是集合是集合A A上的一个关系，对任意上的一个关系，对任意a a，b b，c Ac A，若，若 那么称那么称R R为为

41、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是自反，得是自反，得 ，因，因R R是循环的是循环的 ，即，即R R是对称的；是对称的；45/574.5 等价关系与划分等价关系与划分(3)(3

42、)，则由，则由R R对称得对称得 ，由，由R R循环，循环，R R是传递的；是传递的；RR等价。等价。46/574.6 次序关系次序关系在一些研究中，需要把研究的对象排出次序，因此，在一些研究中，需要把研究的对象排出次序，因此，集合的元素之间还有一种重要关系，称为集合的元素之间还有一种重要关系，称为“先后先后次序次序”关系，即偏序关系。关系，即偏序关系。定义定义4.214.21：(1)(1)设设R R为非空集合为非空集合A A上的关系，如果上的关系，如果R R是是自反的，反对称的，传递的，则称自反的，反对称的，传递的，则称R R为为A A上的偏序上的偏序关系关系(Partial Order r

43、elation)(Partial Order relation)。记作。记作“”“”,读读作作“小于等于小于等于”；(2)(2)设设R R为非空集合为非空集合A A上的关系，上的关系，如果如果R R是反自反的，反对称的，传递的，则称是反自反的，反对称的，传递的，则称R R为为A A上的拟序关系上的拟序关系(Quasi Order relation)(Quasi Order relation)。记作。记作“”表示，读作表示，读作“大于大于”。47/574.6 次序关系次序关系例：例：(1)(1)集合集合A A上的幂集上的幂集(A)(A)上定义的上定义的“”“”和和“”分别是偏序关系和拟序关系；分

44、别是偏序关系和拟序关系；(2)(2)实数集合实数集合R R上定义的数的上定义的数的“小于等于小于等于”关系，关系，“小于小于”关系，分别是偏序关系和拟序关系；关系，分别是偏序关系和拟序关系；(3)(3)自然数集合自然数集合N N上定义的上定义的“整除整除”关系，也是一个关系，也是一个偏序集合。偏序集合。定义定义4.224.22：设设是一个偏序集，对是一个偏序集，对 ，x yx y或或y xy x，则称，则称x x与与y y是可比的是可比的(Comparable),(Comparable),若若x x与与y y是可比的，是可比的，xyxy，且不存在，且不存在 ，使得，使得xzyxzy，则称，则称

45、y y覆盖覆盖(Overlay)x(Overlay)x。48/574.6 次序关系次序关系例：例：(1)(1)集合集合A=aA=a，b b，cc，则偏序集，则偏序集 中，中，aa与与aa，bb是可比的；是可比的；a a与与bb，cc是不可比的；是不可比的；aa，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都是可比的，都是可比的，x x覆盖覆盖x-1x-1。(4)(4)偏序集偏序集N|中，中

46、，2 2与与3 3不是可比的，不是可比的，2 2与与6 6是可比是可比的，并且的，并且6 6覆盖覆盖2,22,2与与8 8可比，但可比，但8 8不覆盖不覆盖2 2。49/574.6 次序关系次序关系：偏序集的哈斯图：偏序集的哈斯图由于偏序关系本身具有自反，反对称，传递的性质，由于偏序关系本身具有自反，反对称，传递的性质，在用关系图来描述偏序关系且不引起混淆，可以在用关系图来描述偏序关系且不引起混淆，可以对其进行简化，得到的图叫做偏序图或哈斯图对其进行简化，得到的图叫做偏序图或哈斯图(Hasse)(Hasse)。哈斯图的作图方法如下：哈斯图的作图方法如下：(1):(1):用小圆圈或点表示用小圆圈

47、或点表示A A中的元素，省掉关系图中的中的元素，省掉关系图中的所有环所有环(因自反性因自反性)；(2):(2):对对 ，若，若xyxy则将则将x x画在画在y y的下方，可省掉的下方，可省掉关系图中所有边的箭头；关系图中所有边的箭头；(3):(3):对对 ，若，若y y覆盖覆盖x x，则在，则在x x与与y y之间连条线，之间连条线，否则无线相连。否则无线相连。50/574.6 次序关系次序关系按按(1)(1)，(2)(2)，(3)(3)所作成的图称为哈斯图。所作成的图称为哈斯图。例例4-164-16：设设A=2,3,6,12,24,36A=2,3,6,12,24,36，“”“”是是A A上的

48、上的整除关系，画出其一般关系图和哈斯图。整除关系，画出其一般关系图和哈斯图。例例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 次序关系次序关系：偏序集中的特殊元素：偏序集中的特殊元素定义定义4.234.23：设设为偏序集，为偏序集，最小元与极小元不一样，最小元是最小元与极小元不一样，最小元是B B中最小的元素，中最小的元素，它与它与B B中其它元素都是可比的，而极小元不一定与中其它元素都是可比的，而极小元不一定与B B中的元素都可比

49、，只要没有比它小的元素，它就中的元素都可比，只要没有比它小的元素，它就是极小元；是极小元；对于有穷集，极小元一定存在，但最小元不一定对于有穷集，极小元一定存在，但最小元不一定存在；存在；52/574.6 次序关系次序关系如果最小元存在，最小元唯一，但极小元可以有如果最小元存在，最小元唯一，但极小元可以有多个；多个；b b是是B B的最小元的最小元bb是是B B中的唯一极小元；中的唯一极小元；反之，极大元亦然。反之，极大元亦然。定义定义4.244.24：设设为偏序集，为偏序集，53/574.6 次序关系次序关系例例4-184-18：设集合设集合A=aA=a，b b，cc，求偏序集，求偏序集 的的

50、子集的子集子集的子集 的最大元，最小元，极大元，极小元，上的最大元，最小元，极大元，极小元，上界，下界，上确界，下确界。界，下界，上确界，下确界。解：画图解：画图 集合集合最大元最大元最小元最小元极大元极大元极小元极小元上界上界下界下界上确界上确界下确界下确界无a,b，b，ca，b，ca，b，ca，c 无a，ca，ca,c，a，b，ca，ca，b，ca，b，ca，b，ca，b，c54/574.6 次序关系次序关系例例4-194-19：设设A=aA=a，b b，c c，dd，A A上定义偏序集上定义偏序集A 的哈斯图如图所示，求的哈斯图如图所示，求B=aB=a，bb和和 C=c C=c，dd的最