离散数学集合论部分PPT课件.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第二部分 集合与关系,1,对于从事计算机科学工作的人们来说，集合论是必不可少的基础知识。例如程序设计语言、数据结构、形式语言等都离不开子集、幂集、集合的分类等概念。集合成员表和范式在逻辑设计、定理证明中也都有重要应用。,本部分从集合的直观概念出发，介绍了集合论中的一些,基本概念,和,基本理论,。,2,集合论是研究集合的一般性质的数学分支,，它研究集合不依赖于组成它的事物的特性的性质。集合论总结出由各种对象构成的集合的共同性质，并用统一的方法来处理。,集合论的特点是研究对象的广泛性，集合是各种不同对象的抽象，这些对象可以是数或图形，也可以使任意其它事务。,3,1.,二十六个英文字母可以看成是一个集合；,2.,所有的自然数看成是一个集合；,3.,重庆邮电大学计算机学院,2010,级的本科学生可以看成是一个集合；,4.,这间教室中的所有座位可以看成是一个集合。,例,:,集合的基本概念,4,组成一个集合的那些对象或单元称为这个集合的元素。,通常，用小,写的英文字母,a,b,c,表示,集合中的元素。元素可以是单个的数字也可以是字母，还可以是集合。,如：,A=a,c,b;B=a,b,c,集合的元素,5,元素与集合的属于关系：,设,A,是一个集合，,a,是集合,A,中的元素，,元素与集合的关系：,属于；不属于,若,a,是集合,A,中的元素记为,a,A,，读作,a,属于,A,；,若,a,不是集合,A,中的元素，则记为,a,A,，读作,a,不属于,A,。,例如：,A,是正偶数集合，则,2,A,，,4,A,，,6,A,；而,1,A,，,3,A,，,19,A,。,6,特别注意：,集合并不决定于它的元素展示方法。集合的元素被重复或重新排列，集合并不改变，即,a,a,b,c,d,c=a,b,c,d,。,集合的元素可以是具体事物，可以是抽象概念，也可以是集体，如一本书，一支笔；集合,1,2,3,可以是集合,B=,一本书，一支笔，,1,2,3,的元素。特别地，以集合为元素的集合称为集合族或集合类如,A=1,2,3,8,9,6,。,集合中元素之间可以有某种关联，也可以彼此毫无关系。,7,有限集,A,中所含元素的个数称为集合的元数。记作：,|A|,如：,A=1,3,2,4,5,9,则,|A|=,6,；,设,A,是所有英文字母组成的集合，则,A,=26,。特别，,|=0,集合的元素数,8,列举法,(,列元素法,),：,将集合中的元素一一列举，或列出足够多的元素以反映集合中元素的特征，例如：,V=a,b,c,d,e,或,B=1,2,3,4,5,6,。,描述法,(,谓词表示法,):,将集合元素的条件或性质用文字或符号在花括号内竖线后面表示出来。,A=x|,关于,x,的一个命题,P;,如：,B=x|0 x10;B=x|x=a,2,a,是自然数,。,集合的表示法,9,E,A,a,e,文氏图,用一个大的矩形表示全集，在矩形内画一些圆或其它的几何图形，来表示集合，有时也用一些点来表示集合中的特定元素。,例如：,集合,A,=a,b,c,d,e,，用,文氏图,表示如下,:,d,c,b,10,几类特殊集合,:,N,=0,1,2,3,，即自然数集合。,Z,=,-2,-1,0,1,2,3,，即整数集合。,Z,+,=1,2,3,，即正整数集合。,Q,=,有理数集合。,R,=,实数集合。,C,=,复数集合。,11,确定性；,互异性；,无序性；,多样性；,集合的特征,12,任何一个对象，或者是这个集合的元素，或者不是，二者必居其一；,例如：,A=x|x,是自然数，且,x100,；,B=x|x+1=3,；,C=x|x,是大学生,。,确定性,13,集合中任何两个元素都是不同的，即集合中不允许出现重复的元素。,例如：,集合,A=a,b,c,c,b,d,，实际,上，应该是,A=a,b,c,d,。,再如,1,2,3,2,4=1,2,3,4,。,互异性,14,集合与其中的元素的顺序无关；,例如：,集合,a,b,c,d,e,、,d,c,e,a,b,、,e,c,d,b,a,，都是表示同一个集合。,集合,4,2,1,3=1,2,3,4,。,无序性,15,集合中的元素可以是任意的对象，相互独立，不要求一定要具备明显,的共同特征。,例如：,A=a,a,a,b,a,1,；,A=1,a,*,-3,a,b,x|x,是汽车,地球,注意,:,对于任何集合,A,都有,A,A,。,多样性,16,设,A,，,B,是两个集合，若,B,的元素都是,A,的元素，则称,B,是,A,的,子集,，也称,A,包含,B,，或,B,被,A,包含，记以,B,A,，或,A,B,。,若,B,A,，且,A,B,，则称,B,是,A,的,真子集,，也称,A,真包含,B,，或,B,真包含于,A,，记以,A,B,，或,B,A,。,子集：,17,例,3.1,设,A=a,b,c,a,a,b,试判断下列表达式正确与否。,（,1,）,a,A,（,2,）,a,A,（,3,）,a,A,（,4,）,A,（,5,）,A,（,6,）,b,A,（,7,）,b,A,（,8,）,b,A,（,9,）,a,b,A,(10)a,b,A,(11)c,A (12),c,A,(13),c,A (14),a,b,c,A,。,解,：,(,4),，,(7),，,(11),，,(13),(14),错误。,18,例,3.2,对于任意集合,A,B,和,C,下述论断是否正确,（,1,）若,A,B,B C,则,A,C,（,2,）若,A,B,B C,则,A,C,（,3,）若,A,B,BC,则,A,C,解,：（,1,）（,2,）,（,3,）,对,(3),举反例,A=,B=1,C=1,。,19,例,3.3,设,A=1,2,3,4,5,6,7,8,下列选项正确的是（,3,）；,（,1,）,1,A,（,2,）,1,2,3,A,（,3,）,4,5,A,（,4,）,A,例,3.4,下列各选项错误的是（,2,）；,（,1,）,（,2,）,（,3,）,（,4,）,例,3.5,在,0,_,之间填上正确的符号：（,4,）,（,1,）,=,（,2,）,（,3,）,（,4,）,20,当两个集合,A,和,B,的元素完全一样，即,A,，,B,实际上是同一个集合时，则称集合,A,，,B,相等，记为,A=B,。,符号化表示为：,A=B,A,B,B,A,例：,设,A=x|x,是偶数，且,0 x10,，,B=2,4,6,8,，则,A=B,。,集合相等,21,注：,说明两个集合,A,、,B,相等，需说明两,个问题：,1,、,A,是集合,B,的子集（,A,B,）,（任意元素,aA,，有,aB,）,2,、,B,是集合,A,的子集（,A,B,）,（任意元素,aB,，有,aA,）,22,集合的包含关系也可表成,A,B,(,x)(x,A,x,B),这表明，要证明,A,B,，只需对任意元素,x,，有下式,x,A,x,B,成立即可。,23,空集,不含任何元素的集合叫做空集，记作,。,空集的符号化表示为：,=x|P(x),P(x),。,其中,P(x),为任何谓词公式。,如：,A=x|x,R x,2,+1=0,。,该方程无实数解。,注意：,由定义可知，对任何集合,A,，有,A,。这是因为任意元素,x,，公式,x,x,A,总是为真。,24,注意：,与,是不同的。,是以,为元素的集合，而,没有任何元素，能用,构成集合的无限序列：,，,，,，,该序列除第一项外，每项均以前一项为元素的集合。,25,定理：,空集是一切集合的子集。,证明：,对于任何集合,A,，由子集定义有,A,x(x,x,A),右边的蕴涵式中前件为,x,为假，所以整个,蕴涵式对一切,x,为真，所以,A,为真,推论,：空集是唯一的。,证明,:,如不唯一,设存在空集,1,和,2,由空集是一切集合的子集得,1,2,和,2,1,。根据集合相等的定义得，,1,=,2,26,全集：,如果一个集合包含了所要讨论的每一个集合，则称该集合为全集，记为,E,或,U,。它可形式地表为,E,=x|P(x),P(x),。其中,P(x),为任何谓词公式。,27,注意符号,和意义的区别：,表示元素与集合之间的关系，而则表示集合与集合之间的关系。但由于集合的抽象性，集合中的元素可以是集合，故可以发生如：,A B,且,A B,的情形,例,设,A=1,2,3,1,2,3,，则,1,2,3,A,且,1,2,3,A,。,注意：,28,对任意集合,A,有,A,A,。,空集是任意集合的子集，且空集是唯一的。,对于任意两个集合,A,、,B,，,A=B,的充 要条件是,A,B,且,B,A,。（,这个结论非常简单，但它非常重要，很多证明都是用这个方法或思路来证明。）,重要结论,29,设,A,是集合，,A,的所有子集为元素做成的集合称为,A,的,幂集,记以,P,(A),符号化表示为：,P(A)=x|x,A,。,例：,A=a,b,c,，则,P,(A)=,a,b,c,a,b,a,c,b,c,a,b,c,。,幂集,30,例,3.6,设,A=a,a,下列选项错误的是,A.a,P,(A)B.a,P,(A),C.a,P,(A)D.a,P,(A),例,3.7,幂集,P(P(P(,),),为（,C,）,A.,B.,C.,D.,P(A)=,a,a,a,a,31,例,3.8,判断下面的关系是否正确,并简要说明理由。,a,b,a,b,c,a,b,c,a,b a,b,c,a,b,c,a,b,a,b,a,b,a,b a,b,a,b,32,解答,：,对选项,因为,a,b,中每个元素,(,只有,a,和,b),均在集合,a,b,c,a,b,c,对选项,因为,a,b,中每个元素,(,只有,a,和,b),均在集合,a,b,a,b,对选项,集合,a,b,c,a,b,c,中含有,4,个元素，分别为,a,b,c,a,b,c,没有,a,b,，所以不正确。,对选项,集合,a,b,a,b,中含有,3,个元素，分别为,a,b,a,b,没有,a,b,，所以不正确。,33,若,A,为有穷集，,|A|=n,，则,|2,A,|=C,n,0,+C,n,1,+,+C,n,n,=2,n,。,x,P,(A),当且仅当,x,A,。,设,A,、,B,是两个集合，,A,B,当且仅当,P,(A),P,(B),。,幂集的性质,34,并,A,B,=,x,|,x,A,x,B,；,交,A,B,=,x,|,x,A,x,B,；,相对补,A,B,=,x,|,x,A,x,B,；,对称差,A,B,=(,A,B,),(,B,A,),=(,A,B,)(,A,B,),；,绝对补,A,=,E,A,。,3.2,集合的基本运算,35,A B A,A B,A,A B A B,A-B A,B,A,A B B C,A B (A B)-C,集合运算对应的文氏图表示,36,并和交运算可以推广到有穷个集合上，即,A,1,A,2,A,n,=,x,|,x,A,1,x,A,2,x,A,n,A,1,A,2,A,n,=,x,|,x,A,1,x,A,2,x,A,n,某些重要结果：,A,B,A,A,B,A,B,=,A,B,=,A,B,=,A,37,集合的广义交和广义并,设,S,为集合，,S,的元素的元素构成的集合称为,S,的,广义并,，记为,S,，其中,S=x,z(z,S,x,z,；,设,S,非空集合，,S,的元素的公共元素构成的集合称为,S,的广义交，记为,S,，其中,S=x,z(z,S,x,z,。,38,说明：,（,1,）规定,=,，,无意义。,（,2,）若 ，则由定义不难证明,S=,S=,（,3,）并运算和广义并运算的运算符相同，但前者是二元运算，,后者是一元运算，因此在运算过程中不会对,产生误解。,39,例：,设集合,A=a,b,c,a,c,d,a,c,e,，求,A,，,A,，,A,，,A,，,A,，,A,。,解：,A=a,b,c,d,e,；,A=a,c,；,A=a,b,c,d,e,；,A=a,c,；,A=a,c,；,A=a,b,c,d,e,。,40,优先级,一般地,一元运算符,(,补集,幂集,广义并,广义交,),优先于,二元运算符,(,差集,并集,交集,对称差,笛卡儿积,),；二元运算符,优先于,集合关系符,(,),。,此外,许多集合表达式里还使用到联结词,和逻辑关系符以及括号,我们规定,:,(1),集合运算优先于逻辑运算；,(2),括号内优先于括号外；,(3),同一括号内,同一优先级按从左至右运算。,41,集合运算律,幂等律,：,AA,A,；,AA,A,同一律,：,A,A,；,AE=A,零 律：,AE=E,；,A,结合律：,(AB)C,A(BC),；,(AB)C,A(BC),交换律,：,AB,BA,；,AB,BA,分配律,：,A,（,BC,）（,AB,）,(AC),；,A(BC)=(AB)(AC),42,排中律：,矛盾律：,吸收律,：,A,（,AB,）,A,A(AB),A,摩根律：,双重否定律,：,43,其它常用结论：,AB,A,AB,B,；,A,AB,B,AB,；,A-B,A,，,A-B=AB,；,AB=B,A,B,A,B=A,A-B=,；,A,B=B A,；,(A,B)C=A(B C),A,=A,；,A,A,=,；,A,B=A CB=C,。,44,集合,等式的证明，可采用命题逻辑的等值式证明，,其基本思想是,互为子集,：,欲证,:A=B,即证,:,即证,:,对任意的,x,，,当上述过程可逆时，可以合并为,对任意的,x,集合相等的证明方法,45,例：,证明下列集合恒等式。,（,1,）,A,（,BC,）（,AB,）,(AC),（,2,）,（,3,）,证明：,(1),对任意的,x,46,(2),对任意的,x,(3),对任意的,x,47,例,3.3.2,证明：（,1,）,（,2,）,A,B=,（,AB,）,-,（,AB,）,证明,：,(1),(2)A,B=,（,A-B,）,（,B-A,）,48,例,证明,(AB)-C=(A-C)(B-C).,证明,:,对于,x,x (AB)-C,x (AB),x,C,(,x A,xB),x,C,(,x A,x,C),(xB,x,C),x(A-C),x(B-C),x(A-C)(B-C),(AB)-C=(A-C)(B-C),49,例,证明,证明：,(1),必要性,：对任意的,X,因此，。,(2),充分性,：对任意的,x,，,因此 ，结论得证。,50,例,求在,1,和,1000,之间不能被,5,或,6,，也不能被,8,整除的数的个数解：设,1,到,1000,之间的整数构成全集,E,，,A,，,B,，,C,分别表示其中可被,5,，,6,或,8,整除的数的集合。,解：,在,ABC,中的数一定可被,5,6,和,8,的最小公倍数,5,6,8,=120,整除，即,ABC,=1000/5,6,8=8,同样可得,AB,=1000/5,6=33,；,AC,=1000/5,8=25,；,BC,=1000/6,8=41,；,51,然后计算,A,=1000/5=200,；,B,=1000/6=166,；,C=1000/8=125,从而得到 ,ABC,=200+100+33+67=400,所以，,不能被,5,或,6,也不能被,8,整除的数有,600,个。,150,100,67,17,33,25,8,52,对上述子集计数：,|S|=1000,；,|A|=,1000/5,=200,；,|B|=,1000/6=133,；,|C|=,1000/8,=125,；,|A,B|=,1000/30,=33,；,|B,C|=,1000/40,=25,|B,C|=,1000/24,=41,；,|A,BC|=,1000/120,=8,。,代入公式：,N,=1000,(200+133+125)+(33+25+41),8=600,。,这个方法叫,容斥原理。,53,称为包含排斥原理，简称,容斥原理,。,容斥原理,定理：,有穷集,S,中不具有,p,1,p,2,p,m,元素数是,54,推论,设,A,1,A,2,A,n,是,n,个集合，则,55,例,某班有,25,个学生，其中,14,人会打篮球，,12,人会打排球，,6,人会打篮球和排球，,5,人会打篮球和网球，还有,2,人会打这三种球。而,6,个会打网球的人都会打另外一种球,(,指篮球或排球,),，求不会打这三种球的人数。,解：,设会打排球、网球、篮球的学生集合分别为,A,，,B,和,C,，则有,A=12,，,B=6,，,C=14,，,S=25,A,C,=6,，,B,C,=5,，,A,BC,=2,56,现在求,A,B,，因为会打网球的人都会打另一种球，即篮球和排球，而其中会打篮球的有,5,人，那么另一个人肯定会打排球但不会打篮球，再加上会打三种球的,2,人，共有,3,人会打排球和网球，即,A,B,=3,，根据容斥定理有,A,BC,=25-,（,12+6+14,）,+,（,3+6+5,）,-2=5,3,2,4,排球,12,篮球,14,网球,6,1,5,5,不会打三种球人数为：,25-(12+5+3)=5,57,课堂练习：证明下列等式,58,第四章 二元关系和函数,说起关系这个词，对我们并不陌生，世界上存在着各种各样的关系，人与人之间的,“,同志,”,关系；,“,同学,”,关系；,“,朋友,”,关系；,“,师生,”,关系；,“,上下级,”,关系；,“,父子,”,关系；两个数之间有,“,大于,”,关系；,“,等于,”,关系和,“,小于,”,关系；两个变量之间有一定的,“,函数,”,关系；计算机内两电路间有导线,“,连接,”,关系；程序间有,“,调用,”,关系等等。所以对关系进行深刻的研究，对数学与计算机科学都有很大的用处。,59,集合的笛卡尔积与二元关系,由两个元素,x,y,（允许,x=y,）按一定顺序排列成,的二元组叫做一个,有序对或序偶,，记作,其中,x,是,它的,第一元素,，,y,是它的,第二元素,。,有序对,具有以下性质：,(1),当,xy,时，,(2)=,x=w,y=v,例,：已知,=,，求,x,和,y,。,解：由有序对相等的充要条件得,x+3=y+7,y-2=3y-x,解得,x=6,y=2,。,60,一个,有序,n,元组,(n3),是一个有序对，其中第一个元素是一个有序,n-1,元组，一个有序,n,元组记作,即,=,x,n,例：,空间直角坐标系中点的坐标,等都是有序,3,元组。,n,维空间中点的坐标或,n,维向量都是有序,n,元组。,形式上也可以把,看成有序,1,元组。,61,设,A,，,B,为集合，用,A,中元素为第一元素，,B,中元素为第二元素构成有序对。所有这样的有序对组成的集合叫做,A,和,B,的,笛卡儿积,，记作,AB,。,笛卡儿积的符号化表示为：,AB=|x A,yB,例,：若,A=1,2,B=a,b,c,则,AB=,BA=,易知：若,|A|=m,(,即集合,A,的元素的个数,),|B|=n,则,|AB|=|BA|=m n,62,有序对就是有顺序的数组,，如,，,x,y,的,位置是确定的，不能随意放置。,注意,：有序对,，以,a,b,为元素的集合,a,b=b,a,；有序对,(a,a),有意义，而集合,a,a,不成立。,笛卡儿积是一种集合合成的方法,，把集合,A,，,B,合成集合,AB,，规定,AB,x,A,y,B,。,由于有序对,中,x,y,的位置是确定的，因此,AB,的记法也是确定的，不能写成,BA,。,笛卡儿积也可以多个集合合成,A,1,A,2,A,n,。,笛卡儿积的运算性质。,63,笛卡儿积的性质：,1,、对任意集合,A,，根据定义有,A =A=,2,、一般来说，笛卡儿积不满足交换律，即,ABBA,（当,A B B ,、,A ,时）,3,、笛卡儿积不满足结合律，即,(AB)CA(B C),（当,A,B,C,时）,4,、笛卡儿积运算对并和交运算满足分配律，即,A(BC)=(AB)(A C),(BC)A=(BA)(C A),A(BC)=(AB)(A C),(BC)A=(BA)(C A),64,例：,证明,(BC)A=(BA)(C A),对于,(BC)A,x,(B C),y,A,x,B,x,C,y,A,x,B,x,C,y,A y,A,(x,B,y,A),(x,C y,A),B A,C A,(BA)(C A),(BC)A=(BA)(C A),65,例,：设,A,，,C,，,B,，,D,为任意集合，,判断以下命题是否为真，并说明理由。,(1)AB=AC=B=,C,。,(2)A-(BC)=(A-B)(A-C),。,(3),存在集合,A,使得,A,A A,。,解：,(1),不一定为真。反例,A=,B,、,C,为任意不相,等的非空集合。,(2),不一定为真。反例,A=1,B=2,C=3.,(3),为真。当,A=,时成立。,66,设,A,1,A,2,A,n,是集合,(n2),它们的,n,阶笛卡儿积记作,A,1,A,2,A,n,，其中,A,1,A,2,A,n,=,|x,1,A,1,x,2,A,2,x,n,A,n,。,当,A,1,=A,2,=A,n,=A,时,将起,n,阶笛卡儿积记作,A,n,例,，,A=a,b,则：,A,3,=AAA=,a,b,a,b,a,b,=,。,67,例,：设集合,A=a,b,B=1,2,3,C=d,求,ABC,，,BA,。,解：,先计算,AB,ABC,d,BA,。,68,例：,设集合,A,1,2,求,AP(A),。,解：,P(A)=,1,2,1,2,AP(A),1,2,1,2,1,2=,69,如果一个集合符合以下条件之一：,(1),集合非空，且它的元素都是有序对,(2),集合是空集,则称该集合为一个,二元关系,，记作,R,，简称为关系。,对于二元关系,R,，若,R,可记作,xRy;,如果,R,则记作,xRy,。,例,：,R,1,=,aR,1,b,1R,1,2,。,70,二元关系,是两种客体之间的联系，例如某学生,学习语文、数学、外语，表示为：,A,语文,数学,外语,功课的成绩分四个等级，记作,B,A,，,B,，,C,，,D,于是该生成绩的全部可能为,A,B,A,B,而该生的实际成绩,P,P,是,A,B,的一个子集，它表示了功课与其成绩的一种关系。,由此可见：,两个集合之间的二元关系，实际上就是两个元素之间的某种相关性。,71,设,A,，,B,为集合，,AB,的任何子集所定义的,二元关系叫做从,A,到,B,的,二元关系,；,特别当,A=B,时则叫做,A,上的,二元关系,。,例：,若,A=a,b,，,B=1,2,3,，则,A,B=,令,R,1,=,R,2,=,R,3,=,。,因为,R,1,A,B,，,R,2,A,B,，,R,3,A,B,，所以,R,1,R,2,和,R,3,均是由,A,到,B,的二元关系。,72,又例：若,A=a,b,，,B=1,2,3,，则,B,A,=,令,R,4,=,R,5,=,因为,R,4,B,A,，,R,5,B,A,，,所以,R,4,和,R,5,均是由,B,到,A,的关系。,又,BB,=,。,令,R,6,=,，,R,7,=,因为,R,6,B,B,，,R,7,B,B,，,所以,R,6,和,R,7,均是集合,B,上,的关系。,73,若集合,|A|=n,则集合,A,上的二元关系有多少个？,答：,|A|=n,，则,|A A|=n,2,A A,的任一个子集就是,A,上的二元关系，即,P(A)=2,n,个。,例,A=1,2,则,A A,有,2,n,个不同的二元关系；,AA=1,21,2=,。,AA,的任一个子集就是,A A,的幂集，即,P(A),P(A)=,74,三类特殊的关系,空关系：,对于任何集合,A,，空集,是,A A,的,子集，称作,A,上的,空关系；,全关系：,定义,E,A,=|xA,y,A=AA,为,全域关系；,恒等关系：,定义,I,A,=|xA,为,A,上,恒等关系。,例：,若,A=1,2,3,，则,E,A,=,I,A,=,。,75,例：,设,A=1,2,3,4,，请表示下列关系。,(1)R=,|x,是,y,的倍数,(2)R=,|(x-y),2,A,(3)R=,|x,除,y,是素数,(4)R=,|xy,解：,(1)R=,；,(2)R=,；,(3)R=,；,(4)R=,76,关系表示法,有穷集合上的二元关系的三种表示方法：,集合表示法（前已使用）,关系矩阵法,关系图,关系矩阵是表示关系的另一种有效的方法，其优点是可以利用矩阵作为研究关系的手段，而且这样做便于计算机进行处理。,77,设,R,：,A,B,，,A,和,B,都是有限集，且,|,A,|,=n,|B|,=m,A,B,中的元素已按一定的次序排列若,A=x,1,x,2,x,n,B=y,1,y,2,y,m,且,R,A,B,若,则称矩阵,M(R),=(,r,ij,),n,m,为,R,的,关系矩阵,。,关系矩阵法,78,0 1 1 1,M,R,=0 0 1 1,0 0 0 1,0 0 0 0,例,A=1,2,3,4,R,为,A,上的小于关系，,则,R=,R,的关系矩阵为：,1 2 3 4,1 2 3 4,79,例,:,设集合,A,2,3,4,B=8,9,12,14,。,R,是由,A,到,B,的二元关系，定义：,R=,|,a,整除,b,写出,R,的表达式和关系矩阵。,解,：,R=,R,的关系矩阵：,80,关系图,关系图是表示关系的一种直观形象的方法，设,R,：,A,B,，,A,和,B,都是有限集，,A=x,1,x,2,x,n,B=y,1,y,2,y,m,关系,R,的有序对,可用图中从结点,x,i,到,y,j,的有向边表示，这样即可将关系用图表示之。,例,设,R:A,B,，,A=x,1,x,2,x,3,x,4,B=y,1,y,2,y,3,R=,，,R,的关系如下图所示,x,1,x,2,x,3,x,4,y,1,y,2,y,3,81,设,R,是在,A,上的二元关系，,A=x,1,x,2,x,n,关系,R,的有序偶,可用图中从结点,x,i,到,x,j,的有向边表示，这样即可将关系用图表示之。,例：,设,R:A,A,，,A=a,b,c,d,R=,R,的关系如下图所示：,a,b,c,d,82,例：,设集合,A=a,b,c,d,R,是,A,上的关系,R=,试以关系矩阵和关系图来表示关系,R,。,解：,（,1,）关系矩阵为：,（,2,）关系图为：,83,关系的运算,（,1,）,R,中所有的有序对的第一元素构成的集合称为,R,的,定义域,，记作,domR,。,domR=x|,y(,R,（,2,）,R,中所有的有序对的第二元素构成的集合称为,R,的,值域,，记作,ranR,。,ranR=y|,x,R,（,3,）,R,的定义域和值域的并集称为,R,的,域,，记作,fldR,。,fldR=domR,ranR,例：,设,R=,则,domR=1,，,2,，,3,ranR=1,，,2,，,3,，,4,fldR=1,，,2,，,3,，,4,84,限制关系,设,R,为二元关系，,A,是集合,（,1,）,R,在,A,上的限制，记作,R,A,其中,R,A=|xRy,x,A,（,2,）,A,在,R,下的象，记作,RA,，其中,RA=ran(R,A),例,：设集合,A=1,2,3,4,R,是,A,上的关系,R=,集合,B=1,2,4,试求,R,B,及,RB,。,解：,R,B=,；,RB=1,，,3,，,4,。,85,逆运算,设,R,为二元关系，称 为,R,的逆关系，其中,=|,R,定理,4.1,设,F,是任意关系，则,（,1,）（,2,）,证明：,（,1,）对任意的,86,（,2,）对任意的,y,对任意的,x,87,复合运算,设,F,G,为二元关系,G,对,F,的右复合记作,F,G,其中,F,G=|,t(,F,G,。,说明：,（,1,）本书采用右复合的规则，而有的教材采用左复合规则，两者都可行，只是需要注意它们的区别，从变换的角度来说，,G,对,F,的右复合是先,F,变换后,G,变换，而,G,对,F,的左复合是先,G,变换后,F,变换。,（,2,）一般来说，并没有,F,G,等于,G,F,，请读者仔细注意其区别。,例：,设,F=,G=,则求,F,F,，,G,G,，,F,G,和,G,F,。,解：,F,F=,，,G,G=,F,G=G,F=,。,88,例：,设有集合,A=4,5,8,15,B=3,4,5,9,11,C=1,6,8,13,F,是由,A,到,B,的关系,G,是由,B,到,C,的关系,分别定义为,F=,|b-a|=1,G=|b-c|=2,或,|b-c|=4,求合成关系,G,F,和,F,G,解：,先求,G,F,由题意知,F=,；,G=,；,G,F=,。,89,定理：,设,F,、,G,、,H,是任意关系,则,(1)(F,-1,),-1,=F,(2)dom(F,-1,)=ranF,ranF,-1,=domF,(3)(F,G),H=F,(G,H),(4)(F,G),-1,=G,-1,F,-1,证明,:,(1),任取,由逆的定义有,(F,-1,),-1,F,-1,F,(F,-1,),-1,=F,(2),任取,x,x,ran F,-1,y(,F,-1,),y(,F),x,dom F,ran F,-1,=dom F,同理可证,dom(F,-1,)=ran F,90,证明,:,(3),任取,(F,G),H,t(,F,G,H),t s(,F,G,H),s(,F,t,(,G,H),s(,F,G,。,H),F,(,G,H),(4),任取,(F,G),-1,F,G,t(,F,G),t(,G,-1,F,-1,),G,-1,F,-1,91,定理：,设,F,、,G,、,H,是任意关系,则,(1)F,(GH)=F,G F,H,(2)(GH),F=G,F H,F,(3)F,(GH),F,G F,H,(4)(GH),F,G,F H,F,证明,:,(1),任取,F,(GH),t(,F,G H),t(,F,(,G,H),t(,F,G),(,F,H),t(,F,G),t(,F,H),F,G,F,H,F,G F,H,92,证明,:,(3),任取,F,(GH),t(,F,G H),t(,F,G,H),t(,F,G),(,F,H),=,t(,F,G),t(,F,H),F,G,F,H,F,G F,H,93,本定理对有限个关系的并和交都成立。,R,(R,1,R,2,R,n,)=R,R,1,R,R,2,R,R,n,(R,1,R,2,R,n,),R=R,1,RR,2,RR,n,R,R,(R,1,R,2,R,n,),R,R,1,R,R,2,R,R,n,(R,1,R,2,R,n,),R,R,1,RR,2,RR,n,R,94,幂运算：,设,R,是,A,上的关系,n,为自然数，则,R,的,n,次幂规定如下：,(1)R,0,=|xA,(2)R,n,=R,n-1,R n1,由定义可以知道,R,0,就是,A,上的恒等关系,I,A,，不难证,明下面的等式,R,R,0,=R=R,0,R,。,由这个等式立即可以得到,R,1,=R,0,R=R,例：,设,A=a,b,c,d,R=,求,R,0,，,R,1,，,R,2,，,R,3,，,R,4,和,R,5,解：,R,0,=,R,1,=R,0,R=,=,。,95,R,2,=R,R=,=,R,3,=R,2,R =,=,R,4,=R,3,R=,=,R,5,=R,4,R=,=,96,定理：,设,R,是,A,上的关系,m,n,为自然数，,则下面的等式成立,(1)R,m,R,n,=R,m+n,(2)(R,m,),n,=R,mn,证明：,(1),任给,m,，对,n,作归纳法。,n=0,时，,R,m,R,0,=R,m,=R,m+0,。假设,R,m,R,n,=R,m+n,，那么,R,m,R,n+1,=R,m,(R,n,R,1,)=,(R,m,R,n,),R,1,=R,m+n,R,1,=R,m+n+1,=R,m+(n+1),。,(2),任给,m,，对,n,作归纳法。,n=0,时，,(R,m,),0,=R,0,=R,m,0,。假设,(R,m,),n,=R,mn,。那么,(R,m,),n+1,=(R,m,),n,R,m,=R,mn,R,m,=R,mn+m,=R,m(n+1),97,例,:,已知集合,A=a,b,c,d,A,上的关系,R=,，求 。,解：,法一,：由复合定义知,=,=,法二,：关系,R,矩阵为,=,=,98,法三：,R,的关系图为,的关系图为,的关系图为,99,定理,A,为,n,元集,R,为,A,上的关系,则存在自然数,s,和,t,，,使得,R,s,=R,t,证明：,因为,A,为,n,元集，所以集合,A,上的关系为有限,N=,个，而关系序列,存在无限多个关系，故存在自然数,s,和,t,，使得,R,s,=R,t.,。,100,设,R,是,A,上的关系，,R,的性质主要有以下,5,种,:,(1),自反性：,若,x(x,A,R,),则称,R,在,A,上是,自反,的。,也就是说，对,R,A,A,，若,A,中每个,x,，都有,xRx,，则称,R,是自反的，即,A,上关系,R,是自反的,x(x,A,xRx),。,该定义表明了，在自反的关系,R,中，除其它有序对外，必须包括有全部由每个,x,A,所组成的元素相同的有序对。,例如：设,A=1,2,3,R,是,A,上的关系，,R=,则,R,是自反的,关系的性质,101,(2,),反自反性：,若,x(x,A,R,),，则称,R,在,A,上是,反自反,的。,也就是说，对,R,A,A,，若,A,中每个,x,，有,xRx,，则称,R,是反自反的，即,A,上关系,R,是反自反的,x(x,A,xRx),该定义表明了，一个反自反的关系,R,中，不应包括有任何相同元素的有序对。,例如,：设,A=1,2,3,，,R,是,A,上的关系，,R=,R,是反自反的,。,102,应该指出：,任何一个不是自反的关系，未必是反自反的；,任何一个不是反自反的关系，未必是自反的。,这就是说，存在既不是自反的也不是反自反的二元关系。,例,：设,A=1,2,3,R,是,A,上的关系，,R=,缺少,则,R,是既不是自反的，也不是反自反的。,103,(3),对称性：,若,x y(x,y,A,R,R,),则称,R,在,A,上是,对称的,。,也就是说,对,R,A,A,对,A,中每个,x,和,y,若,xRy,则,yRx,称,R,是对称的,即,A,上关系,R,是对称的,(,x)(,y)(x,y,A,xRyyRx),该定义表明了，在表示对称的关系,R,的有序对集合中，,若有有序对,，则必定还会有,。,例,：设,A=1,2,3,R,是,A,上的关系，,R,4,=,则,R,是对称的。,104,(4),反对称性,：若,x y(x,y,A,R,xy ,R,),则称,R,在,A,上是,反对称的,。,也就是说，对,R,A,A,，对,A,中每个,x,和,y,，若,xRy,且,yRx,，则,x=y,，称,R,是反对称的，即,A,上关系,R,是反对称的,(,x)(,y)(x,y,A,xRy,yRxx=y),该定义表明了，在表示反对称关系,R,的有序对集合中，若存在有序对,和,，则必定是,x=y,。或者说，在,R,中若有有序对,，则除非,x=y,，否则必定不会出现,。,例,：设,A=1,2,3,R,=,是,A,上,的关系，,则,R,是反对称的。,105,注意：,有些关系既是对称的又是反对称的；,有的关系既不是对称的又不是反对称的,。,例：,设,A=1,2,3,R,6,R,7,是,A,上的关系，,R,6,=,R,7,=,则,R,6,是对称的，也是反对称的,R,7,既不,是对称的又不是反对称的,106,课堂问题：,设,A=1,2,3,R,1,R,2,R,3,和,R,4,是,A,上的关系,R,1,=,，,R,2,=,，,R,3,=,，,R,4,=,试说明,R,1,R,2,R,3,和,R,4,是否为,A,上的对称和反对称关系。,107,(5),传递性,：,xyz(x,y,z,A,R,R,R,),则称,R,在,A,上是,传递的关系,。,也就是说,对,R,A,A,，对于,A,中每个,x,y,z,，若,xRy,且,yRz,，则,xRz,，称,R,是传递的，即,A,上关系,R,是传递的,(,x)(,y)(,z)(x