《第3章集合与关系hhs》由会员分享，可在线阅读，更多相关《第3章集合与关系hhs（68页珍藏版）》请在金锄头文库上搜索。
1、1/38第二部分第二部分 集合论集合论集合论溯源集合论溯源十六世纪末十六世纪末 起源起源十九世纪十九世纪 德国数学家德国数学家康托康托创立创立古典集合论古典集合论19001900年前后年前后 出现各种出现各种悖论悖论19081908年年 策莫罗建立集合论的公理系统策莫罗建立集合论的公理系统目前目前 集合论公理系统有两种形式集合论公理系统有两种形式: :策莫罗策莫罗- -弗兰克尔弗兰克尔- -柯很形式柯很形式（ZFCZFC）贝尔内斯贝尔内斯- -诺伊曼诺伊曼- -葛德尔形式（葛德尔形式（BNGBNG）在在计算机领域计算机领域得到广泛应用得到广泛应用2/38第二部分第二部分 集合论集合论古典集合论
2、古典集合论康托称集合是康托称集合是“一些确定的、不同的东西的总体，这些东西，一些确定的、不同的东西的总体，这些东西，人们能够意识到，并且能够判断一个给定的东西是否属于这个总体人们能够意识到，并且能够判断一个给定的东西是否属于这个总体”。悖论悖论-理发师悖论：理发师悖论：在一个小岛上有唯一的一位理发师。他宣称：我为在一个小岛上有唯一的一位理发师。他宣称：我为岛上所有不为自己理发的人理发，而不给那些为自己理发的人理发。岛上所有不为自己理发的人理发，而不给那些为自己理发的人理发。”。请问：理发师的头发由谁来理呢？请问：理发师的头发由谁来理呢？-罗素悖论：罗素悖论：令集合令集合S为包含所有不以自身为元
3、素的那些集合，即为包含所有不以自身为元素的那些集合，即S=x|xx请问：请问：SS吗吗？3/38第二部分第二部分 集合论集合论ZFCZFC公理：公理：公理：公理： 包括九个公理包括九个公理外延公理外延公理空集公理空集公理无序对公理无序对公理正则公理正则公理替换公理替换公理方幂集公理方幂集公理集公理集公理无限公理无限公理选择公理选择公理外外延延公公理理：假假定定A和和B都都是是集集合合，如如果果任任何何一一个个事事物物属属于于A也也一一定定属属于于B，属属于于B也也一一定定属属于于A，那那么么A和和B是是同同一一个个集合，或称两个集合集合，或称两个集合A和和B相等。相等。空空集集公公理理：存存在
4、在一一个个不不包包括括任任何何元元素素的的集集合。合。正正则则公公理理：任任何何一一个个非非空空集集合合A一一定定包包含含一一个个元元素素a，A的的任任何何一一个个元元素素都都不不是是a的元素的元素计算机应用领域计算机应用领域计算机应用领域计算机应用领域集合论是学习计算机科学必备的基础知识集合论是学习计算机科学必备的基础知识,计算机领域的大多计算机领域的大多数基本概念和理论都可以采用集合论的有关术语来描述和论证数基本概念和理论都可以采用集合论的有关术语来描述和论证,集合集合论被广泛地应用于形式语言、编译理论、信息检索、数据结构、算论被广泛地应用于形式语言、编译理论、信息检索、数据结构、算法分析
5、、程序设计、人工智能等领域法分析、程序设计、人工智能等领域。 4/38第三章第三章 集合与关系集合与关系3.1 集合的基本概念3.2 集合的基本运算3.3 集合中元素的计数3.4 笛卡尔乘积3.5 关系的概念3.6 关系的表示与性质3.7 关系的运算3.8 关系的闭包运算3.9 相容关系与覆盖3.10 等价关系与划分3.11 偏序关系5/383.1 集合的基本概念集合的基本概念1.集合定义集合定义集合没有精确的数学定义集合没有精确的数学定义理解：由离散个体构成的整体称为理解：由离散个体构成的整体称为集合集合，称这些个体为集，称这些个体为集合的合的元素元素常见的数集：常见的数集：N, Z, Q,
6、R,C等分别表示自然数、整数、有等分别表示自然数、整数、有理数、实数、复数集合理数、实数、复数集合2.集合表示法集合表示法枚举法枚举法-通过列出全体元素来表示集合通过列出全体元素来表示集合谓词表示法谓词表示法-通过谓词概括集合元素的性质通过谓词概括集合元素的性质实例：实例：枚举法：枚举法：谓词法：谓词法：6/383.1 集合的基本概念集合的基本概念3.集合的元素具有的性质集合的元素具有的性质无序性无序性：元素列出的顺序无关：元素列出的顺序无关相异性相异性：集合的每个元素只计：集合的每个元素只计数一次数一次确定性确定性：对任何元素和集合都：对任何元素和集合都能确定这个元素是否能确定这个元素是否为
7、该集合的元素为该集合的元素任意性任意性：集合的元素也可以是：集合的元素也可以是集合集合4元素与集合的关系元素与集合的关系隶属关系：隶属关系： 或者或者 5集合的树型层次结构集合的树型层次结构d A,a A7/383.1 集合的基本概念集合的基本概念6.集合与集合之间的关系：集合与集合之间的关系： ,=, , , , 定义定义6.1 A B x(x A x B )，A是是B的子集的子集定义定义6.2 A=BA B B A定义定义6.3 A BA B A B，A是是B的真子集的真子集 A B x(x A x B )思考：思考： 和和 的定义的定义注意注意 和和 是不同层次的问题是不同层次的问题8/
8、383.1 集合的基本概念集合的基本概念7空集空集：不含有任何元素的集合不含有任何元素的集合实例：实例：x |x R x2+1=0定理定理6.1空集是任何集合的子集。空集是任何集合的子集。证证:对于任意集合对于任意集合A，A x(xx A)T(恒真命题恒真命题)推论推论是惟一的是惟一的 一般地，称集合A的子集和A为A的平凡子集。8.幂集：幂集：(A)=x|x A 实例：实例：()=,()=,计数：计数：如果如果|A|=n，则，则|(A)|=2n.9.全集全集E：包含了所有集合的集合包含了所有集合的集合全集具有相对性：与问题有关，不存在绝对的全集全集具有相对性：与问题有关，不存在绝对的全集9/3
9、83.1 集合的基本概念集合的基本概念例 A= a, b, c，求A的幂幂集(A) 。 解： 将A的子集从小到大分类： 0元子集，即空集, ； 1元子集，即单元集，a，b，c； 2元子集，a, b，b, c，a, c； 3元子集，a, b, c； 集合A有(A) = , a, b, c, a, b, a, c, b, c, a, b, c。习题：P86（6）d10/383.2 集合的基本运算集合的基本运算1 集合的运算2 集合运算算律集合的基本运算有集合的基本运算有:并并A B=x|x A x B交交A B=x|x A x B相相对对补补A B=x|x A x B对对 称称 差差 A B=(A
10、 B) (B A)绝对补绝对补 A=E A A BA BABA BA文氏图11/383.2 集合的基本运算集合的基本运算1 集合的运算2 集合运算算律说明说明(1)并和交运算可以推广到有穷个集合上，即并和交运算可以推广到有穷个集合上，即 A1 A2 An =x |x A1 x A2 x An A1 A2 An =x |x A1 x A2 x An (2) A B A B =A B =A B =A例 A=0, 1, 2，B=2, 3，计算解：12/383.2 集合的基本运算集合的基本运算1 集合的运算2 集合运算算律 任何代数运算都遵从一定的算律，集合运算也不例外。下面给出集合运算的主要算律，其
11、中A，B，C表示任意的集合。 幂等律 结合律 交换律 分配律 同一律 零 律 排中律 矛盾律 吸收律 双重否定律 德摩根律 13/383.2 集合的基本运算集合的基本运算1 集合的运算2 集合运算算律 除了以上算律，还有一些关于集合运算性质的重要结论，在此一并给出。 建立了相对补运算和交运算之间的联系，可以利用它将相对补转变成交。 给出了 的三种等价的定义，为证明两个集合之间包含关系提供了新方法，同时也可以用于集合公式的化简。习题：P95（11）a14/38*3.3 集合中元素的计数集合中元素的计数包含排斥原理包含排斥原理 集合A含有n个元素，可以说集合A的基数是n，记作card A=n。所谓
12、基数就是表示集合中所含元素多少的量。如果集合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| = |A|-| AB|=47-23=2
13、4 | B-A| = |B|-| AB|=35-23=12 从而得到| AB|=24+23+12=59, 故，| (AB)|=100-59=41， 即两种语言都不熟悉的有41人。15/38*3.3 集合中元素的计数集合中元素的计数包含排斥原理包含排斥原理 设S是有穷集，P1和P2分别表示两种性质，对于S中的任何一个元素x，只能处于以下四种情况之一： （1）只具有性质P1 ； （2）只具有性质P2 ； （3）具有P1和P2两种性质； （4）两种性质都没有。 令A1和A2分别表示S中具有性质P1和P2的元素的集合。为了使表达式简洁，对任何集合B，用 代替B。由文氏图不难得到以下公式 这就是容斥原理
14、的一种简单形式。 如果涉及到三条性质，容斥原理的公式则变成16/38*3.3 集合中元素的计数集合中元素的计数包含排斥原理包含排斥原理定理定理3.3.1 S中不具有性质P1, P2, , Pm的元素数是 定理3.3.1证明略。推论推论 在S中至少具有一条性质的元素数是17/38* *3.3 3.3 集合中元素的计数集合中元素的计数集合中元素的计数集合中元素的计数包含排斥原理包含排斥原理包含排斥原理包含排斥原理例：某班学生150人。数学考试成绩90分以上的有80人，语文考试成绩90分以上的有75人，两门课程均在90分以上的有50人，问 （1）只有一门课程成绩90分以上的学生有多少人？ （2）两门
15、课程成绩均不在90分以上的学生有多少人？解：全集为该班学生组成的集合。设 由题意可知 （1）即需求 。因为 所以， ，即（2）即需求18/383.4 笛卡尔乘积笛卡尔乘积定义定义7.1由两个元素由两个元素x 和和y，按照一定的顺序组成的二元组，按照一定的顺序组成的二元组称为称为有序对有序对，记作，记作.有序对性质有序对性质:(1)有序性有序性 （当（当x y时）时）(2)与与相等的充分必要条件是相等的充分必要条件是=x=u y=v定义定义7.2设设A,B为集合，为集合，A与与B的的笛卡儿积笛卡儿积记作记作A B，且，且A B =|x A y B.19/383.4 笛卡尔乘积笛卡尔乘积例例1A=
16、1,2,3,B=a,b,c A B=, B A=,A=,B=P(A) A =,P(A) B = 20/383.4 笛卡尔乘积笛卡尔乘积笛卡儿积的性质笛卡儿积的性质:(1)不适合交换律不适合交换律A B B A(A B,A,B)(2)不不适适合合结结合合律律(A B) C A (B C)(A,B,C)(3)对于并或交运算满足分配律对于并或交运算满足分配律A (B C) = (A B) (A C) (B C) A =(B A) (C A)A (B C) = (A B) (A C) (B C) A =(B A) (C A)(4)若若A 或或B 中有一个为空集，则中有一个为空集，则A B 就是空集就是
17、空集. A=B =(5)若若|A|=m,|B|=n,则则|A B|=mn证明证明A (B C)=(A B) (A C)证证任取任取:A(BC)xAyBC xA(yByC)(xAyB)(xAyC)ABAC(AB)(AC)所以有所以有A(BC)=(AB)(AC).21/383.4 笛卡尔乘积笛卡尔乘积例例2(1)证明证明A=B,C=D A C=B D(2)A C =B D是是否否推推出出A=B,C=D?为为什什么么？解解(1)任取任取 A Cx A y Cx B y D B D(2)不一定不一定.反例如下：反例如下：A=1，B=2,C =D =,则则A C =B D但是但是A B.22/383.5
18、 关系的概念关系的概念定定义义3.5.1设设A，B是是任任意意两两个个集集合合，AB的的子子集集R称称为为从从A到到B的二元关系，当的二元关系，当A=B时，称时，称R为为A上的二元关系。上的二元关系。从上述定义可以看出从上述定义可以看出A到到B的二元关系，也是序偶的集合。的二元关系，也是序偶的集合。若若R，则称，则称a与与b有关系有关系R，记作，记作a Rb。若若，则称，则称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是是任任意意两两个个
19、集集合合，R是是A到到B上上的的二二元元关关系系，若若R=，则称为空关系。若，则称为空关系。若R=AB，则称，则称R为全关系。为全关系。称为称为A上的恒等关系。上的恒等关系。全关系全关系例如：设例如：设A=0,1,2，则，则。23/383.5 关系的概念关系的概念定义定义3.5.3 设A，B是两个集合，R是从A到B上的二元关系，则 (1)若存在bB，使得R，则所有这样的aA组成的集合，称为二元关系R的定义域。记作dom(R)或D(R)，即 (2)若存在aA，使得 R，则所有这样的bB组成的集合，称为二元关系R的值域。记作ran(R)或R(R)，即 R的定义域和值域一起称作R的域，记作FLDR，
20、即 FLDR = dom(R)ran(R) 从X到Y的二元关系R，也可以用图解的方式表示，如图3.5.1所示，X和Y是两个集合。xi是集合X中的元素，yj是集合Y中的元素，当且仅当xiRyj时，才有一条从xi指向yj的有向边。24/383.5 关系的概念关系的概念图 3.5.1 图解表示法25/383.5 关系的概念关系的概念定定理理3.5.1若若R和和S是是从从集集合合A到到B上上的的两两个个二二元元关关系系，则则R和和S的并、交、补、差也是的并、交、补、差也是A到到B上的二元关系。上的二元关系。证明：因为证明：因为R和和S是从集合是从集合A到到B上的二元关系上的二元关系所以有所以有RAB，
21、SAB。从而有。从而有即即RS和和RS都是都是A到到B上的二元关系。上的二元关系。又因为又因为所以所以R和和S也是也是A到到B上的二元关系。上的二元关系。由于由于故故R-S也是也是A到到B上的二元关系上的二元关系26/383.6 关系的表示与性质关系的表示与性质 1 关系的矩阵表示2 关系的图形表示3 关系的性质 设 X=a, b, c, Y=0, 1, 2, 3，R=, , 。可得关系R的矩阵表示如下： 由上例看出，给定从有限集X到Y的二元关系R，就可以构造出它的关系矩阵。 给定两个有限集合 和 ，并且R是从X到Y的二元关系 。如果有 则称矩阵 是R的关系矩阵，并记作 。27/383.6 关
22、系的表示与性质关系的表示与性质 1 关系的矩阵表示2 关系的图形表示3 关系的性质设画出R的关系图。 解： R的关系图如图3.6.1所示。 图3.6.1 R的关系图 28/383.6 关系的表示与性质关系的表示与性质 1 关系的矩阵表示2 关系的图形表示3 关系的性质定义定义3.6.1设设R 为为A上的关系上的关系,(1)若若 x(xA R),则称则称R 在在A 上是上是自反自反的的.(2)若若 x(xA R),则称则称R 在在A 上是上是反自反反自反的的. 实例：实例：自反：全域关系自反：全域关系EA,恒等关系恒等关系IA,小于等于关系小于等于关系LA,整除关系整除关系DA反自反：实数集上的
23、小于关系、幂集上的真包含关系反自反：实数集上的小于关系、幂集上的真包含关系.A=1,2,3,R1,R2,R3是是A上的关系上的关系,其中其中 R1, R2, R3R2自反自反，R3反自反，反自反，R1既不是自反的也不是反自反的既不是自反的也不是反自反的.29/383.6 关系的表示与性质关系的表示与性质 1 关系的矩阵表示2 关系的图形表示3 关系的性质定义定义3.6.2设设R 为为A上的关系上的关系,(1)若若 x y(x,yARR),则称则称R 为为A上上对称对称的关系的关系.(2)若若 x y(x,yARRx=y),则称则称R 为为A上的上的反对称反对称关系关系.实例：实例：对称关系：对
24、称关系：A上的全域关系上的全域关系EA,恒等关系恒等关系IA和空关系和空关系反对称关系：恒等关系反对称关系：恒等关系IA和空关系也是和空关系也是A上的反对称关系上的反对称关系.设设A1,2,3,R1,R2,R3和和R4都是都是A上的关系上的关系,其中其中 R1,，R2, R3,，R4,R1：对称和反对称；：对称和反对称；R2：只有对称；：只有对称；R3：只有反对称；：只有反对称；R4：不对称、不反对称：不对称、不反对称30/383.6 关系的表示与性质关系的表示与性质 1 关系的矩阵表示2 关系的图形表示3 关系的性质定义定义3.6.3设设R为为A上的关系上的关系,若若 x y z(x,y,z
25、ARRR),则称则称R 是是A上的上的传递传递关系关系.实例：实例： A上的全域关系上的全域关系EA,恒等关系恒等关系IA和空关系和空关系，小于等小于等于和小于关系，整除关系，包含与真包含关系于和小于关系，整除关系，包含与真包含关系设设A1,2,3,R1,R2,R3是是A上的关系上的关系,其中其中 R1,R2,R3R1和和R3是是A上的传递关系上的传递关系,R2不是不是A上的传递关系上的传递关系. 31/383.6 关系的表示与性质关系的表示与性质 1 关系的矩阵表示2 关系的图形表示3 关系的性质自反性反自反性对称性反对称性传递性关系矩阵主对角线元素全是1主对角线元素全是0矩阵是对称矩阵若r
26、ij1, 且ij, 则rji0M2中1位置, M中相应位置都是1关系图每个顶点都有环每个顶点都没有环两点之间有边, 是一对方向相反的边两点之间有边,是一条有向边点xi到xj有边, xj 到xk有边, 则xi到xk也有边 32/383.7 关系的运算关系的运算 1 关系的逆运算2 关系的合成运算定定义义3.7.1设设R是是从从集集合合X到到集集合合Y的的二二元元关关系系，如如果果将将R中中每每一一对对序序偶偶的的元元素素顺顺序序互互换换，所所得得到到的的新新的的集集合合则则称称为为R的逆关系，记作的逆关系，记作，即，即由由逆逆关关系系的的定定义义可可知知，的的关关系系图图可可以以通通过过将将R的
27、的关关系系图图的的所所有有有有向向弧弧逆逆转转得得到到，它它的的关关系系矩矩阵阵可可以以通通过过将将R的的关系矩阵转置得到。关系矩阵转置得到。例例3.7.1设设，求求。解：解：。33/383.7 关系的运算关系的运算 1 关系的逆运算2 关系的合成运算定定理理3.7.1设设R和和S都都是是从从X到到Y的的二二元元关关系系，则则下下列各式成立。列各式成立。（1）（2）（3）（4），这里，这里R表示表示（5）（6）若）若，则，则34/383.7 关系的运算关系的运算 1 关系的逆运算2 关系的合成运算定理定理3.7.2设设R是是A上的二元关系，则上的二元关系，则（1）R在在A上是自反的，当且仅当上
28、是自反的，当且仅当。（2）R在在A上是反自反的，当且仅当上是反自反的，当且仅当。（3）R在在A上是对称的，当且仅当上是对称的，当且仅当。（4）R在在A上是反对称的，当且仅当上是反对称的，当且仅当。35/383.7 关系的运算关系的运算 1 关系的逆运算2 关系的合成运算定定义义3.7.2 设R是从集合X到集合Y的二元关系，S是从集合Y到Z的关系，则R S称为R和S的合成关系，定义为 R S称为关系的合成运算。 设R是从集合 到集合 的关系， S是从集合 到集合 的关系， 则 是一个 的矩阵， 是一个 的矩阵。依照普通矩阵乘法的运算，可以定义两个关系矩阵的合成运算。36/383.7 关系的运算关
29、系的运算 由上述前两个矩阵可以构造这两个矩阵的合成矩阵，记作 。 元素 可由下式得到： 其中 。和的运算规则如下： 两个关系的合成运算，就是将布尔关系矩阵做乘法，所得结果即为合成关系矩阵。 1 关系的逆运算2 关系的合成运算37/383.7 关系的运算关系的运算 1 关系的逆运算2 关系的合成运算定定理理3.4.3设设X,Y,Z和和W都都是是集集合合。R是是从从集集合合X到到Y的的关关系系，S是是从从集集合合Y到到Z的关系，的关系，T是从集合是从集合Z到到W的关系。于是有的关系。于是有(R S )T= R (ST )即关系的合成运算满足结合律。即关系的合成运算满足结合律。证证明明：对对任任意意
30、的的(R S )T，根根据据合合成成关关系系的的定定义义可可知知，必必然然存存在在zZ，使使得得(R S )，T。又又因因为为(R S )，故故必必存存在在yY，使使得得R并并且且S。由由S且且T，根根据据合合成成关关系系的的定定义义知知(ST )，又又因因为为R且且ST ，得得到到R (ST )。故故由由的的任任意意性性可可知知(R S)T R (ST )。同理可证同理可证R (S T )(R S )T。综综上上所所述述，得得到到(R S)T= R (ST )，即即关关系系的的合合成成运运算算满满足足结结合合律。律。一般来说，关系的合成运算是不满足交换律的，即一般来说，关系的合成运算是不满足
31、交换律的，即R SSR。38/383.7 关系的运算关系的运算 定义定义3.7.3设设R是集合是集合X中的二元关系，中的二元关系，nN（N是自然数集）是自然数集），于是，于是R的的n次幂次幂定义为：定义为：（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)39/383.8 关系的闭包运算关系的闭包运算 1 关
32、系的闭包定义2 关系的闭包构造方法3 关系的闭包性质定定义义3.7.1设设R是是非非空空集集合合A上上的的关关系系,R的的自自反反(对对称称或或传传递递)闭包闭包是是A上的关系上的关系R ,使得使得R 满足以下条件：满足以下条件：(1)R 是自反的是自反的(对称的或传递的对称的或传递的)(2)R R (3)对对A上上任任何何包包含含R的的自自反反(对对称称或或传传递递)关关系系R 有有RR 则则称称R是是R的的自自反反闭闭包包，记记作作r(R),（对对称称闭闭包包记记作作s(R),传传递闭包记作递闭包记作t(R).）由定义可知：由定义可知：（1）自反自反(对称或传递对称或传递)闭包闭包是关系是
33、关系（2）自自反反(对对称称或或传传递递)闭闭包包是是包包含含R的的最最小小自自反反(对对称称或或传递传递)关系关系40/383.8 关系的闭包运算关系的闭包运算 1 关系的闭包定义2 关系的闭包构造方法3 关系的闭包性质集合构造方法：集合构造方法：设设R为为A上的关系上的关系,则有则有(1)r(R)=RR0(2)s(R)=RR 1(3)t(R)=RR2R3说说明明：对对有有穷穷集集A(|A|=n)上上的的关关系系,(3)中中的的并并最最多多不不超超过过Rn（参参见见课课本本P122定理定理3.8.5）矩阵构造方法：矩阵构造方法：设关系设关系R,r(R),s(R),t(R)的关系矩阵分别为的关
34、系矩阵分别为M,Mr ,Ms 和和Mt 则则Mr=M+E Ms=M+M Mt=M+M2+M3+E 是单位矩阵是单位矩阵,M 是是转置矩阵，相加时使用转置矩阵，相加时使用逻辑加逻辑加.说明：对有穷集说明：对有穷集A(|A|=n)上的关系上的关系, Mt=M+M2+Mn41/383.8 关系的闭包运算关系的闭包运算 1 关系的闭包定义2 关系的闭包构造方法3 关系的闭包性质关系图构造方法：关系图构造方法：设设关关系系R,r(R),s(R),t(R)的的关关系系图图分分别别记记为为G,Gr,Gs,Gt,则则Gr ,Gs ,Gt 的的顶顶点点集集与与G 的的顶顶点点集集相相等等.除除了了G 的的边边以
35、以外外,以以下下述方法添加新的边：述方法添加新的边：(1)考察考察G 的每个顶点的每个顶点,若没环就加一个环，得到若没环就加一个环，得到Gr (2)考察考察G 的每条边的每条边,若有一条若有一条xi 到到xj 的单向边的单向边,ij,则在则在G中加一条中加一条xj 到到xi 的反向边的反向边,得到得到Gs(3)考察考察G 的每个顶点的每个顶点xi,找找xi 可达的所有顶点可达的所有顶点xj (允许允许i=j )， 如果没有从如果没有从xi 到到xj的边的边,就加上这条边就加上这条边,得到图得到图Gt42/383.8 关系的闭包运算关系的闭包运算 1 关系的闭包定义2 关系的闭包构造方法3 关系
36、的闭包性质例例设设A=a,b,c,d,R=,R和和r(R),s(R),t(R)的关系图如下图所示的关系图如下图所示. Rr(R)s(R)t(R)43/383.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上上的的关关系系,且且R1 R2,则则(1)r
37、(R1) r(R2)(2)s(R1) s(R2)(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)是传递的是传递的.44/383.8 关系的闭包运算关系的闭包运算 1 关系的闭包定义2 关系的闭包构造方法3 关系的闭包性质二二元元关关系系的的闭闭包包仍仍然然是是二二元元关关系系，还还可可以以求求它它的的闭闭包包。例例如如，R是是A上上的的二二元元关关系系，r(R)是
38、是它它的的自自反反闭闭包包，还还可可以以求求r(R)的的对对称称闭闭包包。r(R)的的对对称称闭闭包包记记为为s(r(R)，简简记记为为sr(R)，读读作作R的的自自反反闭闭包包的的对对称称闭闭包包。其余类似。其余类似。定理定理3.7.4 设R是集合A上的二元关系，则 （1） （2） （3） 例 题 12,习 题 :P127(1)、(2)a45/383.9集合的覆盖与划分集合的覆盖与划分1覆盖与划分覆盖与划分2 2加细与真加细加细与真加细3 3交叉划分交叉划分定定义义3.9.1 给定非空集合A，设有集合 ，其中 ，且 ， ，且 ，则称集合S为集合A的覆盖。若还满足条件 则称 S 是 A 的划分
39、.说明： 划分是覆盖的特殊情形. 划分的元素 Si 称为划分的类.例1：令 Z=所有整数的集合 A1=所有偶数的集合 A2=所有奇数的集合则 A1,A2是 Z 的一个划分。46/383.9集合的覆盖与划分集合的覆盖与划分1覆盖与划分覆盖与划分2 2加细与真加细加细与真加细3 3交叉划分交叉划分例2：已知 下面哪些集合是 A 的覆盖或划分？最小划分：是由作为类的集合本身构成.如S4最大划分：是由包含单个元素的类组成.如S547/383.9集合的覆盖与划分集合的覆盖与划分1覆盖与划分覆盖与划分2 2加细与真加细加细与真加细3 3交叉划分交叉划分定义3.9.2 设 A 和 B 是同一集合 X 的两种
40、划分,且有 A=A1,A2,.Am,B=B1,B2,.Bn若 A 的每一个类都是 B 的某一类的子集,即 则称 A 是 B 的加细。若 A 是 B 的加细,且 BA, 则称 A 是 B 的真加细。例例3 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,c48/383.9集合的覆盖与划分集合的覆盖与划分1覆盖与划分覆盖与划分2 2加细与真加细加细与真加细3 3交叉划分交叉划分定义3.9.3 若 A=A1,A2,Ar 与 B=B1,B
41、2,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 任何两种划分的交叉划分，都是原来划分的一种加细。49/383.10 等价关系与等价类等价关系与等价类1等价关系的定义等价关系
42、的定义2 2等价类的定义等价类的定义3 3商集与划分商集与划分定定义义3.10.1设设R为为非非空空集集合合上上的的关关系系.如如果果R是是自自反反的的、对对称称的的和传递的和传递的,则称则称R为为A上的上的等价关系等价关系.设设R 是一个等价关系是一个等价关系,若若R,称称x等价于等价于y,记做记做xy. 例例1设设A=1,2,8,如下定义如下定义A上的关系上的关系R：R=|x,yAx y(mod3)其中其中x y(mod3)叫做叫做x与与y 模模3相等相等,即即x除以除以3的余数与的余数与y除以除以3的余数相等的余数相等.不难验证不难验证R 为为A上的等价关系上的等价关系,因为因为(1)
43、xA,有有 x x (mod3)(2) x,yA,若若x y(mod3),则有则有y x(mod3)(3) x,y,zA,若若x y(mod3),y z(mod3),则有则有x z(mod3)模模3等价关系的关系图等价关系的关系图50/383.10 等价关系与等价类等价关系与等价类1等价关系的定义等价关系的定义2 2等价类的定义与性质等价类的定义与性质3 3商集与划分商集与划分定义定义3.10.2设设R为非空集合为非空集合A上的等价关系上的等价关系, xA，令，令xR =y |yAxRy称称xR 为为x关于关于R的等价类的等价类,简称为简称为x的的等价类等价类,简记为简记为xR实例实例A=1,
44、2,8上模上模3等价关系的等价类：等价关系的等价类：1=4=7=1,4,72=5=8=2,5,83=6=3,6定理定理3.10.1设设R是非空集合是非空集合A上的等价关系上的等价关系,则则(1) x A,x是是A的非空子集的非空子集(2) x,y A,如果如果xRy,则则x=y(3) x,y A,如果如果x y,则则x与与y不交不交(4)x|x A=A51/383.10 等价关系与等价类等价关系与等价类1等价关系的定义等价关系的定义2 2等价类的定义与性质等价类的定义与性质3 3商集与划分商集与划分证证(1)由定义由定义, x A有有x A.又又x x,即即x非空非空.(2)任取任取z,则有则
45、有zxR R R R R R从从 而而 证证 明明 了了 zy. 综综 上上 所所 述述 必必 有有 x y. 同同 理理 可可 证证 y x.这就得到了这就得到了x=y.(3) 假假 设设 xy, 则则 存存 在在 z xy, 从从 而而 有有z xz y,即即 R R成立成立.根据根据R的对称性和传递性必有的对称性和传递性必有 R,与与xy矛盾矛盾(4)先证先证x|x A A. 任取任取y,y x|x A x(x Ay x)y xx A y A 从而有从而有x|xA A再证再证A x|xA.任取任取y,y A y yy A yx|x A从而有从而有x|xA A成立成立.综上所述得综上所述得
46、x|x A=A.52/383.10 等价关系与等价类等价关系与等价类1等价关系的定义等价关系的定义2 2等价类的定义与性质等价类的定义与性质3 3商集与划分商集与划分定义定义3.10.3设设R 为非空集合为非空集合A上的等价关系上的等价关系,以以R 的所有等价的所有等价类类 作作 为为 元元 素素 的的 集集 合合 称称 为为 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关于恒等关系和全域关系的商集为：关于恒等关
47、系和全域关系的商集为： A/IA =1,2,8，A/EA =1,2,8定义定义3.10.4设设A为非空集合为非空集合,若若A的子集族的子集族( P(A)满足满足:(1) (2) x y(x,y xyxy=)(3) =A则称则称是是A的一个的一个划分划分,称称中的元素为中的元素为A的的划分块划分块.53/383.10 等价关系与等价类等价关系与等价类1等价关系的定义等价关系的定义2 2等价类的定义与性质等价类的定义与性质3 3商集与划分商集与划分例例3给出给出A1,2,3上所有的等价关系上所有的等价关系解解先做出先做出A的划分的划分,从左到右分别记作从左到右分别记作 1, 2, 3, 4, 5.
48、1对应对应EA,5对应对应IA,2,3和和4分别对应分别对应R2,R3和和R4. R2=,IAR3=,IAR4=,IA1231 1235123212341233例题14,习题:P134(3)、(5)54/383.11 偏序关系偏序关系1偏序关系与偏序集偏序关系与偏序集2 2 盖住与哈斯图盖住与哈斯图3 3 链与全序关系链与全序关系4 4 偏序集中的特殊元素及性质偏序集中的特殊元素及性质定义定义1:设设R 为定义在集合为定义在集合A 上的一个关系上的一个关系,若若R 是是 a)自反的自反的 b)反对称的反对称的 c)传递的传递的则则R 称为称为偏序关系偏序关系，记为，记为 .序偶序偶称作称作偏序
49、集偏序集.例1 证明在实数集R上, 是偏序关系.证明： 1）对于任何 a R，有 a a 成立，故 是自反的； 2）对于任何 a,b R, 如果有 a b 且 b a 成立，则必有 a=b ,故 是反对称的； 3）如果有 a b, b c 成立，则必有 ac, 故 是传递的。 因此是偏序关系。55/383.11 偏序关系偏序关系1偏序关系与偏序集偏序关系与偏序集2 2 盖住与哈斯图盖住与哈斯图3 3 链与全序关系链与全序关系4 4 偏序集中的特殊元素及性质偏序集中的特殊元素及性质例例2 2 已知 A=2,3,6,8, =|x整除y，验证 是偏序关系.证明：56/383.11 偏序关系偏序关系1
50、偏序关系与偏序集偏序关系与偏序集2 2 盖住与哈斯图盖住与哈斯图3 3 链与全序关系链与全序关系4 4 偏序集中的特殊元素及性质偏序集中的特殊元素及性质定定义义2：在在偏偏序序集集合合中中，如如果果x , y A, x y, x y,且且没没有有其其它它元元素素z,满满足足x z, z y, 则则称称元元素素y 盖盖住住元元素素x .并并且记且记 COVA=| x, y A;y 盖住盖住x 对于给定偏序集合 ，它的盖住关系是唯一的。所以可用盖住的性质画出偏序集合图，称为哈斯图对于给定偏序集合对于给定偏序集合，其哈斯图做图规则如下：，其哈斯图做图规则如下：（1）用小圆圈代表元素；）用小圆圈代表元
51、素；（2）如如果果x y 且且x y，则则将将代代表表y的的小小圆圆圈圈画画在在代代表表x的小圆圈之上；的小圆圈之上；（3）如果）如果 COVA,则在则在x与与y之间用直线连接。之间用直线连接。57/383.11 偏序关系偏序关系1偏序关系与偏序集偏序关系与偏序集2 2 盖住与哈斯图盖住与哈斯图3 3 链与全序关系链与全序关系4 4 偏序集中的特殊元素及性质偏序集中的特殊元素及性质例例3 3 A 是 m=12 的因子集合, 为整除关系, 求 COVA，并画出哈斯图。解: =, , , , ,IACOVA=,6,12哈斯图是简化的关系图哈斯图是简化的关系图(1)自反性：每个顶点都有自回路，自反性
52、：每个顶点都有自回路，省去自回路省去自回路。(2)反对称性：从小到大安置顶点，反对称性：从小到大安置顶点，可省略箭头可省略箭头。(3)传传递递性性：由由于于有有(，)，(，)R则则(，)R，故只画（，），（，）对应的边，故只画（，），（，）对应的边，省略边（，）。省略边（，）。58/383.11 偏序关系偏序关系1偏序关系与偏序集偏序关系与偏序集2 2 盖住与哈斯图盖住与哈斯图3 3 链与全序关系链与全序关系4 4 偏序集中的特殊元素及性质偏序集中的特殊元素及性质例例4 4 画出哈斯图59/383.11 偏序关系偏序关系1偏序关系与偏序集偏序关系与偏序集2 2 盖住与哈斯图盖住与哈斯图3 3
53、链与全序关系链与全序关系4 4 偏序集中的特殊元素及性质偏序集中的特殊元素及性质A1=1,2,3,4 为小于等于关系为小于等于关系A2=,a,a,b,a,b,c 为包含关系为包含关系不同的偏序集不同的偏序集,哈斯图可以有同样的结构哈斯图可以有同样的结构60/383.11 偏序关系偏序关系1偏序关系与偏序集偏序关系与偏序集2 2 盖住与哈斯图盖住与哈斯图3 3 链与全序关系链与全序关系4 4 偏序集中的特殊元素及性质偏序集中的特殊元素及性质定定义义4：设设是是一一偏偏序序集集合合，在在A 的的一一个个子子集集中中，如如果果每每两两个个元元素都是有素都是有(无无)关系的，则称这个子集是链关系的，则
54、称这个子集是链(反链反链)。约定：若 A 的子集只有单个元素,则它既是链又是反链.例例6 6 已知已知A=a,b,c,d,eR=,验证验证是偏序集，画出哈斯图，举例说明链和反链。是偏序集，画出哈斯图，举例说明链和反链。解：解： = =1000011000101001011011111RM关关系系矩矩阵阵对对角角线线都都为为1，且且rij 和和rji 不不同同时时为为1，所所以以R 是是自自反反的的和和反对称反对称的的。定定义义5：在在偏偏序序集集中中，如如果果A是是一一个个链链，则则称称为为全全序序集集合合(线序集合线序集合)，二元关系，二元关系 为全序关系为全序关系(线序关系线序关系)。61
55、/383.11 偏序关系偏序关系1偏序关系与偏序集偏序关系与偏序集2 2 盖住与哈斯图盖住与哈斯图3 3 链与全序关系链与全序关系4 4 偏序集中的特殊元素及性质偏序集中的特殊元素及性质关系图关系图R是传递的。是传递的。COVA=,哈斯图哈斯图a、b,d和和c,d是反链是反链a、a,b,c,e和和a,d,e是链是链62/383.11 偏序关系偏序关系1偏序关系与偏序集偏序关系与偏序集2 2 盖住与哈斯图盖住与哈斯图3 3 链与全序关系链与全序关系4 4 偏序集中的特殊元素及性质偏序集中的特殊元素及性质极极大大元元：设设是是一一个个偏偏序序集集合合,且且B是是A的的子子集集,若若有有某某个个元元
56、素素b B,B中没有任何元素中没有任何元素x满足满足b x 且且b x ，则称则称b为为B的极大元的极大元极极小小元元：设设是是一一个个偏偏序序集集合合,且且B是是A的的子子集集,若若有有某某个个元元素素b B,B中没有任何元素中没有任何元素x满足满足b x 且且x b ，则称则称b为为B的极小元的极小元例例7 7 已知已知A=2,3,5,7,14,15,21,偏序关系哈斯图如下偏序关系哈斯图如下:B 的极大元集：21,14B 的极小元集：2,7,3极大元与极小元不唯一极大元与极小元不唯一当 B=A 时，其极大元集是14,21,15，极小元集是2,7,3,563/383.11 偏序关系偏序关系
57、1偏序关系与偏序集偏序关系与偏序集2 2 盖住与哈斯图盖住与哈斯图3 3 链与全序关系链与全序关系4 4 偏序集中的特殊元素及性质偏序集中的特殊元素及性质最最大大（小小）元元：设设是是一一个个偏偏序序集集合合,且且B是是A的的子子集集,若若有有某某个个元元素素b B,对对于于B中中每每一一个个元元素素x有有x b (b x) ,则则称称b为为B的最大元的最大元(最小元最小元).定理定理1：令令 为偏序集且 BA，若 B 有最大(最小)元,则必是唯一的.例例例例8 8B=a,B=a, 、B=B=a,ba,b最大元、最小元最大元、最小元最大元、最小元最大元、最小元B最大元：最大元：aB最小元：最小
58、元：B最大元：无最大元：无B最小元：无最小元：无64/383.11 偏序关系偏序关系1偏序关系与偏序集偏序关系与偏序集2 2 盖住与哈斯图盖住与哈斯图3 3 链与全序关系链与全序关系4 4 偏序集中的特殊元素及性质偏序集中的特殊元素及性质上上(下下)界界：设设是是一一个个偏偏序序集集合合,对对于于B A, 若若有有a A,且且对对B的的任任意意元元素素x都都满满足足x a (a x),则则称称a为为子子集集B的的上上界界(下下界界).B=a,b,c,d,e,f,g上界：上界：h,i,j,k下界：无下界：无B=h,i,j,k上界：上界：无无下界：下界：a,b,c,d,e,f,gB=h,i,f,g
59、上界：上界：k下界：下界：a上界、下界上界、下界不唯一不唯一65/383.11 偏序关系偏序关系1偏序关系与偏序集偏序关系与偏序集2 2 盖住与哈斯图盖住与哈斯图3 3 链与全序关系链与全序关系4 4 偏序集中的特殊元素及性质偏序集中的特殊元素及性质上上（下下）确确界界：设设是是一一个个偏偏序序集集合合且且B A, a 为为 的的任任一一上上界界，若若对对 的的所所有有上上界界y ，都都有有a y则则称称a为为B的的最最小小上上界界(上上确确界界).若若为为 的的任任一一下下界界，若若对对的的所所有有下下界界y ，都都有有y b则称则称b为为B的最大下界的最大下界(下确界下确界).良序：任意偏
60、序集合, 假如它的每一个非空子集存在最小元素，这种偏序集称为良序的。定理2：每一个良序集合，一定是全序集合。定理3：每一个有限的全序集合，一定是良序集合。66/383.11 偏序关系偏序关系1偏序关系与偏序集偏序关系与偏序集2 2 盖住与哈斯图盖住与哈斯图3 3 链与全序关系链与全序关系4 4 偏序集中的特殊元素及性质偏序集中的特殊元素及性质例例1 1 设偏序集 ，画出哈斯图,并求 B = 2,3,6 上、下(确)界上界： 6,12,24,36上确界：6下(确)界： 无67/383.11 偏序关系偏序关系1偏序关系与偏序集偏序关系与偏序集2 2 盖住与哈斯图盖住与哈斯图3 3 链与全序关系链与全序关系4 4 偏序集中的特殊元素及性质偏序集中的特殊元素及性质例例2 2 设偏序集,画出哈斯图,并求 B = 2,3,6 上、下(确)界上界： 6,12上确界：6下(确)界： 1P139例例16，习题：，习题：p146(6)68/38 第一篇结束了第一篇结束了. . .思考思考别忘了总结与回顾别忘了总结与回顾!
