



下载本文档
版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
1、关系及其运算关系及其运算离散数学集合论南京大学计算机科学与技术系回顾回顾l集合的基本概念l集合及其描述l集合相等、子集关系l幂集、笛卡尔乘积l集合运算l交并补、广义交、广义并l集合恒等式l集合相关命题的证明方式提要提要l关系的定义l关系的表示l关系的运算l0-1矩阵运算l关系的性质有序对(有序对(Ordered pair)l(a, b)是集合a, a, b的简写l次序的体现l(x,y)=(u,v) iff x=u 且 y=v若x,x,y=u,u,v,则x=u或x= u,v, 因此x=u。假设yv(1) 若x=y, 左边=x, 而vx,右边x; (2) 若xy,则必有x,y= u,v, 但y既非
2、u,又非v, 矛盾。笛卡尔乘积(笛卡尔乘积(Cartesian Product)l对任意集合A, B笛卡尔积 AB = (a, b)|aA, bBl例:1,2,3a,b = (1, a), (3, a) , (3, a), (1, b), (2, b) , (3, b) l若A,B是有限集合, |AB|= |A|B| 例题例题lA=1,2, (A)A=?l|A|=m, |B|=n, |AB|=?(二元)关系的定义(二元)关系的定义l若A, B是集合,从A到B的一个关系是AB的一个子集.l集合, 可以是空集l集合的元素是有序对l关系意味着什么?l两类对象之间建立起来的联系!从从A到到B的二元关系
3、的二元关系l笛卡尔乘积的子集l“从A到B的关系”R;RABl若A=B: 称为“集合A上的(二元)关系”l例子l常用的数学关系:不大于、整除、集合包含等 l网页链接、文章引用、相互认识特殊的二元关系特殊的二元关系 l集合A上的空关系: 空关系即空集l全域关系 EA: EA = (x, y) | x, yA l恒等关系 IA : IA =(x, x) | xA 函数是一种特殊的关系函数是一种特殊的关系 l函数 f : ABlR= (x, f(x) | xA 是一个从A到B的一个关系关系的表示关系的表示 假设A=a,b,c,d, B=, / 假设为有限集合l集合表示: R1=(a, ), (b, )
4、, (c, ),(c, ) 0-1矩阵 有向图000101001010abcd adcb AB二元关系和有向图二元关系和有向图关系 RABA和B是集合有序对集合(x,y)R若A=B, R中存在序列:(x1,x2), (x2,x3),(xn-1,xn)有向图 (VD , ED )顶点集 VD= AB有向边集ED从x到y有一条边图D中存在从 x1 到 xn 的长度为 n-1的通路关系的运算(关系的运算(1)l关系是集合, 所有的集合运算对关系均适用l例子:l自然数集合上: “” “=” 等同于 “”l自然数集合上: “” “”等同于“=”l自然数集合上: “”等同于关系的运算(关系的运算(2)l与
5、定义域和值域有关的运算ldom R = x | y (x,y)Rlran R = y | x (x,y)Rlfld R = dom R ran RlR A = (x,y) | xA xRy RlRA = y | x (xA (x,y)R)= ran(RA) ranRl例:A=1,2,3,4,5, B=1,3,5,6, A上关系R: R=(1,2), (1,4),(2,3),(3,5),(5,2), 求 RB、RB、R(1)和R(2)关系的运算(关系的运算(3)l逆运算lR-1 = (x, y) | (y,x)Rl注意:如果R是从A到B的关系,则R-1是从B到A的。l(R-1)-1 = Rl例子
6、:(R1R2)-1 = R1-1R2-1 l(x, y) (R1R2)-1 (y, x)(R1R2) l (y, x)R1 或 (y, x)R2 l (x, y)R1-1 或 (x, y)R2-1关系的关系的运算(运算(4)l关系的复合(合成, Composition)设 R1AB, R2BC, R1与R2的复合(合成), 记为 R2 R1, 定义如下:R2 R1=(a, c) AC | bB (a, b) R1(b, c)R2) 复合关系的图示复合关系的图示l(a, c)R2 R1 当且仅当 aA, cC, 且存在bB,使得(a, b) R1, (b,c) R2abcR1R2关系的复合运算:
7、举例关系的复合运算:举例l设A=a, b, c, d, R1, R2为A上的关系,其中:R1 = (a, a), (a, b), (b, d)R2 = (a, d), (b, c), (b, d), (c, b)则:R2 R1 = (a, d), (a, c), (a, d)R1 R2 = (c, d)R12 = (a, a), (a, b), (a, d)关系的复合运算的性质(关系的复合运算的性质(1)l结合律l给定R1AB, R2BC, R3CD, 则: (R3 R2) R1 = R3 (R2 R1) l证明左右两个集合相等.关系的复合运算的性质(关系的复合运算的性质(2)l复合关系的逆关
8、系l给定R1AB, R2BC, 则: (R2 R1)-1 = R1-1 R2-1 l同样,证明左右两个集合相等l(x, y) (R2 R1)-1 (y, x) R2 R1 tB (y, t)R1 (t, x)R2) tB (t, y) R1-1(x, t)R2-1 ) (x, y) R2-1 R1-1 关系的复合运算的性质(关系的复合运算的性质(3)l对集合并运算满足分配律l给定FAB, GBC, HBC, 则: (GH) F = (G F) (H F) l对集合交运算: (G H) F (G F) (H F) l注意:等号不成立。A=a, B=s,t, C=b; F=(a,s), (a,t)
9、, G=(s,b), H=(t,b); GH=, (G F) (H F)=(a,b) 0-1 矩阵运算矩阵运算l令0-1矩阵M1=aij,M2=bij:lC=M1 M2: cij=1 iff. aij=bij=1lC=M1 M2: cij=1 iff. aij=1或bij=1l令rs矩阵M1=aij;st矩阵M2=bij:lC=M1 M2: cij=1 iff. 11011011110110101010001110) 11(kjikbak关系运算的矩阵关系运算的矩阵法(法(1)l命题2121RRRRMMM2121RRRRMMM2112RRRRMMM11011011110110101010001
10、110证明:111),(,1MMDMCMBMA;:;:2112RRR1R2RR212121ijkjikjkkikjijidbaRzyRyxYyRRzxcZYRYXR有,令令factors) ( have we,set finite aon relation a and , 2For nMMMMARnRRRRn2112RRRRMMM关系的性质:自反性关系的性质:自反性 reflexivityl集合A上的关系 R 是:l自反的 reflexive:定义为:对所有的 aA, (a,a)Rl反自反的 irreflexive:定义为:对所有的aA, (a,a)R注意区分”非”与”反”l设 A=1,2,3
11、, RAAl(1,1), (1,3), (2,2), (2,1), (3,3) 是自反的l(1,2), (2,3), (3,1) 是反自反的l(1,2), (2,2), (2,3),( 3,1) 既不是自反的,也不是反自反的自反性与恒等关系自反性与恒等关系lR 是 A 上的自反关系 IAR, 这里IA是集合A上的恒等关系,即: IA=(a,a)| aA 直接根据定义证明:l 只需证明:对任意(a,b) ,若(a,b)IA, 则(a,b)Rl 只需证明:对任意的a, 若aA, 则(a,a)R自反关系的有向图和自反关系的有向图和0-1矩阵矩阵abcA=a,b,c110111001RM关系的性质:对
12、称性关系的性质:对称性 Symmetryl集合A上的关系R是: l对称的 symmetric:定义为:若 (a,b)R, 则 (b,a)Rl反对称的 anti-:定义为:若(a,b)R 且(b,a)R ,则a=bl设 A=1,2,3, RAAl(1,1),(1,2),(1,3),(2,1),(3,1),(3,3) 是对称的l(1,2),(2,3),(2,2),(3,1) 是反对称的理解对称性理解对称性l关系R满足对称性:对任意(a,b),若 (a,b)R, 则 (b,a)Rl注意:是对称关系。l反对称并不是对称的否定: ( 令:A=1,2,3, RAA)l(1,1),(2,2) 既是对称的,也
13、是反对称的l是对称关系,也是反对称关系。),(, RRabRbaba是对称的关系对称性与逆关系对称性与逆关系lR 是集合A上的对称关系 R-1=R l证明一个集合等式R-1=R l若(a,b)R-1, 则(b,a)R, 由R的对称性可知(a,b)R, 因此:R-1R; 同理可得:RR-1; l 只需证明:对任意的(a,b) 若(a,b)R, 则(b,a)R对称关系的对称关系的有向图和有向图和0-1矩阵矩阵110101011RMabcA=a,b,c关系的性质:传递性关系的性质:传递性 transitivityl集合A上的关系R是l传递的 transitive: 若 (a,b)R, (b,c)R,
14、 则 (a,c) Rl设 A=1,2,3, RAAl(1,1),(1,2),(1,3),(2,1),(2,2),(2,3),(3,3) 传递的l(1,2),(2,3),(3,1) 是非传递的l(1,3)? l?),(),(),)(,( RRcaRcbRbacba是传递关系关系传递性与关系的乘幂传递性与关系的乘幂 l关系的复合(乘)运算满足结合律,可以用 Rn 表示R R R (n是正整数) l命题:(a,b)Rn 当且仅当:存在t1,t2,tn-1A, 满足:(a,t1),(t1,t2),(tn-2,tn-1),(tn-1,b)R。l对n=1用数学归纳法:n=1, trivial. 奠基n=2
15、,直接由关系复合的定义可得;归纳基于:Rn=Rn-1 Rl集合A上的关系R是传递关系 R2Rl必要性:任取(a,b) R2 ,根据上述命题以及R的传递性可得(a,b)Rl充分性: 若(a,b)R, (b,c)R, 则(a,c)R2, 由R2R可得: (a,c)R,则 R是传递关系传递关系的有向图和传递关系的有向图和0-1矩阵矩阵abcA=a,b,c110111101RM一些常用关系的性质一些常用关系的性质= | 3E自反自反 反自反反自反 对称对称 反对称反对称 传递传递 关系运算与性质的保持关系运算与性质的保持自反自反反自反反自反对称对称反对称反对称传递传递R1-1 R1R2 R1R2 R1
16、R2 小结小结l关系:笛卡尔积的子集l关系的运算l集合运算;复合运算;逆l0-1矩阵运算l关系的性质lreflexivity, ir-; symmetry, anti-; transitivity l图特征;矩阵特征作业作业l教材内容:Rosen 2.1.3、8.1 节 8.3节l课后习题:l见课程主页函数及其运算函数及其运算离散数学集合论南京大学计算机科学与技术系回顾回顾l关系:笛卡尔积的子集l关系的运算l集合运算;复合运算;逆l0-1矩阵运算l关系的性质lreflexivity, ir-; symmetry, anti-; transitivity l图特征;矩阵特征提要提要l函数的定义l
17、子集的像l单射与满射l反函数l函数的复合l函数加法与乘法函数函数(function)的定义的定义l设 A 和 B 为非空集合,从集合A到B的函数 f 是对元素的一种指派,对A的每个元素恰好指派B的一个元素。记作 f :AB。lWell defined(良定义)lf :AB:函数的型构lf 的定义域(domain)是A,f 的伴域(codomain)是Bl如果 f 为A中元素a指派的B中元素为b,就写成 f(a)=b。此时,称 b是a的像,而a是b的一个原像。lA中元素的像构成的集合称为f的值域 range ( f的像 image)。l函数也称为映射(mapping)或变换(transforma
18、tion)函数的集合定义函数的集合定义函数的集合定义(续)函数的集合定义(续)函数举例函数举例l下取整函数 x: R Zl函数 f 的图像: (a, b) | aA f(a)=bJava Programint floor(float real) xyfloor: float int 函数举例函数举例l某课程成绩某课程成绩ProgramCourseGrade grade(StudentName sname,CourseName cname) Function:Grade: StudentName CourseName CourseGrade 姓名姓名课程课程成绩成绩张明离散数学A李宁程序设计B王
19、琴数据结构A函数原型函数型构(signature)函数举例函数举例l设A为非空集合,A上的 恒等函数A:AA定义为lA(x)=x,xAl设U为非空集合,对任意的AU, 特征函数A:U0,1 定义为:lA(x)=1,xAlA(x)=0,xU-A函数的集合函数的集合函数函数(function)的相等的相等l函数相等 f=g ifldom(f)=dom(g)lcodom(f)=codom(g)lx(xdom(f) f(x)=g(x)函数的相等函数的相等子集在函数下的像子集在函数下的像l设 f 是从集合A到B的函数,S 是A的一个子集。S 在 f 下的像,记为f(S),定义如下:lf (S)= t |
20、 sS (t= f (s) l备注:f (A) 即为 f 的值域。Bf(S):TASfS的像和逆像的像和逆像S的像:Tabcb的逆像T的逆像是什么?并集的像并集的像l设函数 f: AB,且X,Y是A的子集,则f (XY) = f(X)f (Y) l证明:lf (XY) f(X)f (Y) 对任意的t,若tf (XY) , 则存在sXY, 满足f(s)=t; 假设sX, 则tf(X), 假设sY, 则tf(Y), tf (X)f(Y) lf(X)f (Y) f (XY) 对任意的t,若tf (X)f(Y) 情况1:tf (X), 则存在sX XY, 满足f(s)=t, t f (XY) 情况2:
21、 tf (Y), 同样可得t f (XY) t f (XY) 交集的像交集的像l设函数 f : AB,且X,Y是A的子集,则lf (XY) f(X)f (Y)ABXYa1a2cf在f(X)f (Y)中,但不在f (XY)中函数性质函数性质l:AB是单射单射(一对一的)linjection, injective function, one-to-one functionlx1, x2A, 若x1x2,则(x1) (x2)l/等价的说法:x1, x2A, 若(x1) =(x2),则x1=x2l/另一种等价的说法?l:AB是满射满射(映上的)lsurjection, surjective funct
22、ion, onto functionlyB, xA, 使得(x)=yl/等价的说法:f (A)=Bl:AB是双射双射(一一对应)lbijection, bijective function, one-to-one correspondencel满射+单射函数性质的证明函数性质的证明l判断:RRRR, () = 的性质l单射?l令() = ()lx1+y1=x2+y2且x1-y1=x2-y2,易见: x1=x2且y1=y2l=l满射?l任取 RR,总存在,使得l()=函数性质的证明函数性质的证明l设A有限集合,f 是从A到A的函数。f 是单射当且仅当 f 是满射。反函数反函数l设f 是从A到B的一一对应,f 的反函数是从B到A的函数,它指派给B中元素b的是A中满足f(a)=b的(唯一的)a。 f 的反函数记作f -1。lf(a)=b 当且仅当 f -1(b)=al任何函数都有反函数吗?l例子l:RRRR, () = lf -1:RRRR, -1 () = 函数的复合函数的复合 l设g是从A到B的函数,f是从B到C的函数,f和g的复合用f g表示,定义为:l(f g) (x)= f(g(x), xAaAg(a)BCf(g(a)gff g复合运算的性质复合运算的性质l函数的复合满足结合律l(f g) h = f (g h)l满射的复合是满射l单射的复合是单射 l双射的
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 三年级数学角度认识教学设计方案
- 电气工程施工方案与技术交底
- 药材种植与可持续利用-洞察及研究
- 互动性增强路径-洞察及研究
- 物联网与电信业务融合-洞察及研究
- 智能化脚手架应用研究-洞察及研究
- AR技术提升铁路客流量管理-洞察及研究
- 试点方案在促进全球健康平等中的潜力与挑战研究-洞察及研究
- 管理安全方案
- 生产安全培训方案
- 《红星照耀中国》中考题集(含答案解析)
- 应聘妇女主任的简历
- 非遗蜀绣的传承发展路径研究
- 河北农业大学分子生物学题库(带答案)
- 公共管理学:理论、实践与方法 课件全套 汪大海 第1-18章 公共管理与公共管理学- 公共管理的变革
- 瑞幸咖啡副店长认证考试题库
- 某校水、电、气、暖安全管理制度(4篇)
- 【MOOC】食物营养与食品安全-中南大学 中国大学慕课MOOC答案
- 【课件】第21课《小圣施威降大圣》课件2024-2025学年统编版语文七年级上册
- 桑叶种植技术
- 透析器反应的应急处理
评论
0/150
提交评论