离散数学,二元关系与运算

《离散数学,二元关系与运算》由会员分享，可在线阅读，更多相关《离散数学,二元关系与运算（60页珍藏版）》请在金锄头文库上搜索。

1、1. . 二元有序组二元有序组二元有序组二元有序组：由两个元素由两个元素x和和y按一定顺序按一定顺序排成二元组，记作：排成二元组，记作： 。4.1 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中元素作为第二元素构成的二元有序组的全

2、体叫做A和B的笛卡儿积。记作：A B符号化：A B = | xA y B例例 设A=a,b，B=0,1,2 ，求A B，B A解：解：根据笛卡儿积的定义知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都不是空集时，有(A B) C A (B C)因为(A B)C中的元素 , z，而A (B C)中的元素为 x, 。(4) A (BC) = (A B)(A C) ( 对

3、的分配律)(BC) A = (B A)(C A)A (BC) = (A B)(A C)(BC) A = (B A)(C A)我们证明：A (BC) = (A B)(A C)( ? )( ? )( ? ) 要证明两个集合相等，通常有两种方法：一是证两个集合相互包含；二是利用已有的集合运算的性质(算律和已证明过的公式)，仿照代数恒等式的证明方法，一步步从左(右)边推出右(左)边，或从左、右边分别推出同一个集合式子。一般说来，最根本的集合相等关系要用第一种证法，比较复杂的集合相等关系用第二种方法更好，但第二种方法的使用取决于我们对算律和常用公式的熟练程度。证明：证明： 用第一种方法对于任意的 A (

4、 BC ) xA y(BC) xA (yB yC ) (xA yB) (xA yC) A B A C (A B)(A C) A (BC)=(A B)(A C)例例 设A=1,2，求P(A) A解：解： P(A) A= ，1，2，1,2 = ，n阶笛卡儿积：= (x1,x2, xn) | x1A1 x2A2 xnAnA1 A2 An1,2， ，二二元元关关系系：如如果果一一个个集集合合的的元元素素都都是是二二元元有有序序组组，那那么么这这个个集集合合称称为为一一个个二二元关系，记作：元关系，记作：R 。如果 R ，记作 x R y如果 R ，记作 x R y3、二元关系的数学定义、二元关系的数学

5、定义从从A到到B的二元关系：的二元关系：设设A，B为集合，为集合，A B的任的任何子集所定义的二元关系叫做从何子集所定义的二元关系叫做从A到到B的二元关系。的二元关系。假设A=B，叫做 A上的二元关系；假设|A|n，那么|AA|n2。就是说，A上有 个不同的二元关系，其中包括空关系、全域关系UA和恒等关系IA。A A的所有子集有 个。例例 设A = a,b，写出P(A)上的包含关系R ：解：解： P(A) = ,a,ba,bR = , , , , , 1. 关系矩阵：设A=x1, x2, , xn)，R是A上的关系，rij =1 若xi R xj0 若xi R xj(i, j = 1,2, n

6、)那么 (rij)nxn =是R的关系矩阵令：二、二元关系的表示方法2. 关系图：以E = | xiA xjA xiRxj为有向边集组成的有向图G = 以V=A=x1, x2, xn 为顶点集，例例 设A=1,2,3,4，R=,是A上的关系，试写出R的关系矩阵并画出关系图：解：解： 关系矩阵 ：0 0 1 10 0 0 00 1 0 01 1 0 0关系图 ：134 24.2 4.2 关系的运算关系的运算关系关系R的定义域：的定义域： domR = x | ( y) R (即即R中有序组的第中有序组的第一个元素构成的集合一个元素构成的集合)关关系系R的的值值域域： ranR =y | ( x)

7、 R (即即R中中有有序序组组的的第第二个元素构成的集合二个元素构成的集合)一、关系的定义域与值域例例 以下关系都是整数集以下关系都是整数集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

8、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)(xGz zFy)关系F在集A上的限制，记作：F | A= | xFy xA集A在关系F下的象FA = ran(F | A)(1) 逆：(2) 合成：(3) 限制：(4) 象：例例 设F，G是N上的关系，其定义为：F = | x, yN y = x2G

9、= | x,yN y = x+1求 G1，F G，G F，F |1,2，F1,2解：解：由定义知：G1 = | y, xN y = x+1列出G1 中的元素就是G1 = ,为了求F G，可以先直观表示如下：对任何xNx x+1=G即 y = (x+1)2因此 F G = | x,yN y = (x+1)2 同理可求 G F = | (?) (自己做！)发现 F G G FF |1,2 = ,F 1,2 = ran(F |1,2) = 1,4F Z Z2 = y关系运算的性质：设关系运算的性质：设F、G、H、为任意关系，那么有：、为任意关系，那么有：(1) (F1)1 = F(2) domF1

