《离散数学》讲义课件.pptx

《《离散数学》讲义课件.pptx》由会员分享，可在线阅读，更多相关《《离散数学》讲义课件.pptx（181页珍藏版）》请在三一办公上搜索。

1、,第三章 集合与关系 31 集合的概念和表示法,离散数学,1,集合论起源：起源16世纪末，数学危机（理发师：只给那些不给自己理发的人理发，不给那些给自己理发的人理发）（理发师？属于那一类？）定义集合的方法在逻辑上来说，有矛盾1876-1908，cantor奠定了集合论基础(朴素集合论)20世纪初，zermole建立的公理化集合论，解决了悖论（公理化集合论）,离散数学,2,离散数学,3,1、集合概念及表示,（1）集合概念一般地说，把具有相同性质的一些东西，汇集成一个整体，就形成一个集合。例如：教室内的桌子；全国的高等学校；自然数的全体；直线上的点。分类有限集：集合的元素个数是限的。无限集：集合的

2、元素个数是无限的。,离散数学,4,（2）表示,集合：AZ；元素（集合中的事物）：az。I 元素a属于集合A，记作：aA II 元素a不属于集合A，记作：aA,离散数学,5,说明集合的方法I 列举法：将某集合的元素列举出来。例如：A=a,b,c,d,D=桌子，灯泡，自然数，老虎，C=2,4,6,2n注意：集合的元素可以是一个集合。例如：S=a,1,2,p,q，qq，但qS。II 叙述法：利用一些规则，来决定某一事物是否属于该集合。例如：S1=x|x是正奇数S2=x|x是中国的省S3=y|y=a或y=b。另外，用P(x)表示任何谓词，则x|P(x)可表示集合。,离散数学,6,2、集合相等,外延性原

3、理：两个集合是相等的，当且仅当它们有相同的成员。两个集合A和B相等，记作：A=B，两个集合不相等，则记作AB。,离散数学,7,例如：设A是小于10的素数集合，即A=2,3,5,7，设代数方程x417x3101x2247x2100的所有根可组成集合B，则B=2,3,5,7。又如：1,2,4=1,2,2,4 1,2,4=1,4,2 1,3,5,=x|x是正奇数 但：1,2,41,2,4注意：集合没有次序之分，集合中的元素可以重复。,离散数学,8,3、子集,（1）概念定义3-1.1 设A、B是任意两个集合，假设A是每一个元素是B的成员，则称A为B的子集，或A包含在B内，或B包含A。记作：AB，或BA

4、。AB(x)(xAxB)例如：A=1,2,3，B=1,2，C=1,3，D=3;则有：BA，CA，DA，DC。根据子集的定义，有：AA 自反性(AB)(BC)(AC)传递性,离散数学,9,（2）应用,定理3-1.1 集合A和B相等的充分必要条件是这两个集合互为子集。,离散数学,10,4、真子集,定义3-1.3 如果集合A的每一个元素都属于B，但集合B中至少有一个元素不属于A，则称A为B的真子集。记作：AB。即：AB(AB)(AB)AB(x)(xAxB)(x)(xBxA),离散数学,11,5、空集,（1）概念定义3-1.3 不包含任何元素的集合是空集。记作：。x|P(x)P(x)，其中P(x)是任

5、意谓词。注意：，但。,离散数学,12,（2）性质,定理3-1.2 对于任意一个集合A，A。注意：I 对于每一个非空集合A，至少有两个不同的子集：A和，即：AA和A。我们称A和为平凡子集。II 一般来说，A的每一个元素都能确定A的一个子集，即若aA，则aA。,离散数学,13,6、全集,定义3-1.4 在一定范围内，如果所有集合均为某一集合的子集，则称该集合为全集。记作：E。(x)(xE)恒真。Ex|P(x)P(x)，P(x)任何谓词。注意：全集概念相当于论域 设全集E=a,b,c，可能的子集有：S0=,S1=a,S2=b,S3=c,S4=a,b,S5=a,c,S6=b,c,S7=a,b,c。Si

6、E(i=0,1,2,7)。注意：对于一个元素个数为n的全集E，其可能的子集个数为2n。,离散数学,14,7、幂集,定义3-1.5 给定集合A，有集合A的所有子集为元素组成的集合，称为集合A的幂集。记作：P(A)例如：A=a,b,c P(A)=,a,b,c,a,b,a,c,b,c,a,b,c,离散数学,15,（2）性质,定理3-1.3 如果有限集合A有n个元素，则其幂集P(A)有2n个元素。,离散数学,16,（3）编码,引入一种编码，用来唯一地表示有限幂集的元素。例如：Sa,b,c P(S)=Si|iJ其中：J=i|i是二进制数且000i111则：S011=S3=b,c,S110=S6=a,b。

