第7章特殊关系北极熊校园

1、12022-3-272022-3-27第三篇第三篇 二元关系二元关系第第7 7章章 特殊关系特殊关系22022-3-272022-3-277.0 7.0 内容提要内容提要集合的概念集合的概念1集合的表示方法集合的表示方法2偏序关系偏序关系3良序关系良序关系4等价关系等价关系1拟序关系拟序关系2全序关系全序关系432022-3-272022-3-277.17.1本章学习要求本章学习要求重点掌握重点掌握一般掌握一般掌握了解了解11 1 几个特殊关几个特殊关系的概念系的概念2 2 等价和偏序等价和偏序关系的证明关系的证明3 3 等价类和商等价类和商集的计算集的计算4 84 8个特殊元个特殊元31 1

2、 拟序、全序拟序、全序和良序关系的和良序关系的相关性质。相关性质。 21 1 拟序、全序拟序、全序和良序关系的和良序关系的定义；定义；2 2拟序与偏序关拟序与偏序关的联系的联系3 3 拟序、全序、拟序、全序、良序的联系。良序的联系。42022-3-272022-3-27判定下列关系具有哪些性质判定下列关系具有哪些性质1 1、在全体中国人所组成的集合上定义的、在全体中国人所组成的集合上定义的“同姓同姓”关系；关系；2 2、对任何非空集合、对任何非空集合A A，A A上的全关系上的全关系；3 3、三角形的、三角形的4 4、直线的、直线的“平行关系平行关系”；5 5；解：解：1 1，2 2，3 3都

3、都具有具有；4 4 具有具有反自反，对称和传递性，反自反，对称和传递性，不具有自反性；不具有自反性；5 5 具有自反和对称性，具有自反和对称性，不具有传递性。不具有传递性。52022-3-272022-3-277.2 7.2 等价关系等价关系定义定义7.2.17.2.1设设R R是定义在非空集合是定义在非空集合A A上的关系，如上的关系，如果果R R是是自反的、对称的、传递的自反的、对称的、传递的，则称，则称R R为为A A上的上的等等价关系价关系。由定义由定义7.2.17.2.1知：知：（1 1）关系关系R R是等价关系是等价关系当且仅当当且仅当R R同时具备自同时具备自反性、对称性和传递性

4、；反性、对称性和传递性；（2 2）关系）关系R R不是等价关系不是等价关系当且仅当当且仅当R R不具备自不具备自反性或对称性或传递性。反性或对称性或传递性。62022-3-272022-3-27例例7.2.17.2.1 1. 1. 幂集上定义的幂集上定义的“ ”关系；关系； 2. 2. 整数集上定义的整数集上定义的“ ”关系；关系； 3. 3. 全体中国人所组成的集合上定义的全体中国人所组成的集合上定义的“同性别同性别”关系。关系。不具有对称性不具有对称性不具有对称性，自反性不具有对称性，自反性是等价关系是等价关系判定下列关系是否是等价关系判定下列关系是否是等价关系? ?72022-3-272

5、022-3-27例例7.2.27.2.2在时钟集合在时钟集合A A1,1,24,24上上定义定义整除关系：整除关系：R R|x,y|x,y A)(x-y)A)(x-y)被被1212所整除所整除) )。（1 1）写出）写出R R中的所有元素；中的所有元素；（2 2）画出）画出R R的关系图；的关系图；（3 3）证明）证明R R是一个等价关系。是一个等价关系。82022-3-272022-3-27例例7.2.2 7.2.2 解解（2 2）此等价关系的关系图：）此等价关系的关系图：（1 1）R=, R=, , , , , , , , , , , , , , , , , , , 113图图7.2.12

6、14315122492022-3-272022-3-271 1、对、对 xAxA，有，有(x-x)(x-x)被被1212所整除，所以所整除，所以RR，即，即R R是自反的是自反的。2 2、对、对 x,yA,x,yA,若若R,R,有有(x-y)(x-y)被被1212整除，则整除，则(y-x)(y-x)-(x-y)-(x-y)被被1212整除整除, ,所以所以,R,R, ,即即R R是对称的是对称的。3 3、对、对 x,y,zA,x,y,zA,若若RR且且R,R,有有(x-y)(x-y)被被1212所整除且所整除且(y-z)(y-z)被被1212所整除所整除, ,所以所以(x-z)(x-z)(x-

7、y)(x-y)(y-(y-z)z)被被1212所整除所整除, ,所以所以,R,R, ,即即R R是传递的是传递的. .由由1,2,31,2,3知知R R是等价关系。是等价关系。例例7.2.2 7.2.2 解解 ( (续续) )102022-3-272022-3-27从例从例7.2.27.2.2可以看出可以看出关系关系R R将集合将集合A A分成了如下的分成了如下的1212个子集：个子集： 1, 13, 2,14, 3,15, 4,16, 5,17, 1, 13, 2,14, 3,15, 4,16, 5,17, 6, 18, 7,19, 8,20, 9,21, 10,22, 6, 18, 7,1

