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

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

2、：A B = | xA y B精选ppt5例例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, , , , , 精选ppt6(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, 。精选ppt7(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)( ? )( ? )( ? )精选ppt8 要证明两个集合相等，通常有两种方法：一是证两个集合相互包含；二是利用已有的集合运算的性质(算律和已证明过的公式)，仿照代数恒等式的证明方法，一步步从左(右)边推出右(左)边，或从左、右边分别推出同一个集合式子。一般说来，最基本的集合相等关系要用第一种证法，比较复杂的集合相等关系用第二种方法更好，但第二种方法的使用取决于我们对算律和常用公式的熟练程度。精选ppt9证明：证明： 用第一种

4、方法对于任意的 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)精选ppt10例例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， ，精选ppt11二元关系：二元关系：如果一个集合的元素都是二元有如果一个集合的元素都是二元有序组，则这个集合称为一个二元序组，则这个集合称为一个二元关系，记作：关系，记作：R 。如果 R ，记作 x R y如果 R

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

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

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

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

9、 xA集A在关系F下的象FA = ran(F | A)(1) 逆：(2) 合成：(3) 限制：(4) 象：精选ppt22例例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 = ,精选ppt23为了求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

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

11、 F1) G1 F1(4) (F G)1 = G1 F1的证明：精选ppt26任取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的证明：精选ppt27R的关系矩阵：主对角线元素全是1R的关系图：每个顶点都有环自反性： x A 有R (R是A上的关系) 关系矩阵：主对角线元素全是0关系图： 每个顶点都没有环反自反性：x A R精选ppt28对称性：若 R，则 R 关系矩阵：对称阵关 系 图：如果两个顶点之间有边，一定是一对方向相反的边。精选ppt29反对称性

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

13、而R是对称的对称的；如果A中三 个元素x，y，z满足xRy， yRz，则x y，yz被3整除，由于xz=(xy)+(yz)，所以xz被3整除，从而xRz即R具有传递性传递性。 精选ppt33闭包：设RAA，自反闭包 记作 r(R)对称闭包 记作 s(R)传递闭包 记作 t(R)由A求r(R)，s(R)，t(R)的过程叫闭包运算。那么，包含R而使之具有自反性质的最小关系，称之为R的自反闭包自反闭包；包含R而使之具有对称性质(传递性质)的最小关系，称之为R的对称(传递传递)闭包闭包。一、定义精选ppt34幂运算：设RAA，kN，约定(1) R0 = IA = | xA(2) R1 = R(3) R

14、k+1 = Rk R显然 Rm Rn = Rm+n (Rm)n = Rmn二、计算方法为了有效地计算关系R的各种闭包，先引进关系的幂运算概念。精选ppt35闭包运算的方法：闭包运算的方法：设R是A上的任一关系，则(1) r (R) = RIA(2) s (R) = RR(3) t (R) = RR2R3 Rn精选ppt36矩阵形式矩阵形式：(M为R的关系矩阵)(1) Mr = M + E(2) Ms = M + M (M 是M的转置)(3) Mt = M+M2+M3其中“ +” 均表示“ 逻辑加”精选ppt37例例4.8 设A=a,b,c,d，A上的关系求 r (R)，s (R) 和 t (R

15、)解：解： r(R) = RIA=, , , , , , R=, = R,三、实例精选ppt38s(R) = RR=,t(R) = RR2R3= R,精选ppt39而R2 = R RR3 = R2 RR4 = R3 R= ,= ,= , , , 实际上，看到当k 4时，已有R4 RR2R3故 t(R) = RR2R3=, ,精选ppt40四、闭包运算的性质设A是有限集且|A| = n，R A A，则：ikiRRtnk1)()1(，使有)()()2(RsrRrs)()()3(RtrRrt)( )()4(RtsRst 精选ppt41等价关系：集A上的关系R是自反的, 对称的和传递的。等价类： R是

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

17、为A则 为A的划分。如果存在一个A的子集族， P(A)满足以下条件：精选ppt45 由等价类的性质和商集的定义可知，商集A/R是A的划分，称之为由R诱导的划分。反过来，给定A的任一划分 ，则A被分割成若干个划分块。 若定义A上的二元关系R：x，yA且x,y属 的同一块，则xRy，那么R是A上的等价关系，称之为由 诱导的等价关系。集A上的等价关系与划分是一一对应的。精选ppt46例例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,3精选ppt47设对应于划分i 的等价关系 Ri，i = 1,2,5，则有R5 = ，R1 = ，R2 = ，R3 = ，R4 = ，精选ppt48偏序关系：偏序关系：集集A上的关系上的关系R是自反的，反对是自反的，反对称的和传递的，记作称的和传递的，记作“ ”，且，且称称A, )为偏序集。为偏序集。二、偏序关系及用途精选ppt49例例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。精选ppt50例例4.11 设C=a,b,a,b,，C上关系T是集合的“ 包含于”，试写出T，并验证它是偏序关系。解：解： 同例4.10类似，自己做！精选ppt51(1) 用小圆圈表示偏序集的元素 (称为结点)；(2) 按每个元素在偏序中的次序从底向上列结点位置；(3) 对于偏序集中任意两个元素x和y，如果xy且不存在另一个元素a，使xa ay，则在x与y两结点之间划上一杠，即“ | ” (x在下，y在上)精选ppt52全序关系：设是偏序集，(x)(y)(xA yA (xy yx)成立，则称A,)为全序集，这时的偏序关系叫全序关系。全序集A,)中全部元素可以排序，它的哈斯图为一条直线。如果精选ppt53设是偏序集，B A(1) 如果yB，使得(x)(xByx)为真，则y是B的最小元 (“ 小于” B中所有元 )(2) 如果yB，使得(x)(xB xy)为真，则y是B的最大元 (“ 大于” B中所有元 )精选ppt54(4) 若yB，使得 (x)(xB xy)，则称y是B的极大元 (B中没有比y大的其他元)(5) 若yA，使得(x)(xB xy)为真，则称y是B的上界(3) 若yB，使得 (x)