7、一般地P(S)=S0,S1,S2n-1即：P(S)=Si|iJ其中：,离散数学,17,31习题作业P86（6）c）；（7）；（10）,32 集合的运算,离散数学,18,离散数学,19,1、集合的交,（1）概念定义3-2.1 设任意两个集合A和B，由集合A和B的所有共同元素组成的集合S，称为A和B的交集。记作：ABS=AB=x|(xA)(xB)交集的定义如图3-2.1（文氏图）所示。,离散数学,20,例1 A=0,2,4,6,8,10,12;B=1,2,3,4,5,6AB=2,4,6例2 设A是所有矩形的集合，B是平面上所有菱形的集合，AB是正方形的集合。,离散数学,21,例题1 设AB，求证A

8、CBC,离散数学,22,（2）性质,AA=AA=AE=AAB=BA(AB)C=A(BC)ABA，ABB,离散数学,23,(AB)C=A(BC),离散数学,24,（3）不相交若集合AB=，则A与B不相交。（4）表示n个集合A1,A2,An的交可记为：,例如：A1=1,2,8,A2=2,8,A3=4,8。则：,离散数学,25,2、集合的并,（1）概念定义3-2.2 设任意两个集合A和B，所有属于A或属于B的元素组成的集合S，称为A和B的并集。记作：AB=x|(xA)(xB)并集的定义如图3-2.2所示。例如：设A=1,2,3,4,B=2,4,5。则：AB=1,2,3,4,5,离散数学,26,（2）

9、性质,AA=AAE=EA=AAB=BA(AB)C=A(BC)AAB,BAB,离散数学,27,例题2 设AB,CD,则ACBD,离散数学,28,（3）表示,对于n个集合A1,A2,An的交可记为：,例如：设A1=1,2,3,A2=3,8,A3=2,6则：,离散数学,29,3、交并的性质,（1）分配律定理3-2.1 设A、B、C为三个集合，则下列分配律成立。a)A(BC)=(AB)(AC)A(BC)=(AB)(AC),离散数学,30,（2）吸收律,定理3-2.2 设A、B为任意两个集合，则下列关系成立。a)A(AB)=AA(AB)=A,离散数学,31,（3）AB时，A和B的交并关系,定理3-2.3

10、 AB，当且仅当AB=B或AB=A,离散数学,32,4、集合的补,（1）概念1)相对补定义3-2.3 设A和B为任意两个集合，所有属于A而不属于B的一切元素S称为B对于A的补集，或相对补。记作：A-BS=x|xAxB=x|xA(xB)定义如图3-2.3。例题3 设A=2,5,6,B=1,2,4,7,9,求AB。解：AB=5,6,离散数学,33,2）绝对补定义3-2.4 设E为全集，对任一集合A关于E的补集EA，称为集合A的绝对补。记作：AA=E-A=x|xExAA的定义如同3-2.4所示。,离散数学,34,（2）性质,a)(A)=Ab)E=c)=Ed)AA=Ee)AA=,离散数学,35,5、“

11、、”关系,定理3-2.4 设A、B为任意两个集合，则下列关系成立。a)(AB)=ABb)(AB)=AB,离散数学,36,（2）相对补的性质,定理3-2.5 设A、B为任意两个集合，则下列关系式成立。a)AB=ABb)AB=A(AB),离散数学,37,（3）交对相对补的分配,定理3-2.6 设A、B、C为三个集合，则A(BC)=(AB)(AC),离散数学,38,（4）子集与集合补的关系,定理3-2.7 设A、B为两个集合，若AB，则a)BAb)(BA)AB,离散数学,39,5、集合的对称差,定义3-2.5 设A、B为任意两个集合，A和B的对称差为集合S，其元素或属于A，或属于B，但不能既属于A又

12、属于B。记作：ABS=AB=(AB)(BA)=,对称差的定义如图3-2.5所示。,离散数学,40,（2）性质,a)AB=BA(交换律)b)A=Ac)AA=d)AB=(AB)(AB)e)(AB)C=A(BC),离散数学,41,(AB)C=A(BC),离散数学,42,从图3-2.7的文氏图可得出下列关系。AB=(AB)(BA)(AB)AB=(AB)(AB),离散数学,43,32 习题 P95（5）c；（9）,34 序偶与笛卡尔积,离散数学,44,离散数学,45,1、序偶,例如：34张华高于李明。中国处于亚洲。,离散数学,46,（1）概念,一般地说，两个具有固定次序的客体组成一个序偶，它常常表示两个

