集合与关系节课件.ppt

《集合与关系节课件.ppt》由会员分享，可在线阅读，更多相关《集合与关系节课件.ppt（87页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、集合与关系节第1页，此课件共87页哦第三章 集合与关系3.4 序偶与笛卡尔积3.5 关系及其表示3.6 关系的性质3.7 关系的运算（复合关系和逆关系）3.8 关系的闭包运算3.9 相容关系与覆盖3.10 等价关系与划分3.12 偏序关系第2页，此课件共87页哦2023/4/112023/4/113-4 序偶与笛卡尔积n 关系理论历史悠久。它与集合论、数理逻辑、组合学、图论和布尔代数都有密切的联系。n关系是日常生活以及数学中的一个基本概念，例如：n兄弟关系，师生关系、位置关系、大小关系、等于关系、包含关系等。第3页，此课件共87页哦2023/4/112023/4/113-4 序偶与笛卡尔积n另

2、外，关系理论还广泛用于计算机科学技术，如n计算机程序的输入、输出关系；n数据库的数据特性关系；n数据结构本身就是一个关系等。n在某种意义下，关系是有联系的一些对象相互之间的各种比较行为。第4页，此课件共87页哦2023/4/112023/4/113-4 序偶与笛卡尔积n 序偶与笛卡尔积n上,下；左，右；34；中国地处亚洲；平面上点的坐标（x,y）等。n特征：成对出现、具有一定的顺序。n定义由两个元素x,y按照一定的次序组成的二元组称为有序偶对(序偶),记作,其中x为第一个元素，y为第二个元素。第5页，此课件共87页哦2023/4/112023/4/11n用序偶表示下列语句中的次序关系n(1)平

3、面上点A的横坐标是x,n 纵坐标是y,其中x,yR；n(2)成都是四川的省会；n(3)英语课本在书桌上；n(4)左，右关系。解 各语句的序偶表示如下：(1)，x,yR；(2)；(3)；(4)。第6页，此课件共87页哦2023/4/112023/4/11n定义6.2.2 给定序偶和，n 如果a=c，b=d，则=。1.序偶可以看作是具有两个元素的集合，2.但是序偶中的两个元素具有确定的次序。即但是a,b=b,a.第7页，此课件共87页哦2023/4/112023/4/11N重有序组定义由n个元素a1,a2,a3,an按照一定次序组成的n元组称为n重有序组(n-Type)(Vector)，记作:n例

4、用n重有序组描述下列语句。n（1）中国四川成都电子科技大学计算机学院；n（2）2006年9月10日18点16分25秒；n（3）16减5再加3除以7等于2。解各语句的n重有序组表示如下：（1）（2）；（3）。定义给定n重有序组和。如 果ai bi(i 1,2,，n)，则=。第8页，此课件共87页哦2023/4/112023/4/11笛卡尔乘积定义 设A，B是两个集合，称集合：AB|(xA)(yB)为集合A与B的笛卡尔积DescartesProduct)。注意：（1）集合A与B的笛卡儿积AB仍然是集合；（2）集合AB中的元素是序偶，序偶中的第一个元素取自A，第二个元素取自B。第9页，此课件共87页

5、哦2023/4/112023/4/11例n设A=a,B=b,c,C=,D=1,2，请分别写出下列笛卡儿积中的元素。n（1）AB,BA；（2）AC,CA；n（3）A(BD),(AB)D。n解 根据笛卡儿积的定义，有n（1）AB=,BA=,；n（2）AC=,CA=；第10页，此课件共87页哦2023/4/112023/4/11解（续）n（3）因为BD=,，n所以A(BD)=a,a,na,a,。n同理，(AB)D=,1,2,n,1,2。第11页，此课件共87页哦2023/4/112023/4/11注意n由例我们可以看出：n（1）笛卡儿积不满足交换律；n（2）AB=当且仅当A=或者B=；n（3）笛卡儿

6、积不满足结合律；n（4）对有限集A,B，有|AB|=|BA|=|A|B|。第12页，此课件共87页哦2023/4/112023/4/11集合相等两个集合互相包含等式成立两个集合相等定理n设A,B,C是任意三个集合，则n（1）A(BC)=(AB)(AC)；n（2）(BC)A=(BA)(CA)；n（3）A(BC)=(AB)(AC)；n（4）(BC)A=(BA)(CA)。分析显然，待证等式两端都是集合第13页，此课件共87页哦2023/4/112023/4/11定理 分析对（1）A(BC)=(AB)(AC)A(BC)(AB)(AC),(AB)(AC)A(BC)利用按定义证明方法，首先叙述包含关系的定

