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