离散数学第2章关系ppt课件.ppt

《离散数学第2章关系ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、离散数学西安交通大学电子与信息工程学院计算机系1离散数学第二章关系(relation)§1.集合的叉积n元组§2.关系§3.关系的表示关系的性质§4.关系的运算§5.等价关系§6.半序关系2离散数学§1.集合的叉积　n元组定义1.叉积，笛卡尔积(crossproduct,Cartesianproduct(1637))n个集合A1，A2，，An的n维叉积定义为=A1×A2××An={(a1,a2,,an):aiAi(1in)}；3离散数学n维叉积A1×A2××An的每个元素(a1,a2,,an)

2、都称为一个n元组（n-tuple）；即，叉积是元组的集合；每个n元组(a1,a2,,an)的第i个位置上的元素ai称为该n元组的第i个分量（坐标或投影）；元组各分量的顺序不能改变；n称为该叉积及其元组的维数；两个元组相等它们的维数相同且对应的分量相等。即(a1,a2,,an)=(b1,b2,,bm)n=m(iN)(1in)(ai=bi)；注：笛卡尔(1596-1650)，法国数学家，1637年发表《方法论》之一《几何学》，首次提出坐标及变量概念。这里是其概念的推广。4离散数学定义2.二个

3、集合A，B的(二维或二重)叉积定义为A×B={(a,b):aAbB}；其元素——二元组(a,b)通常称为序偶或偶对(orderedpair)；二元组(a,b)的第一分量上的元素a称为前者；第二分量上的元素b称为后者；二重叉积的AB第一集合A称为前集；第二集合B称为后集。5离散数学例1.A={a,b,c},B={0,1}A×B={(a,0),(a,1),(b,0),(b,1),(c,0),(c,1)}B×A={(0,a),(0,b),(0,c),(1,a),(1,b),(1,c)}例2.A={张三,李四

4、}，B={白狗,黄狗}A×B={(张三,白狗),(张三,黄狗),(李四,白狗),(李四,黄狗)}B×A={(白狗,张三),(白狗,李四),(黄狗,张三),(黄狗,李四)}6离散数学一般地说，关于叉积和元组我们有：(1)(a,b)(b,a)；(2)A×BB×A；(3)二元组不是集合，因为二元组中的分量计较顺序,而集合中的元素是不讲顺序的。(4)我们也可用二元组来递归的定义n元组如下：(a,b,c)=((a,b),c)(a1,a2,,an-1,an)=((a1,a2,,an-1),an)7离散数学(

5、5)这样，我们也就可用二重叉积来递归的定义n维叉积如下：A×B×C=(A×B)×CA1×A2××An-1×An=(A1×A2××An-1)×An8离散数学(6)利用(5)所给的定义，我们可以递归的定义集合的叉积幂如下：A2=A×AA3=A2×AAn=An-1×A(7)我们规定空集与任何集合A的叉积是空集。即A×==×A由于若偶对的第一分量或第二分量不存在就没有偶对存在，故规定它们的叉积集合为空集是合理的。9离散数学定理1.设A,B,C,D是四个非空的集合。那么A×B=C×DA=CB=

6、D　。[证].)：（采用逻辑法）对任何的元素a,b(a,b)A×B(a,b)C×D(条件：A=CB=D）所以　A×B=C×D。10离散数学)：（采用逻辑法）对任何的元素a,baAbB(a,b)A×B(a,b)C×D(条件：A×B=C×D）aCbD所以　A=CB=D。11离散数学定理2.设A,B,C是三个非空集合。则(1)左分配律：A×(B∪C)=(A×B)∪(A×C)(2)左分配律：A×(B∩C)=(A×B)∩(A×C)(3)右分配律：(A∪B)×C=(A×C)∪(B×C)

7、(4)右分配律：(A∩B)×C=(A×C)∩(B×C)12离散数学[证].只证(1)（采用逻辑法）对任何的元素a,b(a,b)A×(B∪C)aAbB∪CaA(bBbC)(aAbB)(aAbC)(分配律：p(qr)(pq)(pr))(a,b)A×B(a,b)A×C(a,b)(A×B)∪(A×C)所以A×(B∪C)=(A×B)∪(A×C)。13离散数学§2.关系一.关系的基本概念定义1.二元关系(binaryrelation)设A,B是两个非空的集合。

8、二重叉集A×B的任何一个子集R都称为是从集合A到集合B的一种二元关系。即RA×B；当(a,b)R时，称a与b有关系R，记为aRb；当(a,b)R时，称a与b没有关系R，记为或；当A=B时，即RA×A，则称R是A上的一个二元关系。14离散数学例1.设A是西安交通大学全体同学组成的集合。R={(a,b):aAbAa与b是同乡}A×A于是，R是西安交通大学同学之间的同乡关系。例2.设N是