7、义，即首先叙述A(BC)(AB)(AC)的定义：对任意A(BC)，有(AB)(AC)，则A(BC)(AB)(AC)。同理可分析(AB)(AC)A(BC)。第14页，此课件共87页哦2023/4/112023/4/11定理 证明n（1）对任意A(BC)，n由笛卡儿积的定义知，xA且yBC；n由并运算定义知，yB或者yC。n于是有xA且yB或者xA且yC。n从而，AB或者AC。n即(AB)(AC)，n所以，A(BC)(AB)(AC)。第15页，此课件共87页哦2023/4/112023/4/11定理 证明（续）另一方面，对任意(AB)(AC)，由并运算定义知,AB或者AC。由笛卡儿积的定义知,xA

8、且yB或xA且yC。进一步有xA且yBC，从而A(BC)。所以(AB)(AC)A(BC)。于是，根据定理1.2.2，有A(BC)=(AB)(AC)。(2)、(3)和(4)的证明作为练习，自证。第16页，此课件共87页哦2023/4/112023/4/11定理n设A,B,C,D是任意四个集合，则(AB)(CD)AC，BD。n证明 充分性()：n对任意AB，有xA且yB。n又因为AC，BD，所以有xC且yD，即nCD，从而(AB)(CD)。第17页，此课件共87页哦2023/4/112023/4/11定理 证明（续）n必要性()：n对任意的xA，yB，有AB。n又因为(AB)(CD)，所以CD。n

9、根据笛卡儿积的定义有xC且yD，从而nAC，BD。n综上所述，定理成立。第18页，此课件共87页哦定理：定理：若C，则AB(AC B C)(C A C B)第19页，此课件共87页哦2023/4/112023/4/11定义n设A1,A2,An是n个集合，称集合nA1A2Ann =|(aiAi)i1,2,3,nn为集合A1,A2,An的笛卡儿积(DescartesProduct)n当A1=A2=An=A时，有A1A2An=An。第20页，此课件共87页哦2023/4/112023/4/11n当集合A1,A2,An都是有限集时，n|A1A2An|=|A1|A2|An|。第21页，此课件共87页哦日

10、常生活中，大家熟知一些常见关系,例：家庭集合，有父子关系、兄弟关系等。全校同学作为一个集合，有同班关系，同组关系。把任一序偶的集合确定了一个二元关系R,R中任一序偶可记作R或aRb,不在R中的序偶可记作R例：一组同学为集合A，A有4名同学，其中1，2同寝室，3，4同寝室。则：R=，反映了同寝室关系，3-5 关系及其表示第22页，此课件共87页哦 关系及其表示 定义定义 设A，B是任意两个集合，AB的子集R称为 从A到B的二元关系，当A=B 时，称R为A上的二元关系。从上述定义可以看出A到B的二元关系，也是序偶的集合。若 R，则称a与b有关系R，记作a R b。若 ，则称a与b没有关系R，记作

11、。例如：设A=a,b,c,d,B=0,1，则R=a,0,b,0,c,1 就是一个从A到B的二元关系。第23页，此课件共87页哦：AB的子集叫做A到B上的一个二元关系。：A1A2A3的子集叫做A1A2A3上的一个二元关系。:A1A2An的子集叫做A1A2An上的一个n元关系。:AAA A的子集叫做A上的n元关系。关系及其表示 第24页，此课件共87页哦 关系及其表示 定义定义 设A，B是两个集合，R是从A到B上的二元关系，则 (1)若存在bB，使得R，则所有这样的aA组成的集合，称为二元关系R的定义域。记作dom(R)或D(R)，即 (2)若存在aA，使得 R，则所有这样的bB组成的集合，称为二

12、元关系R的值域。记作ran(R)或R(R)，即 R的定义域和值域一起称作R的域，记作FLDR，即FLDR=dom(R)ran(R)从X到Y的二元关系R，也可以用图解的方式表示，X和Y是两个集合。xi是集合X中的元素，yj是集合Y中的元素，当且仅当xiRyj时，才有一条从xi指向yj的有向边。第25页，此课件共87页哦 关系及其表示图 4.1.1 图解表示法第26页，此课件共87页哦例例 设设R1=|（x，y Z）(x y)R2=|（x，y Z）(y=2x+1)R3=|（x，y Z）(|x|=|y|=5)都是定义在整数集都是定义在整数集Z上的关系，求他们的定义域，值域和域。上的关系，求他们的定义

