第3章集合与关系hhs.ppt

《第3章集合与关系hhs.ppt》由会员分享，可在线阅读，更多相关《第3章集合与关系hhs.ppt（68页珍藏版）》请在三一办公上搜索。

1、第二部分 集合论,集合论溯源十六世纪末 起源十九世纪 德国数学家康托创立古典集合论1900年前后 出现各种悖论1908年 策莫罗建立集合论的公理系统目前 集合论公理系统有两种形式:策莫罗-弗兰克尔-柯很形式（ZFC）贝尔内斯-诺伊曼-葛德尔形式（BNG）在计算机领域得到广泛应用,第二部分 集合论,古典集合论 康托称集合是“一些确定的、不同的东西的总体，这些东西，人们能够意识到，并且能够判断一个给定的东西是否属于这个总体”。悖论-理发师悖论：在一个小岛上有唯一的一位理发师。他宣称：我为岛上所有不为自己理发的人理发，而不给那些为自己理发的人理发。”。请问：理发师的头发由谁来理呢？-罗素悖论：令集合

2、S为包含所有不以自身为元素的那些集合，即S=x|x x 请问：S S吗？,第二部分 集合论,ZFC公理：包括九个公理外延公理空集公理无序对公理正则公理替换公理方幂集公理集公理无限公理选择公理,外延公理：假定A和B都是集合，如果任何一个事物属于 A也一定属于B，属于B 也一定属于A，那么A和B是同一个集合，或称两个集合A和B相等。,空集公理：存在一个不包括任何元素的集合。,正则公理：任何一个非空集合A一定包含一个元素a，A的任何一个元素都不是 a 的元素,计算机应用领域 集合论是学习计算机科学必备的基础知识,计算机领域的大多数基本概念和理论都可以采用集合论的有关术语来描述和论证,集合论被广泛地应

3、用于形式语言、编译理论、信息检索、数据结构、算法分析、程序设计、人工智能等领域。,第三章 集合与关系,3.1 集合的基本概念3.2 集合的基本运算3.3 集合中元素的计数3.4 笛卡尔乘积3.5 关系的概念3.6 关系的表示与性质3.7 关系的运算3.8 关系的闭包运算3.9 相容关系与覆盖3.10 等价关系与划分3.11 偏序关系,3.1 集合的基本概念,1.集合定义 集合没有精确的数学定义 理解：由离散个体构成的整体称为集合，称这些个体为集 合的元素 常见的数集：N,Z,Q,R,C 等分别表示自然数、整数、有 理数、实数、复数集合,2.集合表示法 枚举法-通过列出全体元素来表示集合 谓词表

4、示法-通过谓词概括集合元素的性质 实例：枚举法：谓词法：,3.1 集合的基本概念,3.集合的元素具有的性质 无序性：元素列出的顺序无关 相异性：集合的每个元素只计 数一次 确定性：对任何元素和集合都 能确定这个元素是否 为该集合的元素 任意性：集合的元素也可以是 集合4元素与集合的关系 隶属关系：或者5集合的树型层次结构,d A,a A,3.1 集合的基本概念,6.集合与集合之间的关系：,=,定义6.1 A B x(xA xB)，A是B的子集 定义6.2 A=B A B B A 定义6.3 A B A B A B，A是B的真子集 A B x(xA xB)思考：和 的定义 注意 和 是不同层次的

5、问题,3.1 集合的基本概念,7空集：不含有任何元素的集合 实例：x|xR x2+1=0 定理6.1 空集是任何集合的子集。证:对于任意集合A，A x(xxA)T(恒真命题)推论 是惟一的 一般地，称集合A的子集和A为A的平凡子集。,8.幂集：(A)=x|x A 实例：()=,()=,计数：如果|A|=n，则|(A)|=2n.,9.全集 E：包含了所有集合的集合 全集具有相对性：与问题有关，不存在绝对的全集,3.1 集合的基本概念,例 A=a,b,c，求A的幂集(A)。解：将A的子集从小到大分类：0元子集，即空集,；1元子集，即单元集，a，b，c；2元子集，a,b，b,c，a,c；3元子集，a