10、= 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)(G F(H F) F GF H F (GH) = F GF H(5

11、) F (GH) = F GF H的证明：4.3 4.3 关系的性质关系的性质R的关系矩阵：主对角线元素全是1R的关系图：每个顶点都有环自反性： x A 有R (R是A上的关系) 关系矩阵：主对角线元素全是0关系图： 每个顶点都没有环反自反性：x A R对称性：假设 R，那么 R 关系矩阵：对称阵关 系 图：如果两个顶点之间有边，一定是一对方向相反的边。反对称性：假设反对称性：假设 R且且x y，那么，那么 R 关系矩阵：如果rij = 1，且 i j，那么rji = 0 关系图： 如果两个顶点之间有边，一定是只有一条有向边。传递性：假设传递性：假设 R且且 R，那么，那么 R 关系图：如果顶

12、点xi到xj有边， xj到xk有边，那么从xi到xk有边例例 设A=1,2,10，对于A上的关系R= | (xy)/3II为整数集，问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 4.4 关系的闭包运算关系的闭包运算闭包：设RAA，自反闭包 记作 r

13、(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

14、) = 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其中“ + 均表示“ 逻辑加例例 设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 RR3 = R2 RR4 = R3 R= ,= ,= , , , 实际上，看到当k 4时，已有R4 RR2R3故

15、t(R) = RR2R3=, ,四、闭包运算的性质设A是有限集且|A| = n，RAA，那么： 4.6 4.6 等价关系和偏序关系等价关系和偏序关系等价关系：集A上的关系R是自反的, 对称的和传递的。等价类： R是集A上的等价关系，对于任一aA，aR=x | aRx, xA被称为a的等价类。即A中所有和a有R关系的元素的集合。一、等价关系及用途等价类的性质：等价类的性质：R是非空集合，对任意的x，yA，下面的结论成立：(1) x且x A (等价类为A的子集)(2) 假设xRy，那么x = y(3) 假设xRy，那么xy = 集A在等价关系R下的商集：设R为非空集A上的等价关系，以R的不交的等价

16、类为元素的集合叫做A在R下的商集，记作A/R.即：A/R = xR | x A集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上的等价关系与划分是一一对应的。例例 设A=1,2,3，求出A上所有的等价关系：解：解：先求A的各种划

17、分：只有1个划分块的划分1，具有两个划分块的划分2， 3，和4，具有3个划分块5。1 = A2 = 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, )为偏序集。为偏序集。二、偏序关系及用途例例 设A=2,4,6,8，A上关系R是通常意义下的小于或等于关系，试写出R并验证它是偏序关系。解：解：R=, , , , (1)自反性：(2

18、)反对称性：(3)传递性：, , , , ,均属于R对任意的R， 必有xy，当xy时， yx，从而R对任意的R， R,由于 xy yz ，所以xz，从而R。例例 设设C=a,b,a,b, ，C上关系上关系T是集是集合的合的“ 包含于，试写出包含于，试写出T，并验，并验证它是偏序关系。证它是偏序关系。解：解： 同例类似，自己做！(1) 用小圆圈表示偏序集的元素 (称为结点)；(2) 按每个元素在偏序中的次序从底向上列结点位置；(3) 对于偏序集中任意两个元素x和y，如果xy且不存在另一个元素a，使xaay，那么在x与y两结点之间划上一杠，即“ | (x在下，y在上)全序关系：设是偏序集，(x)(

19、y)(xA yA (xy yx)成立，那么称A,)为全序集，这时的偏序关系叫全序关系。全序集A,)中全部元素可以排序，它的哈斯图为一条直线。如果设是偏序集，B A(1) 如果如果 y B，使得，使得( x)(x By x)为真，为真，那么那么y是是B的最小元的最小元 (“ 小于小于 B中所有中所有元元 )(2) 如果如果 y B，使得，使得( x)(x B x y)为真，为真，那么那么y是是B的最大元的最大元 (“ 大于大于 B中所有中所有元元 )(4) 假设假设 y B，使得，使得 ( x)(x B x y)，那么，那么称称y是是B的极大元的极大元 (B中没有比中没有比y大的其他元大的其他元

20、)(5) 假设假设 y A，使得，使得( x)(x B x y)为真，为真，那么称那么称y是是B的上界的上界(3) 假设假设 y B，使得，使得 ( x)(x B x y)，那么，那么称称y是是B的极小元的极小元 (B中找不到中找不到x小于小于y )(6) 假设假设 y A，使得，使得( x)(x B y x)为真，为真，那么称那么称y是是B的下界的下界(7) 令令C=y | y为为B的上界的上界，那么称，那么称C的最小元的最小元为为B的上确界或最小上界的上确界或最小上界(8) 令令D =y | y为为B的下界的下界，那么，那么D的最大元为的最大元为B的下确界或最大下界的下确界或最大下界12

21、84610例例 画出和的哈斯图，并指出其中的特殊元。解：解： (1) 的哈斯图如下：92513711由图可知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,ca,b,ca,ca,bb,ccab由图可知： 为P(a,b,c)的最小元，a,b,c为它的最大元；同时，a,b,c也分别为它们的极小元和极大元、下确界和上确界。abcde例例 偏序集偏序集的哈斯图如下：的哈斯图如下：hgf 试写出对应的A和A上的偏序关系R

22、，并指出A中的特殊元。, , , , ,解：解： A = a,b,c,d,e,f, g,h 直接由哈斯图可知：A中没有最小元和最大元；e, g和h均为A的极大元，a, b, f 和h均为A的极小元；没有上确界和下确界。R = ,abcdehgf, ,了了了了解解解解二二二二元元元元关关关关系系系系的的的的定定定定义义义义和和和和表表表表示示示示方方方方法法法法；熟熟熟熟练练练练掌掌掌掌握握握握关关关关系系系系的的的的性性性性质质质质和和和和运运运运算算算算；特特特特别别别别是是是是复复复复合合合合和和和和三三三三种种种种闭闭闭闭包包包包运运运运算算算算; ;理理理理解解解解等等等等价价价价关关关关系系系系和和和和偏偏偏偏序序序序关关关关系系系系，明明明明确确确确它它它它们们们们在在在在描描描描述述述述研研研研究究究究对对对对象象象象的的的的结结结结构构构构和和和和特特特特点点点点时时时时重重重重要要要要作作作作用用用用 ( (即即即即分分分分类类类类和和和和覆覆覆覆盖盖盖盖) )。它它它它们们们们在在在在计计计计算算算算机机机机科科科科学学学学中中中中有有有有重重重重要应用。要应用。要应用。要应用。