1、关系及其运算关系及其运算离散数学集合论南京大学计算机科学与技术系1感谢你的观看2019年8月23回顾回顾l集合的基本概念l集合及其描述l集合相等、子集关系l幂集、笛卡尔乘积l集合运算l交并补、广义交、广义并l集合恒等式l集合相关命题的证明方式2感谢你的观看2019年8月23提要提要l关系的定义l关系的表示l关系的运算l0-1矩阵运算l关系的性质3感谢你的观看2019年8月23有序对（有序对（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,
2、左边=x,而vx,右边x;(2)若xy,则必有x,y=u,v,但y既非u,又非v,矛盾。4感谢你的观看2019年8月23笛卡尔乘积（笛卡尔乘积（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|5感谢你的观看2019年8月23例题例题lA=1,2,(A)A=?l|A|=m,|B|=n,|AB|=?6感谢你的观看2019年8月23（二元）关系的定义（二元）关系的定义l若A,B是集合,从A到B的一个关系是AB的一个子集.l
3、集合,可以是空集l集合的元素是有序对l关系意味着什么？l两类对象之间建立起来的联系！7感谢你的观看2019年8月23从从A到到B的二元关系的二元关系l笛卡尔乘积的子集l“从A到B的关系”R；RABl若A=B：称为“集合A上的（二元）关系”l例子l常用的数学关系：不大于、整除、集合包含等 l网页链接、文章引用、相互认识8感谢你的观看2019年8月23特殊的二元关系特殊的二元关系 l集合A上的空关系:空关系即空集l全域关系 EA:EA=(x,y)|x,yA l恒等关系 IA:IA=(x,x)|xA 9感谢你的观看2019年8月23函数是一种特殊的关系函数是一种特殊的关系 l函数 f:ABlR=(x
4、,f(x)|xA 是一个从A到B的一个关系10感谢你的观看2019年8月23关系的表示关系的表示 假设A=a,b,c,d,B=,/假设为有限集合l集合表示:R1=(a,),(b,),(c,),(c,)0-1矩阵 有向图000101001010abcd adcb AB11感谢你的观看2019年8月23二元关系和有向图二元关系和有向图关系 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的通路12感谢你的观看2019年8月
5、23关系的运算（关系的运算（1）l关系是集合,所有的集合运算对关系均适用l例子:l自然数集合上:“”“=”等同于 “”l自然数集合上:“”“”等同于“=”l自然数集合上:“”等同于13感谢你的观看2019年8月23关系的运算（关系的运算（2）l与定义域和值域有关的运算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
6、、RB、R(1)和R(2)14感谢你的观看2019年8月23关系的运算（关系的运算（3）l逆运算lR-1=(x,y)|(y,x)Rl注意:如果R是从A到B的关系,则R-1是从B到A的。l(R-1)-1=Rl例子：(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-115感谢你的观看2019年8月23关系的关系的运算（运算（4）l关系的复合（合成,Composition）设 R1AB,R2BC,R1与R2的复合（合成）,记为 R2 R1,定义如下：R2 R1=(a,c)AC|bB(a,
7、b)R1(b,c)R2)16感谢你的观看2019年8月23复合关系的图示复合关系的图示l(a,c)R2 R1 当且仅当 aA,cC,且存在bB，使得(a,b)R1,(b,c)R2abcR1R217感谢你的观看2019年8月23关系的复合运算：举例关系的复合运算：举例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)18感谢你的观看2019年8月23关系的复合运算的性质（关系的复合运算的性
8、质（1）l结合律l给定R1AB,R2BC,R3CD,则：(R3 R2)R1=R3 (R2 R1)l证明左右两个集合相等.19感谢你的观看2019年8月23关系的复合运算的性质（关系的复合运算的性质（2）l复合关系的逆关系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 20感谢你的观看2019年8月23关系的复合运算的性质（关系的复合运算的性质（3）l对集合并运算满足分配律l给定FAB
9、,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),G=(s,b),H=(t,b);GH=,(G F)(H F)=(a,b)21感谢你的观看2019年8月230-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.11011011110110101010001
10、110)11(kjikbak22感谢你的观看2019年8月23关系运算的矩阵关系运算的矩阵法（法（1）l命题2121RRRRMMM2121RRRRMMM2112RRRRMMM1101101111011010101000111023感谢你的观看2019年8月23证明：111),(,1MMDMCMBMA;:;:2112RRR1R2RR212121ijkjikjkkikjijidbaRzyRyxYyRRzxcZYRYXR有，令令factors)(have we,set finite aon relation a and,2For nMMMMARnRRRRn2112RRRRMMM24感谢你的观看201
11、9年8月23关系的性质：自反性关系的性质：自反性 reflexivityl集合A上的关系 R 是:l自反的 reflexive：定义为：对所有的 aA,(a,a)Rl反自反的 irreflexive：定义为：对所有的aA,(a,a)R注意区分”非”与”反”l设 A=1,2,3,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)既不是自反的，也不是反自反的25感谢你的观看2019年8月23自反性与恒等关系自反性与恒等关系lR 是 A 上的自反关系 IAR,这里IA是集合A上的恒等
12、关系,即:IA=(a,a)|aA 直接根据定义证明：l 只需证明：对任意(a,b)，若(a,b)IA,则(a,b)Rl 只需证明：对任意的a,若aA,则(a,a)R26感谢你的观看2019年8月23自反关系的有向图和自反关系的有向图和0-1矩阵矩阵abcA=a,b,c110111001RM27感谢你的观看2019年8月23关系的性质：对称性关系的性质：对称性 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,
13、3),(2,1),(3,1),(3,3)是对称的l(1,2),(2,3),(2,2),(3,1)是反对称的28感谢你的观看2019年8月23理解对称性理解对称性l关系R满足对称性：对任意(a,b)，若(a,b)R,则(b,a)Rl注意：是对称关系。l反对称并不是对称的否定:(令：A=1,2,3,RAA)l(1,1),(2,2)既是对称的，也是反对称的l是对称关系，也是反对称关系。),(,RRabRbaba是对称的关系29感谢你的观看2019年8月23对称性与逆关系对称性与逆关系lR 是集合A上的对称关系 R-1=R l证明一个集合等式R-1=R l若(a,b)R-1,则(b,a)R,由R的对称
14、性可知(a,b)R,因此：R-1R;同理可得：RR-1;l 只需证明：对任意的(a,b)若(a,b)R,则(b,a)R30感谢你的观看2019年8月23对称关系的对称关系的有向图和有向图和0-1矩阵矩阵110101011RMabcA=a,b,c31感谢你的观看2019年8月23关系的性质：传递性关系的性质：传递性 transitivityl集合A上的关系R是l传递的 transitive:若(a,b)R,(b,c)R,则(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)是非传递的
15、l(1,3)?l?),(),(),)(,(RRcaRcbRbacba是传递关系关系32感谢你的观看2019年8月23传递性与关系的乘幂传递性与关系的乘幂 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,直接由关系复合的定义可得；归纳基于：Rn=Rn-1 Rl集合A上的关系R是传递关系 R2Rl必要性：任取(a,b)R2,根据上述命题以及R的传递性可得(a,b)Rl充
16、分性：若(a,b)R,(b,c)R,则(a,c)R2,由R2R可得：(a,c)R，则 R是传递关系33感谢你的观看2019年8月23传递关系的有向图和传递关系的有向图和0-1矩阵矩阵abcA=a,b,c110111101RM34感谢你的观看2019年8月23一些常用关系的性质一些常用关系的性质=|-1|3|-1|。s s不是反对称的，如不是反对称的，如-3|2|-3|2|，2|-3|2|-3|，但，但-32-32。s s不是可传递的，不是可传递的，100|-101|100|-101|，-101|2|-101|2|，但，但100|2|100|2|习题举例一习题举例一37感谢你的观看2019年8月
17、2338感谢你的观看2019年8月2339感谢你的观看2019年8月2340感谢你的观看2019年8月2341感谢你的观看2019年8月23小结小结l关系：笛卡尔积的子集l关系的运算l集合运算；复合运算；逆l0-1矩阵运算l关系的性质lreflexivity,ir-;symmetry,anti-;transitivity l图特征；矩阵特征42感谢你的观看2019年8月23作业作业l教材内容：Rosen 2.1.3、8.1 节 8.3节l课后习题：l见课程主页43感谢你的观看2019年8月23函数及其运算函数及其运算离散数学集合论南京大学计算机科学与技术系44感谢你的观看2019年8月23回顾
18、回顾l关系：笛卡尔积的子集l关系的运算l集合运算；复合运算；逆l0-1矩阵运算l关系的性质lreflexivity,ir-;symmetry,anti-;transitivity l图特征；矩阵特征45感谢你的观看2019年8月23提要提要l函数的定义l子集的像l单射与满射l反函数l函数的复合l函数加法与乘法46感谢你的观看2019年8月23函数函数(function)的定义的定义l设 A 和 B 为非空集合，从集合A到B的函数 f 是对元素的一种指派，对A的每个元素恰好指派B的一个元素。记作 f:AB。lWell defined(良定义)lf:AB：函数的型构lf 的定义域（domain）是
19、A，f 的伴域（codomain）是Bl如果 f 为A中元素a指派的B中元素为b，就写成 f(a)=b。此时，称 b是a的像，而a是b的一个原像。lA中元素的像构成的集合称为f的值域 range（f的像 image）。l函数也称为映射(mapping)或变换(transformation)47感谢你的观看2019年8月23函数的集合定义函数的集合定义48感谢你的观看2019年8月23函数的集合定义（续）函数的集合定义（续）49感谢你的观看2019年8月23函数举例函数举例l下取整函数 x:R Zl函数 f 的图像:(a,b)|aA f(a)=bJava Programint floor(flo
20、at real)xyfloor:float int 50感谢你的观看2019年8月23函数举例函数举例l某课程成绩某课程成绩ProgramCourseGrade grade(StudentName sname，CourseName cname)Function：Grade:StudentName CourseName CourseGrade 姓名姓名课程课程成绩成绩张明离散数学A李宁程序设计B王琴数据结构A函数原型函数型构(signature)51感谢你的观看2019年8月23函数举例函数举例l设A为非空集合，A上的 恒等函数A:AA定义为lA(x)=x，xAl设U为非空集合，对任意的AU,特
21、征函数A:U0,1 定义为：lA(x)=1，xAlA(x)=0，xU-A52感谢你的观看2019年8月23函数的集合函数的集合53感谢你的观看2019年8月23函数函数(function)的相等的相等l函数相等 f=g ifldom(f)=dom(g)lcodom(f)=codom(g)lx(xdom(f)f(x)=g(x)54感谢你的观看2019年8月23函数的相等函数的相等55感谢你的观看2019年8月23子集在函数下的像子集在函数下的像l设 f 是从集合A到B的函数，S 是A的一个子集。S 在 f 下的像，记为f(S)，定义如下：lf(S)=t|sS(t=f(s)l备注：f(A)即为 f
22、 的值域。56感谢你的观看2019年8月23Bf(S):TASfS的像和逆像的像和逆像S的像:Tabcb的逆像T的逆像是什么？57感谢你的观看2019年8月23并集的像并集的像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：tf(Y),同样可得t f(XY)t f(XY)58感
23、谢你的观看2019年8月23交集的像交集的像l设函数 f:AB，且X，Y是A的子集，则lf(XY)f(X)f(Y)ABXYa1a2cf在f(X)f(Y)中，但不在f(XY)中59感谢你的观看2019年8月23函数性质函数性质l:AB是单射单射（一对一的）linjection,injective function,one-to-one functionlx1,x2A,若x1x2，则(x1)(x2)l/等价的说法：x1,x2A,若(x1)=(x2)，则x1=x2l/另一种等价的说法？l:AB是满射满射（映上的）lsurjection,surjective function,onto functio
24、nlyB,xA,使得(x)=yl/等价的说法：f(A)=Bl:AB是双射双射（一一对应）lbijection,bijective function,one-to-one correspondencel满射+单射60感谢你的观看2019年8月23函数性质的证明函数性质的证明l判断:RRRR,()=的性质l单射？l令()=()lx1+y1=x2+y2且x1-y1=x2-y2,易见：x1=x2且y1=y2l=l满射？l任取 RR，总存在,使得l()=61感谢你的观看2019年8月23函数性质的证明函数性质的证明l设A有限集合，f 是从A到A的函数。f 是单射当且仅当 f 是满射。62感谢你的观看20
25、19年8月23反函数反函数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()=63感谢你的观看2019年8月23函数的复合函数的复合 l设g是从A到B的函数，f是从B到C的函数，f和g的复合用f g表示，定义为：l(f g)(x)=f(g(x)，xAaAg(a)BCf(g(a)gff g64感谢你的观看2019年8月23复合运算的性质复合运算的性质l函数的复合满足结合律l(f g)h=
26、f (g h)l满射的复合是满射l单射的复合是单射 l双射的复合是双射 l设f 是从A到B的双射l f-1 f=Alf f-1=B65感谢你的观看2019年8月23复合运算复合运算66感谢你的观看2019年8月23复合运算复合运算67感谢你的观看2019年8月23但是但是 l若f g是满射，能推出f 和g是满射吗？lf一定是满射，g不一定是满射。l若f g是单射，能推出f 和g是单射吗？lg一定是单射，f 不一定是单射。68感谢你的观看2019年8月23gfABC69感谢你的观看2019年8月23gfABC70感谢你的观看2019年8月23函数的加法、乘法函数的加法、乘法l设f和g是从A到R的
27、函数，那么 f+g 和 f g也是从A到R的函数，其定义为l(f+g)(x)=f(x)+g(x)，xAlf g(x)=f(x)g(x)，xA71感谢你的观看2019年8月23递增（递减）函数递增（递减）函数l设f的定义域和伴域都是实数(或其子集)，lf是递增的lx y(xy f(x)f(y)lf是严格递增的lx y(xy f(x)f(y)72感谢你的观看2019年8月23练习练习73感谢你的观看2019年8月23练习练习74感谢你的观看2019年8月23一个有趣的例子一个有趣的例子l自然数1,2,3,n2+1的任何一种排列中，必然含一个长度不小于n+1的严格递增链或严格递减链。l7,4,3,5
28、,2,1,9,8,6,10/10,3,2,6,4,7,5,9,1,8l在所给的序列中，以k开始的严格递增序列长度为I(k),以k开始的严格递减序列长度为D(k)。lf:k (I(k),D(k),k1,2,n2+1lf(7)=(3,5),f(4)=(4,4),f(3)=(4,3),f(5)=(3,3),f(2)=(3,2),f(1)=(3,1)lf(9)=(2,3),f(8)=(2,2),f(6)=(2,1),f(10)=(1,1)lf是单射：对于k1k2，如果k1排在k2前面，则I(k1)I(k2)，如果k2排在k1前面，则D(k2)D(k1)。l反证法：给定任一种排列，假设严格递增与递减序列最大长度均不大于n：l f的值域最多有n2个元素lf不可能是单射75感谢你的观看2019年8月23作业作业l教材2.3l见课程主页76感谢你的观看2019年8月23