13、域，值域和域。解：解：dom R1=Z，ran R1=Z，fld R1=Z；dom R2=Z，ran R2=2y+1|y Z，fld R2=Z；dom R3=5，-5，ran R3=5，-5，fld R3=5，-5。例例 设设R=，则，则解：解：domR=1，2，4 ranR=2，3，4 fldR=1，2，3，4第27页，此课件共87页哦定义 设R是AA A的子集，若R=,则称R为A的空关系。若R=AAA,则称R为A的全域关系。R=|xA称为A上恒等关系，记为IA 关系及其表示-几个特殊关几个特殊关系系第28页，此课件共87页哦 关系及其表示 定理定理 若R和S是从集合A到B上的两个二元关系，

14、则R和S的并、交、补、差也是A到B上的二元关系。证明：因为R和S是从集合A到B上的二元关系 所以有R AB，S AB。从而有 即AB和AB都是A到B上的二元关系。又因为 所以R和S也是A到B上的二元关系。由于 故R-S也是A到B上的二元关系。第29页，此课件共87页哦 关系的矩阵表示 设 X=a,b,c,Y=0,1,2,3，R=,。可得关系R的矩阵表示如下：由上例看出，给定从有限集X到Y的二元关系R，就可以构造出它的关系矩阵。给定两个有限集合 和 ，并且R是从X到Y的二元关系。如果有 则称矩阵 是R的关系矩阵，并记作 。第30页，此课件共87页哦例例 设设X=x1，x2，x3，x4，Y=y1，

15、y2，y3。X到到Y的关系的关系R为为R=，。则。则R的关系矩阵是的关系矩阵是 例例 设设A=1，2，3，4，A上的大于关系上的大于关系“”定义为定义为n=，。则关系的关。则关系的关系矩阵是系矩阵是集合集合A中元素的排序是中元素的排序是1，2，3，4，即，即1对应第对应第1行、第行、第1列，例如列，例如就就是第是第2行与第行与第1列相交处的点，依此类推。列相交处的点，依此类推。第31页，此课件共87页哦关系及其表示-关系的图形表示 设画出R的关系图。解：R的关系图如图所示。R的关系图 第32页，此课件共87页哦 3-6 关系的性质 定义定义3.6.1 设R是集合A上的二元关系。若对任意一个aA

16、，都有aRa，即 R，则称R是自反的。即R是自反的 。也就是说，在自反关系中，每个元素都和自己有关系。例如，设R是整数集上的关系，则R是自反的。因为对于任意一个整数a，都有aa成立。定义定义3.6.2 设R是集合A上的二元关系。若对任意一个aA,都有 ，即 ，则称R是反自反的。即R是反自反的 。也就是说，在反自反关系中，每个元素都和自己没有关系。例如，设R是整数集上的 关系，则R是反自反的。因为对于任意整数a，都有a a 不成立。一个关系不是自反的，不一定就是反自反的。同样，一个关系不是反自反的，也不一定就是自反的。例如：在集合 上定义的二元关系 既不是自反的也不是反自反的。第33页，此课件共

17、87页哦 3-6 关系的性质 定义定义3.6.3 设R是集合A上的二元关系。若对任意的a,bA，当R时，就有 R，则称R是对称的。即 R是对称的 例如，平面上各三角形集合中，三角形的相似关系是对称的。定义定义3.6.4 设R是集合A上的二元关系。若对任意的a,bA，当R且 R时，有a=b，则称R是反对称的。即 R是反对称的 上述定义也可表述为：对任意的a,bA，若R且a b，则 。例如，在A的幂集中各元素之间的关系是反对称的。实数集合上的关系也都是反对称的。值得注意的是，存在既是对称的又是反对称的二元关系。如，恒等关系就是对称关系，同时也是反对称关系。又如 ，R既是对称的，也是反对称的。也有既

