《离散数学》讲义 - 3

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

2、元素（集合中的事物）：az。 I 元素a属于集合A， 记作：aA II 元素a不属于集合A， 记作：aA5说明集合的方法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)可表示集合。62、集合相等外延性原理：两个集合是相等的，当且仅当它们有相同的成员。 两个集合A和B相等，记作：

3、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注意：集合没有次序之分，集合中的元素可以重复。83、子集（1）概念定义3-1.1 设A、B是任意两个集合，假设A是每一个元素是B的成员，则称A为B的子集，或A包含在B内，或B包含A。记作：AB，或BA。AB(x)(xAxB)例如：A=1,2,3，B=1,2，C=1,3，D=3;则有：BA，CA，D

4、A，DC。根据子集的定义，有：AA 自反性(AB)(BC)(AC)传递性9（2）应用定理3-1.1 集合A和B相等的充分必要条件是这两个集合互为子集。104、真子集 定义3-1.3 如果集合A的每一个元素都属于B，但集合B中至少有一个元素不属于A，则称A为B的真子集。 记作：AB。即：AB(AB)(AB) AB(x)(xAxB)(x)(xBxA)115、空集（1）概念定义3-1.3 不包含任何元素的集合是空集。记作：。x|P(x)P(x)， 其中P(x)是任意谓词。注意：，但。12（2）性质定理3-1.2 对于任意一个集合A，A。注意：I 对于每一个非空集合A，至少有两个不同的子集：A和，即：

5、AA和A。我们称A和为平凡子集。II 一般来说，A的每一个元素都能确定A的一个子集，即若aA，则aA。136、全集定义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。 SiE(i=0,1,2,7)。注意：对于一个元素个数为n的全集E，其可能的子集个数为2n。147、幂集 定义3-1.5 给定集合A，有集合A的所有子集为元素组成

6、的集合，称为集合A的幂集。记作： P (A)例如：A=a,b,c P (A) = ,a, b, c, a,b,a,c,b,c, a,b,c15（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。一般地P (S)=S0,S1,S2n-1即：P (S)=Si|iJ其中：1731习题作业P86（6）c）；（7）；（10）32 集合的运算18191、集合的交（1）概念定义3

7、-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，求证ACBC22（2）性质AA=AA=AE=AAB=BA(AB)C=A(BC)ABA，ABB23(AB)C=A(BC)24（3）不相交若集合AB=，则A与B不相交。（4）表示n个集合A1,A2,An的交可记为：例如：A1=1,2,8,A2=2,8,

8、A3=4,8。则：252、集合的并（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,526（2）性质AA=AAE=EA=AAB=BA(AB)C=A(BC)AAB,BAB27例题2 设AB,CD,则ACBD28（3）表示对于n个集合A1,A2,An的交可记为：例如：设A1=1,2,3,A2=3,8,A3=2,6则：293、交并的性质 （1）分配律定理3-2.1 设A、B、C为三个集合，则下列分配律成立。a)A(B

9、C)=(AB)(AC)A(BC)=(AB)(AC)30（2）吸收律定理3-2.2 设A、B为任意两个集合，则下列关系成立。a)A(AB)=AA(AB)=A31（3）AB时，A和B的交并关系定理3-2.3 AB，当且仅当AB=B或AB=A324、集合的补（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,6332）绝对补定义3-2.4 设E为全集，对任一集合A关于E的补集EA，称为集合A的绝

10、对补。记作： AA=E-A=x|xExAA的定义如同3-2.4所示。34（2）性质a)(A)=Ab)E=c)=Ed)AA=Ee)AA=355、“、”关系 定理3-2.4 设A、B为任意两个集合，则下列关系成立。a)(AB)=ABb)(AB)=AB36（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)AB395、集合的对称差定义3-2.5 设A、B

11、为任意两个集合，A和B的对称差为集合S，其元素或属于A，或属于B，但不能既属于A又属于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)4332 习题 P95（5）c；（9）34 序偶与笛卡尔积44451、序偶 例如：34张华高于李明。中国处于亚洲。46（1）概念 一般地说，两个具有固定次序的客体组成一个序偶，它常常表示两个客体之间的关

12、系。例如：;注意：序偶可看作具有两个元素的集合。但与集合不同的是元素在序偶中有确定的次序。例如：在集合中：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时， ,zx,其中：x,不是三元组。同理：四元组第一元素是三元组 四元组：,w 四元组相等：,w=,s (x=p)(y=q)(z=r)