13、客体之间的关系。例如：;注意：序偶可看作具有两个元素的集合。但与集合不同的是元素在序偶中有确定的次序。例如：在集合中：a,b=b,a 在序偶中：=,离散数学,47,（2）相等,定义3-4.1 两个序偶相等，=,iff x=u,y=v。注意：序偶中的两个元素可以属于不同的集合，可代表不同类型的事物。在序偶中，a称第一元素，b称第二元素。,离散数学,48,（3）推广,三元组是一个序偶，其第一元素也是一个序偶。形如：,z,z=,w,iff=,z=w即：x=u,y=v,z=w。约定：三元组,z记作注意：当xy时，,z其中：不是三元组。同理：四元组第一元素是三元组 四元组：,w 四元组相等：,w=,s(

14、x=p)(y=q)(z=r)(w=s),离散数学,49,推广到n元组：n元组可写成,xn,xn=,yn(x1=y1)(x2=y2)(xn-1=yn-1)(xn=yn)一般地，n元组可简写为，第i个元素xi称作n元组的第i个坐标。,离散数学,50,2、笛卡尔乘积,（1）概念定义3-4.2 令A和B是任意两个集合，若序偶的第一个成员是A的元素，第二个成员是B的元素，所有这样的序偶集合，称为集合A和B的笛卡尔乘积或直积。记作：AB AB=|(xA)(yB),离散数学,51,注意：约定若A=或B，则AB。(AB)CA(BC)(AB)C=,c|(AB)(cC)=|(aA)(bB)(cC)A(BC)=|(

15、aA)(BC),离散数学,52,（2）性质,1）笛卡尔乘积与和的关系定理3-4.1 设A，B，C为任意三个集合，则有：a)A(BC)=(AB)(AC)b)A(BC)=(AB)(AC)c)(AB)C=(AC)(BC)d)(AB)C=(AC)(BC),离散数学,53,a)A(BC)=(AB)(AC),离散数学,54,c)(AB)C=(AC)(BC),离散数学,55,2）笛卡尔乘积与子集之间的关系,一、左右两边同时直积上相同的集合定理3-4.2 若C，则AB(ACBC)(CACB),离散数学,56,二、左右两边直积上不同的集合,定理3-4.3 设A、B、C、D为四个非空集合，则ABCD的充要条件为A

16、C，BD。,离散数学,57,（3）推广,约定：A1A2A3=(A1A2)A3A1A2A3A4=(A1A2A3)A4 一般地，A1A2An=(A1A2An-1)An=|(x1A1)(x2A2)(xnAn)故A1A2An是有关n元组构成的集合。注意：AA=A2 AAA=A3,离散数学,58,3-4习题作业：P105（3）d），e）,35 关系及其表示,离散数学,59,离散数学,60,1、引论,例如：电影票与座位之间的对号关系。设：X：电影票集合。Y：座位集合。则(x)xX(y)yY必有关系：（1）x与y有“对号”关系；或（2）x与y没有“对号”关系。令R：“对号”关系则：（1）xRy或R（2）xR

17、y或R因此，可得到“对号”关系R是序偶的集合。,离散数学,61,2、概念,（1）关系定义3-5.1 任一序偶的集合确定了二元关系R，R中任一序偶可记作R或xRy。不在R中的任一序偶可记作R或xRy。例如：在实数中的关系可记作：=|x,y是实数且xy。,离散数学,62,（2）域,定义3-5.2 令R为二元关系，由R的所有x组成的集合domR称为R的前域，即dom R=x|(y)(R)使R的所有y组成的集合ran R称为R的值域，即ran R=y|(x)(R)R的前域和值域一起称作R的域；记作:FLD R即：FLD R=dom Rran R,离散数学,63,例题1 设A=1,2,3,5,B=1,2

18、,4H=,求：dom H,ran H,FLD H。解：dom H=1,2,3ran H=2,4FLD H=1,2,3,4,离散数学,64,3、直积与关系,（1）概念定义3-5.3 令X和Y是任意两个集合，直积XY的子集R称作X到Y的关系。如图3.5.1所示。,dom RX,ran RY，由例题1表明：HAB，dom HA,ran HB,FLD H=dom H ranHAB。,离散数学,65,（2）特殊关系,1）全域关系和空关系把XY的两个平凡子集XY和，分别称为X到Y的全域关系和空关系。2）二元关系当X=Y时，关系R是XY的子集，这时称R为在X上的二元关系。,离散数学,66,4、恒等关系,定义