18、不是对称的，又不是反对称的关系存在！第34页，此课件共87页哦 3-6 关系的性质 定义定义3.6.5 设R是集合A上的二元关系。若对任意的a,b,c A，当R且R时，就有R，则称R是传递的。即 R是传递的 在判定关系的传递性时，要对所有的有序对都检查之后，才能判断一个关系的传递性是否成立，因此，判断传递性是比较复杂的。例如，设 ，则关系R满足传递性。例 在所有人集合P上的关系 ，说明R的性质。解：R是自反的，因为每个人和自己有同一祖先；R是对称的，因为如果甲和乙有同一祖先，那么乙和甲也有同一祖先；R是传递的，因为若甲和乙有同一祖先，乙和丙有同一祖先，那么甲和丙也有同一祖先。第35页，此课件共

19、87页哦 3-6 关系的性质 判别关系的性质，也可以从关系矩阵和关系图上给予验证。（1）若关系是自反的，当且仅当在关系矩阵中，对角线上的所有元素都是1；在关系图上，每个节点都有一条自己到自己的边（或称圈）。（2）若关系是反自反的，当且仅当关系矩阵中对角线上的元素都为零；在关系图中，每个节点都没有自己到自己的边。（3）若关系是对称的，当且仅当其关系矩阵是对称的；在关系图上，任意两个节点间若有弧，必定是成对出现的。（4）若关系是反对称的，当且仅当关系矩阵以主对角线为对称的元素不能同时为1，且在关系图上两个不同节点间的弧不能成对出现。第36页，此课件共87页哦任何集合上的相等关系实数集合上的小于等于

20、关系非空集合上的空关系基数大于1的集合上的全域关系xRy(x-y)/2是整数自反性反自反性对称性反对称性传递性Y N Y Y Y Y N N N Y N YYY YYNYNYYNYNY举举 例例第37页，此课件共87页哦 3-7关系的运算(复合关系和逆关系)定义定义4.3.14.3.1 设R是从集合X到集合Y的二元关系，如果将R中每一对序偶的元素顺序互换，所得到的新的集合则称为R的逆关系，记作 ，即 由逆关系的定义可知，的关系图可以通过将R的关系图的所有有向弧逆转得到，它的关系矩阵可以通过将R的关系矩阵转置得到。例4.3.1 设 ，求 。解：。第38页，此课件共87页哦 3-7关系的运算(复合

21、关系和逆关系)定理定理 设R和S都是从X到Y的二元关系，则下列各式成立。（1）（2）（3）（4），这里R表示（5）（6）若 ，则 第39页，此课件共87页哦3-7关系的运算(复合关系和逆关系)定理定理 设R是A上的二元关系，则（1）R在A上是自反的，当且仅当 。（2）R在A上是反自反的，当且仅当 。（3）R在A上是对称的，当且仅当 。（4）R在A上是反对称的，当且仅当 。第40页，此课件共87页哦3-7 关系的运算(复合关系和逆关系)定义定义 设R是从集合X到集合Y的二元关系，S是从集合Y到Z的关系，则R S称为R和S的合成关系，定义为 R S称为关系的合成运算。设R是从集合 到集合 的关系，

22、S是从集合 到集合 的关系，则 是一个 的矩阵，是一个 的矩阵。依照普通矩阵乘法的运算，可以定义两个关系矩阵的合成运算。第41页，此课件共87页哦 3-7 关系的运算(复合关系和逆关系)由上述前两个矩阵可以构造这两个矩阵的合成矩阵，记作 。元素 可由下式得到：其中 。和的运算规则如下：两个关系的合成运算，就是将布尔关系矩阵做乘法，所得结果即为合成关系矩阵。第42页，此课件共87页哦3-7 关系的运算(复合关系和逆关系)定理定理 设X,Y,Z和W都是集合。R是从集合X到Y的关系，S是从集合 Y到Z的关系，T是从集合Z到W的关系。于是有(R S)T=R (S T)即关系的合成运算满足结合律。n 证

23、明：对任意的(R S)T，根据合成关系的定义可知，必然存在zZ，使得(R S)，T。又因为(R S)，故必存在yY，使得 R并且 S。由 S且 T，根据合成关系的定义知(S T)，又因为 R且 S T，得到 R (S T)。故由的任意性可知(R S)T R (S T)。n 同理可证R (S T)(R S)T。n 综上所述，得到(R S)T=R (S T)，即关系的合成运算满足结合律。一般来说，关系的合成运算是不满足交换律的，即R S S R。第43页，此课件共87页哦3-7 关系的运算(复合关系和逆关系)定义定义 设R是集合X中的二元关系，nN（N是自然数集），于是R的n次幂 定义为：（1），