13、(w=s)49推广到n元组： n元组可写成,xn,xn=,yn(x1=y1)(x2=y2)(xn-1=yn-1)(xn=yn) 一般地，n元组可简写为，第i个元素xi称作n元组的第i个坐标。502、笛卡尔乘积（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)=a,| (aA)( BC)52（2）性质 1）笛卡尔乘积与和的

14、关系定理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)53a)A(BC)=(AB)(AC)54c)(AB)C=(AC)(BC)552）笛卡尔乘积与子集之间的关系一、左右两边同时直积上相同的集合定理3-4.2 若C，则AB(ACBC)(CACB)56二、左右两边直积上不同的集合定理3-4.3 设A、B、C、D为四个非空集合，则ABCD的充要条件为AC，BD。57（3）推广约定：A1A2A3=(A1A2)A3A1A2A3A4=(A1A2A3)A4 一般地，A1A2An=

15、( A1A2An-1)An=| (x1A1)(x2A2)(xnAn)故A1A2An是有关n元组构成的集合。注意：AA=A2 AAA=A3 583-4习题作业：P105（3）d），e）35 关系及其表示59601、引论例如：电影票与座位之间的对号关系。设：X：电影票集合。 Y：座位集合。则(x)xX(y)yY必有关系：（1）x与y有“对号”关系；或（2）x与y没有“对号”关系。令R：“对号”关系则：（1）xRy或R（2）xRy或R因此，可得到“对号”关系R是序偶的集合。612、概念 （1）关系定义3-5.1 任一序偶的集合确定了二元关系R，R中任一序偶可记作R或xRy。不在R中的任一序偶可记作R

16、或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 R63例题1 设A=1,2,3,5,B=1,2,4H=,求：dom H, ran H, FLD H。解：dom H=1,2,3ran H=2,4FLD H=1,2,3,4643、直积与关系（1）概念定义3-5.3 令X和Y是任意两个集合，直积XY的子集R称作X

17、到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上的二元关系。664、恒等关系定义3-5.4 设IX是X上的二元关系且满足IX=|xX，则称为Ix上是恒等关系。例如：A=1,2,3，则 IA=,。675、关系的运算例题4 设X=1,2,3,4，若H=|(x-y)/2是整数， S=|(x-y)/3是正整数，求HS,HS,H,SH。68定理3

18、-5.1 若Z和S是从集合X到集合Y的两个关系，则Z、S的并、交、补、差仍是X到Y的关系。696、二元关系表示（1）关系矩阵 设给定两个有限集合X=x1,x2,xm,Y=y1,y2,yn，R为从X到Y的一个二元关系。则对应关系R有一个关系矩阵MR=rijmn，其中：(i=1,2,m; j=1,2,n)70注意：1）根据X集合中的元素的个数确定行数；根据Y集合中元素的个数确定列数。2）行和列对应的位置与X和Y集合中元素出现的次序是一一对应的。即：第i行对应X集合中第i个元素，第j列对应Y集合中第j个元素。3）根据序偶是否属于R，确定关系矩阵中行和列对应元素的值（1或0）。71例题5 设X=x1,

19、x2,x3,x4,Y=y1,y2,y3，R=,，写出关系矩阵MR72例题6 设A=1,2,3,4，写出集合A上大于关系的关系矩阵。73（2）关系图 设集合X=x1,x2,xm到Y=y1,y2,yn上的一个二元关系R， 关系图的绘制步骤：（1）在平面上作出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=

20、,75例题8 设A=1,2,3,4,5，在A上的二元关系R给定为：R=, , ,画出R的关系图。76说明： 通常讨论是同一集合上的关系。 从X到Y的关系R有： RXY 且XY(XY)(XY)所以有R(XY)(XY)令Z= XY，则RZZ。773-5习题作业：P110（4）（5）b36 关系的性质78791、自反定义3-6.1 设R为定义在集合X上的二元关系，如果对于每个xX，有xRx，则称二元关系R是自反的。R在X上自反(x)(xXxRx)例如，在实数集合R中，“”是自反的。802、对称定义3-6.2 设R为定义在集合X上的二元关系，如果对于每个x,yX，每当xRy，就有yRx，则称集合X上关

21、系R是对称的。R在X上对称(x)(y)(xXyXxRy)yRx)例如：平面上三角形集合中相似关系是对称的。 在同一街道居住的邻居关系是对称的。81例题1 设A=2,3,5,7,R=| (x-y)/2是整数，验证R在A上是自反的和对称的。823、传递定义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=,

