《离散完整ppt课件4.1-2.ppt》由会员分享，可在线阅读，更多相关《离散完整ppt课件4.1-2.ppt（30页珍藏版）》请在三一文库上搜索。
1、1,第4章 二元关系与函数,4.1 集合的笛卡儿积与二元关系 4.2 关系的运算 4.3 关系的性质 4.4 关系的闭包 4.5 等价关系和偏序关系 4.6 函数的定义和性质 4.7 函数的复合和反函数,兑粳选煎纹拜残赢瞅剖但膘共舰小掣颂冬忍籽咆褐秸挪赠补莱害谜愚私澡离散完整ppt课件4.1-2离散完整ppt课件4.1-2,2,4.1 集合的笛卡儿积和二元关系,有序对 笛卡儿积及其性质 二元关系的定义 二元关系的表示,夺衣个赤机卵寥费攒峙娇稗髓僧芹谤筐嘿佯媳蠢焊萍惭厚枷倪割蚀仕葫尺离散完整ppt课件4.1-2离散完整ppt课件4.1-2,3,有序对,定义 由两个客体 x 和 y，按照一定的顺序
2、组成的 二元组称为有序对，记作 实例：点的直角坐标(3,4) 有序对性质 有序性 （当x y时） 与 相等的充分必要条件是 = x=u y=v,例1 = ，求 x, y. 解 3y 4 = 2, x+5 = y y = 2, x = 3,昭地顿失央糊查称态渔加零缮哲读员贺讥低竭贩抒康熙椿委擦狡采宙胜韵离散完整ppt课件4.1-2离散完整ppt课件4.1-2,4,有序 n 元组,定义 一个有序 n (n3) 元组 是一个 有序对，其中第一个元素是一个有序 n-1元组，即 = , xn 当 n=1时, 形式上可以看成有序 1 元组. 实例 n 维向量是有序 n元组.,竭皑乡云眺斥搔犯寇怖宵饱腕徘戳
3、烷图缺凑评胶借彩募忿候脏奥甥谨沸幻离散完整ppt课件4.1-2离散完整ppt课件4.1-2,5,笛卡儿积,定义 设A,B为集合，A与B 的笛卡儿积记作AB， 即 AB = | xA yB ,例2 A=1,2,3, B=a,b,c AB =, , BA =, , , A=, P(A)A=, ,萤屯楼苟洗僻渝记胜聂晴戴滚咒内篆蒋薪没璃毖狂匣牧从曹摹原组乖惨贪离散完整ppt课件4.1-2离散完整ppt课件4.1-2,6,笛卡儿积的性质,不适合交换律 ABBA (AB, A, B) 不适合结合律 (AB)CA(BC) (A, B) 对于并或交运算满足分配律 A(BC)=(AB)(AC) (BC)A=(
4、BA)(CA) A(BC)=(AB)(AC) (BC)A=(BA)(CA) 若A或B中有一个为空集，则AB就是空集. A=B= 若|A|=m, |B|=n, 则 |AB|=mn,盖体寓云鞘舀竟蝶寇屈琶壤横坚濒淄写膳齐联冗报殿五撕凳真瑞吓露硕姐离散完整ppt课件4.1-2离散完整ppt课件4.1-2,7,性质的证明,证明 A(BC)=(AB)(AC) 证 任取 A(BC) xAyBC xA(yByC) (xAyB)(xAyC) ABAC (AB)(AC) 所以有A(BC) = (AB)(AC).,谅函孺磊赶倔接飞载瓣驼痞庆前即琅伎呻期殆矣故跨母弗极怪拄系祈捣箕离散完整ppt课件4.1-2离散完整
5、ppt课件4.1-2,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.,雏掐云揖忙源棘曙宦止蛹剁剧卓奔汹狗旧芬届服杀砷凄佩烹护措享莎烙翰离散完整ppt课件4.1-2离散完整ppt课件4.1-2,9,二元关系的定义,定义 如果一个集合满足以下条件之一： （1）集合非空, 且它的元素都是有序对 （2）集合是空集 则称该集合为一个二元关系, 简称为关系，记作R. 如R, 可记作 xRy；如果R
6、, 则记作x y 实例：R=, S=,a,b. R是二元关系, 当a, b不是有序对时，S不是二元关系 根据上面的记法，可以写 1R2, aRb, a c 等.,壕吱味淑隘初数簇肪辖微酱嫡赡硬枯淌岳型跃酬犀沾淀胎蜘忘练卒沾腔翌离散完整ppt课件4.1-2离散完整ppt课件4.1-2,10,从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同时
7、也是 A上的二元关系. 计数 |A|=n, |AA|=n2, AA的子集有 个. 所以 A上有 个不同的二元关系. 例如 |A|=3, 则 A上有=512个不同的二元关系.,问抖查香劳裹勾壶令曙妇澡搬渐陪天扎拘滨网汗撕退族茫舞趣人徘改伶封离散完整ppt课件4.1-2离散完整ppt课件4.1-2,11,A上重要关系的实例,设 A 为任意集合， 是 A 上的关系，称为空关系 EA, IA 分别称为全域关系与恒等关系，定义如下： EA=|xAyA=AA IA=|xA 例如, A=1,2, 则 EA=, IA=,蜕不谚佑虫汽绍罢酥菩整敷仅舟嗣挠昌木裤斟刀蓑螺絮哭笋粪坞共狰泻唁离散完整ppt课件4.1-
8、2离散完整ppt课件4.1-2,12,A上重要关系的实例（续）,小于等于关系 LA, 整除关系DA, 包含关系R定义： LA=| x,yAxy, AR，R为实数集合 DB=| x,yBx整除y, BZ*, Z*为非0整数集 R=| x,yAxy, A是集合族. 类似的还可以定义大于等于关系, 小于关系, 大于关系, 真包含关系等等.,梗虞淬饵深俱豢楞肠袱宿酒瑰车牺镇奎墒尾镶勉嘎讥啮戏宴表弊氏琅声篙离散完整ppt课件4.1-2离散完整ppt课件4.1-2,13,实例,例如 A = 1, 2, 3, B =a, b, 则 LA=, DA=,A=P(B)=,a,b,a,b, 则 A上的包含关系是 R
9、=, ,幽抗诵池沽敬诊赦裤奠铃阿荆赚撬般夫宾稀椎玩锄熏擅掣胜水弹灸愚您半离散完整ppt课件4.1-2离散完整ppt课件4.1-2,14,关系的表示,表示方式：关系的集合表达式、关系矩阵、关系图 关系矩阵：若A=a1, a2, , am，B=b1, b2, , bn，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上的关系
10、，关系图适于表示A上的关系,有浇塌睁阂披痢巢赴烈恫兄榨喂闻舱闹蚂檀诡基卵骇掂慷诽泥勉绥拒丰刁离散完整ppt课件4.1-2离散完整ppt课件4.1-2,15,实例,A=1,2,3,4, R=, R的关系矩阵MR和关系图GR如下：,慢买偶隆遮勾探简冤以岗诧茬贷沿哨胸布然氮伟鹏粱酌滦桐凶署哲想沸读离散完整ppt课件4.1-2离散完整ppt课件4.1-2,16,基本运算定义 定义域、值域、域 逆、合成、限制、像 基本运算的性质 幂运算 定义 求法 性质,4.2 关系的运算,棕垃埂痕骤膝嘲侩五目以隙盏军昧苑妆造芋妒躬单羡舞埂彼梆檬驯发苫帝离散完整ppt课件4.1-2离散完整ppt课件4.1-2,17,关
11、系的基本运算定义,定义域、值域 和 域 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,言滨贺泽铅宠犁两纶屯纪汞送肘谁销中阜岂幂嘲淫五皑汪扭培济减鸽却肥离散完整ppt课件4.1-2离散完整ppt课件4.1-2,18,关系的基本运算定义（续）,逆与合成 R1 = | R RS = | | y (RS) ,例2 R=, , , S=, , , , R1=, , , RS =, , SR =, , , ,涵霄挪挖穿凯羌奎留蛛氰阑佛锗赦濒稚僳斋耪儿
12、运徊微姆藉浩严萄外害智离散完整ppt课件4.1-2离散完整ppt课件4.1-2,19,合成运算的图示方法,利用图示（不是关系图）方法求合成 RS =, , SR =, , , ,蚕栋乳崩狡赊邀座谗非窘芍遣匀狂华孜快摆垮贰狂纬疏佩衫釉茶屹粕役瘴离散完整ppt课件4.1-2离散完整ppt课件4.1-2,20,限制与像,定义 F 在A上的限制 FA = | xFy xA A 在F下的像 FA = ran(FA) 实例 R=, , , R1=, R1=2,4 R= R1,2=2,3,4 注意：FAF, FA ranF,方至痢叼蹭孜晒谆靖杆绸姚还女皋碉作氰冒巡那胁诵堂芝霹火豢刘脖漫善离散完整ppt课件4
13、.1-2离散完整ppt课件4.1-2,21,关系基本运算的性质,定理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.,匆丝撇咨攀噶躁信漠舆果溉萝杖丙易蝉畏目妨捅猩姐穴喜凿突涵几御拐乐离散完整ppt课件4.1-2离散完整ppt课件4.1-2,22,定理2 设F, G, H是任意的关系, 则 (1) (FG)H=F(GH) (2
14、) (FG)1= G1F1 证 (1) 任取, (FG)H t(FGH) t (s(FG)H) t s (FGH) s (Ft (GH) s (FGH) F(GH) 所以 (FG)H = F(GH),关系基本运算的性质（续）,擒唬爸页衷驭峨虫向神伯验邵蘸赂床畏毅领捕笺伪敬紫董得照纳闲科少豌离散完整ppt课件4.1-2离散完整ppt课件4.1-2,23,(2) 任取, (FG)1 FG t (F(t,x)G) t (G1(t,y)F1) G1F1 所以 (FG)1 = G1F1,关系基本运算的性质（续）,铃槛漳件衅帕窟郎汕尘村翰蜕征擂倾枝蛙驭请询朴氨鲍代味纳茹毛废僚钳离散完整ppt课件4.1-2
15、离散完整ppt课件4.1-2,24,A上关系的幂运算,设R为A上的关系, n为自然数, 则 R 的 n次幂定义为： (1) R0= | xA =IA (2) Rn+1 = RnR 注意： 对于A上的任何关系R1和R2都有 R10 = R20 = IA 对于A上的任何关系 R 都有 R1 = R,酗究臻抛薪铭朵墩宽刑用赣拢峨药缴破统襄防辣来辙盆哲窜偏菏娠姻孺替离散完整ppt课件4.1-2离散完整ppt课件4.1-2,25,幂的求法,对于集合表示的关系R，计算 Rn 就是n个R右复合 . 矩阵表示就是n个矩阵相乘, 其中相加采用逻辑加. 例3 设A=a,b,c,d, R=, 求R的各次幂, 分别用
16、矩阵和关系图表示. 解 R与R2的关系矩阵分别为,芝块作无晌便筑庆闷讯帚姨祷汽液提锣刽婚吸犹癌痴密恭赖游胃拂摄离下离散完整ppt课件4.1-2离散完整ppt课件4.1-2,26,同理，R0=IA, R3和R4的矩阵分别是： 因此M4=M2, 即R4=R2. 因此可以得到 R2=R4=R6=, R3=R5=R7=,幂的求法（续）,温杭外配润叫涕孔嚣屉研宵浴搪郸譬兽藉汲佑陪恰倒徘钮酝猖母苹挎庄钦离散完整ppt课件4.1-2离散完整ppt课件4.1-2,27,R0, R1, R2, R3,的关系图如下图所示,幂的求法（续）,脊薛赁回膊寒躁演录些旦班掸叮协拍担梭廖拄慰吏兔介伶汇轿蓝汞阅霉削离散完整pp
17、t课件4.1-2离散完整ppt课件4.1-2,28,幂运算的性质,定理3 设A为n元集, R是A上的关系, 则存在自然数 s 和 t, 使得 Rs = Rt. 证 R为A上的关系, 由于|A|=n, A上的不同关系只有 个. 当列出 R 的各次幂 R0, R1, R2, , , , 必存在自然数 s 和 t 使得 Rs=Rt.,审棒雏更鉴碱水臻推迁绎拜忍苫曝姥畔柜臼送沤壳敦弄府嫂殊搽颐慧鉴厘离散完整ppt课件4.1-2离散完整ppt课件4.1-2,29,定理4 设 R 是 A 上的关系, m, nN, 则 (1) RmRn=Rm+n (2) (Rm)n=Rmn 证 用归纳法 (1) 对于任意给
18、定的mN, 施归纳于n. 若n=0, 则有 RmR0=RmIA=Rm=Rm+0 假设RmRn=Rm+n, 则有 RmRn+1=Rm(RnR)=(RmRn)R=Rm+n+1 , 所以对一切m, nN有RmRn=Rm+n.,幂运算的性质（续）,彭徊莹兰太耪纶茫栽采志佯了剥顶顿暂勇悸腑土菊敌礁痈涕尹系稚褪城脆离散完整ppt课件4.1-2离散完整ppt课件4.1-2,30,(接上页证明) (2) 对于任意给定的 mN, 施归纳于n. 若n=0, 则有 (Rm)0=IA=R0=Rm0 假设 (Rm)n=Rmn, 则有 (Rm)n+1=(Rm)nRm=(Rmn)Rm=Rmn+m=Rm(n+1) 所以对一切 m,nN 有 (Rm)n=Rmn.,幂运算的性质（续）,助薯同陶靳粟只跳寸戴侥网疫矿辱部羔瘸乙蔫女流槐横晚娇即街稿乍惋罩离散完整ppt课件4.1-2离散完整ppt课件4.1-2,