8、9, 8,20, 9,21, 10,22, 11,23, 12,2411,23, 12,24。这这1212个个A A的子集具有的子集具有如下特点如下特点：1 1、在同一个子集中的元素之间都有关系、在同一个子集中的元素之间都有关系R R；2 2、不同子集的元素之间无关系、不同子集的元素之间无关系R R。112022-3-272022-3-27例例7.2.37.2.3设设n n为正整数，考虑整数集合为正整数，考虑整数集合Z Z上的上的整除关系整除关系如下：如下：R=|x,yZ(n|(x-y)R=|x,yZ(n|(x-y) 证明证明 (1)(1)对对 x x Z Z，有，有n|(x-x)n|(x-x

9、)，所以所以 R R，即即R R是自反的。是自反的。(2)(2)对对 x,yx,y Z Z，若，若 R R，即即n|(x-y)n|(x-y)，所以，所以m|(y-x)m|(y-x)，所以，所以， R R，即，即R R是对称的是对称的。(3)(3)对对 x,y,zx,y,z Z Z，若，若 R R且且 R R，有，有n|(x-y)n|(x-y)且且n|(y-z)n|(y-z)，所以由，所以由(x-z)=(x-y)+(y-z)(x-z)=(x-y)+(y-z)得得n|(x-z)n|(x-z)，所以，所以， R R，即，即R R是传递是传递的。的。由由(1)(1)、(2)(2)、(3)(3)知，知，

10、R R是是Z Z上的等价关系。上的等价关系。 122022-3-272022-3-27以以n n为模的同余关系为模的同余关系例例7.2.37.2.3：设：设n n为正整数，考虑整数集合为正整数，考虑整数集合Z Z上的整除上的整除关系关系R R如下：如下：R=|x,yZ (n|(x-y),R=|x,yZ (n|(x-y),证证明明R R是一个等价关系。是一个等价关系。证明：上述证明：上述R R称为称为Z Z上上以以n n为模的同余关系为模的同余关系，记，记xRyxRy为为x xy(mod n)y(mod n)称为称为同余式同余式。如用。如用resresn n(x)(x)表示表示x x除以除以n

11、n的余数，则的余数，则x xy(mod n) y(mod n) resresn n(x)(x)resresn n(y)(y)。132022-3-272022-3-27此时，此时，R R将将Z Z分成了如下分成了如下n n个子集：个子集： ,-3n,-2n,-n,0,n,2n,3n,-3n,-2n,-n,0,n,2n,3n, ,-3n+1,-2n+1,-n+1,1,n+1,2n+1,3n+1,-3n+1,-2n+1,-n+1,1,n+1,2n+1,3n+1, , -3n+2,-2n+2,-n+2,2,n+2,2n+2,3n+2, -3n+2,-2n+2,-n+2,2,n+2,2n+2,3n+2,

12、 ,-2n-1,-n-1,-1,n-1,2n-1,3n-1,4n-1,-2n-1,-n-1,-1,n-1,2n-1,3n-1,4n-1, 以以n n为模的同余关系为模的同余关系142022-3-272022-3-27说明说明 同样地，这同样地，这n n个个Z Z的子集具有的子集具有如下特点：如下特点： 1 1、在同一个子集中的元素之间都有关系、在同一个子集中的元素之间都有关系R R； 2 2、不同子集的元素之间没有关系、不同子集的元素之间没有关系R R； 3 3、不同子集的交集是空集；、不同子集的交集是空集； 4 4、所有这些子集的并集就构成集合、所有这些子集的并集就构成集合Z Z。15202

13、2-3-272022-3-277.2.2 7.2.2 集合的划分集合的划分定义定义7.2.2给定非空集合给定非空集合A，设有集合，设有集合S=S1,S2,S3.Sm.如果满足如果满足 Si A且且Si，i1,2,.,m； SiSj，ij，i,j1,2,.,m； 。mii 1SA则集合则集合S S称作集合称作集合A A的一个的一个(Partition)(Partition)，而，而S S1 1,S,S2 2,.S,.Sm m叫做这个划分的叫做这个划分的(Block)(Block)或或(Class)(Class)。162022-3-272022-3-27例例7.2.47.2.4试给出非空集合试给出

14、非空集合A A上上2 2个不同的划分个不同的划分解解（1 1）在）在A A中设定一个非空子集中设定一个非空子集A A1 1，令令A A2 2=A-A=A-A1 1，则根则根据集合划分的定义，据集合划分的定义，AA1 1,A,A2 2 就构成了集合就构成了集合A A的一个的一个划分，见图划分，见图 (a) (a)；（2 2）在在A A中设定两个不相交非空子集中设定两个不相交非空子集A A1 1和和A A2 2，令，令A A3 3=A-=A-(A(A1 1AA2 2) )，则根据集合划分的定义，则根据集合划分的定义，AA1 1,A,A2 2,A,A3 3 就就构成了集合构成了集合A A的一个划分，

15、见图的一个划分，见图 (b) (b)。AAA1A1A2(a)(b)172022-3-272022-3-27例例7.2.57.2.5设设设设A=0,1,2,4,5,8,9A=0,1,2,4,5,8,9， 1 1、写出、写出R R是是A A上的上的以以4 4为模的同余关系为模的同余关系R R的所有元素；的所有元素；2 2、求分别、求分别与元素与元素1,2,3,41,2,3,4有关系有关系R R的所有元素所作成的所有元素所作成的集合。的集合。解：解：1 1、R=,R=,.,. 显然，显然，R R是是A A的一个等价关系。的一个等价关系。182022-3-272022-3-27集合集合1,5,91,5

16、,9称为元素称为元素1 1关于等价关系关于等价关系R R的的等价类，等价类，记为记为11R R，即，即11R R =1,5,9;=1,5,9;例例7.2.5 7.2.5 解解2 2、与元素、与元素1 1有关系有关系R R的所有元素所作成的集合的所有元素所作成的集合1,5,9;1,5,9; 与元素与元素2 2有关系有关系R R的所有元素所作成的集合的所有元素所作成的集合2;2;与元素与元素4 4有关系有关系R R的所有元素所作成的集合的所有元素所作成的集合0,4,8.0,4,8.2R= 2, 44R R = = 0,4,8.0,4,8.192022-3-272022-3-277.2.3 7.2.

17、3 等价类与商集等价类与商集定义定义7.2.37.2.3 设设R R是是非空集合非空集合A A上的等价关系，对任意上的等价关系，对任意xAxA，称集合，称集合 xxR Ry|yARy|yAR为为x x关于关于R R的的等价类等价类(equivalence class)(equivalence class)，或叫作，或叫作由由x x生成的一个生成的一个R R等价类，其中等价类，其中x x称为称为xxR R的的生成元生成元( (或叫或叫代表元代表元，或，或典型元典型元)(generator) )(generator) 。202022-3-272022-3-27由定义由定义7.2.37.2.3可以看

18、出：可以看出：（1 1）等价类产生的前提等价类产生的前提是是A A上的关系上的关系R R必须是等价必须是等价关系；关系；（2 2）A A中所有中所有与与x x有关系有关系R R的元素的元素y y构成了构成了xxR R；（3 3）A A中中任意一个元素任意一个元素一定一定对应对应一个一个由它生成的等由它生成的等价类；价类；（4 4）R R具有具有自反性自反性意味着对意味着对 xAxA，xxR R；（5 5）R R具有具有对称性对称性意味着对任意意味着对任意x x，yAyA，若有若有y yxxR R，则一定有，则一定有x xyyR R。 212022-3-272022-3-27例例7.2.5(7.

19、2.5(续续) )设设A=0,1,2,4,5,8,10A=0,1,2,4,5,8,10，R R是是A A上的以上的以4 4为模的同余为模的同余关系。关系。求求（1 1）R R的所有等价类；（的所有等价类；（2 2）画出）画出R R的关系图。的关系图。解解: (1): (1)11R R1,5,91,5,955R R99R R；22R R=2=2； 44R R0,4,8=0,4,8=00R R88R R。图图7.2.32159159222022-3-272022-3-27定理定理7.2.17.2.1设设R R是非空集合是非空集合A A上的等价关系，则有下面的结论成立：上的等价关系，则有下面的结论成

20、立：1)1)对对 x x A A，xxR R； 2)2)对对 x,yAx,yA， a)a)如果如果y yxxR R，则有，则有 xxR R=y=yR R， b)b)如果如果y xy xR R，则有，则有xxR RyyR R。3)3) A A； Rx Ax232022-3-272022-3-27定理定理7.2.17.2.1的证明的证明2)2) 对任意对任意x,yAx,yA，若若yxyxR R，则，则RR。 a)a) 对对 zxzxR R，则有：，则有：RR，又，又RR， 由由R R的对称性有：的对称性有：RR，由，由R R的传递性的传递性有：有： RR。所以所以zyzyR R，即：，即：xxR