22、，R1,R2和R3都是传递的吗？解：根据传递性的定义， R1是传递的； R2是传递的；而R3不是传递的。R3R3，而R3；R3R3，而R3；故：R3不是传递的。844、反自反定义3-6.4 设R为定义在集合X上的二元关系，如果对于每一个xX，都有R，则R称作反自反的。R在X上反自反(x)(xXR)例如：数的大于关系或小于关系和日常生活中父子关系。注意：一个不是自反的关系，不一定就是反自反的。855、反对称定义3-6.5 设R为定义在集合X上的二元关系，对于每一个x,yX，每当xRy和yRx必有x=y，则称R在X上是反对称的。R在X上反对称(x)(y)(xXyYxRyyRx)x=y)例如：在实数

23、集合中是反对称的，集合的是反对称的。(xRy)(yRx)(x=y) (x=y)(xRy)(yRx)(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是自反的，当且仅当在

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

25、为R和S的复合关系，表示为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,RRR94说明： 由于关系合成满足结合律，因此在同一关系上m次的合成运算，可写成：分别记作：95（3）表示 已知从集合X=x1,x2,xm到集合Y=y1,y2,yn有关系R，则MR=u

26、ijmn表示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=1962、逆关系（1）概念定义3-7.2 设R为X到Y的二元关系，如将R中每一序偶的元素顺序互换，所得到的集合称为R的逆关系。记作：Rc，即：Rc=|R例如：集合X=1,2,3,4到Y=a,b

27、,c上的关系R=,则Rc=,97（2）性质1）R的两次逆(Rc)c=R因为：RRc(Rc)c982）逆与集合运算及直积的关系定理3-7.1 设R，R1和R2都是从A到B的二元关系，则下列各式成立。a)(R1R2)c=R1cR2cb)(R1R2)c=R1cR2cc)(AB)c=BA d)(R)c=Rce)(R1R2)c= R1cR2cd) 993）复合关系与逆关系 定理3-7.2 设T为从X到Y的关系，S为从Y到Z的关系，证明(TS)c=ScTc1004）关系性质与逆关系定理 3-7.3 设R为X上的二元关系，则a）R是对称的，当且仅当R=Rcb）R是反对称的，当且仅当R RcIx101注意：

28、关系Rc的图形，是关系R图形中将其弧的箭头方向反置。关系Rc的矩阵是MR的转置矩阵。10287习题作业P119（2）a）；（8）38 关系的闭包运算1031041、关系闭包（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)105注意：对于X上的二元关系，可以通过扩充序偶的方法来形成包含R的自反（对称、传递）关系；但R的自反（对称、传递）闭包必须是包含R的最小的自反（对称、传递）

29、关系。106（2）闭包与关系性质定理3-8.1 设R是X上二元关系，那么a）R是自反的，当且仅当r(R)=Rb）R是对称的，当且仅当s(R)=Rc）R是传递的，当且仅当t(R)=R1072、求解关系闭包的方法（1）求自反闭包定理3-8.2 设R是集合X上的二元关系，则r(R)=RIx108（2）求对称闭包定理3-8.3 设R是集合X上的二元关系，则s(R)=RRc109（3）求传递闭包定理3-3.4 设R是X上的二元关系，则注意：复合运算的缩写形式Rn或R(n)与同一集合的直积An110例题1 设A=a,b,c，R是A上的二元关系，且给定R=,，求r(R),S(R),t(R)。1113、t(R

30、)与X的关系定理3-8.5 设X是含有n个元素的集合，R是X上的二元关系，则存在一个正整数kn，使得： 由此n个元素的有限集合上关系R的传递闭包可写为： 1124、Warshall的R的有效算法 （1）置新矩阵A:=M（2）置i:=1（3）对所有j如果Aj, i=1，则对k=1,2,nAj,k:=Aj,k+Ai,k;（4）i:=i+1（5）如果in，则转到步骤(3)，否则停止。说明：逐个考察每一列i中为1的元素Aji然后将第j行和第i行实施逻辑加，产生第j行 1135、闭包的复合运算定理3-8.6 设X是集合，R是X上的二元关系，则a)rs(R)=sr(R)b)rt(R)=tr(R)c)ts(

31、R)st(R)114注意：Ix的自身合成关系和逆关系是其本身。Ix与其它关系R的合成是R本身。关系的运算（包含特殊运算）都是X上的二元关系。1151-8习题作业P127（1）；（2）a）b)；(5);（7）c39 集合的划分和覆盖 1161171、覆盖与划分 （1）概念定义3-9.1 若把一个集合A分成若干个叫做分块的非空子集，使得A中每个元素至少属于一个分块，那么这些分块的全体构成的集合叫做A的一个覆盖。如果A中每一个元素属于且仅属于一个分块，那么这些分块的全体构成的集合叫做A的一个划分(或分划)。 118等价定义定义3-9.1 令A为给定非空集合， 其中 集合S称作集合A的覆盖。 如果除以