19、3-5.4 设IX是X上的二元关系且满足IX=|xX，则称为Ix上是恒等关系。例如：A=1,2,3，则 IA=,。,离散数学,67,5、关系的运算,例题4 设X=1,2,3,4，若H=|(x-y)/2是整数，S=|(x-y)/3是正整数，求HS,HS,H,SH。,离散数学,68,定理3-5.1 若Z和S是从集合X到集合Y的两个关系，则Z、S的并、交、补、差仍是X到Y的关系。,离散数学,69,6、二元关系表示,（1）关系矩阵 设给定两个有限集合X=x1,x2,xm,Y=y1,y2,yn，R为从X到Y的一个二元关系。则对应关系R有一个关系矩阵MR=rijmn，其中：,(i=1,2,m;j=1,2,

20、n),离散数学,70,注意：1）根据X集合中的元素的个数确定行数；根据Y集合中元素的个数确定列数。2）行和列对应的位置与X和Y集合中元素出现的次序是一一对应的。即：第i行对应X集合中第i个元素，第j列对应Y集合中第j个元素。3）根据序偶是否属于R，确定关系矩阵中行和列对应元素的值（1或0）。,离散数学,71,例题5 设X=x1,x2,x3,x4,Y=y1,y2,y3，R=,，写出关系矩阵MR,离散数学,72,例题6 设A=1,2,3,4，写出集合A上大于关系的关系矩阵。,离散数学,73,（2）关系图,设集合X=x1,x2,xm到Y=y1,y2,yn上的一个二元关系R，关系图的绘制步骤：（1）在

21、平面上作出m个结点分别记作x1,x2,xm；（2）另作n个结点记作y1,y2,yn；（注：根据Y集合）（3）若xiRyi，则可自结点xi至结点yi处作一有向弧，其箭头指向yi；（4）若xiRyi，则xi与yi间没有线段联结。用以上步骤所绘制的图称为R的关系图。,离散数学,74,例题7 画出例题5的关系图。例题5 设X=x1,x2,x3,x4,Y=y1,y2,y3，R=,离散数学,75,例题8 设A=1,2,3,4,5，在A上的二元关系R给定为：R=,画出R的关系图。,离散数学,76,说明：通常讨论是同一集合上的关系。从X到Y的关系R有：RXY 且XY(XY)(XY)所以有R(XY)(XY)令Z

22、=XY，则RZZ。,离散数学,77,3-5习题作业：P110（4）（5）b,36 关系的性质,离散数学,78,离散数学,79,1、自反,定义3-6.1 设R为定义在集合X上的二元关系，如果对于每个xX，有xRx，则称二元关系R是自反的。R在X上自反(x)(xXxRx)例如，在实数集合R中，“”是自反的。,离散数学,80,2、对称,定义3-6.2 设R为定义在集合X上的二元关系，如果对于每个x,yX，每当xRy，就有yRx，则称集合X上关系R是对称的。R在X上对称(x)(y)(xXyXxRy)yRx)例如：平面上三角形集合中相似关系是对称的。在同一街道居住的邻居关系是对称的。,离散数学,81,例

23、题1 设A=2,3,5,7,R=|(x-y)/2是整数，验证R在A上是自反的和对称的。,离散数学,82,3、传递,定义3-6.3 设R为定义在集合X上的二元关系，如果对于任意x,y,zX，每当xRy,yRz时就有xRz，称关系R在X上是传递的。R在X上传递(x)(y)(z)(xXyXzXxRyyRz)xRz)例如：在实数集合中关系、和，都是传递的。设A是人的集合，在A上的二元关系：祖先关系R也是传递的。,离散数学,83,例题2 设X=1,2,3,R1=,R2=,R3=,，R1,R2和R3都是传递的吗？解：根据传递性的定义，R1是传递的；R2是传递的；而R3不是传递的。R3R3，而R3；R3R3

