二元关系与函数

1、二元关系与函数第1页，共33页，2022年，5月20日，8点2分，星期日14.1 集合的笛卡儿积和二元关系 有序对 笛卡儿积及其性质 二元关系的定义 二元关系的表示第2页，共33页，2022年，5月20日，8点2分，星期日2有序对定义 由两个元素 x 和 y，按照一定的顺序组成的 二元组称为有序对，记作实例：平面直角坐标系中点的坐标有序对性质 1） 有序性 （当x y时） 2） 与 相等的充分必要条件是 = x=u y=v例1 = ，求 x, y. 解 3y 4 = 2, x+5 = y y = 2, x = 3 第3页，共33页，2022年，5月20日，8点2分，星期日3有序 n 元组定义

2、一个有序 n (n3) 元组 是一个有序对，其中第一个元素是一个有序 n-1元组，即 = , xn 实例 ：空间直角坐标系中的坐标 n 维向量是有序 n元组.当 n=1时, 形式上可以看成有序 1 元组. 第4页，共33页，2022年，5月20日，8点2分，星期日4笛卡儿积定义 设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=, 第5页，共33页，2022年，5月20日，8点2

3、分，星期日5笛卡儿积的性质不适合交换律 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 第6页，共33页，2022年，5月20日，8点2分，星期日6性质的证明证明 A(BC)=(AB)(AC)证 任取 A(BC) xAyBC xA(yByC) (xAyB)(xAyC) ABAC (AB)(AC)所以有A(BC) = (A

4、B)(AC).第7页，共33页，2022年，5月20日，8点2分，星期日7例题 解 (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.第8页，共33页，2022年，5月20日，8点2分，星期日8例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=第9页，共3

5、3页，2022年，5月20日，8点2分，星期日9二元关系：集合中两个元素之间的某种关系例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之间的关系第10页，共33页，2022年，5月20日，8

6、点2分，星期日10二元关系的定义定义 如果一个集合满足以下条件之一：（1）集合非空, 且它的元素都是有序对（2）集合是空集则称该集合为一个二元关系, 简称为关系，记作R.如R, 可记作 xRy；如果R, 则记作x y实例：R=, S=,a,b. R是二元关系, 当a, b不是有序对时，S不是二元关系根据上面的记法，可以写 1R2, aRb, a c 等. 第11页，共33页，2022年，5月20日，8点2分，星期日11从A到B的关系与A上的关系定义 设A,B为集合, AB的任何子集所定义的二元关系叫做从A到B的二元关系, 当A=B时则叫做 A上的二元关系.例4 A=0,1, B=1,2,3,

7、R1=, R2=AB, R3=, R4=. 那么 R1, R2, R3, R4是从 A 到 B 的二元关系, R3和R4同时也是 A上的二元关系. 计数|A|=n, |AA|=n2, AA的子集有 个. 所以 A上有 个不同的二元关系. 例如 |A|=3, 则 A上有=512个不同的二元关系. 第12页，共33页，2022年，5月20日，8点2分，星期日12A上重要关系的实例设 A 为任意集合，是 A 上的关系，称为空关系EA, IA 分别称为全域关系与恒等关系，定义如下： EA=|xAyA=AA IA=|xA例如, A=1,2, 则 EA=, IA=,第13页，共33页，2022年，5月20

8、日，8点2分，星期日13A上重要关系的实例（续）小于等于关系 LA, 整除关系DA, 包含关系R定义： LA=| x,yAxy, AR，R为实数集合 DB=| x,yBx整除y, BZ*, Z*为非0整数集 R=| x,yAxy, A是集合族.类似的还可以定义大于等于关系, 小于关系, 大于关系, 真包含关系等等. 第14页，共33页，2022年，5月20日，8点2分，星期日14实例例如 A = 1, 2, 3, B =a, b, 则 LA=, DA=, A=P(B)=,a,b,a,b, 则 A上的包含关系是 R=, ,第15页，共33页，2022年，5月20日，8点2分，星期日15关系的表示

9、表示方式：关系的集合表达式、关系矩阵、关系图 关系矩阵：若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上的关系 第16页，共33页，2022年，5月20日，8点2分，星期日16实例A=1,2,3,4, R=,R的关系矩阵MR和关系图

10、GR如下：第17页，共33页，2022年，5月20日，8点2分，星期日17基本运算定义定义域、值域、域逆、合成、限制、像基本运算的性质幂运算定义求法性质4.2 关系的运算第18页，共33页，2022年，5月20日，8点2分，星期日18关系的基本运算定义定义域、值域 和 域 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 第19页，共33页，2022年，5月20日，8点2分，星期日19关系的基本运算定义（续）逆与合成 R1 = | R RS

11、= | | z ( S R) 例2 R=, , , S=, , , , R1=, , , RS =, , , SR =, , 第20页，共33页，2022年，5月20日，8点2分，星期日20合成运算的图示方法 利用图示（不是关系图）方法求合成 RS = , , , SR =, , 第21页，共33页，2022年，5月20日，8点2分，星期日21限制与像定义 F 在A上的限制 FA = | xFy xA A 在F下的像 FA = ran(FA) 实例 R=, , , R1=, R1=2,4 R= R1,2=2,3,4注意：FAF, FA ranF 第22页，共33页，2022年，5月20日，8点

12、2分，星期日22关系基本运算的性质 定理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.第23页，共33页，2022年，5月20日，8点2分，星期日23定理2 设F, G, H是任意的关系, 则 (1) (FG)H=F(GH) (2) (FG)1= G1F1 证 (1) 任取, (FG)H t( H FG) t ( H s (G)

13、F) ) t s ( H G F) s (Ft (HG) s (FGH) F(GH) 所以 (FG)H = F(GH)关系基本运算的性质（续） 第24页，共33页，2022年，5月20日，8点2分，星期日24 (2) 任取, (FG)1 FG t ( G (t,x) F) t ( F1 (t,y) G1) G1F1 所以 (FG)1 = G1F1 关系基本运算的性质（续） 第25页，共33页，2022年，5月20日，8点2分，星期日25关系基本运算的性质（续） 设F 、G、 H为任意的二元关系，则有：F (G H ) =F G FH (G H ) F = G F HF(合成运算对运算满足分配律

14、）3. F (G H ) F G FH4. (G H ) F G F HF(合成运算对 运算分配后是包含关系）第26页，共33页，2022年，5月20日，8点2分，星期日26A上关系的幂运算设R为A上的关系, n为自然数, 则 R 的 n次幂定义为： (1) R0= | xA =IA (2) Rn+1 = RnR 注意： 对于A上的任何关系R1和R2都有 R10 = R20 = IA 对于A上的任何关系 R 都有 R1 = R 第27页，共33页，2022年，5月20日，8点2分，星期日27幂的求法(1) 对于集合表示的关系R，计算 Rn 就是n个R左复合 . (2) 矩阵表示就是n个矩阵相乘

15、, 其中相加采用逻辑加. 例3 设A=a,b,c,d, R=, 求R的各次幂, 分别用矩阵和关系图表示.解 R与R2的关系矩阵分别为第28页，共33页，2022年，5月20日，8点2分，星期日28同理，R0=IA, R3和R4的矩阵分别是：因此M4=M2, 即R4=R2. 因此可以得到R2=R4=R6=, R3=R5=R7=对于有穷集A，A上关系R的不同幂只有有限个。幂的求法（续）第29页，共33页，2022年，5月20日，8点2分，星期日29R0, R1, R2, R3,的关系图如下图所示幂的求法（续）第30页，共33页，2022年，5月20日，8点2分，星期日30幂运算的性质定理3 设A为n元集, R是A上的关系, 则存在自然数 s 和 t, 使得 Rs = Rt.证 R为A上的关系, 由于|A|=n, A上的不同关系只有 个. 当列出 R 的各次幂 R0, R1, R2, , , , 必存在自然数 s 和 t 使得 Rs=Rt.第31页，共33页，2022年，5月20日，8点2分，星期日31定理4 设 R 是 A 上的关系, m, nN, 则 (1) RmRn=Rm+n (2) (Rm)n=Rmn 证 用归纳法 (1) 对于任意给定的mN, 施归纳于n.若n=0, 则有 RmR0=RmIA=Rm=Rm+0 假设RmRn=Rm+n, 则有RmRn+1=Rm(RnR)=(R