24、即 是R中的恒等关系。（2）。定理定理 设R是集合X中的二元关系。设m,nN。则有（1）（2）第44页，此课件共87页哦3-7 关系的运算(复合关系和逆关系)n定理：设T为A到B的关系，S为B到C的关系，证明：第45页，此课件共87页哦3-7 关系的运算(复合关系和逆关系)定理定理 设A为含有n个元素的集合，R是A上的二元关系，则必存在s和t，使得 定理定理 设R是A上的二元关系，则R在A上是传递的，当且仅当 第46页，此课件共87页哦 例题设R是A上的一个二元关系，（1）如果R是自反的，则Rc一定是自反的吗？（2）如果R是对称的，则Rc一定是对称的吗？（3）如果R是传递的，则Rc一定是传递的

25、吗？(4)如果R是反自反的，则Rc一定是反自反的吗？(5)如果R是反对称的，则Rc一定是反对称的吗？第47页，此课件共87页哦3.8 关系的闭包运算 定义定义3.8.1 3.8.1 设R是集合A上的二元关系。如果有另一A上的关系R 满足：（1）R是自反的；（2）R R；（3）对A上的任意自反关系R，若RR，则RR。那么称R是R的自反闭包，并记作r(R)。定义定义3.8.2 3.8.2 设R是集合A上的二元关系。如果有另一A上的关系R满足：（1）R是对称的；（2）R R；（3）对A上的任意对称关系R，若 RR，则RR。那么称R是R的对称闭包，并记作s(R)。定义定义3.8.3 3.8.3 设R是

26、集合A上的二元关系。如果有另一A上的关系R满足：（1）R是传递的；（2）R R；（3）对A上的任意对称关系R，若 RR，则RR。那么称R是R的传递闭包，并记作t(R)(也记作R+)。第48页，此课件共87页哦3.8 关系的闭包运算 定理3.8.1 设R是集合A上的二元关系，则：(1)自反闭包(2)对称闭包 （3）传递闭包 特别地，若 则 例3.8.1 设X=1,2,3，R是X中的二元关系，R=,。求r(R)、s(R)和t(R)第49页，此课件共87页哦3.8 关系的闭包运算求关系R的传递闭包t(R)(也就是R+)的Warshall算法：(1)置新矩阵A:=MR(2)置i:=1(3)对所有j如果

27、Aj,i=1,则对k=1,2,n Aj,k:=Aj,k+Ai,k(4)i:=i+1(5)如果in，则转到步骤(3),否则停止。第50页，此课件共87页哦3.8 关系的闭包运算 定理定理3.8.2 设R是集合A上的二元关系，则 （1）R是自反的，当且仅当r(R)=R；（2）R是对称的，当且仅当s(R)=R；（3）R是传递的，当且仅当t(R)=R。定理定理3.8.3 设R是集合A上的二元关系，则 （1）若R是自反的，则s(R)和t(R)也是自反的。（2）若R是对称的，则r(R)和t(R)也是对称的。（3）若R是传递的，则r(R)也是传递的。第51页，此课件共87页哦3.8 关系的闭包运算 定理定理