24、，而R3；故：R3不是传递的。,离散数学,84,4、反自反,定义3-6.4 设R为定义在集合X上的二元关系，如果对于每一个xX，都有R，则R称作反自反的。R在X上反自反(x)(xXR)例如：数的大于关系或小于关系和日常生活中父子关系。注意：一个不是自反的关系，不一定就是反自反的。,离散数学,85,5、反对称,定义3-6.5 设R为定义在集合X上的二元关系，对于每一个x,yX，每当xRy和yRx必有x=y，则称R在X上是反对称的。R在X上反对称(x)(y)(xXyYxRyyRx)x=y)例如：在实数集合中是反对称的，集合的是反对称的。(xRy)(yRx)(x=y)(x=y)(xRy)(yRx)(

25、x=y)(xRy)(yRx)(x=y)(xRy)(yRx)(xy)(xRy)(yRx)(xy)(xRy)(yRx)因此关系R的反对称的定义亦为：(x)(y)(xXxX(xy)(xRy)(yRx)注意：有些关系既是对称的，又是反对称的。例如：A=1,2，S=,离散数学,86,例题4 设某人有三个儿子，组成集合A=T,G,H，在A上的兄弟关系具有哪些性质。,离散数学,87,例题5 集合I=1,2,3,4，I上的关系R=,讨论R的性质。,离散数学,88,如何通过矩阵和关系图判断关系R是否具是自反或对称的？,（1）若关系R是自反的，当且仅当在关系矩阵中，对角线上的所有元素都是1，在关系图上每个结点都有

26、自回路。（2）若关系R是对称的，当且仅当关系矩阵是对称的，且在关系图上，任两个结点间若有定向弧线，必是成对出现的。（3）若关系R是反自反的，当且仅当关系矩阵对角线的皆为零，关系图上每个结点都没有回路。（4）若关系R是反对称的，当且仅当关系矩阵中以主对角线对称的元素不能同时为1，在关系图上两个不同结点间的定向弧线不可能成对出现。注意：传递的特征较复杂，不易从关系矩阵和关系图中直接判断。,离散数学,89,36习题作业P113（2）；（4）,37 复合关系和逆关系,离散数学,90,离散数学,91,1、合成关系,（1）概念定义3-7.1 设R为X到Y的关系，S为从Y到Z的关系，则RS称为R和S的复合关

27、系，表示为RS=|xXzZ(y)(yYRS)从R和S，求RS称为关系的合成运算。例如：R1是关系“是的父亲”，R2是关系“是的父亲”，R1R2称为关系“是的祖父”。,离散数学,92,（2）性质,1）结合律 设R是从X到Y的关系，S是从Y到Z的关系，P是从Z到W的关系，则X到W上的关系(RS)P和R(SP)有：(RS)P=R(SP),离散数学,93,例题1 令R=,和S=,求：RS,SR,R(SR),(RS)R,RR,SS,RRR,离散数学,94,说明：由于关系合成满足结合律，因此在同一关系上m次的合成运算，可写成：,分别记作：,离散数学,95,（3）表示,已知从集合X=x1,x2,xm到集合Y

28、=y1,y2,yn有关系R，则MR=uijmn表示R关系矩阵 其中：,(i=1,2,m;j=1,2,n)同理从集合Y=y1,y2,yn到集合Z=z1,z2,zp的关系S，可用Ms=vjknp表示S关系矩阵，其中：,(j=1,2,n;k=1,2,p),复合关系RS的矩阵MRS可构造如下：MRS=MRMS=wikmp其中：,式中表示逻辑加，满足：00=0,01=1,10=1,11=1 表示逻辑乘，满足：00=1,01=0,10=0,11=1,离散数学,96,2、逆关系,（1）概念定义3-7.2 设R为X到Y的二元关系，如将R中每一序偶的元素顺序互换，所得到的集合称为R的逆关系。记作：Rc，即：Rc

29、=|R例如：集合X=1,2,3,4到Y=a,b,c上的关系R=,则Rc=,离散数学,97,（2）性质,1）R的两次逆(Rc)c=R因为：RRc(Rc)c,离散数学,98,2）逆与集合运算及直积的关系,定理3-7.1 设R，R1和R2都是从A到B的二元关系，则下列各式成立。a)(R1R2)c=R1cR2cb)(R1R2)c=R1cR2cc)(AB)c=BA d)(R)c=Rce)(R1R2)c=R1cR2c,d),离散数学,99,3）复合关系与逆关系,定理3-7.2 设T为从X到Y的关系，S为从Y到Z的关系，证明(TS)c=ScTc,离散数学,100,4）关系性质与逆关系,定理 3-7.3 设R

30、为X上的二元关系，则a）R是对称的，当且仅当R=Rcb）R是反对称的，当且仅当R RcIx,离散数学,101,注意：关系Rc的图形，是关系R图形中将其弧的箭头方向反置。关系Rc的矩阵是MR的转置矩阵。,离散数学,102,87习题作业P119（2）a）；（8）,38 关系的闭包运算,离散数学,103,离散数学,104,1、关系闭包,（1）概念定义3-8.1 设R是X上的二元关系，如果有另一个关系R满足：a）R是自反的（对称的，可传递的）；b）RR；c）对于任何自反的（对称的，可传递的）关系R”，如果有R”R，就有R”R。则称R为R的自反（对称，传递）闭包。记作：r(R),(S(R),t(R),离

31、散数学,105,注意：,对于X上的二元关系，可以通过扩充序偶的方法来形成包含R的自反（对称、传递）关系；但R的自反（对称、传递）闭包必须是包含R的最小的自反（对称、传递）关系。,离散数学,106,（2）闭包与关系性质,定理3-8.1 设R是X上二元关系，那么a）R是自反的，当且仅当r(R)=Rb）R是对称的，当且仅当s(R)=Rc）R是传递的，当且仅当t(R)=R,离散数学,107,2、求解关系闭包的方法,（1）求自反闭包定理3-8.2 设R是集合X上的二元关系，则r(R)=RIx,离散数学,108,（2）求对称闭包,定理3-8.3 设R是集合X上的二元关系，则s(R)=RRc,离散数学,10

32、9,（3）求传递闭包,定理3-3.4 设R是X上的二元关系，则,注意：复合运算的缩写形式Rn或R(n)与同一集合的直积An,离散数学,110,例题1 设A=a,b,c，R是A上的二元关系，且给定R=,，求r(R),S(R),t(R)。,离散数学,111,3、t(R)与X的关系,定理3-8.5 设X是含有n个元素的集合，R是X上的二元关系，则存在一个正整数kn，使得：,由此n个元素的有限集合上关系R的传递闭包可写为：,离散数学,112,4、Warshall的R的有效算法,（1）置新矩阵A:=M（2）置i:=1（3）对所有j如果Aj,i=1，则对k=1,2,nAj,k:=Aj,k+Ai,k;（4）

33、i:=i+1（5）如果in，则转到步骤(3)，否则停止。说明：逐个考察每一列i中为1的元素Aji然后将第j行和第i行实施逻辑加，产生第j行,离散数学,113,5、闭包的复合运算,定理3-8.6 设X是集合，R是X上的二元关系，则a)rs(R)=sr(R)b)rt(R)=tr(R)c)ts(R)st(R),离散数学,114,注意：Ix的自身合成关系和逆关系是其本身。Ix与其它关系R的合成是R本身。关系的运算（包含特殊运算）都是X上的二元关系。,离散数学,115,1-8习题作业P127（1）；（2）a）b)；(5);（7）c,39 集合的划分和覆盖,离散数学,116,离散数学,117,1、覆盖与划

