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

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,b，B=0,1,2

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)(C A,我们证明,A(BC) = (AB)(AC,证明思想,要证明两个

3、集合相等，通常有两种方法：一是证两个集合相互包含,二是利用已有的集合运算的性质(算律和已证明过的公式)，仿照代数恒等式的证明方法，一步步从左(右)边推出右(左)边，或从左、右边分别推出同一个集合式子,一般说来，最基本的集合相等关系要用第一种证法，比较复杂的集合相等关系用第二种方法更好，但第二种方法的使用取决于我们对算律和常用公式的熟练程度,证明： 用第一种方法,对于任意的 A ( BC,xAy(BC,xA(yByC,(xAyB)(xAyC,ABAC,(AB)(AC,A(BC)=(AB)(AC,例4.2 设A=1,2，求P(A)A,解： P(A)A,，1，2，1,2,n阶笛卡儿积,(x1,x2,

4、 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上有 个不同的二元关系，其中包括空关系、全域关系UA和恒等关系IA,AA的所有子集有 个,例4.3 设A = a,b，写出P(A)上的包含关系R,解： P(A) = ,a,ba,b,R = , ,A上关系的表示法,1. 关系矩阵,设A

5、=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 0 0,关系图,4.2 关系的运算,关系R的定义域： domR = x | (y)R (即R中有序组的第一个元素构成的集合,关系R的值域： ranR =y | (x)R (即R中有序组的第二个元素构成的集合,一、关系的定义域与

6、值域,例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 = 偶数,解： domR4 = ranR4 = ( ,3) R3= | x, y Z y=2x,4) R4= | x

7、, 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) 限制,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，可以先直观表示如

8、下,对任何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) (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

9、 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)(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,关系矩阵：对称阵,关 系 图：如果两个顶点之间有边，

10、一定是一对方向相反的边,反对称性：若 R且xy，则 R,关系矩阵：如果rij = 1，且 i j，则rji = 0,关系图： 如果两个顶点之间有边，一定是只有一条有向边,传递性：若 R且 R，则 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，

11、y，z满足xRy， yRz，则x y，yz被3整除，由于xz=(xy)+(yz)，所以xz被3整除，从而xRz即R具有传递性,4.4 关系的闭包运算,闭包：设RAA,自反闭包 记作 r(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 =

12、 Rmn,二、计算方法,为了有效地计算关系R的各种闭包，先引进关系的幂运算概念,闭包运算的方法：设R是A上的任一关系，则,1) r (R) = 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,其中“ +” 均表示“ 逻辑加,例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

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

14、下的商集：设R为非空集A上的等价关系，以R的不交的等价类为元素的集合叫做A在R下的商集，记作A/R,即,A/R = xR | xA,集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上的等价关系与划分是一一对应的,例4.9 设A=1,2,3，求出A上

15、所有的等价关系,解：先求A的各种划分：只有1个划分块的划分1，具有两个划分块的划分2， 3，和4，具有3个划分块5,1 = A,2 = 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, )为偏序集,二、偏序关系及用途,例4.10 设A=2,4,6,8，A上关系R是通常意义下的小于或等于关系，试写出R并验证它是偏序关系,解：R=, , ,1)自反性,2)反对称性,3)传递性,均属于R,对任意的

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

17、部元素可以排序，它的哈斯图为一条直线,如果,偏序集中的一些特殊元素,设是偏序集，BA,1) 如果yB，使得(x)(xByx)为真，则y是B的最小元 (“ 小于” B中所有元,2) 如果yB，使得(x)(xB xy)为真，则y是B的最大元 (“ 大于” B中所有元,4) 若yB，使得 (x)(xBxy)，则称y是B的极大元 (B中没有比y大的其他元,5) 若yA，使得(x)(xB xy)为真，则称y是B的上界,3) 若yB，使得 (x)(xBxy)，则称y是B的极小元 (B中找不到x小于y,6) 若yA，使得(x)(xB yx)为真，则称y是B的下界,7) 令C=y | y为B的上界，则称C的最小元为B的上确界或最小上界,8) 令D =y | y为B的下界，则D的最大元为B的下确界或最大下界,例4.12 画出和的哈斯图，并指出其中的特殊元,解： (1) 的哈斯图如下,由图可知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,c,由图可知： 为P(a,b,c)的最小元，a,b,c为它的最大元,同时，a,b,c也分别为它们的极小元和极大元、下确界和上