离散数学第四章二元关系课件.ppt

1、 第四章第四章二元关系二元关系1 序偶与笛卡尔积2 关系及其表示3 关系的性质4 关系的运算5 等价关系与划分6 相容关系与覆盖7 偏序关系1 序偶与笛卡尔乘积序偶与笛卡尔乘积 1 序偶序偶定义定义由二个具有给定次序的客体所组成的序列由二个具有给定次序的客体所组成的序列称为序偶。记作称为序偶。记作x，y 例：例：XY二维平面上的一个点的坐标二维平面上的一个点的坐标x，y就就是一个序偶。是一个序偶。说明：说明：(1)在序偶中二个元素要有确定的排列次序。在序偶中二个元素要有确定的排列次序。若若a b时，则时，则a，b b，a 若若x，y=a，b（x=a y=b）(2)多重序元：多重序元：三元组：三

2、元组：x，y，z=x，y，z n元组：元组：x1，x2，x3，xn=x1,xn2 笛卡尔乘积笛卡尔乘积定义定义设设A，B为二个任意集合，若序偶的第为二个任意集合，若序偶的第一个成员（左元素）是一个成员（左元素）是A的一个元素，序偶的的一个元素，序偶的第二个成员（右元素）是第二个成员（右元素）是B的一个元素，则所的一个元素，则所有这样的序偶有这样的序偶构成构成的集合称为的集合称为A和和B的笛卡尔乘的笛卡尔乘积。积。记作：记作：A B=x，y|（x A）（y B）例：设例：设A=1，2，B=a，b，则：，则：A B=1，a,1，b,2，a,2，b B A=a，1,a，2,b，1,b，2 A B B

3、 A，即即“”是不满足交换律。是不满足交换律。例：设例：设A=a，b，B=1，2，C=z,则则:(A B)C=a,1,a,2,b,1,b,2 z =a,1,z,a,2,z,b,1,z,b,2,z A (B C)=a，b 1,z,2,z=a,1,z,a,2,z,b,1,z,b,2,z（A B）C A （B C）,“”不满足结合律。不满足结合律。定理定理若若A A，B B，C C是三个集合，则有：是三个集合，则有：A A（B CB C）=（A A B B）（A A C C）A A（B CB C）=（A A B B）（A A C C）（A BA B）C=C=（A A C C）（B B C C）（A

4、BA B）C=C=（A A C C）（B B C C）证明证明:A(B C)=(A B)(A C)证明：设证明：设是是A（B C）中的任一元素，则：）中的任一元素，则：A（B C）|x A y B C|x A y B y C|(x A y B)(x A y C)(A B)(A C)即即 A(B C)=(A B)(A C)例：设例：设A=1，B=1，2，C=2，3,则则 A（B C）=1 1，2，3 =1,1,1,2,1,3（A B）（A C）=1 1，2 1 2，3 =1,1,1,2,1,3 例：设例：设A=1，B=1，2，C=2，3,则：则：A（B C）=1 2=1,2（A B）（A C）=

5、1,1,1,2 1,2,1,3 =1,2 注：注：n个集合的笛卡儿乘积的定义个集合的笛卡儿乘积的定义：A2=A AA3=A A AAn=A A An个个A2 关系及其表示关系及其表示1 关系关系 定义：指事物之间（客体之间）的相互联系。定义：指事物之间（客体之间）的相互联系。在数学上关系可表达集合中元素间的联系。在数学上关系可表达集合中元素间的联系。序偶序偶a，b可以反映可以反映a，b二个元素之间具有某二个元素之间具有某 种关系。种关系。定义定义以序偶作为元素的任何集合是一个二元关系。以序偶作为元素的任何集合是一个二元关系。由定义可知：二元二元关系是一个集合。设设R表示二元关系，表示二元关系，