34、分,（1）概念定义3-9.1 若把一个集合A分成若干个叫做分块的非空子集，使得A中每个元素至少属于一个分块，那么这些分块的全体构成的集合叫做A的一个覆盖。如果A中每一个元素属于且仅属于一个分块，那么这些分块的全体构成的集合叫做A的一个划分(或分划)。,离散数学,118,等价定义,定义3-9.1 令A为给定非空集合，,其中,集合S称作集合A的覆盖。,如果除以上条件外，另有,则称S是A的划分（或分划）。,离散数学,119,例如：A=a,b,c，考虑下列子集：S=a,b,b,c,Q=a,a,b,a,cD=a,b,c,G=a,b,cE=a,b,c,F=a,a,cS,Q,D,G,E是覆盖，而F不是覆盖；

35、D,G,E是划分。小结：1）若是划分则必是覆盖，其逆不真。2）任一个集合的最小划分，就是由这个集合全部元素组成的一个分块集合。如：G就是最小划分。即：S中包含分块最少的。3）任一个集合的最大划分是由每个元素构成一个单元素分块的集合。如：E就是最大划分。4）给定集合A的划分并不是唯一的，但已知一个集合很容易构造出一种划分。,离散数学,120,2、交叉划分,（1）概念定义3-9.2 若A1,A2,Ar与B1,B2,Bs是同一集合A的两种划分，则其中所有AiBj组成的集合，称为是原来两种划分的交叉划分。,离散数学,121,例如：所有生物的集合X，可化割成P,A，其中P：所有植物的集合，A：所有动物的

36、集合；另外，X可化为E,F其中E：史前生物，F：史后生物。则，交叉划分为：Q=PE,PF,AE,AF其中：PE：史前生物。PF：史后生物。AE：史前动物。AF：史后动物。,离散数学,122,（2）性质,定理3-9.1 设A1,A2,Ar与B1,B2,Bs 是同一集合X的两种划分，则其交叉亦是原集合的一种划分。,离散数学,123,3、加细划分,（1）概念定义3-9.3 给定X的任意两个划分A1,A2,Ar和B1,B2,Bs，若对于每一个Aj均有Bk使AjBk，则A1,A2,Ar称为是B1,B2,Bs的加细。（2）性质定理3-9.2 任何两种划分的交叉划分，都是原来各划分的一种加细。,离散数学,1

37、24,3-9习题作业P130(5),310 等价关系与等价类,离散数学,125,离散数学,126,1、等价关系,定义3-10.1 设R为定义在集合A上的一个关系，若R是自反的，对称的和传递的，则R称为等价关系。例如：平面三角形集合中，三角形的相似关系是等价关系。,离散数学,127,2、等价类,定义3-10.2 设R为集合A上的等价关系，对任何aA,集合aR=x|xA,aRx称为元素a形成的R的等价类。注意：aR是非空的。,离散数学,128,如：例1 集合T=1,2,3,4上的等价类R=,。1R=1,4=4R2R=2,3=3R,离散数学,129,3、性质,定理3-10.1 设给定集合A上的等价关