6、,b,c；集合A有(A)=,a,b,c,a,b,a,c,b,c,a,b,c。,习题：P86（6）d,3.2 集合的基本运算,1 集合的运算2 集合运算算律,集合的基本运算有:并 AB=x|xA xB 交 AB=x|xA xB 相对补 AB=x|xA xB 对称差 AB=(AB)(BA)绝对补 A=EA,文氏图,3.2 集合的基本运算,1 集合的运算2 集合运算算律,说明(1)并和交运算可以推广到有穷个集合上，即 A1 A2 An=x|xA1 xA2 xAn A1 A2 An=x|xA1 xA2 xAn(2)A B AB=AB=AB=A,例 A=0,1,2，B=2,3，计算解：,3.2 集合的基

7、本运算,1 集合的运算2 集合运算算律,任何代数运算都遵从一定的算律，集合运算也不例外。下面给出集合运算的主要算律，其中A，B，C表示任意的集合。幂等律 结合律 交换律 分配律 同一律 零 律 排中律 矛盾律 吸收律 双重否定律 德摩根律,3.2 集合的基本运算,1 集合的运算2 集合运算算律,除了以上算律，还有一些关于集合运算性质的重要结论，在此一并给出。建立了相对补运算和交运算之间的联系，可以利用它将相对补转变成交。给出了 的三种等价的定义，为证明两个集合之间包含关系提供了新方法，同时也可以用于集合公式的化简。,习题：P95（11）a,*3.3 集合中元素的计数包含排斥原理,集合A含有n个

8、元素，可以说集合A的基数是n，记作card A=n。所谓基数就是表示集合中所含元素多少的量。如果集合A的基数是n，也可以记为|A|=n。显然空集的基数是0，即|=0。定义3.3.1 设为集合，若存在自然数n（0也是自然数），使得|A|=card A=n，则称A为有穷集，否则就称A为无穷集。例3.3.1 有100名程序员，其中47名熟悉C语言，35名熟悉C+语言，23名熟悉这两种语言。问有多少人对这两种语言都不熟悉？解：设A，B分别表示熟悉C和C+语言的程序员的集合，则该问题可以用图3.3.1的文氏图表示。将熟悉两种语言的对应人数23填入AB的区域内，不难得到A-B和B-A的人数分别为|A-B|

9、=|A|-|AB|=47-23=24|B-A|=|B|-|AB|=35-23=12 从而得到|AB|=24+23+12=59,故，|(AB)|=100-59=41，即两种语言都不熟悉的有41人。,*3.3 集合中元素的计数包含排斥原理,设S是有穷集，P1和P2分别表示两种性质，对于S中的任何一个元素x，只能处于以下四种情况之一：（1）只具有性质P1；（2）只具有性质P2；（3）具有P1和P2两种性质；（4）两种性质都没有。令A1和A2分别表示S中具有性质P1和P2的元素的集合。为了使表达式简洁，对任何集合B，用 代替B。由文氏图不难得到以下公式 这就是容斥原理的一种简单形式。如果涉及到三条性质

10、，容斥原理的公式则变成,*3.3 集合中元素的计数包含排斥原理,定理 3.3.1 S中不具有性质P1,P2,Pm的元素数是 定理3.3.1证明略。推论 在S中至少具有一条性质的元素数是,*3.3 集合中元素的计数包含排斥原理,例：某班学生150人。数学考试成绩90分以上的有80人，语文考试成绩90分以上的有75人，两门课程均在90分以上的有50人，问（1）只有一门课程成绩90分以上的学生有多少人？（2）两门课程成绩均不在90分以上的学生有多少人？解：全集为该班学生组成的集合。设 由题意可知（1）即需求。因为 所以，即（2）即需求,3.4 笛卡尔乘积,定义7.1 由两个元素 x 和 y，按照一定