21、R yyR R。 证明：证明：1 1）对任意）对任意xAxA，因为因为R R是等价关系是等价关系，所以，所以R R是是自反的，自反的，因此因此RR，即，即xxxxR R，故，故xxR R。 b) b) 对对 zyzyR R，则有：，则有：RR，又，又RR， 由由R R的传递性有：的传递性有：RR。所以，。所以，zxzxR R，即：，即： yyR R xxR R。所以，由所以，由a)a)和和b)b)知：知：xxR RyyR R。242022-3-272022-3-273 3）因为对任意因为对任意xAxA，xxR R A A，所以所以 A A。定理定理7.2.17.2.1的证明（续）的证明（续）

22、Rx Ax Rx Ax Rx Ax Rx Ax对对任意任意xAxA，因，因R R是自反的，所以是自反的，所以RR，即，即xxxxR R。所以所以xx，即，即A A 。故。故=A=A。 (2(2) ) 若若y y xxR R，设设xxR RyyR R, ,则存在则存在zxzxR RyyR R。即即zxzxR R，zyzyR R，则有：，则有：RR，RR，由，由R R的对称性，的对称性，RR。由。由R R的传递性有：的传递性有：RR，即，即yxyxR R，矛盾矛盾。所以。所以xxR RyyR R。252022-3-272022-3-27商商 集集定义定义7.2.47.2.4 设设R R是非空集合是

23、非空集合A A上的上的等价关系等价关系，由由R R确定的一切等价类的集合确定的一切等价类的集合，称为集合，称为集合A A上关于上关于R R的的商集商集(QuotientSet)(QuotientSet)，记为，记为A/RA/R，即，即 A/RA/RxxR R|(xA)|(xA)例例7.2.67.2.6 设集合设集合A=0,1,2,4,5,8,10A=0,1,2,4,5,8,10，R R为为A A上以上以4 4为模的同余关系为模的同余关系。求。求A/RA/R。 根据例根据例7.2.57.2.5，商集，商集A/R=0A/R=0R R,1,1R R,2,2R R=0,4,8,1,5=0,4,8,1,

