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

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

1、1精选ppt1. . 二元有序二元有序二元有序二元有序组组：由两个元素：由两个元素x和和y按一定按一定顺顺序序排成二元排成二元组组，记记作：作： 。4.1 4.1 二元关系的概念二元关系的概念如： 平面直角坐标系中点的坐标一、二元关系的概念2精选ppt(1) 当x y时， (2) = ，当且仅当x = u，y = v(1)、(2)说明有序组区别于集合n元有序组：由由n个元素个元素x1，x2，xn，按按一定一定顺顺序排成的序排成的n元元组组，记记作：作：(x1，x2，xn) 。3精选ppt2. 一种新的集合运算一种新的集合运算 积运算运算 ： 设A、B为两集合，用A中元素为第一元素，B中元素作为

2、第二元素构成的二元有序组的全体叫做A和B的笛卡儿积。记作：A B符号化：A B = | xA y B4精选ppt例例4.1 设A=a,b，B=0,1,2 ，求A B，B A解：解：根据笛卡儿积的定义知A B = , , , B A = , , 一般地：如果|A|=m，|B|=n，则 |A B|=|B A|=m n, , , , , 5精选ppt(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,

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

4、决于我们对算律和常用公式的熟练程度。8精选ppt证明：明： 用第一种方法对于任意的 A ( 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)9精选ppt例例4.2 设A=1,2，求P(A) A解：解： P(A) A= ，1，2，1,2 = ，n阶笛卡儿积：= (x1,x2, xn) | x1A1 x2A2 xnAnA1 A2 An1,2， ，10精选ppt二二元元关关系系：如如果果一一个个集集合合的的元元素素都都是是二二元元有有序序组，则这个个集集合合称称为一一个个二二元元关系，关系，记

5、作：作：R 。如果 R ，记作 x R y如果 R ，记作 x R y3、二元关系的数学定、二元关系的数学定义11精选ppt从从A到到B的二元关系：的二元关系：设A，B为为集合，集合，A B的任的任何子集所定何子集所定义义的二元关系叫做从的二元关系叫做从A到到B的二元关系。的二元关系。若A=B，叫做 A上的二元关系；若|A|n，则|A A|n2。就是说，A上有 个不同的二元关系，其中包括空关系、全域关系UA和恒等关系IA。A A的所有子集有 个。12精选ppt例例4.3 设A = a,b，写出P(A)上的包含关系R ：解：解： P(A) = ,a,ba,bR = , , , , , 13精选p

6、pt1. 关系矩阵：设A=x1, x2, , xn)，R是A上的关系，rij =1 若xi R xj0 若xi R xj(i, j = 1,2, n)则 (rij)nxn =是R的关系矩阵令：二、二元关系的表示方法14精选ppt2. 关系图：以E = | xiA xjA xiRxj为有向边集组成的有向图G = 以V=A=x1, x2, xn 为顶点集，15精选ppt例例4.4 设A=1,2,3,4，R=,是A上的关系，试写出R的关系矩阵并画出关系图：解：解： 关系矩阵 ：0 0 1 10 0 0 00 1 0 01 1 0 0关系图 ：134 216精选ppt4.2 4.2 关系的运算关系的运

7、算关系关系R的定的定义义域：域： domR = x | ( y) R (即即R中有序中有序组组的第的第一个元素构成的集合一个元素构成的集合)关关系系R的的值值域域： ranR =y | ( x) R (即即R中中有有序序组组的的第第二二个个元元素构成的集合素构成的集合)一、关系的定义域与值域17精选ppt例例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 18精选ppt解：解： domR1

8、= ranR1 = Z解：解： R2 = , , domR2 = ( ? )ranR2 = ( ? )(1) R1= | x, y Z xy (2) R2= | x, y Z x2+y2=1 , 19精选ppt解：解： domR3 = Z， ranR3 = 偶数 解：解： domR4 = ranR4 = ( ? )(3) R3= | x, y Z y=2x (4) R4= | x, y Z |x|=|y|=3 20精选ppt二、关系的常用运算F是任意关系，F的逆F1= | yFx F、G是任意两个关系，F与G的合成记作：F G= | (z)(xGz zFy)关系F在集A上的限制，记作：F |

9、A= | xFy xA集A在关系F下的象FA = ran(F | A)(1) 逆：(2) 合成：(3) 限制：(4) 象：21精选ppt例例4.6 设F，G是N上的关系，其定义为：F = | x, yN y = x2G = | x,yN y = x+1求 G1，F G，G F，F |1,2，F1,2解：解：由定义知：G1 = | y, xN y = x+1列出G1 中的元素就是G1 = ,22精选ppt为了求F G，可以先直观表示如下：对任何xNx x+1=G即 y = (x+1)2因此 F G = | x,yN y = (x+1)2 同理可求 G F = | (?) (自己做！)发现 F G