11、的顺序组成的二元组称为有序对，记作.有序对性质:(1)有序性（当xy时）(2)与相等的充分必要条件是=x=uy=v,定义7.2 设A,B为集合，A与B的笛卡儿积记作AB，且 AB=|xAyB.,3.4 笛卡尔乘积,例1 A=1,2,3,B=a,b,c AB=,BA=,A=,B=P(A)A=,P(A)B=,3.4 笛卡尔乘积,笛卡儿积的性质:(1)不适合交换律 AB BA(AB,A,B)(2)不适合结合律(AB)C A(BC)(A,B,C)(3)对于并或交运算满足分配律 A(BC)=(AB)(AC)(BC)A=(BA)(CA)A(BC)=(AB)(AC)(BC)A=(BA)(CA)(4)若 A

12、或 B 中有一个为空集，则 AB 就是空集.A=B=(5)若|A|=m,|B|=n,则|AB|=mn,证明 A(BC)=(AB)(AC)证 任取:A(BC)xAyBC xA(yByC)(xAyB)(xAyC)ABAC(AB)(AC)所以有A(BC)=(AB)(AC).,3.4 笛卡尔乘积,例2(1)证明A=B,C=D AC=BD(2)AC=BD是否推出 A=B,C=D?为什么？,解(1)任取 AC xAyC xByD BD(2)不一定.反例如下：A=1，B=2,C=D=,则AC=BD但是A B.,3.5 关系的概念,定义3.5.1 设A，B是任意两个集合，AB的子集R称为从A到B的二元关系，当

13、A=B 时，称R为A上的二元关系。从上述定义可以看出A到B的二元关系，也是序偶的集合。若 R，则称a与b有关系R，记作a R b。若，则称a与b没有关系R，记作。例如：设A=a,b,c,d,B=0,1，则R=a,0,b,0,c,1 就是一个从A到B的二元关系。定义3.5.2 设A，B是任意两个集合，R是A到B上的二元关系，若R=，则称为空关系。若R=AB，则称R为全关系。称为A上的恒等关系。全关系 例如：设A=0,1,2，则。,3.5 关系的概念,定义3.5.3 设A，B是两个集合，R是从A到B上的二元关系，则(1)若存在bB，使得R，则所有这样的aA组成的集合，称为二元关系R的定义域。记作d

14、om(R)或D(R)，即(2)若存在aA，使得 R，则所有这样的bB组成的集合，称为二元关系R的值域。记作ran(R)或R(R)，即 R的定义域和值域一起称作R的域，记作FLDR，即 FLDR=dom(R)ran(R)从X到Y的二元关系R，也可以用图解的方式表示，如图3.5.1所示，X和Y是两个集合。xi是集合X中的元素，yj是集合Y中的元素，当且仅当xiRyj时，才有一条从xi指向yj的有向边。,3.5 关系的概念,图 3.5.1 图解表示法,3.5 关系的概念,定理3.5.1 若R和S是从集合A到B上的两个二元关系，则R和S的并、交、补、差也是A到B上的二元关系。证明：因为R和S是从集合A

15、到B上的二元关系 所以有R AB，S AB。从而有 即RS和RS都是A到B上的二元关系。又因为 所以R和S也是A到B上的二元关系。由于 故R-S也是A到B上的二元关系,3.6 关系的表示与性质,1 关系的矩阵表示2 关系的图形表示3 关系的性质,设 X=a,b,c,Y=0,1,2,3，R=,。可得关系R的矩阵表示如下：由上例看出，给定从有限集X到Y的二元关系R，就可以构造出它的关系矩阵。给定两个有限集合 和，并且R是从X到Y的二元关系。如果有 则称矩阵 是R的关系矩阵，并记作。,3.6 关系的表示与性质,1 关系的矩阵表示2 关系的图形表示3 关系的性质,设画出R的关系图。解：R的关系图如图3