32、上条件外，另有 则称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不是覆盖；D,G,E是划分。小结：1）若是划分则必是覆盖，其逆不真。2）任一个集合的最小划分，就是由这个集合全部元素组成的一个分块集合。如：G就是最小划分。即：S中包含分块最少的。3）任一个集合的最大划分是由每个元素构成一个单元素分块的集合。如：E就是最大划分。4）给定集合A的划分并不是唯一的，但已知一个集合很容易构造出一种划分。1202、交叉划分（1）概念定义3-9.2 若A

33、1,A2,Ar与B1,B2,Bs是同一集合A的两种划分，则其中所有AiBj组成的集合，称为是原来两种划分的交叉划分。 121例如：所有生物的集合X，可化割成P,A，其中P：所有植物的集合，A：所有动物的集合；另外，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的两种划分，则其交叉亦是原集合的一种划分。 1233、加细划分 （1）概念定义3-9.3 给定X的任意两个划分A1,A2,Ar和B1,B2,Bs

34、，若对于每一个Aj均有Bk使AjBk，则A1,A2,Ar称为是B1,B2,Bs的加细。 （2）性质定理3-9.2 任何两种划分的交叉划分，都是原来各划分的一种加细。 1243-9习题作业P130(5)310 等价关系与等价类 1251261、等价关系定义3-10.1 设R为定义在集合A上的一个关系，若R是自反的，对称的和传递的，则R称为等价关系。例如：平面三角形集合中，三角形的相似关系是等价关系。1272、等价类 定义3-10.2 设R为集合A上的等价关系，对任何aA,集合aR=x|xA,aRx称为元素a形成的R的等价类。注意：aR是非空的。128如：例1 集合T=1,2,3,4上的等价类R=

35、,。1R=1,4=4R2R=2,3=3R1293、性质定理3-10.1 设给定集合A上的等价关系R，对于a,bA，有aRb iff aR=bR。1304、商集 定义3-10.3 集合A上的等价关系R，其等价类集合aR|aA称作A关于R的商集，记作A/R。如：例题1商集T/R=1R,2R例题3商集I/R=0R,1R,2R 1315、划分、等价关系与商集之间的关系（1）商集与划分定理3-10.2 集合A上的等价关系R，决定了A的一个划分，该划分就是商集A/R。132（2）划分与等价关系定理3-10.3 集合A的一个划分确定A的元素间的一个等价关系。133例题4 设A=a,b,c,d,e,有一个划分

36、S=a,b,c,d,e，试由划分S确定S确定A上的一个等价关系。134（3）等价关系与商集 定理3-10.4 设R1和R2为非空集合A上的等价关系，则R1=R2，当且仅当A/R1=A/R2 1353-10作业P134135(3);(4);(5);(9)311 相容关系1361371、相容关系 定义3-11.1 给定集合A上的关系r，若r是自反的，对称的则称r是相容关系。 1382、相容类定义3-11.2 设r是集合A上的相容关系，若CA，如果对于C中任意两个元素a1,a2有a1ra2，称C是由相容关系r产生的相容类。 产生相容类:x1,x2,x1,x3,x2,x3,x6,x1,x2,x3,x2

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

38、全多边形。2）孤立结点。满足上述条件的结点组成的集合都是最大相容类。 1414、性质定理3-11.1 设r是有限集A上的相容关系，C是一个相容类，那么必存在一个最大相容类Cr，使得CCr。证明：采用构造法证明。注意：1)A中的任意元素a，必属于一个最大相容类Cr中； 2) 所有最大相容类组成的集合必覆盖集合A。 1425、完全覆盖（1）概念定义3-11.4 在集合A上给定相容关系r，其最大相容类的集合称作集合A的完全覆盖，记作Cr(A)。注意：集合A的覆盖不唯一；不同的相容类集合可构成A的覆盖，但给定相容关系r，只能唯一对应一个完全覆盖。例题1中，给定A上相容关系则有唯一的完全覆盖：a1,a2

39、,a4,a6,a3,a4,a6,a4,a5,a7143（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=,1452)完全覆盖与相容关系定理3-11.3 集合A上的相容关系r与完全覆盖Cr(A)存在一一对应。自证。1463-11习题作业P1

