离散数学：第3讲 序偶与笛卡尔积.ppt

,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,序偶与笛卡尔积,*,2025/5/16 周五,序偶与笛卡尔积,1,回顾,集合恒等式及证明方法,对偶原理,与逻辑中格式类似,包含排斥原理（容斥原理）,2025/5/16 周五,序偶与笛卡尔积,2,序偶与笛卡尔积,序偶(有序二元组),有序三元组,有序,n,元组,笛卡尔积,笛卡尔积性质,2025/5/16 周五,序偶与笛卡尔积,3,序偶,(,ordered pair),序偶:,两个具有,固定次序,的客体组成一个序偶,=a,a,b,其中,a,是第一元素,b,是第二元素.,也记作(,a,b),2025/5/16 周五,序偶与笛卡尔积,4,序偶实例,平面中点的坐标,位置包含关系,2025/5/16 周五,序偶与笛卡尔积,5,序偶,相等,相等判定：=,a=cb=d,有序性：,a,b,2025/5/16 周五,序偶与笛卡尔积,6,有序三元组(,ordered triple),有序三元组:（空间中点的坐标）,=,c,有序,n(,2,),元组:,=,a,n,定理:=,a,i,=b,i,i,=1,2,n.#,2025/5/16 周五,序偶与笛卡尔积,7,笛卡尔积(,Cartesian product),笛卡尔积,:,令,A,和,B,是任意两个集合，若序偶的第一个成员是,A,中,的元素，第二个成员是,B,中,的元素，所有这些序偶组成的集合称为集合,A,和,B,的,笛卡尔积或卡氏积,，记作,A,B,。,A,B=|x,A,y,B.,2025/5/16 周五,序偶与笛卡尔积,8,笛卡尔积举例,例:,A=,b,a,B=1,2,3.,A,B=,.,BA,=,.,A,A,=,.,BB,=,.#,Problem:A,B,中元素个数是多少,?,2025/5/16 周五,序偶与笛卡尔积,9,笛卡尔积,元素个数,有限集合笛卡尔积元素个数关系：,若,|,A|=n,|B|=m,则,|A,B|=n,m=|B,A|,Problem:A,B,?=,BA,Problem:(A,B),C,?=,A,(B,C),2025/5/16 周五,序偶与笛卡尔积,10,笛卡尔积,的性质,非交换:,A,B,BA,(,除非,A=B A=,B=,),非结合:(,A,B),C,A,(BC),(,除非,A=,B=,C=,),分配律:,A,(B,C)=(A,B),(A,C),等,其他:,A,B=,A=,B=,等,2025/5/16 周五,序偶与笛卡尔积,11,笛卡尔积非交换性,非交换:,A,B,BA,(,除非,A=B A=,B=,),反例:,A=1,B=2.,A,B,=,B,A=.,2025/5/16 周五,序偶与笛卡尔积,12,笛卡尔积非结合性,非结合:(,A,B),C,A,(BC),(,除非,A=,B=,C=,),反例:,A=B=C=1.,(,A,B),C=,1,A,(,B,C)=.,A,B=,A=,B=,等,2025/5/16 周五,序偶与笛卡尔积,13,笛卡尔积分配律,1.A,(B,C)=(A,B),(A,C),2.A,(B,C)=(A,B),(A,C),3.(B,C),A,=(B,A,),(C,A,),4.(B,C),A,=(B,A,),(C,A,),2025/5/16 周五,序偶与笛卡尔积,14,笛卡尔积图示,二维空间,A,B,C,A,(,B,C,)=(,A,B,),(,A,C,),2025/5/16 周五,序偶与笛卡尔积,15,笛卡尔积分配律(证明),A,(B,C)=(A,B),(A,C).,证明:,A,(B,C),x,A,y(,B,C),x,A,(y,B,y,C),(x,A,y,B),(,x,A,y,C),(,A,B),(,A,C),x(,A,B),(A,C),A,(B,C)=(A,B),(A,C).#,2025/5/16 周五,序偶与笛卡尔积,16,消去律,设,A,B,C,是任意集合,则,A,C,BC,A,B,C,A,CB,A,B,若,C,2025/5/16 周五,序偶与笛卡尔积,17,消去律,(证明,),若,C,则,A,C,BC,A,B.,证明(续),:,(,),若,A=,则,A,C,=,B,C.,设,A,.,A,C,x,A,y,C,x,B,yC,B,C,A,C,B,C.,#,讨论:在(,)中不需要条件,C,.,2025/5/16 周五,序偶与笛卡尔积,18,消去律,(证明,),若,C,则,A,C,B,C,A,B.,证明,:(,)若,A=,则,AB.,设,A,由,C,设,y,C.,x,x,A,A,C,B,C,x,B,yC,xB.,A,B,2025/5/16 周五,序偶与笛卡尔积,19,保持性,设,A,B,C,D,是任意非空集合,则,A,C B,D ,A,B,CD,2025/5/16 周五,序偶与笛卡尔积,20,笛卡尔积图示,二维空间,A,C,B,D,A,B,CD,B,A,C,D,2025/5/16 周五,序偶与笛卡尔积,21,(证明,),A,C B,D,A,B,CD,证明,:(,),A,B,(x,A)(y,B),(x,C)(y,D),C,D,A,B,CD,2025/5/16 周五,序偶与笛卡尔积,22,(证明,),A,C B,D,A,B,CD,证明(续),:,(,),x,y,x,A,y,B,A,B,C,D,x,C,y D,A,C B,D.,#,2025/5/16 周五,序偶与笛卡尔积,23,n,维笛卡尔积,n,维笛卡尔积:,A,1,A,2,A,n,=|x,1,A,1,x,2,A,2,x,n,A,n,A,n,=,A,A,A,|A,i,|=n,i,i,=1,2,n,|A,1,A,2,A,n,|=n,1,n,2,n,n,.,n,维笛卡尔积性质与2维笛卡尔积类似.,2025/5/16 周五,序偶与笛卡尔积,24,n,维笛卡尔积(性质),非交换:,A,BC,BCA,(,要求,A,B,C,均非空,且互不相等),非结合:(非2元运算),分配律:例如,A,B,(C,D,)=(A,B,C),(A,BD,),其他:如,A,B,C=,A,=,B=,C=,.,2025/5/16 周五,序偶与笛卡尔积,25,二元关系,(binary relation,),二,元关系,(,简称关系,),：序偶的任一集合确定了一个二元关系,R,，,R,中任一序偶,可记作,R,或,xRy,；不在,R,中的任一序偶,可记作,R,或,xRy,/,2025/5/16 周五,序偶与笛卡尔积,26,二元关系举例,例,1:R,1,=,R,1,是,二,元关系,.,例,2:R,2,=,R,2,是,二,元关系,.,例,3:A=,a,1,A,不是关系,.#,2025/5/16 周五,序偶与笛卡尔积,27,举例,1,甲、乙、丙三个人进行乒乓球比赛，如果任何两个人之间都要赛一场，那么共要赛三场。假设三场比赛的结果是乙胜甲、甲胜丙、乙胜丙，这个结果可以记作,、,、,，其中,表示,x,胜,y,。它表示了集合,甲,乙,丙,中元素之间的一种胜负关系。,2025/5/16 周五,序偶与笛卡尔积,28,举例,2,有,A,，,B,，,C,三个人和四项工作,1,2,3,4,。已知,A,可以从事工作,1,和,4,，,B,可以从事工作,3,，,C,可以从事工作,1,和,2,。那么人和工作之间的对应关系可以记作,这是人的集合,A,B,C,到工作的集合,1,2,3,4,之间的关系。,2025/5/16 周五,序偶与笛卡尔积,29,二元关系的记号,设,R,是二元关系,则,R x,与,y,具有,R,关系,xRy,对比,:xRy (,中缀,(infix),记号,),R(x,y)(,前缀,(prefix),记号,),R (,后缀,(suffix),记号,),例如,:2.,2025/5/16 周五,序偶与笛卡尔积,30,定义域,值域,域,对任意关系,R,可以定义,:,定义域,(domain)(,前域,):,dom R=x|,y(xRy),值域,(range):,ran R=y|,x,(xRy),域,(field):,fld R=dom R,ran R,2025/5/16 周五,序偶与笛卡尔积,31,定义域,值域,域,(,举例,),例,4:R,1,=,R,2,=,R,3,=,.,dom R,1,=,ran R,1,=,fld R,1,=,dom R,2,=c,e,ran R,2,=d,f,fld R,2,=c,d,e,f,dom R,3,=1,3,5,ran R,3,=2,4,6,fld R,3,=1,2,3,4,5,6.#,2025/5/16 周五,序偶与笛卡尔积,32,讨论,由上我们可看出：,设,domR=A,，,ranR=B,，则,R,A,B,关系由序偶定义的，因此与笛卡尔积有关,.,结论：关系是,两集合,笛卡尔积的子集,.,2025/5/16 周五,序偶与笛卡尔积,33,A,到,B,的二元关系,A,到,B,的二元关系,:,是,A,B,的任意子集,.,R,是,A,到,B,的二元关系,R,A,B,RP(,A,B),当,A=B,时，,则叫做,A,上的二元关系,。,2025/5/16 周五,序偶与笛卡尔积,34,A,到,B,的二元关系的个数,Problem:,若,|A|=m,|B|=n,则,A,到,B,的二元关系有多少个,?,|,A,B|=mn,故,|,P,(,A,B)|=2,mn,即,A,到,B,不同的二元关系共有,2,mn,个,!,2025/5/16 周五,序偶与笛卡尔积,35,A,到,B,的二元关系,(,举例,),例,5:,设,A=a,1,a,2,B=b,则,A,到,B,的二元关系共有,4,个,:,R,1,=,R,2,=,R,3,=,R,4,=,.,B,到,A,的二元关系也有,4,个,:,R,5,=,R,6,=,R,7,=,R,8,=,.#,2025/5/16 周五,序偶与笛卡尔积,36,A,上的二元关系,例,6:,设,B=b,则,B,上的二元关系共有,2,个,:,R,1,=,R,2,=,.#,例,7:,设,A=a,1,a,2,则,A,上的二元关系共有,16,个,.,#,例,8:,设,C=a,b,c,则,C,上的,2,元关系,共有,2,9,=512,个,!#,2025/5/16 周五,序偶与笛卡尔积,37,一些特殊关系,空关系,恒等关系,全域关系,整除关系,小于等于关系,包含关系,真包含关系,2025/5/16 周五,序偶与笛卡尔积,38,特殊关系,设,A,是任意集合,则可以定义,A,上的,:,空关系,:,恒等关系,:,I,A,=|xA,全域关系,:,E,A,=AA=|xA yA,2025/5/16 周五,序偶与笛卡尔积,39,特殊关系,(,续,),设,AZ,则,可以定义,A,上的,:,整除关系,:,D,A,=|xA yA x|y,例,:A=1,2,3,4,5,则,D,A,=,.#,2025/5/16 周五,序偶与笛卡尔积,40,特殊关系,(,续,),设,AR,则,可以定义,A,上的,:,小于等于,(less than or equal to),关系,:,LE,A,=|xA yA xy,小于,(less than),关系,L,A,=|xA yA xy,大于等于,(greater than or equal to),关系,大于,(great than),关系,2025/5/16 周五,序偶与笛卡尔积,41,特殊关系,(,续,),设,A,为任意集合,则,可以定义,P(A),上的,:,包含关系,:,A,=|xA yA xy,真包含关系,:,A,=|xA yA xy,2025/5/16 周五,序偶与笛卡尔积,42,作业,P130,：,(2),(3),(4),(6),