《CH二元关系和函数二元关系的基本概念.pptx》由会员分享，可在线阅读，更多相关《CH二元关系和函数二元关系的基本概念.pptx（44页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、回顾第1页/共44页用推理规则证明：|=A第2页/共44页证明：设论域D=a,b,c，求证：第3页/共44页第4页/共44页第第4 4章二元关系和函数章二元关系和函数本章学习1.1.集合的笛卡尔积2.2.关系及其表示3.3.关系的运算4.4.关系的性质5.5.关系的闭包6.6.等价关系和偏序关系7.7.函数的定义和性质8.8.函数的复合和反函数第5页/共44页今日内容集合的笛卡尔积关系及其表示关系的运算第6页/共44页笛卡尔乘积定义：由两个元素x x和y y（允许x=yx=y）按一定的顺序排列成的二元组叫做一个有序对（也称序偶），记做，其中x x是它的第一元素，y y是它的第二元素。平面直角坐
2、标系中点的坐标就是序偶。例如，,.都代表坐标系中不同的点。第7页/共44页序偶的特点（与集合的不同之处）当xyxy时，两个有序对相等，即=的充要条件是x=u,x=u,且y=vy=v第8页/共44页定义（有序n n元组）:一个有序n n元组（n n3 3）是一个有序对，记做x,其中第一个元组是一个有序n-1n-1元组，即x=,x,xn,n,例如，空间直角坐标系中点的坐标 1,-1,31,-1,3,2,4,02,4,0等都是有序3 3元组。N N维空间中点的坐标或n n维向量都是有序n n元组第9页/共44页定义（笛卡儿积）:设A A，B B为集合，用A A中元素作为第一元素，B B中元素作为第二
3、元素，构成序偶。所有这样的序偶组成的集合叫做A A和B B的笛卡儿积，记作A AB B。符号化表示为 A AB=|xB=|x A A y y BB 例:若A=a,b,B=0,1,2,A=a,b,B=0,1,2,则 A AB=,B=,B BA=,A=,第10页/共44页笛卡儿积中元素的个数如果A A中有m m个元素,B,B中有n n个元素,则A AB B和B BA A中都有mnmn个元素第11页/共44页笛卡儿积运算的性质若A,BA,B中有一个空集,则它们的笛卡儿积是空集.即 B=A B=A =笛卡儿积运算不适合交换律:当ABAB且A,BA,B都不是空集时,有ABBAABBA笛卡儿积运算不适合结
4、合律:当A,B,CA,B,C都不是空集时,有(AB)CA(BC)(AB)CA(BC)设xA,yB,zC,xA,yB,zC,那么,z(AB),z(AB)C,x,A(BC)C,x,A(BC)。一般情况下,z x,z x,所以,(AB)CA(BC),(AB)CA(BC)第12页/共44页笛卡儿积运算对 或 运算满足分配律，即 A (BA (B C)=(A B)C)=(A B)(A C)(A C)(B(B C)A =(B A)C)A =(B A)(C A)(C A)A (B A (B C)=(A C)C)=(A C)(A C)(A C)(B(B C)A =(B A)C)A =(B A)(C A)(C
5、A)证明A (BA (B C)=(A B)C)=(A B)(A C)(A C)对于任何的x,yx,y，x,yx,y A (B A (B C)C)x A x A yByB C C x A x A (y B (y B y C)y C)(x A (x A y B)y B)(x A (x A yC)yC)x,yx,y A B A B x,yx,y A C A C x,yx,y(A B)(A B)(A (A C)C)所以 A (BA (B C)=(A B)C)=(A B)(A(A C)C)第13页/共44页例例:设设A=1A=1，22，求，求P P（A A）AA 解解:P P（A A）AA =，11，2
6、2，1,2,11,2,1，22 =,1,2,，22，2 2，11，22，1 1,1,1，22，2 2 第14页/共44页定义 (n n阶笛卡儿积)设A A1 1,A,A2 2,An,An是n n个集合(n2)(n2)。它们的n n阶笛卡儿积 A A1 1 A A2 2 A An n=x x1 1,x,x2 2,x,xn n|x|x1 1AA1 1xx2 2AA2 2xxn nAAn n 当A A1 1=A=A2 2=A=An n=A=A时，可将它们的n n阶笛卡儿积 简记为A An n例如，A=aA=a，bb，则 A A3 3=a a，a a，a a，a a，a a，b b，a a，b b，a
7、 a，a a，b b，b b，b b，a a，a a，b b，a a，b b，b b，b b，a a，b b，b b，b b 第15页/共44页关系及其表示 什么是关系什么是关系关系的表示关系的表示第16页/共44页所谓所谓二元关系二元关系就是在集合中两个元素之间的就是在集合中两个元素之间的某种相关性某种相关性例如：甲、乙、丙三人进行乒乓球比赛，如例如：甲、乙、丙三人进行乒乓球比赛，如果任何两人之间都要赛一场，那么共要赛三场。果任何两人之间都要赛一场，那么共要赛三场。假设三场比赛的结果是乙胜甲，甲胜丙，乙胜假设三场比赛的结果是乙胜甲，甲胜丙，乙胜丙，这个结果可以记作丙，这个结果可以记作 乙，甲
8、乙，甲，甲，丙甲，丙，乙，丙乙，丙 其中其中x，y表示表示x胜胜y。它表示了集合它表示了集合甲、乙、丙甲、乙、丙中元素之间的一种中元素之间的一种胜负关系胜负关系1、什么是关系第17页/共44页l再例如，有甲，乙，丙三个人和四项工作，b b，c c，d d。已知甲可以从事工作和b b，乙可以从事工作c c，丙可以从事工作和d d。那么人和工作之间的对应关系可以记作 R=R=,d 这是人的集合 甲，乙，丙 到工作的集合，b b，c c，dd之间的关系。第18页/共44页l除了二元关系以外还有多元关系 本书只讨论二元关系。以后凡是出现关系的地方均指二元关系 下面给出二元关系的一般定义l定义（二元关系
9、）如果一个集合为空集或它的元素都是有序对，则称这个集合是一个二元关系，一般记作R R。对于二元关系R R，如果x x，y y R R，则记作xRyxRy。l设A A，B B为集合，A AB B的任何子集所定义的二元关系称作从A A到B B的二元关系，特别当A=BA=B时，则叫做A A上的二元关系。第19页/共44页例：集合例：集合A0,1，B2,3AB，AA的子集：的子集：R3=，R4=，都是都是A上的二元关系上的二元关系AA，AB的子集：的子集：R1=，R2=，都是都是A到到B上的二元关系上的二元关系第20页/共44页l|A|=n|A|=n，A AA A的子集有2 2n n2 2个，每个子集
10、代表一个A A上的关系，所以A A上有2 2n n2 2个不同的二元关系。lA A上的3 3种特殊的关系空关系：空集全域关系:E:EA A=A=AA A恒等关系:I:IA A=x x，x x|x|x A A第21页/共44页例：集合例：集合A A0,10,1为为A A上的上的空关系空关系E EA A 00，01，10，11为为A A上的全域关系上的全域关系I IA A 00，11为为A A上的恒等关系上的恒等关系AAAA00，01，10，11第22页/共44页其它一些常见关系:l设A A为实数集R R的某个子集，则A A上小于等于关系定义为:L LA A=x x，y y|x|x，y y Axy
11、 Axy例如：A=-1 A=-1，3 3，44，则 A A上小于等于关系 L LA A=-1-1，-1-1,-1-1，3 3,-1-1，4 4,3 3，3 3,3 3，4 4，4 4，4 4 第23页/共44页l设B B为实数集Z Z+的某个子集，则B B上整除关系定义为:D DB B=x x，y y|x|x，y y B x|y B x|y例：B=1B=1，2 2，3 3，66，则B B上整除关系D DB B=1,11,1,1,21,2,1,31,3,1,61,6,2,22,2,2,62,6,3,33,3,3,63,6,6,66,6 第24页/共44页集合A A的幂集P(A)P(A)上的包含关
12、系：R=R=x x，y y|x|x，y y P(A)x P(A)x y y 例:设A=aA=a，bb，则有:P(A)=P(A)=,aa，bb，AA R=R=,b,A,第25页/共44页2 2、关系的表示方法集合表示法关系矩阵法（A A是有穷集时）设A=xA=x1 1，x x2 2，x xn n，B=yB=y1 1，y y2 2，y ym m，R R是A A到B B的关系，则R R的关系矩阵是M MR R=（r rijij)n*m,n*m,其中其中 rij=1 若若 R rij=0 若若 R（i=1,n;j=1m）M MR R=第26页/共44页 例:A=1,2,3,4,B=a,b,c:A=1,
13、2,3,4,B=a,b,c，A A到B的关系R=,R=,R R的关系矩阵:1 11 11 11 11 1第27页/共44页 例:A=1,2,3,4,B=a,b,c:A=1,2,3,4,B=a,b,c，A A到B的关系R=,R=,R R的关系矩阵:第28页/共44页 例:A=1,2,3,4,A:A=1,2,3,4,A上的关系R=,4,4R=,R R的关系矩阵:第29页/共44页关系图法（A A是有穷集时）集合A=xA=x1 1，x x2 2，x xn n，B=yB=y1 1，y y2 2，y ym m，R R是A A到B B上的关系。首先在平面上画上n n个结点分别代表x x1 1，x xn n
14、，再画上m m个结点分别代表y y1 1，y y2 2，y ym m。如果x R R，则在x xi i到y yj j之间画上一 条从x xi i指向 y yj j的带箭头的直线 。这样得到的图就是R R的关系图。第30页/共44页 例:A=1,2,3,4,B=a,b,c:A=1,2,3,4,B=a,b,c，A A到B的关系R=,R=,R R的关系图:第31页/共44页 A A上关系R R的关系图：集合A=xA=x1 1，x x2 2，x xn n，R R是A A上的关系 首先在平面上画上n n个结点分别代表x x1 1，x xn n，如果x R R，则在x xi i到x xj j之间画上一 条
15、从x xi i指向 y yj j的有向边 。这样得到的图就是R R的关系图。第32页/共44页 例如：设 A=1A=1，2 2，3 3，4,A 4,A 上的关系 R=R=1,11,1,1,21,2,2,32,3,2,42,4,4,24,2 R R的关系图:第33页/共44页课堂练习：集合A=1，2，3写出A上的恒等关系，全域关系，小于等于关系，整除关系，并画出关系图第34页/共44页4.24.2关系的运算本节学习与关系有关的各种运算本节学习与关系有关的各种运算:域域关系的逆、关系的合成关系的逆、关系的合成关系的幂关系的幂 第35页/共44页1.1.域域定义定义（域域）关系）关系R R的的定义域
16、定义域domRdomR，值域值域ranRranR和和域域fldRfldR分别是分别是:domR=x|domR=x|y y（x x，y y R R）ranR=y|ranR=y|x x（x x，y y R R）fldR =domR fldR =domR ranR ranR第36页/共44页例例:下列关系都是整数下列关系都是整数Z Z上的关系，分别求上的关系，分别求出它们的定义域和值域出它们的定义域和值域 R1=R1=x x，y y|x|x，y y Zxy ZxyR2=R2=x x，y y|x|x，y y Zy=2x Zy=2x R3=R3=x x，y y|x|x，y y Z|x|=|y|=3 Z|
17、x|=|y|=3解解:DomR1=RanR1=ZDomR1=RanR1=ZDomR2=Z,RanR2=DomR2=Z,RanR2=（2z|z 2z|z Z Z），即偶），即偶数集数集DomR3=RanR3=-3DomR3=RanR3=-3，33第37页/共44页2 2.关系的逆、合成关系的逆、合成定义：定义：设设F F，G G为集合为集合A A上任意的关系，上任意的关系，则则F F的逆的逆记作记作F F-1-1，F F-1-1=x x，y y|yFx|yFxF F与与G G的合成的合成记作记作F FG G，F FG=G=x x，y y|z z（xGzzFyxGzzFy）第38页/共44页例例:
18、设设A=1，2，3，4，5，A上关系上关系 R,S,求求R-1,RS,SR。解解:R-1 ,RS,SR,第39页/共44页例例:设设F F，G G是是N N上的关系，其定义为上的关系，其定义为 F=F=x x，y y|x|x，y N y=xy N y=x2 2 G=G=x x，y y|x|x，y N y=x+1y N y=x+1求求G G-1-1，F F G G，G G F F。解解 :G G-1-1=y y，x x|y|y，x x N y=x+1 N y=x+1 =x x，y y|y|y，x x N x=y+1 N x=y+1 =x x，y y|y|y，x x N y=x-1 N y=x-1 =1 1，0 0，2 2，1 1，x+1x+1，x x，第40页/共44页F G=|z(xGz zFy)=|z(x,z N z=x+1,z,y N y=z2=|x,y N y=(x+1)2第41页/共44页G F=|z(xFz zGy)=|z(x,z N z=x2,z,y N y=z+1=|x,y N y=x 2+1合合成成运运算算不不是是可可交交换换的的，即即对对任任何何关关系系F F，G G，一般说来，一般说来FGGFFGGF第42页/共44页Q&A43第43页/共44页感谢您的观看！第44页/共44页