《第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 等分别表示自然数、整
4、数、有 理数、实数、复数集合,2. 集合表示法 枚举法-通过列出全体元素来表示集合 谓词表示法-通过谓词概括集合元素的性质 实例: 枚举法: 谓词法:,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
5、 B B A 定义6.3 A B A B A B ,A是B的真子集 A B x ( xA xB ) 思考: 和 的定义 注意 和 是不同层次的问题,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:包含了所有集合的集合 全集具有相对性:与问题有关,不存在绝对的全集,
6、3.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)d,3.2 集合的基本运算,1 集合的运算 2 集合运算算律,集合的基本运算有: 并 AB = x | xA xB 交 AB = x | xA xB 相对补 AB = x | xA xB 对称差 AB = (AB)(BA) 绝对补 A = EA,文氏图,
7、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 集合的基本运算,1 集合的运算 2 集合运算算律,任何代数运算都遵从一定的算律,集合运算也不例外。下面给出集合运算的主要算律,其中A,B,C表示任意的集合。 幂等律 结合律 交换律 分配律 同一律 零 律 排中律 矛盾律 吸收律 双重否定律 德摩根律,3.2 集合的基本运算,1
8、 集合的运算 2 集合运算算律,除了以上算律,还有一些关于集合运算性质的重要结论,在此一并给出。 建立了相对补运算和交运算之间的联系,可以利用它将相对补转变成交。 给出了 的三种等价的定义,为证明两个集合之间包含关系提供了新方法,同时也可以用于集合公式的化简。,习题:P95(11)a,*3.3 集合中元素的计数包含排斥原理,集合A含有n个元素,可以说集合A的基数是n,记作card A=n。所谓基数就是表示集合中所含元素多少的量。如果集合A的基数是n,也可以记为|A|=n。显然空集的基数是0,即|=0 。 定义3.3.1 设为集合,若存在自然数n(0也是自然数),使得|A|=card A=n ,
9、则称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=24 | B-A| = |B|-| AB|=35-23=12 从而得到| AB|=24+23+12=59, 故,| (AB)|=100-59=41, 即两种语言都不熟悉的有41人。,*3.3 集合中元素的计数
10、包含排斥原理,设S是有穷集,P1和P2分别表示两种性质,对于S中的任何一个元素x,只能处于以下四种情况之一: (1)只具有性质P1 ; (2)只具有性质P2 ; (3)具有P1和P2两种性质; (4)两种性质都没有。 令A1和A2分别表示S中具有性质P1和P2的元素的集合。为了使表达式简洁,对任何集合B,用 代替B。由文氏图不难得到以下公式 这就是容斥原理的一种简单形式。 如果涉及到三条性质,容斥原理的公式则变成,*3.3 集合中元素的计数包含排斥原理,定理 3.3.1 S中不具有性质P1, P2, , Pm的元素数是 定理3.3.1证明略。 推论 在S中至少具有一条性质的元素数是,*3.3
11、集合中元素的计数包含排斥原理,例:某班学生150人。数学考试成绩90分以上的有80人,语文考试成绩90分以上的有75人,两门课程均在90分以上的有50人,问 (1)只有一门课程成绩90分以上的学生有多少人? (2)两门课程成绩均不在90分以上的学生有多少人? 解:全集为该班学生组成的集合。设 由题意可知 (1)即需求 。因为 所以, ,即 (2)即需求,3.4 笛卡尔乘积,定义7.1 由两个元素 x 和 y,按照一定的顺序组成的二元组 称为有序对,记作. 有序对性质: (1) 有序性 (当xy时) (2) 与相等的充分必要条件是 = x=uy=v,定义7.2 设A,B为集合,A与B的笛卡儿积记
12、作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 或 B 中有一个为空集,则 AB 就是空集. A = B = (5) 若 |A|
13、= 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
14、的二元关系,当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,使得
15、R,则所有这样的aA组成的集合,称为二元关系R的定义域。记作dom(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
16、和S的并、交、补、差也是A到B上的二元关系。 证明:因为R和S是从集合A到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
17、关系的表示与性质,1 关系的矩阵表示 2 关系的图形表示 3 关系的性质,设 画出R的关系图。 解: R的关系图如图3.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,
18、 R2, R3 R2 自反 ,R3 反自反,R1既不是自反的也不是反自反的.,3.6 关系的表示与性质,1 关系的矩阵表示 2 关系的图形表示 3 关系的性质,定义3.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:只有对称;
19、R3:只有反对称; R4:不对称、不反对称,3.6 关系的表示与性质,1 关系的矩阵表示 2 关系的图形表示 3 关系的性质,定义3.6.3 设R为A上的关系, 若 xyz(x,y,zARRR), 则称 R 是A上的传递关系.,实例: A上的全域关系 EA,恒等关系 IA和空关系 ,小于等 于和小于关系,整除关系,包含与真包含关系 设 A1,2,3, R1, R2, R3是A上的关系, 其中 R1, R2, R3 R1和R3是A上的传递关系, R2不是A上的传递关系.,3.6 关系的表示与性质,1 关系的矩阵表示 2 关系的图形表示 3 关系的性质,3.7 关系的运算,1 关系的逆运算 2 关
20、系的合成运算,定义3.7.1 设R是从集合X到集合Y的二元关系,如果将R中每一对序偶的元素顺序互换,所得到的新的集合则称为R的逆关系,记作 ,即 由逆关系的定义可知, 的关系图可以通过将R的关系图的所有有向弧逆转得到,它的关系矩阵可以通过将R的关系矩阵转置得到。 例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上的二元关系,则 (
21、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和S的合成关系,定义为 R S称为关系的合成运算。 设R是从集合 到集合 的关系, S是从集合 到集合 的关系, 则 是一个 的矩阵, 是一个 的矩阵。依照普通矩阵乘法的运算,可以定义两个关系矩阵的合成运算。,3.7 关系的运算,由上述前两个矩阵可以构造这两个矩阵的合成矩阵,记作 。 元素
22、可由下式得到: 其中 。和的运算规则如下: 两个关系的合成运算,就是将布尔关系矩阵做乘法,所得结果即为合成关系矩阵。,1 关系的逆运算 2 关系的合成运算,3.7 关系的运算,1 关系的逆运算 2 关系的合成运算,定理3.4.3 设X, Y, Z和W都是集合。R是从集合X到Y的关系,S是从集合 Y到Z的关系,T是从集合Z到W的关系。于是有 (R S ) T= R ( S T ) 即关系的合成运算满足结合律。 证明:对任意的 (R S ) T,根据合成关系的定义可知,必然存在zZ,使得 (R S ), T。又因为 (R S ),故必存在yY,使得 R并且 S。由 S且 T,根据合成关系的定义知
23、( 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次幂 定义为: (1) ,即 是R中的恒等关系。 (2) 。 定理3.7.4 设R是集合X中的二元关系。设m, nN。则有 (1) (2) 定理3.7.5 设R是A上的二元关系,则R在A上是传递
24、的,当且仅当,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), 传递闭包记作t(R). ) 由定义可知: (1)自反(对称或传递)闭包是关系 (2)自反(对称或传递)闭包是包含R的最小自反(对称或传
25、递)关系,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 是 转置矩阵,相加时使用逻辑加. 说明:对有穷集A(|A|=n)上的关系, Mt=M+M
26、2+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 ), 如果没有从 xi
27、 到 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)
28、 (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) 是传递的.,3.8 关系的闭包运算,1 关系的闭包定义 2 关系的闭包构造方法 3 关系的闭包性质,二元关系的闭包仍然是二元关系,还可以求它的闭包。例如,R是A上的二元关系,r(R)是它的自反闭包,还可以求r(R)的对称闭包。r(R)的对称闭包记为s(r(R),简记为sr(R),读作R的自反闭包的对称闭包。其余类似。,定理
29、3.7.4 设R是集合A上的二元关系,则 (1) (2) (3),例题12,习题: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 的覆盖或划分?
30、,最小划分:是由作为类的集合本身构成.如S4 最大划分:是由包含单个元素的类组成.如S5,3.9集合的覆盖与划分,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
31、,b,c B6=a,d,b,c,3.9集合的覆盖与划分,1覆盖与划分 2加细与真加细 3交叉划分,定义3.9.3 若 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 的两种划分,则其交叉
32、划分也是原集合的一种划分。 定理2 任何两种划分的交叉划分,都是原来划分的一种加细。,3.10 等价关系与等价类,1等价关系的定义 2等价类的定义 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) (
33、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.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.1
34、0.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有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
35、矛盾 (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 的所有等价 类作为元素的集合称为A关于R的商集, 记做A/R, A/R = xR | xA 实例 设 A=1,2,8,A关于模3等价关系R的商集为 A/R = 1,4,7, 2,5,8, 3,6 A关于恒
36、等关系和全域关系的商集为: 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, 2, 3 和 4分别对应 R2, R3和 R4. R2=,IA R3=,IA R4=,IA,例题14,习题:P
37、134(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 成立,则必有 ac, 故 是传递的。 因此是偏序关系。,3.11 偏序关系,1
38、偏序关系与偏序集 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,对于给定偏序集合 ,它的盖住关系是唯一的。所以可用盖住的性质画出偏序集合图,称为哈斯图,对于给定偏序集合 ,其哈斯图做图规则如下: (1
39、)用小圆圈代表元素; (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)传递性:由于有(,)
40、,(,)R 则 (,)R,故只画(,),(,)对应的边,省略边(,)。,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 的一个子集中,如果每两个元素都
41、是有(无)关系的,则称这个子集是链(反链)。,约定:若 A 的子集只有单个元素,则它既是链又是反链.,例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 盖住与哈斯图
42、 3 链与全序关系 4 偏序集中的特殊元素及性质,极大元:设 是一个偏序集合, 且 B 是 A 的子集,若有某个元素 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,14 B 的极小元集:2,7,3,极大元与极小元不唯一,当 B=A 时,其极大元集是14,21,15,极小元集是2,7,3,5,3.11 偏序
43、关系,1 偏序关系与偏序集 2 盖住与哈斯图 3 链与全序关系 4 偏序集中的特殊元素及性质,最大(小)元:设 是一个偏序集合, 且 B 是 A 的子集,若有某个元素 b B, 对于B 中每一个元素 x 有 xb (b x) , 则称 b 为 B 的最大元(最小元).,定理1: 令 为偏序集且 BA,若 B 有最大(最小)元,则必是唯一的.,例8 B=a, 、B=a,b最大元、最小元,B最大元:a B最小元: 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,d,e,f,g,上界: k 下界:a,上界、下界 不唯一,3.11 偏序关系,1 偏序关系与偏序集 2 盖住与哈斯图 3 链与全序关系 4 偏序集中的特殊元素及性质,上(下)确界:设 是一个偏序集合且 B A, a 为 的任一上界,若对
链接地址:https://www.31doc.com/p-2255079.html