离散数学集合论部分

第二部分集合与关系,对于从事计算机科学工作的人们来说，集合论是必不可少的基础知识。例如程序设计语言、数据结构、形式语言等都离不开子集、幂集、集合的分类等概念。集合成员表和范式在逻辑设计、定理证明中也都有重要应用。本部分从集合的直观概念出发，介绍了集合论中的一些基本概念和基本理论。,集合论是研究集合的一般性质的数学分支，它研究集合不依赖于组成它的事物的特性的性质。集合论总结出由各种对象构成的集合的共同性质，并用统一的方法来处理。集合论的特点是研究对象的广泛性，集合是各种不同对象的抽象，这些对象可以是数或图形，也可以使任意其它事务。,1.二十六个英文字母可以看成是一个集合；2.所有的自然数看成是一个集合；3.重庆邮电大学计算机学院2010级的本科学生可以看成是一个集合；4.这间教室中的所有座位可以看成是一个集合。,例:,集合的基本概念,组成一个集合的那些对象或单元称为这个集合的元素。通常，用小写的英文字母a,b,c,表示集合中的元素。元素可以是单个的数字也可以是字母，还可以是集合。如：A=a,c,b;B=a,b,c,集合的元素,元素与集合的属于关系：,设A是一个集合，a是集合A中的元素，元素与集合的关系：属于；不属于若a是集合A中的元素记为aA，读作a属于A；若a不是集合A中的元素，则记为aA，读作a不属于A。例如：A是正偶数集合，则2A，4A，6A；而1A，3A，19A。,特别注意：集合并不决定于它的元素展示方法。集合的元素被重复或重新排列，集合并不改变，即a,a,b,c,d,c=a,b,c,d。集合的元素可以是具体事物，可以是抽象概念，也可以是集体，如一本书，一支笔；集合1,2,3可以是集合B=一本书，一支笔，1,2,3的元素。特别地，以集合为元素的集合称为集合族或集合类如A=1,2,3,8,9,6。集合中元素之间可以有某种关联，也可以彼此毫无关系。,有限集A中所含元素的个数称为集合的元数。记作：|A|如：A=1,3,2,4,5,9则|A|=6；设A是所有英文字母组成的集合，则A=26。特别，|=0,集合的元素数,列举法(列元素法)：将集合中的元素一一列举，或列出足够多的元素以反映集合中元素的特征，例如：V=a,b,c,d,e或B=1,2,3,4,5,6,。描述法(谓词表示法):将集合元素的条件或性质用文字或符号在花括号内竖线后面表示出来。A=x|关于x的一个命题P;如：B=x|0x10;B=x|x=a2,a是自然数。,集合的表示法,E,A,a,e,文氏图用一个大的矩形表示全集，在矩形内画一些圆或其它的几何图形，来表示集合，有时也用一些点来表示集合中的特定元素。例如：集合A=a,b,c,d,e，用文氏图表示如下:,d,c,b,几类特殊集合:N=0,1,2,3,，即自然数集合。Z=,-2,-1,0,1,2,3,，即整数集合。Z+=1,2,3,，即正整数集合。Q=有理数集合。R=实数集合。C=复数集合。,确定性；互异性；无序性；多样性；,集合的特征,任何一个对象，或者是这个集合的元素，或者不是，二者必居其一；例如：A=x|x是自然数，且x100；B=x|x+1=3；C=x|x是大学生。,确定性,集合中任何两个元素都是不同的，即集合中不允许出现重复的元素。例如：集合A=a,b,c,c,b,d，实际上，应该是A=a,b,c,d。再如1,2,3,2,4=1,2,3,4。,互异性,集合与其中的元素的顺序无关；例如：集合a,b,c,d,e、d,c,e,a,b、e,c,d,b,a，都是表示同一个集合。集合4,2,1,3=1,2,3,4。,无序性,集合中的元素可以是任意的对象，相互独立，不要求一定要具备明显的共同特征。例如：A=a,a,a,b,a,1；A=1,a,*,-3,a,b,x|x是汽车,地球注意:对于任何集合A,都有AA。,多样性,设A，B是两个集合，若B的元素都是A的元素，则称B是A的子集，也称A包含B，或B被A包含，记以BA，或AB。若BA，且AB，则称B是A的真子集，也称A真包含B，或B真包含于A，记以AB，或BA。,子集：,例3.1设A=a,b,c,a,a,b试判断下列表达式正确与否。（1）aA（2）aA（3）aA（4）A（5）A（6）bA（7）bA（8）bA（9）a,bA(10)a,bA(11)cA(12)cA(13)cA(14)a,b,cA。,解：(4)，(7)，(11)，(13),(14)错误。,例3.2对于任意集合A,B和C,下述论断是否正确（1）若AB,BC则AC（2）若AB,BC则AC（3）若AB,BC则AC,解：（1）（2）（3）对(3)举反例A=,B=1,C=1。,例3.3设A=1,2,3,4,5,6,7,8下列选项正确的是（3）；（1）1A（2）1,2,3A（3）4,5A（4）A例3.4下列各选项错误的是（2）；（1）（2）（3）（4）例3.5在0_之间填上正确的符号：（4）（1）=（2）（3）（4）,当两个集合A和B的元素完全一样，即A，B实际上是同一个集合时，则称集合A，B相等，记为A=B。符号化表示为：A=BABBA例：设A=x|x是偶数，且0B=C。(2)A-(BC)=(A-B)(A-C)。(3)存在集合A,使得AAA。,解：(1)不一定为真。反例A=,B、C为任意不相等的非空集合。(2)不一定为真。反例A=1,B=2,C=3.(3)为真。当A=时成立。,设A1,A2,An,是集合(n2),它们的n阶笛卡儿积记作A1A2An，其中A1A2An=|x1A1x2A2xnAn。当A1=A2=An=A时,将起n阶笛卡儿积记作An例，A=a,b,则：A3=AAA=a,ba,ba,b=,。,例：设集合A=a,b,B=1,2,3,C=d,求ABC，BA。解：先计算AB,ABC,d,BA,。,例：设集合A1,2,求AP(A)。解：P(A)=,1,2,1,2AP(A)1,2,1,2,1,2=,如果一个集合符合以下条件之一：(1)集合非空，且它的元素都是有序对(2)集合是空集则称该集合为一个二元关系，记作R，简称为关系。对于二元关系R，若R,可记作xRy;如果R,则记作xRy。例：R1=,aR1b,1R12。,二元关系是两种客体之间的联系，例如某学生学习语文、数学、外语，表示为：A语文,数学,外语功课的成绩分四个等级，记作BA，B，C，D于是该生成绩的全部可能为ABAB,而该生的实际成绩P,P是AB的一个子集，它表示了功课与其成绩的一种关系。由此可见：两个集合之间的二元关系，实际上就是两个元素之间的某种相关性。,设A，B为集合，AB的任何子集所定义的二元关系叫做从A到B的二元关系；特别当A=B时则叫做A上的二元关系。例：若A=a,b，B=1,2,3，则AB=,令R1=,R2=,R3=。因为R1AB，R2AB，R3AB，所以R1,R2和R3均是由A到B的二元关系。,又例：若A=a,b，B=1,2,3，则BA=,令R4=,R5=,因为R4BA，R5BA，所以R4和R5均是由B到A的关系。又BB=,。令R6=，,R7=,因为R6BB，R7BB，所以R6和R7均是集合B上的关系。,若集合|A|=n,则集合A上的二元关系有多少个？答：|A|=n，则|AA|=n2,AA的任一个子集就是A上的二元关系，即P(A)=2n个。,例A=1,2则AA有2n个不同的二元关系；AA=1,21,2=,。AA的任一个子集就是AA的幂集，即P(A)P(A)=,三类特殊的关系空关系：对于任何集合A，空集是AA的子集，称作A上的空关系；全关系：定义EA=|xAyA=AA为全域关系；恒等关系：定义IA=|xA为A上恒等关系。例：若A=1,2,3，则EA=,IA=,。,例：设A=1,2,3,4，请表示下列关系。(1)R=|x是y的倍数(2)R=|(x-y)2A(3)R=|x除y是素数(4)R=|xy,解：(1)R=,；(2)R=,；(3)R=,；(4)R=,关系表示法有穷集合上的二元关系的三种表示方法：集合表示法（前已使用）关系矩阵法关系图关系矩阵是表示关系的另一种有效的方法，其优点是可以利用矩阵作为研究关系的手段，而且这样做便于计算机进行处理。,设R：AB，A和B都是有限集，且|A|=n,|B|=m,A,B中的元素已按一定的次序排列若A=x1,x2,xn,B=y1,y2,ym且RAB,若则称矩阵M(R)=(rij)nm为R的关系矩阵。,关系矩阵法,0111MR=001100010000,例A=1,2,3,4,R为A上的小于关系，则R=,R的关系矩阵为：,1234,1234,例:设集合A2,3,4,B=8,9,12,14。R是由A到B的二元关系，定义：R=|a整除b写出R的表达式和关系矩阵。解：R=,R的关系矩阵：,关系图关系图是表示关系的一种直观形象的方法，设R：AB，A和B都是有限集，A=x1,x2,xn,B=y1,y2,ym关系R的有序对可用图中从结点xi到yj的有向边表示，这样即可将关系用图表示之。例设R:AB，A=x1,x2,x3,x4,B=y1,y2,y3R=,，R的关系如下图所示,x1,x2,x3,x4,y1,y2,y3,设R是在A上的二元关系，A=x1,x2,xn关系R的有序偶可用图中从结点xi到xj的有向边表示，这样即可将关系用图表示之。例：设R:AA，A=a,b,c,dR=,R的关系如下图所示：,a,b,c,d,例：设集合A=a,b,c,d,R是A上的关系R=,试以关系矩阵和关系图来表示关系R。,解：（1）关系矩阵为：,（2）关系图为：,关系的运算,（1）R中所有的有序对的第一元素构成的集合称为R的定义域，记作domR。domR=x|y(R（2）R中所有的有序对的第二元素构成的集合称为R的值域，记作ranR。ranR=y|xR（3）R的定义域和值域的并集称为R的域，记作fldR。fldR=domRranR,例：设R=,则domR=1，2，3ranR=1，2，3，4fldR=1，2，3，4,限制关系设R为二元关系，A是集合（1）R在A上的限制，记作RA,其中RA=|xRyxA（2）A在R下的象，记作RA，其中RA=ran(RA),例：设集合A=1,2,3,4,R是A上的关系R=,集合B=1,2,4,试求RB及RB。解：RB=,；RB=1，3，4。,逆运算,设R为二元关系，称为R的逆关系，其中=|R定理4.1设F是任意关系，则（1）（2）,证明：（1）对任意的,（2）对任意的y,对任意的x,复合运算,设F,G为二元关系G对F的右复合记作FG,其中FG=|t(FG。,说明：（1）本书采用右复合的规则，而有的教材采用左复合规则，两者都可行，只是需要注意它们的区别，从变换的角度来说，G对F的右复合是先F变换后G变换，而G对F的左复合是先G变换后F变换。（2）一般来说，并没有FG等于GF，请读者仔细注意其区别。,例：设F=,G=,则求FF，GG，FG和GF。解：FF=，GG=,FG=GF=。,例：设有集合A=4,5,8,15,B=3,4,5,9,11C=1,6,8,13,F是由A到B的关系,G是由B到C的关系,分别定义为F=|b-a|=1G=|b-c|=2或|b-c|=4求合成关系GF和FG解：先求GF,由题意知F=,；G=,；GF=,。,定理：设F、G、H是任意关系,则(1)(F-1)-1=F(2)dom(F-1)=ranF,ranF-1=domF(3)(FG)H=F(GH)(4)(FG)-1=G-1F-1证明:(1)任取,由逆的定义有(F-1)-1F-1F(F-1)-1=F(2)任取x,xranF-1y(F-1)y(F)xdomFranF-1=domF同理可证dom(F-1)=ranF,证明:(3)任取,(FG)Ht(FGH)ts(FGH)s(Ft(GH)s(FG。H)F(GH)(4)任取,(FG)-1FGt(FG)t(G-1F-1)G-1F-1,定理：设F、G、H是任意关系,则(1)F(GH)=FGFH(2)(GH)F=GFHF(3)F(GH)FGFH(4)(GH)FGFHF证明:(1)任取,F(GH)t(FGH)t(F(GH)t(FG)(FH)t(FG)t(FH)FGFHFGFH,证明:(3)任取,F(GH)t(FGH)t(FGH)t(FG)(FH)=t(FG)t(FH)FGFHFGFH,本定理对有限个关系的并和交都成立。R(R1R2Rn)=RR1RR2RRn(R1R2Rn)R=R1RR2RRnRR(R1R2Rn)RR1RR2RRn(R1R2Rn)RR1RR2RRnR,幂运算：设R是A上的关系,n为自然数，则R的n次幂规定如下：(1)R0=|xA(2)Rn=Rn-1Rn1由定义可以知道R0就是A上的恒等关系IA，不难证明下面的等式RR0=R=R0R。由这个等式立即可以得到R1=R0R=R例：设A=a,b,c,d,R=,求R0，R1，R2，R3，R4和R5解：R0=,R1=R0R=,=,。,R2=RR=,=,R3=R2R=,=,R4=R3R=,=,R5=R4R=,=,定理：设R是A上的关系,m,n为自然数，则下面的等式成立(1)RmRn=Rm+n(2)(Rm)n=Rmn证明：(1)任给m，对n作归纳法。n=0时，RmR0=Rm=Rm+0。假设RmRn=Rm+n，那么RmRn+1=Rm(RnR1)=(RmRn)R1=Rm+nR1=Rm+n+1=Rm+(n+1)。(2)任给m，对n作归纳法。n=0时，(Rm)0=R0=Rm0。假设(Rm)n=Rmn。那么(Rm)n+1=(Rm)nRm=RmnRm=Rmn+m=Rm(n+1),例:已知集合A=a,b,c,d,A上的关系R=,，求。,解：法一：由复合定义知,法二：关系R矩阵为,=,=,法三：R的关系图为,的关系图为,的关系图为,定理A为n元集,R为A上的关系,则存在自然数s和t，使得Rs=Rt证明：因为A为n元集，所以集合A上的关系为有限N=个，而关系序列存在无限多个关系，故存在自然数s和t，使得Rs=Rt.。,设R是A上的关系，R的性质主要有以下5种:(1)自反性：若x(xAR),则称R在A上是自反的。也就是说，对RAA，若A中每个x，都有xRx，则称R是自反的，即A上关系R是自反的x(xAxRx)。该定义表明了，在自反的关系R中，除其它有序对外，必须包括有全部由每个xA所组成的元素相同的有序对。例如：设A=1,2,3,R是A上的关系，R=,则R是自反的,关系的性质,(2)反自反性：若x(xAR)，则称R在A上是反自反的。也就是说，对RAA，若A中每个x，有xRx，则称R是反自反的，即A上关系R是反自反的x(xAxRx)该定义表明了，一个反自反的关系R中，不应包括有任何相同元素的有序对。例如：设A=1,2,3，R是A上的关系，R=,R是反自反的。,应该指出：任何一个不是自反的关系，未必是反自反的；任何一个不是反自反的关系，未必是自反的。这就是说，存在既不是自反的也不是反自反的二元关系。例：设A=1,2,3,R是A上的关系，R=,缺少则R是既不是自反的，也不是反自反的。,(3)对称性：若xy(x,yARR),则称R在A上是对称的。也就是说,对RAA,对A中每个x和y,若xRy,则yRx,称R是对称的,即A上关系R是对称的(x)(y)(x,yAxRyyRx)该定义表明了，在表示对称的关系R的有序对集合中，若有有序对，则必定还会有。例：设A=1,2,3,R是A上的关系，R4=,则R是对称的。,(4)反对称性：若xy(x,yARxyR),则称R在A上是反对称的。也就是说，对RAA，对A中每个x和y，若xRy且yRx，则x=y，称R是反对称的，即A上关系R是反对称的(x)(y)(x,yAxRyyRxx=y)该定义表明了，在表示反对称关系R的有序对集合中，若存在有序对和，则必定是x=y。或者说，在R中若有有序对，则除非x=y，否则必定不会出现。例：设A=1,2,3,R=,是A上的关系，则R是反对称的。,注意：有些关系既是对称的又是反对称的；有的关系既不是对称的又不是反对称的。例：设A=1,2,3,R6,R7是A上的关系，R6=,R7=,则R6是对称的，也是反对称的R7既不是对称的又不是反对称的,课堂问题：设A=1,2,3,R1,R2,R3和R4是A上的关系,R1=,，R2=,，R3=，R4=,试说明R1,R2,R3和R4是否为A上的对称和反对称关系。,(5)传递性：xyz(x,y,zARRR)则称R在A上是传递的关系。也就是说,对RAA，对于A中每个x,y,z，若xRy且yRz，则xRz，称R是传递的，即A上关系R是传递的(x)(y)(z)(x,y,zAxRyyRzxRz)该定义表明了，在表示可传递关系R的有序对集合中，若有和，则必有。,例：设A=1,2,3,4,5,A上的关系R为R=|a-b是偶数用列举法表示RR是否是可传递的？解:R=,对于任意的a,b,cA若a-b=2m,b-c=2n,则a-c=(a-b)+(b-c)=2(m+n)也是偶数。因此A是可传递的。RRR,例：设A=1,2,3,R1,R2和R3是A上的关系，R1=,，R2=,，R3=。试说明R1,R2和R3是否为A上的传递关系。解：其中R1，R3是传递关系，R2不是传递关系。,例：设A=1,2,3,4,5,6,7,8，R是A上的关系，R=|x,yAx+y=9说明R具有哪些性质。解：R=,，,易知R既不是自反也不是反自反的；是对称的R不是反对称的；R不是传递的。,性质的判定,定理设R为A上的关系，则（1）R在A上自反当且仅当IAR。（2）R在A上反自反当且仅当RIA=。（3）R在A上对称当且仅当R=R-1。（4）R在A上反对称当且仅当RR-1IA。（5）R在A上传递当且仅当RRR。,证明：（1）必要性：若R在A上自反，则对xA有R，所以IAR。充分性：若IAR，则xA,有IAR，则R在A上自反。,2）必要性：若R在A上反自反，则对xA有R，所以RIA=。充分性：若RIA=，则对xA有R，否则，不妨设yA有R,则有RIA,与已知矛盾,所以R在A上反自反。,3）必要性：若R在A上对称，下证R=。对任意xA,yA,若R,即R=R-1成立。,充分性：若R=R-1,则对任意xA,yA,若R,则R-1,则有R，则R在A上对称成立。,（4）必要性：若R在A上反对称，任取则有,充分性，若RR-1IA，任取则有,（5）必要性：若R在A上传递，任取则有,充分性：若RRR成立，任取R，R，则有,关系性质的几种表示,R=,例：判断下图中关系的性质，并说明理由。,（3）,（2）,（1）,解：（1）该关系图有的顶点有环，有的顶点没有环，故关系即不是自反关系，也不是反自反关系；关系图中，无双边，故应该是反对称关系；该关系图从顶点a到顶点b有边，顶点b到顶点c，但从顶点a到顶点c没有边，故该关系不是传递关系。,（2）该关系图每个顶点都有环，故关系是自反关系；在关系图中，无双边，故应该是反对称关系；该关系图从顶点a到顶点b有边，顶点b到顶点c，从顶点a到顶点c有边，故该关系是传递关系。（3）该关系图每个顶点都没有环，故关系是反自反关系；在关系图中，无双边，故应该是反对称关系；该关系图中没有两步间接到达的路径，故该关系是传递关系。,思考题：设A为集合，R1和R2是A上的关系，说明下面命题是否成立，若成立，则证明之，若不成立，则举例说明。R1和R2是A上的自反关系，则也是A上的自反关系。(2)R1和R2是A上的传递关系，则R1-R2也是A上的传递关系。,设R是非空集合A上的关系，R的自反(对称或传递)闭包是A上的关系R,使得R满足以下条件:(1)R是自反(对称或传递)的(2)RR(3)对A上的任何包含R的自反(对称或传递)关系R均有RR。一般将R的自反闭包记作r(R)；对称闭包记作s(R)；传递闭包记作t(R)。,关系的闭包,设R是非空集合A上的关系，则有(1)r(R)=RR0(2)s(R)=RR-1(3)t(R)=RR2R3此定理提供了一种集合表示形式下关系闭包的求解方法。,例：设A=a,b,c,d,在A的定义二元关系R=,则r(R)=RR0=,;s(R)=RR-1=,;t(R)=RR2R3(甚不方便),定理:设R是非空集合上的关系，则有,（1）r(R)=RR0（2）s(R)=RR-1（3）t(R)=RR2R3,证明：（1）IA=R0RR0，故RR0是自反的，且满足RRR0，设R是A上包含R的自反关系，则有RR和IAR，则必有RR0R。即证r(R)=RR0。,（3）先证RR2R3t(R)，我们只需证明对任意的正整数n，有Rnt(R)成立，下面采用数学归纳法证明之。i,当n=1时，有R1=Rt(R)。ii,若当n=k时，有Rkt(R),那么当n=k+1时，任取则有,（2）课堂练习。,综合i,ii，则证明：对任意的正整数n，有Rnt(R)成立。,下面再证t(R)R，,只需证明R传递。,任取R，R，则有,所以RR2R3传递，故结论得证。,闭包生成算法：,一、集合法,（1）r(R)=RR0（2）s(R)=RR-1（3）t(R)=RR2R3,二、关系矩阵法,三、关系图法,给出R的关系图G，设r(R),s(R),t(R)关系图分别为,则以G的顶点集为顶点集，在原图G上做以下相应操作，则可得闭包图。,在无环的顶点上加环。,单边加成双边，方向相反。,凡在图G中，若从出发经过若干步到达顶点则在中加一条从到的边，找遍所有的顶点，就得到图。,例：已知集合A=a,b,c,d,A上的关系R=,，求r(R)、s（R）、t(R)。,解：法一：集合法,=,=,r(R)=RR0=,，,s(R)=RR-1=,t(R)=RR2R3=RR2R3=,，,法二：关系矩阵,法三：r(R)的关系图为：,s(R)的关系图为：,t(R)的关系图为：,R,r(R),s(R),t(R）,例：设A=a,b,c,d,R=,画出R、r(R)、s（R）、t(R)的关系图。,等价关系,设R是非空集合A上的关系。若R是自反的、对称的和传递的,则称R是A上的等价关系。如果R是一个等价关系，若R,称x等价于y,记作xy。等价关系=自反性+对称性+传递性也就是说,若R,或aRb,称a等价b,记ab由于R是对称的，a等价b即b等价a，反之亦然，a与b彼此等价。,.,例：设有一个整数集Z上的关系R：R=|x-y可被3整除证明R是Z上等价关系。证：对每个xZ,x-x可被3整除，所以是自反的。对于x,yZ,如果x-y能被3整除，则y-x也能被3整除所以是对称的。对于x,yZ,如果有x-y，y-z均能被3整除，则x-z=(x-y)+(y-z)亦能被3整除，所以是传递的。综合起来，R是Z上等价关系。,例：设A=1，2，8如下定义A上的关系：R=|x,yAxy(mod3)。解：R=,，,，,，,R满足自反、对称和传递，所以，R是等价关系。,R的关系图为：,设R是非空集合A上的等价关系,对任一个xA,可以构造一个A的子集xRxR=y|yAxRy称xR为x关于R的等价类,简称为x的等价类,简记为x例：设A=1,2,3,4,5,6,7,8,R为A上的关系R=|x,yAx=y(mod3)其中,x=y(mod3)的含义就是x-y可以被3整除等价类为：1=4=7=1,4,7；2=5=8=2,5,8；3=6=3,6。,等价类,定理：设R是非空集合A上的等价关系，则（1）xA,x是A的非空子集；（2）x,yA如果xRy,则x=y；（3）x,yA如果R则x与y不交；（4）xxA=A。,证明：（1）由等价类的定义知道，xA,xA，又R自反，所以xx，即x非空。（2）任取z,若zx,则R,由R对称，则R,若R，由R传递，则有R,又由R对称，则R,所以zy，以上证明了xy。同理可证yx,从而x=y成立。,（3）反证：若x与y相交不空，不妨设zxy，则有R且R,由R对称性，传递性则有R与已知R矛盾，即假设错误，原命题成立。（4）先证xxAA,任取z,若zxxA,则存在xA且yx，又xA，则有yA,从而xxAA成立。（5）再证AxxA,任取zA,则zz,则有zxxA，从而AxxA成立。综合上述，有xxA=A成立。,设R为非空集合A上的等价关系，以R的所有等价类作为元素的集合称为A关于R的商集，记作A/R，其中A/R=xR|xA。,前面例题中的商集是：A/R=1，2，3=1，4，7，2，5，8，3，6。实际上我们可以得到更加推广的结论，设R为整数集上模n同余的等价关系，则可以得到其n个等价类：i=nz+i|zZ,i=0,1,n-1。则相应的商集为nz+i|zZ|i=0,1,n-1。,商集,设A为非空集合，若A的子集族（P（A）)，满足下面条件：（1）；（2）xy(x,yxyxy=)；（3）=A；则称是A上的一个划分，称中元为A上的划分块。,划分,例：设A=1,2,3,4,5,给定如下集合：=1，2，3，3,4，5；=1，2，3，4，5；=，1，2，3，4，5；=1，2，3，5；=1，2，3，4，5。,由以上定义不难知道，其中，是A的划分，其它都不是。,定理设是A上的一个划分，定义A上的一个关系R:R=|x,yAx与y在的同一分块中则R是A上的等价关系。,例：设A=a,b,c,d,e，A上的一个划分=a,b,c,d,e，求出A上的等价关系R,使得A/R等于该划分。解：R=,IA。,偏序关系,设R为非空集合A上的关系,如果R是自反的、反对称和传递的，则称R是A上的偏序关系。记“”，把集合A和A上的偏序关系“”一起称作偏序集，记作,（1）设R是一个偏序关系，若R,读作x小于或等于y，记为xy。若xy且xy，则记作xy，称x小于y。,注：,（2）此处y，不是比较数的大小，而是指按照定义的偏序关系，x排在y前面。,例：设A=a，b，c，证明集合P(A)上的“”关系为偏序。证明:(1)自反性任取XP(A)，则有XX,故关系“”自反。(2)对称性任取X，YP(A)，若XY且YX，则有X=Y，故关系“”反对称。(3)传递性任取X，Y，ZP(A)，若XY且YZ，则有XZ，故关系“”传递。综合（1），（2），（3）则得证R是A上的偏序关系。,例:集合A=2,3,6,8上的“整除”关系RR=,(x整除y）那么R有哪些关系？解：,RR是自反的又,R而,RR是反对称的x,y,zA,若R且R,则R由R有y|x=n由R有z|y=m将y=z|m代入y|x=n得z|x=mn即R(z|x=mn)R是可传递的。(事实上,R则,RR是可传递的）综上所述：R是偏序关系,例：设集合A18的正整数因子,为整除关系(x整除y）证明：是偏序关系。分析偏序关系只需验证自反性、反对称性和传递性。解:集合A1,2,3,6,9,18，整除关系为IA,容易验证IA，故有自反性；(a,b),ab,则(b,a)，故有反对称性x,y,zA,若且,则整除关系且是正整数因子x,y,zA有y|x=n由有z|y=my=z|m并将其代入上式z|x=mn所以具有传递性.是偏序关系。,设R是非空集合A上的偏序关系,对任意的x,yA,如果偏序xy或者yx成立,则称x与y是可比的,如果x是偏序集。那么对xA都有1x,所以1和1,2,3,4,5都是可比的,但是2不能整除3,3也不能整除2,所以2和3是不可比的,对于1和2来说,12,并且不存在zA使得1整除z并且z整除2,所以2盖住1,同样,4盖住2,但4盖不住1,因为124成立。显然,如果x与y不可比,则一定不会有x盖住y或y盖住x。,全序关系设为偏序集,若对任意的x,yA,x和y都可比,(即xy或yx)则称R为A上的全序关系,且称为全序集。例：A=1,2,3,4,5上的小于等于关系是全序关系,因为由前例知集合A上的小于等于关系是偏序关系,所以为偏序集。又因为对任意的x,yA,x,y均可比较大小,即xy或yx所以是全序关系。而整除关系亦为偏序集，但对任意的x,yA,x,y相互不能整除,所以不是全序关系。,哈斯图哈斯图的画法：在画偏序集的哈斯图时，首先适当排列A中元素的顺序。对于x,yA，若xy，则将x画在y的下方。其次考虑y是否盖住了x，若y盖住x，则用一条线段连接y和x。,也就是说分以下两步:(其中表示偏序关系)若xy，且xy，则将x画在y的下面。若xy，xy，并且没有不同于x，y的z使得xzy，则在x，y之间用直线连结。,例：A=1,2,3,4,6上的整除关系为R,画出的哈斯图,1,2,3,4,6,在画偏序集的哈斯图时，首先适当排列顶点的顺序使得：x,yA，若xy，则将x画在y的下方。对于A中的两个不同元素x和y,如果y盖住x,就用一条线段连接x和y。,例设Aa,b,a,b,a,b,c,a,b,c,d,a,b,c,e，画出的哈斯图。,解：A=,1,2,3,1,2,2,3R=,IA,1,22,3123,例：已知偏序集的哈斯图如下所示,写出集合A和关系R的表达式。,例画出偏序集的哈斯图。解：哈斯图如下图所示。,特殊元,设为偏序集，BA，yB，（1）若x(xByx)成立，则称y为B的最小元。（2）若x(xBxy)成立，则称y为B的最大元。（3）若x(xBxyx=y)成立，则称y为B的极小元。（4）若x(xByxx=y)成立，则称y为B的极大元。,（1）有限集合B的最小元（最大元）不一定存在，但极小元（极大元）一定存在。（2）集合B的最小元（最大元）与B中的元素都可比，但极小元（极大元）不一定与B中的元素都可比。（3）集合B的最小元（最大元）如果存在，则一定唯一，但极小元（极大元）可能有很多个。,说明：,设为偏序集，BA，yA若x(xBxy)成立，则称y为B的上界。x(xByx)成立，则称y为B的下界。令C=y|y为B的上界，则称C的最小元为B的上确界。令C=y|y为B的下界，则称C的最大元为B的下确界。,（1）集合B的上界，下界，上确界，下确界都不一定存在。（2）集合B的最小元（最大元）一定是B中的下界（上界），而且是下确界（上确界），但B的下确界（上确界）不一定是B中的最小元（最大元）。（为什么？）（3）集合B的下确界（上确界）如果存在，则一定唯一，但下界（上界）可能有很多个。,说明：,1,2,4,8,7,11,5,10,3,6,12,9,例如偏序集没有最大元,有最小元1，有极大元7,8,9,10,11和12,极小元,分别是1，无上确界，下确界1。,例偏序集有最小元，有最大元a,b,c,有唯一极大元a,b,c，有极小元。有上确界a,b,c，下确界。,a,b,c,a,b,a,c,b,c,a,b,c,例：在上图整除关系的偏序集里,如果B=2,3,6,那么B的上界是6和12,最小上界是6。B的下界是1,最大下界也是1。在右上图中,令B=c,d,e,则B的上界和最小上界都是e,B的下界为a,b,但B没有最大下界。,1,2,4,8,7,11,5,10,3,6,12,9,f,b,c,d,a,g,h,e,设A和B是任意两个集合，且F是从A到B的关系,若对每一个xA，都存在唯一的yB，使F，则称F为从A到B的函数，并记作F:AB。A称为函数F的定义域，即D(F)=A，R(F)称为函数F的值域，且R(F)B。有时也用F(A)表示函数F的值域，即F(A)=R(F)=y|yB(x)(xAy=F(x)并称F(A)(值域)为函数F的像。,函数的定义和性质,对于F:AB来说，若F，则称x为函数的自变元，称y为函数因变元，因为y值依赖于x所取的值，或称y是F在x处的值，或称y为F下x的像。通常把F记作F(x)=y。例:设F：ABA=x1,x2,x3B=y1,y2,y3F1=,;F2=;判断它们是否为函数。,从函数的定义可以看出，从A到B的函数F和一般从A到B的二元关系之不同有以下两点：A的每一元素都必须是F的有序对之第一分量。若F(x)=y，则函数F在x处的值是唯一的，即F(x)=yF(x)=zy=z考虑到习惯用法，以下常常将大写函数符号F改为小写字母f。,设F为二元关系，若xdomF都存在唯一的yranF使xFy成立，则称F为函数。对于函数F，如果有xFy,则记作y=F(x),并称y为F在x点的值。,设A,B为集合,如果f为函数,且domf=AranfB,则称f为从A到B的函数记作f:AB例：当xN时,f(x)=2x,g(x)=4均为从N到N的函数。所有从A到B的函数的集合记作BA，读作“B上A”。符号化表示为：BA=f|f:AB,在AB的所有子集中，是全部还是部分子集可以定义函数？令BA表示这些函数的集合，即BA=f|f:AB。设|A|=m，|B|=n，则|BA|=nm。这是因为对每个自变元，它的函数值都有n种取法，故总共有nm种从A到B的函数。,例：设A=1,2,3,4,B=a,b,c,d,e,A到B的关系f1=,f2=,f3=,试确定上述各式是否为A到B的函数解:式中的f1不是由A到B的函数,因为A中的元素1在B中没有任何元素与它对应。、式中f2，f3是由A到B的函数。因为A中的每一个元素在B中都有唯一一个元素与它对应。,例：设A=1,2,3,B=a,b,求BA。解：由排列组合的知识知，若|A|=m,|B|=n,则|BA|=nm。所以本题有23个函数。BA=f1,f2,f3,f4,f5,f6,f7,f8,其中f1=,f2=,f3=,f4=,f5=,f6=,f7=,f8=,因为函数是集合，所以两个函数f和g相等就是它们的集合表达式相等，即f=gfggf也就是1、domf=domg2、xdomf=domg都有f(x)=g(x),函数相等,设函数f:AB,AA,则A在f下的像是f(A)=f(x)|xA=fA当A=A时称f(A)=f(A)=ranf是函数的像。对任何xA,f(x)与f(A)是不一样的，f(x)是函数在x的值，也可以看作x在f下的象，它是象集f(A)中的一个元素，即f(x)f(A)例：设A=B=Rf：RR，f(x)=x2(或f=|xR)令A=A,那么有：f(A)=f(x)|xA=x2|xR所以f(A)=f(A)=f(R)=R+,R+为正实数集。,满射、单射、双射设函数f:AB(1)若对任意yB,必存在xA使f(x)=y则称f是A到B的满射；(2)若对于任何的x1,x2A,x1x2，都有f(x1)f(x2)则称f是单射的(或一对一的）。(3)若f:AB既是满射的又是单射的,则称f是双射的(或一一到上的)。,a,b,c,1,2,3,4,a,b,c,d,1,2,3,a,b,c,1,2,3,A,B,a,d,c,b,a,3,2,1,b,c,1,2,3,4,右上图是单射，但不是满射。所谓单射，就是集合A中不同的元素在B中必须有不同的象。单射使得集合A的元素与f的值域Rf的元素一一对应。,右下图是满射，但不是单射。所谓满射，即B每一个元素都必须是A中至少一个元素的象。,例：判断下列函数是否为满射、单射或双射设A=a,b,c,B=1,2,且函数f:AB,f=,；设N为自然数集合,且皮亚诺函数S:NNs(n)=n+1；设Z为整数集合,O为奇数集合且函数g:ZOg(x)=2x-1；,f是满射但不是单射函数s是单射但不是满射函数g是双射函数,解：,例：以下都是实数集上的函数,判断它们是否为单射，满射或双射函数，为什么？,(1)f(x)=x-1,(2),(3),解:(1)双射函数。因为它是单调函数，而且ranf=R。(2)不是单射，因为f(0)=f(1)=0；也不是满射，因为函数的最小值为-1/4,ranfR。(3)不是单射，因为f(1)=f(3)=0；也不是满射，因为-2没有原像。,(2)将Z中元素以下列顺序与N中元素对应：Z:0-11-22-33N:0123456,可得函数2xx0f(