离散数学课件第四章(第1讲).ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,第四章二元关系,1,序偶与笛卡尔积,2,关系及其表示,3,关系的性质,4,关系的运算,5,等价关系与划分,6,相容关系与覆盖,7,偏序关系,1,序偶与笛卡尔乘积,1,序偶,定义,由二个具有给定次序的客体所组成的序列称为序偶。记作,x,，,y,例：,XY,二维平面上的一个点的坐标,x,，,y,就是一个序偶。,说明：,(1),在序偶中二个元素要有确定的排列次序。,若,a,b,时，则,a,，,b,b,，,a,若,x,，,y=a,，,b,（,x=a,y=b,）,(2),多重序元：,三元组：,x,，,y,，,z=x,，,y,，,z,n,元组：,x,1,，,x,2,，,x,3,，,x,n,=x,1,x,n,2,笛卡尔乘积,定义,设,A,，,B,为二个任意集合，若序偶的第一个成员（左元素）是,A,的一个元素，序偶的第二个成员（右元素）是,B,的一个元素，则所有这样的序偶,构成,的集合称为,A,和,B,的笛卡尔乘积。,记作：,A,B=x,，,y|,（,x,A,）,（,y,B,）,例：设,A=1,，,2,，,B=a,，,b,，则：,A,B=1,，,a,1,，,b,2,，,a,2,，,b,B,A=a,，,1,a,，,2,b,，,1,b,，,2,A,B,B,A,，,即“,”是不满足交换律。,例：设,A=a,，,b,，,B=1,，,2,，,C=z,则,:,(A,B),C=a,1,a,2,b,1,b,2,z,=a,1,z,a,2,z,b,1,z,b,2,z,A,(B,C)=a,，,b,1,z,2,z,=a,1,z,a,2,z,b,1,z,b,2,z,（,A,B,）,C,A,（,B,C,）,“,”不满足结合律。,定理,若,A,，,B,，,C,是三个集合，则有：,A,（,B C,）,=,（,A,B,）,（,A,C,）,A,（,B C,）,=,（,A,B,）,（,A,C,）,（,A B,）,C=,（,A,C,）,（,B,C,）,（,A B,）,C=,（,A,C,）,（,B,C,）,证明,:A,(B,C)=(A,B),(A,C),证明：设,是,A,（,B,C,）中的任一元素，则：,A,（,B,C,）,|xA yB,C,|x,A,y,B,y,C,|(x,A,y,B),(x,A,y,C),(A,B),(A,C),即,A,(B,C)=(A,B),(A,C),例：设,A=1,，,B=1,，,2,，,C=2,，,3,则,A,（,B,C,）,=1,1,，,2,，,3,=1,1,1,2,1,3,（,A,B,）,（,A,C,）,=1,1,，,2,1,2,，,3,=1,1,1,2,1,3,例：设,A=1,，,B=1,，,2,，,C=2,，,3,则：,A,（,B,C,）,=1,2=1,2,（,A,B,）,（,A,C,）,=1,1,1,2,1,2,1,3,=1,2,注：,n,个集合的笛卡儿乘积的定义：,A,2,=A,A,A,3,=A,A,A,A,n,=A,A,A,n,个,A,2,关系及其表示,1,关系,定义：指事物之间（客体之间）的相互联系。,在数学上关系可表达集合中元素间的联系。,序偶,a,，,b,可以反映,a,，,b,二个元素之间具有某 种关系。,定义,以序偶作为元素的任何集合是一个二元关系。,由定义可知：,二元,关系是一个集合。,设,R,表示二元关系，若,R,用,xRy,表示，,若,R,，则也可写成：,x R y,。,关系表示方法,（,1,）枚举法（列举法）,例：二元关系,R,定义如下图：,可用枚举法表示为：,（,2,）谓词公式表示法,一个集合可用谓词公式来表达，所以二元关系也可用谓词公式来表达。,例：实数集合,R,上的,“,”,关系可表达为：,“,”,=,（,3,）关系矩阵表示法,设二元关系,R,是,A B,上的二元关系，,关系矩阵表示法描述如下：,(a),集合,A,中的元素表示矩阵的行元素，集合,B,中的元素表示矩阵的列元素；,(b),若,R,，则在关系矩阵对应位置记上,“,1,”,，否则记为,“,0,”,。,例：设,A=a,，,b,，,c,，,B=1,，,3,，,4,，,R,1,是,A,B,上的二元关系，给出,R,1,的关系矩阵,.,R,1,=,a,b,c,1,3,4,1,0,1,1,1,0,M,R,1,=,1,1,0,例：设,X=a,，,b,，,c,，,Y=1,，,2,，,R,2,是,X,Y,上的二元关系，给出,R,2,的关系矩阵,.,例：设,X=a,，,b,，,c,，,Y=1,，,2,，,R,3,是,X,Y,上的二元关系且,R,3,=,，,给出,R,3,的关系矩阵,.,例：设,X=1,，,2,，,3,，,4,，,R,4,是,X,X,上的二元关系,，给出,R,4,的关系矩阵,.,R,4,=,1,0,0,1,1,0,M,R,4,=,1,1,1,0,0,0,0,0,0,0,（,4,）关系图表示法,设,R,为集合,X,Y,上的二元关系，,关系矩阵图表示法描述如下：,(a),把集合、中的元素以点的形式全部画在平面上；,(b),若,R,，则在,x,和,y,之间画一带箭头弧线，其箭头指向,y,。,反之不画任何联线。,例：设,X=1,，,2,，,3,，,4,，,R,1,是,X,上的二元关系，给出,R,1,的关系图。,R,1,=,.,关系的前域和值域,定义,设,R,是一个二元关系，由,R,的所有序偶的第一元素,x,组成的集合,dom R,称,R,的前域,即,定义,R,的前域和值域的并集称做,R,的域,记做,FLD R,即,:FLD R=dom R,ran R,定义,设,R,是一个二元关系，由,R,的所有序偶的第二元素,y,组成的集合,ran R,称,R,的值域,即,例：,X=1,2,3,4,5,6,Y=a,b,c,d,e,f,R,为,X,到,Y,的二元关系,.,dom R=1,2,3,4,ran R=a,b,c,d,FLD R=1,2,3,4,a,b,c,d,关系和笛卡尔乘积,笛卡尔乘积的任何子集都可以定义一种二元关系。,例：,X=1,2,3,4,，,Y=1,2,思考：,集合,XY,上可以产生多少种二元关系？,S,1,S,2,都是,X,Y,的子集，并且它们,二元关系。,S,1,=|x,X yYx y,=,三个特殊关系：全域关系，空关系，恒等关系,定义,集合,A,2,定义了,A,集合中的一种关系，该关系称为,A,中的全域关系，用,E,A,表示：,例：,A=,1,，,2,则集合,A,上的全域关系为：,E,A,=,定义,空集也是,AxA,的一个子集，它也定义了一种关系,称为空关系，用,A,表示。,例：,A=,1,，,2,则集合,A,上的空关系为：,A,=,定义,：集合,A,中的恒等关系，用,I,A,表示：,思考：集合,A=1,2,R,为,AXA,上的恒等关系，则,R,如何表示？,I,A,=|,x,A,例：,A=,1,2,3,4,则集合,A,上的恒等关系为：,I,A,=,