40、39(2),(3)312 序关系 1471481、偏序关系 定义3-12.1 设A是一个集合，如果A上的一个关系R，满足自反性，反对称性和传递性，则称R是A上的一个偏序关系，并记作“”。序偶称作偏序集。 149例题1 在实数集R中， 证明小于等于关系“”是偏序关系。1502、盖住（1）概念定义3-12.2 在偏序集合中，如果x,yA,xy,xy且没有其它元素z满足xz,zy，则称元素y盖住x。并且记作COV A=|x,yA;y盖住x。注意：xy类似xRy，即：偏序关系。zxy（z是其它的不同x，y） 151（2）表示对于给定偏序集，其盖住关系是唯一的，可用盖住的性质画出偏序集合图，或称哈斯图，

41、其作图规则为：1)用小圆圈代表元素。2)如果xy且xy，则将代表y的小圆圈画在代表x的小圆圈之上。3)如果COV A，则在x与y之间用直线连接。注意：层次性1523、链与反链定义3-12.3 设是一个偏序集合，在A的一个子集中，如果每两个元素都是有关系的，则称这个子集为链。在A的一个子集中，如果每两个元素都是无关的，则称这个子集为反链。约定，如A的子集只有单个元素，则这个子集既是链又是反链。例如:A表示一个单位里所有工作人员的集合，表示领导关系，则为一偏序集，其中部分工作人员有领导关系的组成一个链。还有部分工作人员没有领导关系的组成一个反链。 1534、全序关系 定义3-12.4 在偏序集中，

42、如果A是一个链，则称为全序集合或称线序集合，在这种情况下，二元关系称为全序关系或线序关系。 全序集就是对任意x,yA，或者有xy或者有yx成立。例如，定义在自然数集合N上的“”是偏序关系，且对于任意i,jN，必有：(ij)(ji)成立，故“”是全序关系。1545、极大(极小)元与最大(最小)元（1）极大(极小)元定义3-12.5 设是一个偏序集合，且B是A的子集，对于B中的一个元素b，如果B中没有元素x， 满足bx且bx，则称b为B的极大元。同理，对于bB，如果B中没有任何元素x， 满足bx且xb，则称b为B的极小元。 155（2）最大(最小)元定义3-12.6 令是一个偏序集，且B是A的子集

43、，若有某个元素bB，对于B中每一个元素x有xb，则称b为的最大元。同理，若有某个元素bB，对每一个xB有bx，则称b为的最小元。156（3）性质定理3-12.1 令为偏序集且BA，若B有最大元(最小元)，则必是唯一的。证明：反证法。 1576、上界(下界)与上确界(下确界)（1）上界(下界)定义3-12.7 设为一偏序集，对于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的最小上界(上

44、确界)，记作LUB B。同样，若b为B的任一下界， 若对B的所有下界z，均有zb，则称b为B的最大下界(下确界)，记作GLB B。 1597、良序（1）概念定义3-12.9 任一偏序集合，假如它的每一个非空子集存在最小元素，这种偏序集称为良序的。例如：In=1,2,n及N=1,2,3,，对于小于等于关系是良序集合。即：,是良序集合。 160（2）性质定理3-12.2 每一个良序集合，一定是全序集合。证明：根据良序集合的定义和最小元素的定义。定理312.3 每一个有限的全序集合，一定是良序集合.证明：采用反证法。注意：结论对于无限的全序集合不一定成立。例如：大于0小于1的全部实数，按大小关系是一

45、个全序集合，但不是良序集合。1613-12习题作业P145P145146(1);(2);(7)cd41 函数的概念 1621631、函数（1）概念定义4-1.1 设X和Y是任何两个集合，而f是X到Y的一个关系，如果对于每一个xX，有唯一的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

46、的前域和值域在f中，f的前域就是 函数y=f(x)的定义域记作dom f=X, f的值域ran fY,有时也记作Rf，即： Rf=y|(x)(xX)(y=f(x)集合Y称为f的共域，ran f亦称为函数的象集合。 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+x210b. f=|y1,y2Ry22=y1c. f=|x1,x2N,x2为小于x1的素数个数 1662、函数相等定义4-1.2 设函数f: AB, g: CD

47、,如果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=,f5=,f6=,f7=,注意：1)设X和Y为有限集，|X|=m,|Y|=n，从X到Y共有nm个不同的函数。2)符号Yx表示从X到Y的所有函数的集合，当X和Y是无限集，也用这个符号。 1673、函数的分类（1）满射定义4-1.3 对于f:XY的映射中，如果ran f=Y， 即Y的每一个元素是X中一个或多个元素的象点，则称这个映射为满射（或到上映射）。 设f: XY是满射，即对于任意的yY，必存在xX使得f(x)=y成立。例如：A=a,b,c,d,B=1,2,3