16、.6.1所示。图3.6.1 R的关系图,3.6 关系的表示与性质,1 关系的矩阵表示2 关系的图形表示3 关系的性质,定义3.6.1 设 R 为A上的关系,(1)若 x(xAR),则称 R 在 A 上是自反的.(2)若 x(xAR),则称 R 在 A 上是反自反的.,实例：自反：全域关系EA,恒等关系IA,小于等于关系LA,整除关系DA反自反：实数集上的小于关系、幂集上的真包含关系.A=1,2,3,R1,R2,R3是A上的关系,其中 R1,R2,R3R2 自反，R3 反自反，R1既不是自反的也不是反自反的.,3.6 关系的表示与性质,1 关系的矩阵表示2 关系的图形表示3 关系的性质,定义3.

17、6.2 设 R 为 A上的关系,(1)若xy(x,yARR),则称 R 为 A上对称的关系.(2)若xy(x,yARRx=y),则称 R 为A上的反对称关系.,实例：对称关系：A上的全域关系EA,恒等关系IA和空关系反对称关系：恒等关系IA和空关系也是A上的反对称关系.设A1,2,3,R1,R2,R3和R4都是A上的关系,其中 R1,，R2,R3,，R4,R1：对称和反对称；R2：只有对称；R3：只有反对称；R4：不对称、不反对称,3.6 关系的表示与性质,1 关系的矩阵表示2 关系的图形表示3 关系的性质,定义3.6.3 设R为A上的关系,若 xyz(x,y,zARRR),则称 R 是A上的

18、传递关系.,实例：A上的全域关系 EA,恒等关系 IA和空关系，小于等于和小于关系，整除关系，包含与真包含关系设 A1,2,3,R1,R2,R3是A上的关系,其中 R1,R2,R3R1和R3是A上的传递关系,R2不是A上的传递关系.,3.6 关系的表示与性质,1 关系的矩阵表示2 关系的图形表示3 关系的性质,3.7 关系的运算,1 关系的逆运算2 关系的合成运算,定义3.7.1 设R是从集合X到集合Y的二元关系，如果将R中每一对序偶的元素顺序互换，所得到的新的集合则称为R的逆关系，记作，即 由逆关系的定义可知，的关系图可以通过将R的关系图的所有有向弧逆转得到，它的关系矩阵可以通过将R的关系矩

19、阵转置得到。例3.7.1 设，求。解：。,3.7 关系的运算,1 关系的逆运算2 关系的合成运算,定理3.7.1 设R和S都是从X到Y的二元关系，则下列各式成立。（1）（2）（3）（4），这里R表示（5）（6）若，则,3.7 关系的运算,1 关系的逆运算2 关系的合成运算,定理3.7.2 设R是A上的二元关系，则（1）R在A上是自反的，当且仅当。（2）R在A上是反自反的，当且仅当。（3）R在A上是对称的，当且仅当。（4）R在A上是反对称的，当且仅当。,3.7 关系的运算,1 关系的逆运算2 关系的合成运算,定义3.7.2 设R是从集合X到集合Y的二元关系，S是从集合Y到Z的关系，则R S称为R

20、和S的合成关系，定义为 R S称为关系的合成运算。设R是从集合 到集合 的关系，S是从集合 到集合 的关系，则 是一个 的矩阵，是一个 的矩阵。依照普通矩阵乘法的运算，可以定义两个关系矩阵的合成运算。,3.7 关系的运算,由上述前两个矩阵可以构造这两个矩阵的合成矩阵，记作。元素 可由下式得到：其中。和的运算规则如下：两个关系的合成运算，就是将布尔关系矩阵做乘法，所得结果即为合成关系矩阵。,1 关系的逆运算2 关系的合成运算,3.7 关系的运算,1 关系的逆运算2 关系的合成运算,定理3.4.3 设X,Y,Z和W都是集合。R是从集合X到Y的关系，S是从集合 Y到Z的关系，T是从集合Z到W的关系。

21、于是有(R S)T=R(S T)即关系的合成运算满足结合律。证明：对任意的(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)。同理可证R(S T)(R S)T。综上所述，得到(R S)T=R(S T)，即关系的合成运算满足结合律。一般来说，关系的合成运算是不满足交换律的，即R S S R。,3.7 关系的运算,定义3.7.3 设R是集合X中的二元关系，nN（N是自然数集），于是R的n次幂 定义为