24、5，9,29,2。262022-3-272022-3-27例例7.2.77.2.7设集合设集合A=1,2,3,4,5,8A=1,2,3,4,5,8，R R为为A A上以上以3 3为模的同余为模的同余关系。关系。求求A/RA/R。解解 根据例根据例7.2.37.2.3知，知，A A上以上以3 3为模的同余关系为模的同余关系R R是等是等价关系。价关系。因为因为11R R=1,4=4=1,4=4R R,2,2R R=5=5R R=8=8R R=2,5,8,=2,5,8, 3 3R R=3=3，所以根据商集的定义，所以根据商集的定义，A/R=1A/R=1R R,2,2R R,3,3R R=1,4,2

25、,5,8,3=1,4,2,5,8,3。272022-3-272022-3-27计算商集计算商集A/RA/R的通用过程：的通用过程：（1 1）任选任选A A中一个元素中一个元素a a，计算，计算aaR R；（2 2）如果）如果aaR RAA，任选一个元素任选一个元素bA-abA-aR R，计，计算算bbR R；（3 3）如果）如果aaR RbbR RAA，任选一个元素任选一个元素cA-cA-aaR R-b-bR R，计算，计算ccR R；以此类推，以此类推，直到直到A A中所有元素都包含在计算出的中所有元素都包含在计算出的等价类中。等价类中。282022-3-272022-3-277.2.47.

26、2.4等价关系与划分等价关系与划分 设设R R是非空集合是非空集合A A上的等价关系，上的等价关系，则则A A对对R R的商集的商集A/RA/R是是A A的一个划分的一个划分，称之为由，称之为由R R所导所导出的等价划分。出的等价划分。给定集合给定集合A A的的一个划分一个划分 =A=A1 1,A,A2 2, ,A,An n, , 则由该划分确定的关系则由该划分确定的关系R=(AR=(A1 1A A1 1)(A)(A2 2A A2 2)(A(An nA An n) )是是A A上的等价关系上的等价关系。我们称该关系。我们称该关系R R为由划分为由划分所导出的等价关系。所导出的等价关系。2920

27、22-3-272022-3-27证明证明 1 1）R R是自反的是自反的对对 xAxA，因为，因为(A)(A)是是A A的一个划分，所以存在一个划分的一个划分，所以存在一个划分块块A Ai i(A)(A)，使得，使得xAxAi i，显然，显然x x和和x x同属于同属于(A)(A)的一个的一个划分块划分块A Ai i，故，故RR，所以，所以R R是自反的。是自反的。 2)R2)R是对称的是对称的 对对 x,yAx,yA，若，若RR，则，则x x和和y y同属于同属于(A)(A)的一个的一个划分块划分块A Ai i，因此，因此y y和和x x同属于同属于(A)(A)的一个划分块的一个划分块A A

28、i i，故，故RR，所以，所以R R是对称的是对称的。302022-3-272022-3-27( (续续) )3) R3) R是传递的是传递的对对 x,y,zAx,y,zA，若，若RR，RR，则，则x x和和y y同属于同属于(A)(A)的一个划分块的一个划分块A Ai i，y y和和z z同属于同属于(A)(A)的一个划分的一个划分块块A Aj j，因此，因此yAyAi iAAj j，由于不同的划分块交为空，所，由于不同的划分块交为空，所以以A Ai i=A=Aj j，因此，因此x x和和z z同属于同属于(A)(A)的一个划分块的一个划分块A Ai i，即，即RR，所以，所以R R是传递的

29、。是传递的。综上，由综上，由1)1)、2)2)、3)3)知，知，R R是是A A上的等价关系。上的等价关系。 说明：说明：集合集合A A上的等价关系和上的等价关系和A A的划分是一一对应的。的划分是一一对应的。312022-3-272022-3-27例例7.2.87.2.8解解只有只有1 1个划分块的划分为个划分块的划分为S S1 1，见图，见图(a)(a)；具有；具有2 2个划分块的划分个划分块的划分为为S S2 2、S S3 3和和S S4 4，见图，见图(b)(b)、(c)(c)和和(d)(d)，具有，具有3 3个划分块的划分个划分块的划分为为S S5 5，见图，见图(e)(e)。设设A

