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

1、离散数学 第四章二元关系和函数第1页，共80页，2022年，5月20日，1点51分，星期六2第4章 二元关系与函数4.1 集合的笛卡儿积与二元关系4.2 关系的运算4.3 关系的性质4.4 关系的闭包4.5 等价关系和偏序关系4.6 函数的定义和性质4.7 函数的复合和反函数第2页，共80页，2022年，5月20日，1点51分，星期六34.1 集合的笛卡儿积和二元关系 有序对 笛卡儿积及其性质 二元关系的定义 二元关系的表示第3页，共80页，2022年，5月20日，1点51分，星期六4 有序对的性质： 1） 有序性 （当x y时） 2） 与 相等的充分必要条件是 = x=u y=v例4.1 =

2、 ，求 x, y. 解 3y 4 = 2, x+5 = y y = 2, x = 3 4.1 二元关系的概念1. 有序对/序偶：由两个元素x和y按一定顺序排成二元组，记作： 。其中x称作第一个元素；y称作第二个元素。第4页，共80页，2022年，5月20日，1点51分，星期六5 实例 ：1.空间直角坐标系中的坐标 是有序三元组2. 图书馆记录是一个有序六元组. 2. 有序n元组：一个有序 n (n3) 元组 是一个有序对，其中第一个元素是一个有序 n-1元组，即 , xn= 。我们将来的研究重点为有序二元组，即有序对/序偶第5页，共80页，2022年，5月20日，1点51分，星期六6例4.2

3、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 。第6页，共80页，2022年，5月20日，1点51分，星期六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,

4、B=2,C=3AB=, (AB)C=,3=BC=, A(BC) =1, 第7页，共80页，2022年，5月20日，1点51分，星期六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,

5、B,C到工作集合G1,G2,G3,G4之间的关系第8页，共80页，2022年，5月20日，1点51分，星期六如R, 可记作 xRy；如果R, 则记作xR y实例：R1=, R2= , R3=,3,4，R4=|xNy ZR1,R2,R4是二元关系；R3不是二元关系。4. 二元关系： 如果一个集合满足以下条件之一：（1）集合非空, 且它的元素都是有序对(以有序对为 元素的集合)（2）集合是空集则称该集合为一个二元关系, 简称为关系，记作R.第9页，共80页，2022年，5月20日，1点51分，星期六105.从A到B的关系与A上的关系设A,B为集合, AB的任何子集所定义的二元关系叫做从A到B的二元

6、关系, 当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个不同的二元关系. 第10页，共80页，2022年，5月20日，1点51分，星期六11A上重要关系的实例设 A 为任意集合，是 A 上的关系

7、，称为空关系EA, IA 分别称为全域关系与恒等关系，定义如下： EA=|xAyA=AA IA=|xA例如, A=1,2, 则 EA=, IA=,注： IA; IA第11页，共80页，2022年，5月20日，1点51分，星期六12A上重要关系的实例（续）小于等于关系 LA, 整除关系DA, 包含关系R定义： LA=| x,yAxy, DA=| x,yAx整除y, R=| x,yP(A)xy, A是某集合.类似的还可以定义大于等于关系, 小于关系, 大于关系, 真包含关系等等. 第12页，共80页，2022年，5月20日，1点51分，星期六13实例例如 A = 1, 2, 3, B =a, b,

8、 则 LA=, DA=, P(B)=,a,b,a,b, 则 B上的包含关系是 R=, ,第13页，共80页，2022年，5月20日，1点51分，星期六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的关

9、系或者A上的关系，关系图仅适于表示A上的关系 第14页，共80页，2022年，5月20日，1点51分，星期六15 实例A=1,2,3,4, R=,R的关系矩阵MR和关系图GR如下：习题：4.1第15页，共80页，2022年，5月20日，1点51分，星期六 练习1.令A=1,2,3;B=a,b,求R1=,的关系矩阵。2.令A=1,2,3;求R2=,的关系图。3. 令F=,，G=,求FG, GF, FF。（方法自选）第16页，共80页，2022年，5月20日，1点51分，星期六17基本运算定义定义域、值域、域逆、合成、限制、像基本运算的性质幂运算定义求法性质4.2 关系的运算第17页，共80页，2