22、：（1），即 是R中的恒等关系。（2）。定理3.7.4 设R是集合X中的二元关系。设m,nN。则有（1）（2）定理3.7.5 设R是A上的二元关系，则R在A上是传递的，当且仅当,1 关系的逆运算2 关系的合成运算,例题14,习题:P119(5)、(6),3.8 关系的闭包运算,1 关系的闭包定义2 关系的闭包构造方法3 关系的闭包性质,定义3.7.1 设R是非空集合A上的关系,R的自反(对称或传递)闭包是A上的关系R,使得R满足以下条件：(1)R是自反的(对称的或传递的)(2)RR(3)对A上任何包含R的自反(对称或传递)关系R 有RR则称R是R的自反闭包，记作r(R),（对称闭包记作s(R)

23、,传递闭包记作t(R).）由定义可知：（1）自反(对称或传递)闭包是关系（2）自反(对称或传递)闭包是包含R的最小自反(对称或传递)关系,3.8 关系的闭包运算,1 关系的闭包定义2 关系的闭包构造方法3 关系的闭包性质,集合构造方法：设R为A上的关系,则有(1)r(R)=RR0(2)s(R)=RR1(3)t(R)=RR2R3说明：对有穷集A(|A|=n)上的关系,(3)中的并最多不超过Rn（参见课本P122定理3.8.5）,矩阵构造方法：设关系R,r(R),s(R),t(R)的关系矩阵分别为M,Mr,Ms 和 Mt 则 Mr=M+E Ms=M+M Mt=M+M2+M3+E 是单位矩阵,M 是

