《CH4二元关系和函数1二元关系的基本概念.ppt》由会员分享，可在线阅读，更多相关《CH4二元关系和函数1二元关系的基本概念.ppt（36页珍藏版）》请在三一办公上搜索。
1、离散数学CH4二元关系和函数,回顾,用推理规则证明：|=A,证明：设论域D=a,b,c，求证：,第4章二元关系和函数,本章学习1.集合的笛卡尔积2.关系及其表示3.关系的运算4.关系的性质5.关系的闭包6.等价关系和偏序关系7.函数的定义和性质8.函数的复合和反函数,今日内容,集合的笛卡尔积关系及其表示关系的运算,笛卡尔乘积,定义：由两个元素x和y（允许x=y）按一定的顺序排列成的二元组叫做一个有序对（也称序偶），记做，其中x是它的第一元素，y是它的第二元素。平面直角坐标系中点的坐标就是序偶。例如，,.都代表坐标系中不同的点。,序偶的特点（与集合的不同之处）当xy时，两个有序对相等，即=的充要
2、条件是x=u,且y=v,定义（有序n元组）:一个有序n元组（n3）是一个有序对，记做,其中第一个元组是一个有序n-1元组，即=,xn,例如，空间直角坐标系中点的坐标 1,-1,3,2,4,0等都是有序3元组。N维空间中点的坐标或n维向量都是有序n元组,定义（笛卡儿积）:设A，B为集合，用A中元素作为第一元素，B中元素作为第二元素，构成序偶。所有这样的序偶组成的集合叫做A和B的笛卡儿积，记作AB。符号化表示为 AB=|xAyB 例:若A=a,b,B=0,1,2,则 AB=,BA=,笛卡儿积中元素的个数如果A中有m个元素,B中有n个元素,则AB和BA中都有mn个元素,笛卡儿积运算的性质若A,B中有
3、一个空集,则它们的笛卡儿积是空集.即 B=A=笛卡儿积运算不适合交换律:当AB且A,B都不是空集时,有ABBA笛卡儿积运算不适合结合律:当A,B,C都不是空集时,有(AB)CA(BC)设xA,yB,zC,那么,z(AB)C,A(BC)。一般情况下,z 所以,(AB)CA(BC),笛卡儿积运算对或运算满足分配律，即 A(BC)=(A B)(A C)(BC)A=(B A)(C A)A(BC)=(A C)(A C)(BC)A=(B A)(C A)证明A(BC)=(A B)(A C)对于任何的x,y，x,y A(B C)x A yBC x A(y B y C)(x A y B)(x A yC)x,y
4、A B x,y A C x,y(A B)(A C)所以 A(BC)=(A B)(AC),例:设A=1，2，求P（A）A 解:P（A）A=，1，2，1,2,1，2=,1,，2，2，1，2，1,1，2，2,定义(n阶笛卡儿积)设A1,A2,An是n个集合(n2)。它们的n阶笛卡儿积 A1 A2 An=x1,x2,xn|x1A1x2A2xnAn 当A1=A2=An=A时，可将它们的n阶笛卡儿积 简记为An例如，A=a，b，则 A3=a，a，a，a，a，b，a，b，a，a，b，b，b，a，a，b，a，b，b，b，a，b，b，b,关系及其表示,什么是关系关系的表示,所谓二元关系就是在集合中两个元素之间的
5、某种相关性例如：甲、乙、丙三人进行乒乓球比赛，如果任何两人之间都要赛一场，那么共要赛三场。假设三场比赛的结果是乙胜甲，甲胜丙，乙胜丙，这个结果可以记作 乙，甲，甲，丙，乙，丙 其中x，y表示x胜y。它表示了集合甲、乙、丙中元素之间的一种胜负关系,1、什么是关系,再例如，有甲，乙，丙三个人和四项工作a，b，c，d。已知甲可以从事工作a和b，乙可以从事工作c，丙可以从事工作a和d。那么人和工作之间的对应关系可以记作 R=,这是人的集合甲，乙，丙到工作的集合a，b，c，d之间的关系。,除了二元关系以外还有多元关系 本书只讨论二元关系。以后凡是出现关系的地方均指二元关系 下面给出二元关系的一般定义定义
6、（二元关系）如果一个集合为空集或它的元素都是有序对，则称这个集合是一个二元关系，一般记作R。对于二元关系R，如果x，y R，则记作xRy。设A，B为集合，AB的任何子集所定义的二元关系称作从A到B的二元关系，特别当A=B时，则叫做A上的二元关系。,例：集合A0,1，B2,3,AB，,AA的子集：R3=，R4=，都是A上的二元关系,AA，,AB的子集：R1=，R2=，都是A到B上的二元关系,|A|=n，AA的子集有2n2个，每个子集代表一个A上的关系，所以A上有2n2个不同的二元关系。A上的3种特殊的关系空关系：空集全域关系:EA=AA恒等关系:IA=x，x|x A,例：集合A0,1,为A上的空
7、关系EA，为A上的全域关系IA，为A上的恒等关系,AA，,其它一些常见关系:设A为实数集R的某个子集，则A上小于等于关系定义为:LA=x，y|x，y Axy例如：A=-1，3，4，则 A上小于等于关系 LA=-1，-1,-1，3,-1，4,3，3,3，4，4，4,设B为实数集Z+的某个子集，则B上整除关系定义为:DB=x，y|x，y B x|y例：B=1，2，3，6，则B上整除关系DB=1,1,1,2,1,3,1,6,2,2,2,6,3,3,3,6,6,6,集合A的幂集P(A)上的包含关系：R=x，y|x，y P(A)x y 例:设A=a，b，则有:P(A)=,a，b，A R=,2、关系的表示
8、方法集合表示法关系矩阵法（A是有穷集时）设A=x1，x2，xn，B=y1，y2，ym，R是A到B的关系，则R的关系矩阵是MR=（rij)n*m,其中 rij=1 若 R rij=0 若 R（i=1,n;j=1m）,MR=,例:A=1,2,3,4,B=a,b,c，A到B的关系R=,R的关系矩阵:,1,1,1,1,1,例:A=1,2,3,4,B=a,b,c，A到B的关系R=,R的关系矩阵:,例:A=1,2,3,4,A上的关系R=,R的关系矩阵:,关系图法（A是有穷集时）集合A=x1，x2，xn，B=y1，y2，ym，R是A到B上的关系。首先在平面上画上n个结点分别代表x1，xn，再画上m个结点分别
9、代表y1，y2，ym。如果 R，则在xi到yj之间画上一 条从xi指向 yj的带箭头的直线。这样得到的图就是R的关系图。,例:A=1,2,3,4,B=a,b,c，A到B的关系R=,R的关系图:,A上关系R的关系图：集合A=x1，x2，xn，R是A上的关系 首先在平面上画上n个结点分别代表x1，xn，如果 R，则在xi到xj之间画上一 条从xi指向 yj的有向边。这样得到的图就是R的关系图。,例如：设 A=1，2，3，4,A 上的关系 R=1,1,1,2,2,3,2,4,4,2 R的关系图:,课堂练习：,集合A=1，2，3写出A上的恒等关系，全域关系，小于等于关系，整除关系，并画出关系图,Q&A,36,