10、022年，5月20日，1点51分，星期六4.2 关系的运算关系R的定义域： domR = x | (y)R (即R中有序组的第一个元素构成的集合)关系R的值域： ranR =y | (x)R (即R中有序组的第二个元素构成的集合)一、关系的定义域与值域关系R的域： fldR = domR ranR 第18页，共80页，2022年，5月20日，1点51分，星期六19关系的基本运算定义例1 R=, 则 domR=1, 2, 4 ranR=2, 3, 4 fldR=1, 2, 3, 4 第19页，共80页，2022年，5月20日，1点51分，星期六20关系的基本运算定义（续） R1 = | R RS

11、 = | | z ( S R) 例2 R=, , , S=, , , , R1=, , , RS =, , , SR =, , 二. 逆与合成第20页，共80页，2022年，5月20日，1点51分，星期六21合成运算的图示方法 利用图示（不是关系图）方法求合成 R=, , , S=, , , , RS = , , , SR =, , RSSRS RR S第21页，共80页，2022年，5月20日，1点51分，星期六22实例 R=, , , R1=, R1=2,4 R1,2=, R= R1,2=2, 4 三 限制和像： 已知二元关系F 和集合A F 在A上的限制 FA = | xFy xA A

12、在F下的像 FA = ran(FA) 注意：FAF, FA ranF第22页，共80页，2022年，5月20日，1点51分，星期六23四. 关系运算的基本性质 (1) (2) (3) 不满足交换律： F GG F(4) 满足结合律： F G H=F (G H)(5) 第23页，共80页，2022年，5月20日，1点51分，星期六第24页，共80页，2022年，5月20日，1点51分，星期六25五. A上关系的幂运算设R为A上的关系, n为自然数, 则 R 的 n次幂定义为： (1) R0= | xA =IA (2) Rn+1 = Rn R 注意： 对于A上的任何关系R1和R2都有 R10 =

13、R20 = IA 对于A上的任何关系 R 都有 R1 = R 第25页，共80页，2022年，5月20日，1点51分，星期六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的关系矩阵分别为六. 幂的求法：第26页，共80页，2022年，5月20日，1点51分，星期六27同理，R0=IA, R3和

14、R4的矩阵分别是：因此M4=M2, 即R4=R2. 因此可以得到R2=R4=R6=, R3=R5=R7=第27页，共80页，2022年，5月20日，1点51分，星期六28R0, R1, R2, R3,的关系图如下图所示关系图法结论：仅当A有回路时，上述结论成立。第28页，共80页，2022年，5月20日，1点51分，星期六当图中没有回路时：第29页，共80页，2022年，5月20日，1点51分，星期六30七. 幂的性质：当关系图有回路时： (2) (3) 第30页，共80页，2022年，5月20日，1点51分，星期六31证明（2）：用数学归纳法 若n=0, 则有 RmR0=RmIA=Rm=Rm

15、+0 假设RmRn=Rm+n, 则有RmRn+1=Rm (RnR)=(RmRn) R=Rm+n+1 。幂运算的性质（续）证明（3）： 若n=0, 则有 假设 则有课后习题：4.2，4.3，4.13第31页，共80页，2022年，5月20日，1点51分，星期六第32页，共80页，2022年，5月20日，1点51分，星期六第33页，共80页，2022年，5月20日，1点51分，星期六第34页，共80页，2022年，5月20日，1点51分，星期六4.3 关系的性质R的关系矩阵：主对角线元素全是1R的关系图：每个顶点都有环自反性： x A 有R (R是A上的关系) 关系矩阵：主对角线元素全是0关系图：

16、 每个顶点都没有环反自反性：x A R第35页，共80页，2022年，5月20日，1点51分，星期六例1：A=1,2,3,R1=,R2=,R3=, R4=,R5=,既不是自反的也不是非自反的自反的自反的既不是自反的也不是非自反的反自反的例1：是自反的一定不是反自反的；是反自反的一定不是自反的！在自反性方面R有3种可能：自反的；反自反的；既非自反又非反自反的第36页，共80页，2022年，5月20日，1点51分，星期六对称性：若 R，则 R 关系矩阵：对称阵(aij=aji)关 系 图：如果两个顶点之间有边，一定是一对方向相反的边。反对称性：若 R且xy，则 R 关系矩阵：如果rij = 1，且

17、 i j，则rji = 0 关系图： 如果两个顶点之间有边，一定是只有一条有向边。！R= |xR既是对称关系又是反对称关系第37页，共80页，2022年，5月20日，1点51分，星期六例2：A=1,2,3,R1=,R2=,R3=,R4=,R5=,反对称的既对称又反对称的对称的反对称的既非对称又非反对称的！在对称性方面R有4种可能：对称的；反对称的；既对称又反对称的；既非对称又非反对称的第38页，共80页，2022年，5月20日，1点51分，星期六传递性：若 R且 R，则 R 关系图：如果顶点xi到xj有边， xj到xk有边，则从xi到xk有边！若a可经过两条或两条以上的线到达b，则 R 第39