30、=1,2,3A=1,2,3，求，求A A上所有的等价关系及其对应的商集。上所有的等价关系及其对应的商集。231231231231231 (a) (b) (c) (d) (e)(a) (b) (c) (d) (e)322022-3-272022-3-27例例7.2.87.2.8( (续）续）假设由假设由S Si i导出的对应等价关系为导出的对应等价关系为R Ri i，i=1,2,3,4,5i=1,2,3,4,5，则有则有 R R1 1=S=S1 1S S1 1=A=AA A， A/RA/R1 1=1,2,3=1,2,3； R R2 2=1,2=1,21,231,2333 =, =, A/R A/

31、R2 2=1,2,3=1,2,3； R R3 3=1,3=1,31,321,3222 =, =, A/RA/R3 3=1,3,2=1,3,2；332022-3-272022-3-27例例7.2.87.2.8( (续）续）R R4 4=2,3=2,32,312,3111 =, =,， A/RA/R4 4=1,2,3=1,2,3；R R5 5=1=11212232333 =,= =,=I IA A， A/RA/R5 5=1,2,3=1,2,3。 342022-3-272022-3-27例例7.2.97.2.9设设R R是是A A上的自反和传递关系上的自反和传递关系，S S也是也是A A上的关系，且

32、上的关系，且满足：满足：S S (RR)(7.2.2)(RR)(7.2.2)证明证明 S S是是A A上的等价关系。上的等价关系。证明证明（1 1）S S是自反的：是自反的：对任意对任意aAaA，因，因R R是自反的，所以是自反的，所以RR，由，由RR并且并且RR和和(7.2.2)(7.2.2)得得SS，即即S S是自反的。是自反的。352022-3-272022-3-27例例7.2.9 (7.2.9 (续续) )（2 2）S S是对称的：是对称的：对对 a,bAa,bA，若，若SS，则由，则由(7.2.2)(7.2.2)得得RR并且并且RR，即有，即有RR并且并且RR，所以有，所以有SS，即

33、即S S是对称的。是对称的。362022-3-272022-3-27例例7.2.9 (7.2.9 (续续) )（3 3）S S是传递的：是传递的：对对 a,b,cAa,b,cA，若，若SS，SS，则由，则由(7.2.2)(7.2.2)得得RR且且RR和和RR且且RR。因为因为R R是传递的，所以有是传递的，所以有RR和和RR。从而，。从而，SS，即即S S是传递的。是传递的。由由(1),(2)(1),(2)和和(3)(3)知，知，S S是是A A上的一个等价关系。上的一个等价关系。372022-3-272022-3-27例例7.2.10 7.2.10 设设R R是集合是集合A A上的一个关系上

34、的一个关系. .对对 a,b,cAa,b,cA，若，若RR并且并且RR，则有，则有RR，则，则R R称为称为A A上的循环关系。上的循环关系。试证明试证明R R是是A A上的一个等价关系的充要条件是上的一个等价关系的充要条件是R R是是循环关系和自反关系。循环关系和自反关系。382022-3-272022-3-27例例7.2.10 7.2.10 证明证明“” 若若R R是等价关系是等价关系。1)1)、显然、显然R R是自反的是自反的。2)2)、对任意、对任意a,b,cAa,b,cA，若，若R,RR,R，则由则由R R是对称的，有是对称的，有RR并且并且RR，由，由R R是是传递的，所以，传递的

35、，所以，RR。即。即R R是循环的关系是循环的关系。由由1)1)，2)2)知知R R是自反的和循环的。是自反的和循环的。392022-3-272022-3-27“” 若若R R是自反的和循环的。是自反的和循环的。1)1)、 显然显然R R是是自反性自反性的；的；2)2)、对任意、对任意a,ba,bA,A,若若R,R,则由则由R R是自反的是自反的, ,有有R R，因，因R R是循环的，所以，是循环的，所以，R R且且R R R R，即即R R是对称的。是对称的。例例7.2.107.2.10证明证明( (续续) )402022-3-272022-3-273)3)、对任意、对任意a,b,ca,b,

36、cA A，若，若R R，R R，则由则由R R对称的，有对称的，有RR并且并且RR；由；由R R是是循环的，所以循环的，所以RR且且RRRR，即即R R是传递的。是传递的。由由1)1)、2)2)、3)3)知知R R是是A A上的一个等价关系上的一个等价关系。例例7.2.107.2.10证明证明( (续续) )412022-3-272022-3-277.2.67.2.6等价关系的应用等价关系的应用例例7.2.11 7.2.11 在图在图7.2.57.2.5中，中，点点i i和和j j之间有路当且仅当之间有路当且仅当从结点从结点i i通过图中的边能够到达结点通过图中的边能够到达结点j j。规定对任

37、意规定对任意结点结点i i，i i和和i i之间一定有路之间一定有路。定义。定义R R如下：如下：RRi i和和j j之间有路。之间有路。试说明该关系试说明该关系R R是否可以是否可以给定结点集给定结点集A=1,2,3,4,5,A=1,2,3,4,5,6,7,86,7,8一个划分？如果能，一个划分？如果能，请给出具体的划分。请给出具体的划分。图图7.2.575683124422022-3-272022-3-27例例7.2.11 7.2.11 解解（1 1）由于规定任意结点）由于规定任意结点i i与他自身之间一定有路，因与他自身之间一定有路，因此此RR，即，即R R具有自反性具有自反性；（2 2

