《CH4_二元关系和函数____1_二元关系基本概念.ppt》由会员分享，可在线阅读，更多相关《CH4_二元关系和函数____1_二元关系基本概念.ppt（44页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、离散数学离散数学CH4CH4二元关系和函数二元关系和函数回顾用推理规则证明：|=A证明：证明：设论域D=a,b,c，求证：第第4 4章二元关系和函数章二元关系和函数本章学习本章学习1.1.集合的笛卡尔积集合的笛卡尔积2.2.关系及其表示关系及其表示3.3.关系的运算关系的运算4.4.关系的性质关系的性质5.5.关系的闭包关系的闭包6.6.等价关系和偏序关系等价关系和偏序关系7.7.函数的定义和性质函数的定义和性质8.8.函数的复合和反函数函数的复合和反函数今日内容集合的笛卡尔积集合的笛卡尔积关系及其表示关系及其表示关系的运算关系的运算笛卡尔乘积笛卡尔乘积定义：由两个元素定义：由两个元素x x和
2、和y y（允许（允许x=yx=y）按）按一定的顺序排列成的二元组叫做一个一定的顺序排列成的二元组叫做一个有序对有序对（也称（也称序偶序偶），记做），记做，其，其中中x x是它的第一元素，是它的第一元素，y y是它的第二元是它的第二元素。素。平面直角坐标系中点的坐标就是序偶。平面直角坐标系中点的坐标就是序偶。例如，例如，,.都代都代表坐标系中不同的点。表坐标系中不同的点。序偶的特点序偶的特点（与集合的不同之处）（与集合的不同之处）当当xyxy时，时，两个有序对相等，即两个有序对相等，即=的充的充要条件是要条件是x=u,x=u,且且y=vy=v定义（定义（有序有序n n元组元组）:一个有序一个有序
3、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元组元组定义定义（笛卡儿积笛卡儿积）:设设A A，B B为集合，用为集合，用A A中元中元素作为第一元素，素作为第一元素，B B中元素作为第二元素，构中元素作为第二元素，构成序偶。所有这样的序偶组成的集
4、合叫做成序偶。所有这样的序偶组成的集合叫做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=,笛卡儿积中元素的个数笛卡儿积中元素的个数如果如果A A中有中有m m个元素个元素,B,B中有中有n n个元素个元素,则则A AB B和和B BA A中都有中都有mnmn个元素个元素笛卡儿积运算的性质笛卡儿积运算的性质若若A,BA,B中有一个空集中有一个空集,则它们的笛卡儿积是空集则它们的笛卡儿积是空集.即即 B=
5、A B=A =笛卡儿积运算笛卡儿积运算不适合交换律不适合交换律:当当ABAB且且A,BA,B都不是空集时都不是空集时,有有A ABBBBA A笛卡儿积运算笛卡儿积运算不适合结合律不适合结合律:当当A,B,CA,B,C都不是空集时都不是空集时,有有(A(AB)B)CACA(B(BC)C)设设xA,yB,zC,xA,yB,zC,那么那么,z(A,z(AB)B)C,x,AC,x,A(B(BC)C)。一般情况下一般情况下,z x,z x,所以所以,(A,(AB)B)CACA(B(BC)C)笛卡儿积运算笛卡儿积运算对对 或或 运算满足分配律运算满足分配律，即，即 A A (B(B C)=(A C)=(A
6、 B)B)(A (A C)C)(B(B C)C)A =(B A =(B A)A)(C (C A)A)A A (B(B C)=(A C)=(A C)C)(A (A C)C)(B(B C)C)A =(B A =(B A)A)(C (C A)A)证明证明A A (B(B C)=(A C)=(A B)B)(A (A C)C)对于任何的对于任何的x,yx,y，x,yx,y A A (B (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 A B B x,yx,y A A
7、C C x,yx,y(A (A B)B)(A (A C)C)所以所以 A A (B(B C)=(A C)=(A B)B)(A(A C)C)例例:设设A=1A=1，22，求，求P P（A A）A A 解解:P P（A A）A A =，11，22，1,2,1,2,1 1，22 =,1,2,，22，2 2，11，22，1 1,1,1，22，2 2 定义定义 (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
8、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 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 关系及其表示关系及其表示 什么是关系什么是关系关系的表示关系的表示所谓所谓二元关系二元关系就是在集合中两个元素之间的就是在集合中两个元素之间的某种相关性某种相关性例如：
9、甲、乙、丙三人进行乒乓球比赛，如例如：甲、乙、丙三人进行乒乓球比赛，如果任何两人之间都要赛一场，那么共要赛三场。果任何两人之间都要赛一场，那么共要赛三场。假设三场比赛的结果是乙胜甲，甲胜丙，乙胜假设三场比赛的结果是乙胜甲，甲胜丙，乙胜丙，这个结果可以记作丙，这个结果可以记作 乙，甲乙，甲，甲，丙甲，丙，乙，丙乙，丙 其中其中x，y表示表示x胜胜y。它表示了集合它表示了集合甲、乙、丙甲、乙、丙中元素之间的一种中元素之间的一种胜负关系胜负关系1、什么是关系再例如，有再例如，有甲，乙，丙甲，乙，丙三个人和四项工作三个人和四项工作，b b，c c，d d。已知甲可以从事工作已知甲可以从事工作和和b b
10、，乙可以从事工作，乙可以从事工作c c，丙可以从事工作，丙可以从事工作和和d d。那么人和工作之间的对应关系可以记作那么人和工作之间的对应关系可以记作 R=R=,d 这是人的这是人的集合集合 甲，乙，丙甲，乙，丙 到到工作的工作的集合集合，b b，c c，dd之间的关系之间的关系。除了二元关系以外还有除了二元关系以外还有多元关系多元关系 本书只讨论二元关系。以后凡是出现关系的地本书只讨论二元关系。以后凡是出现关系的地方均指二元关系方均指二元关系 下面给出二元关系的一般定义下面给出二元关系的一般定义定义（定义（二元关系二元关系）如果一个集合为空集或它的）如果一个集合为空集或它的元素都是有序对，则
11、称这个集合是一个元素都是有序对，则称这个集合是一个二元关二元关系系，一般记作，一般记作R R。对于二元关系对于二元关系R R，如果，如果x x，y y R R，则记作，则记作xRyxRy。设设A A，B B为集合，为集合，A AB B的任何子集所定义的二元的任何子集所定义的二元关系称作从关系称作从A A到到B B的二元关系的二元关系，特别当，特别当A=BA=B时，时，则叫做则叫做A A上的二元关系上的二元关系。例：集合例：集合A0,1，B2,3AB，AA的子集：的子集：R3=，R4=，都是都是A上的二元关系上的二元关系AA，AB的子集：的子集：R1=，R2=，都是都是A到到B上的二元关系上的二
12、元关系|A|=n|A|=n，A AA A的子集有的子集有2 2n n2 2个，每个子集代表一个个，每个子集代表一个A A上的上的关系，关系，所以所以A A上有上有2 2n n2 2个不同的二元关系。个不同的二元关系。A A上的上的3 3种特殊的关系种特殊的关系空关系空关系：空集空集全域关系全域关系:E:EA A=A=AA A恒等关系恒等关系:I:IA A=x x，x x|x|x A A例：集合例：集合A A0,10,1为为A A上的上的空关系空关系E EA A 00，01，10，11为为A A上的全域关系上的全域关系I IA A 00，11为为A A上的恒等关系上的恒等关系A AA A00，0
13、1，10，11其它一些常见关系其它一些常见关系:设设A A为实数集为实数集R R的某个子集，则的某个子集，则A A上上小于等小于等于于关系定义为关系定义为:L LA A=x x，y y|x|x，y y Axy 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 设设B B为实数集为实数集Z Z+的某个子集，则的某个子集，则B B上上整除关整除关系系定义为定义为:D DB B=x x，y y|x|x，y y B x|y B x|y例：例
14、：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 集合集合A A的幂集的幂集P(A)P(A)上的上的包含关系：包含关系：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,2 2、关系的表示方法、关系的表示方法集合表示法集合表示法关系矩阵法关系矩阵法（A A是有穷集时）是有穷集时）设设A=xA=x1 1，x x2 2，
15、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=例例: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的关系矩阵的关系矩阵:1 11 11 11 11 1 例例: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的关系矩阵的关系矩阵:例例:A
16、=1,2,3,4,A:A=1,2,3,4,A上的关系上的关系R=,R=,R R的关系矩阵的关系矩阵:关系图法关系图法（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，再画上再画上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
17、j的带箭头的带箭头的直线的直线 。这样得到的图就是这样得到的图就是R R的关系图。的关系图。例例: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的关系图的关系图: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之间画上一之间画上一 条从条从x xi i指向指向 y yj j的有向边的有向边 。
18、这样得到的图就是这样得到的图就是R R的关系图。的关系图。例如：例如：设设 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的关系图的关系图:课堂练习：集合A=1，2，3写出A上的恒等关系，全域关系，小于等于关系，整除关系，并画出关系图4.24.2关系的运算关系的运算本节学习与关系有关的各种运算本节学习与关系有关的各种运算:域域关系的逆、关系的合成关系的逆、关系的合成关系的幂关系的幂 1.1.域域定义定义（域域）关系）关系R R的的定义域定义域domRdomR，值域值域ranRranR和和域域f
19、ldRfldR分别是分别是: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例例:下列关系都是整数下列关系都是整数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|x|=|y|=3解解:DomR1=RanR1=ZDomR1=RanR1=ZD
20、omR2=Z,RanR2=DomR2=Z,RanR2=（2z|z 2z|z Z Z），即偶），即偶数集数集DomR3=RanR3=-3DomR3=RanR3=-3，332 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）例例:设设A=1，2，3，4，5，A上关系上关系 R,S,求求R-1,RS,SR。解解:R-1 ,RS,SR,例例:设
21、设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，F G=|z(xGz zFy)=|z(x,zNz=x+1,z,y N y=z2=|x,yNy=(x+1)2G F=|z(xFz zGy)=|z(x,zNz=x2,z,yN y=z+1=|x,yNy=x 2+1合合成成运运算算不不是是可可交交换换的的，即即对对任任何何关关系系F F，G G，一般说来，一般说来FGGFFGGFQ&AQ&A44