18、页，共80页，2022年，5月20日，1点51分，星期六例3：A=1,2,3,4,R1=,R2=,R3=,R4=,R5=,传递的传递的非传递的传递的非传递的！在传递性方面，R有两种可能：传递的；非传递的。第40页，共80页，2022年，5月20日，1点51分，星期六练习：自反的对称的反对称的传递的自反的对称的传递的反自反的反对称的反对称的传递的课后习题：4.4，4.12根据关系图判断关系的综合性质：第41页，共80页，2022年，5月20日，1点51分，星期六4.4 关系的闭包运算闭包：设RAA，自反闭包 记作 r(R)对称闭包 记作 s(R)传递闭包 记作 t(R)那么，包含R而使之具有自反

19、性质的最小关系，称之为R的自反闭包；包含R而使之具有传递性质的最小关系，称之为R的传递闭包。一、定义包含R而使之具有对称性质的最小关系，称之为R的对称闭包。第42页，共80页，2022年，5月20日，1点51分，星期六幂运算：设RAA，kN，约定(1) R0 = IA = | xA(2) R1 = R(3) Rk+1 = Rk R二、计算方法为了有效地计算关系R的各种闭包，先引进关系的幂运算概念。第43页，共80页，2022年，5月20日，1点51分，星期六逻辑运算方法：设R是A上的任一关系，则(1) r (R) = RIA(2) s (R) = RR(3) t (R) = RR2R3 Rn-

20、1第44页，共80页，2022年，5月20日，1点51分，星期六矩阵形式：(M为R的关系矩阵)(1) Mr = M + E（单位矩阵）(2) Ms = M + M (M 是M的转置)(3) Mt = M+M2 +.+Mn-1其中“ +” 均表示“ 逻辑加”第45页，共80页，2022年，5月20日，1点51分，星期六关系图法：(1) 自反闭包图：对没有加环的点加环(2) 对称闭包图：单边的加方向相反的边(3) 传递闭包图：若Ai经过两条或两条以 上的边可到达Aj，且无 边则加边第46页，共80页，2022年，5月20日，1点51分，星期六例4.10 设A=a,b,c,d，A上的关系求 r (R

21、)，s (R) 和 t (R)解：1.逻辑求法： r(R) = RIA=, , , , , , R=,= R,三、实例第47页，共80页，2022年，5月20日，1点51分，星期六=, , , , = R,s (R) = RRt (R) = RR2R3 Rn-1= R,=, , ,R=,第48页，共80页，2022年，5月20日，1点51分，星期六2.矩阵运算： R=,第49页，共80页，2022年，5月20日，1点51分，星期六3.关系图方法： 课后习题：4.14Rr(R)t(R)s(R)第50页，共80页，2022年，5月20日，1点51分，星期六第51页，共80页，2022年，5月20日

22、，1点51分，星期六4.5 等价关系和偏序关系等价关系：集A上的关系R是自反的, 对称的和传递的。一、等价关系及用途例：A=1,2,3,8，R=|x y(mod 3)则 147，258，36设 R 是一个等价关系, 若R, 称 x 等价于y, 记做 xy.第52页，共80页，2022年，5月20日，1点51分，星期六相容关系： R是集A上的关系，且R是自反的，对称的(1)在一群人的集合上年龄，姓名相同的关系是等价关系,而朋友关系是相容关系，因为它可能不是传递的. (2)动物是按种属分类的；“具有相同种属性”的关系是动物集合上的等价关系. (3)集合上的恒等关系和全域关系都是等价关系. (4)在

23、同一平面上三角形之间的相似关系是等价关系,但直线间的平行关系不是等价关系也不是相容关系,因为它不是自反的.例子：！等价关系一定是相容关系；相容关系不一定是等价关系第53页，共80页，2022年，5月20日，1点51分，星期六等价类： R是集A上的等价关系，对于任一aA，aR=x | aRx, xA被称为a的等价类。即：xR=y | xy在例中：1R =4R =7R =1,4,7;2R =5R =8R =2,5,8;3R =6R =9R =3,6,9;第54页，共80页，2022年，5月20日，1点51分，星期六等价类的性质：R是非空集合，对任意的x，yA，下面的结论成立：(1) xR 且xR

