离散数学二元关系与运算.ppt

二元关系和运算,第四章,1. 二元有序组：由两个元素x和y按一定顺序排成二元组，记作： 。,4.1 二元关系的概念,如： 平面直角坐标系中点的坐标,一、二元关系的概念,二元有序组的性质,(1) 当x y时， ,(2) = ，当且仅当x = u，y = v,(1)、(2)说明有序组区别于集合,n元有序组：由n个元素x1，x2，xn，按一定顺序排成的n元组，记作：(x1，x2，xn) 。,2. 一种新的集合运算 积运算 ：,设A、B为两集合，用A中元素为第一元素，B中元素作为第二元素构成的二元有序组的全体叫做A和B的笛卡儿积。,记作：A B,符号化：A B = | xA y B,例4.1 设A=a,b，B=0,1,2 ，求AB，BA,解：根据笛卡儿积的定义知,A B = , , , ,B A = , , ,一般地：如果|A|=m，|B|=n，则 |AB|=|BA|=m n, , , , ,积运算的性质,(1) 若A，B中有一个空集，则笛卡儿积是空集，即： B = A = ,(2) 当AB，且A，B都不是空集时，有ABBA,(3) 当A，B，C都不是空集时，有(AB)C A(BC),因为(AB)C中的元素, z，而A(BC)中的元素为 。,(4) A(BC) = (AB)(AC) (对的分配律),(BC)A = (BA)(CA),A(BC) = (AB)(AC),(BC)A = (BA)(C A),我们证明：,A(BC) = (AB)(AC),( ? ),( ? ),( ? ),证明思想,要证明两个集合相等，通常有两种方法：一是证两个集合相互包含；,二是利用已有的集合运算的性质(算律和已证明过的公式)，仿照代数恒等式的证明方法，一步步从左(右)边推出右(左)边，或从左、右边分别推出同一个集合式子。,一般说来，最基本的集合相等关系要用第一种证法，比较复杂的集合相等关系用第二种方法更好，但第二种方法的使用取决于我们对算律和常用公式的熟练程度。,证明： 用第一种方法,对于任意的 A ( BC ), xAy(BC), xA(yByC ), (xAyB)(xAyC), ABAC, (AB)(AC), A(BC)=(AB)(AC),例4.2 设A=1,2，求P(A)A,解： P(A)A,= ，1，2，1,2,= ，,n阶笛卡儿积：,= (x1,x2, xn) | x1A1x2A2 xnAn,A1 A2 An,1,2,，,，,，,二元关系：如果一个集合的元素都是二元有序组，则这个集合称为一个二元关系，记作：R 。,如果 R ，记作 x R y,3、二元关系的数学定义,从A到B的二元关系：设A，B为集合，A B的任何子集所定义的二元关系叫做从A到B的二元关系。,若A=B，叫做 A上的二元关系；,若|A|n，则|AA|n2。,就是说，A上有 个不同的二元关系，其中包括空关系、全域关系UA和恒等关系IA。,AA的所有子集有 个。,例4.3 设A = a,b，写出P(A)上的包含关系R ：,解： P(A) = ,a,ba,b,R = , , , ,A上关系的表示法,1. 关系矩阵：,设A=x1, x2, , xn)，R是A上的关系，,则 (rij)nxn =,是R的关系矩阵,令：,二、二元关系的表示方法,2. 关系图：,以E = | xiAxjAxiRxj为有向边集组成的有向图G = ,以V=A=x1, x2, xn 为顶点集，,例4.4 设A=1,2,3,4，R=,是A上的关系，试写出R的关系矩阵并画出关系图：,解： 关系矩阵 ：,0 0 1 1,0 0 0 0,0 1 0 0,关系图 ：,4.2 关系的运算,关系R的定义域： domR = x | (y)R (即R中有序组的第一个元素构成的集合),关系R的值域： ranR =y | (x)R (即R中有序组的第二个元素构成的集合),一、关系的定义域与值域,例4.5 下列关系都是整数集Z上的关系，分别求出它们的定义域和值域：,(1) R1= | x, y Z xy,(2) R2= | x, y Z x2+y2=1,(3) R3= | x, y Z y=2x,(4) R4= | x, y Z |x|=|y|=3,解： domR1 = ranR1 = Z,解： R2 = , ,domR2 = ( ? ),ranR2 = ( ? ),(1) R1= | x, y Z xy,(2) R2= | x, y Z x2+y2=1, ,解： domR3 = Z， ranR3 = 偶数,解： domR4 = ranR4 = ( ? ),(3) R3= | x, y Z y=2x,(4) R4= | x, y Z |x|=|y|=3,二、关系的常用运算,F是任意关系，F的逆F1= | yFx,F、G是任意两个关系，F与G的合成记作：F G= | (z)(xGzzFy),关系F在集A上的限制，记作：F | A= | xFyxA,集A在关系F下的象FA = ran(F | A),(1) 逆：,(2) 合成：,(3) 限制：,(4) 象：,例4.6 设F，G是N上的关系，其定义为：,F = | x, yNy = x2,G = | x,yNy = x+1,求 G1，F G，G F，F |1,2，F1,2,解：由定义知：,G1 = | y, xNy = x+1,列出G1 中的元素就是,G1 = ,为了求F G，可以先直观表示如下：,对任何xN,即 y = (x+1)2,因此 F G = | x,yNy = (x+1)2,同理可求 G F = | (?) (自己做！),发现 F G G F,F |1,2 = ,F 1,2 = ran(F |1,2) = 1,4,关系运算的性质：设F、G、H、为任意关系，则有：,(1) (F1)1 = F,(2) domF1 = ranF，ranF1 = domF,(3) (F G) H = F (G H),(4) (F G)1 = G1 F1,(5) F (GH) = F GF H (对的分配律),(6) F (GH) F GF H (对的半分配律),(7) (GH) F = G FH F,(8) (GH) F G FH F,( ? ),( ? ),任取, (F G)1, F G, (z)( G F), (z)( G1 F1), G1 F1,(4) (F G)1 = G1 F1的证明：,任取,F (GH), (z)(GH)F), (z)(GH)F) (注意对括号的顺序), (z)(GF(HF), F GF H, F (GH) = F GF H,(5) F (GH) = F GF H的证明：,4.3 关系的性质,R的关系矩阵：主对角线元素全是1,R的关系图：每个顶点都有环,自反性： x A 有R (R是A上的关系),关系矩阵：主对角线元素全是0,关系图： 每个顶点都没有环,反自反性：x A R,对称性：若 R，则 R,关系矩阵：对称阵,关 系 图：如果两个顶点之间有边，一定是一对方向相反的边。,反对称性：若 R且xy，则 R,关系矩阵：如果rij = 1，且 i j，则rji = 0,关系图： 如果两个顶点之间有边，一定是只有一条有向边。,传递性：若 R且 R，则 R,关系图：如果顶点xi到xj有边， xj到xk有边，则从xi到xk有边,例4.7 设A=1,2,10，对于A上的关系R= | (xy)/3I,I为整数集，问R有哪些性质？,解：逐条性质加以验证R= | (xy)/3I,任取A中元素x，由于(xx)/3=0，所以R是自反的；,又设A中任意两个元素x,y，如果 xRy，即xy可被3整除，则yx也一定可被3整除，即yRx，从而R是对称的；,如果A中三 个元素x，y，z满足xRy， yRz，则x y，yz被3整除，由于xz=(xy)+(yz)，所以xz被3整除，从而xRz即R具有传递性。,4.4 关系的闭包运算,闭包：设RAA，,自反闭包 记作 r(R),对称闭包 记作 s(R),传递闭包 记作 t(R),由A求r(R)，s(R)，t(R)的过程叫闭包运算。,那么，包含R而使之具有自反性质的最小关系，称之为R的自反闭包；,包含R而使之具有对称性质(传递性质)的最小关系，称之为R的对称(传递)闭包。,一、定义,幂运算：设RAA，kN，约定,(1) R0 = IA = | xA,(2) R1 = R,(3) Rk+1 = Rk R,显然 Rm Rn = Rm+n (Rm)n = Rmn,二、计算方法,为了有效地计算关系R的各种闭包，先引进关系的幂运算概念。,闭包运算的方法：设R是A上的任一关系，则,(1) r (R) = RIA,(2) s (R) = RR,(3) t (R) = RR2R3 Rn,矩阵形式：(M为R的关系矩阵),(1) Mr = M + E,(2) Ms = M + M (M 是M的转置),(3) Mt = M+M2+M3,其中“ +” 均表示“ 逻辑加”,例4.8 设A=a,b,c,d，A上的关系,求 r (R)，s (R) 和 t (R),解： r(R) = RIA,=, , , , , , ,R=, ,= R,三、实例,s(R) = RR,=,t(R) = RR2R3,= R,而R2 = R R,R3 = R2 R,R4 = R3 R,= ,= ,= , , , ,实际上，看到当k 4时，已有R4 RR2R3,故 t(R) = RR2R3,=, ,四、闭包运算的性质,设A是有限集且|A| = n，RAA，则：,4.6 等价关系和偏序关系,等价关系：集A上的关系R是自反的, 对称的和传递的。,等价类： R是集A上的等价关系，对于任一aA，,aR=x | aRx, xA,被称为a的等价类。,即A中所有和a有R关系的元素的集合。,一、等价关系及用途,等价类的性质：R是非空集合，对任意的x，yA，下面的结论成立：,(1) x且xA (等价类为A的子集),(2) 若xRy，则x = y,(3) 若xRy，则xy = ,集A在等价关系R下的商集：设R为非空集A上的等价关系，以R的不交的等价类为元素的集合叫做A在R下的商集，记作A/R.,即：,A/R = xR | xA,集A的划分：设A是非空集合，,(1) ,(2) 中任意两个元素不交,(3) 中所有元素的并集为A,则 为A的划分。,如果存在一个A的子集族， P(A)满足以下条件：,由等价类的性质和商集的定义可知，商集A/R是A的划分，称之为由R诱导的划分。,反过来，给定A的任一划分 ，则A被分割成若干个划分块。,若定义A上的二元关系R：x，yA且x,y属 的同一块，则xRy，那么R是A上的等价关系，称之为由 诱导的等价关系。,集A上的等价关系与划分是一一对应的。,例4.9 设A=1,2,3，求出A上所有的等价关系：,解：先求A的各种划分：只有1个划分块的划分1，具有两个划分块的划分2， 3，和4，具有3个划分块5。,1 = A,2 = 1,2,3，,4 = 3,1,2，,3 = 2,1,3，,5 = 1,2,3,设对应于划分i 的等价关系 Ri，i = 1,2,5，则有,R5 = ，,R1 = ，,R2 = ，,R3 = ，,R4 = ，,，,，,，,，,，,，,，,，,偏序关系：集A上的关系R是自反的，反对称的和传递的，记作“ ”，且称<A, )为偏序集。,二、偏序关系及用途,例4.10 设A=2,4,6,8，A上关系R是通常意义下的小于或等于关系，试写出R并验证它是偏序关系。,解：R=, , , ,(1)自反性：,(2)反对称性：,(3)传递性：, , , ,均属于R,对任意的R， 必有xy，当xy时， yx，从而R,对任意的R， R,由于 xyyz ，所以xz，从而R。,例4.11 设C=a,b,a,b,，C上关系T是集合的“ 包含于”，试写出T，并验证它是偏序关系。,解： 同例4.10类似，自己做！,偏序集的哈斯图,(1) 用小圆圈表示偏序集的元素 (称为结点)；,(2) 按每个元素在偏序中的次序从底向上列结点位置；,(3) 对于偏序集中任意两个元素x和y，如果xy且不存在另一个元素a，使xaay，则在x与y两结点之间划上一杠，即“ | ” (x在下，y在上),全序关系：设是偏序集，,(x)(y)(xAyA(xyyx),成立，则称<A,)为全序集，这时的偏序关系叫全序关系。,全序集<A,)中全部元素可以排序，它的哈斯图为一条直线。,如果,偏序集中的一些特殊元素,设是偏序集，BA,(1) 如果yB，使得(x)(xByx)为真，则y是B的最小元 (“ 小于” B中所有元 ),(2) 如果yB，使得(x)(xB xy)为真，则y是B的最大元 (“ 大于” B中所有元 ),(4) 若yB，使得 (x)(xBxy)，则称y是B的极大元 (B中没有比y大的其他元),(5) 若yA，使得(x)(xB xy)为真，则称y是B的上界,(3) 若yB，使得 (x)(xBxy)，则称y是B的极小元 (B中找不到x小于y ),(6) 若yA，使得(x)(xB yx)为真，则称y是B的下界,(7) 令C=y | y为B的上界，则称C的最小元为B的上确界或最小上界,(8) 令D =y | y为B的下界，则D的最大元为B的下确界或最大下界,例4.12 画出和的哈斯图，并指出其中的特殊元。,解： (1) 的哈斯图如下：,由图可知1为最小元，没有最大元；,7,8,9,10,11, 12均为极大元，极小元为1；,1为1,2,12的下界，也是下确界；,1,2,12中没有上确界或上界。,(2) 的哈斯图如下：,P(a,b,c)=,a,b,c,a,b,a,c,b,c,a,b,c,由图可知： 为P(a,b,c)的最小元，a,b,c为它的最大元；,同时，a,b,c也分别为它们的极小元和极大元、下确界和上确界。,a,b,c,d,e,例4.13 已知偏序集的哈斯图如下：,h,g,f,试写出对应的A和A上的偏序关系R，并指出A中的特殊元。, , , , ,解： A = a,b,c,d,e,f, g,h,直接由哈斯图可知：A中没有最小元和最大元；,e, g和h均为A的极大元，a, b, f 和h均为A的极小元；没有上确界和下确界。,R = ,a,b,c,d,e,h,g,f, ,小结与学习要求：,了解二元关系的定义和表示方法；熟练掌握关系的性质和运算；特别是复合和三种闭包运算;理解等价关系和偏序关系，明确它们在描述研究对象的结构和特点时重要作用 (即分类和覆盖)。它们在计算机科学中有重要应用。,