离散数学第四章：二元关系和函数.ppt

二元关系和函数,第四章,2,第4章 二元关系与函数,4.1 集合的笛卡儿积与二元关系 4.2 关系的运算 4.3 关系的性质 4.4 关系的闭包 4.5 等价关系和偏序关系 4.6 函数的定义和性质 4.7 函数的复合和反函数,3,4.1 集合的笛卡儿积和二元关系,有序对 笛卡儿积及其性质 二元关系的定义 二元关系的表示,4,有序对的性质： 1） 有序性 （当x y时） 2） 与 相等的充分必要条件是 = x=u y=v,例4.1 = ，求 x, y. 解 3y 4 = 2, x+5 = y y = 2, x = 3,4.1 二元关系的概念,1. 有序对/序偶：由两个元素x和y按一定顺序 排成二元组，记作： 。其中x称作第 一个元素；y称作第二个元素。,5,实例 ： 1.空间直角坐标系中的坐标 是有序三元组 2. 图书馆记录是一个有序六元组.,2. 有序n元组：一个有序 n (n3) 元组 是一个有序对，其中第一个元素是一个有序 n-1元组，即 , xn= 。,我们将来的研究重点为有序二元组，即有序对/序偶,6,例4.2 A=1,2,3, B=a,b,c,C= AB =, , BA =, , , AA=, , AC= CA= ,3. 笛卡儿积：设A, B为集合，用A中元素为第一个元素，B中元素为第二个元素，构成有序对. 所有这样的有序对组成的集合叫做 A与B 的笛卡儿积 记作AB, 即 AB = | xA yB 。,7,笛卡儿积的性质： 1. 不适合交换律 ABBA (AB, A, B) 2.若A或B中有一个为空集，则AB就是空集. A=B= 3. 若|A|=m, |B|=n, 则 |AB|=mn 4.不适合结合律 (AB)CA(BC) (A,B,C) 例： A=1,B=2,C=3 AB=, (AB)C=,3= BC=, A(BC) = ,8,二元关系：集合中两个元素之间的某种关系 例3 甲、乙、丙3个人进行乒乓球比赛，任何两个人之间都要比赛一场。假设比赛结果是乙胜甲，甲胜丙，乙胜丙。 比赛结果可表示为： ， ， ，其中表示x胜y，它表示了集合甲,乙,丙中元素之间的一种胜负关系. 例4 有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之间的关系,如R, 可记作 xRy；如果R, 则记作xR y 实例：R1=, R2= , R3=,3,4，R4=|xNy Z R1,R2,R4是二元关系；R3不是二元关系。,4. 二元关系： 如果一个集合满足以下条件之一： （1）集合非空, 且它的元素都是有序对(以有序对为 元素的集合) （2）集合是空集 则称该集合为一个二元关系, 简称为关系，记作R.,10,5.从A到B的关系与A上的关系 设A,B为集合, AB的任何子集所定义的二元 关系叫做从A到B的二元关系, 当A=B时则叫做 A上 的二元关系.,例5 A=0,1, B=1,2,3, R1=, R2=AB, R3=, R4=. 那么 R1, R2, R3, R4是从 A 到 B 的二元关系, R3和R4同时也是 A上的二元关系. 计数： |A|=n, |B|=m, |AB|= nm , AB的子集有 个. 所以 A到B上有 个不同的二元关系. |A|=n, |AA|= , AA的子集有 个. 所以 A上有 个不同的二元关系. 例如 |A|=3, 则 A上有512个不同的二元关系.,11,A上重要关系的实例,设 A 为任意集合， 是 A 上的关系，称为空关系 EA, IA 分别称为全域关系与恒等关系，定义如下： EA=|xAyA=AA IA=|xA 例如, A=1,2, 则 EA=, IA=, 注： IA; IA,12,A上重要关系的实例（续）,小于等于关系 LA, 整除关系DA, 包含关系R定义： LA=| x,yAxy, DA=| x,yAx整除y, R=| x,yP(A)xy, A是某集合. 类似的还可以定义大于等于关系, 小于关系, 大于关系, 真包含关系等等.,13,实例,例如 A = 1, 2, 3, B =a, b, 则 LA=, DA=,P(B)=,a,b,a,b, 则 B上的包含关系是 R=, ,14,关系的表示,表示方式：关系的集合表达式、关系矩阵、关系图 关系矩阵：若A=x1, x2, , xm，B=y1, y2, , yn，R是从A到B的关系，以A元素为行，B元素为列，MR = rij mn, 其中 rij = 1 R，否则rij = 0。 关系图：若A= x1, x2, , xm，R是从A上的关系，R的关系图是GR=, 以A中元素为结点，如果 R，则从 xi 到 xj 有一条有向边. 注意：A, B为有穷集，关系矩阵适于表示从A到B的关系或者A上的关系，关系图仅适于表示A上的关系,15,实例,A=1,2,3,4, R=, R的关系矩阵MR和关系图GR如下： 习题：4.1,练习,1.令A=1,2,3;B=a,b,求R1=,的关系矩阵。 2.令A=1,2,3;求R2=,的关系图。 3. 令F=,，G=,求FG, GF, FF。（方法自选）,17,基本运算定义 定义域、值域、域 逆、合成、限制、像 基本运算的性质 幂运算 定义 求法 性质,4.2 关系的运算,4.2 关系的运算,关系R的定义域： domR = x | (y)R (即R中有序组的第一个元素构成的集合),关系R的值域： ranR =y | (x)R (即R中有序组的第二个元素构成的集合),一、关系的定义域与值域,关系R的域： fldR = domR ranR,19,关系的基本运算定义,例1 R=, 则 domR=1, 2, 4 ranR=2, 3, 4 fldR=1, 2, 3, 4,20,关系的基本运算定义（续）,R1 = | R RS = | | z ( S R) 例2 R=, , , S=, , , , R1=, , , RS =, , , SR =, , ,二. 逆与合成,21,合成运算的图示方法,利用图示（不是关系图）方法求合成 R=, , , S=, , , , RS = , , , SR =, , ,R,S,S,R,S RR S,22,实例 R=, , , R1=, R1=2,4 R1,2=, R= R1,2=2, 4,三 限制和像： 已知二元关系F 和集合A F 在A上的限制 FA = | xFy xA A 在F下的像 FA = ran(FA),注意：,FAF, FA ranF,23,四. 关系运算的基本性质,(1),(2),(3) 不满足交换律： F GG F,(4) 满足结合律： F G H=F (G H),(5),25,五. A上关系的幂运算,设R为A上的关系, n为自然数, 则 R 的 n次幂定义为： (1) R0= | xA =IA (2) Rn+1 = Rn R 注意： 对于A上的任何关系R1和R2都有 R10 = R20 = IA 对于A上的任何关系 R 都有 R1 = R,26,(1) 定义法：对于集合表示的关系R，计算 Rn 就是n个R左复合 . (2) 矩阵乘法：矩阵表示就是n个矩阵相乘, 其中相加采用逻辑加. （线性代数，逻辑乘法） (3) 关系图法：若点a经k(k=1,2,n)条线可到达点b，则在 的关系图上，a到b有线相连。 例3 设A=a,b,c,d, R=, 求R的各次幂, 分别用矩阵和关系图表示. 解 R与R2的关系矩阵分别为,六. 幂的求法：,27,同理，R0=IA, R3和R4的矩阵分别是： 因此M4=M2, 即R4=R2. 因此可以得到 R2=R4=R6=, R3=R5=R7=,28,R0, R1, R2, R3,的关系图如下图所示,关系图法,结论： 仅当A有回路时，上述结论成立。,当图中没有回路时：,30,七. 幂的性质：,当关系图有回路时：,(2),(3),31,证明（2）：用数学归纳法 若n=0, 则有 RmR0=RmIA=Rm=Rm+0 假设RmRn=Rm+n, 则有 RmRn+1=Rm (RnR)=(RmRn) R=Rm+n+1 。,幂运算的性质（续）,证明（3）： 若n=0, 则有 假设 则有,课后习题：4.2，4.3，4.13,4.3 关系的性质,R的关系矩阵：主对角线元素全是1,R的关系图：每个顶点都有环,自反性： x A 有R (R是A上的关系),关系矩阵：主对角线元素全是0,关系图： 每个顶点都没有环,反自反性：x A R,例1： A=1,2,3, R1=, R2=, R3=, R4=, R5=,既不是自反的也不是非自反的,自反的,自反的,既不是自反的也不是非自反的,反自反的,例1：,是自反的一定不是反自反的；是反自反的一定不是自反的,！在自反性方面R有3种可能：自反的；反自反的；既非自反又非反自反的,对称性：若 R，则 R,关系矩阵：对称阵(aij=aji),关 系 图：如果两个顶点之间有边，一定是一对方向相反的边。,反对称性：若 R且xy，则 R,关系矩阵：如果rij = 1，且 i j，则rji = 0,关系图： 如果两个顶点之间有边，一定是只有一条有向边。,！R= |xR既是对称关系又是反对称关系,例2：,A=1,2,3, R1=, R2=, R3=, R4=, R5=,反对称的,既对称又反对称的,对称的,反对称的,既非对称又非反对称的,！在对称性方面R有4种可能：对称的；反对称的；既对称又反对称的；既非对称又非反对称的,传递性：若 R且 R，则 R,关系图：如果顶点xi到xj有边， xj到xk有边，则从xi到xk有边,！若a可经过两条或两条以上的线到达b，则 R,例3：,A=1,2,3,4, R1=, R2=, R3=, R4=, R5=,传递的,传递的,非传递的,传递的,非传递的,！在传递性方面，R有两种可能：传递的；非传递的。,练习：,自反的,对称的,反对称的,传递的,自反的,对称的,传递的,反自反的,反对称的,反对称的,传递的,课后习题：4.4，4.12,根据关系图判断关系的综合性质：,4.4 关系的闭包运算,闭包：设RAA，,自反闭包 记作 r(R),对称闭包 记作 s(R),传递闭包 记作 t(R),那么，包含R而使之具有自反性质的最小关系，称之为R的自反闭包；,包含R而使之具有传递性质的最小关系，称之为R的传递闭包。,一、定义,包含R而使之具有对称性质的最小关系，称之为R的对称闭包。,幂运算：设RAA，kN，约定,(1) R0 = IA = | xA,(2) R1 = R,(3) Rk+1 = Rk R,二、计算方法,为了有效地计算关系R的各种闭包，先引进关系的幂运算概念。,逻辑运算方法：设R是A上的任一关系，则,(1) r (R) = RIA,(2) s (R) = RR,(3) t (R) = RR2R3 Rn-1,矩阵形式：(M为R的关系矩阵),(1) Mr = M + E（单位矩阵）,(2) Ms = M + M (M 是M的转置),(3) Mt = M+M2 +.+Mn-1,其中“ +” 均表示“ 逻辑加”,关系图法：,(1) 自反闭包图：对没有加环的点加环,(2) 对称闭包图：单边的加方向相反的边,(3) 传递闭包图：若Ai经过两条或两条以 上的边可到达Aj，且无 边则加边,例4.10 设A=a,b,c,d，A上的关系,求 r (R)，s (R) 和 t (R),解：1.逻辑求法： r(R) = RIA,=, , , , , , ,R=,= R,三、实例,=, , , , ,= R,s (R) = RR,t (R) = RR2R3 Rn-1,= R,=, , ,R=,2.矩阵运算：,R=,3.关系图方法：,课后习题：4.14,R,r(R),t(R),s(R),4.5 等价关系和偏序关系,等价关系：集A上的关系R是自反的, 对称的和传递的。,一、等价关系及用途,例4.5.1：A=1,2,3,8，R=|x y(mod 3) 则 147，258，36,设 R 是一个等价关系, 若R, 称 x 等价于y, 记做 xy.,相容关系： R是集A上的关系，且R是自反的，对称的,(1)在一群人的集合上年龄，姓名相同的关系是等价关系, 而朋友关系是相容关系，因为它可能不是传递的. (2)动物是按种属分类的；“具有相同种属性”的关系是动 物集合上的等价关系. (3)集合上的恒等关系和全域关系都是等价关系. (4)在同一平面上三角形之间的相似关系是等价关系,但直 线间的平行关系不是等价关系也不是相容关系,因为它不 是自反的.,例子：,！等价关系一定是相容关系；相容关系不一定是等价关系,等价类： R是集A上的等价关系，对于任一aA，,aR=x | aRx, xA,被称为a的等价类。,即：xR=y | xy,在例4.5.1中： 1R =4R =7R =1,4,7; 2R =5R =8R =2,5,8; 3R =6R =9R =3,6,9;,等价类的性质：R是非空集合，对任意的x，yA，下面的结论成立：,(1) xR 且xR A (等价类为A的子集),(2) 若xy则xR =yR ，反之成立。,(3) 若xRy，则xR yR = ,集A在等价关系R下的商集：设R为非空集A上的等价关系，A在R下的商集记作A/R， A/R=xR | xA.(集合的集合）,例4.5.1的商集为： A/R=1,4,7,2,5,8,3,6,9,注意：A/EA = A A/IA=x|xA,集A的划分：令=A/R， 满足以下性质：,(1) ,(2) 中任意两个元素不交,(3) 中所有元素的并集为A,则 为A的划分。,集合A上的划分是不唯一的,对于集合A，若给定一个等价关系，则我们可唯一确定一个商集,集合A上的等价关系与划分是一一对应的。,集合A上的一个商集可唯一确定A上的一个划分,例4.5.2 设A=1,2,3，求出A上所有的等价关系：,解：先求A的各种划分：只有1个划分块的划分1，具有两个划分块的划分2， 3，和4，具有3个划分块5。,设对应于划分i 的等价关系 Ri，i = 1,2,5，则有,R5 = ，,R1 = ，,R2 = ，,R3 = ，,R4 = ，,，,，,，,，,，,，,，,，,偏序关系：集合A上的关系R是自反的，反对称的和传递的，记作“ ” 。,二、偏序关系及用途,设R为偏序关系, 如果R, 则记作x y, 读作“x小于等于y”. 注意: 这里的“小于等于”不是指数的大小, 而是在偏序关系中的顺序性.,例4.5.3 设A=1,2,3，求出A上的大于等于关系：,解： =,其中： 1 1, 2 1, 2 2, 3 1, 3 2, 33,偏序关系例子：,（1）任何集合A上的恒等关系,（2）集合A的幂集P(A)上的包含关系,（4）正整数集上的整除关系都是偏序关系.,（3）实数集上的小于等于，大于等于关系,相关概念：,偏序集：集合A和偏序关系R 构成一个偏序集， 记作。如：,等,可比：对于任意两个元素x和y，若xy或y x， 则x与y是可比的,全序关系与全序集：若A中任意两个元素都是可比的， 则R为全序关系； 为全序集。,盖住：如果xy，且不存在z使x z y (不是间接的), 则称y能盖住x。,例：,锅，笼屉，锅盖,火车卧铺的下铺，中铺，上铺,例4.5.4 设A=1,2,3,4，求出A上的整除关系：,解: R整除=, ,则：2,3能盖住1；4能盖住2；4不能盖住1,偏序集的哈斯图,(1) 去掉箭头；（盖住）,(2) 去掉间接关系；（传递）,(3)去掉环。（自反的）,哈斯图实例,例4.5.5：画出 和,全序关系的哈斯图：,全序集中全部元素可以排序，它的哈斯图为一条直线。也称为线序集。,集合A上的偏序关系与哈斯图是一一对应的。,课后习题：4.16,(2) 若yA，使得 (x)(xAyx)，则称y是A的极大元 (没有比我大的),(1) 若yA，使得 (x)(xAxy)，则称y是A的极小元 (没有比我小的 ),偏序集中的一些特殊元素,设是偏序集,极小元与极大元一定存在，不一定唯一,(3) 如果yA，使得(x)(xAyx)为真，则y是A的最小元 (比谁都小 ),(4) 如果yB，使得(x)(xB xy)为真，则y是B的最大元 (比谁都大),最小元与最大元或唯一或不存在,例子：,左图：极小元为1;极大元为5,9,6,8,7 最小元为1;没有最大元。,右图：极小元为 ;极大元为a,b