24、A (等价类为A的子集)(2) 若xy则xR =yR ，反之成立。(3) 若xRy，则xR yR = 第55页，共80页，2022年，5月20日，1点51分，星期六集A在等价关系R下的商集：设R为非空集A上的等价关系，A在R下的商集记作A/R， A/R=xR | xA.(集合的集合）例的商集为：A/R=1,4,7,2,5,8,3,6,9注意：A/EA = A A/IA=x|xA第56页，共80页，2022年，5月20日，1点51分，星期六集A的划分：令=A/R， 满足以下性质：(1) (2) 中任意两个元素不交 (3) 中所有元素的并集为A则 为A的划分。集合A上的划分是不唯一的第57页，共8

25、0页，2022年，5月20日，1点51分，星期六 对于集合A，若给定一个等价关系，则我们可唯一确定一个商集集合A上的等价关系与划分是一一对应的。 集合A上的一个商集可唯一确定A上的一个划分第58页，共80页，2022年，5月20日，1点51分，星期六例 设A=1,2,3，求出A上所有的等价关系：解：先求A的各种划分：只有1个划分块的划分1，具有两个划分块的划分2， 3，和4，具有3个划分块5。第59页，共80页，2022年，5月20日，1点51分，星期六设对应于划分i 的等价关系 Ri，i = 1,2,5，则有R5 = ，R1 = ，R2 = ，R3 = ，R4 = ，第60页，共80页，20

26、22年，5月20日，1点51分，星期六偏序关系：集合A上的关系R是自反的，反对称的和传递的，记作“ ” 。二、偏序关系及用途设R为偏序关系, 如果R, 则记作x y, 读作“x小于等于y”. 注意: 这里的“小于等于”不是指数的大小, 而是在偏序关系中的顺序性.第61页，共80页，2022年，5月20日，1点51分，星期六例 设A=1,2,3，求出A上的大于等于关系：解： =,其中： 1 1, 2 1, 2 2, 3 1, 3 2, 33第62页，共80页，2022年，5月20日，1点51分，星期六偏序关系例子：（1）任何集合A上的恒等关系（2）集合A的幂集P(A)上的包含关系（4）正整数集上

27、的整除关系都是偏序关系.（3）实数集上的小于等于，大于等于关系,第63页，共80页，2022年，5月20日，1点51分，星期六相关概念：偏序集：集合A和偏序关系R 构成一个偏序集，记作。如：,等可比：对于任意两个元素x和y，若xy或y x，则x与y是可比的全序关系与全序集：若A中任意两个元素都是可比的，则R为全序关系； 为全序集。第64页，共80页，2022年，5月20日，1点51分，星期六盖住：如果xy，且不存在z使x z y (不是间接的),则称y能盖住x。例：锅，笼屉，锅盖火车卧铺的下铺，中铺，上铺第65页，共80页，2022年，5月20日，1点51分，星期六例 设A=1,2,3,4，求

28、出A上的整除关系：解: R整除=, ,则：2,3能盖住1；4能盖住2；4不能盖住1第66页，共80页，2022年，5月20日，1点51分，星期六偏序集的哈斯图(1) 去掉箭头；（盖住）(2) 去掉间接关系；（传递）(3)去掉环。（自反的）第67页，共80页，2022年，5月20日，1点51分，星期六哈斯图实例例：画出 和第68页，共80页，2022年，5月20日，1点51分，星期六全序关系的哈斯图：全序集中全部元素可以排序，它的哈斯图为一条直线。也称为线序集。集合A上的偏序关系与哈斯图是一一对应的。课后习题：4.16第69页，共80页，2022年，5月20日，1点51分，星期六第70页，共80

29、页，2022年，5月20日，1点51分，星期六(2) 若yA，使得 (x)(xAyx)，则称y是A的极大元 (没有比我大的)(1) 若yA，使得 (x)(xAxy)，则称y是A的极小元 (没有比我小的 )偏序集中的一些特殊元素设是偏序集极小元与极大元一定存在，不一定唯一第71页，共80页，2022年，5月20日，1点51分，星期六(3) 如果yA，使得(x)(xAyx)为真，则y是A的最小元 (比谁都小 )(4) 如果yB，使得(x)(xB xy)为真，则y是B的最大元 (比谁都大)最小元与最大元或唯一或不存在第72页，共80页，2022年，5月20日，1点51分，星期六例子：左图：极小元为1;极大元为5,9,6,8,7 最小元为1;没有最大元。右图：极小元为 ;极大元为a,b,c 最小元为 ; 最大元为a,b,c。第