38、系R，对于a,bA，有aRb iff aR=bR。,离散数学,130,4、商集,定义3-10.3 集合A上的等价关系R，其等价类集合aR|aA称作A关于R的商集，记作A/R。如：例题1商集T/R=1R,2R例题3商集I/R=0R,1R,2R,离散数学,131,5、划分、等价关系与商集之间的关系,（1）商集与划分定理3-10.2 集合A上的等价关系R，决定了A的一个划分，该划分就是商集A/R。,离散数学,132,（2）划分与等价关系,定理3-10.3 集合A的一个划分确定A的元素间的一个等价关系。,离散数学,133,例题4 设A=a,b,c,d,e,有一个划分S=a,b,c,d,e，试由划分S确

39、定S确定A上的一个等价关系。,离散数学,134,（3）等价关系与商集,定理3-10.4 设R1和R2为非空集合A上的等价关系，则R1=R2，当且仅当A/R1=A/R2,离散数学,135,3-10作业P134135(3);(4);(5);(9),311 相容关系,离散数学,136,离散数学,137,1、相容关系,定义3-11.1 给定集合A上的关系r，若r是自反的，对称的则称r是相容关系。,离散数学,138,2、相容类,定义3-11.2 设r是集合A上的相容关系，若CA，如果对于C中任意两个元素a1,a2有a1ra2，称C是由相容关系r产生的相容类。,产生相容类:x1,x2,x1,x3,x2,x

40、3,x6,x1,x2,x3,x2,x3,x4,x2,x4,x5,注意：前三个相容类可加入新的元素组成新的相容类，而后四个不加入新的元素形成新的相容类，称它们为最大相容类。,离散数学,139,3、最大相容类,（1）概念定义3-11.3 设r是集合A上的相容关系，不能真包含在任何其它相容类中的相容类，称作最大相容类。记作Cr。,离散数学,140,（2）判断方法,I若Cr为最大相容类，显然它是A的子集，且有：1）对于任意xCr，x必与Cr中所有元素有相容关系。2）在A-Cr中没有任何元素与Cr所有元素有相容关系。II在相容关系图中：1）最大完全多边形的顶点集合。完全多边形：多边形结点中，每一个结点都

41、与其它结点有连线。最大完全多边形：不能在加入其它结点使其称为完全多边形。2）孤立结点。满足上述条件的结点组成的集合都是最大相容类。,离散数学,141,4、性质,定理3-11.1 设r是有限集A上的相容关系，C是一个相容类，那么必存在一个最大相容类Cr，使得CCr。证明：采用构造法证明。注意：1)A中的任意元素a，必属于一个最大相容类Cr中；2)所有最大相容类组成的集合必覆盖集合A。,离散数学,142,5、完全覆盖,（1）概念定义3-11.4 在集合A上给定相容关系r，其最大相容类的集合称作集合A的完全覆盖，记作Cr(A)。注意：集合A的覆盖不唯一；不同的相容类集合可构成A的覆盖，但给定相容关系

42、r，只能唯一对应一个完全覆盖。例题1中，给定A上相容关系则有唯一的完全覆盖：a1,a2,a4,a6,a3,a4,a6,a4,a5,a7,离散数学,143,（2）性质,1)覆盖与相容关系定理3-11.2给定集合A的覆盖A1,A2,An，由它确定的关系是相容关系。证明：根据覆盖的定义和相容关系的定义(自反的,对称的)注意：给定集合A上的任意一个覆盖，必可在A上构造对应于此覆盖的一个相容关系；集合A上不同的覆盖却能构造相同的相容关系。,离散数学,144,例如：设A=1,2,3,4,集合1,2,3,3,4和1,2,2,3,1,3,3,4都是A的覆盖，但它们可以产生相同的相容关系。r=,离散数学,145

43、,2)完全覆盖与相容关系,定理3-11.3 集合A上的相容关系r与完全覆盖Cr(A)存在一一对应。自证。,离散数学,146,3-11习题作业P139(2),(3),312 序关系,离散数学,147,离散数学,148,1、偏序关系,定义3-12.1 设A是一个集合，如果A上的一个关系R，满足自反性，反对称性和传递性，则称R是A上的一个偏序关系，并记作“”。序偶称作偏序集。,离散数学,149,例题1 在实数集R中，证明小于等于关系“”是偏序关系。,离散数学,150,2、盖住,（1）概念定义3-12.2 在偏序集合中，如果x,yA,xy,xy且没有其它元素z满足xz,zy，则称元素y盖住x。并且记作

44、COV A=|x,yA;y盖住x。注意：xy类似xRy，即：偏序关系。zxy（z是其它的不同x，y）,离散数学,151,（2）表示,对于给定偏序集，其盖住关系是唯一的，可用盖住的性质画出偏序集合图，或称哈斯图，其作图规则为：1)用小圆圈代表元素。2)如果xy且xy，则将代表y的小圆圈画在代表x的小圆圈之上。3)如果COV A，则在x与y之间用直线连接。注意：层次性,离散数学,152,3、链与反链,定义3-12.3 设是一个偏序集合，在A的一个子集中，如果每两个元素都是有关系的，则称这个子集为链。在A的一个子集中，如果每两个元素都是无关的，则称这个子集为反链。约定，如A的子集只有单个元素，则这个

