离散数学集合的笛卡儿积与二元关系.ppt

1,第4章 二元关系与函数,4.1 集合的笛卡儿积与二元关系 4.2 关系的运算 4.3 关系的性质 4.4 关系的闭包 4.5 等价关系和偏序关系 4.6 函数的定义和性质 4.7 函数的复合和反函数,2,4.1 集合的笛卡儿积和二元关系,有序对 笛卡儿积及其性质 二元关系的定义 二元关系的表示,3,有序对,定义 由两个元素 x 和 y，按照一定的顺序组成的 二元组称为有序对，记作 实例：平面直角坐标系中点的坐标 有序对性质 1） 有序性 （当x y时） 2） 与 相等的充分必要条件是 = x=u y=v,例1 = ，求 x, y. 解 3y 4 = 2, x+5 = y y = 2, x = 3,4,有序 n 元组,定义 一个有序 n (n3) 元组 是一个 有序对，其中第一个元素是一个有序 n-1元组，即 = , xn 实例 ：空间直角坐标系中的坐标 n 维向量是有序 n元组. 当 n=1时, 形式上可以看成有序 1 元组.,5,笛卡儿积,定义 设A, B为集合，用A中元素为第一个元素，B中元素为第二个元素，构成有序对. 所有这样的有序对组成的集合叫做 A与B 的笛卡儿积 记作AB， 即 AB = | xA yB 例2 A=1,2,3, B=a,b,c AB =, , BA =, , , A=, P(A)A=, ,6,笛卡儿积的性质,不适合交换律 ABBA (AB, A, B) 不适合结合律 (AB)CA(BC) (A, B) 对于并或交运算满足分配律 A(BC)=(AB)(AC) (BC)A=(BA)(CA) A(BC)=(AB)(AC) (BC)A=(BA)(CA) 若A或B中有一个为空集，则AB就是空集. A=B= 若|A|=m, |B|=n, 则 |AB|=mn,7,性质的证明,证明 A(BC)=(AB)(AC) 证 任取 A(BC) xAyBC xA(yByC) (xAyB)(xAyC) ABAC (AB)(AC) 所以有A(BC) = (AB)(AC).,8,例题,解 (1) 任取 AC xA yC xB yD BD,例3 (1) 证明 A=B C=D AC=BD (2) AC=BD是否推出 A=B C=D ? 为什么？,(2) 不一定. 反例如下： A=1，B=2, C=D=, 则 AC=BD 但是 AB.,9,例4 (1) 证明 A B C D AC BD (2) AC BD是否推出 A B C D,解 (1) 任取 AC xA yC xB yD BD,(2) 不一定. 反例如下： A=1，B=2, C=D=,10,例5 设A、B、C、D为任意集合，判断以下等式是否成立， 说明为什么。 (AB)(C D)=(AC)(B D) (AB)(CD)=(AC)(B D) (A-B)(C-D)=(AC)-(BD) (AB)(CD)=(AC)(BD) 解： (1)成立，因为对任意的 (AB)(C D) xA B y C D xA x B y C y D AC BD,11,(2)(AB)(C D)=(AC)(B D) 解：不成立，若A=D= B=C= 1 则有： (AB)(C D)= B C= (3)(A-B)(C-D)=(AC)-(BD) 解：不成立， A=B=1 C=2 D=3 (A-B)(C-D)= (AC)-(BD) = = (4)(AB)(CD)=(AC)(BD) 解：A=1 B= C= D=1 (AB)(CD)=1,1 (AC)(BD)= ,12,设A1,A2, ,An是集合(n2),它们的n阶笛卡尔积记作A1A2 An,其中A1A2 An= x1A1, x2 A2 , ,xnAn. 当A1=A2 =An时，可将它们的n阶笛卡尔积记作An 例如：A=a,b,则 A3=,13,二元关系：集合中两个元素之间的某种关系 例1 甲、乙、丙3个人进行乒乓球比赛，任何两个人之间都要比赛一场。假设比赛结果是乙胜甲，甲胜丙，乙胜丙。 比赛结果可表示为： ， ， ，其中表示x胜y，它表示了集合甲,乙,丙中元素之间的一种胜负关系. 例2 有A、B、C3个人和四项工作G1、 G2、 G3、 G4，已知A可以从事工作G1和G4，B可以从事工作G3，C可以从事工作G1和G2. 那么，人和工作之间的对应关系可以记作 R , , , , C,G2 它表示了集合A,B,C到工作G1,G2,G3,G4之间的关系,14,二元关系的定义,定义 如果一个集合满足以下条件之一： （1）集合非空, 且它的元素都是有序对 （2）集合是空集 则称该集合为一个二元关系, 简称为关系，记作R. 如R, 可记作 xRy；如果R, 则记作x y 实例：R=, S=,a,b. R是二元关系, 当a, b不是有序对时，S不是二元关系 根据上面的记法，可以写 1R2, aRb, a c 等.,15,从A到B的关系与A上的关系,定义 设A,B为集合, AB的任何子集所定义的二元 关系叫做从A到B的二元关系, 当A=B时则叫做 A上 的二元关系. 例4 A=0,1, B=1,2,3, R1=, R2=AB, R3=, R4=. 那么 R1, R2, R3, R4是从 A 到 B 的二元关系, R3和R4同时也是 A上的二元关系. 计数 |A|=n, |AA|=n2, AA的子集有 个. 所以 A上有 个不同的二元关系. 例如 |A|=3, 则 A上有=512个不同的二元关系.,16,A上重要关系的实例,设 A 为任意集合， 是 A 上的关系，称为空关系 EA, IA 分别称为全域关系与恒等关系，定义如下： EA=|xAyA=AA IA=|xA 例如, A=1,2, 则 EA=, IA=,17,A上重要关系的实例（续）,小于等于关系 LA, 整除关系DA, 包含关系R定义： LA=| x,yAxy, AR，R为实数集合 DB=| x,yBx整除y, BZ+, Z+为非0整数集 R=| x,yAxy, A是集合族. 类似的还可以定义大于等于关系, 小于关系, 大于关系, 真包含关系等等.,18,实例,例如 A = 1, 2, 3, B =a, b, 则 LA=, DA=,A=P(B)=,a,b,a,b, 则 A上的包含关系是 R=, ,19,关系的表示,表示方式：关系的集合表达式、关系矩阵、关系图 关系矩阵：若A=x1, x2, , xm，B=y1, y2, , yn，R是从A到B的关系，R的关系矩阵是布尔矩阵MR = rij mn, 其中 rij = 1 R. 关系图：若A= x1, x2, , xm，R是从A上的关系，R的关系图是GR=, 其中A为结点集，R为边集.如果属于关系R，在图中就有一条从 xi 到 xj 的有向边. 注意：A, B为有穷集，关系矩阵适于表示从A到B的关系或者A上的关系，关系图适于表示A上的关系,20,实例,A=1,2,3,4, R=, R的关系矩阵MR和关系图GR如下：,21,基本运算定义 定义域、值域、域 逆、合成、限制、像 基本运算的性质 幂运算 定义 求法 性质,4.2 关系的运算,22,关系的基本运算定义,定义域、值域 和 域 domR = x | y (R) ranR = y | x (R) fldR = domR ranR 例1 R=, 则 domR=1, 2, 4 ranR=2, 3, 4 fldR=1, 2, 3, 4,23,关系的基本运算定义（续）,定义 设F、G为任意的关系，A为集合，则 逆与合成 F1 = | F FG = | | z ( G F) 例2 R=, , , S=, , , , R1=, , , SR =, , RS =, , , ,24,合成运算的图示方法,利用图示（不是关系图）方法求合成 RS=, , , SR =, , ,RS,SR,25,限制与像,定义 F 在A上的限制 FA = | xFy xA A 在F下的像 FA = ran(FA) 实例 R=, , , R1=, R1=2,4 R= R1,2=2,3,4 注意：FAF, FA ranF,26,例.设F、G是N上的关系，其定义为 F=x,y N y=x2 G =x,y N y=x+1 求G1、FG 、 GF、 F1,2、F1,2 解：G1= y,xN y=x+1 G1=, , 对任何xN有 y=z2=(x+1)2，所以 FG= x,y N y =(x+1)2 GF= x,y N y =x2+1 F1,2=, F 1,2=ran(F1,2)=1,4,27,例.设F=,求FF、 Fa、Fa 解：FF= Fa= A= a FA = ran(FA)=ran=a,28,关系基本运算的性质,定理4.1 设F是任意的关系, 则 (1) (F1)1=F (2) domF1=ranF, ranF1=domF 证 (1) 任取, 由逆的定义有 (F 1)1 F1 F 所以有 (F1)1=F (2) 任取x, xdomF1 y(F1) y(F) xranF 所以有domF1= ranF. 同理可证 ranF1 = domF.,29,(3) (FG)H=F(GH) (4) (FG)1= G1F1 证 (3) 任取, (FG)H t( H FG) t ( H s (G) F) ) t s ( H G F) s (Ft (HG) s (FGH) F(GH) 所以 (FG)H = F(GH),关系基本运算的性质（续）,30,(4) 任取, (FG)1 FG t ( G (t,x) F) t ( F1 (t,y) G1) G1F1 所以 (FG)1 = G1F1,关系基本运算的性质（续）,31,关系基本运算的性质（续）,定理4.2 设F 、G、 H为任意的二元关系，则有： F (G H ) =F G FH (G H ) F = G F HF (合成运算对运算满足分配律） 3. F (G H ) F G FH 4. (G H ) F G F HF (合成运算对 运算分配后是包含关系）,32,A上关系的幂运算,设R为A上的关系, n为自然数, 则 R 的 n次幂定义为： (1) R0= | xA =IA (2) Rn =Rn-1R, n1 注意： 对于A上的任何关系R1和R2都有 R10 = R20 = IA 对于A上的任何关系 R 都有 R1 = R,33,幂的求法,(1) 对于集合表示的关系R，计算 Rn 就是n个R左复合 . (2) 矩阵表示就是n个矩阵相乘, 其中相加采用逻辑加. 例3 设A=a,b,c,d, R=, 求R的各次幂, 分别用矩阵和关系图表示. 解 R与R2的关系矩阵分别为,34,同理，R0=IA, R3和R4的矩阵分别是： 因此M4=M2, 即R4=R2. 因此可以得到 R2=R4=R6=, R3=R5=R7= 对于有穷集A，A上关系R的不同幂只有有限个。,幂的求法（续）,35,R0, R1, R2, R3,的关系图如下图所示,幂的求法（续）,36,幂运算的性质,定理3 设A为n元集, R是A上的关系, 则存在自然数 s 和 t, 使得 Rs = Rt. 证 R为A上的关系, 由于|A|=n, A上的不同关系只有 个. 当列出 R 的各次幂 R0, R1, R2, , , , 必存在自然数 s 和 t 使得 Rs=Rt.,37,定理4 设 R 是 A 上的关系, m, nN, 则 (1) RmRn=Rm+n (2) (Rm)n=Rmn 证 用归纳法 (1) 对于任意给定的mN, 施归纳于n. 若n=0