1、C CS S|S SWWU US ST TXDCXDC集合和二元关系复习 本课件仅供大家学习学习本课件仅供大家学习学习 学习完毕请自觉删除学习完毕请自觉删除 谢谢谢谢 本课件仅供大家学习学习本课件仅供大家学习学习 学习完毕请自觉删除学习完毕请自觉删除 谢谢谢谢C CS S|S SWWU US ST TXDCXDC集合的表示法集合是由它包含的元素完全确定的，为了表示一个集合，通常有：列举法、隐式法（描述法）、归纳法、文氏图等表示方法。C CS S|S SWWU US ST TXDCXDC2.2集合的运算定义 设A、B是两个集合，则A Bx|x Ax B仍是一个集合，称为集合A与B的并集，称“”为
2、并运算（Union Operation）。用文氏图表示如下：U UABC CS S|S SWWU US ST TXDCXDC交集定义 设A，B是两个集合，则A Bx|x Ax B仍是一个集合，称为集合A与B的交集，称“”为交运算（Intersection Operation）。用文氏图可表示如下：U UABC CS S|S SWWU US ST TXDCXDC差集定义 设A，B是两个集合，则A-Bx|x Ax B仍是一个集合，称为集合A与B的差集，称“-”为差运算（Subtraction Operation)，-又叫相对补集。用文氏图可表示如下：U UABC CS S|S SWWU US ST
3、 TXDCXDC定义 设U是全集，A是U的子集，则 U-Ax|x U并且x A仍是一个集合，称它为集合A的补集(也可记为，AC等），“”称为补运算（Complement Operation）。用文氏图可表示如下：补集UAAAC CS S|S SWWU US ST TXDCXDC关于运算“差”和“补”的几个性质 1.；2.（）；3.（）（）；4（）；5 。BC CS S|S SWWU US ST TXDCXDC对称差(环和)定义：设A，B是两个集合，则 A B=x|(x A)(x B)(x B)(x A)=(A-B)(B-A)仍是一个集合，称它为与的对称差集，称“”为对称差运算。用文氏图可表示如
4、下：ABU图中的阴影部分为A B。C CS S|S SWWU US ST TXDCXDC 1.等幂律：；2交换律：；3结合律：（）（）；（）（）；4恒等律：；5零 律：；6分配律：（）（）（）；（）（）（）。7吸收律：A（AB）A；A（AB）=A；8否定律：AA 9DeMorgan律：BABABABA AA10矛盾律：A =；11排中律：A =U；C CS S|S SWWU US ST TXDCXDC幂集定义由集合A的所有子集组成的集合称为A的幂集，记为(A)或2A。(A)x|一切x A这种以集合为元素构成的集合，常称为集合的集合或集族（Family of Set）。对集族的研究在数学方面、知
5、识库和表处理语言以及人工智能等方面都有十分重要的意义。结论:显然，若集合有个元素，则集合共有2n个子集，即：|(A)|2n。C CS S|S SWWU US ST TXDCXDC容斥原理 定义所谓容斥，是指我们计算某类物的数目时，要排斥那些不应包含在这个计数中的数目，但同时要包容那些被错误地排斥了的数目，以此补偿，这种原理称为容斥原理，又称为包含排斥原理。定理设A和B是任意有限集合，有|AB|A|B|AB|。例 某软件公司的程序员都熟悉C+或VB，其中熟悉C+的共47人，熟悉VB的共35人，C+和VB都熟悉的共23人，问该公司共有多少程序员？C CS S|S SWWU US ST TXDCXD
6、C 推论设U为全集，A和B是任意有限集合，则|U|(|A|B|)|AB|证明：=|U-(AB)|U|AB|U|(|A|B|)|AB|。BABABA 设A1,A2,An是任意有限集合，有:|.|)1(.|)1(|)1(|.21113111221nnkninijjnjkijninijiniinAAAAAAAAAAAAC CS S|S SWWU US ST TXDCXDC2.5 序偶与笛卡尔乘积定义由两个元素x,y按照一定的次序组成的二元组称为有序偶对，简称序偶,记作,其中，称x为的第一元素，y为的第二元素。例1平面上点的坐标，x,yR；中国地处亚洲，,等都是序偶。这条单地址指令也是序偶。性质 （1
7、）（当xy时)（2）当且仅当xu,yv。C CS S|S SWWU US ST TXDCXDCn重有序组定义由n个元素a1,a2,a3,an按照一定的次序组成的n元组称为n重有序组，记作即：,an。例2a年b月c日d时e分f秒可用下述六重有序组来描述：。性质当且仅当aibi（i1,2,3,n）。C CS S|S SWWU US ST TXDCXDC定义设A,B是两个集合，称集合AB|(xA)(yB)为集合A与B的笛卡儿积。特别，记AA为A2。笛卡儿积BA1 12 23 34 4a ab bc cd dD DC CAB|(xA)(yB)CD|(xC)(yD),C CS S|S SWWU US S
8、T TXDCXDC定义设A1,A2,An为n个非空集合，称3.1.1关系的定义A1A2An的任意子集R为以A1A2An为基的n元关系。特别：当R时，则称R为空关系；当RA1A2An时，则称R为全关系。由于A1A2An的任何子集都是一个n元关系，按照子集的定义，A1A2An共有2|A1A2An|个不同的子集。因此，以A1A2An为基的不同关系共有 2|A1A2An|个。C CS S|S SWWU US ST TXDCXDC定义 设A，B为两个集合，AB的任何一个子集R所定义的二元关系称为从A到B的二元关系，简称关系。如R是从A到A的二元关系，则称R为A上的二元关系。3.1.2二元关系由于任何AB
9、的子集都是一个二元关系，按照子集的定义，知AB共有2|A|B|个不同的子集。因此，从A到B不同的关系共有2|A|B|个。设有一序偶：R，常把这一事实记为xRy，读作“x对y有关系R”。如 R，则记为xRy，读作“x对y没有关系R”。C CS S|S SWWU US ST TXDCXDC3.1.3关系的表示法1.集合表示法由于关系也是一种特殊的集合，所以集合的几种基本的表示法也可以用到关系的表示中。可用枚举法和叙述法来表示关系。例设A2,B3,关系R如定义集合N上的“小于等于”关系：R|(x,y N)(xy)。C CS S|S SWWU US ST TXDCXDC2.关系图法设a1,a2,a3,
10、.,an和b1,b2,b3,.,bm分别为图中的节点，用“。”表示；如 R,则从ai到bj可用一有向边aibj相连。为对应图中的有向边。设Aa1,a2,a3,.,an,Bb1,b2,b3,.,bm，R是从A到B的一个二元关系，则对应于关系R之关系图有如下规定：如R,则从ai到ai用一带箭头的小圆环表示ai C CS S|S SWWU US ST TXDCXDC设Aa1,a2,a3,.,an，Bb1,b2,b3,.,bm，R是从A到B的一个二元关系，称矩阵MR(rij)nm为关系R的关系矩阵或邻接矩阵，其中：)m,.,3,2,1j;n,.,3,2,1i(Rb,a,0Rb,a ,1rjijiij
11、3.关系矩阵显然，关系矩阵是布尔矩阵。注意 在写关系矩阵时，首先应对集合A和B中的元素进行排序，不同的排序会得到不同的关系矩阵。当集合以枚举法表示时，如果没有对集合的元素排序，则默认枚举的次序为元素的排序。C CS S|S SWWU US ST TXDCXDC3.1.4 关系的性质（91-93）自反性与反自反性定义设R是集合A上的二元关系，对任意的xA,都满足R，则称R是自反的，或称R具有自反性，即R在A上是自反的(x)(xA)(R)=12)对任意的xA,都满足 R，则称R是反自反的，或称R具有反自反性，即R在A上是反自反的(x)(xA)(R)=1C CS S|S SWWU US ST TXD
12、CXDC设A=a,b,c,d，例R=,。因为A中每个元素x，都有R，所以R是自反的。R R的关系图的关系图1001010100100001RMR R的关系矩阵的关系矩阵C CS S|S SWWU US ST TXDCXDCS=,。例(续1)S S的关系图的关系图0101001110000010SMS S的关系矩阵的关系矩阵因为A中每个元素x，都有 S，所以S是反自反的。C CS S|S SWWU US ST TXDCXDCT=,。例(续2)因为A中有元素b，使 T，所以T不是自反的；因为A中有元素a，使T，所以T不是反自反的。T T的关系图的关系图1110000110100010TMT T的关
13、系矩阵的关系矩阵C CS S|S SWWU US ST TXDCXDC任何不是自反的关系未必一定是反自反的关系，反之亦然。即存在既不是自反的也不是反自反的关系。表现在关系图上：关系R是自反的，当且仅当其关系图中每个结点都有环；关系R是反自反的，当且仅当其关系图中每个结点都无环。表现在关系矩阵上：关系R是自反的，当且仅当其关系矩阵的主对角线上全为1；关系R是反自反的当且仅当其关系矩阵的主对角线上全为0。结论C CS S|S SWWU US ST TXDCXDC对称性与反对称性设R是集合A上的二元关系，对任意的x,yA，如果R，那么R，则称关系R是对称的，或称R具有对称性，即R在A上是对称的 (x
14、)(y)(xA)(yA)(R)(R)=12)对任意的x,y A，如果R且R，那么x=y，则称关系R是反对称的，或称R具有反对称性，即R在A上是反对称的 (x)(y)(xA)(yA)(R)(R)(x=y)=1C CS S|S SWWU US ST TXDCXDC设A=a,b,c,d，例R1=,R2=,R R1 1的关系图的关系图1101000100RMR R1 1的关系矩阵的关系矩阵是对称的是反对称的R R2 2的关系图的关系图2101000000RMR R2 2的关系矩阵的关系矩阵C CS S|S SWWU US ST TXDCXDCR3=,例(续1)R4=,既不是对称的，也不是反对称的R R
15、3 3的关系图的关系图3111000100RMR R3 3的关系矩阵的关系矩阵既是对称的，也是反对称的R R3 3的关系图的关系图4100000001RMR R3 3的关系矩阵的关系矩阵C CS S|S SWWU US ST TXDCXDC任何不是对称的关系未必一定是反对称的关系，反之亦然。即存在既不是对称的也不是反对称的关系，也存在既是对称的也是反对称的关系。表现在关系图上：关系R是对称的当且仅当其关系图中，任何一对结点之间，要么有方向相反的两条边，要么无任何边；关系R是反对称的当且仅当其关系图中，任何一对结点之间，至多有一条边。表现在关系矩阵上：关系R是对称的当且仅当其关系矩阵为对称矩阵，
16、即rij=rji，i,j=1,2,n；关系R是反对称的当且仅当其关系矩阵为反对称矩阵，即rijrji=0，i,j=1,2,n，ij。结论C CS S|S SWWU US ST TXDCXDC传递性定义 设R是集合A上的二元关系，对任意的x,y,zA，如果R且R，那么R，则称关系R是传递的，或称R具有传递性，即R在A上是传递的(x)(y)(z)(xA)(yA)(zA)(R)(R)(R)=1 C CS S|S SWWU US ST TXDCXDC设A=a,b,c,d，例R1=,R2=是传递的R R1 1的关系图的关系图11110001000000000RMR R1 1的关系矩阵的关系矩阵是传递的R
17、 R2 2的关系图的关系图20100000000000000RMR R2 2的关系矩阵的关系矩阵C CS S|S SWWU US ST TXDCXDCR3=,例(续1)R4=,不是传递的R R3 3的关系图的关系图31100001000000000RMR R3 3的关系矩阵的关系矩阵不是传递的R R3 3的关系图的关系图40110001000010000RMR R3 3的关系矩阵的关系矩阵C CS S|S SWWU US ST TXDCXDC表现在关系图上：关系R是传递的当且仅当其关系图中，任何三个结点x,y,z（可以相同）之间，若从x到y有一条边存在，从y到z有一条边存在，则从x到z一定有一
18、条边存在。表现在关系矩阵上：关系R是传递的当且仅当其关系矩阵中，对任意i,j,k1,2,3,n，若rij=1且rjk=1，必有rik=1。结论C CS S|S SWWU US ST TXDCXDC设A是任意的集合，A上的全关系AA是自反的、对称的、传递的关系；A上的空关系是反自反的、反对称的、对称的、传递的关系；1)A上的恒等关系IA是自反的、对称的、反对称的、传递的关系。例例朋友关系是自反的、对称的、而非传递的关系；1)父子关系是反自反的、反对称的、而非传递的关系.C CS S|S SWWU US ST TXDCXDC在整数集I上定义的“小于等于”关系是自反的、反对称的、传递的关系；“小于”
19、关系是反自反的、反对称的、传递的关系；“等于”关系是自反的、反对称的、对称的、传递的关系。例例8.21设A1,2,3,4，R,，是A上的关系。幂集上的“包含”关系是自反的、反对称的、传递的关系；“真包含”关系是反自反的、反对称的、传递的关系；“相等”关系是自反的、反对称的、对称的、传递的关系。则R既不是自反的，又非反自反的；即不是对称的，也非反对称的；也不是传递的。即不具备关系的任何性质。C CS S|S SWWU US ST TXDCXDC关系性质的逻辑表示设R是集合A上的二元关系，1)R是自反的)Rx,x()Ax)(x(是永真的R不是自反的)Rx,x()Ax)(x(是永真的R是反自反的)R
20、x,x()Ax)(x(是永真的R不是反自反的)Rx,x()Ax)(x(是永真的R是对称的)Rx,y()Ry,x)(y)(x(是永真的R不是对称的)Rx,y()Ry,x)(y)(x(是永真的C CS S|S SWWU US ST TXDCXDC关系性质的逻辑表示(续)R是反对称的R是传递的)Rz,x()Rz,y()Ry,x)(z)(y)(x(是永真的R不是传递的)Rz,x()Rz,y()Ry,x)(z)(y)(x(是永真的)Rx,y()Ry,x()yx)(y)(x()yx()Rx,y()Ry,x)(y)(x(是永真的R不是反对称的)Rx,y()Ry,x()yx)(y)(x(是永真的C CS S|
21、S SWWU US ST TXDCXDC设R，S都是集合A到B的两个关系，则：RS|(xRy)(xSy)RS|(xRy)(xSy)R-S|(x R y)(x Sy)|(xy)R 3.2关系的运算RRRR关系的交、并、补、差运算（补充）根据定义，由于AB是相对于R的全集，所以AB-R,且RAB,R。C CS S|S SWWU US ST TXDCXDC定义设R是一个从集合A到集合B的二元关系，则从B到A的关系R-1|R称为R的逆关系,运算“-1”称为逆运算。关系的逆运算 P101注意：关系是一种集合，逆关系也是一种集注意：关系是一种集合，逆关系也是一种集合，因此，如果合，因此，如果R R是一个关
22、系，则是一个关系，则R R-1-1和都是关和都是关系，但系，但R R-1-1和是完全不同的两种关系，千万不要和是完全不同的两种关系，千万不要混淆。混淆。RRC CS S|S SWWU US ST TXDCXDC关系的合成运算 P96设R是一个从集合A到集合 B 的 二 元 关系，S是从集合B到集合C的二元关系(也可简单地描述为R：AB，S：BC)，则R与S的合成关系（合成关系）R S是从A到C的关系，并且：R S|(xA)(zC)(y)(yB)(xRy)(ySz)运算“”称为合成运算。注意，在合成关系中，R的后域B一定是S的前域B，否则R和S是不可合成的。合成的结果R S的前域就是R的前域A，
23、后域就是S的后域C。如果对任意的xA和zC，不存在yB，使得xRy和ySz同时成立，则R S为空，否则为非空。并且，R=R =。C CS S|S SWWU US ST TXDCXDC RSR。SABCAC1。1。11。12。2。22。23。3。33。34。4。44。42).用关系图求R S。例 R,，S,，3).用关系矩阵求R S。P99 0000100000100010MR S MR.MS 00000010010001000010000101000000C CS S|S SWWU US ST TXDCXDC设I是整数集合，R，S是I到I的两个关系：R|xI；S|xI。则：R SS RR RS
24、 S(R R)R(R S)R例|xI|xI|xI|xI|xI|xIC CS S|S SWWU US ST TXDCXDC设R是从集合A到集合B的关系，S1,S2是从集合B到集合C的关系，T是从集合C到集合D的关系，则：R(S1S2)(R S1)(R S2)R(S1S2)(R S1)(R S2)(S1S2)T(S1 T)(S2 T)1)(S1S2)T(S1 T)(S2 T)定理3.2.1 P97证明4)对任意(S1S2)T，则由合成运算知，至少存在cC,使得：(S1S2)，T。即：S1,且S2。因 此，由 S1,且 T，则 有：(S1 T),由S2,且T，则有：(S2 T)。所以，(S1 T)(
25、S2 T)。即，(S1S2)T(S1 T)(S2 T)。C CS S|S SWWU US ST TXDCXDC设R,S,T分别是从集合A到集合B，集合B到集合C，集合C到集合D的二元关系，则1)(R S)TR(S T)2)(R S)-1S-1 R-1(补充)定理3.2.7证明1)设(R S)T，cC,使得：R S，T。则由合成运算知,至少存在R(S T),又对于R S，则至少存一个bB，使得R，S。因此,由S,T,有S T，又由R和S T，知：所以(R S)T R(S T)。同理可证：R(S T)(R S)T。由集合性质知：(R S)TR(S T)。C CS S|S SWWU US ST TX
26、DCXDC2).任取(R S)-1，则R S由“”的定义知：则至少存一个bB,使得：R，S，即：R-1,S-1。由S-1和R-1,有：S-1 R-1，所以，(R S)-1 S-1 R-1。反之，任取S-1 R-1，由“”的定义知：则至少存一个bB,使得：S-1和R-1，所以：R，S。由“”知：R S。即有：(R S)-1。所以，S-1 R-1(R S)-1。由集合的定义知：(R S)-1S-1 R-1。定理(续)2)(R S)-1S-1 R-1 C CS S|S SWWU US ST TXDCXDC定义设R是集合A上的二元关系，则可定义R的n次幂Rn,该Rn也是A上的二元关系，定义如下：1.R
27、0IA|aA；2.R1；3.Rn+1Rn RR Rn。关系的幂 P98显然，Rm RnRm+n,(Rm)nRmn。C CS S|S SWWU US ST TXDCXDC定义设R是定义在A上的二元关系，若存在R的一个扩充ExtR满足：ExtR是自反的(或对称的、或传递的)。对任何的扩充Ext*R，若Ext*R是自反的(对称的、或传递的)，则：ExtR Ext*R。此时称ExtR为R的自反闭包关系(或对称闭包关系、或传递闭包关系)，分别记为r(R)(s(R)或t(R)。关系的闭包C CS S|S SWWU US ST TXDCXDC求一个关系的自反闭包，即将图中的所有无环的节点加上环；关系矩阵中对
28、角线上的值rij全变为“1”。求一个关系的对称闭包，则在图中，任何一对节点之间，若仅存在一条边，则加一条方向相反的另一条边；关系矩阵中则为：若有rij1(ij)，则令rji1(若rji1),即Ms(R)MRMR-1。求一个关系的传递闭包，则在图中，对任意节点a,b,c,若a到b有一条边，同时b到c也有一条边，则从a到c必增加一条边(当a到c无边时)；在关系矩阵中，若rij1，rjk1,则令rik1(若rik1)。利用关系图和关系矩阵求闭包C CS S|S SWWU US ST TXDCXDC设R是集合A上的二元关系，则：r(R)RIA。s(R)RR-1。1)t(R)，若|A|n，则t(R)。R
29、i1i Rin1i 定理C CS S|S SWWU US ST TXDCXDC设PP1,P2,P3,P4是四个程序，R,S是定义在P上的调用关系如下：R,S,求r(R),s(R),t(R)，r(S),s(S),t(S)。例解：r(R)RIA,。,。C CS S|S SWWU US ST TXDCXDC例(续1)s(R)RR-1,。t(R)RR2R3R4,。r(S)SIA,。C CS S|S SWWU US ST TXDCXDCs(S)SS-1,例(续2)t(S)SS2S3S4,),。C CS S|S SWWU US ST TXDCXDC定义1）集合A上的关系的自反对称闭包定义为rs(R)r(s
30、(R)2）集合A上的关系的自反传递闭包定义为rt(R)r(t(R)3）集合A上的关系的对称传递闭包定义为st(R)s(t(R)同上，我们还可定义sr(R),tr(R),ts(R),多重闭包定理设R是集合A上的关系，则：1)rs(R)sr(R)2)rt(R)tr(R)3)st(R)ts(R)C CS S|S SWWU US ST TXDCXDC设A1,2,R,则：例传递闭包和自反传递闭包，常用于形式语言与程序设计中，在计算机文献中，常把关系R的传递闭包t(R)记作R+，而自反传递闭包rt(R)记作R*。显然有(R+)+=R+。st(R)s(t(R)s(),ts(R)t(s(R)t(,),即：st
31、(R)ts(R)C CS S|S SWWU US ST TXDCXDC3.4次序关系次序关系的定义定义 设R是集合A上的自反的、反对称的、传递的关系，则称R是A上的偏序关系(记为“”)。序偶称为偏序集。设R是集合A上的反自反的、反对称的、传递的关系，则称R是A上的拟序关系(记为“”)。序偶称为拟序集。为使叙述简洁，我们常将ab并且a b记为ab。容易证明：偏序的逆关系-1也是一个偏序，我们用“”表示，读作“大于等于”；拟序的逆关系-1也是一个拟序，我们用“”表示，读作“大于”。C CS S|S SWWU US ST TXDCXDC集合A的幂集(A)上定义的“”和“”分别是偏序关系和拟序关系。是
32、偏序集，是拟序集。例实数集合R上定义的“”和“”分别是偏序关系和拟序关系。是偏序集，是拟序集。大于零的自然数集合N上定义的“整除”关系“”也是一个偏序关系,是偏序集。ALGOL或PL/I等都是块结构语言，设：Bb1,b2,b3,bn是这种语言的一个程序中的块的集合。对所有i和j，定义关系“”如下：bibj当且仅当bi被bj所包含。则“”也是一个偏序关系,是偏序集。C CS S|S SWWU US ST TXDCXDC定义 设是一个偏序集，对任意x,y A，如果xy或yx，则称x与y是可比的。若x与y是可比的，xy，并且不存在zA，使得xzy，则称y覆盖x。可比与覆盖例 1）集合A=a,b,c，
33、偏序集中，a与a,b是可比的，a与b,c不是可比的；a,b覆盖a，但a,b,c不覆盖a。偏序集中，对任意x,yA，x与y都是可比的，但是，x不覆盖y，y也不覆盖x。偏序集中，对任意x,yA，x与y都是可比的，但是，x覆盖x-1。Z:所有的整数 2)偏序集中，2与3不是可比的；2与6是可比的，并且6覆盖2；2与8是可比的，但8不覆盖2；对任意nN+，0与n是可比的，但0不覆盖n。N:自然数的全体 C CS S|S SWWU US ST TXDCXDC偏序集的哈斯图用小圆圈或点表示A中的元素，省掉关系图中所有的环。(因自反性)对任意x,yA，若xy，则将x画在y的下方，可省掉关系图中所有边的箭头。
34、(因反对称性)对任意x,yA，若y覆盖x，则x与y之间用一条线相连之，否则无线相连。(因传递性)按1),2),3)所作成的图称为哈斯图(Hasse图)。关系图关系图2 23 36 6121236362424C CS S|S SWWU US ST TXDCXDC例设A2,3,6,12,24,36,“”是A上的整除关系，画出其一般的关系图和哈斯图。哈斯图哈斯图2 23 36 6121236362424关系图关系图2 23 36 6121236362424C CS S|S SWWU US ST TXDCXDC例设集合Aa，Ba,b，Ca,b,c，Da,b,c,d。分别画出集合A、B、C、D之幂集P(
35、A)、P(B)、P(C)、P(D)上定义的“”的哈斯图。a aba,b abca,ba,cb,ca,b,c abcda,ba,cb,ca,db,dc,da,b,ca,b,da,c,db,c,da,b,c,dC CS S|S SWWU US ST TXDCXDC偏序集中的特殊元素定义设是偏序集，B是A的任何一个子集。若存在元素bB,使得对任意xB,都有xb,则称b为B的最大元素，简称最大元。若存在元素bB,使得对任意xB,都有bx,则称b为B的最小元素，简称最小元。若存在元素bB,使得对任意xB,满足bxxb,则称b为B的极大元素，简称极大元。若存在元素bB,使得对任意xB,满足xbxb,则称b
36、为B的极小元素，简称极小元。若存在元素aA,使得对任意xB,都有xa,则称a为B的上界。若存在元素aA,使得对任意xB,都有ax,则称a为B的下界。若元素aA是B的上界,元素aA是B的任何一个上界,若均有aa,则称a为B的最小上界或上确界,记aSupB。或lub若元素aA是B的下界,元素aA是B的任何一个下界,若均有aa,则称a为B的最大下界或下确界,记aInfB。或glbC CS S|S SWWU US ST TXDCXDC设是一偏序集，B是A的子集。则：若bB是B的最大元b是B的极大元、上界、最小上界；若bB是B的最小元b是B的极小元、下界、最大下界；若aA是B的最小上界，且aBa是B的最
37、大元；若aA是B的最大下界，且aBa是B的最小元；若B存在最大元，则B的最大元是惟一的；若B存在最小元，则B的最小元是惟一的；若bB是B的极大元，且b是唯一的b是B的最大元；若bB是B的极小元，且b是唯一的b是B的最小元；若B存在最小上界，则B的最小上界是惟一的；1.若B存在最大下界，则B的最大下界是惟一的。定理C CS S|S SWWU US ST TXDCXDC集合的划分 P120定义设A是一个集合，A1,A2,A3.Am是A的任何m个子集，如果A1,A2,A3.Am满足：对一切的ij(i,j1,2,3,.,m)，都有AiAj。1)。则称集合(A)A1,A2,A3,.,Am为集合A的一个划
38、分,而A1,A2,A3,.Am叫做这个划分的块。AAim1i C CS S|S SWWU US ST TXDCXDC例上述划分用文氏图可表示如下：对任何一个集合，我们要对集合中的元素进行划分，那么，按照“怎样”的方式才能得到“正确”的划分呢？通常，不严格的“分类”是要闹出笑话的。下面，我们将会看到集合中的元素如果按照“等价关系”进行“分类”时，就可得到正确的划分。C CS S|S SWWU US ST TXDCXDC等价关系定义设R是定义在集合A上的关系，如果R是自反的、对称的、传递的，则称此关系R为A上的等价关系。例3.4.11）在全体中国人所组成的集合上定义的“同姓”关系，就是具备自反的、
39、对称的、传递的性质，因此，就是一个等价关系；对任何集合A,考虑RAA,则R是A上的等价关系；三角形的“相似关系”、“全等关系”等都是等价关系；直线的“平行关系”不是等价关系，因为它们不是自反的。幂集上定义的“”，整数集上定义的“”都不是等价关系，因为它们不是对称的。2)“朋友”关系，则不是等价关系，因它不是传递的。C CS S|S SWWU US ST TXDCXDC以m为模的同余关系R称为Z上以m为模的同余关系，一般记xRy为xy(mod m)称为同余式。如用resm(x)表示x除以m的余数，则xy(mod m)resm(x)resm(y)。此时，R将Z分成了如下m个子集：,-3m,-2m,
40、-m,0,m,2m,3m,-3m+1,-2m+1,-m+1,1,m+1,2m+1,3m+1,-3 m+2,-2 m+2,-m+2,2,m+2,2m+2,3m+2,-2m-1,-m-1,-1,m-1,2m-1,3m-1,4m-1,C CS S|S SWWU US ST TXDCXDC以m为模的同余关系这m个Z的子集具有的特点：在同一个子集中的元素之间都有关系R，而不同子集的元素之间无关系R。也就是说，通过等价关系，将集合分成若干子集，使这些子集构成的集合就是Z的一个划分。例如我们常见的时钟上的时针重复关系即为m=12，A=0,1,2,3,23，此等价关系R的关系图如下图所示，A被分成了12个子集0,12、1,13、2,14、11,23。
