《第四部分二元关系和函数教学课件.ppt》由会员分享，可在线阅读，更多相关《第四部分二元关系和函数教学课件.ppt（50页珍藏版）》请在三一办公上搜索。
1、1,第四章 二元关系和函数,2,本章主要内容:,集合的笛卡尔积与二元关系关系的运算关系的性质关系的闭包等价关系和偏序关系函数的定义和性质函数的复合和反函数,3,4.1 集合的笛卡儿积与二元关系,定义4.1 由两个元素x和y(允许x=y)按一定的顺序排列成的二元组叫做一个有序对(也称序偶),记作,其中x是它的第一元素,y是它的第二元素。平面直角坐标系中点的坐标就是有序对,例如,(1,1),(1,1),都代表坐标系中不同的点。,4,有序对的特点：1.当xy时,。2.两个有序对相等,即 的充分必要条件是xu且yv。,5,定义4.2 一个有序n元组(n3)是一个有序对,其中第一个元素是一个有序n1元组
2、,一个有序n元组记作,即,xn 例如,空间直角坐标系中点的坐标,等都是有序3元组。n维空间中点的坐标或n维向量都是有序n元组。,6,定义4.3 设A,B为集合,用A中元素为第一元素,B中元素为第二元素,构成有序对,所有这样的有序对组成的集合叫做A和B的笛卡儿积,记作AB。符号化表示为 AB(x,y)|xAyB.例如,Aa,b,B0,1,2,则 AB,；BA,。,7,如果A中有m个元素,B中有n个元素,则AB和BA中都有多少个元素?mn个若AB,则有xA和yB。若AB,则有xA或者y B.,8,笛卡儿积运算的性质:1.若A,B中有一个空集,则它们的笛卡儿积是空集,即 BB 2.当AB且A,B都不
3、是空集时,有 ABBA。所以,笛卡儿积运算不适合交换律。3.当A,B,C都不是空集时,有(AB)CA(BC).所以,笛卡儿积运算不适合结合律。,9,4.笛卡儿积运算对或运算满足分配律即 A(BC)(AB)(AC)；(BC)A(BA)(CA)；A(BC)(AB)(AC)；(BC)A(BA)(CA)。,10,证明 A(BC)(AB)(AC)证明 对于任意的,A(BC)xAyBC xA(yByC)(xAyB)(xAyC)ABAC(x,y)(AB)(AC).所以 A(BC)(AB)(AC)。,11,例4.1 设A=1,2,求P(A)A 解 P(A)A,1,2,1,21,2,12,例4.2 设A,B,C
4、,D为任意集合,判断以下等式是否成立,说明为什么。(1)(AB)(CD)(AC)(BD)；(2)(AB)(CD)(AC)(BD)；(3)(AB)(CD)(AC)(BD)；(4)(AB)(CD)(AC)(BD)。,13,解.(1)成立.因为对于任意的,(AB)(CD)xAByCD xAxB yCyD AC BD(AC)(BD)(2)不成立。举一反例如下：若AD,BC1 则有：(AB)(CD)BC,(AC)(BD)。(3)和(4)都不成立,14,例4.3 设A,B,C,D为任意集合,判断以下命题的真假.(1)若AC且BD,则有ABCD。(2)若ABCD,则有AC且BD.解(1)命题为真。请思考：为
5、什么？(2)命题为假.当AB时,或者A且B时,该命题的结论是成立的。但是当A和B之中仅有一个为时,结论不一定成立,例如,令ACD,B1,这时ABCD,但BD。,15,定义4.4 设A1,A2,An是集合(n2),它们的n阶笛卡儿积,记作A1A2An,其中 AlA2An|x1Alx2A2xnAn。例如:A=a,b,则A3=,16,二元关系Relation,所谓二元关系就是在集合中两个元素之间的某种相关性.例如,甲、乙、丙三个人进行乒乓球比赛,如果任何两个人之间都要赛一场,那么共要赛三场。假设三场比赛的结果是乙胜甲、甲胜丙、乙胜丙,这个结果可以记作,其中表示x胜y。它表示了集合甲,乙,丙中元素之间
6、的一种胜负关系.,17,例子.有A,B,C三个人和四项工作,已知A可以从事工作,B可以从事工作,C可以从事工作,。那么人和工作之间的对应关系可以记作 R,。这是人的集合A,B,C到工作的集合,之间的关系。,18,定义4.5 如果一个集合为空集或者它的元素都是有序对,则称这个集合是一个二元关系,一般记作R。对于二元关系R,如果R,则记作xRy；如果R,则记作,19,定义4.6 设A,B为集合,AB的任何子集所定义的二元关系称作从A到B的二元关系,特别当AB时,则叫做A上的二元关系。关系RAB,R is a relation from A to B.RAA,R is a relation on A
7、.A上有多少个不同的二元关系?|A|=n|AA|=n2|P(AA)|=2n2每一个子集代表一个A上的关系,共2n2个关系.,20,对于任何集合A都有3种特殊的关系:其中之一就是空集,称做空关系。另外两种就是全域关系EA和恒等关系IA。定义4.7 对任何集合A,EAxAyAAA。IAxA。例如：A=0,1,2,则 EA,IA,2,2)。,21,常用的关系:小于等于关系、整除关系,例如:设A为实数集R的某个子集,则A上的小于等于关系定义为 LAx,yAxy设B为正整数集Z的某个子集,则B上的整除关系定义为 DBx,yBxy.,22,例如:A=4,0.5,-1,B=1,2,3,6,则,LA,.,DB
8、,.,23,例4.4 设Aa,b,R是P(A)上的包含关系,R|x,yP(A)xy,则有P(A),a,b,A。R,.,24,有穷集A上的关系R,可用关系矩阵和关系图给出。设A1,2,3,4,A上的关系R,。R的关系矩阵和关系图如图,关系矩阵和关系图,25,26,关系矩阵和关系图,设V是顶点的集合,E是有向边的集合,令VAx1,x2,xn,如果xiRxj,则有向边E.那么G就是R的关系图。设Ax1,x2,xn,R是A上的关系,则R的关系矩阵可表示为：,27,4.2 关系的运算,关系R的定义域,值域和域关系F的逆关系F与G的合成关系F在集合A上的限制集合A在关系F下的象关系R的n次幂,28,定义4
9、.8 关系R的定义域 domR,值域ranR和域fldR分别是 domRxy(R)ranRy|x(R)fldRdomRranR。domR就是R的所有有序对的第一个元素构成的集合,ranR就是R的所有有序对的第二个元素构成的集合.例:实数集R上的关系S=|x,yRx2+y2=1,domS=ranS=fldS=1,1.,29,例4.5 下列关系都是整数集Z上的关系,分别求出它们的定义域和值域,(1)R1x,yZxy；(2)R2x,yZx2+y2=1；(3)R3x,yZy2x；(4)R4x,yZ x y=3。解(1)domR1ranR1Z.(2)R2,domR2ranR20,1,1.(3)domR3
10、Z ranR32z|zZ,即偶数集(4)domR4ranR4-3,3.,30,从A到B的某些关系R的图解方法(不是R的关系图)1.用封闭的曲线表示R的定义域(或集合A)和值域(或集合B).2.从x到y画一个箭头,如果R,31,32,逆、合成、限制和象,定义4.9 设F,G为任意的关系,A为集合,则(1)F的逆记作F-1 F-1|yFx.(2)F与G的合成记作FG,FG,z(xGzzFy)(3)F在A上的限制记作 F A F A|xFyxA.(4)A在F下的象记作FA,FAran(F A),33,例4.6 设F,G是N上的关系,其定义为 Fx,yNyx2 Gx,yNyx1。解：1)2)对任何的x
11、N有则 所以,34,由这个例子不难看出,合成运算不是可交换的,即对任何关系F,G,一般说来FGGF.,35,定理4.1 设F,G,H是任意的关系,则有(3)(FG)HF(GH)(4)怎样证明?,关系的基本运算的主要性质,36,定理4.2 设F,G,H为任意的关系,则有(1)F(GH)=FGFH(2)(GH)F=GF HF(3)F(GH)FGFH(4)(GH)F GF HF怎样证明?,37,定义4.10 设R为A上的关系,n为自然数,则R的n次幂规定如下：,R0=IAR1=R0R=R R0,38,39,在有穷集A上给定了关系R和自然数n,求Rn的方法:,1.集合运算:依据定义2.关系矩阵:用关系
12、矩阵M表示关系R,计算MM,在两个矩阵相乘时,第i行第j列的元素rij满足下式(i,j=1,2,3,4)rij=ri1 r1j+ri2 r2j+ri3 r3j+ri4 r4j这里的加法+是逻辑加,即0+0=0,0+1=1,1+0=1,1+1=13.关系图:对R的关系图G中的任何一个结点x,考虑从x出发的长为n的路径,如果路径的终点是y,则在Rn的关系图中有一条从x到y的有向边.,40,定理4.3 设R为A上的关系,m,n是自然数,则下面的等式成立.,41,42,4.3 关系的性质,设R是A上的关系,R的性质主要有以下5种：自反性、反自反性、对称性、反对称性传递性。,43,44,判断下列关系的性
13、质,集合A上的全域关系:自反的、对称的和传递的恒等关系自反的、对称的和传递的.整除关系自反的、反对称的和传递的小于等于关系自反的、反对称的和传递的幂集上的包含关系自反的、反对称的和传递的,45,设A为非空集合:1.A上的关系可以是自反的,反自反的,或者既不是自反的也不是反自反的.例如:Q=1,2,3,令A=,IQ RB=,IQR=C=,IQR且IQR,46,2.A上的关系可以是对称的,反对称的,或者既是对称的又是反对称的,既不是对称的也不是反对称的.例如:Q=1,2,3,令A=,R-1=RB=,R R-1 IQ C=R IQ D=,RR R是什么关系?,47,例4.9 试判断图4.5中关系的性质。,48,设R1,R2是A上的关系,如果经过某种运算后仍保持原来的性质,则在相对应的格内划,否则划。,49,例：设R1,R2为A上的对称关系,证明R1R2也是A上的对称关系。证明：对于任意的 R1R2 R1 R2 R1 R2 R1 R2所以,R1R2在A上是对称的。例:R1,R2 是A上的反对称关系,A=x1,x2,R1=,R2=,R1 R2=,不是A上的反对称关系.,50,作业,证明表4.2的反对称性和传递性P105 4.1 4.2 4.3 4.4,
