离散数学第二章关系

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

1、离散数学西安交通大学电子与信息工程学院计算机软件所刘国荣1等价关系叉积关系幺关系元组全关系传递闭包逆关系复合关系关系幂自反传递闭包自反关系对称关系反对称关系传递关系半序关系空关系余关系并关系差关系交关系2离散数学第二章关系(relation)§1.集合的叉积n元组§2.关系§3.关系的表示关系的性质§4.关系的运算§5.等价关系§6.半序关系3离散数学§1.集合的叉积n元组定义1.叉积，笛卡尔积(crossproduct,Cartesianproduct(1637))n个集合A1，A2，，An的n维叉积定义为=A1×A2××An={(a1,a2,,an):aiAi(1in)}

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

3、的(二维或二重)叉积定义为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={张三,李四}，B={白狗,黄狗}A×B={(张三,白狗),(张三,黄狗),(李四,白狗),(李四

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

5、n-1),an)(5)这样，我们也就可用二重叉积来递归的定义n维叉积如下：A×B×C=(A×B)×CA1×A2××An-1×An=(A1×A2××An-1)×An7离散数学(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。8离散数学[证].):显然。)：（采用逻辑法）对任何的元素a,ba

6、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)左分配律：A×(B∪C)=(A×B)∪(A×C)(叉积对并的)；(2)左分配律：A×(B∩C)=(A×B)∩(A×C)(叉积对交的)；(3)右分配律：(A∪B)×C=(A×C)∪(B×C)9离散数学(叉积对并的)；(3)右分配律：(A∩B)×C=(A×C)∩(B×C)(叉积对交的)。[证].只证(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

7、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)。10离散数学§2.关系一.关系的基本概念定义1.二元关系(binaryrelation)设A,B是两个非空的集合。二重叉集A×B的任何一个子集R都称为是从集合A到集合B的一种二元关系。即RA×B；当(a,b)R时，称a与b有关系R，记为aRb