38、）若）若RR，则两个结点，则两个结点i i和和j j之间存在路，当然之间存在路，当然也存在也存在j j和和i i之间的路，所以之间的路，所以RR，即，即R R具有对称性具有对称性；（3 3）若）若R,RR,R，则结点，则结点i i和和j j之间有路，之间有路，j j和和k k之间也有路，从而之间也有路，从而i i到到k k之间存在经过之间存在经过j j的路，即有的路，即有RR，因此得到，因此得到R R具有传递性。具有传递性。由由(1)(1)、(2)(2)和和(3)(3)知，知，R R是等价关系。是等价关系。432022-3-272022-3-27例例7.2.11 7.2.11 解解( (续续)

39、 )于是所有不同的等价类为：于是所有不同的等价类为：11R R=1,2,3,4=1,2,3,4，55R R=5,6,7=5,6,7，88R R=8=8。根据定理根据定理7.2.27.2.2知，知，A/R=1A/R=1R R,5,5R R,8,8R R=1,2,3,4, 5,6,7,8=1,2,3,4, 5,6,7,8就是就是A A的一个划分。的一个划分。442022-3-272022-3-27总结总结1 1、熟记等价关系的定义；、熟记等价关系的定义；2 2、利用等价关系的定义证明一个关系是等价关、利用等价关系的定义证明一个关系是等价关系；系；3 3、给定、给定A A上的等价关系上的等价关系R

40、R，会求所有的等价类和，会求所有的等价类和商集商集A/RA/R；并求出对应的集合的划分；并求出对应的集合的划分；4 4、给定集合、给定集合A A上的划分，会求对应的等价类。上的划分，会求对应的等价类。452022-3-272022-3-27判定下列关系具有哪些性质判定下列关系具有哪些性质1 1、对任何非空集合、对任何非空集合A A，A A上的恒等关系；上的恒等关系；2 2、多边形的、多边形的“相似关系相似关系”、“全等关系全等关系”；3 3、集合、集合A A的幂集的幂集P P( (A)A)上定义上定义的的“包含关系包含关系”；4 4、集合、集合A A的幂集的幂集P P( (A)A)上定义上定义

41、的的“真包含关系真包含关系”。解：解：1 1，2 2都都具有具有 3 3 具有具有反对称性和传递性；反对称性和传递性； 4 4 具有具有反对称性，反对称性， 传递性。传递性。偏序偏序关系关系拟序关拟序关系系462022-3-272022-3-277.3 7.3 次序关系次序关系拍摄一张室内闪光灯照片，需要完成如下任务：拍摄一张室内闪光灯照片，需要完成如下任务：1 1、打开镜头盖；、打开镜头盖；2 2、照相机调焦；、照相机调焦；3 3、打开闪光灯；、打开闪光灯；4 4、按下快门按钮。、按下快门按钮。这些任务中有的必须在其他任务之前完成。这些任务中有的必须在其他任务之前完成。例如，例如，任务任务1

42、 1必须在任务必须在任务2 2之前完成，任务之前完成，任务2 2，3 3必须在任务必须在任务4 4之前完成，即任务之间存在之前完成，即任务之间存在“先后先后”关系，即次关系，即次序关系。序关系。472022-3-272022-3-277.3.17.3.1拟序关系拟序关系定义定义7.3.1 7.3.1 设设R R是非空集合是非空集合A A上的关系，如果上的关系，如果R R是是反自反自反和传递的反和传递的，则称，则称R R是是A A上的拟序关系上的拟序关系(Quasi-(Quasi-OrderRelation)OrderRelation)，简称，简称拟序拟序，记为，记为“”，读作，读作“小小于于”

43、，并将，并将“”记为记为“a ab b”。序偶序偶A, 称为拟序集称为拟序集(Quasi-OrderSet)(Quasi-OrderSet)。482022-3-272022-3-27由定义由定义7.3.17.3.1知：知：（1 1）R R是拟序关系是拟序关系R R同时具有反自反性和传递同时具有反自反性和传递性性；（2 2）R R不是拟序不是拟序关系关系R R不具有反自反性或者传不具有反自反性或者传递性递性；（3 3）拟序）拟序“”的的逆关系逆关系“-1-1”也是拟序，也是拟序，用用“”表示，读作表示，读作“大于大于”。492022-3-272022-3-27例例7.3.17.3.1设设R R是

44、集合是集合A A上的拟序关系，则上的拟序关系，则R R是反对称的。是反对称的。 假设假设R R不是反对称的关系不是反对称的关系，则必存在，则必存在x,yAx,yA，且且xyxy，满足，满足RR并且并且RR。因为。因为R R是是A A上上的拟序关系，所以的拟序关系，所以R R具有传递性，从而有具有传递性，从而有RR。这与这与R R是反自反的矛盾，从而假设错误，即是反自反的矛盾，从而假设错误，即R R一定是一定是反对称的。反对称的。502022-3-272022-3-27例例7.3.27.3.2判断下列关系是否为拟序关系判断下列关系是否为拟序关系（1 1）集合）集合A A的的幂集幂集P(A)P(A

45、)上定义的上定义的“ ”；（2 2）实数集）实数集R R上定义的上定义的“小于小于”关系关系( () )；解（解（1 1）集合）集合A A的幂集的幂集P(A)P(A)上定义的上定义的“ ”具有反自具有反自反性和传递性，反性和传递性，所以所以P(A), 是拟序集是拟序集。（2 2）实数集合）实数集合R R上定义的上定义的“小于小于”关系关系( () )具有反具有反自反性和传递性自反性和传递性，所以，所以R, 是拟序集是拟序集。512022-3-272022-3-277.3.27.3.2偏序关系偏序关系 设设R R是非空集合是非空集合A A上的关系，上的关系，如果如果R R是自反是自反的、反对称的