10、 G FF |1,2 = ,F 1,2 = ran(F |1,2) = 1,4F Z Z2 = y23精选ppt关系运算的性关系运算的性质：设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( ? )( ? )24精选ppt任取 (F G)1 F G (z)( G F) (z)

11、( G1 F1) G1 F1(4) (F G)1 = G1 F1的证明：25精选ppt任取F (GH) (z)(GH)F) (z)(GH) F) (注意对括号的顺序) (z)(G F(H F) F GF H F (GH) = F GF H(5) F (GH) = F GF H的证明：26精选ppt4.3 4.3 关系的性关系的性质R的关系矩阵：主对角线元素全是1R的关系图：每个顶点都有环自反性： x A 有R (R是A上的关系) 关系矩阵：主对角线元素全是0关系图： 每个顶点都没有环反自反性：x A R27精选ppt对称性：若 R，则 R 关系矩阵：对称阵关 系 图：如果两个顶点之间有边，一定

12、是一对方向相反的边。28精选ppt反反对称性：称性：若 R且xy，则 R 关系矩阵：如果rij = 1，且 i j，则rji = 0 关系图： 如果两个顶点之间有边，一定是只有一条有向边。29精选ppt传递性：性：若 R且 R，则 R 关系图：如果顶点xi到xj有边， xj到xk有边，则从xi到xk有边30精选ppt例例4.7 设A=1,2,10，对于A上的关系R= | (xy)/3II为整数集，问R有哪些性质？31精选ppt解：解：逐条性质加以验证R= | (xy)/3I 任取A中元素x，由于(xx)/3=0，所以R是自反的自反的； 又设A中任意两个元素x,y，如果 xRy，即xy可被3整除

13、，则yx也一定可被3整除，即yRx，从而R是对对称的称的； 如果A中三 个元素x，y，z满足xRy， yRz，则x y，yz被3整除，由于xz=(xy)+(yz)，所以xz被3整除，从而xRz即R具有传递传递性性。 32精选ppt4.4 4.4 关系的关系的闭包运算包运算闭包：设RAA，自反闭包 记作 r(R)对称闭包 记作 s(R)传递闭包 记作 t(R)由A求r(R)，s(R)，t(R)的过程叫闭包运算。那么，包含R而使之具有自反性质的最小关系，称之为R的自反自反闭闭包包；包含R而使之具有对称性质(传递性质)的最小关系，称之为R的对称(传递传递)闭闭包包。一、定义33精选ppt幂运算：设R

14、AA，kN，约定(1) R0 = IA = | xA(2) R1 = R(3) Rk+1 = Rk R显然 Rm Rn = Rm+n (Rm)n = Rmn二、计算方法为了有效地计算关系R的各种闭包，先引进关系的幂运算概念。34精选ppt闭包运算的方法：包运算的方法：设R是A上的任一关系，则(1) r (R) = RIA(2) s (R) = RR(3) t (R) = RR2R3 Rn35精选ppt矩矩阵阵形式形式：(M为R的关系矩阵)(1) Mr = M + E(2) Ms = M + M (M 是M的转置)(3) Mt = M+M2+M3其中“ +” 均表示“ 逻辑加”36精选ppt例例

15、4.8 设A=a,b,c,d，A上的关系求 r (R)，s (R) 和 t (R)解：解： r(R) = RIA=, , , , , , R=, = R,三、实例37精选ppts(R) = RR=,t(R) = RR2R3= R,38精选ppt而R2 = R RR3 = R2 RR4 = R3 R= ,= ,= , , , 实际上，看到当k 4时，已有R4 RR2R3故 t(R) = RR2R3=, ,39精选ppt四、闭包运算的性质设A是有限集且|A| = n，R A A，则： 40精选ppt4.6 4.6 等价关系和偏序关系等价关系和偏序关系等价关系：集A上的关系R是自反的, 对称的和传递

16、的。等价类： R是集A上的等价关系，对于任一aA，aR=x | aRx, xA被称为a的等价类。即A中所有和a有R关系的元素的集合。一、等价关系及用途41精选ppt等价等价类的性的性质：R是非空集合，对任意的x，yA，下面的结论成立：(1) x且x A (等价类为A的子集)(2) 若xRy，则x = y(3) 若xRy，则xy = 42精选ppt集A在等价关系R下的商集：设R为非空集A上的等价关系，以R的不交的等价类为元素的集合叫做A在R下的商集，记作A/R.即：A/R = xR | x A43精选ppt集A的划分：设A是非空集合，(1) (2) 中任意两个元素不交 (3) 中所有元素的并集为

17、A则 为A的划分。如果存在一个A的子集族， P(A)满足以下条件：44精选ppt 由等价类的性质和商集的定义可知，商集A/R是A的划分，称之为由R诱导的划分。 反过来，给定A的任一划分 ，则A被分割成若干个划分块。 若定义A上的二元关系R：x，yA且x,y属 的同一块，则xRy，那么R是A上的等价关系，称之为由 诱导的等价关系。集A上的等价关系与划分是一一对应的。45精选ppt例例4.9 设A=1,2,3，求出A上所有的等价关系：解：解：先求A的各种划分：只有1个划分块的划分1，具有两个划分块的划分2， 3，和4，具有3个划分块5。1 = A2 = 1,2,3，4 = 3,1,2，3 = 2,

18、1,3，5 = 1,2,346精选ppt设对应于划分i 的等价关系 Ri，i = 1,2,5，则有R5 = ，R1 = ，R2 = ，R3 = ，R4 = ，47精选ppt偏序关系：偏序关系：集集A上的关系上的关系R是自反的，反是自反的，反对对称的和称的和传递传递的，的，记记作作“ ”，且，且称称A, )为为偏序集。偏序集。二、偏序关系及用途48精选ppt例例4.10 设A=2,4,6,8，A上关系R是通常意义下的小于或等于关系，试写出R并验证它是偏序关系。解：解：R=, , , , (1)自反性：(2)反对称性：(3)传递性：, , , , ,均属于R对任意的R， 必有xy，当xy时， yx