24、 转置矩阵，相加时使用逻辑加.说明：对有穷集A(|A|=n)上的关系,Mt=M+M2+Mn,3.8 关系的闭包运算,1 关系的闭包定义2 关系的闭包构造方法3 关系的闭包性质,关系图构造方法：设关系R,r(R),s(R),t(R)的关系图分别记为G,Gr,Gs,Gt,则Gr,Gs,Gt 的顶点集与G 的顶点集相等.除了G 的边以外,以下述方法添加新的边：(1)考察G 的每个顶点,若没环就加一个环，得到Gr(2)考察G 的每条边,若有一条 xi 到 xj 的单向边,ij,则在G 中加一条 xj 到 xi 的反向边,得到Gs(3)考察G 的每个顶点 xi,找 xi 可达的所有顶点 xj(允许i=j

25、)，如果没有从 xi 到 xj 的边,就加上这条边,得到图Gt,3.8 关系的闭包运算,1 关系的闭包定义2 关系的闭包构造方法3 关系的闭包性质,例 设A=a,b,c,d,R=,R和r(R),s(R),t(R)的关系图如下图所示.,3.8 关系的闭包运算,1 关系的闭包定义2 关系的闭包构造方法3 关系的闭包性质,定理3.7.1 设R是非空集合A上的关系,则(1)R是自反的当且仅当 r(R)=R.(2)R是对称的当且仅当 s(R)=R.(3)R是传递的当且仅当 t(R)=R.,定理3.7.2 设R1和R2是非空集合A上的关系,且 R1R2,则(1)r(R1)r(R2)(2)s(R1)s(R2

26、)(3)t(R1)t(R2),定理3.7.3 设R是非空集合A上的关系,(1)若R是自反的,则 s(R)与 t(R)也是自反的(2)若R是对称的,则 r(R)与 t(R)也是对称的(3)若R是传递的,则 r(R)是传递的.,3.8 关系的闭包运算,1 关系的闭包定义2 关系的闭包构造方法3 关系的闭包性质,二元关系的闭包仍然是二元关系，还可以求它的闭包。例如，R是A上的二元关系，r(R)是它的自反闭包，还可以求r(R)的对称闭包。r(R)的对称闭包记为s(r(R)，简记为sr(R)，读作R的自反闭包的对称闭包。其余类似。,定理3.7.4 设R是集合A上的二元关系，则（1）（2）（3）,例题12

27、,习题:P127(1)、(2)a,3.9集合的覆盖与划分,1覆盖与划分2加细与真加细3交叉划分,定义3.9.1 给定非空集合A，设有集合，其中，且，且，则称集合S为集合A的覆盖。,若还满足条件 则称 S 是 A 的划分.,说明：划分是覆盖的特殊情形.划分的元素 Si 称为划分的类.,例1：令 Z=所有整数的集合 A1=所有偶数的集合 A2=所有奇数的集合,则 A1,A2是 Z 的一个划分。,3.9集合的覆盖与划分,1覆盖与划分2加细与真加细3交叉划分,例2：已知 下面哪些集合是 A 的覆盖或划分？,最小划分：是由作为类的集合本身构成.如S4最大划分：是由包含单个元素的类组成.如S5,3.9集合

28、的覆盖与划分,1覆盖与划分2加细与真加细3交叉划分,定义3.9.2 设 A 和 B 是同一集合 X 的两种划分,且有 A=A1,A2,.Am,B=B1,B2,.Bn,若 A 的每一个类都是 B 的某一类的子集,即 则称 A 是 B 的加细。,若 A 是 B 的加细,且 BA,则称 A 是 B 的真加细。,例3：已知X=a,b,c,d，A=a,b,c,d,下面的 Bi 哪些是 A的加细？B1=a,b,c,d B2=a,b,c,d,B3=a,b,c,d B4=a,b,c,d B5=d,a,b,c B6=a,d,b,c,3.9集合的覆盖与划分,1覆盖与划分2加细与真加细3交叉划分,定义3.9.3 若

29、 A=A1,A2,Ar 与 B=B1,B2,Bs 是同一个集合 X 的两种划分，则其中所有 Ai Bj 组成的集合，称为是原来两种划分的交叉划分。,例4：X=所有生物的集合 P=所有植物的集合 E=所有史前生物 A=所有动物的集合 F=所有史后生物则：P,A、E,F 是 X 的两种划分。,其交叉划分为 PE,PF,AE,AF,其中 PE表示史前植物 PF表示史后植物 AE表示史前动物 AF表示史后动物,定理1 若 A,B 是同一集合 X 的两种划分,则其交叉划分也是原集合的一种划分。定理2 任何两种划分的交叉划分，都是原来划分的一种加细。,3.10 等价关系与等价类,1等价关系的定义2等价类的

30、定义3商集与划分,定义3.10.1 设R为非空集合上的关系.如果R是自反的、对称的和传递的,则称R为A上的等价关系.设 R 是一个等价关系,若R,称 x等价于y,记做xy.,例1 设 A=1,2,8,如下定义A上的关系R：R=|x,yAx y(mod 3)其中x y(mod 3)叫做 x与 y 模3相等,即x除以3的余数与y除以3的余数相等.不难验证 R 为A上的等价关系,因为(1)xA,有 x x(mod 3)(2)x,yA,若x y(mod 3),则有y x(mod 3)(3)x,y,zA,若x y(mod 3),y z(mod 3),则有x z(mod 3),模 3 等价关系的关系图,3

31、.10 等价关系与等价类,1等价关系的定义2等价类的定义与性质3商集与划分,定义3.10.2 设R为非空集合A上的等价关系,xA，令 xR=y|yAxRy称xR 为x关于R的等价类,简称为x的等价类,简记为xR 实例 A=1,2,8上模3等价关系的等价类：1=4=7=1,4,7 2=5=8=2,5,8 3=6=3,6,定理3.10.1 设R是非空集合A上的等价关系,则(1)xA,x是A的非空子集(2)x,yA,如果 xRy,则 x=y(3)x,yA,如果 x y,则 x与y不交(4)x|xA=A,3.10 等价关系与等价类,1等价关系的定义2等价类的定义与性质3商集与划分,证(1)由定义,xA

32、有xA.又xx,即x非空.(2)任取 z,则有 zx R R RR R R 从而证明了zy.综上所述必有 xy.同理可证 yx.这就得到了x=y.(3)假设 xy,则存在 zxy,从而有zxzy,即RR成立.根据R的对称性和传递性必有 R,与 x y矛盾(4)先证x|xA A.任取y,yx|xA x(xAyx)yxx A yA 从而有x|xA A 再证A x|xA.任取y,yA yyyA yx|xA 从而有x|xA A成立.综上所述得x|xA=A.,3.10 等价关系与等价类,1等价关系的定义2等价类的定义与性质3商集与划分,定义3.10.3 设 R 为非空集合A上的等价关系,以 R 的所有等

33、价类作为元素的集合称为A关于R的商集,记做A/R,A/R=xR|xA实例 设 A=1,2,8，A关于模3等价关系R的商集为 A/R=1,4,7,2,5,8,3,6A关于恒等关系和全域关系的商集为：A/IA=1,2,8，A/EA=1,2,8,定义3.10.4设A为非空集合,若A的子集族(P(A)满足:(1)(2)xy(x,yxyxy=)(3)=A则称是A的一个划分,称中的元素为A的划分块.,3.10 等价关系与等价类,1等价关系的定义2等价类的定义与性质3商集与划分,例3 给出 A1,2,3上所有的等价关系,解 先做出A的划分,从左到右分别记作 1,2,3,4,5.,1对应 EA,5 对应 IA

34、,2,3 和 4分别对应 R2,R3和 R4.R2=,IA R3=,IA R4=,IA,例题14,习题:P134(3)、(5),3.11 偏序关系,1 偏序关系与偏序集2 盖住与哈斯图3 链与全序关系4 偏序集中的特殊元素及性质,定义1:设 R 为定义在集合 A 上的一个关系,若 R 是 a)自反的 b)反对称的 c)传递的 则 R 称为偏序关系，记为.序偶 称作偏序集.,例1 证明在实数集R上,是偏序关系.,证明：1）对于任何 a R，有 a a 成立，故 是自反的；2）对于任何 a,b R,如果有 a b 且 b a 成立，则必有 a=b,故 是反对称的；3）如果有 a b,b c 成立，

