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

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

1、1：由两个元素由两个元素x和和y按一定顺序按一定顺序排成二元组，记作：排成二元组，记作： 。如： 平面直角坐标系中点的坐标一、二元关系的概念(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=

2、a,b，B=0,1,2 ，求A B，B A解：解：根据笛卡儿积的定义知A B = , , , B A = , , 一般地：如果|A|=m，|B|=n，则 |A B|=|B A|=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) ( 对的分配律)(BC) A = (B A)(C A)A (BC) = (A B)(A C)

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

4、A B A C (A B)(A C) A (BC)=(A B)(A C)例例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， ，二元关系：二元关系：如果一个集合的元素都是二元有如果一个集合的元素都是二元有序组，则这个集合称为一个二元序组，则这个集合称为一个二元关系，记作：关系，记作：R 。如果 R ，记作 x R y如果 R ，记作 x R y3、二元关系的数学定义、二元关系的数学定义从从A到到B的二元关系：的二元关系：设设A，B为集合，为集合，A B的任的任

5、何子集所定义的二元关系叫做从何子集所定义的二元关系叫做从A到到B的二元关系。的二元关系。若A=B，叫做 A上的二元关系；若|A|n，则|A A|n2。2n2就是说，A上有 个不同的二元关系，其中包括空关系、全域关系UA和恒等关系IA。2n2A A的所有子集有 个。例例4.3 设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)则 (rij)nxn =是R的关系矩阵令：nnnnnnrrrrr

6、rrrr212222111211二、二元关系的表示方法2. 关系图：以E = | xiA xjA xiRxj为有向边集组成的有向图G = 以V=A=x1, x2, xn 为顶点集，例例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关系关系R的定义域：的定义域： domR = x | ( y) R (即即R中有序组的第一个元中有序组的第一个元素构成的集合素构成的集合)关系关系R的值域：的值域： ranR =y | ( x) R (即即R中有序组的第二个元中有序组的

7、第二个元素构成的集合素构成的集合)一、关系的定义域与值域例例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 = 偶数 解：解： do

8、mR4 = 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) 象：例例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解：解

9、：由定义知：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 = ranF，ranF1 = domF(3) (F G) H = F (G H)(4) (F G)1 = G1

10、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) F (GH) = F GF H的证明：R的关系矩阵：主对角线元素全是1R的关系图：每个顶点都有环自反性： x