19、，从而R对任意的R， R,由于 xy yz ，所以xz，从而R。49精选ppt例例4.11 设C=a,b,a,b,，C上关系T是集合的“ 包含于”，试写出T，并验证它是偏序关系。解：解： 同例4.10类似，自己做！50精选ppt(1) 用小圆圈表示偏序集的元素 (称为结点)；(2) 按每个元素在偏序中的次序从底向上列结点位置；(3) 对于偏序集中任意两个元素x和y，如果xy且不存在另一个元素a，使xa ay，则在x与y两结点之间划上一杠，即“ | ” (x在下，y在上)51精选ppt全序关系：设是偏序集，(x)(y)(xA yA (xy yx)成立，则称A,)为全序集，这时的偏序关系叫全序关系

20、。全序集A,)中全部元素可以排序，它的哈斯图为一条直线。如果52精选ppt设是偏序集，B A(1) 如果yB，使得(x)(xByx)为真，则y是B的最小元 (“ 小于” B中所有元 )(2) 如果yB，使得(x)(xB xy)为真，则y是B的最大元 (“ 大于” B中所有元 )53精选ppt(4) 若yB，使得 (x)(xB xy)，则称y是B的极大元 (B中没有比y大的其他元)(5) 若yA，使得(x)(xB xy)为真，则称y是B的上界(3) 若yB，使得 (x)(xB xy)，则称y是B的极小元 (B中找不到x小于y )54精选ppt(6) 若yA，使得(x)(xB yx)为真，则称y是

21、B的下界(7) 令C=y | y为B的上界，则称C的最小元为B的上确界或最小上界(8) 令D =y | y为B的下界，则D的最大元为B的下确界或最大下界55精选ppt12 84610例例4.12 画出和的哈斯图，并指出其中的特殊元。解：解： (1) 的哈斯图如下：92513711由图可知1为最小元，没有最大元；7,8,9,10,11, 12均为极大元，极小元为1；1为1,2,12的下界，也是下确界；1,2,12中没有上确界或上界。56精选ppt(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)

22、的最小元，a,b,c为它的最大元；同时，a,b,c也分别为它们的极小元和极大元、下确界和上确界。57精选pptabcde例例4.13 已知偏序集的哈斯图如下：hgf 试写出对应的A和A上的偏序关系R ，并指出A中的特殊元。58精选ppt, , , , ,解：解： A = a,b,c,d,e,f, g,h 直接由哈斯图可知：A中没有最小元和最大元；e, g和h均为A的极大元，a, b, f 和h均为A的极小元；没有上确界和下确界。R = ,abcdehgf, ,59精选ppt了了了了解解解解二二二二元元元元关关关关系系系系的的的的定定定定义义和和和和表表表表示示示示方方方方法法法法；熟熟熟熟练练

23、掌掌掌掌握握握握关关关关系系系系的的的的性性性性质质和和和和运运运运算算算算；特特特特别别是是是是复复复复合合合合和和和和三三三三种种种种闭闭包包包包运运运运算算算算; ;理理理理解解解解等等等等价价价价关关关关系系系系和和和和偏偏偏偏序序序序关关关关系系系系，明明明明确确确确它它它它们们在在在在描描描描述述述述研研研研究究究究对对象象象象的的的的结结构构构构和和和和特特特特点点点点时时重重重重要要要要作作作作用用用用 ( (即即即即分分分分类类和和和和覆覆覆覆盖盖盖盖) )。它它它它们们在在在在计计算算算算机机机机科科科科学学学学中中中中有有有有重重重重要要要要应应用。用。用。用。60精选ppt此课件下载可自行编辑修改，供参考！感谢您的支持，我们努力做得更好！61精选ppt