46、和传递的的、反对称的和传递的，则称，则称R R是是A A上的上的偏序关系偏序关系(PartialOrderRelation)(PartialOrderRelation)，简称偏序，记为，简称偏序，记为“”，读作读作“小于等于小于等于”，并将，并将“”记为记为abab。序偶序偶称为偏序集称为偏序集(PartialOrderSet)(PartialOrderSet)。522022-3-272022-3-27由定义由定义7.3.27.3.2知知（1 1）R R是偏序关系是偏序关系R R同时同时具有自反性、反对称性具有自反性、反对称性和传递性和传递性；（2 2）R R不是偏序关系不是偏序关系R R不具

47、备自反性或反对称性不具备自反性或反对称性或传递性或传递性；（3 3）偏序）偏序“”的逆关系的逆关系“- -1 1”也是一个偏序，也是一个偏序，我们用我们用“”表示，读作表示，读作“大于等于大于等于”；（4 4）( (“”-I-IA A) )为为A A上的上的拟序关系拟序关系，( (“”I IA A) )为为A A上的上的偏序关系偏序关系。 532022-3-272022-3-27试判断下列关系是否为偏序关系试判断下列关系是否为偏序关系集合集合A A的幂集的幂集P P( (A)A)上的上的包含包含关系关系“ ”；实数集合实数集合R R上的上的小于小于等于关系等于关系“”“”；自然数集合自然数集合

48、N N上的上的模模m m同余关系；同余关系；例例7.3.37.3.3偏序集偏序集偏序集偏序集不具有反对称不具有反对称性性542022-3-272022-3-27例例7.3.57.3.5考虑任务集考虑任务集T T，它包含了拍摄一张室内闪光照片必须按，它包含了拍摄一张室内闪光照片必须按顺序完成的任务：顺序完成的任务：1 1、打开镜头盖；、打开镜头盖；2 2、照相机调焦；、照相机调焦；3 3、打开闪光灯；、打开闪光灯；4 4、按下快门按钮。、按下快门按钮。在在T T上定义关系上定义关系R R如下：如下：R R如果如果i=ji=j或者任务或者任务i i必须在任务必须在任务j j之前完成。之前完成。试判

49、断试判断R R是是T T上的偏序关系并画出它的关系图。上的偏序关系并画出它的关系图。552022-3-272022-3-27例例7.3.5 7.3.5 解解根据根据R R的定义，有的定义，有R=,R=,。根据自反、反对称和根据自反、反对称和传递的定义知，关系传递的定义知，关系R R具有自反性，对称性具有自反性，对称性和传递性。从而和传递性。从而R R是偏是偏序关系，其关系图如右图所示。序关系，其关系图如右图所示。1234562022-3-272022-3-272 2 哈斯图哈斯图（1 1）用）用小圆圈或点表示小圆圈或点表示A A中的元素中的元素，省掉关系图中，省掉关系图中所有的环；所有的环；（

50、2 2）对任意）对任意x,yAx,yA，若若x xy y，则将，则将x x画在画在y y的下方，的下方，可省掉关系图中所有边的箭头；可省掉关系图中所有边的箭头；（3 3）对任意）对任意x,yA(xy)x,yA(xy)，若若xyxy，且，且x x与与y y之间之间不存在不存在zAzA，使得，使得xz,zyxz,zy，则，则x x与与y y之间用一条之间用一条线相连，线相连，否则无线相连否则无线相连。（因自反性（因自反性) )（因反对称性）（因反对称性）（因传递性）（因传递性）572022-3-272022-3-27例例7.3.77.3.7设设A=2,3,6,12,24,36A=2,3,6,12,

51、24,36，“”是是A A上的整除关系上的整除关系R R，画出其一般的关系图和哈斯图。画出其一般的关系图和哈斯图。解解关系图关系图哈斯图哈斯图2 23 36 61212363624242 23 36 6121236362424582022-3-272022-3-273 3 特殊元素特殊元素设设是偏序集，是偏序集，B B是是A A的任何一个子的任何一个子集集，若，若存在元素存在元素bBbB，使得，使得（1 1）都有都有xbxb, ,则称则称b b为为B B的最大元素的最大元素, ,简称简称最大元最大元（2 2）都有都有bxbx, ,则称则称b b为为B B的最小元素，简称的最小元素，简称最小元最

52、小元（3 3）满足满足bxbxx=bx=b，则称则称b b为为B B的极大元素的极大元素, ,简称简称极大元极大元；（4 4）满足满足xbxbx=bx=b，则称，则称b b为为B B的极小元素的极小元素, ,简称简称极小元极小元。592022-3-272022-3-27定义定义7.3.37.3.3可以符号化为：可以符号化为：bB( x)(xB)(xb)1 是 的最大元bB( x)(xB)(bx)1 是 的最小元bB( xB)(bx)(bx)1 是 的极大元bB( xB)(xb)(bx)1 是 的极小元602022-3-272022-3-27注意注意（1 1）B B的最大元、最小元、极大元和极小

