1、第四章第四章 关关 系系第三节第三节 关系类型关系类型一、等价关系一、等价关系v集合中的各个元素总是具有某些有用的性质，时常不是把这些元集合中的各个元素总是具有某些有用的性质，时常不是把这些元素作为单一的个体，逐个地对待它们；而是按它们所具有的性质素作为单一的个体，逐个地对待它们；而是按它们所具有的性质进行分类，并根据这些性质处理它们，或者是使用它们。在处理进行分类，并根据这些性质处理它们，或者是使用它们。在处理实际问题时，可以不去考察那些不感兴趣的性质，而专注于感兴实际问题时，可以不去考察那些不感兴趣的性质，而专注于感兴趣的某些性质。凡是具有同样性质的元素，可以看成是不可区分趣的某些性质。凡
2、是具有同样性质的元素，可以看成是不可区分的或相互等价的，也称它们之间存在等价关系。的或相互等价的，也称它们之间存在等价关系。第三节第三节 关系类型关系类型一、等价关系一、等价关系v定义：定义：设设R是集合是集合A上的二元关系，上的二元关系，若若R是是和和，则称则称R是是A上的上的。若若 R，或者，或者xRy，称，称x等价等价y，记做，记做xy等价关系等价关系因为因为R是自反的，因此是自反的，因此R的关系图中每个结点都有有向环的关系图中每个结点都有有向环因为因为R是对称的，因此是对称的，因此R的关系图中的有向弧都是成对出的关系图中的有向弧都是成对出现，即若有从现，即若有从a到到b的弧，必定有从的
3、弧，必定有从b到到a的弧的弧(任意两个结任意两个结点间或没有弧连接，或有成对的弧出现点间或没有弧连接，或有成对的弧出现)。因为因为R是传递的，因此若有从是传递的，因此若有从a到到b的弧以及从的弧以及从b到到c的弧，的弧，必定有从必定有从a到到c的弧的弧等价关系等价关系例例4.3.1 同学集合同学集合A=a, b, c, d, e, f，A中的关系中的关系R是是“住住在同一个房间在同一个房间”。问：。问：R是等价关系吗？是等价关系吗？答：是。答：是。1) 任何一个人都和自己住在同一房间，因此任何一个人都和自己住在同一房间，因此R是是2) 若若x和和y住在同一房间（即住在同一房间（即xRy），则）
4、，则y和和x也住在同也住在同一房间（即一房间（即yRx），因此），因此R是是3) 若若x和和y住在同一房间住在同一房间(xRy)，并且，并且y和和z住在同一房间住在同一房间(yRz)，则，则x和和z住在同一房间住在同一房间(xRz)，因此，因此R是是等价关系等价关系假设假设a和和b住在同一房间，住在同一房间，d和和e和和f住在同一房间，住在同一房间，c住一间。则住一间。则R=,关系图为：关系图为：abcefd等价关系等价关系整数集合整数集合Z中的相等关系、中的相等关系、在全集在全集U所有子集的集合中的相等关系，所有子集的集合中的相等关系，以及命题演算中的命题集合的以及命题演算中的命题集合的关系
5、等关系等都是等价关系都是等价关系空集上的任意二元关系空集上的任意二元关系R是等价关系是等价关系等价关系等价关系v定义：定义：设设m是一个正整数，是一个正整数，a和和b都是整数，若存在某整数都是整数，若存在某整数k，使得使得，则称，则称，记为，记为m叫作等价的叫作等价的等价关系等价关系v定理：定理：。证明：如果证明：如果A= ，那么模，那么模m等价是等价是A上的等价关系。上的等价关系。若若A ，设任意，设任意a,b,c A，将模，将模m等价记为等价记为R1) 因为因为 a a = 0m，因此，因此R是是2) 假设有假设有aRb，则存在一个整数，则存在一个整数k，使得，使得a-b=km，则则b-a
6、=-km，所以有，所以有bRa，所以，所以R是是3) 假设有假设有aRb和和bRc，则存在整数，则存在整数p和和q，使得，使得a-b=pm，b-c=qm，所以，所以a-c=(a-b)+(b-c)=(p+q)m因此因此R是是综上所述，综上所述，。等价类等价类v定义：定义：设设R是非空集合是非空集合A上的等价关系，对于任意上的等价关系，对于任意a A，令，令 称称，简称，简称a的等价类，简记为的等价类，简记为a。称。称a为为aR的的。（。（aR称为元素称为元素a形成的形成的R的等价类）的等价类）若等价类个数有限，则若等价类个数有限，则R的不同等价类的个数叫作的不同等价类的个数叫作。对于任意对于任意
7、a A ， aR非空，因为非空，因为a aR按照按照R等价类的定义，是由集合等价类的定义，是由集合A中与中与a有等价关系有等价关系R的的所有元素，构成集合所有元素，构成集合aR。常用。常用a代替代替aR因此，任给集合因此，任给集合A及其上的等价关系及其上的等价关系R，必可写出，必可写出A上各个元素的等价类上各个元素的等价类等价等价类类例例4.3.2 设设A=a,b,c,d,e,f, R=, , ,，则等价关系，则等价关系R的关系图是：的关系图是：abcefd等价关系等价关系R的等价类如下：的等价类如下：aR = bR = a, b， cR = c dR = eR = fR = d, e, f等
8、价关系等价关系R的秩是的秩是3等价等价类类例例4.3.3 若若R是整数集合是整数集合Z上的模上的模4等价关系，则等价类有：等价关系，则等价类有：0R = , -8, -4, 0, 4, 8, = 4R = -4R = 1R = , -7, -3, 1, 5, 9, = 5R = -3R = 2R = , -6, -2, 2, 6, 10, = 6R = -2R = 3R = , -5, -1, 3, 7, 11, = 7R = -1R = 每个等价类中的元素互相等价。每个等价类中的元素互相等价。若若R是整数集合是整数集合Z上的模上的模2等价关系，则等价类有等价关系，则等价类有0R = , -4
9、, -2, 0, 2, 4, = 2R = -2R = 1R = , -3, -1, 1, 3, 5, = 3R = -1R = 等价类等价类v定理定理1：设：设R是非空集合是非空集合A上的等价关系，对于任意上的等价关系，对于任意a,b A证明：证明：1) ，则，则a a=b，所以所以bRa， 根据根据R的对称性，可知的对称性，可知2)，对于任意对于任意x a，有有aRx，所以也有，所以也有xRa根据根据R的传递性，可知有的传递性，可知有xRb；根据；根据R的对称性，可知有的对称性，可知有bRx则则x b，所以，所以a b同理可证：对于任意同理可证：对于任意x b有有x a，即，即b a所以：
10、所以： xRa xRb等价类等价类v定理定理2：设：设R是非空集合是非空集合A上的等价关系，对于任意上的等价关系，对于任意a,b A证明：假设证明：假设a b ，则存在某个，则存在某个x A，有，有 x a b x a x b aRx bRx aRx xRb aRb与与 R矛盾。因此矛盾。因此a b = 。v也就是说，也就是说，等价类等价类v定理定理3：设：设R是非空集合是非空集合A上的等价关系，对于任意上的等价关系，对于任意a,b A证明：证明：1) 对任意的对任意的x a，可知，可知x A，所以，所以 a Aa Aa A2) 对任意的对任意的x A，有，有x x，所以，所以x a。因此因此
11、A aa Aa A所以：所以： a = Aa A等价类等价类v定理定理4：设：设R1和和R2是非空集合是非空集合A上的等价关系，那么上的等价关系，那么证明：证明： ，则对于任意，则对于任意a A，有，有aR1 = x|aR1x= x|aR2x= aR2 ，则有：，则有： x|aR1x= x|aR2x则对于任意则对于任意x A和和a A ，有，有aR1x x aR1 x aR2 aR2x因此因此R1=R2 集合的划分和覆盖集合的划分和覆盖 定义：定义：若把一个集合若把一个集合A分成若干个叫做分块的非空子集，使得分成若干个叫做分块的非空子集，使得A中每个元素至少属于一个分块，那么这些分块的全体构成
12、的集中每个元素至少属于一个分块，那么这些分块的全体构成的集合叫做合叫做A的一个的一个覆盖覆盖。如果。如果A中每个元素属于且仅属于一个分块，中每个元素属于且仅属于一个分块，那么这些分块的全体构成的集合叫做那么这些分块的全体构成的集合叫做A的一个的一个划分划分。 等价定义：等价定义：令令A为给定非空集合，为给定非空集合， B=A1, A2, , An (Ai A)，Ai 且且 Ai=A，则集合，则集合B称作称作A的覆盖；的覆盖； 若除上述条件外，另有若除上述条件外，另有Ai Aj= (i j)则称则称B是是A的划分的划分划分划分i = 1n划分划分v利用非空集合利用非空集合A及其上的等价关系，及其
13、上的等价关系，可以构造一个新的集合：可以构造一个新的集合：。v定义：设定义：设A是非空集合，若是非空集合，若B=A1, A2, , An (Ai A) 且且Ai Ai Aj= (i j) Ai=A则称则称B是是A的的，称，称B中的元素为中的元素为A的的。若划分是有限的，则若划分是有限的，则|B|称为划分的称为划分的。i = 1n划分划分例例4.3.4 设设S = 1, 2, 3A= 1,2, 2,3 B= 1, 1,2, 1,3 C= 1, 2,3 D= 1,2,3 E= 1, 2, 3 F= 1, 1,2 问：哪些是问：哪些是S的划分？秩是多少？的划分？秩是多少？1,2 2,3 1 1,2
14、1,3 1 1,2 1 1,2 A划分划分例例4.3.4 设设S = 1, 2, 3A= 1,2, 2,3 B= 1, 1,2, 1,3 C= 1, 2,3 D= 1,2,3 E= 1, 2, 3 F= 1, 1,2 划分划分例例4.3.5 将一张纸撕成几片，则所得的碎片的集合将一张纸撕成几片，则所得的碎片的集合就是该纸的一个划分，该划分的秩就是碎片的张数就是该纸的一个划分，该划分的秩就是碎片的张数集合族集合族 x, -x|x 整数集合整数集合Z 是是Z的一个划分，的一个划分，其秩是无限的其秩是无限的自己尝试举出几个属于划分的例子。（课后思考）自己尝试举出几个属于划分的例子。（课后思考）商集商
15、集v定义：设定义：设A是非空集合，是非空集合，R是是A上等价关系，上等价关系，R的所有等价类集合的所有等价类集合 是是A的划分，称为的划分，称为，也叫作，也叫作A模模Rv定理：设定理：设R1和和R2是是A的等价关系，则的等价关系，则该定理说明：该定理说明：A上的等价关系可以诱导出上的等价关系可以诱导出A的划分，且是唯一的。的划分，且是唯一的。反之，反之，A的划分也可以诱导出的划分也可以诱导出A上的等价关系上的等价关系商集商集A/R是以是以R的所有等价类为元素的集合的所有等价类为元素的集合商集商集A/R就是就是A的一个划分，并且不同的商集对应于不同的划分的一个划分，并且不同的商集对应于不同的划分
16、商集商集v定理：设定理：设B=A1, A2, , An是非空集合是非空集合A上的任意划分，上的任意划分， 则则A的二元关系的二元关系或或是是A上的等价关系。上的等价关系。证明：证明：1) 因为对于任意一个因为对于任意一个a A，都有，都有aRa，因此，因此2) 假设有假设有aRb，那么存在某块，那么存在某块Ai ，使得，使得a Ai且且b Ai ，因此有，因此有bRa，所以，所以。3) 假设有假设有aRb，并且有，并且有bRc，则存在，则存在Ai和和Aj ，使得，使得a,b Ai且且b,c Aj，根据划分的定义可知，或者，根据划分的定义可知，或者Ai Aj或者或者AiAj，因此因此 AiAj，
17、因此有，因此有a,c Ai，因此有，因此有aRc，因此，因此。所以：所以：R是是A上的等价关系。上的等价关系。设集合设集合A有一个划分有一个划分B，现定义一个关系，现定义一个关系R，aRb当且当且仅当仅当a，b在同一分块中在同一分块中(a与与a在同一分块中，故在同一分块中，故aRa)若若a与与b在同一分块中，在同一分块中，b与与a也必须在同一分块中，也必须在同一分块中，即：即：aRb bRa若若a与与b在同一分块中，在同一分块中，b与与c在同一分块中，因为：在同一分块中，因为：Ai Aj=，即，即b属于且仅属于一个分块，故属于且仅属于一个分块，故a，c同块同块即：即：aRb bRc aRc商集
18、商集例例4.3.6 试给出试给出A=a,b,c上的所有等价关系上的所有等价关系解：解：A的所有划分为：的所有划分为：B1=a,b,cB2=a,b,cB3=a,c,bB4=b,c,aB5=a,b,c偏序关系偏序关系二、偏序关系二、偏序关系 在一个集合上，我们常常要考虑元素的次序关系，其中很重在一个集合上，我们常常要考虑元素的次序关系，其中很重要的就是偏序关系要的就是偏序关系v定义：定义：设设R是非空集合是非空集合A上的二元关系，上的二元关系，若若R是是，则称则称R是是A上的上的。称称为偏序集为偏序集偏序关系偏序关系v若若R是偏序，偏序集是偏序，偏序集常记为常记为v若若R是是A上的偏序，则上的偏序
19、，则R-1也是也是A上的偏序。上的偏序。若用若用 表示表示R，则用，则用 表示表示R-1 v和和都是偏序集都是偏序集注意：注意： 偏序关系偏序关系例例4.3.7 v是偏序集合，这里的是偏序集合，这里的“”表示小于等于关系表示小于等于关系v是偏序集合，这里的是偏序集合，这里的“ ”表示集合间的包含关系表示集合间的包含关系vA=2, 3, 6，D代表整除关系，代表整除关系，M代表整倍数关系，则代表整倍数关系，则D=,，M=,和和都是偏序集合都是偏序集合偏序关系偏序关系v定义：设定义：设R是非空集合是非空集合A上的偏序关系上的偏序关系 a, b A， a, b A，a b读作读作“a小于小于b”，它
20、是指在偏序中，它是指在偏序中，a排在排在b前边前边v可见，在偏序集可见，在偏序集中，对于中，对于 a, b A ，有，有a b或或b aa = b a 和和 b不可比不可比偏序关系偏序关系例例4.3.8 A=1, 2, 3， 是是A上的整除关系，则有上的整除关系，则有1 2， 1 31 = 1，2 = 2，3 = 32 和和 3 不可比不可比哈斯图哈斯图v定义：定义：设设为偏序集，对于为偏序集，对于 a, b A，若，若ab且不存在且不存在c A，使，使acb，则称，则称v偏序集可以用关系图来表示，但一般习惯用偏序集可以用关系图来表示，但一般习惯用表示。图中仅画出符合条件表示。图中仅画出符合条
21、件“”的有序对的有序对，则则图中没有回路图中没有回路（ ）图中不含传递性所蕴涵的边图中不含传递性所蕴涵的边（）图中没有成对的有向边图中没有成对的有向边（）图中每条弧都向上画，略去箭头图中每条弧都向上画，略去箭头哈斯图哈斯图例例4.3.8 A=1, 2, 3， 是是A上的整除关系，则有上的整除关系，则有 = , ,关系图为：关系图为：123 中满足中满足“b盖住盖住a”的有序对是：的有序对是： ,哈斯图为：哈斯图为：123哈斯图哈斯图例例4.3.7 A=2, 4, 6, 8，D代表整除关系，则代表整除关系，则D=, ,，的关系图为：的关系图为：D 中满足中满足“b盖住盖住a”的有序对是：的有序对
22、是： , , 哈斯图为：哈斯图为：24682468哈斯图哈斯图例例4.3.9 A=1, 2, 3,4， 是是A上的小于等于关系，上的小于等于关系，的哈斯图为：的哈斯图为：2134A=2, 3, 6, 12, 24, 36 是是A上的整除关系，上的整除关系，的哈斯图为：的哈斯图为：326362412偏序关系偏序关系v定义：设定义：设为偏序集，为偏序集，B A，若若( x)( x B b x)为真，称为真，称b为为B的的若若( x)( x B x b)为真，称为真，称b为为B的的若若 ( x)( x Bbxx b)为真，称为真，称b为为B的的若若 ( x)( x Bbxb x)为真，称为真，称b为
23、为B的的偏序关系偏序关系v最小最小(大大)元是元是B中最小中最小(大大)的与其他元素都可比的元素，的与其他元素都可比的元素，最小最小(大大)元不一定存在，若存在则必唯一。元不一定存在，若存在则必唯一。v极小极小(大大)元不一定与元不一定与B中所有元素都可比，中所有元素都可比，只要没有比它小只要没有比它小(大大)的元素即可。的元素即可。极小极小(大大)元一定存在，而且可能有多个。元一定存在，而且可能有多个。v若若B中仅有一个极小中仅有一个极小(大大)元，则它一定是元，则它一定是B的最小的最小(大大)元。元。偏序关系偏序关系例例4.3.7 A=2, 4, 6, 8，D代表整除关系，则代表整除关系，
24、则D=, ,，的关系图为：的关系图为：B的极小元：的极小元：B的极大元：的极大元：B的最小元：的最小元：B的最大元：的最大元：24, 6 (8不在不在B中中)2无无B=2, 4, 62468偏序关系偏序关系例例4.3.9 A=1, 2, 3,4， 是是A上的小于等于关系，上的小于等于关系，的哈斯图为：的哈斯图为：2134A=2, 3, 6, 12, 24, 36 是是A上的整除关系，上的整除关系，的哈斯图为：的哈斯图为：B的极小元：的极小元：B的极大元：的极大元：B的最小元：的最小元：B的最大元：的最大元：B的极小元：的极小元：B的极大元：的极大元：B的最小元：的最小元：B的最大元：的最大元：
25、1414224224B=1, 3, 4B=2, 6, 12, 24326362412偏序关系偏序关系v定义：设定义：设为偏序集，为偏序集，B A，若若( x)( x B b x)为真，称为真，称b为为B的的若若( x)( x B x b)为真，称为真，称b为为B的的若若b是一个下界，且对每一个是一个下界，且对每一个B的下界的下界b都有都有b b，称称b为为B的的或或，记为，记为glb(B)若若b是一个上界，且对每一个是一个上界，且对每一个B的上界的上界b都有都有b b，称称b为为B的的或或，记为，记为lub(B)偏序关系偏序关系例例4.3.7 A=2, 4, 6, 8，D代表整除关系，则代表整
26、除关系，则D=, ,，的关系图为：的关系图为：B的上界：的上界：B的下界：的下界：B的最小上界：的最小上界：B的最大下界：的最大下界：无无2无无2B=2, 4, 62468若若b是一个上界，且对每一个是一个上界，且对每一个B的上界的上界b都有都有b b ，称，称b为为B的的偏序关系偏序关系例例4.3.9 A=1, 2, 3,4， 是是A上的小于等于关系，上的小于等于关系，的哈斯图为：的哈斯图为：2134B=2, 3B的上界：的上界：B的下界：的下界：B的最小上界：的最小上界：B的最大下界：的最大下界：3, 42, 132若若b是一个上界，且对每一个是一个上界，且对每一个B的上界的上界b都有都有
27、b b ，称，称b为为B的的偏序关系偏序关系例例4.3.9 A=2, 3, 6, 12, 24, 36 是是A上的整除关系，上的整除关系，的哈斯图为：的哈斯图为：B=2, 6, 12B的上界：的上界：B的下界：的下界：B的最小上界：的最小上界：B的最大下界：的最大下界：12, 24, 362122326362412若若b是一个上界，且对每一个是一个上界，且对每一个B的上界的上界b都有都有b b ，称，称b为为B的的偏序关系偏序关系vB的最小的最小(大大)元一定是元一定是B的下的下(上上)界界而且是而且是B的最大下界的最大下界(最小上界最小上界) 而而B的下的下(上上)界不一定是界不一定是B的最
28、小的最小(大大)元元vB的上界、下界、最小上界和最大下界都可能不存在的上界、下界、最小上界和最大下界都可能不存在若存在，最小上界和最大下界是唯一的。若存在，最小上界和最大下界是唯一的。最小最小(大大)元是元是B中最小中最小(大大)的与其他元素都可比的与其他元素都可比极小极小(大大)元不一定与元不一定与B中所有元素都可比中所有元素都可比若若b是一个上界，且对每一个是一个上界，且对每一个B的上界的上界b都有都有b b ，称，称b为为B的的偏序关系偏序关系例例4.3.10 A=2, 5, 6, 10, 15, 30， 是是A上的整除关系，上的整除关系， B=A=2, 5, 6, 10, 15, 30
29、523015610B的极小元：的极小元：B的最小元：的最小元：B的下界：的下界：B的最大下界：的最大下界：B的极大元：的极大元：B的最大元：的最大元：B的上界：的上界：B的最小上界：的最小上界：2, 5无无无无无无30303030全序关系全序关系v定义：定义：设设为偏序集，若对于任意为偏序集，若对于任意 a, b A，a与与b都是可比的，即都是可比的，即 则称为则称为A上的上的（线序关系）（线序关系）称称为为（或线序集、链）（或线序集、链）v可知，全序集的哈斯图为一竖立的结点序列，可知，全序集的哈斯图为一竖立的结点序列，所有结点位于竖线上所有结点位于竖线上良序关系良序关系v定义：定义：设设为全
30、序集，若为全序集，若，则称则称为为A上上，称，称为为v每一个有限的全序集都是良序集每一个有限的全序集都是良序集良序关系良序关系v全序集全序集整数集合整数集合I, 小于等于关系小于等于关系是良序集吗？是良序集吗？vA=x|x是整数，并且是整数，并且-1x1，那么那么是良序集吗？是良序集吗？v若若A=x|x是实数，并且是实数，并且-1x1那么那么是良序集吗？是良序集吗？相容关系相容关系三、相容关系三、相容关系v定义：定义：设设R是集合是集合A上的二元关系，若上的二元关系，若R是是，则称则称R是是A上的上的。相容关系相容关系例例4.3.12设设Aa, b, c, d，R=,可以验证，可以验证，R是是
31、A上的相容关系。其关系矩阵为：上的相容关系。其关系矩阵为：1 1 1 11 1 1 11 1 1 01 1 0 1MR=由于由于R的自反性，因此的自反性，因此MR的主对角线的主对角线上都是上都是1又由于又由于R是对称的，因此可以简化为：是对称的，因此可以简化为：bcd 1 1 1a b c 1 1 0相容关系相容关系例例4.3.12设设Aa, b, c, d，R=,可以验证，可以验证，R是是A上的相容关系。其关系图为：上的相容关系。其关系图为：bacd由于由于R的自反性，的自反性，因此每个结点都有有向环因此每个结点都有有向环因此可以把关系图简化因此可以把关系图简化将有向环取消将有向环取消相容关
32、系相容关系例例4.3.12设设Aa, b, c, d，R=,可以验证，可以验证，R是是A上的相容关系。其关系图为：上的相容关系。其关系图为：bacd由于由于R的自反性，的自反性，因此每个结点都有有向环因此每个结点都有有向环因此可以把关系图简化因此可以把关系图简化将有向环取消将有向环取消相容关系相容关系例例4.3.12设设Aa, b, c, d，R=,可以验证，可以验证，R是是A上的相容关系。其关系图为：上的相容关系。其关系图为：bacd由于由于R的对称性，的对称性，因此每条有向边都成对出现因此每条有向边都成对出现因此可以把关系图简化因此可以把关系图简化用一条无向边代替两条有向边用一条无向边代替
33、两条有向边相容关系相容关系例例4.3.12设设Aa, b, c, d，R=,可以验证，可以验证，R是是A上的相容关系。其关系图为：上的相容关系。其关系图为：由于由于R的对称性，的对称性，因此每条有向边都成对出现因此每条有向边都成对出现因此可以把关系图简化因此可以把关系图简化用一条无向边代替两条有向边用一条无向边代替两条有向边bacd相容关系相容关系v定义：定义：设设A是非空集合，且是非空集合，且B=A1, A2, , An (Ai A) ，若若 Ai = A，则称，则称B为为A的的显然，显然，i = 1n相容关系相容关系v定义：定义：设设R是非空集合是非空集合A上的相容关系，上的相容关系，C
34、A，若对，若对C中任意两中任意两元素元素a,b有有aRb，则称，则称C是由是由R产生的产生的例例4.3.12设设Aa, b, c, d，R=,R可以产生相容类：可以产生相容类： a, b, c, d, a, b, a, c, a, d, b, c, b, d, a, b, c, a, b, d相容关系相容关系v定义：定义：设设R是非空集合是非空集合A上的相容关系，上的相容关系，C是是R产生的相容类，产生的相容类，若若A-C中的元素没有与中的元素没有与C中所有元素都有相容关系，中所有元素都有相容关系，则称则称C为为R的的，记为，记为相容关系相容关系例例4.3.12设设Aa, b, c, d，R=
35、,R可以产生相容类：可以产生相容类： a, b, c, d, a, b, a, c, a, d, b, c, b, d, a, b, c, a, b, d其中最大相容类是：其中最大相容类是： a, b, c, a, b, d前前9个相容类都能加进新的元素组成新的相容类，个相容类都能加进新的元素组成新的相容类，而对于最后两个相容类来讲，加入任一新元素就而对于最后两个相容类来讲，加入任一新元素就不再组成相容类，我们称它为最大相容类不再组成相容类，我们称它为最大相容类相容关系相容关系v定义：定义：设设R是非空集合是非空集合A上的相容关系，其最大相容类集合称为上的相容关系，其最大相容类集合称为集合集合
36、A的的，记为，记为对于相容关系对于相容关系R，只能对应唯一的完全覆盖，只能对应唯一的完全覆盖相容关系相容关系v利用关系矩阵构成最大相容类：利用关系矩阵构成最大相容类：例例4.3.13 已知关系已知关系R的关系矩阵，试给出的关系矩阵，试给出R的所有最大相容类的所有最大相容类1 1 0 1 01 1 0 1 10 0 1 0 01 1 0 1 10 1 0 1 1MR=由于相容关系的性质，只考虑：由于相容关系的性质，只考虑：dcbedc1a 0 1 0 1 1b 0 0 0 1相容关系相容关系v利用关系矩阵构成最大相容类：利用关系矩阵构成最大相容类：例例4.3.13 已知关系已知关系R的关系矩阵，
37、试给出的关系矩阵，试给出R的所有最大相容类的所有最大相容类 ，能够分别单独构成最大相能够分别单独构成最大相容类，因此可以从矩阵中容类，因此可以从矩阵中删除这些元素删除这些元素R的最大相容类：的最大相容类：cc与其他任何元素都没有相容关系与其他任何元素都没有相容关系dcbedc1a 0 1 0 1 1b 0 0 0 1相容关系相容关系v利用关系矩阵构成最大相容类：利用关系矩阵构成最大相容类：例例4.3.13 已知关系已知关系R的关系矩阵，试给出的关系矩阵，试给出R的所有最大相容类的所有最大相容类 由简化的矩阵由简化的矩阵开始向左扫描，发现开始向左扫描，发现1时，时，以相应的行号和列号组成以相应的
38、行号和列号组成一相容类一相容类c与其他任何元素都没有相容关系与其他任何元素都没有相容关系dbed1a 1 1 1b 0 1c与其他任何元素都没有相容关系与其他任何元素都没有相容关系dbed1a 1 1 1b 0 1生成的相容类：生成的相容类：d, eR的最大相容类：的最大相容类：c相容关系相容关系v利用关系矩阵构成最大相容类：利用关系矩阵构成最大相容类：例例4.3.13 已知关系已知关系R的关系矩阵，试给出的关系矩阵，试给出R的所有最大相容类的所有最大相容类 ，发现，发现1时，时，以相应的行号和列号组成相以相应的行号和列号组成相容类，并检查是否可以与之容类，并检查是否可以与之前生成的相容类合并
39、前生成的相容类合并c与其他任何元素都没有相容关系与其他任何元素都没有相容关系dbed1a 1 1 1b 0 1c与其他任何元素都没有相容关系与其他任何元素都没有相容关系dbed1a 1 1 1b 0 1R的最大相容类：的最大相容类：c生成的相容类：生成的相容类：d, e , b, d, b, e合并成合并成 b, d, e相容关系相容关系v利用关系矩阵构成最大相容类：利用关系矩阵构成最大相容类：例例4.3.13 已知关系已知关系R的关系矩阵，试给出的关系矩阵，试给出R的所有最大相容类的所有最大相容类 向左继续扫描，发现向左继续扫描，发现1时，时，以相应的行号和列号组成相以相应的行号和列号组成相
40、容类，并检查是否可以与之容类，并检查是否可以与之前生成的相容类合并前生成的相容类合并c与其他任何元素都没有相容关系与其他任何元素都没有相容关系dbed1a 1 1 1b 0 1R的最大相容类：的最大相容类：c生成的相容类：生成的相容类：b, d, e, a, b, a, d, b, d, e, a, b, d合并成合并成a, b, d相容关系相容关系v定理：定理：例例4.3.14， a,b,c, b和和a,b,b,c,a,c都都是是A的覆盖，它们可以产生相同的相容关系的覆盖，它们可以产生相同的相容关系R a,b,c也是也是A的覆盖，它产生相容关系的覆盖，它产生相容关系S 相容关系相容关系v定理
41、：定理：v定理：定理：。准序关系准序关系四、准序关系四、准序关系v定义：定义：设设R是集合是集合A上的二元关系，若上的二元关系，若R是是，则称则称R是是A上的上的（拟序关系）。（拟序关系）。通常记为通常记为 称称 A, 为为例如，实数集合上的例如，实数集合上的关系和集合族中的关系和集合族中的 关系都是准序关系关系都是准序关系准序关系准序关系v定理：定理：。证明：设对于证明：设对于 x, y A，同时有，同时有xRy和和yRx，根据准序关系的，根据准序关系的传递性，可知必有传递性，可知必有xRx。而而R是反自反的，与是反自反的，与xRx矛盾，故同时有矛盾，故同时有xRy和和yRx为假，为假，故故 xRyyRx x=y为真。为真。因此因此R是反对称的是反对称的之前给出过定理：之前给出过定理：准序关系准序关系v定理：定理：设设R是非空集合是非空集合A上的关系上的关系若若R是准序关系，则是准序关系，则 r(R) = R IA是偏序关系。是偏序关系。若若R是偏序关系，则是偏序关系，则 R - IA是准序关系。是准序关系。证明：证明：P82
