《CH4二元关系和函数1二元关系的基本概念.ppt》由会员分享，可在线阅读，更多相关《CH4二元关系和函数1二元关系的基本概念.ppt（36页珍藏版）》请在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和和y y（允（允许x=yx
2、=y）按）按一定的一定的顺序排列成的二元序排列成的二元组叫做一个叫做一个有序有序对（也称（也称序偶序偶），），记做做，其，其中中x x是它的第一元素，是它的第一元素，y y是它的第二元是它的第二元素。素。平面直角坐平面直角坐标系中点的坐系中点的坐标就是序偶。就是序偶。例如，例如，,.都代都代表坐表坐标系中不同的点。系中不同的点。序偶的特点序偶的特点（与集合的不同之（与集合的不同之处）当当xyxy时，两个有序两个有序对相等，即相等，即=的充的充要条件是要条件是x=u,x=u,且且y=vy=v定定义（有序有序n n元元组）:一个有序一个有序n n元元组（n n3 3）是）是一个有序一个有序对，记做
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中元素作中元素作为第二元素，构第二元素，构成序偶。所有成序偶。所有这样的序偶的序偶组成的集合叫做成的集合叫做A A和和B B的的笛卡儿笛卡儿积，记作作A AB B。符号化表示。符
4、号化表示为 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=A B=A =笛卡儿笛卡儿积运算运算不适合交不适合交换律律:当当ABAB且且A,BA,B都不是空集都不是空集时,有有ABBAABBA笛卡
5、儿笛卡儿积运算运算不适合不适合结合律合律:当当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)笛卡儿笛卡儿积运算运算对 或或 运算运算满足分配律足分配律，即，即 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
6、)(A C)(B(B C)A =(B A)C)A =(B A)(C A)(C 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)例例:设设A=1A=1，
7、22，求，求P P（A A）AA 解解:P P（A A）AA =，11，22，1,2,11,2,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 1AA1 1xx2 2AA2 2xxn nAAn n 当当A A1 1=A=A2 2=A=An n=A=A时，可将它，可将它们的的n n阶笛卡儿笛卡儿积 简记为A An n例如，例如
8、，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 关系及其表示关系及其表示 l什么是关系什么是关系l关系的表示关系的表示l所谓所谓二元关系二元关系就是在集合中两个元素之间的就是在集合中两个元素之间的某种相关性某种相关性l例如：甲、乙、丙三人进行乒乓球比赛，如例如：甲、乙、丙三人进行乒乓球比赛，如果任何两人之间都要赛一场，那么共要赛三场。果任何两人之间都要赛一场，那么共要赛三场。假设三场比赛的结果是乙胜甲，甲胜丙，乙
9、胜假设三场比赛的结果是乙胜甲，甲胜丙，乙胜丙，这个结果可以记作丙，这个结果可以记作 乙，甲乙，甲，甲，丙甲，丙，乙，丙乙，丙 其中其中x，y表示表示x胜胜y。它表示了集合它表示了集合甲、乙、丙甲、乙、丙中元素之间的一种中元素之间的一种胜负关系胜负关系1、什么是关系l再例如，有再例如，有甲，乙，丙甲，乙，丙三个人和四三个人和四项工作工作a a，b b，c c，d d。已知甲可以从事已知甲可以从事工作工作a a和和b b，乙可以从事工作，乙可以从事工作c c，丙可以从事，丙可以从事工作工作a a和和d d。那么人和工作之那么人和工作之间的的对应关系可以关系可以记作作 R=R=,d 这是人的是人的集
10、合集合 甲，乙，丙甲，乙，丙 到到工作的工作的集合集合aa，b b，c c，dd之之间的关系的关系。l除了二元关系以外除了二元关系以外还有有多元关系多元关系 本本书只只讨论二元关系。以后凡是出二元关系。以后凡是出现关系的地关系的地方均指二元关系方均指二元关系 下面下面给出二元关系的一般定出二元关系的一般定义l定定义（二元关系二元关系）如果一个集合）如果一个集合为空集空集或它的或它的元素都是有序元素都是有序对，则称称这个集合是一个个集合是一个二元关二元关系系，一般，一般记作作R R。对于二元关系于二元关系R R，如果，如果x x，y y R R，则记作作xRyxRy。l设A A，B B为集合，集
11、合，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上的二元关系上的二元关系l|A|=n|A|=n，A AA A的子集有的子集有2 2n n2 2个，每个子集代表一个个，每个子集代表一个A A上的上的关系，关系，所以所以A A上有上有2 2n n2 2个不同的二元关系。个不同的二元关系。lA A上
12、的上的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上的恒等关系上的恒等关系AAAA00，01，10，11其它一些常其它一些常见关系关系:l设A A为实数集数集R R的某个子集，的某个子集，则A A上上小于等小于等于于关系定关系定义为:L LA A=x x，y y|x|x，y y Axy Axy例如：例如：A=-1 A
13、=-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 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 集合集合A A的的幂集集P(A)P(A)上的上的
14、包含关系：包含关系：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，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=例例
15、: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=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上的关系。上的关
16、系。首先在平面上画上首先在平面上画上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 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的有向的有向边 。这样得到的得到的图就是就是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上的恒等关系，全域关系，小于等于关系，整除关系，并画出关系图Q&AQ&A36