6、若若 R,用用 xRy 表示，表示，若若 R，则也可写成：，则也可写成：x R y。关系表示方法关系表示方法（1）枚举法（列举法）枚举法（列举法）例：二元关系例：二元关系R定义如下图：定义如下图：可用枚举法表示为：可用枚举法表示为：,4,3,2,1dcbaR（2 2）谓词公式表示法）谓词公式表示法 一个集合可用谓词公式来表达，所以二元关系一个集合可用谓词公式来表达，所以二元关系也可用谓词公式来表达。也可用谓词公式来表达。例：实数集合例：实数集合R R上的上的“”关系可表达为：关系可表达为：“”=”=)(|,yxRyRxyx（3 3）关系矩阵表示法）关系矩阵表示法 设二元关系设二元关系 R R

7、是是A B上的二元关系，上的二元关系，关系矩关系矩阵表示法描述如下：阵表示法描述如下：(a)(a)集合集合A A中的元素表示矩阵的行元素，集合中的元素表示矩阵的行元素，集合B B中的中的元素表示矩阵的列元素；元素表示矩阵的列元素；(b)(b)若若 R ，则在关系矩阵对应位置记上，则在关系矩阵对应位置记上“1”1”，否则记为，否则记为“0”0”。例：设例：设A=aA=a，b b，cc，B=1 B=1，3 3，44，R R1 1 是是ABAB上的上的二元关系，给出二元关系，给出R R1 1的关系矩阵的关系矩阵.R R1 1=abc134101110MR1=1102,1,2,1,2,1,2ccbba

8、aYXR例：设例：设X=aX=a，b b，cc，Y=1 Y=1，22，R R2 2 是是XYXY上上的二元关系，的二元关系，给出给出R R2 2的关系矩阵的关系矩阵.例：设例：设X=aX=a，b b，cc，Y=1 Y=1，22，R R3 3 是是X YX Y上的二元关系且上的二元关系且R R3 3=，给出给出R R3 3的关系矩阵的关系矩阵.例：设X=1，2，3，4，R R4 4 是是X X X X上的二元关上的二元关系系，给出，给出R R4 4的关系矩阵的关系矩阵.R4=100110M R4 =1110000000（4）关系图表示法）关系图表示法设设R为集合为集合XYXY上的二元关系，上的二

9、元关系，关系矩阵图表示法描述如下：关系矩阵图表示法描述如下：(a)把集合、中的元素以点的形式全部画在平面上；把集合、中的元素以点的形式全部画在平面上；(b)若若 R ，则在，则在x和和y之间画一带箭头弧线，其箭头指之间画一带箭头弧线，其箭头指向向y。反之不画任何联线。反之不画任何联线。例：设例：设X=1X=1，2 2，3 3，44，R R1 1 是是X X 上的二元关系，上的二元关系，给出给出R R1 1的关系图。的关系图。R1=.关系的前域和值域关系的前域和值域 定义定义设设R是一个二元关系，由是一个二元关系，由 R的所有序偶的的所有序偶的第一元素第一元素x组成的集合组成的集合dom R称称

10、R的前域的前域,即即),(|RyxyxdomR定义定义 R R的前域和值域的并集称做的前域和值域的并集称做R R的域的域,记做记做FLD R,FLD R,即即:FLD R=dom R:FLD R=dom R ran R ran R定义定义设设R是一个二元关系，由是一个二元关系，由 R的所有序偶的的所有序偶的第二元素第二元素y组成的集合组成的集合ran R称称R的值域的值域,即即,(|RyxxyranR例：例：X=1,2,3,4,5,6,Y=a,b,c,d,e,f,RX=1,2,3,4,5,6,Y=a,b,c,d,e,f,R为为X X到到Y Y的的二元关系二元关系.,4,3,2,1dcbaRdo

11、m R=1,2,3,4dom R=1,2,3,4ran R=a,b,c,dran R=a,b,c,dFLD R=1,2,3,4,a,b,c,dFLD R=1,2,3,4,a,b,c,d关系和笛卡尔乘积关系和笛卡尔乘积笛卡尔乘积的任何子集都可以定义一种二元关系。笛卡尔乘积的任何子集都可以定义一种二元关系。例：X=1,2,3,4，Y=1,2 2,41,1|,22yxYyXxyxS思考：思考：集合集合XY上可以产生多少种二元关系？上可以产生多少种二元关系？2,4,1,4,2,3,1,3,2,2,1,2,2,1,1,1YXS1,S2都是XY的子集，并且它们二元关系。S1=|x X y Y x y=三个

12、特殊关系：全域关系，空关系，恒等关系三个特殊关系：全域关系，空关系，恒等关系定义定义集合集合A2定义了定义了A集合中的一种关系，该关系集合中的一种关系，该关系称为称为 A中的全域关系，用中的全域关系，用EA表示：表示：,|,AEAAx yxA yA 例：例：A=1，2,则集合则集合A上的全域关系为：上的全域关系为：E EA A=定义定义空集也是空集也是 AxA的一个子集，它也定义了一的一个子集，它也定义了一种关系种关系,称为空关系，用称为空关系，用A表示。表示。例：例：A=1，2,则集合则集合A上的空关系为：上的空关系为：A=定义定义：集合：集合A A中的恒等关系，用中的恒等关系，用I IA

13、A表示：表示：思考：集合思考：集合A=1,2,R为为AXA上的恒等关系，则上的恒等关系，则R如如何表示？何表示？I IA A=|=|x x A A 例：例：A=1,2,3,4,则集合则集合A上的恒等关系为：上的恒等关系为：I IA A=3 关系的性质关系的性质自反性自反性根据根据R的关系矩阵和关系图，也可以判断的关系矩阵和关系图，也可以判断R是自反的。是自反的。定义定义 设是集合设是集合A A中的二元关系，对于任中的二元关系，对于任xA,R,xA,R,即即 x(xx(x A A RR），），则称是自反关系。则称是自反关系。思考：集合思考：集合A 上的恒等关上的恒等关系系IA与与R的自反性有什么

14、联的自反性有什么联系？系？001010110RM例：设A=a,b,c,R=是自反的。例：设X=1,2,3,1,22,11S2,12S1,23S000100000,000000010,000100010321SSSMMM2反自反性反自反性定义定义 设是集合设是集合A A中的二元关系，对于任中的二元关系，对于任xA,xA,R,R,即即 x(xx(x A A R R），），则称是反自反关系。则称是反自反关系。2,31,31,21,14S110100100RMS4既不是自反的，又不是反自反的既不是自反的，又不是反自反的思考：集合思考：集合A 上的恒等关系上的恒等关系IA与与R的反自反性有什么联系？的反

15、自反性有什么联系？3对称性对称性定义定义：设：设R是是A中的二元关系，对于每一个中的二元关系，对于每一个x x，yA,yA,如果如果每当有每当有xRy，则必有，则必有yRx，则称，则称R是是A中的对称关系中的对称关系.例：设例：设A=1,2,3,R=,则则R是对称的关系是对称的关系.010101110RM思考：思考：RC与与R的对称性有什么联系？的对称性有什么联系？x x y(xy(x A A y y A A xRy xRy yRxyRx）定义定义1：设：设R是是A集合中的二元关系，对于每一个集合中的二元关系，对于每一个x x，yA,yA,如果每当如果每当xRy和和yRx就必有就必有x=y，则

16、称，则称R是反对称的关系。是反对称的关系。4反对称性反对称性即当且仅当即当且仅当 x x y(xy(x A A y y A A xRy xRy yRx yRx x=yx=y）,R,R才是反才是反对称的。对称的。例：设例：设A=a,b,c，R=是反对称的。是反对称的。定义定义2：设：设R是是A集合中的二元关系，对于每一个集合中的二元关系，对于每一个x x，yAyA，如果如果xy且且xRy,则则 R R,称称R是反对称的关系。是反对称的关系。)(yRxxRyyxAyAxyx思考：思考：RC与与R的反对称性有什么联系？的反对称性有什么联系？例：设例：设A=a,b,c,R1,R2,R3都是反对称的都是

17、反对称的,1accbbaR,2ccbbaacaR,3accbaaR100001100,001010101,100001010321RRRMMM例：例：X=a,b,c,判断下列关系是否对称的，是否反对称的。判断下列关系是否对称的，是否反对称的。,1cbabbaR,2cabccbaaR010001101,00010101021RRMM这两个二元关系既不是对称的，也不是反对称的。这两个二元关系既不是对称的，也不是反对称的。5传递性传递性 思考：复合运算与思考：复合运算与R的传递性有什么联系？的传递性有什么联系？定义定义：设：设R R是是A A中的二元关系，对于每一个中的二元关系，对于每一个x x，y

18、 y，zA,zA,如如果每当果每当xRy xRy yRz,yRz,就必有就必有xRz,xRz,则称则称R R是可传递的，并表示成：是可传递的，并表示成：x x y y z(xz(x A A y y A A z z A A xRy xRy yRz yRz xRzxRz）例：设例：设X=a,b,c，判断下列关系是否满足传递性质。，判断下列关系是否满足传递性质。,1cbcabaaaR,2baR,3cabaR4R()x y z xAyAzAxRyyRzxRz 以上关系都满足传递性质。以上关系都满足传递性质。而二元关系而二元关系R5不具有传递性不具有传递性.,5accbbaR()x y z xAyAzA

19、xRyyRzxRz 例例:判断下列二元关系的性质。判断下列二元关系的性质。（1）设）设X=1,2,33,13,22,11R性质有：反自反，反对称，传递性质有：反自反，反对称，传递3,22,11,12R性质有：反对称性质有：反对称 3,32,21,13R性质有：自反，对称，反对称，传递性质有：自反，对称，反对称，传递 xER4性质有：自反，对称，传递性质有：自反，对称，传递 5R性质有：反自反，对称，反对称，传递性质有：反自反，对称，反对称，传递 性质有：自反，反自反，对称，反对称，传递性质有：自反，反自反，对称，反对称，传递 若X=,则X上的空关系具有什么性质？4 关系的运算关系的运算关系的复

20、合关系的复合定义定义：设 YX（R关系），关系），ZY（S关系），关系），于是可获得：于是可获得：ZX（RS）的关系，称的关系，称 RS为为R和和S的复合关系，并规定为：的复合关系，并规定为：),(|,SzyRyxYyyZzXxzxSR),(|,SzyRyxYyyZzXxzxSR例：设例：设A=1,2,3,4,5，R,S均为均为AA的关系，且的关系，且R=S=则则 R S=S R=讨论：讨论：（1）RS SR，因此因此“”是不可交换的。是不可交换的。（2）RS为新的二元关系，且为新的二元关系，且RS为X Z Z上的二元关系。上的二元关系。定理定理：设 WZYXRRR321则有：则有：32132

21、1321)()(RRRRRRRRR即即:关系的复合运算满足结合律关系的复合运算满足结合律.定义定义给定集合给定集合X，R是是X中的二元关系，设中的二元关系，设 Nn于是于是R的的n次幂次幂)(nR可以定义成：可以定义成：RRRnn)1()(,Ra bb cc a,cbaX 例：例：多个相同的二元关系多个相同的二元关系R 复合复合(3)(2),xRRRa ab bc cI (2),RR Ra cb ac b 复合运算的矩阵表示：复合运算的矩阵表示：设有三个集合：设有三个集合：ZYXzzzZyyyYxxxXSRpnm,212121nmikRaM而而|X|=m,|Y|=n,|Z|=p，则关系矩阵：，

22、则关系矩阵：pnkjSbMpmijSRcMSRSRMMM)(1kjiknkijbac例：设例：设X=1,2,3,R,S均是均是X中的二元关系，中的二元关系，R=,S=0 1 00 1 01 0 0MR=0 1 10 0 11 0 0MS=（0 0）（1 0）（0 1）=00 0 10 0 10 1 1MRS=2逆关系逆关系 定义定义:设设X,Y是二个集合，若是二个集合，若R是是XY的关系，从的关系，从YX的的关系，称为关系，称为R的逆关系，用的逆关系，用,|,RyxxyR表示，或用表示，或用 cR表示。表示。例：例：X=0,1,2，R=110100001,100001011RRMMR=2逆关系

23、逆关系 讨论定义：讨论定义：（1）只要将）只要将R中每一个序偶中的元素全部调换位置，就可得到中每一个序偶中的元素全部调换位置，就可得到R的的逆关系逆关系。（2）R的关系矩阵为的关系矩阵为 RM的转置矩阵；的转置矩阵；（3）在）在R的关系图中，只要把所有箭头改换方向就可得到的关系图中，只要把所有箭头改换方向就可得到的关系图。（自回路箭头改变与否无关）的关系图。（自回路箭头改变与否无关）R定理定理设 ZYXSR，则可有：，则可有：RSSR RSSR同样 xRSzxRyySz)(xSRzzSRxySzxRy)()(证明：对于任一证明：对于任一 ZzYyXx,来讲，若有来讲，若有 R SSR同理可证同

24、理可证SRRSR一定是对称的一定是对称的 定理定理:设设R是集合是集合X中的二元关系，当且仅当中的二元关系，当且仅当RR则则R才是对称的。才是对称的。证明：充分性：证明：充分性：R是对称的是对称的 RR对于任一对于任一 RbaRabRba,RR必要性：必要性：RRR是对称的，是对称的，RR对任一对任一 RabRbaRba,定理：给定集合定理：给定集合X,Y,YXSRRR,21，于是可有：，于是可有：RR)1(SRSR)2(SRSR)3(XYYX)4()6(2121)5(RRRR3.闭包运算闭包运算定义定义：给定集合：给定集合X，R是是X中的二元关系，若有另一中的二元关系，若有另一关系关系R满足

25、下列条件：满足下列条件：（1）R 是自反的（对称，可传递的）；是自反的（对称，可传递的）；（2）RR则称则称R是是R的自反（对称，传递的）闭包，的自反（对称，传递的）闭包，并依次用并依次用r(R),s(R),t(R)来表示。来表示。4关系的运算关系的运算RR，则 RR（3）对于任一自反（对称，传递的）关系）对于任一自反（对称，传递的）关系 ，若，若 R 例：设例：设A=1,2,3，R为为AA的关系，且的关系，且R=R=具有自反性质具有自反性质RRR=具有具有自反性质自反性质RR RR R是包含是包含R的具有自反性质的的具有自反性质的最小最小的二元关系的二元关系讨论定义：讨论定义：（1）已知一个

26、集合中的二元关系）已知一个集合中的二元关系R，则，则r(R),s(R),t(R)是是包含包含R的具有自反（对称，传递）性质的的具有自反（对称，传递）性质的最小最小的二元关系的二元关系,它它们是们是唯一唯一的；的；（2）若）若R不是自反（对称，传递）的，则我们可以补上不是自反（对称，传递）的，则我们可以补上最少最少序偶，使之变为自反、对称、传递关系，从而得到序偶，使之变为自反、对称、传递关系，从而得到r(R),s(R),t(R)；定理定理：给定集合：给定集合X，R是是X中的二元关系，于是可有：中的二元关系，于是可有：（1）当且仅当）当且仅当r(R)=R，则，则R是自反的；是自反的；（2）当且仅当

27、）当且仅当s(R)=R，则，则R是对称的；是对称的；（3）当且仅当）当且仅当t(R)=R，则，则R是可传递的。是可传递的。该定理说明：若该定理说明：若R是自反（对称，传递）的，则是自反（对称，传递）的，则r(R),s(R),t(R)就是就是R本身。本身。xI定理定理：R是是X中的二元关系中的二元关系,是是X中的恒等关系，中的恒等关系，则有则有 xIRRr)(证明：按定义证：证明：按定义证：（1）设设 xIRR，则，则R是自反的，是自反的，（3）设有任一包含）设有任一包含R的二元关系的二元关系R也是自反的，即也是自反的，即则 )(RRIRRxRRIRx RR)2(xIRR 例：设例：设X=a,b

28、,c,R=，求，求r(R)解：解：r(R)=,ccbbaaaccbbaIRx定理定理：给定集合：给定集合X，R是是X中的二元关系，则有中的二元关系，则有 RRRS)(例：设例：设X=a,b,c,R=，求，求s(R)s(R)=,caacbccbabbaRR 定理定理：设：设X是一集合，是一集合，R是是X中的二元关系，则：中的二元关系，则：(2)()1(),()iit RRRU RiI例：例：X=a,b,c,R=，|X|=3,计算计算t(R)(2)(3)(2)(4)(3),=,=RR Ra cb ac bRRRa ab bc cRRR R,)()3()2(ccbbaabcabcaaccbbaRRR

29、Rt例：例：X=a,b,c,d,R=,计算t(R)4()3()2(,RdaRdbcaR,)()4()3()2(dadbcadccbbaRRRRRt定理定理：设：设|X|=n，R是是X中的二元关系，则中的二元关系，则)()2()(kRRRRt)0(nK 例：设例：设X=a,b,R=，求，求r(R),s(R),t(R)r(R)=s(R)=t(R)=R定理定理：设：设X是一集合，是一集合，R是是X中的二元关系，则有：中的二元关系，则有：r(S(R)=S(r(R)r(t(R)=t(r(R)S(t(R)t(S(R)证明：r(s(R)()xr RRRRI()()xxRIRI()()xxRIRI()()()

30、r Rr RSr Rr(S(R)=S(r(R)例：设例：设X=a,b,c,R=（1）rs(R)=r=sr(R)=s=（2）rt(R)=r=tr(R)=t=（3）ts(R)=t=st(R)=S=5 覆盖与划分覆盖与划分定义定义：给定一非空集合，又设：给定一非空集合，又设 若若（1）),2,1(,miSAi（2）miiSA1则称则称A为为S的覆盖。的覆盖。例：例：S=a,b,c，A=a,b,b,c，B=a,a,b,c，C=a,b,c，D=a,b,a,c 集合集合A,B,C,D都为都为S的覆盖。的覆盖。12,miAAAAA，定义定义：给定一非空集合：给定一非空集合S，设非空集合，设非空集合 12,m

31、iAA AAA，如果有：如果有：),2,1(,)1(miSAimiiSA1)3(jiAA)2(（i,j=1,2,m）则称集合则称集合A是集合是集合S的一个划分。的一个划分。例：例：S=a,b,c，A=a,b,c，B=a,c,b，C=a,b,c，D=a,b,c 集合集合A,B,C,D都为都为S的划分。的划分。讨论定义：讨论定义：（2）划分）划分A中的元素，称为划分的类，在定义中中的元素，称为划分的类，在定义中 mAAA21,都是都是A中的一个类，类的个数称为划分的秩；中的一个类，类的个数称为划分的秩；（1）集合的划分一定是一个覆盖，而覆盖不一定是划分；）集合的划分一定是一个覆盖，而覆盖不一定是划

32、分；（3）集合）集合S上的秩最大的划分称最大划分，最小的称最小划分。上的秩最大的划分称最大划分，最小的称最小划分。例：设例：设S=a,b,c，下列，下列 iA均为均为S的一个划分：的一个划分：,1cbaA 类有二个类有二个a,b,c,秩为秩为2；,2cbaA 类有二个类有二个a,b,c,秩为秩为2；,3bcaA 类有二个类有二个a,c,b,秩为秩为2；,4cbaA 秩为秩为3；类有三个类有三个a,b,c,5cbaA 秩为秩为1。类有一个类有一个a,b,c,所以所以A4 是最大划分，是最大划分，A5 是最小划分是最小划分定义定义：设：设A和和A是非空集合是非空集合S的二种划分，并可表示成：的二种

33、划分，并可表示成：,1miiAAnjjAA1若若A的每一个类的每一个类 jA都是都是A的某一个类的某一个类 iA的子集，则称划分的子集，则称划分A是划分是划分A的加细，的加细，或讲或讲A加细了加细了A，若，若A加细了加细了A且且 AA 则称则称A是是A的真加细。的真加细。例：例：S=a,b,c,d,S的划分：的划分：A=a,b,c,d,A=abc,d，则，则A是是A的真加细的真加细 A=abcd,则则A 是是A的真加细的真加细 定义定义：设：设X是一个集合，是一个集合，R是是X中的二元关系，若中的二元关系，若R是是自反自反的，的，对称对称的和的和可传递可传递的，则称的，则称R是等价关系。是等价

34、关系。例：实数集合上的例：实数集合上的“=”关系（相等）为等价关系关系（相等）为等价关系6 等价关系等价关系试验证试验证R是等价关系，是等价关系，画出画出R的关系图，列出的关系图，列出R的关系矩阵的关系矩阵 解：（解：（1）R=（2）R的关系矩阵和关系图的关系矩阵和关系图 1 0 0 10 1 0 00 0 1 01 0 0 1RMR满足自反、对称和传递性质，满足自反、对称和传递性质，R是等价关系是等价关系例：设例：设A=1,2,3,4，R是是A集合上的二元关系集合上的二元关系,|,3xyRx yx yA 为整数为整数定义定义：设：设 ImIyx,若若myx 为整数，为整数，则称则称x模模m等

35、于等于y，记作：，记作：)(mod myx R=|，则，则R是一个等价关系。是一个等价关系。)(mod myx 定理定理：任何集合：任何集合 AI，R是集合是集合A中的关系，中的关系，mI，例：设例：设A=0，1，2，3，6，R=x,y|xy(x,yA)yx(mod 3)，计算计算domR和和ranR。定义定义：设：设R是是A集合中的等价关系，对于任何的集合中的等价关系，对于任何的 Ax来讲，可把集合来讲，可把集合 AxR规定成：规定成：|xRyAyyxR并称是由并称是由 Ax生成的生成的R等价类。等价类。RRddcc,RRbbaa,例：设例：设A=a,b,c,d,R是是A中的等价关系，中的等

36、价关系，R=（1）AxR（2）Rx（3）若）若 Ax，则，则 Rxx（4）对于所有的）对于所有的 Ayx,，或者，或者 RRyx或者或者 RRyx（5）XxRAx定理定理：设：设A是一个非空集合，是一个非空集合，R是是A中的等价关系，则中的等价关系，则例：设例：设X=N，关系，关系R=)3(mod|,yxXyXxyx是一等价关系，是一等价关系，则则R可以找出三个等价类：可以找出三个等价类：R0=0，3，6，9R 1=1，4，7，10R2=2，5，8，11定理定理：设：设A是一非空集合，是一非空集合，R是是A中的等价关系，中的等价关系，R等价类的集合等价类的集合xR|x A是是A的一个划分，且此

37、集合的一个划分，且此集合称为称为A关于关于R的商集，用的商集，用 RA表示之。例：设例：设A=x1,x2.xn（1）A集合中的全域关系集合中的全域关系:AAR1是一个等价关系，是一个等价关系，1,RxA xA X关于关于R1的商集的商集1|,|11RAAxxRAR它形成了它形成了A的一个最小划分的一个最小划分（2）A中的恒等关系中的恒等关系 xIR 2|22AxxRAR221RnRxx),(21Axxxn它形成了它形成了A的一个最大划分的一个最大划分 定理定理：X是一非空集合，是一非空集合，A为为X的一个划分，且的一个划分，且A=A1,A2,.An，则由，则由A导出的导出的X中的一个等价关系中

38、的一个等价关系)(1iiniAAR例：例：Xa,b,c,d，A=a,b,c,d则则 R(a,b a,b)(c,d c,d)=,因此：集合因此：集合X上的等价关系与上的等价关系与X的划分之间有一一对应关系。的划分之间有一一对应关系。定义定义：设：设X是一个集合，是一个集合，R是是X中的二元关系，若中的二元关系，若R是是自反的，对称的自反的，对称的，则称，则称R是是相容关系相容关系。n 由定义知由定义知,等价关系是具有等价关系是具有传递性传递性的相容关系的相容关系;相容关相容关 系是一个比等价关系更为普遍的关系。系是一个比等价关系更为普遍的关系。7 相容关系相容关系因为相容关系是自反和对称的因为相

39、容关系是自反和对称的,其关系矩阵是对称的且其关系矩阵是对称的且主对角线元素全为主对角线元素全为1,因此我们可仅用下三角矩阵因此我们可仅用下三角矩阵T来表来表示和存储就够了示和存储就够了,即关系矩阵可以简化为即关系矩阵可以简化为“阶梯形阶梯形”。EX：设：设A=cat,teacher,cold,desk,knife,byR=x,y|x,y A 且且 x和和y至少有一个相同的字母至少有一个相同的字母nR 是是 A上的一个相容关系上的一个相容关系,简记简记 A 中元素依次为中元素依次为x1,x2,x3,x4,x5,x6,则则R的关系矩阵的关系矩阵MR和对应简化的下三角矩阵和对应简化的下三角矩阵TR为

40、：为：111000111110111100011110010110000001RM111111011101011000001RTcatteacher cold desk knife bycat teacher cold desk knife byEX：在相容关系的关系图上，每个顶点都有：在相容关系的关系图上，每个顶点都有自回路自回路且每两个顶点且每两个顶点间的弧线都是间的弧线都是成对出现成对出现的。为简化相容关系的关系图的。为简化相容关系的关系图,不画自回路不画自回路,并用无箭头的单线段代替来回弧线并用无箭头的单线段代替来回弧线,使之成为无向图。上例的关系使之成为无向图。上例的关系图如下图如下

41、:x1x2x3x4x5x6定义定义1：设：设R是集合是集合A上的相容关系上的相容关系,若若C A,若任意若任意a,b C,有有aRb,则称则称C是由是由R产生的相容类。产生的相容类。例如上例的相容关系例如上例的相容关系R可产生相容类可产生相容类x1,x2，x1,x3，x2,x3，x6，x2,x4,x5，等等。，等等。对于前三个相容类，都能加进新的元素组成新的相容类，而对于前三个相容类，都能加进新的元素组成新的相容类，而后两个相容类，加入任一新元素，就不能组成相容类，我们后两个相容类，加入任一新元素，就不能组成相容类，我们称它为最大相容类。称它为最大相容类。x3x2x1求最大相容类的方法：求最大

42、相容类的方法：关系图法：画出简化相容关系的关系图后，先确定结点最多的完关系图法：画出简化相容关系的关系图后，先确定结点最多的完全多边形，以后逐次减少。全多边形，以后逐次减少。最大完全多边形最大完全多边形:每个顶点都与其他所有顶点相联结的多边形。每个顶点都与其他所有顶点相联结的多边形。(1)一个结点的最大的完全多边形；一个结点的最大的完全多边形；(2)二个结点的最大完全多边形；二个结点的最大完全多边形；(3)三个结点的最大完全多边形；三个结点的最大完全多边形；(4)四个结点的最大完全多边形；四个结点的最大完全多边形；(5)五个结点的最大完全多边形五个结点的最大完全多边形;最大完全多边形最大完全多

43、边形例：已知相容关系图，求出最大相容类例：已知相容关系图，求出最大相容类5,45,23,24,3,14321XXXX4,35,4,16,5,2,1321XXX最大相容类集合为：最大相容类集合为：121,3,42,32,54,5,1,2,5,61,4,53,4SS完全覆盖：设有完全覆盖：设有 集合集合 A 上的相容关系上的相容关系 R，其中最大相容，其中最大相容类的集合，称作集合类的集合，称作集合 A 的完全覆盖。的完全覆盖。定理：定理：A 上的每个相容关系，唯一的定义一个完全覆盖。上的每个相容关系，唯一的定义一个完全覆盖。最大相容类：最大相容类：b,g,f,e，b,a,e，b,c，d该集合的完

44、全覆盖为：该集合的完全覆盖为：b,g,f,e，b,a,e，b,c，d gabcdef偏序关系偏序关系n偏序关系及基本概念偏序关系及基本概念n哈斯图哈斯图n特殊元素特殊元素n其它序关系其它序关系 定义定义：设：设 A 是一个集合，如果是一个集合，如果A上的关系上的关系 R，满足自反性，反对，满足自反性，反对称性和传递性，则称称性和传递性，则称 R 是是 A上上 的偏序关系，记作的偏序关系，记作“”.nEX1：在实数集：在实数集 Z上，小于等于关系是偏序关系吗？上，小于等于关系是偏序关系吗？nEX2：在实数集：在实数集Z上，小于关系是偏序关系吗？上，小于关系是偏序关系吗？nEX3：设集合：设集合A

45、的幂集的幂集 (A)上的包含关系是偏序关系吗？上的包含关系是偏序关系吗？nEX4：正整数：正整数 I+集合上的整除关系是偏序关系吗？集合上的整除关系是偏序关系吗？偏序关系及基本概念偏序关系及基本概念1 1、偏序关系定义、偏序关系定义 表示表示偏序关系偏序关系,如果如果 ,则记作则记作x y,读作读作“小于等于小于等于”.注意注意:这里的这里的“小于等于小于等于”不是指数的大小不是指数的大小,而是指而是指 偏偏 序序 关系中元素的顺序性关系中元素的顺序性.不同的偏序关系对不同的偏序关系对 有不同的序解释有不同的序解释.例如例如:正整数正整数I+集合上的整除关系是偏序关系集合上的整除关系是偏序关系

46、,3 6的的含义是含义是3整除整除62 2、偏序集定义、偏序集定义定义：定义：集合集合A和和A上的偏序关系合在一起叫做偏序集上的偏序关系合在一起叫做偏序集,记作记作例如例如:实数集合实数集合Z和数的小于等于关系和数的小于等于关系 构成偏序集构成偏序集 集合集合A的幂集的幂集P(A)和包含关系和包含关系 构成偏序集构成偏序集正整数正整数 I+集合和整除关系构成偏序集集合和整除关系构成偏序集哈斯图哈斯图(Hasse Diagram)是偏序关系的关系图，要画出哈斯图，是偏序关系的关系图，要画出哈斯图，需要先定义偏序集中顶点之间的盖住关系。需要先定义偏序集中顶点之间的盖住关系。COV A=|xA yA

47、y盖住盖住x定义定义：在偏序集：在偏序集中，对中，对A上任意元素上任意元素x和和y,若有若有 x y和x y，且没有其它元素z,满足x z且且z y,则称元素则称元素y盖住盖住x。盖住集。盖住集(盖住关系盖住关系)记为：记为：3、盖住集、盖住集(盖住关系盖住关系)说明：给定偏序集说明：给定偏序集，它的盖住集，它的盖住集(盖住关系盖住关系)是唯一的。是唯一的。例：设例：设A=2，3，4，6，8，则定义在，则定义在A上的整除关系上的整除关系R=，求，求COV A 按照盖住集定义分析得：按照盖住集定义分析得：COV A =COV A=|xA yAy盖住盖住x定义定义：在偏序集合：在偏序集合A，中，对

48、中，对A上任意元素上任意元素x和和y,若有若有 x y和x y，且没有其它元素z,满足x z且且z y,则称元素则称元素y盖住盖住x.盖住集盖住集(盖住关系盖住关系)记为：记为：4、分析研究盖住集、分析研究盖住集(盖住关系盖住关系)定义定义结论：结论：(1)盖住集中不存在任何序偶盖住集中不存在任何序偶且且xA(2)若存在其它元素z，满足x z且且z y，可通过复合运算获，可通过复合运算获得序偶得序偶(3)通过复合运算获得的序偶通过复合运算获得的序偶不属于盖住集。不属于盖住集。定义定义:设设R是集合是集合A上的偏序关系，上的偏序关系，IA是集合是集合A上的恒等关系，上的恒等关系，R1=R-IA,

49、则则R1-(R1 o R1)为盖住集为盖住集COV A。以上所给的盖住集定义是立足于集合运算的观点以上所给的盖住集定义是立足于集合运算的观点,应用此应用此等价定义判定偏序关系的盖住集等价定义判定偏序关系的盖住集,不仅有条理不仅有条理,而且步骤清而且步骤清晰。晰。可从以下几步求盖住集可从以下几步求盖住集:(1)计算计算R1=R-IA(2)将将R1 与其自身复合与其自身复合,得集合得集合R2,即即 R2=R1 o R1(3)计算集合计算集合R1 和和R2 的差的差,则盖住集为则盖住集为:COV A=R1-R2 5、盖住集、盖住集(盖住关系盖住关系)的等价定义的等价定义例：设例：设A=2，3，4，6

50、，8，则定义在，则定义在A上的整除关系上的整除关系R=，求，求COV A 解解:IA=R1=R-IA=R2=R1 o R1=COV A=R1 R2=例例 设集合设集合A=a,b,c,d,e,R 是是A 上的偏序关系。上的偏序关系。R=,求求盖住集盖住集COV A。解解:IA=R1=R-IA=R2=R1 o R1=COV A=R1 R2=偏序集偏序集的哈斯图画法的哈斯图画法:(1)用小圆圈代表用小圆圈代表集合集合A中的元素中的元素(2)若若x y且且x y,则将则将x画在画在y的下方的下方(3)若若COV A,就用一条线段连接就用一条线段连接x和和y 给定偏序集给定偏序集A，它的盖住集是唯一的。