《离散数学：r03关系d》由会员分享，可在线阅读，更多相关《离散数学：r03关系d（29页珍藏版）》请在金锄头文库上搜索。
1、1n关系的概念及运算关系的概念及运算n关系的性关系的性质n关系的关系的闭包运算包运算n等价关系等价关系n序关系序关系 关系关系2等价关系等价关系n设R为集合集合A上的等价关系，上的等价关系，对任何任何aA，集合集合aR=x|xA, xRa称称为元素元素a关于关于R的的等价等价类(equivalence class)。可以。可以简记为a，称称a为等价等价类a的的代表元素代表元素。如果等价。如果等价类个数有限，个数有限，则R的不同等价的不同等价类的个数称的个数称为R的秩的秩；否；否则秩是无限的。秩是无限的。因因为aaR，所以所以aR非空。非空。例：写出整数集合例：写出整数集合I上的模上的模3同余关
2、系的等价同余关系的等价类。0R=3R=-3R=.1R=4R=-2R=.2R=5R=-1R=. 该等价关系等价关系R的秩的秩为3。 例：集合例：集合A上相等关系的秩等于？上相等关系的秩等于？A的元素个数。3定理定理2： 设R是非空集合是非空集合A上的等价关系上的等价关系,aRb当且当且仅当当aR=bR证 ：1)充分性：充分性： 因因为aaR 且且 aR=bR, 即即abR, 所以所以aRb。 2)必要性：必要性： 对任意任意xaR, 有有xRa， 又因又因为aRb,由由传递性可知性可知xRb，即，即xbR 所以所以aR bR ，同理可，同理可证bR aR 故故aR=bR 。等价关系等价关系4等价
3、关系等价关系n设给定集合定集合A上的等价关系上的等价关系R，其等价其等价类集合集合aR|aA称称作作A关于关于R的商集的商集(quotient set)，记为A/R。例如，整数集合上同余模例如，整数集合上同余模3关系关系R的商集的商集为 I/R=0R,1R,2R。其中，其中， 0R 1R 2R=I，且任意两个等价且任意两个等价类的交的交为空集，空集，于是有下述定理：于是有下述定理：5等价关系等价关系定理定理3：设R是非空集合是非空集合A上的等价关系，上的等价关系，则有有(a) 任取任取 xA, xR ;(b) 任取任取x,yA，或者，或者xR=yR, 或者或者xRyR= ；(c)证明明: (a
4、) 任取任取xA, 因因为R是自反的，所以有是自反的，所以有xRx，即，即xxR ， 故故 xR ; (b) 若若xRyR , 则存在某元素存在某元素z, zxR和和zyR 。 根据定理根据定理2, 得得 xR = zR = yR 。 又因又因xR 和和 yR 都非空都非空, 所以所以xRyR= 和和xR=yR不能兼得。不能兼得。 6等价关系等价关系定理定理3：设R是非空集合是非空集合A上的等价关系，上的等价关系，则有有(a) 任取任取 xA, xR ;(b) 任取任取x,yA，或者，或者xR=yR, 或者或者xRyR= ；(c)证明明: (c)A上的等价关系上的等价关系R可以诱导出可以诱导出
5、A的划分的划分,即即A上关于上关于R的商集的商集A/R7例例. 设A=a,b,c,d,e，R是是A上的等价关系，上的等价关系， R=,， 求由求由R诱导的的A上的划分上的划分 。解：解： = a,b,c,d,e等价关系等价关系8定理定理4：设是非空集合是非空集合A的一个划分的一个划分,则A上的二元关系上的二元关系: 是是A上的等价关系。上的等价关系。证：(a) 对任意任意aA，因因为a是在是在的某的某块B中中,所以所以aRa， 故故R自反自反。 (b)如果如果aRb,那么有某那么有某块B,使使aB和和bB， 所以所以bRa，故故 R是是对称的。称的。 (c)如果如果aRb和和bRc,那么存在那
6、么存在B1和和B2,使使 a,bB1和和b,cB2,即即bB1B2,由划分的定由划分的定义, 要么要么B1B2= ,要么要么B1=B2,所以所以B1=B2。 因此因此,cB1,有有aRc，故故 R是是传递的。的。通通过该定理可知定理可知A的划分也可的划分也可诱导出出A上的等价关系上的等价关系。等价关系等价关系9等价关系等价关系例：例：设A=a,b,c,d,e，有一个划分有一个划分S=a,b,c,d,e，求由划求由划 分分S确定的确定的A上的一个等价关系上的一个等价关系R。解：解： R=(a,ba,b)(cc)(d,ed,e) =, ,； = ,10等价关系等价关系定理定理5：设R1和和R2为非
7、空集合非空集合A上的等价关系，上的等价关系，则R1=R2当且当且 仅当当A/R1=A/R2。（。（等价关系与划分一一等价关系与划分一一对应）证明：明：必要性：必要性：充分性：11等价关系和划分只是相同概念的不同描述，本等价关系和划分只是相同概念的不同描述，本质相同。相同。例：例：设A=a,b,c,d,e，构造构造A上的一个等价关系上的一个等价关系S，使得，使得|S|=7。例：例：设A=a,b,c,，求求A上所有的等价关系。上所有的等价关系。等价关系等价关系12 3.4 序关系序关系n设A是一个集合，如果是一个集合，如果A上的一个关系上的一个关系R，满足足自反性、反自反性、反对称性和称性和传递性
8、性，则称称R是是A上的一个上的一个偏序关系偏序关系(partial order)，记为“”。序偶。序偶称称为偏序集偏序集(partially ordered set, poset) 。 例如：在例如：在实数集数集R上的小于等于关系上的小于等于关系“”是偏序关系是偏序关系。 在集合在集合A的的幂集上的包含关系集上的包含关系“ ”是偏序关系。是偏序关系。13偏序关系偏序关系n在偏序集在偏序集中，如果中，如果x,yA，xy，xy且没有其它元素且没有其它元素z满足足xz，zy，则称元素称元素y盖住盖住元素元素x。盖住集盖住集CovA定定义为CovA=|x,yA,且且y盖住盖住x。例：例：给定集合定集合
9、A=1,2,3,4,6,12，设R为A上的整除关系，即上的整除关系，即R=|x整除整除y，验证R是是A上的偏序关系，并求上的偏序关系，并求COV A。解：解：证略。略。 R=, , , COV A=,14偏序关系偏序关系n偏序关系偏序关系图哈斯哈斯图(hasse diagram)用小用小圆圈代表元素圈代表元素如果如果xy，且且xy，则将代表将代表y的小的小圆圈画在代表圈画在代表x的小的小圆圈圈之上之上如果如果COV A，则在在x与与y之之间用直用直线相相连。 将哈斯将哈斯图的的边方向朝上，构造它的自反方向朝上，构造它的自反传递闭包，就包，就可得到可得到该偏序关系的关系偏序关系的关系图。15偏序
10、关系偏序关系例：画哈斯例：画哈斯图a、P=1,2,3,4，的哈斯的哈斯图；b、A=1,2,3,4,6,12，的哈斯的哈斯图； b、COV A=,解：解：a、 COV P=,1643212142316偏序关系偏序关系n设偏序集偏序集，在在A的子集中，如果每两个元素都是有关系的子集中，如果每两个元素都是有关系的，的，则称称这个子集个子集为链(chain)。在。在A的一个子集中，如果每的一个子集中，如果每两个元素都是无关的，两个元素都是无关的，则称称这个子集个子集为反反链(anti-chain)。 约定定：若若A的子集只有的子集只有单个元素，个元素，则这个子集既是个子集既是链，又是，又是反反链。如：
11、如：271568以左面的哈斯以左面的哈斯图为例，例，1,2,8,56及及其子集都是其子集都是链，2,7,7,8都是反都是反链。17偏序关系偏序关系n设偏序集偏序集，且且B是是A的子集，的子集，对于于B中某一元素中某一元素b，如果如果B中没有任何元素中没有任何元素x，满足足bx且且bx，则称称b为B的的极大元极大元(maximal element)。xb，则称称b为B的的极小元极小元(minimal element)。例：例：设集合集合A=2,3,5,7,14,15,21，其偏序关系其偏序关系图如下如下图所示，所示，求子集求子集B=2,3,7,14,21的极大元和极小元。的极大元和极小元。273
12、5152114B的极小元集合的极小元集合为2,3,7，极大元集合极大元集合为14,21极大元和极小元可以存在也可以不存在，极大元和极小元可以存在也可以不存在，而且当它而且当它们存在存在时可以不唯一。可以不唯一。？18偏序关系偏序关系n设偏序集偏序集，且且B是是A的子集，若的子集，若B中某一元素中某一元素b，对于于B中每一元素中每一元素x，满足足xb ，则称称b为的的最大元最大元(greatest element)。满足足bx ，则称称b为的的最小元最小元(least element)。27114以左面的哈斯以左面的哈斯图为例，例，若若B=1,2，则2是是B的最大元，的最大元，1是是B的最小元；
13、的最小元；若若B=2,7，则没有最大元和最小元；没有最大元和最小元；若若B=1,2,7，则1是最小元，没有最大元。是最小元，没有最大元。设偏序集设偏序集，且且B是是A的子集，若的子集，若B中有最大中有最大(最小最小)元，则必是唯一的。元，则必是唯一的。19偏序关系偏序关系n设偏序集偏序集，且且B是是A的子集，的子集，若若A中某一元素中某一元素a，对于于B中每一元素中每一元素x，满足足xa ，则称称a为B的的上界上界(upper bound)。满足足ax ，则称称a为B的的下界下界(lower bound)。以左面的哈斯以左面的哈斯图为例，例，若若B=1,2，则2,8,14是是B的上界的上界，1
14、是下界；是下界；若若B=2,7，则14是是B的上界的上界，1是下界；是下界；若若B=8,14，则2,1是是B的下界的下界,B没有上界；没有上界；上界和下界不是唯一的上界和下界不是唯一的27114820偏序关系偏序关系n设偏序集偏序集，且且B是是A的子集，的子集，若若a为B的上界，的上界，对于于B的所有上界的所有上界y，满足足ay ，则称称a 为B的的最小上界最小上界(上确界上确界)(Least Upper Bound)，记为LUB B。若若b为B的下界，的下界，对于于B的所有下界的所有下界z，满足足zb ，则称称b 为B的的最大下界最大下界(下确界下确界)(Greatest Lower Bou
15、nd)，记为 GLB B。21偏序关系偏序关系263362412以左面的哈斯以左面的哈斯图为例，例，若若B=2,3,6， 则最小上界最小上界为6，没有最大下界；，没有最大下界；若若B=6,12， 则最小上界最小上界为12，最大下界，最大下界为6。设偏序集设偏序集，且且B是是A的子集，若的子集，若B 有最大下界有最大下界(最小上界最小上界)，则必是唯一的。，则必是唯一的。22 例例. 偏偏序序集集合合I,设B=2iiN,那那么么B的的最最大大元元素素、最最小小元元素素、极极大大元元素素、极极小小元元素素、上上界界、下下界界、最最小小上上界界、 最最大大下界分下界分别是什么？是什么？ B 没有最大
16、元素；没有最大元素； B 的最小元素是的最小元素是0； B 没有极大元素；没有极大元素； B 的极小元素是的极小元素是0； B 也没有上界和最小上界；也没有上界和最小上界； B 的下界集合是的下界集合是iiIi0,0是最大下界。是最大下界。 偏序关系偏序关系23偏序关系偏序关系nB的最大（小）元和极大（小）元都必的最大（小）元和极大（小）元都必须是子集是子集B的元素，而的元素，而B的下（上）界和最小上界（最大下界）可以是也可以不是的下（上）界和最小上界（最大下界）可以是也可以不是B的元素。的元素。n极大元和上界可以存在也可以不存在，且当它极大元和上界可以存在也可以不存在，且当它们存在存在时，也
17、，也可能是不唯一的。可能是不唯一的。对极小元和下界也有极小元和下界也有类似似结论。但但对非空非空有限偏序集合，其极大元和极小元有限偏序集合，其极大元和极小元总是存在的。是存在的。n设偏序集偏序集，且且B是是A的子集，的子集，如果如果b是是B的最大元，的最大元，则b是是B的极大元和最小上界；的极大元和最小上界；如果如果b是是B的一个上界，且的一个上界，且b在在B中，中，则b是是B的最大元。的最大元。同理可得最小元、极小元和最大下界的关系。同理可得最小元、极小元和最大下界的关系。24拟序关系拟序关系n拟序集合：如果集合序集合：如果集合A上的二元关系上的二元关系R是是反自反的和反自反的和传递的的，那
18、么那么R叫做叫做A上的上的拟序序。记为。拟序是反序是反对称的。因称的。因为如果如果xRy，yRx，则有有xRx，而而R是是反自反的，所以反自反的，所以xRy，yRx不能同不能同时为真，真，则有有在集合在集合A上，上，v如果如果R是一是一拟序，那么序，那么r(R)=RIA是偏序；是偏序；v如果如果R是一偏序，那么是一偏序，那么R-IA是一是一拟序。序。即即拟序集合和偏序集合的唯一区序集合和偏序集合的唯一区别是相等关系。是相等关系。25线序关系线序关系n设偏序集偏序集，如果如果A是一个是一个链，则称称为全序集合全序集合或或称称线序集合序集合(linearly ordered set)，此，此时，二
19、元关系，二元关系称称为全序全序或或线序序(linear order)。 全序集全序集就是就是对任意任意A中的两个元素中的两个元素x，y，或者有或者有xy，或者有或者有yx成立。成立。 全序集合的哈斯全序集合的哈斯图是一是一竖立的立的结点序列，每一点序列，每一对相相邻结点都用一条弧点都用一条弧连通。通。例：例： (a)I, (b)1,2,3,6,整除整除 (c)(A),是是线序集合序集合不是不是线序集合序集合如果如果A是多于一个元素的集合是多于一个元素的集合,那么不是那么不是线序集合序集合。26良序关系良序关系n任一任一线序集合，假如它的每一非空子集都存在最小元，称序集合，假如它的每一非空子集都
20、存在最小元，称这种偏序集种偏序集为良序良序(well order)。如：正整数集上的如：正整数集上的 整数集上的整数集上的 N, A=0,1上的上的是良序集合是良序集合是良序集合是良序集合不是良序集合不是良序集合不是良序集合不是良序集合27良序关系良序关系n每一个有限的全序集合，一定是良序集合。每一个有限的全序集合，一定是良序集合。证明：明：设A=a1,a2,.an，令令是全序集合，是全序集合，现在假定在假定 不是良序集合，那么必定存在一个非空集合不是良序集合，那么必定存在一个非空集合B， 是是A的子集，在的子集，在B中不存在最小元，由于中不存在最小元，由于B是一个有限是一个有限 集合，故一定
21、存在两个元素集合，故一定存在两个元素x与与y是无关的，由于是无关的，由于 是全序集合，是全序集合，x,yA，所以所以x，y必有关系，得出矛盾，必有关系，得出矛盾， 故故必是良序集合。必是良序集合。28小结小结n关系的定关系的定义、表示和运算、表示和运算n集合上的二元关系及性集合上的二元关系及性质n关系的关系的闭包运算包运算n等价关系与划分等价关系与划分n偏序、全序、良序及其相互关系偏序、全序、良序及其相互关系 哈斯哈斯图及极大（小）元、最大（小）元、上（下）及极大（小）元、最大（小）元、上（下）界、上（下）确界界、上（下）确界29作业作业n3-4 1、5、10(1)(2)n3-5 3、9、11、13