35、则必有 ac,故 是传递的。因此是偏序关系。,3.11 偏序关系,1 偏序关系与偏序集2 盖住与哈斯图3 链与全序关系4 偏序集中的特殊元素及性质,例2 已知 A=2,3,6,8,=|x整除y，验证 是偏序关系.,证明：,3.11 偏序关系,1 偏序关系与偏序集2 盖住与哈斯图3 链与全序关系4 偏序集中的特殊元素及性质,定义2：在偏序集合 中，如果 x,y A,x y,x y,且没有其它元素 z,满足x z,z y,则称元素 y 盖住元素 x.并且记 COVA=|x,y A;y 盖住 x,对于给定偏序集合，它的盖住关系是唯一的。所以可用盖住的性质画出偏序集合图，称为哈斯图,对于给定偏序集合，

36、其哈斯图做图规则如下：（1）用小圆圈代表元素；（2）如果 x y 且 x y，则将代表 y 的小圆圈画在代表 x 的小圆圈之上；（3）如果 COVA,则在 x 与 y 之间用直线连接。,3.11 偏序关系,1 偏序关系与偏序集2 盖住与哈斯图3 链与全序关系4 偏序集中的特殊元素及性质,例3 A 是 m=12 的因子集合,为整除关系,求 COVA，并画出哈斯图。,解:,=,IA,COVA=,6,12,哈斯图是简化的关系图(1)自反性：每个顶点都有自回路，省去自回路。(2)反对称性：从小到大安置顶点，可省略箭头。(3)传递性：由于有(，)，(，)R 则(，)R，故只画（，），（，）对应的边，省略

37、边（，）。,3.11 偏序关系,1 偏序关系与偏序集2 盖住与哈斯图3 链与全序关系4 偏序集中的特殊元素及性质,例4 画出哈斯图,3.11 偏序关系,1 偏序关系与偏序集2 盖住与哈斯图3 链与全序关系4 偏序集中的特殊元素及性质,A1=1,2,3,4 为小于等于关系,A2=,a,a,b,a,b,c 为包含关系,不同的偏序集,哈斯图可以有同样的结构,3.11 偏序关系,1 偏序关系与偏序集2 盖住与哈斯图3 链与全序关系4 偏序集中的特殊元素及性质,定义4：设 是一偏序集合，在 A 的一个子集中，如果每两个元素都是有(无)关系的，则称这个子集是链(反链)。,约定：若 A 的子集只有单个元素,