45、子集既是链又是反链。例如:A表示一个单位里所有工作人员的集合，表示领导关系，则为一偏序集，其中部分工作人员有领导关系的组成一个链。还有部分工作人员没有领导关系的组成一个反链。,离散数学,153,4、全序关系,定义3-12.4 在偏序集中，如果A是一个链，则称为全序集合或称线序集合，在这种情况下，二元关系称为全序关系或线序关系。全序集就是对任意x,yA，或者有xy或者有yx成立。例如，定义在自然数集合N上的“”是偏序关系，且对于任意i,jN，必有：(ij)(ji)成立，故“”是全序关系。,离散数学,154,5、极大(极小)元与最大(最小)元,（1）极大(极小)元定义3-12.5 设是一个偏序集合

46、，且B是A的子集，对于B中的一个元素b，如果B中没有元素x，满足bx且bx，则称b为B的极大元。同理，对于bB，如果B中没有任何元素x，满足bx且xb，则称b为B的极小元。,离散数学,155,（2）最大(最小)元,定义3-12.6 令是一个偏序集，且B是A的子集，若有某个元素bB，对于B中每一个元素x有xb，则称b为的最大元。同理，若有某个元素bB，对每一个xB有bx，则称b为的最小元。,离散数学,156,（3）性质,定理3-12.1 令为偏序集且BA，若B有最大元(最小元)，则必是唯一的。证明：反证法。,离散数学,157,6、上界(下界)与上确界(下确界),（1）上界(下界)定义3-12.7

47、 设为一偏序集，对于BA，如有aA，且对B的任意元素x，都满足xa，则称a为子集B的上界。同样地，对于B的任意元素x，都满足ax，则称a为B的下界。,离散数学,158,（2）上确界(下确界),定义3-12.8 设为偏序集且BA为一子集，a是B的任一上界，若对B的所有上界y均有ay，则称a为B的最小上界(上确界)，记作LUB B。同样，若b为B的任一下界，若对B的所有下界z，均有zb，则称b为B的最大下界(下确界)，记作GLB B。,离散数学,159,7、良序,（1）概念定义3-12.9 任一偏序集合，假如它的每一个非空子集存在最小元素，这种偏序集称为良序的。例如：In=1,2,n及N=1,2,

48、3,，对于小于等于关系是良序集合。即：,是良序集合。,离散数学,160,（2）性质,定理3-12.2 每一个良序集合，一定是全序集合。证明：根据良序集合的定义和最小元素的定义。定理312.3 每一个有限的全序集合，一定是良序集合.证明：采用反证法。注意：结论对于无限的全序集合不一定成立。例如：大于0小于1的全部实数，按大小关系是一个全序集合，但不是良序集合。,离散数学,161,3-12习题作业P145P145146(1);(2);(7)cd,41 函数的概念,离散数学,162,离散数学,163,1、函数,（1）概念定义4-1.1 设X和Y是任何两个集合，而f是X到Y的一个关系，如果对于每一个x

49、X，有唯一的yY，使得f，称关系f为函数，记作：f:XY或假如f，则x称为自变量，y称为在f作用下x的象，f亦可记作y=f(x)，且记f(x)=f(x)|xX注意：函数与关系的区别：a.函数的定义域是X，而不是X的某个真子集。b.一个xX只能对应于唯一的一个y。即如果f(x)=y且f(x)=z，那么，y=z。2)从X到Y的函数往往也叫做从X到Y的映射。,离散数学,164,（2）f的前域和值域,在f中，f的前域就是 函数y=f(x)的定义域记作dom f=X,f的值域ran fY,有时也记作Rf，即：Rf=y|(x)(xX)(y=f(x)集合Y称为f的共域，ran f亦称为函数的象集合。,离散数

50、学,165,例1设X=1,5,p,张明,Y=2,q,7,9,Gf=,即f(1)=2,f(5)=q,f(p)=7,f(张明)=G，dom f=X,Rf=2,q,7,G例 3 判断下列关系中哪个构成函数。a.f=|x1,x2Nx1+x2|y1,y2Ry22=y1c.f=|x1,x2N,x2为小于x1的素数个数,离散数学,166,2、函数相等定义4-1.2 设函数f:AB,g:CD,如果A=C,B=D,且对于所有xA和xC有f(x)=g(x)，则称函数f和g相等，记作f=g。注意：XY的子集并不能都成为X到Y的函数。例如：X=a,b,c,Y=0,1,XY=,f0=,f1=,f2=,f3=,f4=,f