28、3.8.4 3.8.4 设R1和R2是集合A上的二元关系，且 ，则 （1）（2）（3）二元关系的闭包仍然是二元关系，还可以求它的闭包。例如，R是A上的二元关系，r(R)是它的自反闭包，还可以求r(R)的对称闭包。r(R)的对称闭包记为s(r(R)，简记为sr(R)，读作R的自反闭包的对称闭包。其余类似。定理定理3.8.53.8.5 设R是集合A上的二元关系，则 （1）（2）（3）第52页，此课件共87页哦3-9 集合的划分和覆盖定义3-9.1设A为非空集合，S=S1,S2,Sm,其中SiA，Si，i=1,2,m且则集合S称为集合A的覆盖。如果除了以上条件外，还满足SiSj=(ij)，则集合S称

29、为集合A的划分。第53页，此课件共87页哦3-9 集合的划分和覆盖 定义3-9.2 若A1,A2,Ar和B1,B2,Bs都是集合A的划分，则其中所有Ai Bj 组成的集合，称为是原来两种划分的交叉划分。定理3-9.1若A1,A2,Ar和B1,B2,Bs都是集合A的划分，则其交叉 划分也是原集合A的一种划分。第54页，此课件共87页哦3-9 集合的划分和覆盖n定义3-9.3 给定集合A的任意两个划分A1,A2,Ar和B1,B2,Bs，若对于每一个Aj均有Bk使Aj Bk,则划分A1,A2,Ar称为划分B1,B2,Bs的加细。n定理3-9.2 任何两种划分的交叉划分，都是原来各划分的一种加细。第5

30、5页，此课件共87页哦 3-9 集合的划分和覆盖-例题 例题1 设A1,A2,Am是集合A的一个划分，我们定义A上的二元关系R,使R当且仅当a和b在这个划分的同一块中，证明：R是自反的、对称的、传递的。例题2 设A1,A2,An是集合A的划分,若A B ，1in,试证明 A1 B,A2 B,Ar B是集合A B的划分。第56页，此课件共87页哦3.10 等价关系与等价类 定义定义3.10.1设R是定义在集合A上的二元关系，若R是自反的、对称的和传递的，则称R是等价关系。显然，若关系R是等价关系，则也必然是相容关系。反之，则不一定成立。例 设 ，在集合A上定义关系R如下 证明R是等价关系并画出其

31、关系图。解：由R的定义可知，R的关系图为：第57页，此课件共87页哦3.10 等价关系与等价类 下面来证明R是等价关系：（1）对于任意的 ，因为a-a可被3整除，故 ，因此R是自反的。（2）对于任意的 ，若 ，则a-b可被3整除，又因为b-a=-(a-b)，故b-a也可被3整除。即 ，因此R是对称的。（3）对于任意的 ，若 ，则a-b 和b-c均可被3整除，又因为a-c=(a-b)+(b-c)，故a-c也可被3整除。即 ，因此R是传递的。综上所述，知R是等价关系。第58页，此课件共87页哦3.10 等价关系与等价类 定义定义3.10.2 设R是集合A上的等价关系，对于任一 ，集合 称为元素a形

32、成的等价类。定理定理4.6.1 设R是集合A上的等价关系，则有 （1），是A的非空子集。（2），如果 ，则 。（3），如果 ，则 。（4）。（5）aRb 当且仅当aR=bR 定义定义4.6.3 设R是非空集合A上的等价关系。由A中各元素生成的关于R的等价类的集合 ，称为A关于R的商集，记作 。例如，例1中的集合A关于R的商集为 第59页，此课件共87页哦练习题设集合A=1,2,3,4,5,6,7,说明A上的下列二元关系哪些是等价关系并求其等价类,如果不是说明原因。(1)R=,(2)S=,(3)T=,第60页，此课件共87页哦3.10 等价关系与等价类 给定非空集合A，若有集合 ，其中 ，且 ，

33、同时有 则称S是A的划分。定理定理3.10.2 设R是非空集合A上的等价关系，则A关于R的商集A/R是集合A上的一种划分。定理3.10.2给出了根据集合的等价关系求出其相应划分的方法。定理定理3.10.3 设S是非空集合A中的一种划分。,在集合A上定义关系R如下：则R是集合A中的等价关系。定理3.10.3给出了由集合的划分求等价关系的方法。第61页，此课件共87页哦3.10 等价关系与等价类注1：集合A上的等价关系R，决定了A的一个划分，该划分就是商集A/R注2：集合A的一个划分确定了A的元素之间的一个等价关系。定理：设R1和R2是非空集合A上的等价关系，则R1=R2当且仅当A/R1=A/R2

34、其中A/R1=aR1|aA,A/R2=aR2|aA第62页，此课件共87页哦练习题一、已知集合A=1,2,3,4,5,6上的划分S=1,2,3,4,5,6,求由此划分所确定的A上的等价关系。二、已知集合A=1,2,3,4,5,6上的等价关系R=,求由此等价关系所确定的A上的划分。第63页，此课件共87页哦3-11 相容关系定义定义3.11.13.11.1设R是集合A上的二元关系，若R是自反的和对称的，则称R是相容关系。例 设A=cat,teacher,cold,desk,knife,by,在A上定义关系R如下 试画出R的关系图和关系矩阵，并说明R是相容关系。解：令则 的关系图如下面图4.5.1

35、所示第64页，此课件共87页哦3-11 相容关系 图4.5.1 关系矩阵 从关系图和关系矩阵中可以看出，关系R是相容关系。因为在关系图中，每个节点都有环且任意两个节点之间如有连线，必有双向线；在关系矩阵中，其对角线上各元素均为1，且关系矩阵以对角线为轴对称。约定：相容关系的关系图上，不画出每个元素的环、每对双向线，只画出无向连线。相容关系的关系矩阵中，只画出主对角线以下的下三角矩阵。第65页，此课件共87页哦3-11 相容关系 图4.5.2 关系图 图4.5.3 关系矩阵第66页，此课件共87页哦3.11 相容关系 给定非空集合A，设有集合 ，其中 ，且 ，且 ，则称集合S为集合A的覆盖。由覆

36、盖可以构造相容关系。例如，设 ，则S和T均是A的覆盖，且两者不同。定理定理3.11.1 给定集合A上的一个覆盖 ，由它确定的关系 是相容关系。从这个定理可以看出，给定集合A上的任一覆盖，就可以构造出与此覆盖相对应的一个相容关系。但是，请注意：不同的覆盖可以构造出相同的相容关系。第67页，此课件共87页哦相容类：设r是集合A上的相容关系，若CA，如果对于C中任意两个元素a1,a2有a1ra2，称C是由相容关系r产生的相容类。第68页，此课件共87页哦3-11 相容关系 定义定义3.11.3 设R是集合A中的相容关系，若有 ，使得对于任意的 ，必有 ，并且在 中，没有任何一个元素与 中的所有元素都

37、有R关系，则称 是由R产生的最大相容类。例如，例4.5.1中的相容关系有以下4个最大相容类：由R所产生的所有最大相容类所构成的集合，称为集合A的完全覆盖。根据任意一个给定的集合A的相容关系R，求它的完全覆盖有两种常用的方法。第69页，此课件共87页哦 在相容关系图中，最大完全多边形的顶点集合，就是最大相容类。所谓完全多边形，就是其每个顶点都与其它顶点连接的多边形。例如一个三角形是完全多边形，一个四边形加上两条对角线就是完全多边形。第70页，此课件共87页哦求最大相容关系的关系图法 例3.11.2 设集合上的相容关系的简化关系图如图4.5.4所示，求出其完全覆盖。图4.5.4 解：从图中可以看出

38、，它的最大相容类为 ，则其完全覆盖为 。第71页，此课件共87页哦3-12 偏序关系 定义定义3.12.1 设R是集合A上的二元关系，若关系R满足自反性、反对称性和传递性，则称R是集合A上的一个偏序关系，并记作“”。集合A和集合A上的偏序关系“”所构成的序偶称作偏序集。例3.12.1 在实数集P上，证明大于等于关系“”是偏序关系。证明：（1）对于任意的实数x，都有xx，故“”在实数集上是自反的。（2）对于任意的实数x和y，若有xy且yx，则必有x=y，故“”在实数集上是反对称的。（3）对于任意的实数x、y和z，若有xy，yz，则必有x z。故“”在实数集上是传递的。综上所述，“”是实数集上的偏

39、序关系。是一个偏序集。第72页，此课件共87页哦3-12 偏序关系 由于偏序关系满足自反性、反对称性和传递性，其关系图中的各元素就会呈现出一定的层次关系。因此，为了突出偏序关系中各元素的层次性，我们按如下规定对偏序关系的关系图进行化简，从而得到一种简明的关系图。（1）省略关系图中表示自反性的自己到自己的边 （2）省略关系图中，可以通过传递关系表示出来的边。按上述约定化简了的关系图称为哈斯图（Hasse）下面给出其相关定义及画法。第73页，此课件共87页哦3.12 偏序关系定义定义3.12.2 在偏序集中，如果有x,yA，xy且 ，并且不存在其他元素 ，使得xz，zy，则称元素y盖住元素x。CO

40、V A=|x,yA;y盖住 x 画法：在哈斯图中，若有元素y盖住元素x，则将代表y的圆圈画在代表x的圆圈的上方。并且在y和x之间用直线相连。例3.12.2 设集合 ，R是集合A上的整除关系。试画出的哈斯图。解：的哈斯图如下图所示。第74页，此课件共87页哦3-12 偏序关系 定义定义3.12.3 设R是集合A上的二元关系，若R关系满足反自反性和传递性，则称R是A上的拟序关系，并把 称为拟序集，记作 A，。由拟序关系的定义可知，若R是拟序关系，则R必是反对称的。在实数集上的小于关系“”和大于关系“”，集合A的幂集 上的真包含关系“”等都是拟序关系。通过比较拟序关系和偏序关系，可以发现：拟序关系和

41、偏序关系都是反对称的、可传递的。但前者是反自反的，后者是自反的。第75页，此课件共87页哦链：设为偏序集，在A的一个子集中，如果每两个元素都有关系，则称这个子集为链。反链：设为偏序集，在A的一个子集中，如果每两个元素都是无关的，则称这个子集为反链。第76页，此课件共87页哦3.12 偏序关系 定义定义3.12.4 设为一偏序集，对于x,yA，若有xy或者yx，则称x和y是可比的。定义定义3.12.5 设是集合A上的二元关系，若对于任意的 x,yA，x和y都是可比的，则称是A上的全序关系（又称线性关系）。并将称为全序集。例如，设A=a,b,c，在集合A上有关系R如下：则R是全序关系，其哈斯图如下

42、图所示。第77页，此课件共87页哦3-12 偏序关系极大元和极小元 定义定义3.12.6 设是一个偏序集，集合B是A的子集。若bB，且不存在任何元素xB，使得xb且bx，则称b是集合B的极大元。同理,若bB，且不存在任何元素xB，使得xb且xb,则称b是集合B的极小元(当B=A时,就是A的极大元与极小元)例3.12.3 设A=2,3,5,7,14,15,21，其偏序关系如下 求B=2,3,7,14,21的极大元和极小元。解：的哈斯图如图所示。B的极大元集合为14,21，极小元集合为2,3,7。第78页，此课件共87页哦3.12 偏序关系最大元和最小元 定义定义3.12.7 设是一个偏序集，集合

43、B是A的子集。若有某个元素bB，使得对于任意一个元素xB，有xb，则称b是集合B的最大元。同理，若有某个元素bB，使得对于任意一个元素xB，有bx，则称b是集合B的最小元.(当B=A时,就是A的最大元与最小元)定理定理3.12.1 设是一个偏序集，BA，若B有最大元或最小元，则必是唯一的。第79页，此课件共87页哦3.12 偏序关系上界和下界定义定义3.12.8 设是一个偏序集，对于BA，若有某个元素aA，使得对于任意一个元素xB，有xa，则称是a子集B的上界。同理，若有某个元素aA，使得对于任意一个元素xB，有ax，则称a是子集B的下界。第80页，此课件共87页哦3.12 偏序关系最小上界和

44、最大下界n定义定义3.12.9 设是一个偏序集，对于子集BA，若存在B的某个上界a，使得对于B的所有上界x，满足ax，则称a是B的最小上界（上确界），记作LUBB。同理，若存在B的某个下界a，使得对于B的所有下界x，满足xa，则称a是B的最大下界（下确界），记作GLBB。第81页，此课件共87页哦3-12 偏序关系良序集 定理定理3.12.2 设是一个偏序集，BA，若B有最小上界或最大下界，则必是唯一的。定义定义3.12.10 设是一个偏序集，若A的任一非空子集都有最小元，则称为良序集。例如，自然数集对于小于等于关系是良序集。但是整数集对于小于等于关系不是良序集。因为整数集本身对于小于等于关系

45、没有最小元。定理定理3.12.3 每一个有限全序集，一定是良序集。定理定理3.12.4 每个良序集，一定是全序集。第82页，此课件共87页哦练习题 设集合为3,5,15,1,2,3,6,12,3,9,27,54，偏序关系为整除，试分别画出这些集合的偏序关系图和哈斯图，并指出哪些是全序关系。第83页，此课件共87页哦例题：试分别构造下述集合的例子（1）非空线序集合，其中某些子集没有最小元。（2）非空偏序集，它不是线序集，其中某些子集没有最大元。（3）偏序集有一子集，它存在一最大下界，但没有最小元素。（4）偏序集有一子集，它存在一上界，但没有最小上界。第84页，此课件共87页哦第三章的重点内容n集合的运算(幂、笛卡尔积)n关系的性质及运算（复合、逆）n等价关系与等价类n序关系第85页，此课件共87页哦 作业P146(6),(7)第86页，此课件共87页哦谢谢!第87页，此课件共87页哦