《离散数学,二元关系与运算》由会员分享，可在线阅读，更多相关《离散数学,二元关系与运算（60页珍藏版）》请在金锄头文库上搜索。
1、二元关系和运算,第四章,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
2、,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)
3、(C A),我们证明：,A(BC) = (AB)(AC),( ? ),( ? ),( ? ),证明思想,要证明两个集合相等，通常有两种方法：一是证两个集合相互包含；,二是利用已有的集合运算的性质(算律和已证明过的公式)，仿照代数恒等式的证明方法，一步步从左(右)边推出右(左)边，或从左、右边分别推出同一个集合式子。,一般说来，最基本的集合相等关系要用第一种证法，比较复杂的集合相等关系用第二种方法更好，但第二种方法的使用取决于我们对算律和常用公式的熟练程度。,证明： 用第一种方法,对于任意的 A ( BC ), xAy(BC), xA(yByC ), (xAyB)(xAyC), ABAC, (A
4、B)(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上有 个不同的二元关系，其中包括空关系、全域关
5、系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
6、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
7、 = ( ? ),(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) 限制：
8、,(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)
9、(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) (注意对括号的顺序),
10、(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，则
11、 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
12、(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
13、 (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的不交的等价类为元素的集