53、元如果存的最大元、最小元、极大元和极小元如果存在，一定在在，一定在B B中；中；（2 2）b b是是B B的最大元的最大元B B中所有的元素都比中所有的元素都比b b小；小； b b是是B B的最小元的最小元B B中所有的元素都比中所有的元素都比b b大；大； b b是是B B的极大元的极大元B B中没有比中没有比b b大的元素；大的元素； b b是是B B的极小元的极小元B B中没有比中没有比b b小的元素。小的元素。612022-3-272022-3-27例例7.3.87.3.8设设B B1 1=6,12=6,12，B B2 2=2,3=2,3，B B3 3=24, =24, 3636，B

54、 B4 4=2,3,6,12=2,3,6,12是集合是集合A A（见左（见左边哈斯图）的子集，边哈斯图）的子集，试求出试求出B B1 1,B,B2 2, , B B3 3和和B B4 4的最大元，最小元，极大元和的最大元，最小元，极大元和极小元。极小元。集合最大元最小元极大元极小元B1B1 12 12 6 6 12 12 6 6B2B2 无无 无无 2,32,3 2,3 2,3B3B3 无无 无无 24,3624,36 24,36 24,36B4B4 12 12 无无 1212 2,3 2,32 23 36 6121236362424622022-3-272022-3-27定义定义7.3.47

55、.3.4设设是偏序集，是偏序集，B B是是A A的任何一个子集。若存在元素的任何一个子集。若存在元素aAaA，使得，使得（1 1）对）对任意任意xBxB，都有，都有xaxa，则称，则称a a为为B B的的上界上界；（2 2）对）对任意任意xBxB，都有，都有axax，则称则称a a为为B B的的下界下界；（3 3）若元素）若元素aAaA是是B B的上界，元素的上界，元素aAaA是是B B的任何一个的任何一个上界，若均有上界，若均有aaaa，则称，则称aa为为B B的的最小上界或上确界最小上界或上确界。记记a=SupBa=SupB；（4 4）若元素）若元素aAaA是是B B的下界，元素的下界，元

56、素aAaA是是B B的任何一个的任何一个下界，若均有下界，若均有aaaa，则称，则称aa为为B B的的最大下界或下确界最大下界或下确界。记记a=InfBa=InfB。632022-3-272022-3-27由定义由定义7.3.47.3.4知知（1 1）子集合子集合B B的上、下界和上、下确界可在的上、下界和上、下确界可在集合集合A A中寻找；中寻找；（2 2）一个子集合）一个子集合B B的的上、下界不一定存在上、下界不一定存在，如果存，如果存在，在，可以不唯一的可以不唯一的；（3 3）一个子集合）一个子集合B B的的上、下确界不一定存在上、下确界不一定存在，如果，如果存在，存在，一定唯一一定唯

57、一；（4 4）一个子集合）一个子集合B B有上有上( (下下) )确界，一定有上确界，一定有上( (下下) )界界，反之不然。反之不然。642022-3-272022-3-27例例7.3.97.3.9集合集合A A的哈斯图如右图所示，设的哈斯图如右图所示，设B B1 1=6,12=6,12，B B2 2=2,3=2,3是集合是集合A A的子的子集，集，试求出试求出B B1 1，B B2 2的上界、下界、的上界、下界、上确界和下确界。上确界和下确界。集合集合上界上界下界下界上确界上确界下确界下确界B B1 112,24,3612,24,362,3,62,3,612126 6B B2 26,12,

58、24,366,12,24,36无无6 6无无2 23 36 6121236362424652022-3-272022-3-27例例7.3.117.3.11设集合设集合A A=a,b,c,d,e,f,g,h=a,b,c,d,e,f,g,h，对应，对应的哈斯图见图右图。令的哈斯图见图右图。令B B1 1=a,b=a,b，B B2 2=c,d,e=c,d,e。求出。求出B B1 1，B B2 2的最大元、的最大元、最小元、极大元、极小元、上界、最小元、极大元、极小元、上界、下界、上确界、下确界。下界、上确界、下确界。eabcdfgh662022-3-272022-3-27定理定理7.3.17.3.1

59、设设是一偏序集，是一偏序集，B B是是A A的子集。的子集。则：则：（1 1）若）若b b是是B B的最大元的最大元b b是是B B的极大元、上界、上的极大元、上界、上确界；确界；（2 2）若）若b b是是B B的最小元的最小元b b是是B B的极小元、下界、下的极小元、下界、下确界；确界；（3 3）若）若a a是是B B的上确界，且的上确界，且aBaBa a是是B B的最大元；的最大元；（4 4）若）若a a是是B B的下确界，且的下确界，且aBaBa a是是B B的最小元。的最小元。672022-3-272022-3-27定理定理7.3.27.3.2设设是一偏序集，是一偏序集，B B是是A

60、 A的子集。则：的子集。则：（1 1）若）若B B存在最大元，则存在最大元，则B B的最大元是惟一的；的最大元是惟一的；（2 2）若）若B B存在最小元，则存在最小元，则B B的最小元是惟一的；的最小元是惟一的；（3 3）b b是是B B的最大元的最大元b b是是B B的惟一极大元；的惟一极大元；（4 4）b b是是B B的最小元的最小元b b是是B B的惟一极小元；的惟一极小元；（5 5）若）若B B存在上确界，则存在上确界，则B B的上确界是惟一的；的上确界是惟一的；（6 6）若）若B B存在下确界，则存在下确界，则B B的下确界是惟一的。的下确界是惟一的。682022-3-272022-