西安交大离散课件第2章

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

1、第二章关系(relation)§1.集合的叉积n元组§2.关系§3.关系的表示关系的性质§4.关系的运算§5.等价关系§6.半序关系1§1.集合的叉积n元组定义1.叉积，笛卡尔积(crossproduct,Cartesianproduct(1637))n个集合A1，A2，，An的n维叉积定义为=A1×A2××An={(a1,a2,,an):aiAi(1in)}；n维叉积A1×A2××An的每个元素(a1,a2,,an)都称为一个n元组（n-tuple）；即，叉积是元组的集合；每个n元组(a1,a2,,an)的第i个位置上的元素ai称为该n元组的第i个分量

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

3、素b称为后者；二重叉积的AB第一集合A称为前集；第二集合B称为后集。一般地说，关于叉积和元组有：(1)(a,b)(b,a)；(2)A×BB×A；(3)二元组不是集合，因为二元组中的分量计较顺4序,而集合中的元素是不讲顺序的。但是为了将所有的概念都统一于集合概念，可采用克亚托斯基(KazimierzKurafowski)在1921年给出的定义(a,b)={{a},{a,b}}将二元组定义为比其元素高二层的集合；(4)也可用二元组来递归的定义n元组如下：(a,b,c)=((a,b),c)(a1,a2,,an-1,an)=((a1,a2,,an-1),an)(5)可

4、用二重叉积来递归的定义n维叉积如下：A×B×C=(A×B)×CA1×A2××An-1×An=(A1×A2××An-1)×An5(6)利用(5)所给的定义，可以递归的定义集合的叉积幂如下：A2=A×AA3=A2×AAn=An-1×A(7)规定空集与任何集合A的叉积是空集。即A×==×A定理1.设A,B,C,D是四个非空的集合。那么A×B=C×DA=CB=D。6[证].)：（采用逻辑法）对任何的元素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。定理2.设A,B,C是三个集合。则(1

5、)A×(B∪C)=(A×B)∪(A×C)；(叉积对并)(2)A×(B∩C)=(A×B)∩(A×C)；(叉积对交)(3)(A∪B)×C=(A×C)∪(B×C)；(叉积对并)(4)(A∩B)×C=(A×C)∩(B×C)。(叉积对交)7[证].只证(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)。8§2.关系一.关系

6、的基本概念定义1.设A,B是两个非空的集合，二重叉集A×B的任何一个子集R都称为是从集合A到集合B的一种二元关系(binaryrelation)。即RA×B；当(a,b)R时，称a与b有关系R，记为aRb；当(a,b)R时，称a与b没有关系R，记为或；当A=B时，即RA×A，则称R是A上的一个二元关系。例1.设A是西安交通大学全体同学组成的集合。9例2.设A是某一大家庭。例3.设N是自然数集合。例4.设Ｉ是整数集合。例5.设A是某一大型FORTRAN程序中诸程序块的集合。例6.设A={风，马，牛}，101°全关系(fullrelation)：R=AB称为全关系

7、；2°空关系(emptyrelation)：R=称为空关系；空关系和全关系都是平凡关系；3°幺关系或单位关系(identicalrelation)：R={(a,a):aA}AA称为A上的幺关系；4°关系的交，并，余运算：叉积是一种（新型的）集合，关系是叉积的子集，因此，关系也是一种集合，有关集合论的一切概念、论述、运算也都适合于关系；5°关系的扩充(expansion)：若R1R2，则称关系R2是关系R1的一个扩充；6°n元关系：n元关系R是n维叉积的一个子集；即RA1A2