38、则它既是链又是反链.,例6 已知 A=a,b,c,d,e R=,验证 是偏序集，画出哈斯图，举例说明链和反链。,解：,关系矩阵对角线都为1，且rij 和rji 不同时为1，所以 R 是自反的和反对称的。,定义5：在偏序集 中，如果 A 是一个链，则称 为全序集合(线序集合)，二元关系 为全序关系(线序关系)。,3.11 偏序关系,1 偏序关系与偏序集2 盖住与哈斯图3 链与全序关系4 偏序集中的特殊元素及性质,R是传递的。,COVA=,3.11 偏序关系,1 偏序关系与偏序集2 盖住与哈斯图3 链与全序关系4 偏序集中的特殊元素及性质,极大元：设 是一个偏序集合,且 B 是 A 的子集,若有某

39、个元素 b B,B 中没有任何元素 x 满足 b x 且 b x，则称 b 为 B 的极大元,极小元：设 是一个偏序集合,且 B 是 A 的子集,若有某个元素 b B,B 中没有任何元素 x 满足 b x 且 x b，则称 b 为 B 的极小元,例7 已知A=2,3,5,7,14,15,21,偏序关系哈斯图如下:,B 的极大元集：21,14B 的极小元集：2,7,3,极大元与极小元不唯一,当 B=A 时，其极大元集是14,21,15，极小元集是2,7,3,5,3.11 偏序关系,1 偏序关系与偏序集2 盖住与哈斯图3 链与全序关系4 偏序集中的特殊元素及性质,最大（小）元：设 是一个偏序集合,

40、且 B 是 A 的子集,若有某个元素 b B,对于B 中每一个元素 x 有 xb(b x),则称 b 为 B 的最大元(最小元).,定理1：令 为偏序集且 BA，若 B 有最大(最小)元,则必是唯一的.,例8 B=a,、B=a,b最大元、最小元,B最大元：aB最小元：B最大元：无B最小元：无,3.11 偏序关系,1 偏序关系与偏序集2 盖住与哈斯图3 链与全序关系4 偏序集中的特殊元素及性质,上(下)界：设 是一个偏序集合,对于 BA,若有 aA,且对 B 的任意元素 x 都满足 x a(a x),则称 a 为子集 B 的上界(下界).,上界：h,i,j,k下界：无,上界：无下界：a,b,c,

41、d,e,f,g,上界：k下界：a,上界、下界不唯一,3.11 偏序关系,1 偏序关系与偏序集2 盖住与哈斯图3 链与全序关系4 偏序集中的特殊元素及性质,上（下）确界：设 是一个偏序集合且 B A,a 为 的任一上界，若对 的所有上界 y，都有a y 则称 a 为 B 的最小上界(上确界).若为 的任一下界，若对的所有下界 y，都有 y b 则称 b 为 B 的最大下界(下确界).,良序：任意偏序集合,假如它的每一个非空子集存在最小元素，这种偏序集称为良序的。,定理2：每一个良序集合，一定是全序集合。,定理3：每一个有限的全序集合，一定是良序集合。,3.11 偏序关系,1 偏序关系与偏序集2 盖住与哈斯图3 链与全序关系4 偏序集中的特殊元素及性质,例1 设偏序集，画出哈斯图,并求 B=2,3,6 上、下(确)界,上界：6,12,24,36上确界：6下(确)界：无,3.11 偏序关系,1 偏序关系与偏序集2 盖住与哈斯图3 链与全序关系4 偏序集中的特殊元素及性质,例2 设偏序集,画出哈斯图,并求 B=2,3,6 上、下(确)界,上界：6,12上确界：6下(确)界：1,P139例16，习题：p146(6),第一篇结束了.,思考,别忘了总结与回顾!,